babyjubjub-rs/src/lib.rs
src/lib.rsRaw
1#[macro_use]
2extern crate arrayref;
3extern crate generic_array;
4extern crate mimc_rs;
5extern crate num;
6extern crate num_bigint;
7extern crate num_traits;
8extern crate rand;
9
10use blake2::{Blake2b, Digest};
11use mimc_rs::Mimc7;
12
13use num_bigint::{BigInt, RandBigInt, Sign, ToBigInt};
14use num_traits::{One, Zero};
15
16use generic_array::GenericArray;
17
18mod utils;
19
20#[derive(Clone, Debug)]
21pub struct Point {
22 pub x: BigInt,
23 pub y: BigInt,
24}
25
26pub struct Signature {
27 r_b8: Point,
28 s: BigInt,
29}
30
31pub struct PrivateKey {
32 bbjj: Babyjubjub,
33 key: BigInt,
34}
35
36impl PrivateKey {
37 pub fn public(&self) -> Point {
38 // https://tools.ietf.org/html/rfc8032#section-5.1.5
39 let pk = &self.bbjj.mul_scalar(self.bbjj.b8.clone(), self.key.clone());
40 pk.clone()
41 }
42
43 pub fn sign(&self, msg: BigInt) -> Signature {
44 // https://tools.ietf.org/html/rfc8032#section-5.1.6
45 let mut hasher = Blake2b::new();
46 let (_, sk_bytes) = self.key.to_bytes_be();
47 hasher.input(sk_bytes);
48 let mut h = hasher.result(); // h: hash(sk)
49 // s: h[32:64]
50 let s = GenericArray::<u8, generic_array::typenum::U32>::from_mut_slice(&mut h[32..64]);
51 let (_, msg_bytes) = msg.to_bytes_be();
52 let r_bytes = utils::concatenate_arrays(s, &msg_bytes);
53 let mut r = BigInt::from_bytes_be(Sign::Plus, &r_bytes[..]);
54 r = utils::modulus(&r, &self.bbjj.sub_order);
55 let r8: Point = self.bbjj.mul_scalar(self.bbjj.b8.clone(), r.clone());
56 // let a = &self.sk_to_pk(sk.clone());
57 let a = &self.public();
58
59 let hm_input = vec![r8.x.clone(), r8.y.clone(), a.x.clone(), a.y.clone(), msg];
60 let mimc7 = Mimc7::new();
61 let hm = mimc7.hash(hm_input);
62
63 let mut s = &self.key << 3;
64 s = hm * s;
65 s = r + s;
66 s = s % &self.bbjj.sub_order;
67
68 Signature {
69 r_b8: r8.clone(),
70 s: s,
71 }
72 }
73}
74
75pub struct Babyjubjub {
76 d: BigInt,
77 a: BigInt,
78 q: BigInt,
79 b8: Point,
80 // order: BigInt,
81 sub_order: BigInt,
82}
83
84impl Babyjubjub {
85 pub fn new() -> Babyjubjub {
86 let d: BigInt = BigInt::parse_bytes(b"168696", 10).unwrap();
87 let a: BigInt = BigInt::parse_bytes(b"168700", 10).unwrap();
88 let q: BigInt = BigInt::parse_bytes(
89 b"21888242871839275222246405745257275088548364400416034343698204186575808495617",
90 10,
91 )
92 .unwrap();
93 let b8: Point = Point {
94 x: BigInt::parse_bytes(
95 b"5299619240641551281634865583518297030282874472190772894086521144482721001553",
96 10,
97 )
98 .unwrap(),
99 y: BigInt::parse_bytes(
100 b"16950150798460657717958625567821834550301663161624707787222815936182638968203",
101 10,
102 )
103 .unwrap(),
104 };
105 let order: BigInt = BigInt::parse_bytes(
106 b"21888242871839275222246405745257275088614511777268538073601725287587578984328",
107 10,
108 )
109 .unwrap();
110 let sub_order: BigInt = &order >> 3;
111
112 Babyjubjub {
113 d: d,
114 a: a,
115 q: q,
116 b8: b8,
117 // order: order,
118 sub_order: sub_order,
119 }
120 }
121
122 pub fn add(&self, p: &Point, q: &Point) -> Point {
123 // x = (x1*y2+y1*x2)/(c*(1+d*x1*x2*y1*y2))
124 // y = (y1*y2-x1*x2)/(c*(1-d*x1*x2*y1*y2))
125
126 // x = (x1 * y2 + y1 * x2) / (1 + d * x1 * y1 * y2)
127 let one: BigInt = One::one();
128 let x_num: BigInt = &p.x * &q.y + &p.y * &q.x;
129 let x_den: BigInt = &one + &self.d * &p.x * &q.x * &p.y * &q.y;
130 let x_den_inv = utils::modinv(&x_den, &self.q);
131 let x: BigInt = utils::modulus(&(&x_num * &x_den_inv), &self.q);
132
133 // y = (y1 * y2 - a * x1 * x2) / (1 - d * x1 * x2 * y1 * y2)
134 let y_num = &p.y * &q.y - &self.a * &p.x * &q.x;
135 let y_den = utils::modulus(&(&one - &self.d * &p.x * &q.x * &p.y * &q.y), &self.q);
136 let y_den_inv = utils::modinv(&y_den, &self.q);
137 let y: BigInt = utils::modulus(&(&y_num * &y_den_inv), &self.q);
138
139 Point { x: x, y: y }
140 }
141
142 pub fn mul_scalar(&self, p: Point, n: BigInt) -> Point {
143 // TODO use & in p and n to avoid clones on function call
144 let mut r: Point = Point {
145 x: Zero::zero(),
146 y: One::one(),
147 };
148 let mut rem: BigInt = n;
149 let mut exp: Point = p;
150
151 let zero: BigInt = Zero::zero();
152 let one: BigInt = One::one();
153 while rem != zero {
154 let is_odd = &rem & &one == one;
155 if is_odd == true {
156 r = self.add(&r, &exp);
157 }
158 exp = self.add(&exp, &exp);
159 rem = rem >> 1;
160 }
161 r.x = utils::modulus(&r.x, &self.q);
162 r.y = utils::modulus(&r.y, &self.q);
163 r
164 }
165
166 pub fn compress(&self, p: Point) -> [u8; 32] {
167 let mut r: [u8; 32];
168 let (_, y_bytes) = p.y.to_bytes_le();
169 r = *array_ref!(y_bytes, 0, 32);
170 if &p.x > &(&self.q >> 1) {
171 r[31] = r[31] | 0x80;
172 }
173 r
174 }
175
176 pub fn decompress_point(&self, bb: [u8; 32]) -> Point {
177 // https://tools.ietf.org/html/rfc8032#section-5.2.3
178 let mut sign: bool = false;
179 let mut b = bb.clone();
180 if b[31] & 0x80 != 0x00 {
181 sign = true;
182 b[31] = b[31] & 0x7F;
183 }
184 let y: BigInt = BigInt::from_bytes_le(Sign::Plus, &b[..]);
185 if y >= self.q {
186 // println!("ERROR0");
187 }
188 let one: BigInt = One::one();
189
190 // x^2 = (1 - y^2) / (a - d * y^2) (mod p)
191 let mut x: BigInt = utils::modulus(
192 &((one - utils::modulus(&(&y * &y), &self.q))
193 * utils::modinv(
194 &utils::modulus(
195 &(&self.a - utils::modulus(&(&self.d * (&y * &y)), &self.q)),
196 &self.q,
197 ),
198 &self.q,
199 )),
200 &self.q,
201 );
202 x = utils::modsqrt(&x, &self.q);
203
204 if (sign && x >= Zero::zero()) || (!sign && x < Zero::zero()) {
205 x = x * -1.to_bigint().unwrap();
206 }
207 x = utils::modulus(&x, &self.q);
208 Point { x: x, y: y }
209 }
210
211 pub fn new_key(&self) -> PrivateKey {
212 // https://tools.ietf.org/html/rfc8032#section-5.1.5
213 let mut rng = rand::thread_rng();
214 let sk_raw = rng.gen_biguint(1024).to_bigint().unwrap();
215
216 let mut hasher = Blake2b::new();
217 let (_, sk_raw_bytes) = sk_raw.to_bytes_be();
218 hasher.input(sk_raw_bytes);
219 let mut h = hasher.result();
220
221 h[0] = h[0] & 0xF8;
222 h[31] = h[31] & 0x7F;
223 h[31] = h[31] | 0x40;
224
225 let sk = BigInt::from_bytes_le(Sign::Plus, &h[..]);
226
227 let bbjj_new = Babyjubjub {
228 d: self.d.clone(),
229 a: self.a.clone(),
230 q: self.q.clone(),
231 b8: self.b8.clone(),
232 sub_order: self.sub_order.clone(),
233 };
234 PrivateKey {
235 bbjj: bbjj_new,
236 key: sk,
237 }
238 }
239
240 pub fn verify(&self, pk: Point, sig: Signature, msg: BigInt) -> bool {
241 let hm_input = vec![
242 sig.r_b8.x.clone(),
243 sig.r_b8.y.clone(),
244 pk.x.clone(),
245 pk.y.clone(),
246 msg,
247 ];
248 let mimc7 = Mimc7::new();
249 let hm = mimc7.hash(hm_input);
250 let l = self.mul_scalar(self.b8.clone(), sig.s);
251 let r = self.add(&sig.r_b8, &self.mul_scalar(pk, 8.to_bigint().unwrap() * hm));
252 if l.x == r.x && l.y == r.y {
253 return true;
254 }
255 false
256 }
257}
258
259#[cfg(test)]
260mod tests {
261 use super::*;
262 extern crate rustc_hex;
263 use rustc_hex::ToHex;
264
265 #[test]
266 fn test_add_same_point() {
267 let p: Point = Point {
268 x: BigInt::parse_bytes(
269 b"17777552123799933955779906779655732241715742912184938656739573121738514868268",
270 10,
271 )
272 .unwrap(),
273 y: BigInt::parse_bytes(
274 b"2626589144620713026669568689430873010625803728049924121243784502389097019475",
275 10,
276 )
277 .unwrap(),
278 };
279 let q: Point = Point {
280 x: BigInt::parse_bytes(
281 b"17777552123799933955779906779655732241715742912184938656739573121738514868268",
282 10,
283 )
284 .unwrap(),
285 y: BigInt::parse_bytes(
286 b"2626589144620713026669568689430873010625803728049924121243784502389097019475",
287 10,
288 )
289 .unwrap(),
290 };
291 let bbjj = Babyjubjub::new();
292 let res = bbjj.add(&p, &q);
293 assert_eq!(
294 res.x.to_string(),
295 "6890855772600357754907169075114257697580319025794532037257385534741338397365"
296 );
297 assert_eq!(
298 res.y.to_string(),
299 "4338620300185947561074059802482547481416142213883829469920100239455078257889"
300 );
301 }
302 #[test]
303 fn test_add_different_points() {
304 let p: Point = Point {
305 x: BigInt::parse_bytes(
306 b"17777552123799933955779906779655732241715742912184938656739573121738514868268",
307 10,
308 )
309 .unwrap(),
310 y: BigInt::parse_bytes(
311 b"2626589144620713026669568689430873010625803728049924121243784502389097019475",
312 10,
313 )
314 .unwrap(),
315 };
316 let q: Point = Point {
317 x: BigInt::parse_bytes(
318 b"16540640123574156134436876038791482806971768689494387082833631921987005038935",
319 10,
320 )
321 .unwrap(),
322 y: BigInt::parse_bytes(
323 b"20819045374670962167435360035096875258406992893633759881276124905556507972311",
324 10,
325 )
326 .unwrap(),
327 };
328 let bbjj = Babyjubjub::new();
329 let res = bbjj.add(&p, &q);
330 assert_eq!(
331 res.x.to_string(),
332 "7916061937171219682591368294088513039687205273691143098332585753343424131937"
333 );
334 assert_eq!(
335 res.y.to_string(),
336 "14035240266687799601661095864649209771790948434046947201833777492504781204499"
337 );
338 }
339
340 #[test]
341 fn test_mul_scalar() {
342 let p: Point = Point {
343 x: BigInt::parse_bytes(
344 b"17777552123799933955779906779655732241715742912184938656739573121738514868268",
345 10,
346 )
347 .unwrap(),
348 y: BigInt::parse_bytes(
349 b"2626589144620713026669568689430873010625803728049924121243784502389097019475",
350 10,
351 )
352 .unwrap(),
353 };
354 let bbjj = Babyjubjub::new();
355 let res_m = bbjj.mul_scalar(p.clone(), 3.to_bigint().unwrap());
356 let res_a = bbjj.add(&p, &p);
357 let res_a = bbjj.add(&res_a, &p);
358 assert_eq!(res_m.x, res_a.x);
359 assert_eq!(
360 res_m.x.to_string(),
361 "19372461775513343691590086534037741906533799473648040012278229434133483800898"
362 );
363 assert_eq!(
364 res_m.y.to_string(),
365 "9458658722007214007257525444427903161243386465067105737478306991484593958249"
366 );
367
368 let n = BigInt::parse_bytes(
369 b"14035240266687799601661095864649209771790948434046947201833777492504781204499",
370 10,
371 )
372 .unwrap();
373 let res2 = bbjj.mul_scalar(p.clone(), n);
374 assert_eq!(
375 res2.x.to_string(),
376 "17070357974431721403481313912716834497662307308519659060910483826664480189605"
377 );
378 assert_eq!(
379 res2.y.to_string(),
380 "4014745322800118607127020275658861516666525056516280575712425373174125159339"
381 );
382 }
383
384 #[test]
385 fn test_point_compress_decompress() {
386 let bbjj = Babyjubjub::new();
387 let p: Point = Point {
388 x: BigInt::parse_bytes(
389 b"17777552123799933955779906779655732241715742912184938656739573121738514868268",
390 10,
391 )
392 .unwrap(),
393 y: BigInt::parse_bytes(
394 b"2626589144620713026669568689430873010625803728049924121243784502389097019475",
395 10,
396 )
397 .unwrap(),
398 };
399 let p_comp = bbjj.compress(p.clone());
400 assert_eq!(
401 p_comp[..].to_hex(),
402 "53b81ed5bffe9545b54016234682e7b2f699bd42a5e9eae27ff4051bc698ce85"
403 );
404 let p2 = bbjj.decompress_point(p_comp);
405 assert_eq!(p.x, p2.x);
406 assert_eq!(p.y, p2.y);
407 }
408
409 #[test]
410 fn test_new_key_sign_verify0() {
411 let bbjj = Babyjubjub::new();
412 let sk = bbjj.new_key();
413 let pk = sk.public();
414 let msg = 5.to_bigint().unwrap();
415 let sig = sk.sign(msg.clone());
416 let v = bbjj.verify(pk, sig, msg);
417 assert_eq!(v, true);
418 }
419
420 #[test]
421 fn test_new_key_sign_verify1() {
422 let bbjj = Babyjubjub::new();
423 let sk = bbjj.new_key();
424 let pk = sk.public();
425 let msg = BigInt::parse_bytes(b"123456789012345678901234567890", 10).unwrap();
426 let sig = sk.sign(msg.clone());
427 let v = bbjj.verify(pk, sig, msg);
428 assert_eq!(v, true);
429 }
430}