1use num::rational::Ratio;
  2use num::BigUint;
  3use plonky2::field::secp256k1_base::Secp256K1Base;
  4use plonky2::field::secp256k1_scalar::Secp256K1Scalar;
  5use plonky2::field::types::{Field, PrimeField};
  6
  7use crate::curve::curve_msm::msm_parallel;
  8use crate::curve::curve_types::{AffinePoint, ProjectivePoint};
  9use crate::curve::secp256k1::Secp256K1;
 10
 11pub const GLV_BETA: Secp256K1Base = Secp256K1Base([
 12    13923278643952681454,
 13    11308619431505398165,
 14    7954561588662645993,
 15    8856726876819556112,
 16]);
 17
 18pub const GLV_S: Secp256K1Scalar = Secp256K1Scalar([
 19    16069571880186789234,
 20    1310022930574435960,
 21    11900229862571533402,
 22    6008836872998760672,
 23]);
 24
 25const A1: Secp256K1Scalar = Secp256K1Scalar([16747920425669159701, 3496713202691238861, 0, 0]);
 26
 27const MINUS_B1: Secp256K1Scalar =
 28    Secp256K1Scalar([8022177200260244675, 16448129721693014056, 0, 0]);
 29
 30const A2: Secp256K1Scalar = Secp256K1Scalar([6323353552219852760, 1498098850674701302, 1, 0]);
 31
 32const B2: Secp256K1Scalar = Secp256K1Scalar([16747920425669159701, 3496713202691238861, 0, 0]);
 33
 34/// Algorithm 15.41 in Handbook of Elliptic and Hyperelliptic Curve Cryptography.
 35///
 36/// Decompose a scalar `k` into two small scalars `k1, k2` with `|k1|, |k2| < √p` that satisfy
 37/// `k1 + s * k2 = k`.
 38/// Returns `(|k1|, |k2|, k1 < 0, k2 < 0)`.
 39pub fn decompose_secp256k1_scalar(
 40    k: Secp256K1Scalar,
 41) -> (Secp256K1Scalar, Secp256K1Scalar, bool, bool) {
 42    let p = Secp256K1Scalar::order();
 43    let c1_biguint = Ratio::new(
 44        B2.to_canonical_biguint() * k.to_canonical_biguint(),
 45        p.clone(),
 46    )
 47    .round()
 48    .to_integer();
 49    let c1 = Secp256K1Scalar::from_noncanonical_biguint(c1_biguint);
 50    let c2_biguint = Ratio::new(
 51        MINUS_B1.to_canonical_biguint() * k.to_canonical_biguint(),
 52        p.clone(),
 53    )
 54    .round()
 55    .to_integer();
 56    let c2 = Secp256K1Scalar::from_noncanonical_biguint(c2_biguint);
 57
 58    let k1_raw = k - c1 * A1 - c2 * A2;
 59    let k2_raw = c1 * MINUS_B1 - c2 * B2;
 60    debug_assert!(k1_raw + GLV_S * k2_raw == k);
 61
 62    let two = BigUint::from_slice(&[2]);
 63    let k1_neg = k1_raw.to_canonical_biguint() > p.clone() / two.clone();
 64    let k1 = if k1_neg {
 65        Secp256K1Scalar::from_noncanonical_biguint(p.clone() - k1_raw.to_canonical_biguint())
 66    } else {
 67        k1_raw
 68    };
 69    let k2_neg = k2_raw.to_canonical_biguint() > p.clone() / two;
 70    let k2 = if k2_neg {
 71        Secp256K1Scalar::from_noncanonical_biguint(p - k2_raw.to_canonical_biguint())
 72    } else {
 73        k2_raw
 74    };
 75
 76    (k1, k2, k1_neg, k2_neg)
 77}
 78
 79/// See Section 15.2.1 in Handbook of Elliptic and Hyperelliptic Curve Cryptography.
 80///
 81/// GLV scalar multiplication `k * P = k1 * P + k2 * psi(P)`, where `k = k1 + s * k2` is the
 82/// decomposition computed in `decompose_secp256k1_scalar(k)` and `psi` is the Secp256k1
 83/// endomorphism `psi: (x, y) |-> (beta * x, y)` equivalent to scalar multiplication by `s`.
 84pub fn glv_mul(p: ProjectivePoint<Secp256K1>, k: Secp256K1Scalar) -> ProjectivePoint<Secp256K1> {
 85    let (k1, k2, k1_neg, k2_neg) = decompose_secp256k1_scalar(k);
 86
 87    let p_affine = p.to_affine();
 88    let sp = AffinePoint::<Secp256K1> {
 89        x: p_affine.x * GLV_BETA,
 90        y: p_affine.y,
 91        zero: p_affine.zero,
 92    };
 93
 94    let first = if k1_neg { p.neg() } else { p };
 95    let second = if k2_neg {
 96        sp.to_projective().neg()
 97    } else {
 98        sp.to_projective()
 99    };
100
101    msm_parallel(&[k1, k2], &[first, second], 5)
102}
103
104#[cfg(test)]
105mod tests {
106    use anyhow::Result;
107    use plonky2::field::secp256k1_scalar::Secp256K1Scalar;
108    use plonky2::field::types::{Field, Sample};
109
110    use crate::curve::curve_types::{Curve, CurveScalar};
111    use crate::curve::glv::{decompose_secp256k1_scalar, glv_mul, GLV_S};
112    use crate::curve::secp256k1::Secp256K1;
113
114    #[test]
115    fn test_glv_decompose() -> Result<()> {
116        let k = Secp256K1Scalar::rand();
117        let (k1, k2, k1_neg, k2_neg) = decompose_secp256k1_scalar(k);
118        let one = Secp256K1Scalar::ONE;
119        let m1 = if k1_neg { -one } else { one };
120        let m2 = if k2_neg { -one } else { one };
121
122        assert!(k1 * m1 + GLV_S * k2 * m2 == k);
123
124        Ok(())
125    }
126
127    #[test]
128    fn test_glv_mul() -> Result<()> {
129        for _ in 0..20 {
130            let k = Secp256K1Scalar::rand();
131
132            let p = CurveScalar(Secp256K1Scalar::rand()) * Secp256K1::GENERATOR_PROJECTIVE;
133
134            let kp = CurveScalar(k) * p;
135            let glv = glv_mul(p, k);
136
137            assert!(kp == glv);
138        }
139
140        Ok(())
141    }
142}