Marco Cieno 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

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

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

	N = 24402191928494981635640497435944050736451453218629774561432653700273120014058697415669445779441226800209154604159648942665855233706977525093135734838825433023506185915211877990448599462290859092875150657461517275171867229282791419867655722945527203477335565212992510088077874648530075739380783193891617730212062455173395228143660241234491822044677453330325054451661281530021397747260054593565182679642519767415355255125571875708238139022404975788807868905750857687120708529622235978672838872361435045431974203089535736573597127746452000608771150171882058819685487644883286497700966396731658307013308396226751130001733
	e1 = 4046316324291866910571514561657995962295158364702933460389468827072872865293920814266515228710438970257021065064390281148950759462687498079736672906875128944198140931482449741147988959788282715310307170986783402655196296704611285447752149956531303574680859541910243014672391229934386132475024308686852032924357952489090295552491

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

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

	# Target secret key
	d = 8

	# 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)

	#!/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

	#!/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)