1#![no_std]
2
3extern crate alloc;
4extern crate byteorder;
5#[macro_use]
6extern crate crunchy;
7#[macro_use]
8extern crate lazy_static;
9extern crate rand;
10#[cfg(feature = "rustc-serialize")]
11extern crate rustc_serialize;
12
13pub mod arith;
14mod fields;
15mod groups;
16
17use fields::FieldElement;
18use groups::{G1Params, G2Params, GroupElement, GroupParams};
19
20use alloc::vec::Vec;
21use core::{ops::{Add, Mul, Neg, Sub}, str::FromStr};
22use rand::Rng;
23
24#[derive(Copy, Clone, Debug, PartialEq, Eq)]
25#[cfg_attr(feature = "rustc-serialize", derive(RustcDecodable, RustcEncodable))]
26#[repr(C)]
27pub struct Fr(fields::Fr);
28
29impl Fr {
30 pub fn zero() -> Self {
31 Fr(fields::Fr::zero())
32 }
33 pub fn one() -> Self {
34 Fr(fields::Fr::one())
35 }
36 pub fn random<R: Rng>(rng: &mut R) -> Self {
37 Fr(fields::Fr::random(rng))
38 }
39 pub fn pow(&self, exp: Fr) -> Self {
40 Fr(self.0.pow(exp.0))
41 }
42 pub fn inverse(&self) -> Option<Self> {
43 self.0.inverse().map(Fr)
44 }
45 pub fn is_zero(&self) -> bool {
46 self.0.is_zero()
47 }
48 pub fn interpret(buf: &[u8; 64]) -> Fr {
49 Fr(fields::Fr::interpret(buf))
50 }
51 pub fn from_slice(slice: &[u8]) -> Result<Self, FieldError> {
52 arith::U256::from_slice(slice)
53 .map_err(|_| FieldError::InvalidSliceLength) .map(Fr::new_mul_factor)
55 }
56 pub fn to_big_endian(&self, slice: &mut [u8]) -> Result<(), FieldError> {
57 self.0
58 .raw()
59 .to_big_endian(slice)
60 .map_err(|_| FieldError::InvalidSliceLength)
61 }
62 pub fn new(val: arith::U256) -> Option<Self> {
63 fields::Fr::new(val).map(Fr)
64 }
65 pub fn new_mul_factor(val: arith::U256) -> Self {
66 Fr(fields::Fr::new_mul_factor(val))
67 }
68 pub fn into_u256(self) -> arith::U256 {
69 (self.0).into()
70 }
71 pub fn set_bit(&mut self, bit: usize, to: bool) {
72 self.0.set_bit(bit, to);
73 }
74}
75
76impl FromStr for Fr {
77 type Err = ();
78
79 fn from_str(s: &str) -> Result<Self, Self::Err> {
80 fields::Fr::from_str(s).map(Fr).ok_or(())
81 }
82}
83
84impl Add<Fr> for Fr {
85 type Output = Fr;
86
87 fn add(self, other: Fr) -> Fr {
88 Fr(self.0 + other.0)
89 }
90}
91
92impl Sub<Fr> for Fr {
93 type Output = Fr;
94
95 fn sub(self, other: Fr) -> Fr {
96 Fr(self.0 - other.0)
97 }
98}
99
100impl Neg for Fr {
101 type Output = Fr;
102
103 fn neg(self) -> Fr {
104 Fr(-self.0)
105 }
106}
107
108impl Mul for Fr {
109 type Output = Fr;
110
111 fn mul(self, other: Fr) -> Fr {
112 Fr(self.0 * other.0)
113 }
114}
115
116#[derive(Debug)]
117pub enum FieldError {
118 InvalidSliceLength,
119 InvalidU512Encoding,
120 NotMember,
121}
122
123#[derive(Debug)]
124pub enum CurveError {
125 InvalidEncoding,
126 NotMember,
127 Field(FieldError),
128 ToAffineConversion,
129}
130
131impl From<FieldError> for CurveError {
132 fn from(fe: FieldError) -> Self {
133 CurveError::Field(fe)
134 }
135}
136
137pub use groups::Error as GroupError;
138
139#[derive(Copy, Clone, Debug, PartialEq, Eq)]
140#[cfg_attr(feature = "rustc-serialize", derive(RustcDecodable, RustcEncodable))]
141#[repr(C)]
142pub struct Fq(fields::Fq);
143
144impl Fq {
145 pub fn zero() -> Self {
146 Fq(fields::Fq::zero())
147 }
148 pub fn one() -> Self {
149 Fq(fields::Fq::one())
150 }
151 pub fn random<R: Rng>(rng: &mut R) -> Self {
152 Fq(fields::Fq::random(rng))
153 }
154 pub fn pow(&self, exp: Fq) -> Self {
155 Fq(self.0.pow(exp.0))
156 }
157 pub fn inverse(&self) -> Option<Self> {
158 self.0.inverse().map(Fq)
159 }
160 pub fn is_zero(&self) -> bool {
161 self.0.is_zero()
162 }
163 pub fn interpret(buf: &[u8; 64]) -> Fq {
164 Fq(fields::Fq::interpret(buf))
165 }
166 pub fn from_slice(slice: &[u8]) -> Result<Self, FieldError> {
167 arith::U256::from_slice(slice)
168 .map_err(|_| FieldError::InvalidSliceLength) .and_then(|x| fields::Fq::new(x).ok_or(FieldError::NotMember))
170 .map(Fq)
171 }
172 pub fn to_big_endian(&self, slice: &mut [u8]) -> Result<(), FieldError> {
173 let mut a: arith::U256 = self.0.into();
174 a.mul(
176 fields::Fq::one().raw(),
177 &fields::Fq::modulus(),
178 self.0.inv(),
179 );
180 a.to_big_endian(slice)
181 .map_err(|_| FieldError::InvalidSliceLength)
182 }
183 pub fn from_u256(u256: arith::U256) -> Result<Self, FieldError> {
184 Ok(Fq(fields::Fq::new(u256).ok_or(FieldError::NotMember)?))
185 }
186 pub fn into_u256(self) -> arith::U256 {
187 (self.0).into()
188 }
189 pub fn modulus() -> arith::U256 {
190 fields::Fq::modulus()
191 }
192
193 pub fn sqrt(&self) -> Option<Self> {
194 self.0.sqrt().map(Fq)
195 }
196}
197
198impl FromStr for Fq {
199 type Err = ();
200
201 fn from_str(s: &str) -> Result<Self, Self::Err> {
202 fields::Fq::from_str(s).map(Fq).ok_or(())
203 }
204}
205
206impl Add<Fq> for Fq {
207 type Output = Fq;
208
209 fn add(self, other: Fq) -> Fq {
210 Fq(self.0 + other.0)
211 }
212}
213
214impl Sub<Fq> for Fq {
215 type Output = Fq;
216
217 fn sub(self, other: Fq) -> Fq {
218 Fq(self.0 - other.0)
219 }
220}
221
222impl Neg for Fq {
223 type Output = Fq;
224
225 fn neg(self) -> Fq {
226 Fq(-self.0)
227 }
228}
229
230impl Mul for Fq {
231 type Output = Fq;
232
233 fn mul(self, other: Fq) -> Fq {
234 Fq(self.0 * other.0)
235 }
236}
237
238#[derive(Copy, Clone, Debug, PartialEq, Eq)]
239#[repr(C)]
240pub struct Fq2(fields::Fq2);
241
242impl Fq2 {
243 pub fn one() -> Fq2 {
244 Fq2(fields::Fq2::one())
245 }
246
247 pub fn i() -> Fq2 {
248 Fq2(fields::Fq2::i())
249 }
250
251 pub fn zero() -> Fq2 {
252 Fq2(fields::Fq2::zero())
253 }
254
255 pub fn new(a: Fq, b: Fq) -> Fq2 {
257 Fq2(fields::Fq2::new(a.0, b.0))
258 }
259
260 pub fn is_zero(&self) -> bool {
261 self.0.is_zero()
262 }
263
264 pub fn pow(&self, exp: arith::U256) -> Self {
265 Fq2(self.0.pow(exp))
266 }
267
268 pub fn real(&self) -> Fq {
269 Fq(*self.0.real())
270 }
271
272 pub fn imaginary(&self) -> Fq {
273 Fq(*self.0.imaginary())
274 }
275
276 pub fn sqrt(&self) -> Option<Self> {
277 self.0.sqrt().map(Fq2)
278 }
279
280 pub fn from_slice(bytes: &[u8]) -> Result<Self, FieldError> {
281 let u512 = arith::U512::from_slice(bytes).map_err(|_| FieldError::InvalidU512Encoding)?;
282 let (res, c0) = u512.divrem(&Fq::modulus());
283 Ok(Fq2::new(
284 Fq::from_u256(c0).map_err(|_| FieldError::NotMember)?,
285 Fq::from_u256(res.ok_or(FieldError::NotMember)?).map_err(|_| FieldError::NotMember)?,
286 ))
287 }
288}
289
290impl Add<Fq2> for Fq2 {
291 type Output = Self;
292
293 fn add(self, other: Self) -> Self {
294 Fq2(self.0 + other.0)
295 }
296}
297
298impl Sub<Fq2> for Fq2 {
299 type Output = Self;
300
301 fn sub(self, other: Self) -> Self {
302 Fq2(self.0 - other.0)
303 }
304}
305
306impl Neg for Fq2 {
307 type Output = Self;
308
309 fn neg(self) -> Self {
310 Fq2(-self.0)
311 }
312}
313
314impl Mul for Fq2 {
315 type Output = Self;
316
317 fn mul(self, other: Self) -> Self {
318 Fq2(self.0 * other.0)
319 }
320}
321
322pub trait Group:
323 Send
324 + Sync
325 + Copy
326 + Clone
327 + PartialEq
328 + Eq
329 + Sized
330 + Add<Self, Output = Self>
331 + Sub<Self, Output = Self>
332 + Neg<Output = Self>
333 + Mul<Fr, Output = Self>
334{
335 fn zero() -> Self;
336 fn one() -> Self;
337 fn random<R: Rng>(rng: &mut R) -> Self;
338 fn is_zero(&self) -> bool;
339 fn normalize(&mut self);
340}
341
342#[derive(Copy, Clone, Debug, PartialEq, Eq)]
343#[cfg_attr(feature = "rustc-serialize", derive(RustcDecodable, RustcEncodable))]
344#[repr(C)]
345pub struct G1(groups::G1);
346
347impl G1 {
348 pub fn new(x: Fq, y: Fq, z: Fq) -> Self {
349 G1(groups::G1::new(x.0, y.0, z.0))
350 }
351
352 pub fn x(&self) -> Fq {
353 Fq(*self.0.x())
354 }
355
356 pub fn set_x(&mut self, x: Fq) {
357 *self.0.x_mut() = x.0
358 }
359
360 pub fn y(&self) -> Fq {
361 Fq(*self.0.y())
362 }
363
364 pub fn set_y(&mut self, y: Fq) {
365 *self.0.y_mut() = y.0
366 }
367
368 pub fn z(&self) -> Fq {
369 Fq(*self.0.z())
370 }
371
372 pub fn set_z(&mut self, z: Fq) {
373 *self.0.z_mut() = z.0
374 }
375
376 pub fn b() -> Fq {
377 Fq(G1Params::coeff_b())
378 }
379
380 pub fn from_compressed(bytes: &[u8]) -> Result<Self, CurveError> {
381 if bytes.len() != 33 {
382 return Err(CurveError::InvalidEncoding);
383 }
384
385 let sign = bytes[0];
386 let fq = Fq::from_slice(&bytes[1..])?;
387 let x = fq;
388 let y_squared = (fq * fq * fq) + Self::b();
389
390 let mut y = y_squared.sqrt().ok_or(CurveError::NotMember)?;
391
392 if (sign == 2 && y.into_u256().get_bit(0).expect("bit 0 always exist; qed"))
393 || (sign == 3 && !y.into_u256().get_bit(0).expect("bit 0 always exist; qed"))
394 {
395 y = y.neg();
396 } else if sign != 3 && sign != 2 {
397 return Err(CurveError::InvalidEncoding);
398 }
399 AffineG1::new(x, y)
400 .map_err(|_| CurveError::NotMember)
401 .map(Into::into)
402 }
403}
404
405impl Group for G1 {
406 fn zero() -> Self {
407 G1(groups::G1::zero())
408 }
409 fn one() -> Self {
410 G1(groups::G1::one())
411 }
412 fn random<R: Rng>(rng: &mut R) -> Self {
413 G1(groups::G1::random(rng))
414 }
415 fn is_zero(&self) -> bool {
416 self.0.is_zero()
417 }
418 fn normalize(&mut self) {
419 let new = match self.0.to_affine() {
420 Some(a) => a,
421 None => return,
422 };
423
424 self.0 = new.to_jacobian();
425 }
426}
427
428impl Add<G1> for G1 {
429 type Output = G1;
430
431 fn add(self, other: G1) -> G1 {
432 G1(self.0 + other.0)
433 }
434}
435
436impl Sub<G1> for G1 {
437 type Output = G1;
438
439 fn sub(self, other: G1) -> G1 {
440 G1(self.0 - other.0)
441 }
442}
443
444impl Neg for G1 {
445 type Output = G1;
446
447 fn neg(self) -> G1 {
448 G1(-self.0)
449 }
450}
451
452impl Mul<Fr> for G1 {
453 type Output = G1;
454
455 fn mul(self, other: Fr) -> G1 {
456 G1(self.0 * other.0)
457 }
458}
459
460#[derive(Copy, Clone, Debug, PartialEq, Eq)]
461#[cfg_attr(feature = "rustc-serialize", derive(RustcDecodable, RustcEncodable))]
462#[repr(C)]
463pub struct AffineG1(groups::AffineG1);
464
465impl AffineG1 {
466 pub fn new(x: Fq, y: Fq) -> Result<Self, GroupError> {
467 Ok(AffineG1(groups::AffineG1::new(x.0, y.0)?))
468 }
469
470 pub fn x(&self) -> Fq {
471 Fq(*self.0.x())
472 }
473
474 pub fn set_x(&mut self, x: Fq) {
475 *self.0.x_mut() = x.0
476 }
477
478 pub fn y(&self) -> Fq {
479 Fq(*self.0.y())
480 }
481
482 pub fn set_y(&mut self, y: Fq) {
483 *self.0.y_mut() = y.0
484 }
485
486 pub fn from_jacobian(g1: G1) -> Option<Self> {
487 g1.0.to_affine().map(AffineG1)
488 }
489}
490
491impl From<AffineG1> for G1 {
492 fn from(affine: AffineG1) -> Self {
493 G1(affine.0.to_jacobian())
494 }
495}
496
497#[derive(Copy, Clone, Debug, PartialEq, Eq)]
498#[cfg_attr(feature = "rustc-serialize", derive(RustcDecodable, RustcEncodable))]
499#[repr(C)]
500pub struct G2(groups::G2);
501
502impl G2 {
503 pub fn new(x: Fq2, y: Fq2, z: Fq2) -> Self {
504 G2(groups::G2::new(x.0, y.0, z.0))
505 }
506
507 pub fn x(&self) -> Fq2 {
508 Fq2(*self.0.x())
509 }
510
511 pub fn set_x(&mut self, x: Fq2) {
512 *self.0.x_mut() = x.0
513 }
514
515 pub fn y(&self) -> Fq2 {
516 Fq2(*self.0.y())
517 }
518
519 pub fn set_y(&mut self, y: Fq2) {
520 *self.0.y_mut() = y.0
521 }
522
523 pub fn z(&self) -> Fq2 {
524 Fq2(*self.0.z())
525 }
526
527 pub fn set_z(&mut self, z: Fq2) {
528 *self.0.z_mut() = z.0
529 }
530
531 pub fn b() -> Fq2 {
532 Fq2(G2Params::coeff_b())
533 }
534
535 pub fn from_compressed(bytes: &[u8]) -> Result<Self, CurveError> {
536 if bytes.len() != 65 {
537 return Err(CurveError::InvalidEncoding);
538 }
539
540 let sign = bytes[0];
541 let x = Fq2::from_slice(&bytes[1..])?;
542
543 let y_squared = (x * x * x) + G2::b();
544 let y = y_squared.sqrt().ok_or(CurveError::NotMember)?;
545 let y_neg = -y;
546
547 let y_gt = y.0.to_u512() > y_neg.0.to_u512();
548
549 let e_y = if sign == 10 {
550 if y_gt { y_neg } else { y }
551 } else if sign == 11 {
552 if y_gt { y } else { y_neg }
553 } else {
554 return Err(CurveError::InvalidEncoding);
555 };
556
557 AffineG2::new(x, e_y)
558 .map_err(|_| CurveError::NotMember)
559 .map(Into::into)
560 }
561}
562
563impl Group for G2 {
564 fn zero() -> Self {
565 G2(groups::G2::zero())
566 }
567 fn one() -> Self {
568 G2(groups::G2::one())
569 }
570 fn random<R: Rng>(rng: &mut R) -> Self {
571 G2(groups::G2::random(rng))
572 }
573 fn is_zero(&self) -> bool {
574 self.0.is_zero()
575 }
576 fn normalize(&mut self) {
577 let new = match self.0.to_affine() {
578 Some(a) => a,
579 None => return,
580 };
581
582 self.0 = new.to_jacobian();
583 }
584}
585
586impl Add<G2> for G2 {
587 type Output = G2;
588
589 fn add(self, other: G2) -> G2 {
590 G2(self.0 + other.0)
591 }
592}
593
594impl Sub<G2> for G2 {
595 type Output = G2;
596
597 fn sub(self, other: G2) -> G2 {
598 G2(self.0 - other.0)
599 }
600}
601
602impl Neg for G2 {
603 type Output = G2;
604
605 fn neg(self) -> G2 {
606 G2(-self.0)
607 }
608}
609
610impl Mul<Fr> for G2 {
611 type Output = G2;
612
613 fn mul(self, other: Fr) -> G2 {
614 G2(self.0 * other.0)
615 }
616}
617
618#[derive(Copy, Clone, PartialEq, Eq)]
619#[repr(C)]
620pub struct Gt(fields::Fq12);
621
622impl Gt {
623 pub fn one() -> Self {
624 Gt(fields::Fq12::one())
625 }
626 pub fn pow(&self, exp: Fr) -> Self {
627 Gt(self.0.pow(exp.0))
628 }
629 pub fn inverse(&self) -> Option<Self> {
630 self.0.inverse().map(Gt)
631 }
632 pub fn final_exponentiation(&self) -> Option<Self> {
633 self.0.final_exponentiation().map(Gt)
634 }
635}
636
637impl Mul<Gt> for Gt {
638 type Output = Gt;
639
640 fn mul(self, other: Gt) -> Gt {
641 Gt(self.0 * other.0)
642 }
643}
644
645pub fn pairing(p: G1, q: G2) -> Gt {
646 Gt(groups::pairing(&p.0, &q.0))
647}
648
649pub fn pairing_batch(pairs: &[(G1, G2)]) -> Gt {
650 let mut ps: Vec<groups::G1> = Vec::new();
651 let mut qs: Vec<groups::G2> = Vec::new();
652 for (p, q) in pairs {
653 ps.push(p.0);
654 qs.push(q.0);
655 }
656 Gt(groups::pairing_batch(&ps, &qs))
657}
658
659pub fn miller_loop_batch(pairs: &[(G2, G1)]) -> Result<Gt, CurveError> {
660 let mut ps: Vec<groups::G2Precomp> = Vec::new();
661 let mut qs: Vec<groups::AffineG<groups::G1Params>> = Vec::new();
662 for (p, q) in pairs {
663 ps.push(
664 p.0.to_affine()
665 .ok_or(CurveError::ToAffineConversion)?
666 .precompute(),
667 );
668 qs.push(q.0.to_affine().ok_or(CurveError::ToAffineConversion)?);
669 }
670 Ok(Gt(groups::miller_loop_batch(&ps, &qs)))
671}
672
673#[derive(Copy, Clone, PartialEq, Eq)]
674#[cfg_attr(feature = "rustc-serialize", derive(RustcDecodable, RustcEncodable))]
675#[repr(C)]
676pub struct AffineG2(groups::AffineG2);
677
678impl AffineG2 {
679 pub fn new(x: Fq2, y: Fq2) -> Result<Self, GroupError> {
680 Ok(AffineG2(groups::AffineG2::new(x.0, y.0)?))
681 }
682
683 pub fn x(&self) -> Fq2 {
684 Fq2(*self.0.x())
685 }
686
687 pub fn set_x(&mut self, x: Fq2) {
688 *self.0.x_mut() = x.0
689 }
690
691 pub fn y(&self) -> Fq2 {
692 Fq2(*self.0.y())
693 }
694
695 pub fn set_y(&mut self, y: Fq2) {
696 *self.0.y_mut() = y.0
697 }
698
699 pub fn from_jacobian(g2: G2) -> Option<Self> {
700 g2.0.to_affine().map(AffineG2)
701 }
702}
703
704impl From<AffineG2> for G2 {
705 fn from(affine: AffineG2) -> Self {
706 G2(affine.0.to_jacobian())
707 }
708}
709
710#[cfg(test)]
711mod tests {
712 use core::str::FromStr;
713 extern crate rustc_hex as hex;
714 use super::{Fq, Fq2, G1, G2};
715 use alloc::vec::Vec;
716
717 fn hex(s: &'static str) -> Vec<u8> {
718 use self::hex::FromHex;
719 s.from_hex().unwrap()
720 }
721
722 #[test]
723 fn g1_from_compressed() {
724 let g1 = G1::from_compressed(&hex(
725 "0230644e72e131a029b85045b68181585d97816a916871ca8d3c208c16d87cfd46",
726 ))
727 .expect("Invalid g1 decompress result");
728 assert_eq!(
729 g1.x(),
730 Fq::from_str(
731 "21888242871839275222246405745257275088696311157297823662689037894645226208582"
732 )
733 .unwrap()
734 );
735 assert_eq!(
736 g1.y(),
737 Fq::from_str(
738 "3969792565221544645472939191694882283483352126195956956354061729942568608776"
739 )
740 .unwrap()
741 );
742 assert_eq!(g1.z(), Fq::one());
743 }
744
745 #[test]
746 fn g2_from_compressed() {
747 let g2 = G2::from_compressed(
748 &hex("0a023aed31b5a9e486366ea9988b05dba469c6206e58361d9c065bbea7d928204a761efc6e4fa08ed227650134b52c7f7dd0463963e8a4bf21f4899fe5da7f984a")
749 ).expect("Valid g2 point hex encoding");
750
751 assert_eq!(
752 g2.x(),
753 Fq2::new(
754 Fq::from_str(
755 "5923585509243758863255447226263146374209884951848029582715967108651637186684"
756 )
757 .unwrap(),
758 Fq::from_str(
759 "5336385337059958111259504403491065820971993066694750945459110579338490853570"
760 )
761 .unwrap(),
762 )
763 );
764
765 assert_eq!(
766 g2.y(),
767 Fq2::new(
768 Fq::from_str(
769 "10374495865873200088116930399159835104695426846400310764827677226300185211748"
770 )
771 .unwrap(),
772 Fq::from_str(
773 "5256529835065685814318509161957442385362539991735248614869838648137856366932"
774 )
775 .unwrap(),
776 )
777 );
778
779 let g2 = -G2::from_compressed(
781 &hex("0b023aed31b5a9e486366ea9988b05dba469c6206e58361d9c065bbea7d928204a761efc6e4fa08ed227650134b52c7f7dd0463963e8a4bf21f4899fe5da7f984a")
782 ).expect("Valid g2 point hex encoding");
783
784 assert_eq!(
785 g2.x(),
786 Fq2::new(
787 Fq::from_str(
788 "5923585509243758863255447226263146374209884951848029582715967108651637186684"
789 )
790 .unwrap(),
791 Fq::from_str(
792 "5336385337059958111259504403491065820971993066694750945459110579338490853570"
793 )
794 .unwrap(),
795 )
796 );
797
798 assert_eq!(
799 g2.y(),
800 Fq2::new(
801 Fq::from_str(
802 "10374495865873200088116930399159835104695426846400310764827677226300185211748"
803 )
804 .unwrap(),
805 Fq::from_str(
806 "5256529835065685814318509161957442385362539991735248614869838648137856366932"
807 )
808 .unwrap(),
809 )
810 );
811
812 assert!(
814 G2::from_compressed(
815 &hex("0c023aed31b5a9e486366ea9988b05dba469c6206e58361d9c065bbea7d928204a761efc6e4fa08ed227650134b52c7f7dd0463963e8a4bf21f4899fe5da7f984a")
816 ).is_err()
817 );
818 }
819}