1use crate::factor::mod_inverse;
14use logicaffeine_base::BigInt;
15
16pub type Fp2 = (BigInt, BigInt);
18
19#[inline]
20fn ib(x: i64) -> BigInt {
21 BigInt::from_i64(x)
22}
23
24#[inline]
25fn rem_pos(a: &BigInt, p: &BigInt) -> BigInt {
26 let r = a.div_rem(p).map(|(_, r)| r).unwrap_or_else(|| a.clone());
27 if r.is_negative() {
28 r.add(p)
29 } else {
30 r
31 }
32}
33
34#[inline]
35fn m(a: &BigInt, b: &BigInt, p: &BigInt) -> BigInt {
36 rem_pos(&a.mul(b), p)
37}
38#[inline]
39fn s(a: &BigInt, b: &BigInt, p: &BigInt) -> BigInt {
40 rem_pos(&a.sub(b), p)
41}
42#[inline]
43fn a_(a: &BigInt, b: &BigInt, p: &BigInt) -> BigInt {
44 rem_pos(&a.add(b), p)
45}
46
47pub fn fp2_const(k: i64, p: &BigInt) -> Fp2 {
49 (rem_pos(&ib(k), p), ib(0))
50}
51
52pub fn fp2_add(x: &Fp2, y: &Fp2, p: &BigInt) -> Fp2 {
53 (a_(&x.0, &y.0, p), a_(&x.1, &y.1, p))
54}
55pub fn fp2_sub(x: &Fp2, y: &Fp2, p: &BigInt) -> Fp2 {
56 (s(&x.0, &y.0, p), s(&x.1, &y.1, p))
57}
58pub fn fp2_neg(x: &Fp2, p: &BigInt) -> Fp2 {
59 (s(&ib(0), &x.0, p), s(&ib(0), &x.1, p))
60}
61
62pub fn fp2_mul(x: &Fp2, y: &Fp2, p: &BigInt) -> Fp2 {
64 let ac = m(&x.0, &y.0, p);
65 let bd = m(&x.1, &y.1, p);
66 let ad = m(&x.0, &y.1, p);
67 let bc = m(&x.1, &y.0, p);
68 (s(&ac, &bd, p), a_(&ad, &bc, p))
69}
70
71pub fn fp2_inv(x: &Fp2, p: &BigInt) -> Option<Fp2> {
73 let norm = a_(&m(&x.0, &x.0, p), &m(&x.1, &x.1, p), p);
74 let ninv = mod_inverse(&norm, p)?;
75 Some((m(&x.0, &ninv, p), m(&s(&ib(0), &x.1, p), &ninv, p)))
76}
77
78pub fn fp2_is_zero(x: &Fp2) -> bool {
79 x.0.is_zero() && x.1.is_zero()
80}
81
82fn phi2_in_y(j: &Fp2, p: &BigInt) -> [Fp2; 4] {
88 let j2 = fp2_mul(j, j, p);
89 let j3 = fp2_mul(&j2, j, p);
90 let k = |c: i64| fp2_const(c, p);
91 let c3 = k(1);
92 let c2 = fp2_sub(
94 &fp2_add(&fp2_neg(&j2, p), &fp2_mul(&k(1488), j, p), p),
95 &k(162000),
96 p,
97 );
98 let c1 = fp2_add(
100 &fp2_add(&fp2_mul(&k(1488), &j2, p), &fp2_mul(&k(40773375), j, p), p),
101 &k(8_748_000_000),
102 p,
103 );
104 let c0 = fp2_sub(
106 &fp2_add(
107 &fp2_sub(&j3, &fp2_mul(&k(162000), &j2, p), p),
108 &fp2_mul(&k(8_748_000_000), j, p),
109 p,
110 ),
111 &k(157_464_000_000_000),
112 p,
113 );
114 [c0, c1, c2, c3]
115}
116
117fn poly_eval(coeffs: &[Fp2], y: &Fp2, p: &BigInt) -> Fp2 {
119 let mut acc = fp2_const(0, p);
120 for c in coeffs.iter().rev() {
121 acc = fp2_add(&fp2_mul(&acc, y, p), c, p);
122 }
123 acc
124}
125
126fn poly_div_linear(coeffs: &[Fp2], r: &Fp2, p: &BigInt) -> (Vec<Fp2>, Fp2) {
128 let mut q = vec![fp2_const(0, p); coeffs.len().saturating_sub(1)];
129 let mut carry = fp2_const(0, p);
130 for k in (0..coeffs.len()).rev() {
131 let cur = fp2_add(&coeffs[k], &fp2_mul(&carry, r, p), p);
132 if k == 0 {
133 return (q, cur); }
135 q[k - 1] = cur.clone();
136 carry = cur;
137 }
138 (q, fp2_const(0, p))
139}
140
141fn fp2_elements(p: &BigInt) -> Vec<Fp2> {
143 let pu = p.to_i64().expect("small prime") as i64;
144 let mut v = Vec::new();
145 for a in 0..pu {
146 for b in 0..pu {
147 v.push((ib(a), ib(b)));
148 }
149 }
150 v
151}
152
153fn cubic_roots(coeffs: &[Fp2; 4], p: &BigInt) -> Vec<(Fp2, usize)> {
157 let mut out = Vec::new();
158 for y in fp2_elements(p) {
159 if fp2_is_zero(&poly_eval(coeffs, &y, p)) {
160 let mut poly: Vec<Fp2> = coeffs.to_vec();
162 let mut mult = 0usize;
163 loop {
164 let (q, rem) = poly_div_linear(&poly, &y, p);
165 if !fp2_is_zero(&rem) {
166 break;
167 }
168 mult += 1;
169 poly = q;
170 if poly.len() <= 1 {
171 break;
172 }
173 }
174 out.push((y, mult));
175 }
176 }
177 out
178}
179
180#[derive(Clone, Debug)]
183pub struct SsVertex {
184 pub j: Fp2,
185 pub neighbors: Vec<Fp2>,
186}
187
188pub fn supersingular_graph(p: &BigInt) -> Option<Vec<SsVertex>> {
193 if rem_pos(p, &ib(4)) != ib(3) {
194 return None;
195 }
196 let start = fp2_const(1728, p);
197 let mut visited: Vec<Fp2> = Vec::new();
198 let mut queue: Vec<Fp2> = vec![start];
199 let mut graph: Vec<SsVertex> = Vec::new();
200 while let Some(j) = queue.pop() {
201 if visited.iter().any(|v| v == &j) {
202 continue;
203 }
204 visited.push(j.clone());
205 let mut neighbors = Vec::new();
206 for (root, mult) in cubic_roots(&phi2_in_y(&j, p), p) {
207 for _ in 0..mult {
208 neighbors.push(root.clone());
209 }
210 if !visited.iter().any(|v| v == &root) && !queue.iter().any(|v| v == &root) {
211 queue.push(root);
212 }
213 }
214 graph.push(SsVertex { j, neighbors });
215 }
216 Some(graph)
217}
218
219#[derive(Clone, Debug, PartialEq, Eq)]
228pub struct Curve2 {
229 pub a: Fp2,
230 pub b: Fp2,
231 pub p: BigInt,
232}
233
234#[derive(Clone, Debug, PartialEq, Eq)]
236pub enum Point2 {
237 Infinity,
238 Affine(Fp2, Fp2),
239}
240
241impl Curve2 {
242 pub fn new(a: Fp2, b: Fp2, p: BigInt) -> Curve2 {
243 Curve2 { a, b, p }
244 }
245
246 pub fn is_on_curve(&self, pt: &Point2) -> bool {
247 match pt {
248 Point2::Infinity => true,
249 Point2::Affine(x, y) => {
250 let lhs = fp2_mul(y, y, &self.p);
251 let x3 = fp2_mul(&fp2_mul(x, x, &self.p), x, &self.p);
252 let rhs = fp2_add(
253 &fp2_add(&x3, &fp2_mul(&self.a, x, &self.p), &self.p),
254 &self.b,
255 &self.p,
256 );
257 lhs == rhs
258 }
259 }
260 }
261
262 pub fn negate(&self, pt: &Point2) -> Point2 {
263 match pt {
264 Point2::Infinity => Point2::Infinity,
265 Point2::Affine(x, y) => Point2::Affine(x.clone(), fp2_neg(y, &self.p)),
266 }
267 }
268
269 pub fn add(&self, p1: &Point2, p2: &Point2) -> Point2 {
270 match (p1, p2) {
271 (Point2::Infinity, _) => p2.clone(),
272 (_, Point2::Infinity) => p1.clone(),
273 (Point2::Affine(x1, y1), Point2::Affine(x2, y2)) => {
274 if x1 == x2 {
275 if fp2_is_zero(&fp2_add(y1, y2, &self.p)) {
276 return Point2::Infinity; }
278 return self.double(p1); }
280 let den =
281 fp2_inv(&fp2_sub(x2, x1, &self.p), &self.p).expect("distinct x invertible");
282 let lam = fp2_mul(&fp2_sub(y2, y1, &self.p), &den, &self.p);
283 let x3 = fp2_sub(
284 &fp2_sub(&fp2_mul(&lam, &lam, &self.p), x1, &self.p),
285 x2,
286 &self.p,
287 );
288 let y3 = fp2_sub(
289 &fp2_mul(&lam, &fp2_sub(x1, &x3, &self.p), &self.p),
290 y1,
291 &self.p,
292 );
293 Point2::Affine(x3, y3)
294 }
295 }
296 }
297
298 pub fn double(&self, pt: &Point2) -> Point2 {
299 match pt {
300 Point2::Infinity => Point2::Infinity,
301 Point2::Affine(x, y) => {
302 if fp2_is_zero(y) {
303 return Point2::Infinity;
304 }
305 let num = fp2_add(
306 &fp2_mul(&fp2_const(3, &self.p), &fp2_mul(x, x, &self.p), &self.p),
307 &self.a,
308 &self.p,
309 );
310 let den = fp2_inv(&fp2_mul(&fp2_const(2, &self.p), y, &self.p), &self.p)
311 .expect("2y invertible");
312 let lam = fp2_mul(&num, &den, &self.p);
313 let x3 = fp2_sub(
314 &fp2_mul(&lam, &lam, &self.p),
315 &fp2_mul(&fp2_const(2, &self.p), x, &self.p),
316 &self.p,
317 );
318 let y3 = fp2_sub(
319 &fp2_mul(&lam, &fp2_sub(x, &x3, &self.p), &self.p),
320 y,
321 &self.p,
322 );
323 Point2::Affine(x3, y3)
324 }
325 }
326 }
327
328 pub fn mul(&self, k: &BigInt, pt: &Point2) -> Point2 {
330 let mut result = Point2::Infinity;
331 let mut addend = pt.clone();
332 let (_, bytes) = k.to_le_bytes();
333 for byte in bytes {
334 for bit in 0..8 {
335 if (byte >> bit) & 1 == 1 {
336 result = self.add(&result, &addend);
337 }
338 addend = self.double(&addend);
339 }
340 }
341 result
342 }
343
344 pub fn j_invariant(&self) -> Option<Fp2> {
346 let a3 = fp2_mul(&fp2_mul(&self.a, &self.a, &self.p), &self.a, &self.p);
347 let four_a3 = fp2_mul(&fp2_const(4, &self.p), &a3, &self.p);
348 let disc = fp2_add(
349 &four_a3,
350 &fp2_mul(
351 &fp2_const(27, &self.p),
352 &fp2_mul(&self.b, &self.b, &self.p),
353 &self.p,
354 ),
355 &self.p,
356 );
357 if fp2_is_zero(&disc) {
358 return None;
359 }
360 Some(fp2_mul(
361 &fp2_mul(&fp2_const(1728, &self.p), &four_a3, &self.p),
362 &fp2_inv(&disc, &self.p)?,
363 &self.p,
364 ))
365 }
366}
367
368fn fp_sqrt(a: &BigInt, p: &BigInt) -> Option<BigInt> {
372 let ap = rem_pos(a, p);
373 if ap.is_zero() {
374 return Some(ib(0));
375 }
376 let exp = p.add(&ib(1)).div_rem(&ib(4))?.0;
377 let r = crate::factor::modpow(&ap, &exp, p);
378 (m(&r, &r, p) == ap).then_some(r)
379}
380
381pub fn fp2_sqrt(alpha: &Fp2, p: &BigInt) -> Option<Fp2> {
384 let (a, b) = (&alpha.0, &alpha.1);
385 if b.is_zero() {
386 if let Some(r) = fp_sqrt(a, p) {
387 return Some((r, ib(0)));
388 }
389 return fp_sqrt(&s(&ib(0), a, p), p).map(|r| (ib(0), r)); }
391 let norm = a_(&m(a, a, p), &m(b, b, p), p);
392 let sn = fp_sqrt(&norm, p)?;
393 let inv2 = crate::factor::mod_inverse(&ib(2), p)?;
394 for signed in [sn.clone(), s(&ib(0), &sn, p)] {
395 let t = m(&a_(a, &signed, p), &inv2, p); if let Some(x) = fp_sqrt(&t, p) {
397 if x.is_zero() {
398 continue;
399 }
400 let y = m(b, &crate::factor::mod_inverse(&m(&ib(2), &x, p), p)?, p);
401 let cand = (x, y);
402 if fp2_mul(&cand, &cand, p) == *alpha {
403 return Some(cand);
404 }
405 }
406 }
407 None
408}
409
410fn points_on_curve2(c: &Curve2) -> Vec<Point2> {
413 let pu = c.p.to_i64().expect("small prime");
414 let mut v = vec![Point2::Infinity];
415 for xa in 0..pu {
416 for xb in 0..pu {
417 let x = (ib(xa), ib(xb));
418 let x3 = fp2_mul(&fp2_mul(&x, &x, &c.p), &x, &c.p);
419 let rhs = fp2_add(&fp2_add(&x3, &fp2_mul(&c.a, &x, &c.p), &c.p), &c.b, &c.p);
420 if fp2_is_zero(&rhs) {
421 v.push(Point2::Affine(x, fp2_const(0, &c.p)));
422 } else if let Some(y) = fp2_sqrt(&rhs, &c.p) {
423 v.push(Point2::Affine(x.clone(), fp2_neg(&y, &c.p)));
424 v.push(Point2::Affine(x, y));
425 }
426 }
427 }
428 v
429}
430
431pub fn point_of_order2(c: &Curve2, ell: u64) -> Option<Point2> {
433 points_on_curve2(c)
434 .into_iter()
435 .find(|pt| *pt != Point2::Infinity && c.mul(&ib(ell as i64), pt) == Point2::Infinity)
436}
437
438pub fn torsion_basis2(c: &Curve2, n: u64) -> Option<(Point2, Point2)> {
441 let onp: Vec<Point2> = points_on_curve2(c)
442 .into_iter()
443 .filter(|pt| *pt != Point2::Infinity && c.mul(&ib(n as i64), pt) == Point2::Infinity)
444 .collect();
445 for p in &onp {
446 let span: Vec<Point2> = (0..n).map(|k| c.mul(&ib(k as i64), p)).collect();
447 if let Some(q) = onp.iter().find(|q| !span.contains(q)) {
448 return Some((p.clone(), q.clone()));
449 }
450 }
451 None
452}
453
454#[derive(Clone, Debug)]
456pub struct Isogeny2 {
457 pub domain: Curve2,
458 pub codomain: Curve2,
459 pub degree: u64,
460 kernel: Vec<(Fp2, Fp2, Fp2)>, }
462
463impl Isogeny2 {
464 pub fn from_kernel(curve: &Curve2, gen: &Point2, ell: u64) -> Option<Isogeny2> {
465 if ell < 3 || ell % 2 == 0 {
466 return None;
467 }
468 let p = &curve.p;
469 let mut kernel = Vec::new();
470 let mut cur = gen.clone();
471 for _ in 0..((ell - 1) / 2) {
472 match &cur {
473 Point2::Affine(xq, yq) => {
474 let vq = fp2_add(
475 &fp2_mul(&fp2_const(6, p), &fp2_mul(xq, xq, p), p),
476 &fp2_mul(&fp2_const(2, p), &curve.a, p),
477 p,
478 );
479 let uq = fp2_mul(&fp2_const(4, p), &fp2_mul(yq, yq, p), p);
480 kernel.push((xq.clone(), vq, uq));
481 }
482 Point2::Infinity => return None,
483 }
484 cur = curve.add(&cur, gen);
485 }
486 if matches!(gen, Point2::Infinity) || curve.mul(&ib(ell as i64), gen) != Point2::Infinity {
487 return None;
488 }
489 let (mut vsum, mut wsum) = (fp2_const(0, p), fp2_const(0, p));
490 for (xq, vq, uq) in &kernel {
491 vsum = fp2_add(&vsum, vq, p);
492 wsum = fp2_add(&wsum, &fp2_add(uq, &fp2_mul(xq, vq, p), p), p);
493 }
494 let a2 = fp2_sub(&curve.a, &fp2_mul(&fp2_const(5, p), &vsum, p), p);
495 let b2 = fp2_sub(&curve.b, &fp2_mul(&fp2_const(7, p), &wsum, p), p);
496 Some(Isogeny2 {
497 domain: curve.clone(),
498 codomain: Curve2::new(a2, b2, p.clone()),
499 degree: ell,
500 kernel,
501 })
502 }
503
504 pub fn eval(&self, pt: &Point2) -> Point2 {
505 let p = &self.domain.p;
506 match pt {
507 Point2::Infinity => Point2::Infinity,
508 Point2::Affine(x, y) => {
509 let mut xnew = x.clone();
510 let mut yfac = fp2_const(1, p);
511 for (xq, vq, uq) in &self.kernel {
512 let d = fp2_sub(x, xq, p);
513 if fp2_is_zero(&d) {
514 return Point2::Infinity;
515 }
516 let di = fp2_inv(&d, p).expect("nonzero");
517 let di2 = fp2_mul(&di, &di, p);
518 let di3 = fp2_mul(&di2, &di, p);
519 xnew = fp2_add(
520 &xnew,
521 &fp2_add(&fp2_mul(vq, &di, p), &fp2_mul(uq, &di2, p), p),
522 p,
523 );
524 let tail = fp2_add(
525 &fp2_mul(vq, &di2, p),
526 &fp2_mul(&fp2_mul(&fp2_const(2, p), uq, p), &di3, p),
527 p,
528 );
529 yfac = fp2_sub(&yfac, &tail, p);
530 }
531 Point2::Affine(xnew, fp2_mul(y, &yfac, p))
532 }
533 }
534 }
535}
536
537fn mline_double2(c: &Curve2, t: &Point2, xq: &Fp2, yq: &Fp2) -> Option<(Fp2, Fp2)> {
538 let p = &c.p;
539 let (xt, yt) = match t {
540 Point2::Affine(x, y) => (x, y),
541 Point2::Infinity => return None,
542 };
543 if fp2_is_zero(yt) {
544 return None;
545 }
546 let num = fp2_add(&fp2_mul(&fp2_const(3, p), &fp2_mul(xt, xt, p), p), &c.a, p);
547 let lam = fp2_mul(&num, &fp2_inv(&fp2_mul(&fp2_const(2, p), yt, p), p)?, p);
548 let ell = fp2_sub(
549 &fp2_sub(yq, yt, p),
550 &fp2_mul(&lam, &fp2_sub(xq, xt, p), p),
551 p,
552 );
553 let vert = match c.double(t) {
554 Point2::Affine(x2, _) => fp2_sub(xq, &x2, p),
555 Point2::Infinity => fp2_const(1, p),
556 };
557 Some((ell, vert))
558}
559
560fn mline_add2(c: &Curve2, t: &Point2, pp: &Point2, xq: &Fp2, yq: &Fp2) -> Option<(Fp2, Fp2)> {
561 let p = &c.p;
562 let ((xt, yt), (xpp, ypp)) = match (t, pp) {
563 (Point2::Affine(a, b), Point2::Affine(cc, d)) => ((a, b), (cc, d)),
564 _ => return None,
565 };
566 if xt == xpp {
567 if yt == ypp {
568 return mline_double2(c, t, xq, yq);
569 }
570 return Some((fp2_sub(xq, xt, p), fp2_const(1, p)));
571 }
572 let lam = fp2_mul(&fp2_sub(ypp, yt, p), &fp2_inv(&fp2_sub(xpp, xt, p), p)?, p);
573 let ell = fp2_sub(
574 &fp2_sub(yq, yt, p),
575 &fp2_mul(&lam, &fp2_sub(xq, xt, p), p),
576 p,
577 );
578 let vert = match c.add(t, pp) {
579 Point2::Affine(x3, _) => fp2_sub(xq, &x3, p),
580 Point2::Infinity => fp2_const(1, p),
581 };
582 Some((ell, vert))
583}
584
585fn miller2(c: &Curve2, pp: &Point2, qq: &Point2, n: u64) -> Option<Fp2> {
586 let p = &c.p;
587 let (xq, yq) = match qq {
588 Point2::Affine(x, y) => (x, y),
589 Point2::Infinity => return None,
590 };
591 let (mut num, mut den) = (fp2_const(1, p), fp2_const(1, p));
592 let mut t = pp.clone();
593 for bit in (0..(64 - n.leading_zeros() - 1)).rev() {
594 let (ell, vert) = mline_double2(c, &t, xq, yq)?;
595 num = fp2_mul(&fp2_mul(&num, &num, p), &ell, p);
596 den = fp2_mul(&fp2_mul(&den, &den, p), &vert, p);
597 t = c.double(&t);
598 if (n >> bit) & 1 == 1 {
599 let (ell, vert) = mline_add2(c, &t, pp, xq, yq)?;
600 num = fp2_mul(&num, &ell, p);
601 den = fp2_mul(&den, &vert, p);
602 t = c.add(&t, pp);
603 }
604 }
605 if fp2_is_zero(&den) {
606 return None;
607 }
608 Some(fp2_mul(&num, &fp2_inv(&den, p)?, p))
609}
610
611pub fn weil_pairing2(c: &Curve2, pp: &Point2, qq: &Point2, n: u64) -> Option<Fp2> {
613 if pp == qq || matches!(pp, Point2::Infinity) || matches!(qq, Point2::Infinity) {
614 return Some(fp2_const(1, &c.p));
615 }
616 let fp = miller2(c, pp, qq, n)?;
617 let fq = miller2(c, qq, pp, n)?;
618 let ratio = fp2_mul(&fp, &fp2_inv(&fq, &c.p)?, &c.p);
619 Some(if n % 2 == 1 {
620 fp2_neg(&ratio, &c.p)
621 } else {
622 ratio
623 })
624}
625
626pub fn product_weil_pairing(
631 c1: &Curve2,
632 c2: &Curve2,
633 p: (&Point2, &Point2),
634 q: (&Point2, &Point2),
635 n: u64,
636) -> Option<Fp2> {
637 let e1 = weil_pairing2(c1, p.0, q.0, n)?;
638 let e2 = weil_pairing2(c2, p.1, q.1, n)?;
639 Some(fp2_mul(&e1, &e2, &c1.p))
640}
641
642pub fn fp2_pow(alpha: &Fp2, k: u64, p: &BigInt) -> Fp2 {
644 let mut result = fp2_const(1, p);
645 let mut base = alpha.clone();
646 let mut e = k;
647 while e > 0 {
648 if e & 1 == 1 {
649 result = fp2_mul(&result, &base, p);
650 }
651 base = fp2_mul(&base, &base, p);
652 e >>= 1;
653 }
654 result
655}
656
657pub fn point_order2(c: &Curve2, pt: &Point2, bound: u64) -> Option<u64> {
661 let mut cur = pt.clone();
662 for k in 1..=bound {
663 if cur == Point2::Infinity {
664 return Some(k);
665 }
666 cur = c.add(&cur, pt);
667 }
668 None
669}
670
671pub fn kernel_generator2(c: &Curve2, p_pt: &Point2, q_pt: &Point2, s: &BigInt) -> Point2 {
673 c.add(p_pt, &c.mul(s, q_pt))
674}
675
676pub fn full_order_basis2(c: &Curve2, ell: u64, a: u32) -> Option<(Point2, Point2)> {
679 let n = ell.pow(a);
680 let full: Vec<Point2> = points_on_curve2(c)
681 .into_iter()
682 .filter(|pt| point_order2(c, pt, n + 1) == Some(n))
683 .collect();
684 for p in &full {
685 let span: Vec<Point2> = (0..n).map(|k| c.mul(&ib(k as i64), p)).collect();
686 if let Some(q) = full.iter().find(|q| !span.contains(q)) {
687 return Some((p.clone(), q.clone()));
688 }
689 }
690 None
691}
692
693#[derive(Clone, Debug, PartialEq)]
695pub struct IsogenyStep2 {
696 pub domain: Curve2,
697 pub kernel: Point2,
698 pub codomain: Curve2,
699}
700
701pub fn derive_isogeny_path2(
704 c: &Curve2,
705 gen: &Point2,
706 ell: u64,
707 a: u32,
708) -> Option<Vec<IsogenyStep2>> {
709 let mut steps = Vec::with_capacity(a as usize);
710 let mut e = c.clone();
711 let mut g = gen.clone();
712 for step in 0..a {
713 let mut mult = ib(1);
714 for _ in 0..(a - 1 - step) {
715 mult = mult.mul(&ib(ell as i64));
716 }
717 let k = e.mul(&mult, &g);
718 let iso = Isogeny2::from_kernel(&e, &k, ell)?;
719 steps.push(IsogenyStep2 {
720 domain: e.clone(),
721 kernel: k,
722 codomain: iso.codomain.clone(),
723 });
724 g = iso.eval(&g);
725 e = iso.codomain;
726 }
727 Some(steps)
728}
729
730pub fn push_through2(steps: &[IsogenyStep2], ell: u64, pt: &Point2) -> Option<Point2> {
732 let mut cur = pt.clone();
733 for step in steps {
734 cur = Isogeny2::from_kernel(&step.domain, &step.kernel, ell)?.eval(&cur);
735 }
736 Some(cur)
737}
738
739pub fn recover_secret2(
744 e0: &Curve2,
745 basis_a: (&Point2, &Point2),
746 ell: u64,
747 a: u32,
748 basis_b: (&Point2, &Point2),
749 images: (&Point2, &Point2),
750) -> Option<(BigInt, Point2, Vec<IsogenyStep2>)> {
751 let n = ell.pow(a);
752 for s in 0..n {
753 let sb = ib(s as i64);
754 let gen = kernel_generator2(e0, basis_a.0, basis_a.1, &sb);
755 if point_order2(e0, &gen, n + 1) != Some(n) {
756 continue;
757 }
758 let Some(path) = derive_isogeny_path2(e0, &gen, ell, a) else {
759 continue;
760 };
761 match (
762 push_through2(&path, ell, basis_b.0),
763 push_through2(&path, ell, basis_b.1),
764 ) {
765 (Some(ip), Some(iq)) if &ip == images.0 && &iq == images.1 => {
766 return Some((sb, gen, path))
767 }
768 _ => {}
769 }
770 }
771 None
772}
773
774#[allow(clippy::too_many_arguments)]
778fn walk_keyspace_tree(
779 e0: &Curve2,
780 ba: (&Point2, &Point2),
781 ell: u64,
782 a: u32,
783 n: u64,
784 bb: (&Point2, &Point2),
785 images: (&Point2, &Point2),
786 digits: &mut Vec<u64>,
787) -> Option<(BigInt, Point2)> {
788 if digits.len() as u32 == a {
789 let (mut s, mut place) = (ib(0), ib(1));
790 for &d in digits.iter() {
791 s = s.add(&place.mul(&ib(d as i64)));
792 place = place.mul(&ib(ell as i64));
793 }
794 let gen = kernel_generator2(e0, ba.0, ba.1, &s);
795 if point_order2(e0, &gen, n + 1) != Some(n) {
796 return None;
797 }
798 let path = derive_isogeny_path2(e0, &gen, ell, a)?;
799 let (ip, iq) = (
800 push_through2(&path, ell, bb.0)?,
801 push_through2(&path, ell, bb.1)?,
802 );
803 return (&ip == images.0 && &iq == images.1).then_some((s, gen));
804 }
805 for d in 0..ell {
806 digits.push(d);
807 if let Some(found) = walk_keyspace_tree(e0, ba, ell, a, n, bb, images, digits) {
808 return Some(found);
809 }
810 digits.pop();
811 }
812 None
813}
814
815pub fn recover_secret_recursive2(
820 e0: &Curve2,
821 basis_a: (&Point2, &Point2),
822 ell: u64,
823 a: u32,
824 basis_b: (&Point2, &Point2),
825 images: (&Point2, &Point2),
826) -> Option<(Vec<u64>, BigInt, Point2)> {
827 let n = ell.pow(a);
828 let mut digits: Vec<u64> = Vec::with_capacity(a as usize);
829 let (s, gen) = walk_keyspace_tree(e0, basis_a, ell, a, n, basis_b, images, &mut digits)?;
830 Some((digits, s, gen))
831}
832
833pub fn aut_1728(p: &BigInt, pt: &Point2) -> Point2 {
837 match pt {
838 Point2::Infinity => Point2::Infinity,
839 Point2::Affine(x, y) => {
840 let i_unit = (ib(0), ib(1)); Point2::Affine(fp2_neg(x, p), fp2_mul(&i_unit, y, p))
842 }
843 }
844}
845
846pub fn keyspace_codomain_classes(
851 e0: &Curve2,
852 basis_a: (&Point2, &Point2),
853 ell: u64,
854 a: u32,
855) -> Vec<(Fp2, Vec<u64>)> {
856 let n = ell.pow(a);
857 let mut classes: Vec<(Fp2, Vec<u64>)> = Vec::new();
858 for s in 0..n {
859 let gen = kernel_generator2(e0, basis_a.0, basis_a.1, &ib(s as i64));
860 if point_order2(e0, &gen, n + 1) != Some(n) {
861 continue;
862 }
863 let Some(path) = derive_isogeny_path2(e0, &gen, ell, a) else {
864 continue;
865 };
866 let Some(j) = path.last().and_then(|st| st.codomain.j_invariant()) else {
867 continue;
868 };
869 match classes.iter().position(|(cj, _)| *cj == j) {
870 Some(idx) => classes[idx].1.push(s),
871 None => classes.push((j, vec![s])),
872 }
873 }
874 classes
875}
876
877fn ell_isogeny_neighbors(c: &Curve2, ell: u64) -> Vec<Curve2> {
879 let Some((r, s)) = full_order_basis2(c, ell, 1) else {
880 return Vec::new();
881 };
882 let mut gens: Vec<Point2> = (0..ell)
883 .map(|i| c.add(&r, &c.mul(&ib(i as i64), &s)))
884 .collect();
885 gens.push(s);
886 gens.into_iter()
887 .filter_map(|g| Isogeny2::from_kernel(c, &g, ell).map(|iso| iso.codomain))
888 .collect()
889}
890
891pub fn isogeny_graph_distances(target: &Curve2, ell: u64, max_depth: u32) -> Vec<(Fp2, u32)> {
895 let Some(j0) = target.j_invariant() else {
896 return Vec::new();
897 };
898 let mut dist: Vec<(Fp2, u32)> = vec![(j0, 0)];
899 let mut frontier = vec![target.clone()];
900 for d in 1..=max_depth {
901 let mut next = Vec::new();
902 for c in &frontier {
903 for nbr in ell_isogeny_neighbors(c, ell) {
904 if let Some(j) = nbr.j_invariant() {
905 if !dist.iter().any(|(jj, _)| *jj == j) {
906 dist.push((j, d));
907 next.push(nbr);
908 }
909 }
910 }
911 }
912 if next.is_empty() {
913 break;
914 }
915 frontier = next;
916 }
917 dist
918}
919
920#[allow(clippy::too_many_arguments)]
926fn walk_pruned(
927 e0: &Curve2,
928 ba: (&Point2, &Point2),
929 ell: u64,
930 a: u32,
931 n: u64,
932 bb: (&Point2, &Point2),
933 images: (&Point2, &Point2),
934 dists: &[(Fp2, u32)],
935 digits: &mut Vec<u64>,
936 leaves: &mut usize,
937) -> Option<(BigInt, Point2)> {
938 let k = digits.len() as u32;
939 let (mut p, mut place) = (ib(0), ib(1));
940 for &d in digits.iter() {
941 p = p.add(&place.mul(&ib(d as i64)));
942 place = place.mul(&ib(ell as i64));
943 }
944 if k > 0 {
945 let gen_p = kernel_generator2(e0, ba.0, ba.1, &p);
946 let path = derive_isogeny_path2(e0, &gen_p, ell, a)?;
947 let jk = path[(k - 1) as usize].codomain.j_invariant()?;
948 match dists.iter().find(|(jj, _)| *jj == jk).map(|(_, d)| *d) {
949 Some(dk) if dk <= a - k => {} _ => return None, }
952 }
953 if k == a {
954 *leaves += 1;
955 let gen = kernel_generator2(e0, ba.0, ba.1, &p);
956 if point_order2(e0, &gen, n + 1) != Some(n) {
957 return None;
958 }
959 let path = derive_isogeny_path2(e0, &gen, ell, a)?;
960 let (ip, iq) = (
961 push_through2(&path, ell, bb.0)?,
962 push_through2(&path, ell, bb.1)?,
963 );
964 return (&ip == images.0 && &iq == images.1).then_some((p, gen));
965 }
966 for d in 0..ell {
967 digits.push(d);
968 if let Some(found) = walk_pruned(e0, ba, ell, a, n, bb, images, dists, digits, leaves) {
969 return Some(found);
970 }
971 digits.pop();
972 }
973 None
974}
975
976pub fn recover_secret_pruned2(
982 e0: &Curve2,
983 basis_a: (&Point2, &Point2),
984 ell: u64,
985 a: u32,
986 basis_b: (&Point2, &Point2),
987 images: (&Point2, &Point2),
988 target: &Curve2,
989) -> Option<(BigInt, Point2, usize)> {
990 let n = ell.pow(a);
991 let dists = isogeny_graph_distances(target, ell, a);
992 let mut digits: Vec<u64> = Vec::with_capacity(a as usize);
993 let mut leaves = 0usize;
994 let (s, gen) = walk_pruned(
995 e0,
996 basis_a,
997 ell,
998 a,
999 n,
1000 basis_b,
1001 images,
1002 &dists,
1003 &mut digits,
1004 &mut leaves,
1005 )?;
1006 Some((s, gen, leaves))
1007}
1008
1009#[cfg(test)]
1010#[path = "../../logicaffeine_tests/unit/logicaffeine_proof/fp2/tests.rs"]
1011mod tests;