RSA Attack

Introduction

开篇介绍RSA应用非常广泛，介绍了RSA加解密和数字签名的实现。

虽然二十年的研究已经导致了一些迷人的攻击，但没有一个是毁灭性的。它们主要说明了不正确使用RSA的危险。事实上，安全地实现RSA是一项重要的任务。

Elementary Attacks

Common Modulus

为了避免为每个用户生成不同的，有些人可能希望一劳永逸的使用同一个,一个中心机构可以给不同的用户提供不同的,，这样用户的公钥对是,私钥对是。

第一感觉这样的系统是安全的，论文给出了一种攻击方法，但是常见的攻击方法是：

假设Alice使用对消息进行加密得到，记作:

同时Bob使用对消息进行加密得到，记作：

那么这时候一般选取素数，所以大概率得到，(后边会遇到，不互素有时也可以)

那么一定有

那么

攻击完毕

举个栗子：

task.py

e = 797
n = 15944475431088053285580229796309956066521520107276817969079550919586650535459242543036143360865780730044733026945488511390818947440767542658956272380389388112372084760689777141392370253850735307578445988289714647332867935525010482197724228457592150184979819463711753058569520651205113690397003146105972408452854948512223702957303406577348717348753106868356995616116867724764276234391678899662774272419841876652126127684683752880568407605083606688884120054963974930757275913447908185712204577194274834368323239143008887554264746068337709465319106886618643849961551092377843184067217615903229068010117272834602469293571
c = 11157593264920825445770016357141996124368529899750745256684450189070288181107423044846165593218013465053839661401595417236657920874113839974471883493099846397002721270590059414981101686668721548330630468951353910564696445509556956955232059386625725883038103399028010566732074011325543650672982884236951904410141077728929261477083689095161596979213961494716637502980358298944316636829309169794324394742285175377601826473276006795072518510850734941703194417926566446980262512429590253643561098275852970461913026108090608491507300365391639081555316166526932233787566053827355349022396563769697278239577184503627244170930

e = 521
n = 15944475431088053285580229796309956066521520107276817969079550919586650535459242543036143360865780730044733026945488511390818947440767542658956272380389388112372084760689777141392370253850735307578445988289714647332867935525010482197724228457592150184979819463711753058569520651205113690397003146105972408452854948512223702957303406577348717348753106868356995616116867724764276234391678899662774272419841876652126127684683752880568407605083606688884120054963974930757275913447908185712204577194274834368323239143008887554264746068337709465319106886618643849961551092377843184067217615903229068010117272834602469293571
c = 6699274351853330023117840396450375948797682409595670560999898826038378040157859939888021861338431350172193961054314487476965030228381372659733197551597730394275360811462401853988404006922710039053586471244376282019487691307865741621991977539073601368892834227191286663809236586729196876277005838495318639365575638989137572792843310915220039476722684554553337116930323671829220528562573169295901496437858327730504992799753724465760161805820723578087668737581704682158991028502143744445435775458296907671407184921683317371216729214056381292474141668027801600327187443375858394577015394108813273774641427184411887546849

exp.py

import gmpy2
import binascii

n=gmpy2.mpz(15944475431088053285580229796309956066521520107276817969079550919586650535459242543036143360865780730044733026945488511390818947440767542658956272380389388112372084760689777141392370253850735307578445988289714647332867935525010482197724228457592150184979819463711753058569520651205113690397003146105972408452854948512223702957303406577348717348753106868356995616116867724764276234391678899662774272419841876652126127684683752880568407605083606688884120054963974930757275913447908185712204577194274834368323239143008887554264746068337709465319106886618643849961551092377843184067217615903229068010117272834602469293571)

c1=gmpy2.mpz(11157593264920825445770016357141996124368529899750745256684450189070288181107423044846165593218013465053839661401595417236657920874113839974471883493099846397002721270590059414981101686668721548330630468951353910564696445509556956955232059386625725883038103399028010566732074011325543650672982884236951904410141077728929261477083689095161596979213961494716637502980358298944316636829309169794324394742285175377601826473276006795072518510850734941703194417926566446980262512429590253643561098275852970461913026108090608491507300365391639081555316166526932233787566053827355349022396563769697278239577184503627244170930)

c2=gmpy2.mpz(6699274351853330023117840396450375948797682409595670560999898826038378040157859939888021861338431350172193961054314487476965030228381372659733197551597730394275360811462401853988404006922710039053586471244376282019487691307865741621991977539073601368892834227191286663809236586729196876277005838495318639365575638989137572792843310915220039476722684554553337116930323671829220528562573169295901496437858327730504992799753724465760161805820723578087668737581704682158991028502143744445435775458296907671407184921683317371216729214056381292474141668027801600327187443375858394577015394108813273774641427184411887546849)

e1=797

e2=521

s=gmpy2.gcdext(e1,e2)

m1=pow(c1,s[1],n)

m2=pow(c2,s[2],n)

m=(m1*m2)%n

print(binascii.unhexlify(hex(m)[2:]))

Blinding Attacks

假设现在想让在恶意消息上签名，显然不会提供自己用于签名的私钥，这是随机选取一个,然后计算,这时愿意在这个看起来没有恶意的消息上进行签名，签名记作.

这时，我们知道

,这时，得到了在恶意消息上的签名。

举个栗子:

Crypto hack Blinding Light

Low Private Exponent

为了减少解密或者数字签名的运算时间，有些人可能会选取一个较小的作为解密的指数，这可能导致RSA收到维纳攻击。

定理:

假设，并且，同时满足，那么在已知的情况下，攻击者可以高效地恢复。

证明：

这个证明基于连分数近似法，

已知,那么一定存在一个满足,两边同时除以进一步得到:

这时,和十分接近，虽然攻击者并不知道的具体值，但是它可以使用来近似，(解释：因为,并且,也就是,因此可以在这里使用近似)

这是一个经典的近似关系，和非常近似，这时，我们对做连分数展开，其中一项一定和相等。

举个栗子：

task.py

e = 284100478693161642327695712452505468891794410301906465434604643365855064101922252698327584524956955373553355814138784402605517536436009073372339264422522610010012877243630454889127160056358637599704871937659443985644871453345576728414422489075791739731547285138648307770775155312545928721094602949588237119345
n = 468459887279781789188886188573017406548524570309663876064881031936564733341508945283407498306248145591559137207097347130203582813352382018491852922849186827279111555223982032271701972642438224730082216672110316142528108239708171781850491578433309964093293907697072741538649347894863899103340030347858867705231
c = 350429162418561525458539070186062788413426454598897326594935655762503536409897624028778814302849485850451243934994919418665502401195173255808119461832488053305530748068788500746791135053620550583421369214031040191188956888321397450005528879987036183922578645840167009612661903399312419253694928377398939392827

exp.py

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

# wiener attack连分数攻击 e较大

def gen_con(x,y):
    q=[]
    while y:
        q.append(x//y)
        x,y=y,x%y
    return q

def gen_frac(q):
    x,y=0,1
    for qi in q[::-1]:
        x,y=y,x+qi*y
    return (x,y)

def solve_force(q):
    fs=[]
    for i in range(1,len(q)):
        fs.append(gen_frac(q[:i]))
    return fs

def solve_p_q(n,phi):
    # 已知 n，phi求p，q
    '''
    已知phi=(p-q)(q-1)=p*q-q-p+1
    已知n=pq
    推出x=p+q=n-phi+1
    设y=(p-q)^2=(p+q)^2-4pq
    设z=q-p=sqrt(y)
    则q=(x+z)//2
    则p=(x-z)//2
    return p,q
    '''

    x=n-phi+1
    y=x*x-4*n
    z=iroot(y,2)[0]
    q=(x+z)//2
    p=(x-z)//2
    # assert(p*q==n)
    # assert((p-1)*(q-1)==phi)
    return p,q

def wiener_attack(e,n):
    q=gen_con(e,n)
    phi=[]
    for (di,ki) in solve_force(q):
        if di!=0 and ki!=0:
            # phi=(ed-1)//k
            p,q=solve_p_q(n,(e*di-1)//ki)
            if p*q==n:
                return p,q

e = 14058695417015334071588010346586749790539913287499707802938898719199384604316115908373997739604466972535533733290829894940306314501336291780396644520926473
n = 33608051123287760315508423639768587307044110783252538766412788814888567164438282747809126528707329215122915093543085008547092423658991866313471837522758159
p,q=wiener_attack(e,n)

print(p)
print(q)

N-p-r-q">8405ee02-c1f0-4770-8e93-b4cdf1da7d53N=p^r*qd83bc7be-cfd0-49e5-afa8-c62afe7cbc42

**定理：**对于以及当十分接近时，我们可以高效求解，具体需要满足

思路：

这时候我们可以对进行连分数展开，其中有一项与相等。

举个栗子:

task.py

import hashlib
import sympy
from Crypto.Util.number import *

flag = 'GWHT{*********}'

flag1 = flag[:14]
flag2 = flag[14:]
assert(len(flag) == 27)

P1 = getPrime(1038)
P2 = sympy.nextprime(P1)
assert(P2 - P1 < 1000)

Q1 = getPrime(512)
Q2 = sympy.nextprime(Q1)

N1 = P1 * P1 * Q1
N2 = P2 * P2 * Q2

E1 = getPrime(1024)
E2 = sympy.nextprime(E1)

m1 = bytes_to_long(flag1)
m2 = bytes_to_long(flag2)

c1 = pow(m1, E1, N1)
c2 = pow(m2, E2, N2)


output = open('secret', 'w')
output.write('N1=' + str(N1) + '\n')
output.write('c1=' + str(c1) + '\n')
output.write('E1=' + str(E1) + '\n')
output.write('N2=' + str(N2) + '\n')
output.write('c2=' + str(c2) + '\n')
output.write('E2=' + str(E2) + '\n')
output.close()

exp.py

from Crypto.Util import number
import gmpy2

n1=
c1=
e1=

n2=
c2=
e2=


def continuedFra(x, y):
    cF = []
    while y:
        cF += [x // y]
        x, y = y, x % y
    return cF


def Simplify(ctnf):
    numerator = 0
    denominator = 1
    for x in ctnf[::-1]:
        numerator, denominator = denominator, x * denominator + numerator
    return (numerator, denominator)


def getit(c):
    cf = []
    for i in range(1, len(c)):
        cf.append(Simplify(c[:i]))
    return cf


def attack(e, n):
    cf = continuedFra(e, n)
    for (p2, p1) in getit(cf):
        if p1 == 0:
            continue
        if n1 % p1 == 0 and p1 != 1:
            return p1, p2
    print('not find!')


q1, q2 = attack(n1, n2)
p1 = gmpy2.iroot(n1//q1, 2)[0]
p2 = gmpy2.iroot(n2//q2, 2)[0]
phi1 = p1*(p1-1)*(q1-1)
phi2 = p2*(p2-1)*(q2-1)
d1 = gmpy2.invert(e1, phi1)
d2 = gmpy2.invert(e2, phi2)
m1 = number.long_to_bytes(gmpy2.powmod(c1, d1, n1))
m2 = number.long_to_bytes(gmpy2.powmod(c2, d2, n2))
print(m1+m2)

Low Public Exponent

e = 3
n = 18970053728616609366458286067731288749022264959158403758357985915393383117963693827568809925770679353765624810804904382278845526498981422346319417938434861558291366738542079165169736232558687821709937346503480756281489775859439254614472425017554051177725143068122185961552670646275229009531528678548251873421076691650827507829859299300272683223959267661288601619845954466365134077547699819734465321345758416957265682175864227273506250707311775797983409090702086309946790711995796789417222274776215167450093735639202974148778183667502150202265175471213833685988445568819612085268917780718945472573765365588163945754761
c = 150409620528139732054476072280993764527079006992643377862720337847060335153837950368208902491767027770946661

解答：

观察到公钥e非常小，考虑使用低加密指数攻击的方法

基本原理： 因此，

因此可以遍历k，使得m是一个整数即可得到答案

import gmpy2
import binascii

n=gmpy2.mpz(18970053728616609366458286067731288749022264959158403758357985915393383117963693827568809925770679353765624810804904382278845526498981422346319417938434861558291366738542079165169736232558687821709937346503480756281489775859439254614472425017554051177725143068122185961552670646275229009531528678548251873421076691650827507829859299300272683223959267661288601619845954466365134077547699819734465321345758416957265682175864227273506250707311775797983409090702086309946790711995796789417222274776215167450093735639202974148778183667502150202265175471213833685988445568819612085268917780718945472573765365588163945754761)

e=3

c=gmpy2.mpz(150409620528139732054476072280993764527079006992643377862720337847060335153837950368208902491767027770946661)

k=0

while True:
    res=gmpy2.iroot(k*n+c,e)
    if(res[1]==True):
        print(binascii.unhexlify(hex(res[0])[2:]))
       
    break
    k+=1

Vanilla Broadcast Attack

假设想要将消息加密之后发送给多个用户,每个用户有他们自己的公钥，我们假设小于所有的，为了发送加密后的消息，用他们各自的公钥进行加密，为了简化这个问题，我们假设所有的。如果，我们容易得到.

对于任意的都有,(否则，我们有更简单的方法攻击他)。对，借助中国剩余定理，我们容易得到一个,满足

这时候直接对开3次根号，就能得到.

举个栗子：

task.py

from Crypto.Util.number import bytes_to_long, getPrime
import socketserver
import json

FLAG = b'HTB{--REDACTED--}'


class TimeCapsule():

    def __init__(self, msg):
        self.msg = msg
        self.bit_size = 1024
        self.e = 5

    def _get_new_pubkey(self):
        while True:
            p = getPrime(self.bit_size // 2)
            q = getPrime(self.bit_size // 2)
            n = p * q
            phi = (p - 1) * (q - 1)
            try:
                pow(self.e, -1, phi)
                break
            except ValueError:
                pass

        return n, self.e

    def get_new_time_capsule(self):
        n, e = self._get_new_pubkey()
        m = bytes_to_long(self.msg)
        m = pow(m, e, n)

        return {"time_capsule": f"{m:X}", "pubkey": [f"{n:X}", f"{e:X}"]}


def challenge(req):
    time_capsule = TimeCapsule(FLAG)
    while True:
        try:
            req.sendall(
                b'Welcome to Qubit Enterprises. Would you like your own time capsule? (Y/n) '
            )
            msg = req.recv(4096).decode().strip().upper()
            if msg == 'Y' or msg == 'YES':
                capsule = time_capsule.get_new_time_capsule()
                req.sendall(json.dumps(capsule).encode() + b'\n')
            elif msg == 'N' or msg == "NO":
                req.sendall(b'Thank you, take care\n')
                break
            else:
                req.sendall(b'I\'m sorry I don\'t understand\n')
        except:
            # Socket closed, bail
            return


class MyTCPRequestHandler(socketserver.BaseRequestHandler):

    def handle(self):
        req = self.request
        challenge(req)


class ThreadingTCPServer(socketserver.ThreadingMixIn, socketserver.TCPServer):
    pass


def main():
    socketserver.TCPServer.allow_reuse_address = True
    server = ThreadingTCPServer(("0.0.0.0", 1337), MyTCPRequestHandler)
    server.serve_forever()


if __name__ == '__main__':
    main()

exp.py

from sympy.ntheory.modular import crt
from sympy import integer_nthroot
from Crypto.Util.number import long_to_bytes

##加密输出 1
c1 = 

n1 = 

##加密输出 2
c2= 

n2=

##加密输出 3
c3 = 

n3 = 

##使用中国余数定理计算m的e次方
x = crt([n1, n2, n3], [c1, c2, c3], check=True)
print("x=", x)

##开e次方求解m
m = integer_nthroot(x[0], 5)
print("m=", m)

##输出明文
flag = long_to_bytes(m[0])
print("flag=", flag)
#HTB{t3h_FuTUr3_15_bR1ghT_1_H0p3_y0uR3_W34r1nG_5h4d35!}

Håstad's broadcast attack

参考文章

H~证明了在加密之前对消息应用任何固定的多项式进行转换都是不安全的。

假设，采用一个多项式,在对消息进行加密之前，先对消息进行转换，这样每个用户得到的密文就变成了H~证明了如果足够多的用户参与加密，恶意攻击者就能恢复明文。

定理：是互素的几个数，令.令是个次多项式，建设存在一个唯一的满足

,for all

如果，我们得到组那么我们能高效地求解出,

证明：令,假设所有地都是的首一多项式，我们构造如下多项式

我们可以构造

然后借助中国剩余定理求解出

进而计算

,我们可以借助copper求解出

举个栗子

task.py

import random
from Crypto.Util.number import *
m = bytes_to_long(b'NSSCTF{******}')
e = 3
cnt = 5
A = [random.randint(1, 128) for i in range(cnt)]
B = [random.randint(1, 1024) for i in range(cnt)]
Cs = []
Ns = []
ds = []
for i in range(cnt):
    p = getPrime(1024)
    q = getPrime(1024)
    N = p * q
    Ns.append(N)
    c = pow(A[i] * m + B[i], e, N)
    Cs.append(c)

print(f'Cs = {Cs}')
print(f'Ns = {Ns}')
print(f'A = {A}')
print(f'B = {B}')

'''
Cs = [3883550483902420926234302242195949363902226654053022494278088796963093148922544154652393440710324453957805003804862341179812753736616349557399185135880313324078548975985811806182903172952051652658588498612963004980264760087430598878125976827727487812798234711111712162020259061748840871764150680864715622600474900724019717, 44236067230701013362887598977513235723198800481322709348886355202907732899445854511587419035591039483362973933824325371001141984765195796979842132811747908218486539899605454036424269293612496645594202012384509417494958938609654993954815298870367636552785788956298375017694826184378792550191638399421497826339423606821604157, 6357650953899476167368901224389387403906446759598372329485772462484633677698135444868033121301336092469156582681179266678600618088894651608959308419170191169045155695737438290373562868522834196889856654007109891894017495798358315308038562408520108440771857096111507359080036538511243240503551392124933753089110476128205879, 22113876206623661433094377745740418662890776774627724662206682745097788065566600734855556673140969239465263787646309908630165398806037735405429975451284487302914604239730662891329034924321076102542709261476260968369261179396546360622009680551846353241542278987410340410787241742872482813920394082039159494900989803139848, 3482139402999788223900773097355269284333433274039980036209713091774078099956379218113295375979469580323031564990774054948555715060182912479470463142901382767332589017162687376944227096536463901792518843690268101660074429034365722795293704792196728134808253362549344588424246863639211005569740713503298812433885633339928000]
Ns = [16475947720089128737086499038994656469812989231809435921247088488421456071533054401942524421620331649062071397844226728071767213827034006847771426419523100773295773164564476217357610574522713490589578290280800714302496527429690267342283298617108512673396866659851168908725556917773195601048972304412711680140760801040935590195586074637385222382292803661244860123231496798860777536415139625565081790463543592610972293444445484103576151223863074744798386995109810985102707212603792744509634887671301358727199987659311189567616661188675145831286196163294361139604739930788248190209148634033965292667427275010588011907449, 20577756967813119473983751142406348831049793754920537415005815223703461130310397180758312537008616509869607815711902558904863798387297921980544196445945053155779852988514975874071063143079007922739179751830691324912287324521191080786349595537328978318940405478035852622078260078106150355838894304903666410802941404171580632337325226810035755441751019274785623857299274197733366157959314887828355684391955406242669453470960096408521602483306976326328443227588146790803825249363494429478920856868334932355802422905860734038456902208606699044555491079703407805059303577939602439962034474867810455961978123428573930309579, 25378900199358568547963276996842869295995268651191814514603221510827400166103120330924988917554751086130358554721062101701515825946297524373525439060420148179742729309006073061967296139229954269726231365437710075337125457376990188019604789882474361937774315087501386157518068677103700336670450539759041322742305750381808526633011613014316600728378154635620303486714630541107978228937765593165029293600696974317531575469630789089360595175501977260250968161370460576429760743419177492425307438895058834861598683601140950473599184767494278677563047031229859204765208419798131798581975676005652781036214330956450007099403, 9926930930542540303568927026135349869339912234415090245441062010278559018661286180235901235221302260175325531516014675014545716516533078219977130807590578846757066721033900594646767488495122383467444918251577083210413483316448060657426105745966157951221212755678202988755054192555411944547922101946719460879213184073264876177559979901796761414990531875287201475974601204234252323254624416703924391519239658714195344209537776288504410483034555245167972866281710032749023882686703242857598745646748066876170805806058616787854614797120972981188197354785585317082619741063413472652781873599900240100437586392949061248911, 20830107058752240343833750223075661528901765032886427653372256688107333986271844745610709207164953960695218903201021174901973495649232416991828815735226979007977454196096030222267886398005100472650709789400722193947140354500257454594031250139843254349174343293378469322212240525155348525032929797789787100019790044104691478313003888625343348575779856701393153928092199647854293030744711864943595605801812851745568294572509414459253058726953902809163955547592002726224051451969415362170516701646937298176613945563863745599843208814303891064544739910893746169725919856235296428308161065429422882694228900677440053029677]
A = [56, 126, 66, 10, 54]
B = [261, 191, 877, 352, 62]
'''

exp.py

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

Cs=
Ns = []
A = []
B = []
e = 3


Fs = []
for i in range(5):
    PR.<x> = PolynomialRing(Zmod(Ns[i]))
    f = (A[i]*x + B[i])^e - Cs[i]
    f = f.monic()
    f = f.change_ring(ZZ)
    Fs.append(f)
F = crt(Fs, Ns)
M = reduce(lambda x, y: x * y, Ns)
FF = F.change_ring(Zmod(M))
m = FF.small_roots()
print(long_to_bytes(int(m[0])))

Franklin-Reiter Related Message Attack

假设要将两个消息加密之后发送给，并且这两个消息满足并且。将这两个消息用相同的公钥加密成发送给，在已知并且比较小的情况下，可以高效的恢复。

证明：

所以既是的根

同时又是的根

我们计算的最大公因子，如果多项式是一次多项式，那么他的系数就是

举个栗子：

task.py

from Crypto.Util.number import *
flag = b'NSSCTF{******}'

p = getPrime(700)
q = getPrime(700)
n = p*q
e = 5

m1 = bytes_to_long(flag)

a = getPrime(128)
b = getPrime(128)
m2 = a*m1 + b

c1 = pow(m1, e, n)
c2 = pow(m2, e, n)

print(f'n = {n}')
print(f'a = {a}')
print(f'b = {b}')
print(f'c1 = {c1}')
print(f'c2 = {c2}')

'''
n = 13919443827889434443507983317773657992305936401066686387374260636490833628767777134968864107882874635776776741295578533278845576747348959144023000046017344598661215911149680972293657114227644912150926936884507570232880546597335636361816325245444237275023999522533527764240730547185826755972838574195391038131656239536920948158465916528880835693552792260356361022462682037427718404037021825844211741628768123221090717527493
a = 285426137705625850725555147387995674019
b = 277985464990476154618471183198080357743
c1 = 9426395562512809581013620472326672750327318596813074726353079091173842802365552984264585030513998874440683981314827988473250779276622812642078592270162488257445750556180090334901558598065090257832879692296066144186335139137620672058976438826755846843815726564085636220609216862492337842110335421544935056753632826033207088809042045528566533513130910178132026694855125856386336197708244017301467175024440126022121500756597
c2 = 7817626870900560837063304883188246502988767588941344995287074193857215881437472677956793645281329763767094907997432409446021978284194802133451654430505222891535367029301384789198710394554265321474931034378249847884399129098152817955822667403789421376159327548545340231962148603594715994813791837670639630747654837874296940404313828931665262517234613625655607389345122624044747819855804429899373080756267420097146009333048
'''

exp.py

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


n = 13919443827889434443507983317773657992305936401066686387374260636490833628767777134968864107882874635776776741295578533278845576747348959144023000046017344598661215911149680972293657114227644912150926936884507570232880546597335636361816325245444237275023999522533527764240730547185826755972838574195391038131656239536920948158465916528880835693552792260356361022462682037427718404037021825844211741628768123221090717527493
a = 285426137705625850725555147387995674019
b = 277985464990476154618471183198080357743
c1 = 9426395562512809581013620472326672750327318596813074726353079091173842802365552984264585030513998874440683981314827988473250779276622812642078592270162488257445750556180090334901558598065090257832879692296066144186335139137620672058976438826755846843815726564085636220609216862492337842110335421544935056753632826033207088809042045528566533513130910178132026694855125856386336197708244017301467175024440126022121500756597
c2 = 7817626870900560837063304883188246502988767588941344995287074193857215881437472677956793645281329763767094907997432409446021978284194802133451654430505222891535367029301384789198710394554265321474931034378249847884399129098152817955822667403789421376159327548545340231962148603594715994813791837670639630747654837874296940404313828931665262517234613625655607389345122624044747819855804429899373080756267420097146009333048

def attack(c1, c2, a, b, e, n):
    PR.<x>=PolynomialRing(Zmod(n))
    g1 = x^e - c1
    g2 = (a*x + b)^e - c2

    def gcd(g1, g2):
        while g2:
            g1, g2 = g2, g1 % g2
        return g1.monic()
    print(gcd(g1, g2))
    return -gcd(g1, g2)[0]

m1 = attack(c1, c2, a, b, 5, n)
flag = long_to_bytes(int(m1))
print(flag)

Coppersmith’s Short Pad Attack

假设随机填充消息之后加密发给，攻击者截获了这个密文，阻止了收到这个消息，意识到没有收到这个消息，重新对明文进行填充并且加密后继续发送。攻击者现在有两个不同padding的密文，借助这两个密文攻击者能恢复明文。

证明：定义,，我们知道当时，是这两个方程共同的根，换句话说,是"resultant"之后的根。这里的resultant是结式。这时候我们求出再用线性相关攻击求解.

举个栗子

task.py

from Crypto.Util.number import *
m = bytes_to_long(b'NSSCTF{******}')

p = getPrime(512)
q = getPrime(512)

n = p*q

e = 9

r = getPrime(512)

c1 = pow(m, e, n)
c2 = pow(m+r, e, n)


print(f'c1 = {c1}')
print(f'c2 = {c2}')
print(f'r = {r}')
print(f'n = {n}')


'''
c1 = 135074766579407676786282087896424573055829820741326911395660008092908906818293714163243721440579480398437184153110701014575949020137195005556115765711856362529093323957313305701439430406396620730435232669024347062255561124227077117736226705746520202121773331267896121082546807985584499775544186860738299210902
c2 = 52198561898892210533988782934627447441579509170862004216826284305082884787397969852570583444422705227177306845788090962326207704949679636373972262848806083888114511515323970306654941921527306928423850775839578728701294521014874290792581635297504014585143468088934951952990888189000603302912352199468290961647
r = 7226418134082605571805056000800553195029496658257912353583130240746954757224748488491991266548553899116384605868480860827154816241193159482670000874841821
n = 144690523587663809780722437199578577582544144694543134253077982812595463236242062416509866333774784681011350541203308061301675822157859373788530465702809816586981803008466959154241234879285863437666243631170277595720205934928759253610014553402523757331771549475265418644503305010214366648156173843801360148229
'''

exp.py

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

def franklinReiter(n,e,r,c1,c2):
    R.<X> = Zmod(n)[]
    f1 = X^e - c1
    f2 = (X + r)^e - c2
    return Integer(n-(compositeModulusGCD(f1,f2)).coefficients()[0])


def compositeModulusGCD(a, b):
    if(b == 0):
        return a.monic()
    else:
        return compositeModulusGCD(b, a % b)

def CoppersmithShortPadAttack(e,n,C1,C2,eps=1/30):
    """
    求解r
    Figured out from: https://en.wikipedia.org/wiki/Coppersmith's_attack#Coppersmith.E2.80.99s_short-pad_attack
    """
    P.<x,y> = PolynomialRing(ZZ)
    ZmodN = Zmod(n)
    g1 = x^e - C1
    g2 = (x+y)^e - C2
    res = g1.resultant(g2)
    P.<y> = PolynomialRing(ZmodN)
    rres = 0
    # 这一步的目的是因为虽然res只包含y，但它还是在二元多项式环空间中，我们提取系数和指数重新生成一个一元多项式
    for i in range(len(res.coefficients())):
        rres += res.coefficients()[i]*(y^(res.exponents()[i][1]))

    diff = rres.small_roots(epsilon=eps)
    return int(diff[0])


c1 = 135074766579407676786282087896424573055829820741326911395660008092908906818293714163243721440579480398437184153110701014575949020137195005556115765711856362529093323957313305701439430406396620730435232669024347062255561124227077117736226705746520202121773331267896121082546807985584499775544186860738299210902
c2 = 52198561898892210533988782934627447441579509170862004216826284305082884787397969852570583444422705227177306845788090962326207704949679636373972262848806083888114511515323970306654941921527306928423850775839578728701294521014874290792581635297504014585143468088934951952990888189000603302912352199468290961647
r = 7226418134082605571805056000800553195029496658257912353583130240746954757224748488491991266548553899116384605868480860827154816241193159482670000874841821
n = 144690523587663809780722437199578577582544144694543134253077982812595463236242062416509866333774784681011350541203308061301675822157859373788530465702809816586981803008466959154241234879285863437666243631170277595720205934928759253610014553402523757331771549475265418644503305010214366648156173843801360148229

m = franklinReiter(n, 9, r, c1, c2)
print(long_to_bytes(m))