Crypto刷题记录（一）

Crypto Crypto题目记录
Created At :
Count:2k Views 👀 :
  1. [羊城杯 2020]Power
  2. crtrsa
  3. [GKCTF 2021]RRRRsa
  4. 东华杯fermat’s revenge

记录Crypto题中一些值得注意的地方

题目：

import gmpy2
import libnum
import random
import uuid
flag="unctf{"+str(uuid.uuid4())+"}"
m=libnum.s2n(flag)

p=libnum.generate_prime(1024)
q=libnum.generate_prime(1024)
n=p*q
e=65537
c=pow(m*p+n,e,n)
print("n=",n)
print("c=",c)
print("e=",e)
#n= 27023180567533176673625876001733765250439008888496677405372613659387969480500400831799338479404533734632060401129194207025095826786316107611502577395964365591899893794206238112244571942694129959717225168573059987542436467778426312967832431595178558711258027999897974942046398583397445299861338203860420721585460676138091828032223153425728023656897880166788811969523526091221520293020106530587453637600349533427641518473788620430866128331962450325767202417824455886116760280239705754222948387172102353564657340216229891342124971948458724351338597649821310431397426705701275774039588035776573373417654649168810548916141
#c= 3489599657527403893851973553294684608504140532554562294027722218597464669848608337663997115805201027340092733823019661706872544231209523772845492398492677185660213963118144668038183924970370481476141221609706208064428560732214361469135212057355342825193598971775551833240699393482839422273480793244841531126642199202744610656153155545415859410361595564197685655133074582118230993519133935533313364233668337427608419528430102794052261190930670933657287272452581248934890029409559234507626012423255430699687038808658327174609660874748540185589263800447650242593224189976058739054174360024536594384447518687126891675059
#e= 65537

n很大，想分解是不可能的，$c=(m \cdot p+n)^emodn$

$m \cdot p$与n存在公因数p，进一步可以知道，c有p的因子，这样一来通过gcd(c,n)就能求出p来，然后就能解了。注意最后求得的m还得整除上p。代码如下：

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

n= 27023180567533176673625876001733765250439008888496677405372613659387969480500400831799338479404533734632060401129194207025095826786316107611502577395964365591899893794206238112244571942694129959717225168573059987542436467778426312967832431595178558711258027999897974942046398583397445299861338203860420721585460676138091828032223153425728023656897880166788811969523526091221520293020106530587453637600349533427641518473788620430866128331962450325767202417824455886116760280239705754222948387172102353564657340216229891342124971948458724351338597649821310431397426705701275774039588035776573373417654649168810548916141
c= 3489599657527403893851973553294684608504140532554562294027722218597464669848608337663997115805201027340092733823019661706872544231209523772845492398492677185660213963118144668038183924970370481476141221609706208064428560732214361469135212057355342825193598971775551833240699393482839422273480793244841531126642199202744610656153155545415859410361595564197685655133074582118230993519133935533313364233668337427608419528430102794052261190930670933657287272452581248934890029409559234507626012423255430699687038808658327174609660874748540185589263800447650242593224189976058739054174360024536594384447518687126891675059
e= 65537

p = gcd(n,c)
q = n // p
d = invert(e,(p-1)*(q-1))
m = pow(c,d,n)
print(long_to_bytes(m//p))

来自buu的

[羊城杯 2020]Power

题目：

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

p = getPrime(512)
q = getPrime(512)
n = p**4*q

e = 0x10001
phi = gmpy2.lcm(p - 1, q - 1)
d = gmpy2.invert(e, phi)
dp = d % (p - 1)
m = bytes_to_long(flag)
c = pow(m, e, n)
print "dp = " + str(dp)
print "c = " + str(c)

y = 449703347709287328982446812318870158230369688625894307953604074502413258045265502496365998383562119915565080518077360839705004058211784369656486678307007348691991136610142919372779782779111507129101110674559235388392082113417306002050124215904803026894400155194275424834577942500150410440057660679460918645357376095613079720172148302097893734034788458122333816759162605888879531594217661921547293164281934920669935417080156833072528358511807757748554348615957977663784762124746554638152693469580761002437793837094101338408017407251986116589240523625340964025531357446706263871843489143068620501020284421781243879675292060268876353250854369189182926055204229002568224846436918153245720514450234433170717311083868591477186061896282790880850797471658321324127334704438430354844770131980049668516350774939625369909869906362174015628078258039638111064842324979997867746404806457329528690722757322373158670827203350590809390932986616805533168714686834174965211242863201076482127152571774960580915318022303418111346406295217571564155573765371519749325922145875128395909112254242027512400564855444101325427710643212690768272048881411988830011985059218048684311349415764441760364762942692722834850287985399559042457470942580456516395188637916303814055777357738894264037988945951468416861647204658893837753361851667573185920779272635885127149348845064478121843462789367112698673780005436144393573832498203659056909233757206537514290993810628872250841862059672570704733990716282248839
g = 2
x = 2019*p**2 + 2020*p**3 + 2021*p**4
c1 = pow(g, x, y)
print "c1 = " + str(c1)

# dp = 3272293505696712831419859641571956066667516012597886098021642320155056349966612629986261146617139998624603483170466852538289743936225789351270153550594329
# c = 22524257534087703614496632403022329621384173069680778965750290698059674588465640878754707363673789674111671270645152584118206145007310499274423606886261969807360070526126452646719628307689968971699215841867636770320159256301550908771135042912287955209485328267670825390080110910391913063177323585204392804538642393453388536211144485389902591029350060800993352969569703901717308330574394200996651534321547814313195218895547718815009876393987398738932001924661338796059973950012706427109598830049455186171345179840564502215531573714428772608739268313985559628612004439028014417408631851880698512023740903181116906766066951473942201698375224240271523568161242951730224901227589413731025281719101368668617497947995579443908773425555177346524678673641140157885033923288401884
# c1 = 290707924192892686920253390955676600323331633814839708838347288502692494699485764473635783441705302268064111648851157070038783719749721994682837294625334517914882191486257362565066745587415388291939979195637720350919055988532145531805200483161599965215275808797976727969023747299578173497083532351976473770041800769265319548352841139802163279116490053292316399038329210043455932786945180855178341998049756983301499491011851026499269682821602212971062877270127451987836730083380463825717889123804613394241190839837791281657872259492589868751745327696030438893865069941066073554427558697972551085353027574529823439588670263047287131740802375738439636789806332323994866753085014446479034974063195632514803340511247735647970572837053148490258113394359072976858781060349776921428492973183958437965966963122069107876143476772436757554253049619918403996315720023020827394900507088006299225934263699192253079026440287311664705744424959801981503191480257138833694306501816837037995549817186335377411638035575004595417788588264823861850877111374085336446477943372458378834664678094751978400910288151519902977326995118727880223621964441498323865158898463327323193833062919619201107279964663654606753750042791368210261574897455830722232022689695292080269205470491791950839486861811469879413313773338916781857981641910031441448964144000585506870170898052132929034349451945051362244755750988705018897859238859476967568556992146975789444151432386692872801263000639711599152191790766776280

出现了dp，所以这道题应该是与dp泄露相关。代码整体观察下来，或许要从解p入手了，刚好下半段与p有关。

有个关于x与p的方程，如果知道了x，那就可以在Sage里解出方程的解，即p来。看到 $c_1 = pow(g, x, y)$，转换一下：$g^x \equiv c1 \space mod \space y$，在这里可以用到离散对数的知识解出x来：

x = sympy.discrete_log(y,c1,g)#离散对数问题，g^x = c1 mod y，求x

接着解p：

#Sage
y = 449703347709287328982446812318870158230369688625894307953604074502413258045265502496365998383562119915565080518077360839705004058211784369656486678307007348691991136610142919372779782779111507129101110674559235388392082113417306002050124215904803026894400155194275424834577942500150410440057660679460918645357376095613079720172148302097893734034788458122333816759162605888879531594217661921547293164281934920669935417080156833072528358511807757748554348615957977663784762124746554638152693469580761002437793837094101338408017407251986116589240523625340964025531357446706263871843489143068620501020284421781243879675292060268876353250854369189182926055204229002568224846436918153245720514450234433170717311083868591477186061896282790880850797471658321324127334704438430354844770131980049668516350774939625369909869906362174015628078258039638111064842324979997867746404806457329528690722757322373158670827203350590809390932986616805533168714686834174965211242863201076482127152571774960580915318022303418111346406295217571564155573765371519749325922145875128395909112254242027512400564855444101325427710643212690768272048881411988830011985059218048684311349415764441760364762942692722834850287985399559042457470942580456516395188637916303814055777357738894264037988945951468416861647204658893837753361851667573185920779272635885127149348845064478121843462789367112698673780005436144393573832498203659056909233757206537514290993810628872250841862059672570704733990716282248839
x = 5535722692962580764045545539105119140941061679289569420988353884209653851308860058948669740693107863231179565602072744542122031789184119031739723962825082929025825322421201364211726001366490949760887367407718763255964735567971493859197583624076478457865073449246835949075135223468616834636386958924709024763349115622062848212445867198457630368236782421195503713107838541903829979118327675371550868768159024260793541264335548489228744367609071659968450303895118817379316060805148754136917043160175570565717388336822960389664337656603584425629662613786203920234401824957121860225422901340950436355650311392398098947210940
R.<p>=Zmod(y)[]
f=2019*p**2 + 2020*p**3 + 2021*p**4-x
f.roots()

解出来两个解，其中一个很大，显然不符合要求，选择小的那个。

因为$dp \equiv d \space mod \space (p-1)$，则有$d = dp+k \cdot (p-1)$，可以爆破出d来（其实d可以猜出来，因为dp已经很大了，又dp<p，所以dp跟d应该是相等的）：

k = 0
while True:
    d = dp + k*(p-1)
    m = pow(c,d,p)
    flag = long_to_bytes(m)
    if  b'{' in flag:
        print(flag)
        print(k)
        break
    k+=1

当然更严谨的是通过推导来求：

已知$c\equiv m^e \space mod \space n和dp \equiv d \space mod \space (p-1) $

在两侧同乘e，$e\ cdot dp \equiv e \cdot d \space mod \space(p-1)$

又$e \cdot d = 1 + k \cdot (p-1) \cdot (q-1)$

故$e \cdot dp \equiv e \cdot d \space mod \space (p-1) \equiv 1 \space mod \space (p-1) = 1+k \cdot (p-1)$

在c公式两侧加上dp次方，$c^{dp} \equiv m^{e \cdot dp} \space mod \space n$，把n拆开，得到：

$c^{dp} \space mod \space p \equiv m^{e \cdot dp} \space mod \space p$

把上面求得的$e \cdot dp$代入得到:

$c^{dp} \space mod \space p \equiv m^{1+k \cdot (p-1)} \space mod \space p$

运用费马小定理：$m^{p-1} \equiv 1 \space mod \space p$

$c^{dp} \space mod \space p\equiv m \space mod \space p$

其实也证明了$dp=d$

故$flag = pow(c,dp,p)$

整体代码如下：

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

e = 0x10001
dp = ...
c = ...
c1 = ...

y = ...
g = 2
#x = 2019*p**2 + 2020*p**3 + 2021*p**4
#x = sympy.discrete_log(y,c1,g)#离散对数问题，a^x = b mod m，求x
#求解会比较慢
#print(x)
#x = 5535722692962580764045545539105119140941061679289569420988353884209653851308860058948669740693107863231179565602072744542122031789184119031739723962825082929025825322421201364211726001366490949760887367407718763255964735567971493859197583624076478457865073449246835949075135223468616834636386958924709024763349115622062848212445867198457630368236782421195503713107838541903829979118327675371550868768159024260793541264335548489228744367609071659968450303895118817379316060805148754136917043160175570565717388336822960389664337656603584425629662613786203920234401824957121860225422901340950436355650311392398098947210940
'''
Sage
y = ...
x = ...
R.<p>=Zmod(y)[]
f=2019*p**2 + 2020*p**3 + 2021*p**4-x
f.roots()
'''
p = 7234391427703598327916723159145232922047935397302241978344500497098972068808591685717500902909442183573763273395725479516998210374727754578133587007330339
k = 0
while True:
    d = dp + k*(p-1)
    m = pow(c,d,p)
    flag = long_to_bytes(m)
    if  b'{' in flag:
        print(flag)
        print(k)
        break
    k+=1
'''
print(long_to_bytes(pow(c,dp,p)))
'''

crtrsa

from secret import flagn,p,q
#p and q are two primes generated by getPrime
import random
def key_gen():
    while True:
    dp = random.randint(1,1<<20)
    dq = random.randint(1,q-1)
    if gcd(dp, p - 1) == 1 and gcd(dq, q - 1) == 1:
        d = crt([dp,dq],[p-1,q-1])
        phi = (p-1)*(q-1)
        R = Integers(phi)
        e = R(d)^-1
        return p*q,e
n,e = key_gen()
print e
print n
print pow(flagn,int(e),n)
 
'''
e = 2953544268002866703872076551930953722572317122777861299293407053391808199220655289235983088986372630141821049118015752017412642148934113723174855236142887
N = 6006128121276172470274143101473619963750725942458450119252491144009018469845917986523007748831362674341219814935241703026024431390531323127620970750816983
flag = 4082777468662493175049853412968913980472986215497247773911290709560282223053863513029985115855416847643274608394467813391117463817805000754191093158289399
'''

来自2021巅峰极客。

已知：

  • $dp \equiv d \space mod \space (p-1)$
  • $ed \equiv 1 \space mod \space \phi(n) \equiv 1\space mod \space (p-1) $

将两式子左右相乘：

$e \cdot dp\equiv 1 \space mod \space (p-1)=1+k(p-1)$

再由欧拉定理，若存在gcd(a,x)=1，则有$a^{\phi(x)}\equiv 1 \space mod \space x$

取$x \in (1,p)$，且与p互素，则$x^{\phi(p)}\equiv 1 \space mod \space p$

$x^{p-1}\equiv 1 \space mod \space p $

$x^{k(p-1)+1}\equiv x \space mod \space p$（先两侧同时加上k次方，再同时乘上一个x）

$x^{e \cdot dp}\equiv x \space mod \space p=x+k \cdot p$

$x^{e \cdot dp} - x=k \cdot p$

综上有$x^{e \cdot dp}-x = k \cdot p$与$n=p \cdot q$，通过两个关系可以得到p，便可以解了。代码如下：

from gmpy2 import *
from Crypto.Util.number import *
import libnum
 
 
e = 2953544268002866703872076551930953722572317122777861299293407053391808199220655289235983088986372630141821049118015752017412642148934113723174855236142887
N = 6006128121276172470274143101473619963750725942458450119252491144009018469845917986523007748831362674341219814935241703026024431390531323127620970750816983
flag = 4082777468662493175049853412968913980472986215497247773911290709560282223053863513029985115855416847643274608394467813391117463817805000754191093158289399
 
 
x = 1000000001
t0 = pow(x,e,N)#把这部分单独拿循环外头计算，爆破能快一点
for dp in range(1,1<<20+1):
    t = pow(t0,dp,N)-x
    p = gcd(t,N)
    if p != 1:
        print(p)
        #p = 88483113499234291234797595363172914275282163218450540253170700235627922981203
        q = N // p
        try:
            d = invert(e,(p-1)*(q-1))
            m = pow(flag,d,N)
            print(long_to_bytes(m))
        except:
            pass
        break

两道题作个对比：

[GKCTF 2021]RRRRsa

from Crypto.Util.number import *
from gmpy2 import gcd
 
flag = b'xxxxxxxxxxxxx'
p = getPrime(512)
q = getPrime(512)
m = bytes_to_long(flag)
n = p*q
e = 65537
c = pow(m,e,n)
print('c={}'.format(c))
 
p1 = getPrime(512)
q1 = getPrime(512)
n1 = p1*q1
e1 = 65537
assert gcd(e1,(p1-1)*(q1-1)) == 1
c1 = pow(p,e1,n1)
print('n1={}'.format(n1))
print('c1={}'.format(c1))
hint1 = pow(2020 * p1 + q1, 202020, n1)
hint2 = pow(2021 * p1 + 212121, q1, n1)
print('hint1={}'.format(hint1))
print('hint2={}'.format(hint2))
 
p2 = getPrime(512)
q2 = getPrime(512)
n2 = p2*q2
e2 = 65537
assert gcd(e1,(p2-1)*(q2-1)) == 1
c2 = pow(q,e2,n2)
hint3 = pow(2020 * p2 + 2021 * q2, 202020, n2)
hint4 = pow(2021 * p2 + 2020 * q2, 212121, n2)
print('n2={}'.format(n2))
print('c2={}'.format(c2))
print('hint3={}'.format(hint3))
print('hint4={}'.format(hint4))
 
#c=13492392717469817866883431475453770951837476241371989714683737558395769731416522300851917887957945766132864151382877462142018129852703437240533684604508379950293643294877725773675505912622208813435625177696614781601216465807569201380151669942605208425645258372134465547452376467465833013387018542999562042758
#n1=75003557379080252219517825998990183226659117019770735080523409561757225883651040882547519748107588719498261922816865626714101556207649929655822889945870341168644508079317582220034374613066751916750036253423990673764234066999306874078424803774652754587494762629397701664706287999727238636073466137405374927829
#c1=68111901092027813007099627893896838517426971082877204047110404787823279211508183783468891474661365139933325981191524511345219830693064573462115529345012970089065201176142417462299650761299758078141504126185921304526414911455395289228444974516503526507906721378965227166653195076209418852399008741560796631569
#hint1=23552090716381769484990784116875558895715552896983313406764042416318710076256166472426553520240265023978449945974218435787929202289208329156594838420190890104226497263852461928474756025539394996288951828172126419569993301524866753797584032740426259804002564701319538183190684075289055345581960776903740881951
#hint2=52723229698530767897979433914470831153268827008372307239630387100752226850798023362444499211944996778363894528759290565718266340188582253307004810850030833752132728256929572703630431232622151200855160886614350000115704689605102500273815157636476901150408355565958834764444192860513855376978491299658773170270
#n2=114535923043375970380117920548097404729043079895540320742847840364455024050473125998926311644172960176471193602850427607899191810616953021324742137492746159921284982146320175356395325890407704697018412456350862990849606200323084717352630282539156670636025924425865741196506478163922312894384285889848355244489
#c2=67054203666901691181215262587447180910225473339143260100831118313521471029889304176235434129632237116993910316978096018724911531011857469325115308802162172965564951703583450817489247675458024801774590728726471567407812572210421642171456850352167810755440990035255967091145950569246426544351461548548423025004
#hint3=25590923416756813543880554963887576960707333607377889401033718419301278802157204881039116350321872162118977797069089653428121479486603744700519830597186045931412652681572060953439655868476311798368015878628002547540835719870081007505735499581449077950263721606955524302365518362434928190394924399683131242077
#hint4=104100726926923869566862741238876132366916970864374562947844669556403268955625670105641264367038885706425427864941392601593437305258297198111819227915453081797889565662276003122901139755153002219126366611021736066016741562232998047253335141676203376521742965365133597943669838076210444485458296240951668402513

东华杯fermat’s revenge

from Crypto.Util.number import *
f = open('flag.txt', 'rb')
m = bytes_to_long(f.read())
f.close()
e = 65537
p = getPrime(1024)
q = getPrime(1024)
n = p * q
c = pow(m, e, n)
hint = pow(1010 * p + 1011, q, n)
f = open('cipher.txt', 'w')
f.write(f'n={n}\n')
f.write(f'c={c}\n')
f.write(f'hint={hint}\n')
f.close()

两道题都是从hint入手，通过一些数学定理（二项式定理、费马小定理），以及同余、模关系的各种转换来推出一个式子与n=p*q结合，求得两式的因子p或q解。上面那题不推了，推一下下面这道题。

还是从hint入手：$hint = (1010*p+1011)^{q} \space mod \space n$

通过mod来得到kp或kq的式子，所以把n拆开，p和q都试试。指数为q，或许从mod q入手，但走不通，换成mod p试试：$hint = (1010 \cdot p+1011)^{q} \space mod \space p$，二项式定理得到：$hint = 1011^q \space mod \space p$

又有$1011^n \equiv 1011^{p \cdot q} \equiv 1011^q \space mod \space p$（费马小定理），为什么往这里想，一是题目只给了一个hint，得不出有用的信息；二是想到费马小定理运用的条件和能够的得到的结果形式，就是得到mod p，因为上面已经得到了一个含有mod p的式子。

最后用$hint = 1011^q \space mod \space p$减去$1011^n \equiv 1011^q \space mod \space p$（都把右边化成，其中两个式子的k是不同的），得到$hint-1011^n=k\cdot p$，与$n=p \cdot q$联立，求gcd便得到了p，接着就好解了。代码如下：

from gmpy2 import *
import libnum
 
e = 65537
n = ...
c = ...
hint = ...
 
kp = hint-pow(1011,n,n)
p = gcd(n,kp)
q = n // p
phi_n = (p-1)*(q-1)
d = invert(e,phi_n)
m = pow(c,d,n)
m = 13040004482819619198089467077911742863679763803984073507387072666533743137994822052186842493
print(libnum.n2s(m))

部分题是我在csdn记过的，在这里再回顾一下，并作记录。

总结：学习了用Sage进行同余运算，复习了dp泄露

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1666739907@qq.com

©2022-2023 Luino

Built with Hexo and 3-hexo theme

github