1// BabyJubJub elliptic curve implementation in Rust.
  2// For LICENSE check https://github.com/arnaucube/babyjubjub-rs
  3
  4extern crate num;
  5extern crate num_bigint;
  6extern crate num_traits;
  7
  8use num_bigint::{BigInt, ToBigInt};
  9use num_traits::{One, Zero};
 10
 11pub fn modulus(a: &BigInt, m: &BigInt) -> BigInt {
 12    ((a % m) + m) % m
 13}
 14
 15pub fn modinv(a: &BigInt, q: &BigInt) -> Result<BigInt, String> {
 16    let big_zero: BigInt = Zero::zero();
 17    if a == &big_zero {
 18        return Err("no mod inv of Zero".to_string());
 19    }
 20
 21    let mut mn = (q.clone(), a.clone());
 22    let mut xy: (BigInt, BigInt) = (Zero::zero(), One::one());
 23
 24    while mn.1 != big_zero {
 25        xy = (xy.1.clone(), xy.0 - (mn.0.clone() / mn.1.clone()) * xy.1);
 26        mn = (mn.1.clone(), modulus(&mn.0, &mn.1));
 27    }
 28
 29    while xy.0 < Zero::zero() {
 30        xy.0 = modulus(&xy.0, q);
 31    }
 32    Ok(xy.0)
 33}
 34
 35/*
 36pub fn modinv_v2(a0: &BigInt, m0: &BigInt) -> BigInt {
 37    if m0 == &One::one() {
 38        return One::one();
 39    }
 40
 41    let (mut a, mut m, mut x0, mut inv): (BigInt, BigInt, BigInt, BigInt) =
 42        (a0.clone(), m0.clone(), Zero::zero(), One::one());
 43
 44    while a > One::one() {
 45        inv = inv - (&a / m.clone()) * x0.clone();
 46        a = a % m.clone();
 47        std::mem::swap(&mut a, &mut m);
 48        std::mem::swap(&mut x0, &mut inv);
 49    }
 50
 51    if inv < Zero::zero() {
 52        inv += m0.clone()
 53    }
 54    inv
 55}
 56
 57pub fn modinv_v3(a: &BigInt, q: &BigInt) -> BigInt {
 58    let mut aa: BigInt = a.clone();
 59    let mut qq: BigInt = q.clone();
 60    if qq < Zero::zero() {
 61        qq = -qq;
 62    }
 63    if aa < Zero::zero() {
 64        aa = -aa;
 65    }
 66    let d = num::Integer::gcd(&aa, &qq);
 67    if d != One::one() {
 68        println!("ERR no mod_inv");
 69    }
 70    let res: BigInt;
 71    if d < Zero::zero() {
 72        res = d + qq;
 73    } else {
 74        res = d;
 75    }
 76    res
 77}
 78pub fn modinv_v4(x: &BigInt, q: &BigInt) -> BigInt {
 79    let (gcd, inverse, _) = extended_gcd(x.clone(), q.clone());
 80    let one: BigInt = One::one();
 81    if gcd == one {
 82        modulus(&inverse, q)
 83    } else {
 84        panic!("error: gcd!=one")
 85    }
 86}
 87pub fn extended_gcd(a: BigInt, b: BigInt) -> (BigInt, BigInt, BigInt) {
 88    let (mut s, mut old_s) = (BigInt::zero(), BigInt::one());
 89    let (mut t, mut old_t) = (BigInt::one(), BigInt::zero());
 90    let (mut r, mut old_r) = (b, a);
 91
 92    while r != BigInt::zero() {
 93        let quotient = &old_r / &r;
 94        old_r -= &quotient * &r;
 95        std::mem::swap(&mut old_r, &mut r);
 96        old_s -= &quotient * &s;
 97        std::mem::swap(&mut old_s, &mut s);
 98        old_t -= quotient * &t;
 99        std::mem::swap(&mut old_t, &mut t);
100    }
101
102    let _quotients = (t, s); // == (a, b) / gcd
103
104    (old_r, old_s, old_t)
105}
106*/
107
108pub fn concatenate_arrays<T: Clone>(x: &[T], y: &[T]) -> Vec<T> {
109    x.iter().chain(y).cloned().collect()
110}
111
112#[allow(clippy::many_single_char_names)]
113pub fn modsqrt(a: &BigInt, q: &BigInt) -> Result<BigInt, String> {
114    // Tonelli-Shanks Algorithm (https://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm)
115    //
116    // This implementation is following the Go lang core implementation https://golang.org/src/math/big/int.go?s=23173:23210#L859
117    // Also described in https://www.maa.org/sites/default/files/pdf/upload_library/22/Polya/07468342.di020786.02p0470a.pdf
118    // -> section 6
119
120    let zero: BigInt = Zero::zero();
121    let one: BigInt = One::one();
122    if legendre_symbol(&a, q) != 1 || a == &zero || q == &2.to_bigint().unwrap() {
123        return Err("not a mod p square".to_string());
124    } else if q % 4.to_bigint().unwrap() == 3.to_bigint().unwrap() {
125        let r = a.modpow(&((q + one) / 4), &q);
126        return Ok(r);
127    }
128
129    let mut s = q - &one;
130    let mut e: BigInt = Zero::zero();
131    while &s % 2 == zero {
132        s >>= 1;
133        e += &one;
134    }
135
136    let mut n: BigInt = 2.to_bigint().unwrap();
137    while legendre_symbol(&n, q) != -1 {
138        n = &n + &one;
139    }
140
141    let mut y = a.modpow(&((&s + &one) >> 1), q);
142    let mut b = a.modpow(&s, q);
143    let mut g = n.modpow(&s, q);
144    let mut r = e;
145
146    loop {
147        let mut t = b.clone();
148        let mut m: BigInt = Zero::zero();
149        while t != one {
150            t = modulus(&(&t * &t), q);
151            m += &one;
152        }
153
154        if m == zero {
155            return Ok(y);
156        }
157
158        t = g.modpow(&(2.to_bigint().unwrap().modpow(&(&r - &m - 1), q)), q);
159        g = g.modpow(&(2.to_bigint().unwrap().modpow(&(r - &m), q)), q);
160        y = modulus(&(y * t), q);
161        b = modulus(&(b * &g), q);
162        r = m.clone();
163    }
164}
165
166#[allow(dead_code)]
167#[allow(clippy::many_single_char_names)]
168pub fn modsqrt_v2(a: &BigInt, q: &BigInt) -> Result<BigInt, String> {
169    // Tonelli-Shanks Algorithm (https://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm)
170    //
171    // This implementation is following this Python implementation by Dusk https://github.com/dusk-network/dusk-zerocaf/blob/master/tools/tonelli.py
172
173    let zero: BigInt = Zero::zero();
174    let one: BigInt = One::one();
175    if legendre_symbol(&a, q) != 1 || a == &zero || q == &2.to_bigint().unwrap() {
176        return Err("not a mod p square".to_string());
177    } else if q % 4.to_bigint().unwrap() == 3.to_bigint().unwrap() {
178        let r = a.modpow(&((q + one) / 4), &q);
179        return Ok(r);
180    }
181
182    let mut p = q - &one;
183    let mut s: BigInt = Zero::zero();
184    while &p % 2.to_bigint().unwrap() == zero {
185        s += &one;
186        p >>= 1;
187    }
188
189    let mut z: BigInt = One::one();
190    while legendre_symbol(&z, q) != -1 {
191        z = &z + &one;
192    }
193    let mut c = z.modpow(&p, q);
194
195    let mut x = a.modpow(&((&p + &one) >> 1), q);
196    let mut t = a.modpow(&p, q);
197    let mut m = s;
198
199    while t != one {
200        let mut i: BigInt = One::one();
201        let mut e: BigInt = 2.to_bigint().unwrap();
202        while i < m {
203            if t.modpow(&e, q) == one {
204                break;
205            }
206            e *= 2.to_bigint().unwrap();
207            i += &one;
208        }
209
210        let b = c.modpow(&(2.to_bigint().unwrap().modpow(&(&m - &i - 1), q)), q);
211        x = modulus(&(x * &b), q);
212        t = modulus(&(t * &b * &b), q);
213        c = modulus(&(&b * &b), q);
214        m = i.clone();
215    }
216    Ok(x)
217}
218
219pub fn legendre_symbol(a: &BigInt, q: &BigInt) -> i32 {
220    // returns 1 if has a square root modulo q
221    let one: BigInt = One::one();
222    let ls: BigInt = a.modpow(&((q - &one) >> 1), &q);
223    if ls == q - one {
224        return -1;
225    }
226    1
227}
228
229#[cfg(test)]
230mod tests {
231    use super::*;
232
233    #[test]
234    fn test_mod_inverse() {
235        let a = BigInt::parse_bytes(b"123456789123456789123456789123456789123456789", 10).unwrap();
236        let b = BigInt::parse_bytes(b"12345678", 10).unwrap();
237        assert_eq!(
238            modinv(&a, &b).unwrap(),
239            BigInt::parse_bytes(b"641883", 10).unwrap()
240        );
241    }
242
243    #[test]
244    fn test_sqrtmod() {
245        let a = BigInt::parse_bytes(
246            b"6536923810004159332831702809452452174451353762940761092345538667656658715568",
247            10,
248        )
249        .unwrap();
250        let q = BigInt::parse_bytes(
251            b"7237005577332262213973186563042994240857116359379907606001950938285454250989",
252            10,
253        )
254        .unwrap();
255
256        assert_eq!(
257            (modsqrt(&a, &q).unwrap()).to_string(),
258            "5464794816676661649783249706827271879994893912039750480019443499440603127256"
259        );
260        assert_eq!(
261            (modsqrt_v2(&a, &q).unwrap()).to_string(),
262            "5464794816676661649783249706827271879994893912039750480019443499440603127256"
263        );
264    }
265}