attack_rsa.sage

#!/usr/bin/env sage

from pprint import pprint

def print_f(f):
    fl = f.list()
    if fl[-1] != 1:
        print(f"{hex(fl[-1])}x^{len(fl) - 1}", end=" + ")
    else:
        print(f"x^{len(fl) - 1}", end=" + ")
    for i, x in enumerate(fl[1:-1][::-1]):
        print(f"{hex(x)}x^{len(fl) -2 - i}", end=" + ")
    print(f"{hex(f[0])}", end="\n")

#  while True:
#      p = random_prime(2^49 - 1, false, 2^48)
#      q = random_prime(2^49 - 1, false, 2^48)
#      phi = (p - 1) * (q - 1)
#      e = 3
#      if gcd(e, phi) == 1:
#          break

#  n =  p * q

n = 0x1a34992f64135aedaa0fe2bfd
bl = int(n).bit_length()
N = Zmod(n)
pad = int.from_bytes(b"\xff" * ((bl // 8) - 1), "big")
e = 3
m = 0x4142
a = pad << 16
z = a | m
c = N(z) ^ e
X = 0x7b7b

print(f"n:    {hex(n)}\ne:    {hex(e)}\npad:  {hex(pad)}\nc:    {hex(c)}\na:    {hex(a)}\nX:    {hex(X)}")
print(f"n bit: {bl}")
P.<x> = PolynomialRing(N)
f = (a + x)^e - c
print(f"f:   ", end=" ")
print(f)
print_f(f)
fi = list(map(int, f.list()))

B = matrix([
    [X^3, fi[2]*X^2, fi[1]*X, fi[0]],
    [0,   n*X^2,     0,       0],
    [0,   0,         n*X,     0],
    [0,   0,         0,       n],
])
det = B.det()
predicted_bound = 2^(3/4) * det^(1/4)
nsqrt = n / sqrt(4)
print("\nB:   ")
pprint(B)
print("\n[!] Apply LLL")
L = B.LLL()
print("\nL:   ")
pprint(L)

v = L[0]

print(f"\ndet:               {int(det)}\n")
print(f"||g(xX)||:           {int(v.norm())} <= ")
print(f"2^(3/4)det^(1/4):    {int(predicted_bound)} < ")
print(f"N / sqrt(4):         {int(nsqrt)}")

print("v:    ", end="")
for element in v:
    print(hex(element), end="  ")

assert v in span(B)

P.<x> = PolynomialRing(ZZ)
w = []
for i, l in enumerate(v):
    w.append(l // X^(3 - i))
g = w[0]*x^3 + w[1]*x^2 + w[2]*x + w[3]
print("\ng(x): ", end=" ")
print_f(g)

for r in g.roots():
    if r[0] == m:
        print(f"\n[*] found: {hex(r[0])}")
        break
else:
    print("[!] failed")