针对CTFer的e与phi不互素的问题

跳跳糖社区 2022-04-06
1520

点击 / 关注我们


为什么说是针对CTFer的呢,本篇文章可能针对实用性强一点,针对算法的原理剖析会少一些。最后会总结出板子放在文章的结尾。

前言

在平常遇到的问题中,如果能求出公钥n的欧拉函数,可以说这个RSA加解密问题已经接近成功了。要求私钥d需要求出e在phi中的逆元使得,但直接求逆元需要满足一个前提就是,也就是说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不互素,。该题的具体解法最后讨论,下面是我对e与phi不互素问题的一些小总结。

这种情况可以把看成一个新的需要求的明文,这里以一道我自己之前摸鱼出的一道题目为例,附件如下

from Crypto.Util.number import *
from secret import flag
flag = b'flag{*********}'
m = bytes_to_long(flag)
p = getPrime(1024)
q = getPrime(1024)2
n = p * q
e = 114
c = pow(m,e,n)
print(c)
print(p >> 200)
print(n)

# 4981370648841772812759645290740849305394680703208798679296466901875830602835273402860232301263281323578956193947979697234640828088984992529165349436050379602381023059635247562226192384089521639938396211636613132291696135696985578958227320544060232615333466684704244997055833821133086665356126147182204658744167431612986909752009485714137028204041440181653812250548914729617593568901044728464293232061709058144788756823288190386071071979728390993033661221130338943191220680445314588574185565138844949934691183548291792150029676489045342419826189506616272247940278820931530398810621850374268800818970515221497093852109
# 62037304914409314363888940906845820031382619388386590204815535497699521033644001814874589864676342418539729790446530529473631795496696578029445470682035483391568820927435567100377626022924900710513454770616746573110984342344183967600234091673261776
# 10315159385090642346129000730749042701431892949303034712476198921384639021767097119992198421632142955005047146294210952031882321038272269972695714084199530336742619691272883151455898061330316812891004827724782855036289498818157782936179413509824274682055131552093071749522986951202502017564120645520386407170556413591537187759567563157956331577316042296031033014710853038209000676314440817362756989634719336973373719581572614119144998829076893422175956726616346716072744575347893245428145235967836165207095908913238287634122873060994828380614739915448587956681845973466847711337763120292734433687845920176310499582951

其中第一部分是一个p泄露高位的问题,老生常谈了,这里不过多赘述。求出p之后我们发现,e与phi不互素且公约数,当时出题的flag值未设很长,故可进行尝试,数论推导如下:

   

用此公钥,即有如下关系

   

其中可求且,即直接对进行开次方根即可。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
'''


这题的预期解应该是用rabin算法,一种针对指数为2的有限域开根算法。分析题目,flag在m中,但是flag的前面添加了500个字节填充,这使得,且本题中,可以在不同的环中对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。其中有详细的论文(https://arxiv.org/pdf/1111.4877.pdf),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算法只能找到其中一个根,如何通过一个根找到其他的根,本篇文章(https://stackoverflow.com/questions/6752374/cube-root-modulo-p-how-do-i-do-this)给出了解法。用法大致如下,根据公式

其中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(http://factordb.com/)先把他们给分解了,得到了

_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(https://jayxv.github.io/2022/02/28/2022%20SUSCTF/)里嫖的其中函数onemod()和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)

总结

遇到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很大,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)


推荐阅读:
CodeQL 踩坑指南 - Java
我是如何利用环境变量注入执行任意命令
Make JDBC Attacks Brilliant Again 番外篇
Docker又爆出高危逃逸漏洞了?仔细研究下事情没那么简单
渗透测试工具 OWASP ZAP 的 RCE 反制




跳跳糖是一个安全社区,旨在为安全人员提供一个能让思维跳跃起来的交流平台。
跳跳糖持续向广大安全从业者征集高质量技术文章,可以是漏洞分析,事件分析,渗透技巧,安全工具等等。
通过审核且发布将予以500RMB-1000RMB不等的奖励,具体文章要求可以查看“投稿须知”。

阅读更多原创技术文章,戳“阅读全文
文章转载自跳跳糖社区,如果涉嫌侵权,请发送邮件至:contact@modb.pro进行举报,并提供相关证据,一经查实,墨天轮将立刻删除相关内容。

评论