Howgrave-Graham and Seifert's small private exponent attack on common modulus RSA (2 public exponents).

howgrave-seifert.sage

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