MOV reduction in Python
Transfers ECDLP to a finite-field DLP using pairings; effective for supersingular curves.
- File
menezes_okamoto_vanstone_reduction.py, 157 lines- Level
- I0 not checked yet
- Toolchain
- Python 3.14, pytest 9
- Test framework
- pytest
- Run the tests
python3 -m pytest
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/menezes-okamoto-vanstone-reduction/. The authors are listed in prov/HWKGB7.jsonl.
import random
from math import isqrt
Point = tuple[int, int] | None # affine (x, y), or None for the point at infinity
F2 = tuple[int, int] # a + b i in F_p[i]/(i^2 + 1)
def ec_add(P: Point, Q: Point, p: int) -> Point:
"""Sum of two points on y^2 = x^3 + x over F_p."""
if P is None:
return Q
if Q is None:
return P
(x1, y1), (x2, y2) = P, Q
if x1 == x2 and (y1 + y2) % p == 0:
return None
if P == Q:
lam = (3 * x1 * x1 + 1) * pow(2 * y1, -1, p) % p
else:
lam = (y2 - y1) * pow(x2 - x1, -1, p) % p
x3 = (lam * lam - x1 - x2) % p
return x3, (lam * (x1 - x3) - y1) % p
def ec_mul(k: int, P: Point, p: int) -> Point:
"""k P by double and add, for k >= 0."""
R: Point = None
while k:
if k & 1:
R = ec_add(R, P, p)
P = ec_add(P, P, p)
k >>= 1
return R
def _fmul(u: F2, v: F2, p: int) -> F2:
return (u[0] * v[0] - u[1] * v[1]) % p, (u[0] * v[1] + u[1] * v[0]) % p
def _fpow(u: F2, e: int, p: int) -> F2:
r: F2 = (1, 0)
while e:
if e & 1:
r = _fmul(r, u, p)
u = _fmul(u, u, p)
e >>= 1
return r
def _prime_factors(m: int) -> list[int]:
out, d = [], 2
while d * d <= m:
if m % d == 0:
out.append(d)
while m % d == 0:
m //= d
d += 1
if m > 1:
out.append(m)
return out
def _order(Q: Point, n: int, p: int) -> int:
"""Exact order of a point Q with n Q = O."""
d = n
for r in _prime_factors(n):
while d % r == 0 and ec_mul(d // r, Q, p) is None:
d //= r
return d
def tate(T0: Point, R: tuple[F2, F2], m: int, p: int) -> F2:
"""Reduced Tate pairing f_{m,T0}(R)^((p^2 - 1)/m) by Miller's algorithm.
T0 is in E(F_p) of odd order m with m | p + 1, and R = (x_R, y_R) is a point
of E(F_{p^2}) with x_R in F_p and y_R not in F_p, so that vertical lines,
whose values lie in F_p^*, are killed by the final exponentiation.
"""
(xr, _), yr = R[0], R[1]
f: F2 = (1, 0) # @line L9
T = T0
for bit in bin(m)[3:]: # @line L10
x, y = T
lam = (3 * x * x + 1) * pow(2 * y, -1, p) % p
line = ((yr[0] - y - lam * (xr - x)) % p, yr[1]) # tangent at T, evaluated at R
f = _fmul(_fmul(f, f, p), line, p) # @line L11
T = ec_add(T, T, p)
if bit == "1": # @line L12
x, y = T
x0, y0 = T0
if x != x0: # otherwise T = -T0 and the line is vertical
lam = (y0 - y) * pow(x0 - x, -1, p) % p
line = ((yr[0] - y - lam * (xr - x)) % p, yr[1])
f = _fmul(f, line, p)
T = ec_add(T, T0, p)
return _fpow(f, (p * p - 1) // m, p) # @line L13
def _log_mu(alpha: F2, beta: F2, n: int, p: int) -> int | None:
"""Baby-step giant-step for alpha^x = beta in F_{p^2}, alpha of order n."""
m = isqrt(n) + 1
table: dict[F2, int] = {}
e: F2 = (1, 0)
for j in range(m):
table.setdefault(e, j)
e = _fmul(e, alpha, p)
giant = _fpow(alpha, n - m % n, p) # alpha^(-m)
y = beta
for i in range(m + 1):
if y in table:
return (i * m + table[y]) % n
y = _fmul(y, giant, p)
return None
def mov_reduction(P: Point, Q: Point, n: int, p: int, seed: int = 0) -> int | None:
"""MOV reduction on the supersingular curve y^2 = x^3 + x over F_p, p = 3 mod 4.
Return the x in [0, n) with x P = Q, or None if Q is not a multiple of P.
The problem is moved by the reduced Tate pairing with the distortion map
psi(x, y) = (-x, i y) into the order n subgroup of F_{p^2}^*, where it is
solved here by baby-step giant-step.
Precondition: p is prime, p = 3 (mod 4), P and Q lie on the curve, and
P has exact order n, which must be odd (so the embedding degree is 2).
Raises ValueError if p % 4 != 3 or n is even.
Cost: O(log n) operations in F_{p^2} per pairing (Miller's algorithm and
the final exponentiation), an expected n / phi(n) pairings to find a good
R, and O(n^(1/2)) multiplications in F_{p^2} for the transferred logarithm.
"""
if p % 4 != 3 or n % 2 == 0:
raise ValueError("need p = 3 (mod 4) and odd n")
if ec_mul(n, Q, p) is not None: # @line L1
return None
if Q is None: # @line L2
return 0
rng = random.Random(seed)
primes = _prime_factors(n)
d = _order(Q, n, p)
while True: # @line L3
x0 = rng.randrange(p) # @line L4
rhs = (x0 * x0 * x0 + x0) % p
y0 = pow(rhs, (p + 1) // 4, p)
if rhs == 0 or y0 * y0 % p != rhs:
continue
if rng.randrange(2):
y0 = p - y0
R = ((-x0 % p, 0), (0, y0)) # psi(x0, y0) = (-x0, i y0)
alpha = tate(P, R, n, p) # @line L5
if any(_fpow(alpha, n // r, p) == (1, 0) for r in primes):
continue
beta = tate(Q, R, d, p) # @line L6
x = _log_mu(alpha, beta, n, p) # @line L7
assert x is not None and ec_mul(x, P, p) == Q
return x # @line L8
test_menezes_okamoto_vanstone_reduction.py 200 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/menezes-okamoto-vanstone-reduction/. The authors are listed in prov/HWKGB7.jsonl.
import random
import pytest
from menezes_okamoto_vanstone_reduction import ec_add, ec_mul, mov_reduction, tate
def is_prime(n: int) -> bool:
if n < 2:
return False
d = 2
while d * d <= n:
if n % d == 0:
return False
d += 1
return True
def _sieve(limit: int) -> list[bool]:
flags = [True] * limit
flags[0] = flags[1] = False
for i in range(2, int(limit ** 0.5) + 1):
if flags[i]:
flags[i * i :: i] = [False] * len(range(i * i, limit, i))
return flags
_PRIME = _sieve(100000)
def primes_3_mod_4(lo: int, hi: int) -> list[int]:
return [q for q in range(lo, hi) if q % 4 == 3 and _PRIME[q]]
def random_point(rng: random.Random, p: int) -> tuple[int, int]:
while True:
x = rng.randrange(p)
r = (x * x * x + x) % p
y = pow(r, (p + 1) // 4, p)
if y * y % p == r:
return x, (y if rng.randrange(2) else -y % p)
def multiples(P, p: int) -> list:
"""The multiples kP for 0 <= k < ord(P), in order, by repeated addition."""
out = [None]
T = P
while T is not None:
out.append(T)
T = ec_add(T, P, p)
return out
def odd_part(m: int) -> int:
while m % 2 == 0:
m //= 2
return m
def point_of_odd_order(rng: random.Random, p: int):
"""A random point P with odd order n > 1 and the list of its multiples."""
w = odd_part(p + 1)
while True:
P = ec_mul((p + 1) // w, random_point(rng, p), p)
if P is not None:
mult = multiples(P, p)
return P, mult
def check(P, Q, mult: list, p: int, seed: int = 0) -> None:
n = len(mult)
x = mov_reduction(P, Q, n, p, seed)
if Q in mult:
assert x == mult.index(Q)
else:
assert x is None
def test_worked_example() -> None:
p, P = 43, (4, 5)
Q = (23, 8) # 7 P
assert mov_reduction(P, Q, 11, p) == 7
R = ((41, 0), (0, 15)) # psi(2, 15)
assert tate(P, R, 11, p) == (2, 30)
assert tate(Q, R, 11, p) == (11, 40)
assert mov_reduction(P, (2, 15), 11, p) is None # (2, 15) has order 44
def test_curve_is_supersingular() -> None:
# #E(F_p) = p + 1 for y^2 = x^3 + x and p = 3 mod 4.
for p in primes_3_mod_4(3, 200):
count = 1 + sum(1 for x in range(p) for y in range(p) if (y * y - x ** 3 - x) % p == 0)
assert count == p + 1
def test_trivial_targets() -> None:
rng = random.Random(1)
ps = [q for q in primes_3_mod_4(7, 100000) if odd_part(q + 1) > 1]
for _ in range(60):
p = rng.choice(ps)
P, mult = point_of_odd_order(rng, p)
n = len(mult)
assert mov_reduction(P, None, n, p) == 0
assert mov_reduction(P, P, n, p) == 1
def test_small_primes_exhaustive() -> None:
for p in primes_3_mod_4(7, 60):
w = odd_part(p + 1)
if w == 1:
continue
pts = [(x, y) for x in range(p) for y in range(p) if (y * y - x ** 3 - x) % p == 0]
gens = {ec_mul((p + 1) // w, T, p) for T in pts} - {None}
for P in sorted(gens):
mult = multiples(P, p)
for Q in [None] + pts:
check(P, Q, mult, p)
def test_random_small_groups() -> None:
rng = random.Random(2024)
ps = [q for q in primes_3_mod_4(7, 5000) if odd_part(q + 1) > 1]
for _ in range(300):
p = rng.choice(ps)
P, mult = point_of_odd_order(rng, p)
Q = rng.choice(mult) if rng.random() < 0.5 else random_point(rng, p)
check(P, Q, mult, p, rng.randrange(1000))
def test_random_large_groups() -> None:
rng = random.Random(77)
ps = [q for q in primes_3_mod_4(10000, 100000) if odd_part(q + 1) > 1]
for _ in range(40):
p = rng.choice(ps)
P, mult = point_of_odd_order(rng, p)
n = len(mult)
for _ in range(3):
x = rng.randrange(n)
assert mov_reduction(P, mult[x], n, p, rng.randrange(1000)) == x
check(P, random_point(rng, p), mult, p)
def test_prime_order_subgroups() -> None:
rng = random.Random(5)
ps = primes_3_mod_4(100, 100000)
found = 0
while found < 40:
p = rng.choice(ps)
w = odd_part(p + 1)
r = max(d for d in range(3, w + 1, 2) if w % d == 0 and is_prime(d)) if w > 1 else 1
if r < 3:
continue
P = None
while P is None:
P = ec_mul((p + 1) // r, random_point(rng, p), p)
mult = multiples(P, p)
assert len(mult) == r
for _ in range(4):
x = rng.randrange(r)
assert mov_reduction(P, mult[x], r, p, rng.randrange(100)) == x
check(P, random_point(rng, p), mult, p)
found += 1
def test_composite_order_subgroups() -> None:
rng = random.Random(9)
ps = primes_3_mod_4(100, 50000)
found = 0
while found < 40:
p = rng.choice(ps)
w = odd_part(p + 1)
divisors = [d for d in range(9, w + 1, 2) if w % d == 0 and not is_prime(d)]
if not divisors:
continue
n = rng.choice(divisors)
P = None
while P is None or len(multiples(P, p)) != n:
P = ec_mul((p + 1) // n, random_point(rng, p), p)
mult = multiples(P, p)
for _ in range(4):
x = rng.randrange(n)
assert mov_reduction(P, mult[x], n, p, rng.randrange(100)) == x
# a random point of order dividing n; it lies in <P> because E(F_p) is cyclic
check(P, ec_mul((p + 1) // n, random_point(rng, p), p), mult, p)
found += 1
def test_seed_independence_of_answer() -> None:
for seed in range(20):
assert mov_reduction((4, 5), (23, 8), 11, 43, seed) == 7
def test_bad_input() -> None:
with pytest.raises(ValueError):
mov_reduction((1, 1), (1, 1), 3, 41) # p = 1 mod 4
with pytest.raises(ValueError):
mov_reduction((4, 5), (4, 5), 22, 43) # even n
What the next level needs
- the tests did not run in this build