mcieno

ECDH invalid curve attack

We are given an elliptic curve E: y^2 = x^3 + a x + b with parameters

q = 100173830297345234246296808618734115432031228596757431606170574500462062623677
a = 34797263276731929172113534470189285565338055361167847976642146658712494152186
b = 39258950039257324692361857404792305546106163510884954845070423459288379905976

mcieno

# -*- coding: utf8 -*-
# See: https://eprint.iacr.org/2009/037.pdf

N  = 24402191928494981635640497435944050736451453218629774561432653700273120014058697415669445779441226800209154604159648942665855233706977525093135734838825433023506185915211877990448599462290859092875150657461517275171867229282791419867655722945527203477335565212992510088077874648530075739380783193891617730212062455173395228143660241234491822044677453330325054451661281530021397747260054593565182679642519767415355255125571875708238139022404975788807868905750857687120708529622235978672838872361435045431974203089535736573597127746452000608771150171882058819685487644883286497700966396731658307013308396226751130001733
e1 = 4046316324291866910571514561657995962295158364702933460389468827072872865293920814266515228710438970257021065064390281148950759462687498079736672906875128944198140931482449741147988959788282715310307170986783402655196296704611285447752149956531303574680859541910243014672391229934386132475024308686852032924357952489090295552491

mcieno

# Setup curve
p = 17
a, b = 1, -1

E = EllipticCurve(GF(p), [a, b])
G = E.gen(0)

# Target secret key
d = 8

mcieno

Crusty sandbox && Crsty sndbx

Both services let us load and execute rust programs.

Welcome to the Rust Playground!
[1] New ground
[2] Show ground
[3] Play ground
[4] Exit

mcieno

# Curve parameters
p = 1048583
a, b = 1, -1

# Target secret key
d = 4121

# Setup curve
E = EllipticCurve(GF(p), [a, b])
G = E.gen(0)

mcieno

#!/usr/bin/env python3

def xgcd(a, b):
    x0, x1, y0, y1 = 0, 1, 1, 0
    while a != 0:
        (q, a), b = divmod(b, a), a
        y0, y1 = y1, y0 - q * y1
        x0, x1 = x1, x0 - q * x1
    return b, x0, y0

mcieno

#!/usr/bin/env -S sage -python3
import argparse
from sage.all import PolynomialRing, Zmod


def recover(N, e, c, prefix):
    P = PolynomialRing(Zmod(N), 'x')
    x = P.gen()
    poly = (prefix + x)**e - c
    return poly.small_roots(epsilon=1/2**e)