Skip to content

Instantly share code, notes, and snippets.

@mcieno
Last active March 22, 2021 05:56
Show Gist options
  • Save mcieno/a417c7d82049021036a4b2a6295d8231 to your computer and use it in GitHub Desktop.
Save mcieno/a417c7d82049021036a4b2a6295d8231 to your computer and use it in GitHub Desktop.
Howgrave-Graham and Seifert's small private exponent attack on common modulus RSA (2 public exponents).
# -*- coding: utf8 -*-
# See: https://eprint.iacr.org/2009/037.pdf
N = 24402191928494981635640497435944050736451453218629774561432653700273120014058697415669445779441226800209154604159648942665855233706977525093135734838825433023506185915211877990448599462290859092875150657461517275171867229282791419867655722945527203477335565212992510088077874648530075739380783193891617730212062455173395228143660241234491822044677453330325054451661281530021397747260054593565182679642519767415355255125571875708238139022404975788807868905750857687120708529622235978672838872361435045431974203089535736573597127746452000608771150171882058819685487644883286497700966396731658307013308396226751130001733
e1 = 4046316324291866910571514561657995962295158364702933460389468827072872865293920814266515228710438970257021065064390281148950759462687498079736672906875128944198140931482449741147988959788282715310307170986783402655196296704611285447752149956531303574680859541910243014672391229934386132475024308686852032924357952489090295552491467702140263159982675018932692576847952002081478475199969962357685826609238653859264698996411770860260854720047710943051229985596674736079206428312934943752164281391573970043088475625727793169708939179742630253381871307298938827042259481077482527690653141867639100647971209354276568204913
e2 = 1089598671818931285487024526159841107695197822929259299424340503971498264804485187657064861422396497630013501691517290648230470308986030853450089582165362228856724965735826515693970375662407779866271304787454416740708203748591727184057428330386039766700161610534430469912754092586892162446358263283169799095729696407424696871657157280716343681857661748656695962441400433284766608408307217925949587261052855826382885300521822004968209647136722394587701720895365101311180886403748262958990917684186947245463537312582719347101291391169800490817330947249069884756058179616748856032431769837992142653355261794817345492723
r = RR(2) # Number of primes in N
# delta2 = (3 + r) / (7 * r) - epsilon
DELTA2_BOUND = (3 + r) / (7 * r)
MAX_EPS = 0.1
ATTEMPTS = 100
for eps in range(ATTEMPTS):
delta2 = DELTA2_BOUND - MAX_EPS * (eps / ATTEMPTS)
D2 = diagonal_matrix(ZZ,
[ Integer( N**(2 - 2 / r) ),
Integer( N**(1 - 1 / r) ),
Integer( N**(delta2 + 2 - 2 / r) ),
Integer( 1 ) ] )
B2 = Matrix(ZZ, [ [ 1, -N, 0, N ** 2 ],
[ 0, e1, -e1, -e1 * N ],
[ 0, 0, e2, -e2 * N ],
[ 0, 0, 0, e1 * e2 ] ])
B2_prime = B2 * D2
L = B2_prime.LLL()
v = Matrix(ZZ, L[0])
x = v * B2_prime.inverse()
# x = (k1 * k2, k2 * d1, k1 * d2, d1 * d2)
# phi = ( e1 * d1 - 1 ) / k1 = floor( e1 * (d1 / k1) )
d1_k1 = x[0,1] / x[0,0]
phi = ( e1 * d1_k1 ).floor()
P = PolynomialRing(ZZ, 'x')
x = P.gen()
f = x**2 - (N - phi + 1) * x + N
if f.roots():
p, q = f.roots()[0][0], f.roots()[1][0]
if (p * q == N and p != 1 and q != 1):
print('N factored with delta2 =', delta2)
print('p =', p)
print('q =', q)
break
else:
print('N could not be factored')
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment