import gmpy2
def solve_rsa_primes(s: int, m: int) -> tuple:
""" Solve RSA prime numbers (p, q) from the quadratic equation
p^2 - s * p + m = 0 with the formula p = s/2 +/- sqrt((s/2)^2 - m)
Parameters:
s - sum of primes (p + q)
m - product of primes (p * q)
Return: (p, q)
"""
half_s = s >> 1
tmp = gmpy2.isqrt(half_s ** 2 - m)
return int(half_s + tmp), int(half_s - tmp)
def wiener_attack(n: int, e: int) -> (int, int, int):
""" Wiener's Attack on RSA public key cryptosystem
Paramaters:
N - RSA modulus N = p*q
e - RSA public exponent
Return:
A tuple of (p, q, d)
p, q - the two prime factors of RSA modulus N
d - RSA private exponent
"""
cfe = cf_expansion(e, n) # Convert e/n into a continued fraction
cvg = cf_convergent(cfe) # Get all of its convergents
for k, d in cvg:
# Check if k and d meet the requirements
if k == 0 or d % 2 == 0 or (e * d) % k != 1:
continue
# assume ed ≡ 1 (mod ϕ(n))
phi = (e * d - 1) // k
p, q = solve_rsa_primes(n - phi + 1, n)
if n == p * q:
return d
return None
N = int(
'22836858353287668091920368816286415778103964252589'\
'28295130420474999022996621982166664596581454018899'\
'48429922376560732622754871538043874356270300826321'\
'16650572564937978011181394388679265524940467869924'\
'85473650038355720409426235584833584188449224331698'\
'63569900296911605460645581176522325967221393273906'\
'69673188457131381644120787783215342848744792830245'\
'01805598140668893320307200136190794138325132168722'\
'14217943474001731747822701596634040292342194986951'\
'94551646668806852454006312372413658692027515557841'\
'41440661232146905186431357112566536770669381756925'\
'38179415478954522854711968599279014482060579354284'\
'55238863726089083')
e = int(
'17160819308904585327789016134897914235762203050367'\
'34632679585567058963995675965428034906637374660531'\
'64750599687461192166424505919293706011293378320096'\
'43372382766547546926535697752805239918767190684796'\
'26509298669049485976118315666126871681847641670872'\
'58895073919139366379901867664076540531765577090231'\
'67209821832859747419658344363466584895316847817524'\
'24703257392651850823517297420382138943770358904660'\
'59442300191228592937251734592732623207324742303631'\
'32436274414264865868028527840102483762414082363751'\
'87208612632105886502393648156776330236987329249988'\
'11429508256124902530957499338336903951924035916501'\
'53661610070010419')
d = wiener_attack(N, e)
assert not d is None, "Wiener's attack failed!"
print("d =", d)
new_b = int(gmpy2.root(N, 4)/gmpy2.root(18, 4))
print("new_b =", new_b)
assert d <= new_b
old_b = int(gmpy2.root(N, 4)/3)
print("old_b =", old_b)
assert d > old_b
Became Hot Network Question