1//! An ECDLP instance Q = d·G on a prime-order curve, plus the optional order-3 automorphism data.23use crate::curve::{Counters, Curve, Pt};4use crate::field::Modn;56#[derive(Clone, Copy, Debug)]7pub struct Instance {8 pub curve: Curve,9 pub n: Modn,10 pub g: Pt,11 pub q: Pt,12 /// β (Montgomery form) with (βx, y) = λ·(x, y); only for a = 0, p ≡ 1 (mod 3), n ≡ 1 (mod 3)13 pub beta: Option<u64>,14 pub lambda: Option<u64>,15}1617impl Instance {18 #[allow(clippy::too_many_arguments)]19 pub fn new(p: u64, a: u64, b: u64, n: u64, gx: u64, gy: u64, qx: u64, qy: u64) -> Result<Instance, String> {20 let curve = Curve::new(p, a, b);21 let g = curve.point_from_std(gx, gy);22 let q = curve.point_from_std(qx, qy);23 if !curve.is_on_curve(&g) {24 return Err("G is not on the curve".into());25 }26 if !curve.is_on_curve(&q) {27 return Err("Q is not on the curve".into());28 }29 if g.inf {30 return Err("G must not be the point at infinity".into());31 }32 let mut c = Counters::default();33 if !curve.mul(n, &g, &mut c).inf {34 return Err("n·G != O: n is not the order of G".into());35 }36 Ok(Instance { curve, n: Modn::new(n), g, q, beta: None, lambda: None })37 }3839 /// Install (β, λ) and verify φ(G) = (β·gx, gy) = λ·G on this instance; abort otherwise.40 pub fn with_aut3(mut self, beta_std: u64, lambda: u64) -> Result<Instance, String> {41 let f = &self.curve.f;42 if self.curve.a_std != 0 {43 return Err("--aut3 requires a = 0 (j-invariant 0)".into());44 }45 if f.p % 3 != 1 || self.n.n % 3 != 1 {46 return Err("--aut3 requires p ≡ 1 (mod 3) and n ≡ 1 (mod 3)".into());47 }48 if beta_std == 0 || beta_std >= f.p || beta_std == 1 {49 return Err("beta must satisfy 1 < beta < p".into());50 }51 if lambda <= 1 || lambda >= self.n.n {52 return Err("lambda must satisfy 1 < lambda < n".into());53 }54 if f.pow_plain(beta_std, 3) != 1 {55 return Err("beta^3 != 1 mod p".into());56 }57 if self.n.pow(lambda, 3) != 1 {58 return Err("lambda^3 != 1 mod n".into());59 }60 let beta = f.to_mont(beta_std);61 let phi_g = Pt::new(f.mul(beta, self.g.x), self.g.y);62 let mut c = Counters::default();63 let lam_g = self.curve.mul(lambda, &self.g, &mut c);64 if !self.curve.eq(&phi_g, &lam_g) {65 return Err("(beta*gx, gy) != lambda*G: wrong (beta, lambda) pair for this G".into());66 }67 self.beta = Some(beta);68 self.lambda = Some(lambda);69 Ok(self)70 }7172 /// Check d·G == Q (counted in `c`).73 pub fn verify(&self, d: u64, c: &mut Counters) -> bool {74 let r = self.curve.mul(d % self.n.n, &self.g, c);75 self.curve.eq(&r, &self.q)76 }7778 /// ⌈log2 n⌉79 pub fn bits(&self) -> u32 {80 64 - self.n.n.leading_zeros()81 }82}8384/// Integer square root (floor) of a u128.85pub fn isqrt(n: u128) -> u128 {86 if n < 2 {87 return n;88 }89 let mut x = (n as f64).sqrt() as u128; // float only as a starting guess; corrected exactly below90 while x * x > n {91 x -= 1;92 }93 while (x + 1) * (x + 1) <= n {94 x += 1;95 }96 x97}9899/// ⌈√n⌉100pub fn isqrt_ceil(n: u128) -> u128 {101 let r = isqrt(n);102 if r * r == n {103 r104 } else {105 r + 1106 }107}108109/// 64-bit mixing function (splitmix64 finaliser) used for partition / distinguished-point tests.110#[inline(always)]111pub fn mix64(x: u64) -> u64 {112 let mut z = x.wrapping_add(0x9E3779B97F4A7C15);113 z = (z ^ (z >> 30)).wrapping_mul(0xBF58476D1CE4E5B9);114 z = (z ^ (z >> 27)).wrapping_mul(0x94D049BB133111EB);115 z ^ (z >> 31)116}117118/// Partition index in [0, r) from the high 32 bits of mix64(x) (multiply-high, no division).119#[inline(always)]120pub fn partition(x: u64, r: u64) -> u32 {121 (((mix64(x) >> 32) * r) >> 32) as u32122}123124/// Distinguished-point predicate: the low `dp_bits` bits of mix64(x) are zero.125#[inline(always)]126pub fn is_distinguished(x: u64, dp_mask: u64) -> bool {127 (mix64(x) & dp_mask) == 0128}129