RSA加密分析

task.py

# sagemath
import random
from Crypto.Util.number import *

flag = b''

k = 3
d = k/(2*(k+1))
ns = []
pqs = []
es = []

for i in range(3):
    p = getPrime(512)
    q = getPrime(512)
    if p < q:
        tmp = p
        p = q
        q = tmp
    n = p*q
    ns.append(n)
    pqs.append((p,q))

n = min(ns)
x = random.randint(0,int(n^(d/2)))
x = next_prime(x)

for i in range(3):
    p,q = pqs[i][0],pqs[i][1]
    bound1 = int((p-q)/(3*(p+q)) * x * n ^ 0.25)
    bound2 = int((p-q)/(3*(p+q)) * x^2 * n ^ 0.25)
    z = random.randint(bound1,bound2)
    f = (p-1)*(q-1)
    e = inverse(x^2,f) * z % f
    es.append(e)

e = 8462913
c = pow(bytes_to_long(flag),e,ns[0])

print(f'ns={ns}')
print(f'es={es}')
print(f'c={c}')

'''
ns=[58456238154727772714762362790039415372652580738847549549926175214592421074440425380491278175531057453959583518365006871715668115289674464868754600641087664868445977308497244134179400977293896807231964047365956545629327100737851868274388108150918741474301542596310528990700043925342513137054619092876834352167, 77621328849675766747673031143217563980503830449890233197117569566535170499356584333526498228802079135043121885950830320777642529199704224484173792215691924850086027618183393165197503325417741686635820334799489140360184827244176669486536901652827052817389390205607840551799799037689580359943641014734459153393, 112244920700186260026594736958318991062998987080230137582151100770199379608284829383065111800934933346946496041561749555085922429662611986339400029890877247514987095240380019377389184545006798594193383230298132838994539491402564579629017309643629910561998268286162916487705908044261914142200286678017692930877]
es=[46762963588977775648213636278524171408894671002158172701955774077187382885695296449518850546775920334764033057745226744111631183010556541467024035131602309988991836959736948179491431343087734419406823467043032520956443072556932946767546576469286010676651317873358203560021064830688914958086524112915123700678, 49605058941818136068558533413619424099600243928109466352604646203354430655695939177245076016870792265350960174089601299549033530643078866868937787258274475767441534991912769995268058506952466739575911255510940326565376471493045685544056383561868628029099619187607579109612157304977780126730283103824111801708, 35433601810279274137096137736120773703247868305827931187532982974242279082633517463016086358856291932337981126992048059591164336008738979183437333221010305682689432537562502148059203087673302900990705589870381203411821061168753251557946997898741497047442934600089950257888693394999451561437497637827070063398]
c=45042826649205831967869785980034342377048541926664036544108272069702081866501394370318117629151408517708467341069558466115205805860156690204194355692872459196902123082567148537856941845388225814307822482217762135547080677443326657146552580523747535577686386312386011950929734955156100305548239483424574706729
'''

exp

from Crypto.Util.number import *
import gmpy2
import itertools

def small_roots(f, bounds, m=1, d=None):
    if not d:
        d = f.degree()
    R = f.base_ring()
    N = R.cardinality()
    f /= f.coefficients().pop(0)
    f = f.change_ring(ZZ)
    G = Sequence([], f.parent())
    for i in range(m + 1):
        base = N ^ (m - i) * f ^ i
        for shifts in itertools.product(range(d), repeat=f.nvariables()):
            g = base * prod(map(power, f.variables(), shifts))
            G.append(g)
    B, monomials = G.coefficient_matrix()
    monomials = vector(monomials)
    factors = [monomial(*bounds) for monomial in monomials]
    for i, factor in enumerate(factors):
        B.rescale_col(i, factor)
    B = B.dense_matrix().LLL()
    B = B.change_ring(QQ)
    for i, factor in enumerate(factors):
        B.rescale_col(i, 1 / factor)
    H = Sequence([], f.parent().change_ring(QQ))
    for h in filter(None, B * monomials):
        H.append(h)
        I = H.ideal()
        if I.dimension() == -1:
            H.pop()
        elif I.dimension() == 0:
            roots = []
            for root in I.variety(ring=ZZ):
                root = tuple(R(root[var]) for var in f.variables())
                roots.append(root)
            return roots
    return []

ns = [58456238154727772714762362790039415372652580738847549549926175214592421074440425380491278175531057453959583518365006871715668115289674464868754600641087664868445977308497244134179400977293896807231964047365956545629327100737851868274388108150918741474301542596310528990700043925342513137054619092876834352167, 77621328849675766747673031143217563980503830449890233197117569566535170499356584333526498228802079135043121885950830320777642529199704224484173792215691924850086027618183393165197503325417741686635820334799489140360184827244176669486536901652827052817389390205607840551799799037689580359943641014734459153393, 112244920700186260026594736958318991062998987080230137582151100770199379608284829383065111800934933346946496041561749555085922429662611986339400029890877247514987095240380019377389184545006798594193383230298132838994539491402564579629017309643629910561998268286162916487705908044261914142200286678017692930877]
es = [46762963588977775648213636278524171408894671002158172701955774077187382885695296449518850546775920334764033057745226744111631183010556541467024035131602309988991836959736948179491431343087734419406823467043032520956443072556932946767546576469286010676651317873358203560021064830688914958086524112915123700678, 49605058941818136068558533413619424099600243928109466352604646203354430655695939177245076016870792265350960174089601299549033530643078866868937787258274475767441534991912769995268058506952466739575911255510940326565376471493045685544056383561868628029099619187607579109612157304977780126730283103824111801708, 35433601810279274137096137736120773703247868305827931187532982974242279082633517463016086358856291932337981126992048059591164336008738979183437333221010305682689432537562502148059203087673302900990705589870381203411821061168753251557946997898741497047442934600089950257888693394999451561437497637827070063398]
c = 45042826649205831967869785980034342377048541926664036544108272069702081866501394370318117629151408517708467341069558466115205805860156690204194355692872459196902123082567148537856941845388225814307822482217762135547080677443326657146552580523747535577686386312386011950929734955156100305548239483424574706729
e = 8462913
n1,n2,n3 = ns
e1,e2,e3 = es

n = [n1,n2,n3]
M = isqrt(max(n))

Ge = [[M,e1,e2,e3],
    [0,-n1,0,0],
    [0,0,-n2,0],
    [0,0,0,-n3]]

Ge = Matrix(ZZ,Ge)

line = Ge.LLL()[0]
dM = line[0]
x_2 = abs(dM) // M
x = gmpy2.iroot(x_2,2)[0]
assert isPrime(x)

tmp = abs(line[1])
k1 = (e1 * x_2 - tmp) // n1 + 1

R.<y,z> = PolynomialRing(Zmod(n1))
f = (e1 * x_2) - (z - k1 * y)
res = small_roots(f,(2^513,2^630),m=1,d=2)
y = int(res[0][0])

hint = y >> 250
n = 58456238154727772714762362790039415372652580738847549549926175214592421074440425380491278175531057453959583518365006871715668115289674464868754600641087664868445977308497244134179400977293896807231964047365956545629327100737851868274388108150918741474301542596310528990700043925342513137054619092876834352167

R.<x> = PolynomialRing(RealField(2048))
f = x * ((hint << 250) - x) - n1
res = f.roots()
pbits = 512
for root in res:
    phigh = int(root[0])
    p_high = phigh >> 256
    for i in trange(2**8):
     p4 = p_high << 8           #这里需要先爆破8位，使得知道264位以后再恢复p
     p4 = p4 + i
     kbits = pbits - p4.bit_length()
     p4 = p4 << kbits
     R.<x> = PolynomialRing(Zmod(n))
     f = x + p4
     x = f.small_roots(X=2^kbits, beta=0.4, epsilon=0.01)
     if x:
         p = p4 + int(x[0])
         q = n // p
         print(f"p = {p}")
         print(f"q = {q}")
         break

 """
 p = 7595466686419558151205913432118661460574378336265188601308332178368424478703273480167149453312906478797521330243646557948961908036589158891684701262055023
q = 7696200979887856341831037613988614280823562431557099321251289719686349578851157595313091133333376255237947592610103860940743200558583228583143108125315529
 """

from Crypto.Util.number import *

p = 7595466686419558151205913432118661460574378336265188601308332178368424478703273480167149453312906478797521330243646557948961908036589158891684701262055023
q = 7696200979887856341831037613988614280823562431557099321251289719686349578851157595313091133333376255237947592610103860940743200558583228583143108125315529
n = 58456238154727772714762362790039415372652580738847549549926175214592421074440425380491278175531057453959583518365006871715668115289674464868754600641087664868445977308497244134179400977293896807231964047365956545629327100737851868274388108150918741474301542596310528990700043925342513137054619092876834352167
e = 8462913
c = 45042826649205831967869785980034342377048541926664036544108272069702081866501394370318117629151408517708467341069558466115205805860156690204194355692872459196902123082567148537856941845388225814307822482217762135547080677443326657146552580523747535577686386312386011950929734955156100305548239483424574706729

phi = (p-1)*(q-1)

d_p = inverse(e // 3,p-1)
m_3p = pow(c,d_p,p)

R.<x> = PolynomialRing(Zmod(p))
f = x^3 - m_3p
res = f.roots()
for m in res:
    print(long_to_bytes(int(m[0])))
    # flag{N3w_Attacks_4_key_equat1ons}

Author:DexterJie