带填充的RSA共模攻击(CooperSmith/p高位泄露)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

from Crypto.Util.number import *
import gmpy2
# from secret import flag,x
x = 13 # 利用e的二进制位长推测出x的二进制位长
flag = r'DASCTF{94c8c21d08740f5da9eaa38d1f175c592692f0d1}'

FLAG = hex(bytes_to_long(bytes(flag.encode())))
print(len(FLAG))
while len(FLAG)  < 2048:
  FLAG += '00'
# DEBUG
"""
FLAGa=int(FLAG,16) # 16进制转10进制
print(f'hex->{FLAGa:x}') # hex
print(len(bin(FLAGa))) # flag的二进制位长 # 填充前385 # 填充后8xxx
"""

def task(n, p, q):
  e = x * getPrime(25)
  print(e)
  pk, sk = (n, e), (inverse(e, (p-1)*(q-1)))
  # print (f"privkey = {sk}")
  print (f"pubkey = {pk}")
  assert FLAG < pk[0]
  c = pow(FLAG, pk[1], pk[0]) # c = FLAG^e mod n
  print (f"ciphertext = {c}")

p = getPrime(4096)
q = getPrime(4096)
n = p * q
task(n, p, q)
task(n, p, q)

'''
pubkey = (631704658316107316476631662851232513167305743724051186158554607216138665758651383999780489278091838560489032372900267377736237142312800325510839644655041019350454746285608148076069877827331570306531360928735706136940744879296188814218221415268468882601401290453513620058967937490229879350100210840273601673434791156967887168489949398909636232265730565157705645074778099335973868420591684971700842192135737822163092719010899899900906950920588813409920740847058646752828785385873772281705505151082567637301753513073178877382222686947884464356503084436710964721728934103667575388962027500496785366512559779503975171067515648474317451743950311102788378592650584074924518502042800806374634257689006701099537082929839880680716644107887107277545440883202850169389561038503505611543517665847099355309543791726704508828412748648083667615253805811065493087765182890641394941547224007410230582635739282572999784818993426524660322506552777173684682345617903709438634566739636646813598805189824096257101005511591646200477114782395355594700543654172045449061307743391984162366457405661384570894282509109440702579925256407640046816406501144647037050778323528329913821976003677989099891054333950811501262124243258915504259130280580230299912657442669541457718378886950829044993718306207245034570466513477929865019679408238431035969390774039176113600326758938598312905961726761447479195236692754661127098476166335245118569319315163868742823661391978080155625395638363389335880296389371811509103078703583364479544504724117424456267398768483363594014016511039412147353322943732886624729667119668931889622044935822991901046638537981486137324641851248938171721925238794095980507451649422011021294020116758658798903892915685251627983627496145518772566258707836493016012354879299011651025514693262138104102713765715302120633524663935787265638025681461758686836356777160007235880219089378478714987895528233499888588134943176336612314910896457649467880092378885848765474948336418203366356857880128284792653134100961580205274724342493185974704960927765508980506809171289317650392381155261841525346094897909282358464631129565142466841251641574182477290680783110373339041696933558390263892986185187988896102175806358089155531818651838775580994959917250173754629890300524280224596458984449283141274434578618610753309471105156475116451614745170121602666465090430931564872929117390734021763304624273646435586790080907671369751246596652914201599305562484432951782931086073027568703037735327284365677, 472554661)
ciphertext = 190987504276417030459995870118018106411927956775759012847742153271115853081408559439515500090420659778337774251322924763583703744945725548117826596107116645542242417390155411579632955292564528520440614260557243094399833823703776825260174109620647075222266930807489850145653178950535314869608224045341462372136686325390890689054405086686001100811443562979660892626976910848883193606213100173930615655868314435984441387498754642165766151061008739536079031140840087582367396856029192985567585098853421231849021423950166776436360731699210565052814347301305136231030452336673072044401519429834369139140245097717477442207591860572819484092848769895526302884706675965820142765147054286070702591314107210105634638529040955739525959665452187152373744418055109385189923937410612814332368059055442697514476224539572446022119292246216864736507911101687770449399470300111493467761898288339606268218461414713869261621265548926431739969658851060588469847933207757035870820118151506632080848622808949107266876446402143532885158806752022647196657389362551812094658375646137420717912004993731588408266942954086191081329114054376690515702418030563123621308538946327414923689799905388809280810108810572604423052944060166210108864637349960969813576226954947569269001567594538036335239515820446049796338189866087489579415290966515988794972617897613114169306902686552315662681234085741908135003796792983996537217079533422533672875702933249385450293644264481727769868049295596687776551250104869253909976864238705319499867029873108947287715051353048589899005756254898493157435715455584382285421252226592815717633100684130833535313398285854135049104416584931630961649612263799668626605766084592830857431301960508118967957132590949622478565095552894302156456587375827654576193163705593838932559456550980547713264158180558179573064749914083291869665313434519298805872794848445531668240282892429504465717077102142829322223537966050798014877242907116850396358948946563266157495445976661243015703150210392054301115412770660862765408166194109344334156035055331784788156175540722143596029916953303656978173674438529512674377683439887526966586680024643214529230521291448281299492022962381836977335458591380009655069999490948962732861301906043829089176993890552623525778739163797525576145126381504772928706462746770945831728396867697460511548895998660335284720579047966498756660763368794251021798470067833203405996009675602949792544182705941386274781263007295426151053568079918978166706088381712821903
pubkey = (631704658316107316476631662851232513167305743724051186158554607216138665758651383999780489278091838560489032372900267377736237142312800325510839644655041019350454746285608148076069877827331570306531360928735706136940744879296188814218221415268468882601401290453513620058967937490229879350100210840273601673434791156967887168489949398909636232265730565157705645074778099335973868420591684971700842192135737822163092719010899899900906950920588813409920740847058646752828785385873772281705505151082567637301753513073178877382222686947884464356503084436710964721728934103667575388962027500496785366512559779503975171067515648474317451743950311102788378592650584074924518502042800806374634257689006701099537082929839880680716644107887107277545440883202850169389561038503505611543517665847099355309543791726704508828412748648083667615253805811065493087765182890641394941547224007410230582635739282572999784818993426524660322506552777173684682345617903709438634566739636646813598805189824096257101005511591646200477114782395355594700543654172045449061307743391984162366457405661384570894282509109440702579925256407640046816406501144647037050778323528329913821976003677989099891054333950811501262124243258915504259130280580230299912657442669541457718378886950829044993718306207245034570466513477929865019679408238431035969390774039176113600326758938598312905961726761447479195236692754661127098476166335245118569319315163868742823661391978080155625395638363389335880296389371811509103078703583364479544504724117424456267398768483363594014016511039412147353322943732886624729667119668931889622044935822991901046638537981486137324641851248938171721925238794095980507451649422011021294020116758658798903892915685251627983627496145518772566258707836493016012354879299011651025514693262138104102713765715302120633524663935787265638025681461758686836356777160007235880219089378478714987895528233499888588134943176336612314910896457649467880092378885848765474948336418203366356857880128284792653134100961580205274724342493185974704960927765508980506809171289317650392381155261841525346094897909282358464631129565142466841251641574182477290680783110373339041696933558390263892986185187988896102175806358089155531818651838775580994959917250173754629890300524280224596458984449283141274434578618610753309471105156475116451614745170121602666465090430931564872929117390734021763304624273646435586790080907671369751246596652914201599305562484432951782931086073027568703037735327284365677, 512060519)
ciphertext = 118105806757364864954099740578039575095067736310062562032293775737146734292611491109686416485919016851405784908499094267565612303208935666612372955592240502275304246975609627506123058353391372656409432910534157579594786467732926369572526172564718924601625672422241852492488550283148235537506268392245305690156723219564226402432576938782454753759983137914472704648591878027847262615725429446005016635025420868133866811373289327645413411453859339757836991093908071638328453514104881336701917644665804786789489323672785875877061237766568407039151396946704985496018147569926911261898580756098479100237007941318401021279795364728719207372661460410387690657138651731327964723514386572694325652597994434813931414394101200087900718036550266207104274280840585258295937618660007576916346971377563537978904909890356241631994402505853975554712900758886256393960997065883072603649541752328064420102794034716350179526975824164679514497545031932376505630561041528122534350326851355630277189536132079819347591965123978267329957678172531541870774152820885892748994104282993783130986435408443990102761662449293721684054746590737624241714144192554974418174740935392026309752818843371184788181135723934755921015195135100434571963047279241020959200031451732709183509226119313388765957669702752972765899086633745040942547050498490884353694399849142077796452902507813258263359599139001375752871961305870647115285853030278057230051592204611282860281668566134180445475472981874013691475514350039449881223501881564079522206136571985922976022429024806580161050812111546949423979614963273484255330194797143216964745972075353014043464318808527670570025723913145381743890479373651559112882154125825193684319648524540319399295496316455910887675719072214746078300659747824900422025873021264607615059776370887811316751386521720353564213575161113649210936024834236497270467247374376806151520458934834474873512780450459065406794893079375072143242760903847107206702819919541243590083307963659134589118157841441127260628026207634262496423960483763853574351631049111656076943501743107444844944097456043724623057099318681823470304041478338060550105843257247135981311666581587388804168534632878003367114935690158903476684427898910282066938176875785040879979309200489444338815528259008540300389580292768148738299179013875917009766599802284812113802699460093538336768415249967785549217725394898178950705893233820694790774211856222175935024768782962788732209486972454385313819695038224886978798800124937584338
'''

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

import libnum
import gmpy2
from tqdm import tqdm

n = 631704658316107316476631662851232513167305743724051186158554607216138665758651383999780489278091838560489032372900267377736237142312800325510839644655041019350454746285608148076069877827331570306531360928735706136940744879296188814218221415268468882601401290453513620058967937490229879350100210840273601673434791156967887168489949398909636232265730565157705645074778099335973868420591684971700842192135737822163092719010899899900906950920588813409920740847058646752828785385873772281705505151082567637301753513073178877382222686947884464356503084436710964721728934103667575388962027500496785366512559779503975171067515648474317451743950311102788378592650584074924518502042800806374634257689006701099537082929839880680716644107887107277545440883202850169389561038503505611543517665847099355309543791726704508828412748648083667615253805811065493087765182890641394941547224007410230582635739282572999784818993426524660322506552777173684682345617903709438634566739636646813598805189824096257101005511591646200477114782395355594700543654172045449061307743391984162366457405661384570894282509109440702579925256407640046816406501144647037050778323528329913821976003677989099891054333950811501262124243258915504259130280580230299912657442669541457718378886950829044993718306207245034570466513477929865019679408238431035969390774039176113600326758938598312905961726761447479195236692754661127098476166335245118569319315163868742823661391978080155625395638363389335880296389371811509103078703583364479544504724117424456267398768483363594014016511039412147353322943732886624729667119668931889622044935822991901046638537981486137324641851248938171721925238794095980507451649422011021294020116758658798903892915685251627983627496145518772566258707836493016012354879299011651025514693262138104102713765715302120633524663935787265638025681461758686836356777160007235880219089378478714987895528233499888588134943176336612314910896457649467880092378885848765474948336418203366356857880128284792653134100961580205274724342493185974704960927765508980506809171289317650392381155261841525346094897909282358464631129565142466841251641574182477290680783110373339041696933558390263892986185187988896102175806358089155531818651838775580994959917250173754629890300524280224596458984449283141274434578618610753309471105156475116451614745170121602666465090430931564872929117390734021763304624273646435586790080907671369751246596652914201599305562484432951782931086073027568703037735327284365677
e1 = 472554661
e2 = 512060519
c1 = 190987504276417030459995870118018106411927956775759012847742153271115853081408559439515500090420659778337774251322924763583703744945725548117826596107116645542242417390155411579632955292564528520440614260557243094399833823703776825260174109620647075222266930807489850145653178950535314869608224045341462372136686325390890689054405086686001100811443562979660892626976910848883193606213100173930615655868314435984441387498754642165766151061008739536079031140840087582367396856029192985567585098853421231849021423950166776436360731699210565052814347301305136231030452336673072044401519429834369139140245097717477442207591860572819484092848769895526302884706675965820142765147054286070702591314107210105634638529040955739525959665452187152373744418055109385189923937410612814332368059055442697514476224539572446022119292246216864736507911101687770449399470300111493467761898288339606268218461414713869261621265548926431739969658851060588469847933207757035870820118151506632080848622808949107266876446402143532885158806752022647196657389362551812094658375646137420717912004993731588408266942954086191081329114054376690515702418030563123621308538946327414923689799905388809280810108810572604423052944060166210108864637349960969813576226954947569269001567594538036335239515820446049796338189866087489579415290966515988794972617897613114169306902686552315662681234085741908135003796792983996537217079533422533672875702933249385450293644264481727769868049295596687776551250104869253909976864238705319499867029873108947287715051353048589899005756254898493157435715455584382285421252226592815717633100684130833535313398285854135049104416584931630961649612263799668626605766084592830857431301960508118967957132590949622478565095552894302156456587375827654576193163705593838932559456550980547713264158180558179573064749914083291869665313434519298805872794848445531668240282892429504465717077102142829322223537966050798014877242907116850396358948946563266157495445976661243015703150210392054301115412770660862765408166194109344334156035055331784788156175540722143596029916953303656978173674438529512674377683439887526966586680024643214529230521291448281299492022962381836977335458591380009655069999490948962732861301906043829089176993890552623525778739163797525576145126381504772928706462746770945831728396867697460511548895998660335284720579047966498756660763368794251021798470067833203405996009675602949792544182705941386274781263007295426151053568079918978166706088381712821903
c2 = 118105806757364864954099740578039575095067736310062562032293775737146734292611491109686416485919016851405784908499094267565612303208935666612372955592240502275304246975609627506123058353391372656409432910534157579594786467732926369572526172564718924601625672422241852492488550283148235537506268392245305690156723219564226402432576938782454753759983137914472704648591878027847262615725429446005016635025420868133866811373289327645413411453859339757836991093908071638328453514104881336701917644665804786789489323672785875877061237766568407039151396946704985496018147569926911261898580756098479100237007941318401021279795364728719207372661460410387690657138651731327964723514386572694325652597994434813931414394101200087900718036550266207104274280840585258295937618660007576916346971377563537978904909890356241631994402505853975554712900758886256393960997065883072603649541752328064420102794034716350179526975824164679514497545031932376505630561041528122534350326851355630277189536132079819347591965123978267329957678172531541870774152820885892748994104282993783130986435408443990102761662449293721684054746590737624241714144192554974418174740935392026309752818843371184788181135723934755921015195135100434571963047279241020959200031451732709183509226119313388765957669702752972765899086633745040942547050498490884353694399849142077796452902507813258263359599139001375752871961305870647115285853030278057230051592204611282860281668566134180445475472981874013691475514350039449881223501881564079522206136571985922976022429024806580161050812111546949423979614963273484255330194797143216964745972075353014043464318808527670570025723913145381743890479373651559112882154125825193684319648524540319399295496316455910887675719072214746078300659747824900422025873021264607615059776370887811316751386521720353564213575161113649210936024834236497270467247374376806151520458934834474873512780450459065406794893079375072143242760903847107206702819919541243590083307963659134589118157841441127260628026207634262496423960483763853574351631049111656076943501743107444844944097456043724623057099318681823470304041478338060550105843257247135981311666581587388804168534632878003367114935690158903476684427898910282066938176875785040879979309200489444338815528259008540300389580292768148738299179013875917009766599802284812113802699460093538336768415249967785549217725394898178950705893233820694790774211856222175935024768782962788732209486972454385313819695038224886978798800124937584338
# while len(FLAG)  < 2048:
#   FLAG += '00'
FlagLen = 2048

def rsa_gong_N_def(e1,e2,c1,c2,n):  #共模攻击函数
    e1, e2, c1, c2, n=int(e1),int(e2),int(c1),int(c2),int(n)
    print("e1,e2:",e1,e2)
    s = xgcd(e1, e2) # 无sage用gmpy2.gcdext
    print("mpz:",s)
    s1 = s[1]
    s2 = s[2]
    if s1 < 0:
        s1 = - s1
        c1 = gmpy2.invert(c1, n)
    elif s2 < 0:
        s2 = - s2
        c2 = gmpy2.invert(c2, n)
    m = (pow(c1,s1,n) * pow(c2 ,s2 ,n)) % n
    return int(m)
 

def de(c, e, n): #因为此时的m不是真正的m，而是m^k，所以对m^k进行爆破
    k = 0
    while k < 1000000:
        mk = c + n*k
        flag, true1 = gmpy2.iroot(mk, e)  #返回的第一个数值为开方数，第二个数值为布尔型，可整除为true，可自行测试
        if True == true1:
            # print(libnum.n2s(int(flag)))
            return flag
        k += 1

# 已知 e1 * e2 时用
# for e1 in range(2,e1e2):
#     if e1e2%e1==0:         #爆破可整除的e
#         e2=e1e2//e1
#         c=rsa_gong_N_def(e1, e2, c1, c2, n)
#         e=gmpy2.gcd(e1,e2)
#         m1=de(c, e, n)
#         if m1:  #指定输出m1
#             print(libnum.n2s(int(m1)))

est = xgcd(e1, e2)
estE, estS, estT = est[0], est[1], est[2]
import re
# 因为FLAG填充了00 所以先爆i 也就是flag未被填充的长度
for i in tqdm(range(0,FlagLen * 4)):
    tmp1 = pow(int(1 << (FlagLen * 4 - i)), int(e1), n) # flag长度还可以从加密程序跑 -> print(len(bin(FLAG))) 得出
    cC1 = (inverse_mod(tmp1, n) * c1) % n # 去除填充
    tmp2 = pow(int(1 << (FlagLen * 4 - i)), int(e2), n)
    cC2 = (inverse_mod(tmp2, n) * c2) % n

    cFinal = (pow(cC1, est[1], n) * pow(cC2, est[2], n)) % n
    m = gmpy2.iroot(cFinal,estE)[0] # 开e次方 gcd(e1,e2) != 1
    m = libnum.n2s(int(m))
    # flag格式 ..{..} 正则-> \{.*\} -> 在m中匹配
    # if b'{' in m:
    #     print(f'[+]i = {i}\n[+]m = {m}')
    #     break
    
    pattern = br"\b\w+\{[^{}]+\}" # 匹配以单词字符开头，后跟 {，然后是任意非 {} 字符的部分
    matches = re.findall(pattern, m)
    if matches:
        for match in matches:
            print(f"[+] found: i = {i} m = {match.decode('latin-1')}")
    # else:
        # print("No matches found.")

# 无填充
# c=rsa_gong_N_def(e1, e2, c1, c2, n)
# e=gmpy2.gcd(e1,e2)
# m1=de(c, e, n) # None
# if m1:  #指定输出m1
    # print(libnum.n2s(int(m1)))

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

n = 100648020838898022078488174669858238948252836355880539604184902591446419770655885640874064838016019504757930468526372365287305834911724922755268247689576555258382714443704683337773876570423896859743037673553952616874309723157733040117468274797520314398827998862239801778155652946432995909202504755802439345263
c = 19226780830171024402997593279952814726911151994955441335543843050438731454913304587804155519483305398866497814560686326692709816865094055248395778032165101658510727343245564600691062362841699148758815931344580850649347166763193322551661496913442049415738625451483676883244087797156957033420894246351072763594
p0 = 105438533404834795699367761354925025333799627494289655936363193805277843569948959493479728388550726889295528216927
e = 65537

from Crypto.Util.number import long_to_bytes, getPrime
from tqdm import *
# copperSmith 
for unknown_bit_len in trange(1, 400):
    R.<x> = PolynomialRing(Zmod(n))
    p = p0 * (10 ** unknown_bit_len) + x
    # betaF = unknown_bit_len / 512
    betaF = 0.48
    root = p.monic().small_roots(X = 10^unknown_bit_len, beta = betaF) # beta: 缺了多少位/一共多少位
    if root:
        p = int(p(root[0]))
        q = n // p
        assert n == p * q
        d = inverse_mod(e, (p-1)*(q-1))
        print(unknown_bit_len)
        print(long_to_bytes(pow(c, d, n)))
        break

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

# Author: hash_hash
n = 100648020838898022078488174669858238948252836355880539604184902591446419770655885640874064838016019504757930468526372365287305834911724922755268247689576555258382714443704683337773876570423896859743037673553952616874309723157733040117468274797520314398827998862239801778155652946432995909202504755802439345263
c = 19226780830171024402997593279952814726911151994955441335543843050438731454913304587804155519483305398866497814560686326692709816865094055248395778032165101658510727343245564600691062362841699148758815931344580850649347166763193322551661496913442049415738625451483676883244087797156957033420894246351072763594
p0 = 105438533404834795699367761354925025333799627494289655936363193805277843569948959493479728388550726889295528216927
e = 65537

PR.<x> = PolynomialRing(Zmod(n))
f = p0*10^41+x
root = f.small_roots(X=10^41, beta=0.48)[0]
p = int(p0*10^41+root)
q = n//p
phi = (p-1)*(q-1)
d = inverse_mod(e, phi)
m = pow(c, d, n)
print(bytes.fromhex(hex(m)[2:]))
#b'flag{Sag3_i3_1mp0rt4nt_Sag3_i3_1mp0rt4nt_Sag3_i3_1mp0rt4nt!}'

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

n = 100648020838898022078488174669858238948252836355880539604184902591446419770655885640874064838016019504757930468526372365287305834911724922755268247689576555258382714443704683337773876570423896859743037673553952616874309723157733040117468274797520314398827998862239801778155652946432995909202504755802439345263
c = 19226780830171024402997593279952814726911151994955441335543843050438731454913304587804155519483305398866497814560686326692709816865094055248395778032165101658510727343245564600691062362841699148758815931344580850649347166763193322551661496913442049415738625451483676883244087797156957033420894246351072763594
high_p = 105438533404834795699367761354925025333799627494289655936363193805277843569948959493479728388550726889295528216927
e = 65537

from Crypto.Util.number import long_to_bytes, getPrime
from tqdm import *
# copperSmith 
def phase3(high_p, n, e, c, final_p_unknow_bitlen, p_complete_len):
    high_p = high_p * 10 ** final_p_unknow_bitlen # 生成形如 p >> final_p_unknow_bitlen << final_p_unknow_bitlen 的数, 也就是 p 的最后 final_p_unknow_bitlen 位为 0, 高位泄露标准格式
    R.<x> = PolynomialRing(Zmod(n), implementation='NTL') # NTL: Number Theory Library
    p = high_p + x
    # betaF = unknown_bit_len / p_complete_len
    betaF = 0.48 # 一般为 0.48
    x0 = p.small_roots(X = 10^final_p_unknow_bitlen, beta = betaF)[0] # beta: 缺了多少位/一共多少位
    # print(f'{p.small_roots(X = 2^unknown_bit_len, beta = betaF) = }') # p.small_roots(X = Integer(2)**P未知的bit_len, beta = betaF) = [75667606273019047085258871949587411011977]
    P = int(p(x0))
    Q = n // P
    assert n == P*Q
    d = inverse_mod(e, (P-1)*(Q-1))
    print(f'{hex(power_mod(c, d, n)) = }')
    print(long_to_bytes(power_mod(c, d, n)))
# DEBUG
"""CTF
# 二进制长
temp1 = getPrime(512)
temp2 = getPrime(512)
print(len(bin(temp1 * temp2)) - 2 == len(bin(n)) - 2)  # n 1024, p q 都是 512
"""
# phase3(high_p, n, e, c, 41, 512) # b'flag{Sag3_i3_1mp0rt4nt_Sag3_i3_1mp0rt4nt_Sag3_i3_1mp0rt4nt!}'
final_p_unknow_bitlen = len("10543853340483479569936776135492502533379") 
phase3(high_p, n, e, c, final_p_unknow_bitlen, 512) # b'flag{Sag3_i3_1mp0rt4nt_Sag3_i3_1mp0rt4nt_Sag3_i3_1mp0rt4nt!}'