跳跳糖
为什么说是针对CTFer的呢，本篇文章可能针对实用性强一点，针对算法的原理剖析会少一些。最后会总结出板子放在文章的结尾。
0x00 前言
在平常遇到的问题中，如果能求出公钥n的欧拉函数
，可以说这个RSA加解密问题已经接近成功了。要求私钥d需要求出e在phi中的逆元使得
，但直接求逆元需要满足一个前提就是gcd(e,phi)==1，也就是说e与phi是互素的，如果不互素，问题的复杂度将会增加不少。
相信在这个问题中，有一道CTF题是比较出名的，NCTF2019，附件如下
from flag import flag
e = 0x1337
p = 199138677823743837339927520157607820029746574557746549094921488292877226509198315016018919385259781238148402833316033634968163276198999279327827901879426429664674358844084491830543271625147280950273934405879341438429171453002453838897458102128836690385604150324972907981960626767679153125735677417397078196059
q = 112213695905472142415221444515326532320352429478341683352811183503269676555434601229013679319423878238944956830244386653674413411658696751173844443394608246716053086226910581400528167848306119179879115809778793093611381764939789057524575349501163689452810148280625226541609383166347879832134495444706697124741
n = p * q
assert(flag.startswith('NCTF'))
m = int.from_bytes(flag.encode(), 'big')
assert(m.bit_length() > 1337)
c = pow(m, e, n)
print(c)
# 10562302690541901187975815594605242014385201583329309191736952454310803387032252007244962585846519762051885640856082157060593829013572592812958261432327975138581784360302599265408134332094134880789013207382277849503344042487389850373487656200657856862096900860792273206447552132458430989534820256156021128891296387414689693952047302604774923411425863612316726417214819110981605912408620996068520823370069362751149060142640529571400977787330956486849449005402750224992048562898004309319577192693315658275912449198365737965570035264841782399978307388920681068646219895287752359564029778568376881425070363592696751183359
看似白给，但是这题的逆元d是求不出来的，因为e与phi不互素，gcd(e,p-1)==gcd(e,q-1)==gcd(e,phi)==e。该题的具体解法最后讨论，下面是我对e与phi不互素问题的一些小总结。
令t=gcd(e,phi)
①
这种情况可以把m^t看成一个新的需要求的明文，这里以一道我自己之前摸鱼出的一道题目为例，附件如下
from Crypto.Util.number import *
from secret import flag
flag = b'flag{*********}'
m = bytes_to_long(flag)
p = getPrime(1024)
q = getPrime(1024)
n = p * q
e = 114
c = pow(m,e,n)
print(c)
print(p >> 200)
print(n)
# 4981370648841772812759645290740849305394680703208798679296466901875830602835273402860232301263281323578956193947979697234640828088984992529165349436050379602381023059635247562226192384089521639938396211636613132291696135696985578958227320544060232615333466684704244997055833821133086665356126147182204658744167431612986909752009485714137028204041440181653812250548914729617593568901044728464293232061709058144788756823288190386071071979728390993033661221130338943191220680445314588574185565138844949934691183548291792150029676489045342419826189506616272247940278820931530398810621850374268800818970515221497093852109
# 62037304914409314363888940906845820031382619388386590204815535497699521033644001814874589864676342418539729790446530529473631795496696578029445470682035483391568820927435567100377626022924900710513454770616746573110984342344183967600234091673261776
# 10315159385090642346129000730749042701431892949303034712476198921384639021767097119992198421632142955005047146294210952031882321038272269972695714084199530336742619691272883151455898061330316812891004827724782855036289498818157782936179413509824274682055131552093071749522986951202502017564120645520386407170556413591537187759567563157956331577316042296031033014710853038209000676314440817362756989634719336973373719581572614119144998829076893422175956726616346716072744575347893245428145235967836165207095908913238287634122873060994828380614739915448587956681845973466847711337763120292734433687845920176310499582951
其中第一部分是一个p泄露高位的问题，老生常谈了，这里不过多赘述。求出p之后我们发现，e与phi不互素且公约数t=gcd(e,phi)=6，当时出题的flag值未设很长，故可进行尝试，数论推导如下：
用此公钥，即有如下关系
其中m^t可求且，即直接对m^t进行开t次方根即可。exp如下：
from Crypto.Util.number import *
import gmpy2
c = 4981370648841772812759645290740849305394680703208798679296466901875830602835273402860232301263281323578956193947979697234640828088984992529165349436050379602381023059635247562226192384089521639938396211636613132291696135696985578958227320544060232615333466684704244997055833821133086665356126147182204658744167431612986909752009485714137028204041440181653812250548914729617593568901044728464293232061709058144788756823288190386071071979728390993033661221130338943191220680445314588574185565138844949934691183548291792150029676489045342419826189506616272247940278820931530398810621850374268800818970515221497093852109
e = 114
p = 99690105430259549732952386298363416480730988331578091065948950836198178325904426675017504756348563688521763268566954512895974110780822714951824351709232320913381679046309934991336770483285399157355308073567950907088479972767984569322594411195698421500521401221792581871025328456951904596576566123729811756413
n = 10315159385090642346129000730749042701431892949303034712476198921384639021767097119992198421632142955005047146294210952031882321038272269972695714084199530336742619691272883151455898061330316812891004827724782855036289498818157782936179413509824274682055131552093071749522986951202502017564120645520386407170556413591537187759567563157956331577316042296031033014710853038209000676314440817362756989634719336973373719581572614119144998829076893422175956726616346716072744575347893245428145235967836165207095908913238287634122873060994828380614739915448587956681845973466847711337763120292734433687845920176310499582951
q = 103472248730911851254553434648605804338564109979871343883653538836587422384404224866918549458325035655810767726029600292489262023711038658950506809510441640439838143226881684645307170720125749718552087605871880391263080540577543652043401824062555993901349884856226877853115632353980186588864859131611388824627
phi = (p - 1) * (q - 1)
t = gmpy2.gcd(e,phi)
print(t)
_e = e // t
d = gmpy2.invert(_e,phi)
_m = pow(c,d,n)
m = gmpy2.iroot(_m,t)[0]
print(long_to_bytes(m))
②
这种情况需要结合中国剩余定理求解，由于，就不能再单纯地用第一种方法，应该尝试在有限域内开根。以一道例题(2022ctfshow卷王杯现代密码签到)为例，附件：
from Crypto.Util.number import bytes_to_long
from secrets import p,q,r,s,t,flag
n = p * q * r * s * t
e = 2
m = bytes_to_long(os.urandom(500) + flag)
c = pow(m,e,n)
print(p,q,r,s,t,sep='\n')
print(c)
'''
145332367700944303747548912160113939198078051436029477960348968315913956664143693347226702600438608693933768134575289286283267810723137895903153829001826223446477799895493265422562348917012216790077395795861238257357035152687833639085415763850743538206986781418939737511715957738982536382066693822159860701263
116660458253067608044065523310547233337730583902133756095473339390057738510707447906971188577217274861047379404014140178165569604404468897712846876108444468370709141219302291601408652742006268186059762087155933131837323952675627966299810891805398890428420575425160696531236660480933905879208166090591482794763
157931722402853245421436270609912823260313730941283152856444641969403238646482562190531038393124087232554754746464603598717356255570166081501573727336977292059427220330169044611674973569766966838498453232642731737958791706086957762244686953294662693939604300864961637325536379321027705854708492453330690705531
100973451687449518854742673778783266158999451072058606348222018797891147675959983616210003484476577612134482311993701677242007759556951494382833070563369964294544839433671087037596159753825249018950693369209927951667775267086896180395776150188902057785214767230658487267587289809918132337927575673868568976679
93960345071948255233882121683650797512129333868351496468898834736770441398743300745703393838320587998953678254272245400344928586394089488734271897540051673996675973642347859306921527430850673334243441180183460927865980713929789963587608547554858491264614271309608925634272282292964002897650355047792764365447
9144597920381774885442906257311149465702295057238600973973598305004391534618770363098565074541384771979931799878381439264848137810353858418200992191234142740194489573540381681161219332611454834544291634628456257670178843484698324641739324687497388018406214041657278323855749902661752448796122517061920880552011343608609622885787617238758769398972009949575526258430282648817039091284796330585349957724522615105102735930258969562103112238020133587096826386028128471852377225525357348919204333121695432662339443004327748973224423132988376298843862056631045488285859621661802413201793962883794915513510467912312842687601478117040419013468059983777273699192408773551806581458197324620065210523913467414181480875280203580147077789063808832356486197271376615883221558265591069223727607585313240243619515521180600435114131162272519949101464089935441251751426683447701142156416866113627126765919641034042927519834229168536331952275698122511502745177547569813354280565828372968703810158857859460406828090199683324760956105682902577189283246483314689365570862217407333103243336691401424548702387876409228977278498691200028282744239512091373110111792177228979867318546462714521296256938374618636206565791541769138267080789842400796973226733816939794717596194090232425688504890234304977612220790858557639246367437740975495450011676714198668471438814299689325208882261918460708833888406187912527346628912894921059735420931656953236560178909180587372589456926690219114173193202048332172538564489660440225377822914097420807957784201785024166011709377791129
'''
from Crypto.Util.number import bytes_to_long
from secrets import p,q,r,s,t,flag
n = p * q * r * s * t
e = 2
m = bytes_to_long(os.urandom(500) + flag)
c = pow(m,e,n)
print(p,q,r,s,t,sep='\n')
print(c)
'''
145332367700944303747548912160113939198078051436029477960348968315913956664143693347226702600438608693933768134575289286283267810723137895903153829001826223446477799895493265422562348917012216790077395795861238257357035152687833639085415763850743538206986781418939737511715957738982536382066693822159860701263
116660458253067608044065523310547233337730583902133756095473339390057738510707447906971188577217274861047379404014140178165569604404468897712846876108444468370709141219302291601408652742006268186059762087155933131837323952675627966299810891805398890428420575425160696531236660480933905879208166090591482794763
157931722402853245421436270609912823260313730941283152856444641969403238646482562190531038393124087232554754746464603598717356255570166081501573727336977292059427220330169044611674973569766966838498453232642731737958791706086957762244686953294662693939604300864961637325536379321027705854708492453330690705531
100973451687449518854742673778783266158999451072058606348222018797891147675959983616210003484476577612134482311993701677242007759556951494382833070563369964294544839433671087037596159753825249018950693369209927951667775267086896180395776150188902057785214767230658487267587289809918132337927575673868568976679
93960345071948255233882121683650797512129333868351496468898834736770441398743300745703393838320587998953678254272245400344928586394089488734271897540051673996675973642347859306921527430850673334243441180183460927865980713929789963587608547554858491264614271309608925634272282292964002897650355047792764365447
9144597920381774885442906257311149465702295057238600973973598305004391534618770363098565074541384771979931799878381439264848137810353858418200992191234142740194489573540381681161219332611454834544291634628456257670178843484698324641739324687497388018406214041657278323855749902661752448796122517061920880552011343608609622885787617238758769398972009949575526258430282648817039091284796330585349957724522615105102735930258969562103112238020133587096826386028128471852377225525357348919204333121695432662339443004327748973224423132988376298843862056631045488285859621661802413201793962883794915513510467912312842687601478117040419013468059983777273699192408773551806581458197324620065210523913467414181480875280203580147077789063808832356486197271376615883221558265591069223727607585313240243619515521180600435114131162272519949101464089935441251751426683447701142156416866113627126765919641034042927519834229168536331952275698122511502745177547569813354280565828372968703810158857859460406828090199683324760956105682902577189283246483314689365570862217407333103243336691401424548702387876409228977278498691200028282744239512091373110111792177228979867318546462714521296256938374618636206565791541769138267080789842400796973226733816939794717596194090232425688504890234304977612220790858557639246367437740975495450011676714198668471438814299689325208882261918460708833888406187912527346628912894921059735420931656953236560178909180587372589456926690219114173193202048332172538564489660440225377822914097420807957784201785024166011709377791129
'''
这题的预期解应该是用rabin算法，一种针对指数为2的有限域开根算法。分析题目，flag在m中，但是flag的前面添加了500个字节填充，这使得
，且本题中t=e，可以在不同的环中对c开e次方，然后把得到的结果进行CRT组合，也就是说
代码实现
from Crypto.Util.number import *
import gmpy2
import os
from functools import reduce
p = 145332367700944303747548912160113939198078051436029477960348968315913956664143693347226702600438608693933768134575289286283267810723137895903153829001826223446477799895493265422562348917012216790077395795861238257357035152687833639085415763850743538206986781418939737511715957738982536382066693822159860701263
q = 116660458253067608044065523310547233337730583902133756095473339390057738510707447906971188577217274861047379404014140178165569604404468897712846876108444468370709141219302291601408652742006268186059762087155933131837323952675627966299810891805398890428420575425160696531236660480933905879208166090591482794763
r = 157931722402853245421436270609912823260313730941283152856444641969403238646482562190531038393124087232554754746464603598717356255570166081501573727336977292059427220330169044611674973569766966838498453232642731737958791706086957762244686953294662693939604300864961637325536379321027705854708492453330690705531
s = 100973451687449518854742673778783266158999451072058606348222018797891147675959983616210003484476577612134482311993701677242007759556951494382833070563369964294544839433671087037596159753825249018950693369209927951667775267086896180395776150188902057785214767230658487267587289809918132337927575673868568976679
t = 93960345071948255233882121683650797512129333868351496468898834736770441398743300745703393838320587998953678254272245400344928586394089488734271897540051673996675973642347859306921527430850673334243441180183460927865980713929789963587608547554858491264614271309608925634272282292964002897650355047792764365447
c = 9144597920381774885442906257311149465702295057238600973973598305004391534618770363098565074541384771979931799878381439264848137810353858418200992191234142740194489573540381681161219332611454834544291634628456257670178843484698324641739324687497388018406214041657278323855749902661752448796122517061920880552011343608609622885787617238758769398972009949575526258430282648817039091284796330585349957724522615105102735930258969562103112238020133587096826386028128471852377225525357348919204333121695432662339443004327748973224423132988376298843862056631045488285859621661802413201793962883794915513510467912312842687601478117040419013468059983777273699192408773551806581458197324620065210523913467414181480875280203580147077789063808832356486197271376615883221558265591069223727607585313240243619515521180600435114131162272519949101464089935441251751426683447701142156416866113627126765919641034042927519834229168536331952275698122511502745177547569813354280565828372968703810158857859460406828090199683324760956105682902577189283246483314689365570862217407333103243336691401424548702387876409228977278498691200028282744239512091373110111792177228979867318546462714521296256938374618636206565791541769138267080789842400796973226733816939794717596194090232425688504890234304977612220790858557639246367437740975495450011676714198668471438814299689325208882261918460708833888406187912527346628912894921059735420931656953236560178909180587372589456926690219114173193202048332172538564489660440225377822914097420807957784201785024166011709377791129
n = p * q * r * s * t
e = 2
# print(n)
phi = (p - 1) * (q - 1) * (r - 1) * (s - 1) * (t - 1)
R.<x> = Zmod(p)[]
f = x ^ e - c
f = f.monic()
res1 = f.roots()
R.<x> = Zmod(q)[]
f = x ^e - c
f = f.monic()
res2 = f.roots()
R.<x> = Zmod(r)[]
f = x ^e - c
f = f.monic()
res3 = f.roots()
R.<x> = Zmod(s)[]
f = x ^e - c
f = f.monic()
res4 = f.roots()
R.<x> = Zmod(t)[]
f = x ^e - c
f = f.monic()
res5 = f.roots()
print(res1,res2,res3,res4,res5,sep='\n')
之后再进行CRT组合，其中满足题意的即为答案
#一个手写的CRT板子，sage中的CRT_list函数会快些
def union(x1, x2):
a1, m1 = x1
a2, m2 = x2
d = gmpy2.gcd(m1, m2)
assert (a2 - a1) % d == 0
p1,p2 = m1 // d,m2 // d
_,l1,l2 = gmpy2.gcdext(p1,p2)
k = -((a1 - a2) // d) * l1
lcm = gmpy2.lcm(m1,m2)
ans = (a1 + k * m1) % lcm
return ans,lcm
def excrt(ai,mi):
tmp = zip(ai,mi)
return reduce(union, tmp)
for i in res1:
for j in res2:
for k in res3:
for l in res4:
for m in res5:
ai = [i[0],j[0],k[0],l[0],m[0]]
# print(ai)
mi = [p,q,r,s,t]
flag = excrt(ai,mi)
flag = long_to_bytes(flag[0])
if b'ctfshow' in flag:
print(flag)
③AMM算法(Adleman-Manders-Miller cubic root extraction method)
如果谈论有限域开根问题，AMM算法是绕不过的。AMM算法在RSA中适用于指数e整除phi的情况，也就是说phi % e == 0。其中有详细的论文，AMM算法具体的作用就是在有限域中开出一个根。具体实现论文也明确地给出了
截图部分仅是AMM算法的实现过程，代码实现如下
def AMM(o, r, q):
start = time.time()
print('\n----------------------------------------------------------------------------------')
print('Start to run Adleman-Manders-Miller Root Extraction Method')
print('Try to find one {:#x}th root of {} modulo {}'.format(r, o, q))
g = GF(q)
o = g(o)
p = g(random.randint(1, q))
while p ^ ((q-1) // r) == 1:
p = g(random.randint(1, q))
print('[+] Find p:{}'.format(p))
t = 0
s = q - 1
while s % r == 0:
t += 1
s = s // r
print('[+] Find s:{}, t:{}'.format(s, t))
k = 1
while (k * s + 1) % r != 0:
k += 1
alp = (k * s + 1) // r
print('[+] Find alp:{}'.format(alp))
a = p ^ (r**(t-1) * s)
b = o ^ (r*alp - 1)
c = p ^ s
h = 1
for i in range(1, t):
d = b ^ (r^(t-1-i))
if d == 1:
j = 0
else:
print('[+] Calculating DLP...')
j = - discrete_log(d, a)
print('[+] Finish DLP...')
b = b * (c^r)^j
h = h * c^j
c = c^r
result = o^alp * h
end = time.time()
print("Finished in {} seconds.".format(end - start))
print('Find one solution: {}'.format(result))
return result
其中AMM(o,r,q)的返回值满足
就是在有限域q中对o开r次根。还有一个比较方便的函数，但是没有具体研究过，作用也是在有限域内得到一个根。得到一个x满足
from sympy.ntheory.residue_ntheory import nthroot_mod
nthroot_mod(a,n,p)
先引入一个例题(2022hws crypto_Elgamal)
from Crypto.Util.number import *
from key import FLAG
def keygen(size):
q = getPrime(80)
k = getPrime(944)
while True:
p = q * k + 1
if isPrime(p):
break
k += 1
g = 2
while True:
if pow(g, q, p) == 1:
break
g += 1
A = getRandomInteger(size) % q
B = getRandomInteger(size) % q
x = getRandomInteger(size) % q
h = pow(g, x, p)
return (g, h, A, B, p, q), (x)
def rand(A, B, q):
global rand_state
rand_state, ret = (A * rand_state + B) % q, rand_state
return ret
def encrypt(pubkey, m):
g, h, A, B, p, q = pubkey
assert 0 < m <= p
r = rand(A, B, q)
c1 = pow(g, r, p)
c2 = (m * pow(h, r, p)) % p
return (c1, c2)
rand_state = getPrime(1024)
pubkey, privkey = keygen(1024)
m = bytes_to_long(FLAG)
c1, c2 = encrypt(pubkey, m)
c1_, c2_ = encrypt(pubkey, m)
print(c1, c2)
print(c1_, c2_)
s0 = 543263588863771657634119
s1 = 628899245716105951093835
s2 = 78708024695487418261582
s3 = 598971435111109998816796
s4 = 789474285039501272453373
assert ( A * s0 + B ) % q == s1
assert ( A * s1 + B ) % q == s2
assert ( A * s2 + B ) % q == s3
assert ( A * s3 + B ) % q == s4
p = 65211247300401312530078141569304950676358489059623557848188896752173856845051471066071652073612337629832155846984721797768267868868902023383604553319793550396610085424563231688918357710337401138108050205457200940158475922063279384491022916790549837379548978141370347556053597178221402425212594060342213485311
g = 27642593390439430783453736408814717946185190497201679721975757020767271070510268596627490205095779429964809833535285315202625851326460572368018875381603399143376574281200028337681552876140857556460885848491160812604549770668188783258592940823128376128198726254875984002214053523752696104568469730021811399216
h = 54585833166051670245656045196940486576634589000609010947618047461787934106392112227019662788387352615714332234871251868259282522817042504587428441746855906297390193418159792477477443129333707197013251839952389651332058368911829464978546505729530760951698134101053626585254469108630886768357270544236516534904
c1 = 60724920570148295800083597588524297283595971970237964464679084640302395172192639331196385150232229004030419122038089044697951208850497923486467859070476427472465291810423905736825272208842988090394035980454248119048131354993356125895595138979611664707727518852984351599604226889848831071126576874892808080133
c2 = 48616294792900599931167965577794374684760165574922600262773518630884983374432147726140430372696876107933565006549344582099592376234783044818320678499613925823621554608542446585829308488452057340023780821973913517239972817669309837103043456714481646128392677624092659929248296869048674230341175765084122344264
c1_ = 42875731538109170678735196002365281622531058597803022779529275736483962610547258618168523955709341579773947887175626960699426438456382655370090748369934296474999389316334717699127421889816721511602392591677377678759026657582648354688447456509292302633971842316239774410380221303269351351929586256938787054867
c2_ = 64829024929257668640929285124747107162970460545535885047576569803424908055130477684809317765011143527867645692710091307694839524199204611328374569742391489915929451079830143261799375621377093290249652912850024319433129432676683899459510155157108727860920017105870104383111111395351496171846620163716404148070
分析代码就是一个lcg算法+Elgamal，这两个部分都不难做，得到数论关系之后最后有一个有限域开根问题。当时本人比赛的时候非预期出的，想着前面都分析推理出那么多东西了，最后求不出e是怀疑自己之前的abq求错了，后面还真给我用lcg的板子跑出了另一组abq，完美地非预期绕过了最后的有限域开根的问题。
后面自己再回过头思考最后这个有限域开根问题，部分关键代码如下
e = 12742153496769814072596
p = 65211247300401312530078141569304950676358489059623557848188896752173856845051471066071652073612337629832155846984721797768267868868902023383604553319793550396610085424563231688918357710337401138108050205457200940158475922063279384491022916790549837379548978141370347556053597178221402425212594060342213485311
c = 45326527081735095684632585216508484943819720696878842043540554720229674414296707918873385105075387912310299691748216658256439485784388880803922134863731374059731970174794936075890019917038396488161530769759774808480182049272235808430693365496648819656078275683885130420969875204155207145247880895891885126527
phi = p - 1
assert pow(m,e,p) == c
私钥d无法通过直接求逆元求出，且公约数t=7438，但这题有一个特殊点的地方为，当得到之后，得到的e'仍然不满足于phi互素，还有一个公约数2，所以这题要先对c进行有限域内开二次方根，开完二次方根之后再将
看作一个整体进行有限域内开根，即
设
将
看成一个整体进行RSA解密之后，得到
问题转化成c''在有限域p内开7438次根，但是AMM算法只能找到其中一个根，如何通过一个根找到其他的根，本篇文章给出了解法。用法大致如下，根据公式
其中m0是求出来的一个根
def findAllPRoot(p, e):
print("Start to find all the Primitive {:#x}th root of 1 modulo {}.".format(e, p))
start = time.time()
proot = set()
while len(proot) < e:
proot.add(pow(random.randint(2, p-1), (p-1)//e, p))
end = time.time()
print("Finished in {} seconds.".format(end - start))
return proot
上述代码的返回值就是
的合集，故最终求出本题的代码如下
_gcd = gmpy2.gcd(e,phi)
#_gcd = 7438
e //= 2
_c = AMM(c,2,p)
d = gmpy2.invert(e // _gcd,phi)
_c = pow(_c,d,p)
# _m = AMM(_c,7438,p)
e = 7438
mps = findAllPRoot(p, e)
for r in mps:
m = _m * r % p
flag = long_to_bytes(m)
if b'flag' in flag:
print(flag)
break
再引一个例题，2022SUSCTF large case
from Crypto.Util.number import *
from secret import e,message
def pad(s):
if len(s)<3*L:
s+=bytes(3*L-len(s))
return s
L=128
p = 127846753573603084140032502367311687577517286192893830888210505400863747960458410091624928485398237221748639465569360357083610343901195273740653100259873512668015324620239720302434418836556626441491996755736644886234427063508445212117628827393696641594389475794455769831224080974098671804484986257952189021223
q = 145855456487495382044171198958191111759614682359121667762539436558951453420409098978730659224765186993202647878416602503196995715156477020462357271957894750950465766809623184979464111968346235929375202282811814079958258215558862385475337911665725569669510022344713444067774094112542265293776098223712339100693
r = 165967627827619421909025667485886197280531070386062799707570138462960892786375448755168117226002965841166040777799690060003514218907279202146293715568618421507166624010447447835500614000601643150187327886055136468260391127675012777934049855029499330117864969171026445847229725440665179150874362143944727374907
n = p * q * r
assert isPrime(GCD(e,p-1)) and isPrime(GCD(e,q-1)) and isPrime(GCD(e,r-1)) and e==GCD(e,p-1)*GCD(e,q-1)*GCD(e,r-1)
assert len(message)>L and len(message)<2*L
assert b'SUSCTF' in message
m=bytes_to_long(pad(message))
c=pow(m,e,n)
print(c)
'''
2832775557487418816663494645849097066925967799754895979829784499040437385450603537732862576495758207240632734290947928291961063611897822688909447511260639429367768479378599532712621774918733304857247099714044615691877995534173849302353620399896455615474093581673774297730056975663792651743809514320379189748228186812362112753688073161375690508818356712739795492736743994105438575736577194329751372142329306630950863097761601196849158280502041616545429586870751042908365507050717385205371671658706357669408813112610215766159761927196639404951251535622349916877296956767883165696947955379829079278948514755758174884809479690995427980775293393456403529481055942899970158049070109142310832516606657100119207595631431023336544432679282722485978175459551109374822024850128128796213791820270973849303929674648894135672365776376696816104314090776423931007123128977218361110636927878232444348690591774581974226318856099862175526133892
'''
仔细分析代码，发现e是p-1,q-1,r-1的一个因子积。所以思路很容易想到是用yafu或者是factordb先把他们给分解了，得到了
_p = [7,757,1709,85015583,339028665499,149105250954771885483776047,1642463892686572578602085475101104723805585678675707586553009837707279291648160744722745420570786735582631019452016654157586623543454908938807521637550223579103317696104438456966780396624343550451096013730928292041667133825444056448136643704677066463120079]
_q = [66553,81768440203,84405986771,38037107558208320033,16137718604846030589135490851713,14369576056311038198362075935199486201201115381094289671031774994452214307042971166730146897009438957078052300683916910041250723573953110349566216311685009675744215421971185909678546052934704709232060199286321405045769976194110037]
_r = [5156273,10012111,11607389,68872137169799749,9691125310820433463,193,503,8626099,23475306212762953,105542779117757989082125573006184239099114297326009052949090033290335389936473768853350493434701637229350628852969771464325532199330764558757048653132496329427393914440142892591943594757483633317785007973120414022644727591]
这里将过小的因子剔除了，因子不会太大，所以测出来
。再分析题目，要求的明文m是被pad过，所以后1/3部分全是0，可以根据数论变换给删去，得到
c = c * gmpy2.invert(pow(256,128 * e,n),n) % n
因为删去了1/3，这里分别在p和q下开根，再CRT组合就好了。完整代码：
from Crypto.Util.number import *
import gmpy2
import time
import random
from tqdm import tqdm
p = 127846753573603084140032502367311687577517286192893830888210505400863747960458410091624928485398237221748639465569360357083610343901195273740653100259873512668015324620239720302434418836556626441491996755736644886234427063508445212117628827393696641594389475794455769831224080974098671804484986257952189021223
q = 145855456487495382044171198958191111759614682359121667762539436558951453420409098978730659224765186993202647878416602503196995715156477020462357271957894750950465766809623184979464111968346235929375202282811814079958258215558862385475337911665725569669510022344713444067774094112542265293776098223712339100693
r = 165967627827619421909025667485886197280531070386062799707570138462960892786375448755168117226002965841166040777799690060003514218907279202146293715568618421507166624010447447835500614000601643150187327886055136468260391127675012777934049855029499330117864969171026445847229725440665179150874362143944727374907
n = p * q * r
c = 2832775557487418816663494645849097066925967799754895979829784499040437385450603537732862576495758207240632734290947928291961063611897822688909447511260639429367768479378599532712621774918733304857247099714044615691877995534173849302353620399896455615474093581673774297730056975663792651743809514320379189748228186812362112753688073161375690508818356712739795492736743994105438575736577194329751372142329306630950863097761601196849158280502041616545429586870751042908365507050717385205371671658706357669408813112610215766159761927196639404951251535622349916877296956767883165696947955379829079278948514755758174884809479690995427980775293393456403529481055942899970158049070109142310832516606657100119207595631431023336544432679282722485978175459551109374822024850128128796213791820270973849303929674648894135672365776376696816104314090776423931007123128977218361110636927878232444348690591774581974226318856099862175526133892
e = 757 * 66553 * 5156273
# c = c * gmpy2.invert(pow(256,128 * e,n),n) % n
c = 280255407228236757409815887816839305916013793019016233556655881177084422973195335022587512823438603244476043620827618294521590422727109511126415701233621433629240428867472167324658030697632936334280396757560948574122348115659399270054958107088934452614887088952896264179020173433953077103667481291070508539455758662089418673467059205006535938089060238423612896891987917999584958061136036905447992065531255981463313994015042735163816799075348821119889190340460982992279626227831798343223551589026122303723190113833517871336399306996954589023298254133748866058614684423538364147817066529477497132575245720700870565926266788795913995176704128093239281548107568333922105485755437756178962461996506944599470241130124718452661102076116228019710853593988020056387355430180299354138576803527595019867293888047502553256446787799726850487133374683211529254614387387388363258745961934823313987871646019723020739519484511573598334592780
def AMM(o, r, q):
start = time.time()
print('\n----------------------------------------------------------------------------------')
print('Start to run Adleman-Manders-Miller Root Extraction Method')
print('Try to find one {:#x}th root of {} modulo {}'.format(r, o, q))
g = GF(q)
o = g(o)
p = g(random.randint(1, q))
while p ^ ((q-1) // r) == 1:
p = g(random.randint(1, q))
print('[+] Find p:{}'.format(p))
t = 0
s = q - 1
while s % r == 0:
t += 1
s = s // r
print('[+] Find s:{}, t:{}'.format(s, t))
k = 1
while (k * s + 1) % r != 0:
k += 1
alp = (k * s + 1) // r
print('[+] Find alp:{}'.format(alp))
a = p ^ (r**(t-1) * s)
b = o ^ (r*alp - 1)
c = p ^ s
h = 1
for i in range(1, t):
d = b ^ (r^(t-1-i))
if d == 1:
j = 0
else:
print('[+] Calculating DLP...')
j = - discrete_log(d, a)
print('[+] Finish DLP...')
b = b * (c^r)^j
h = h * c^j
c = c^r
result = o^alp * h
end = time.time()
print("Finished in {} seconds.".format(end - start))
print('Find one solution: {}'.format(result))
return result
def onemod(p,r):
t=p-2
while pow(t,(p-1) // r,p)==1:
t -= 1
return pow(t,(p-1) // r,p)
def solution(p,root,e):
g = onemod(p,e)
may = set()
for i in range(e):
may.add(root * pow(g,i,p)%p)
return may
ep = 757
eq = 66553
er = 5156273
cp = pow(c,gmpy2.invert(eq*er,p-1),p)
cq = pow(c,gmpy2.invert(ep*er,q-1),q)
mp = AMM(cp,ep,p)
mq = AMM(cq,eq,q)
mps = solution(p,mp,ep)
mqs = solution(q,mq,eq)
for mpp in tqdm(mps):
for mqq in mqs:
ai = [int(mpp),int(mqq)]
mi = [p,q]
m = CRT_list(ai,mi)
flag = long_to_bytes(m)
if b'SUSCTF' in flag:
print(flag)
exit(0)
板子从V神blog里嫖的其中函数onemod()和solution()组合求出剩下的根并进行组合，solution函数得到的就是在当前质数环下满足条件的所有根。
def onemod(p,r):
t=p-2
while pow(t,(p-1) // r,p)==1:
t -= 1
return pow(t,(p-1) // r,p)
def solution(p,root,e):#(质数环，AMM求出的一个根，需要开e次根)
g = onemod(p,e)
may = set()
for i in range(e):
may.add(root * pow(g,i,p)%p)
return may
最终可以求解得到flag
所以回到开头提到的NCTF2019的AMM问题，也大同小异，这里就不解释直接贴exp了。
from Crypto.Util.number import *
import gmpy2
import time
import random
from tqdm import tqdm
e = 0x1337
p = 199138677823743837339927520157607820029746574557746549094921488292877226509198315016018919385259781238148402833316033634968163276198999279327827901879426429664674358844084491830543271625147280950273934405879341438429171453002453838897458102128836690385604150324972907981960626767679153125735677417397078196059
q = 112213695905472142415221444515326532320352429478341683352811183503269676555434601229013679319423878238944956830244386653674413411658696751173844443394608246716053086226910581400528167848306119179879115809778793093611381764939789057524575349501163689452810148280625226541609383166347879832134495444706697124741
n = p * q
c = 10562302690541901187975815594605242014385201583329309191736952454310803387032252007244962585846519762051885640856082157060593829013572592812958261432327975138581784360302599265408134332094134880789013207382277849503344042487389850373487656200657856862096900860792273206447552132458430989534820256156021128891296387414689693952047302604774923411425863612316726417214819110981605912408620996068520823370069362751149060142640529571400977787330956486849449005402750224992048562898004309319577192693315658275912449198365737965570035264841782399978307388920681068646219895287752359564029778568376881425070363592696751183359
def AMM(o, r, q):
start = time.time()
print('\n----------------------------------------------------------------------------------')
print('Start to run Adleman-Manders-Miller Root Extraction Method')
print('Try to find one {:#x}th root of {} modulo {}'.format(r, o, q))
g = GF(q)
o = g(o)
p = g(random.randint(1, q))
while p ^ ((q-1) // r) == 1:
p = g(random.randint(1, q))
print('[+] Find p:{}'.format(p))
t = 0
s = q - 1
while s % r == 0:
t += 1
s = s // r
print('[+] Find s:{}, t:{}'.format(s, t))
k = 1
while (k * s + 1) % r != 0:
k += 1
alp = (k * s + 1) // r
print('[+] Find alp:{}'.format(alp))
a = p ^ (r**(t-1) * s)
b = o ^ (r*alp - 1)
c = p ^ s
h = 1
for i in range(1, t):
d = b ^ (r^(t-1-i))
if d == 1:
j = 0
else:
print('[+] Calculating DLP...')
j = - discrete_log(d, a)
print('[+] Finish DLP...')
b = b * (c^r)^j
h = h * c^j
c = c^r
result = o^alp * h
end = time.time()
print("Finished in {} seconds.".format(end - start))
print('Find one solution: {}'.format(result))
return result
def onemod(p,r):
t=p-2
while pow(t,(p-1) // r,p)==1:
t -= 1
return pow(t,(p-1) // r,p)
def solution(p,root,e):
g = onemod(p,e)
may = set()
for i in range(e):
may.add(root * pow(g,i,p)%p)
return may
def union(x1, x2):
a1, m1 = x1
a2, m2 = x2
d = gmpy2.gcd(m1, m2)
assert (a2 - a1) % d == 0
p1,p2 = m1 // d,m2 // d
_,l1,l2 = gmpy2.gcdext(p1,p2)
k = -((a1 - a2) // d) * l1
lcm = gmpy2.lcm(m1,m2)
ans = (a1 + k * m1) % lcm
return ans,lcm
def excrt(ai,mi):
tmp = zip(ai,mi)
return reduce(union, tmp)
cp = c % p
cq = c % q
mp = AMM(cp,e,p)
mq = AMM(cq,e,q)
mps = solution(p,mp,e)
mqs = solution(q,mq,e)
for mpp in tqdm(mps):
for mqq in mqs:
ai = [int(mpp),int(mqq)]
mi = [p,q]
m = CRT_list(ai,mi)
flag = long_to_bytes(m)
if b'NCTF' in flag:
print(flag)
exit(0)
0x01 总结
遇到e与phi不互素的问题，首先就考虑问题的复杂程度，从e的大小和e与phi的公约数大小入手。总结出了三个板子针对不同的情况。不过遇到实际的问题还需具体情况具体分析。
①e较小
from Crypto.Util.number import *
import gmpy2
c =
e =
n =
p =
q =
phi = (p - 1) * (q - 1)
t = gmpy2.gcd(e,phi)
print(t)
_e = e // t
d = gmpy2.invert(_e,phi)
_m = pow(c,d,n)
m = gmpy2.iroot(_m,t)[0]
print(long_to_bytes(m))
②e不算大但需结合CRT求解
from Crypto.Util.number import *
import gmpy2
p =
q =
c =
n =
e =
phi = (p - 1) * (q - 1)
R.<x> = Zmod(p)[]
f = x ^ e - c
f = f.monic()
res1 = f.roots()
R.<x> = Zmod(q)[]
f = x ^e - c
f = f.monic()
res2 = f.roots()
for i in res1:
for j in res2:
ai = [i[0],j[0]]
mi = [p,q]
flag = CRT_list(ai,mi)
flag = long_to_bytes(flag)
if b'flag' in flag:
print(flag)
③e很大，且e与phi的公约数就是e，AMM算法
from Crypto.Util.number import *
import gmpy2
import time
import random
from tqdm import tqdm
e =
p =
q =
n = p * q
c =
def AMM(o, r, q):
start = time.time()
print('\n----------------------------------------------------------------------------------')
print('Start to run Adleman-Manders-Miller Root Extraction Method')
print('Try to find one {:#x}th root of {} modulo {}'.format(r, o, q))
g = GF(q)
o = g(o)
p = g(random.randint(1, q))
while p ^ ((q-1) // r) == 1:
p = g(random.randint(1, q))
print('[+] Find p:{}'.format(p))
t = 0
s = q - 1
while s % r == 0:
t += 1
s = s // r
print('[+] Find s:{}, t:{}'.format(s, t))
k = 1
while (k * s + 1) % r != 0:
k += 1
alp = (k * s + 1) // r
print('[+] Find alp:{}'.format(alp))
a = p ^ (r**(t-1) * s)
b = o ^ (r*alp - 1)
c = p ^ s
h = 1
for i in range(1, t):
d = b ^ (r^(t-1-i))
if d == 1:
j = 0
else:
print('[+] Calculating DLP...')
j = - discrete_log(d, a)
print('[+] Finish DLP...')
b = b * (c^r)^j
h = h * c^j
c = c^r
result = o^alp * h
end = time.time()
print("Finished in {} seconds.".format(end - start))
print('Find one solution: {}'.format(result))
return result
def onemod(p,r):
t=p-2
while pow(t,(p-1) // r,p)==1:
t -= 1
return pow(t,(p-1) // r,p)
def solution(p,root,e):
g = onemod(p,e)
may = set()
for i in range(e):
may.add(root * pow(g,i,p)%p)
return may
cp = c % p
cq = c % q
mp = AMM(cp,e,p)
mq = AMM(cq,e,q)
mps = solution(p,mp,e)
mqs = solution(q,mq,e)
for mpp in tqdm(mps):
for mqq in mqs:
ai = [int(mpp),int(mqq)]
mi = [p,q]
m = CRT_list(ai,mi)
flag = long_to_bytes(m)
if b'NCTF' in flag:
print(flag)
exit(0)
板子不是万能的，实际问题还需实际分析，希望我的分享对你有帮助
