crypto1_6.py

# Breaking RSA when N is generated incorrectly (p and q are close)

import time
from math import ceil
from useful import isSquare, sqrt, modinv
import decimal


def factor_with_fermat(m, c=1, d=1):
    n = m * c * d
    decimal.getcontext().prec = len(str(n)) + 2
    dec = decimal.Decimal(n * 4)
    a = int(ceil(dec.sqrt()))
    b2 = a * a - n * 4
    while not isSquare(b2):
        a += 2
        b2 = a * a - n * 4
    p = (a - sqrt(b2)) // 2
    assert n % p == 0
    q = n // p
    assert p * q == n
    if p % c == 0:
        p //= c
        q //= d
    else:
        p //= d
        q //= c
    return sorted([p, q])

start = time.time()

x1 = 179769313486231590772930519078902473361797697894230657273430081157732675805505620686985379449212982959585501387537164015710139858647833778606925583497541085196591615128057575940752635007475935288710823649949940771895617054361149474865046711015101563940680527540071584560878577663743040086340742855278549092581
f1 = factor_with_fermat(x1)
print(min(f1))

x2 = 648455842808071669662824265346772278726343720706976263060439070378797308618081116462714015276061417569195587321840254520655424906719892428844841839353281972988531310511738648965962582821502504990264452100885281673303711142296421027840289307657458645233683357077834689715838646088239640236866252211790085787877
f2 = factor_with_fermat(x2)
print(min(f2))

x3 = 720062263747350425279564435525583738338084451473999841826653057981916355690188337790423408664187663938485175264994017897083524079135686877441155132015188279331812309091996246361896836573643119174094961348524639707885238799396839230364676670221627018353299443241192173812729276147530748597302192751375739387929
f3 = factor_with_fermat(x3, 3, 2)
print(min(f3))

x4 = 22096451867410381776306561134883418017410069787892831071731839143676135600120538004282329650473509424343946219751512256465839967942889460764542040581564748988013734864120452325229320176487916666402997509188729971690526083222067771600019329260870009579993724077458967773697817571267229951148662959627934791540
phi1 = int(x1 - f1[0] - f1[1] + 1)
e = 65537
d = modinv(e, phi1)
m4 = pow(x4, d, x1)
b4 = m4.to_bytes((m4.bit_length() + 7) // 8, 'big')
for i, b in enumerate(b4):
    if b == 0:
        pt = bytes(b4[i+1:]).decode()
        print(pt)
        break

elapsed = time.time() - start
if elapsed < 1:
    elapsed *= 1000
    text = "milliseconds"
else:
    text = "seconds"
print("Program took:", elapsed, text)