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