首页周刊友链关于

ctfshow刷题小记-crypto

发表于 2026-02-11 13:43 2188 字 11 min read

Yolo avatar

Yolo

CTFer / misc / V&N

13 文章

8 分类

20 标签
首页 周刊
分类 标签 归档
友链 关于
ctfshow刷题小记-cryptoBUU刷题小记-crypto
记录下学习密码的过程

crypto4

p=447685307 q=2053 e=17

提交 flag{d}即可

这个入门题考察我 rsa 算法（俺不会，先去求助下 ai

RSA 相关公式

  • 计算模数 n
n=p×qn = p \times q
  • 计算欧拉函数
ϕ(n)=(p−1)(q−1)\phi(n) = (p-1)(q-1)
  • 计算私钥
e×d≡1(modϕ(n))e \times d \equiv 1 \pmod{\phi(n)}

模逆元

求解 dd 的本质是求解 ee 在模 ϕ(n)\phi(n) 下的乘法逆元，也就是说，必须满足 ed≡1(modϕ(n))ed\equiv1\pmod{\phi(n)}

这里需要扩展欧几里德算法进行求解

扩展欧几里德算法

先从普通欧几里德算法说起，也就是我们最常见的辗转相除法

问题：求解gcd(48,18)
48 ÷ 18 = 2 余 12
18 ÷ 12 = 1 余 6  
12 ÷ 6  = 2 余 0  ← 余数为0，停止！
所以gcd(48,18)=6

核心思想：gcd(a,b)=gcd(b,a mod b),一直到余数为 0

那么扩展欧几里德的创新点就在于，它不仅能求出gcd(a,b)，还能找到两个整数 x 和 y，使得ax+by=gcd(a,b)这也叫贝祖等式

举个例子

问题：求解gcd(48,18),同时找到x,y使得48x+18y=6
步骤1： 48 ÷ 18 = 2 余 12
步骤2： 18 ÷ 12 = 1 余 6  
步骤3： 12 ÷ 6  = 2 余 0  ← 余数为0，停止！
结论：gcd(48,18)=6

重点来了，开始回代，从步骤 2 开始

6 = 18 - 1 x 12
6 = 18 - 1 x (48 - 2 x 18)
整理：6 = -1 x 48 + 3 x 18
因此：48 x (-1) + 18 x 3 = 6 = gcd(48,18)

那么为啥说扩展欧几里德能求模逆元呢？

可以观察到，当 gcd(a,b)=1 时，即 a 和 b 互质，那么我们就能通过扩展欧几里德算法得到ax+by=1

两边同时mod b: ax≡1(modb)

这样就意味着 x 就是 a 在模 b 下的逆元

这时候回到上面的密码题中

a=e=17
b=ϕ(n)=(p-1)*(q-1)=918650247912

因为 e 和ϕ(n)互质(gcd=1),所以存在逆元 d，通过算法，可以得到 17d+yϕ(n)=1，然后这里的 y 对于我们求解 d 作用不大，那么整个问题可以整理转换成利用扩展欧几里德，计算 gcd(e,ϕ(n)),同时求解 d,y 使得 de+yϕ(n)=gcd(e,ϕ(n))

那么开始编写脚本

p = 447685307
q = 2053
e = 17

phi_n= (p-1) * (q-1)
def extended_gcd(a,b):
    if b==0: #递归结束，没有余数
        return a,1,0  
    gcd,x1,y1=extended_gcd(b,a%b)  #这里有递归
    x=y1
    y=x1-(a//b)*y1
    return gcd,x,y
gcd ,x ,y=extended_gcd(e,phi_n)

d=x%phi_n
print(f"flag{{{d}}}")
#flag{594420748649}

but，本题其实也不用一定掌握扩展欧几里德，直接求逆元就可以了

  • 计算私钥
e×d≡1(modϕ(n))e \times d \equiv 1 \pmod{\phi(n)}

请看这个公式，稍微变换一下，就是d=e^-1 (mod ϕ(n))

p = 447685307
q = 2053
e = 17
phi= (p-1) * (q-1)
d=pow(e,-1,phi)
print(f"flag{{{d}}}")

crypto5

p=447685307 q=2037 e=17 c=704796792

提交 flag{m}

上一个题目，我学会求解 d 了，接下来学下，怎么求明文 m

RSA 解密公式

m≡cd(modn)m \equiv c^d \pmod{n}

那么我可以在上一个脚本的基础上,稍微调整即可,然后 python 中有个特别方便的函数 pow(),比如这里要求解 m，我应该写m=pow(c,d,n)

p = 447685307
q = 2037
e = 17
c = 704796792

phi_n= (p-1) * (q-1)
def extended_gcd(a,b):
    if b==0:
        return a,1,0
    gcd,x1,y1=extended_gcd(b,a%b)
    x=y1
    y=x1-(a//b)*y1
    return gcd,x,y
gcd ,x ,y=extended_gcd(e,phi_n)

d=x%phi_n
print(f"d: {d}")
m=pow(c,d,p*q)
print(f"flag{{{m}}}")
"""
d: 53616899001
flag{904332399012}
"""

babyrsa

这个题我自己写的，算是把基础的 rsa 算法搞明白了

from Crypto.Util.number import long_to_bytes
e = 65537
p = 104046835712664064779194734974271185635538927889880611929931939711001301561682270177931622974642789920918902563361293345434055764293612446888383912807143394009019803471816448923969637980671221111117965227402429634935481868701166522350570364727873283332371986860194245739423508566783663380619142431820861051179
q = 140171048074107988605773731671018901813928130582422889797732071529733091703843710859282267763783461738242958098610949120354497987945911021170842457552182880133642711307227072133812253341129830416158450499258216967879857581565380890788395068130033931180395926482431150295880926480086317733457392573931410220501
c = 4772758911204771028049020670778336799568778930072841084057809867608022732611295305096052430641881550781141776498904005589873830973301898523644744951545345404578466176725030290421649344936952480254902939417215148205735730754808467351639943474816280980230447097444682489223054499524197909719857300597157406075069204315022703894466226179507627070835428226086509767746759353822302809385047763292891543697277097068406512924796409393289982738071019047393972959228919115821862868057003145401072581115989680686073663259771587445250687060240991265143919857962047718344017741878925867800431556311785625469001771370852474292194

phi_n= (p-1) * (q-1)
def extended_gcd(a,b):
    if b==0:
        return a,1,0
    gcd,x1,y1=extended_gcd(b,a%b)
    x=y1
    y=x1-(a//b)*y1
    return gcd,x,y
gcd ,x ,y=extended_gcd(e,phi_n)

d=x%phi_n
print(f"d: {d}")
m=pow(c,d,p*q)
flag=long_to_bytes(m).decode()
print(f"flag: {flag}")
#flag: flag{b4by_R5A}

long_to_bytes 很好用哎

easyrsa1

这个题目不给我 p,q，可以使用在线工具进行因式分解https://factordb.com/

from Crypto.Util.number import long_to_bytes

e = 65537
c = 69380371057914246192606760686152233225659503366319332065009
n = 1455925529734358105461406532259911790807347616464991065301847
p=1201147059438530786835365194567
q=1212112637077862917192191913841


phi_n= (p-1) * (q-1)
def extended_gcd(a,b):
    if b==0:
        return a,1,0
    gcd,x1,y1=extended_gcd(b,a%b)
    x=y1
    y=x1-(a//b)*y1
    return gcd,x,y
gcd ,x ,y=extended_gcd(e,phi_n)

d=x%phi_n
print(f"d: {d}")
m=pow(c,d,p*q)
flag=long_to_bytes(m).decode()
print(f"flag: {flag}")
#flag{fact0r_sma11_N}

easyrsa2

通过 ai 描述，这里可能是共素数攻击，比如说 n1,n2 共用一个 q，这个样子

那么可以有这样的解题思路

已知：
	n1=p*q1
	n2=p*q2
那么，我们可以通过求解最大公因数拿到p
p=gcd(n1,n2)
q1=n1//p
q2=n2//p

这里的 math 库真好，直接有 gcd 可以让我用

from math import gcd
from Crypto.Util.number import long_to_bytes
e = 65537
n1 = 23686563925537577753047229040754282953352221724154495390687358877775380147605152455537988563490716943872517593212858326146811511103311865753018329109314623702207073882884251372553225986112006827111351501044972239272200616871716325265416115038890805114829315111950319183189591283821793237999044427887934536835813526748759612963103377803089900662509399569819785571492828112437312659229879806168758843603248823629821851053775458651933952183988482163950039248487270453888288427540305542824179951734412044985364866532124803746008139763081886781361488304666575456680411806505094963425401175510416864929601220556158569443747
c1 = 1627484142237897613944607828268981193911417408064824540711945192035649088104133038147400224070588410335190662682231189997580084680424209495303078061205122848904648319219646588720994019249279863462981015329483724747823991513714172478886306703290044871781158393304147301058706003793357846922086994952763485999282741595204008663847963539422096343391464527068599046946279309037212859931303335507455146001390326550668531665493245293839009832468668390820282664984066399051403227990068032226382222173478078505888238749583237980643698405005689247922901342204142833875409505180847943212126302482358445768662608278731750064815

n2 = 22257605320525584078180889073523223973924192984353847137164605186956629675938929585386392327672065524338176402496414014083816446508860530887742583338880317478862512306633061601510404960095143941320847160562050524072860211772522478494742213643890027443992183362678970426046765630946644339093149139143388752794932806956589884503569175226850419271095336798456238899009883100793515744579945854481430194879360765346236418019384644095257242811629393164402498261066077339304875212250897918420427814000142751282805980632089867108525335488018940091698609890995252413007073725850396076272027183422297684667565712022199054289711
c2 = 2742600695441836559469553702831098375948641915409106976157840377978123912007398753623461112659796209918866985480471911393362797753624479537646802510420415039461832118018849030580675249817576926858363541683135777239322002741820145944286109172066259843766755795255913189902403644721138554935991439893850589677849639263080528599197595705927535430942463184891689410078059090474682694886420022230657661157993875931600932763824618773420077273617106297660195179922018875399174346863404710420166497017196424586116535915712965147141775026549870636328195690774259990189286665844641289108474834973710730426105047318959307995062

p=gcd(n1,n2)
q1=n1//p
q2=n2//p

phi1=(p-1)*(q1-1)
phi2=(p-1)*(q2-1)

d1=pow(e,-1,phi1)
d2=pow(e,-1,phi2)

m1=pow(c1,d1,n1)
m2=pow(c2,d2,n2)
print(long_to_bytes(m1))
print(long_to_bytes(m2))
#flag{m0_bv_hv_sv}

easyrsa3

上面那个是共素数，这个题目是共模数

共模攻击的核心条件是：gcd(e1,e2)=1

因为：

  • c1 ≡ m^e1 (mod n)
  • c2 ≡ m^e2 (mod n)
  • gcd(792,521)=1 -> a*e1+b*e2=1

所以就会存在

c1^a * c2^b ≡ m^(a*e1) * m^(b*e2) ≡ m^(a*e1 + b*e2) ≡ m^1 ≡ m (mod n)

exp 如下

from math import gcd
from Crypto.Util.number import long_to_bytes

e1 = 797
c1 = 11157593264920825445770016357141996124368529899750745256684450189070288181107423044846165593218013465053839661401595417236657920874113839974471883493099846397002721270590059414981101686668721548330630468951353910564696445509556956955232059386625725883038103399028010566732074011325543650672982884236951904410141077728929261477083689095161596979213961494716637502980358298944316636829309169794324394742285175377601826473276006795072518510850734941703194417926566446980262512429590253643561098275852970461913026108090608491507300365391639081555316166526932233787566053827355349022396563769697278239577184503627244170930
e2 = 521
n = 15944475431088053285580229796309956066521520107276817969079550919586650535459242543036143360865780730044733026945488511390818947440767542658956272380389388112372084760689777141392370253850735307578445988289714647332867935525010482197724228457592150184979819463711753058569520651205113690397003146105972408452854948512223702957303406577348717348753106868356995616116867724764276234391678899662774272419841876652126127684683752880568407605083606688884120054963974930757275913447908185712204577194274834368323239143008887554264746068337709465319106886618643849961551092377843184067217615903229068010117272834602469293571
c2 = 6699274351853330023117840396450375948797682409595670560999898826038378040157859939888021861338431350172193961054314487476965030228381372659733197551597730394275360811462401853988404006922710039053586471244376282019487691307865741621991977539073601368892834227191286663809236586729196876277005838495318639365575638989137572792843310915220039476722684554553337116930323671829220528562573169295901496437858327730504992799753724465760161805820723578087668737581704682158991028502143744445435775458296907671407184921683317371216729214056381292474141668027801600327187443375858394577015394108813273774641427184411887546849

def extended_gcd(a,b):
    if b==0:
        return a,1,0
    g,x1,y1=extended_gcd(b,a%b)
    return g,y1,x1-(a//b)*y1

g,a,b=extended_gcd(e1,e2)

if a < 0:
    c1_inv=pow(c1,-1,n)
    m=(pow(c1_inv,-a,n)*pow(c2,b,n))%n
elif b < 0:
    c2_inv=pow(c2,-1,n)
    m=(pow(c1,a,n)*pow(c2_inv,-b,n))%n
else:
    m=(pow(c1,a,n)*pow(c2,b,n))%n
print(long_to_bytes(m))
#b'flag{sh4r3_N}'

负指数在模运算

数学原理：负指数=模逆元

在模 n 下

c^(-k) ≡ (c^(-1))^k (mod n)

这里 c^(-1)是 c 的模逆元，就是满足c * c^(-1) ≡ 1 (mod n)的数

在 python 中，一般这样求模逆元

c_inv = pow(c, -1, n)  # 等价于 c^(phi(n)-1) mod n

下次遇到这样的题目，可以这样写脚本

if a < 0:
    c1 = pow(c1, -1, n)  # c1变成c1的逆元
    a = -a               # a变成正数
elif b < 0:
    c2 = pow(c2, -1, n)
    b = -b

m = pow(c1, a, n) * pow(c2, b, n) % n

easyrsa4

这个题目的特点是 e 特别小，只有 3,看 ai 的描述，应该考察的是小消息攻击

仔细观察数据，发现 n 特别特别大，我们可以轻松验证 m^e << n，那么这个 m^e 除以 n 的余数一定还是它本身，所以 c=m^3，这里和 n 没有啥关系了（压根没有触发模运算

这就意味着对 c 开立方可以直接获取 m，这是脚本

import gmpy2
c = 150409620528139732054476072280993764527079006992643377862720337847060335153837950368208902491767027770946661
m = gmpy2.iroot(c, 3)
if m[1]:
    print(bytes.fromhex(hex(m[0])[2:]).decode())
#flag{Sm4ll_eee}

easyrsa5

这个题感觉没有上面的难

先进行因式分解,成功了，下次不能再偷懒用 n//q 了，精度会损失

from Crypto.Util.number import *

e = 284100478693161642327695712452505468891794410301906465434604643365855064101922252698327584524956955373553355814138784402605517536436009073372339264422522610010012877243630454889127160056358637599704871937659443985644871453345576728414422489075791739731547285138648307770775155312545928721094602949588237119345
n = 468459887279781789188886188573017406548524570309663876064881031936564733341508945283407498306248145591559137207097347130203582813352382018491852922849186827279111555223982032271701972642438224730082216672110316142528108239708171781850491578433309964093293907697072741538649347894863899103340030347858867705231
c = 350429162418561525458539070186062788413426454598897326594935655762503536409897624028778814302849485850451243934994919418665502401195173255808119461832488053305530748068788500746791135053620550583421369214031040191188956888321397450005528879987036183922578645840167009612661903399312419253694928377398939392827
p=18489327396055733397216193236128138397765028288613793035021305599301380136673327250408422592244732819005905679957567952974717041052102175277835219391448987
q=25336772790324258952117622504537139442881120269760383961991795601846585772802865528712760553670210656524156997774484665833049279421936394718949688217533213

phi=(p-1)*(q-1)
d=pow(e, -1, phi)
m=pow(c, d, n)
print(long_to_bytes(m))
#b'flag{very_biiiiig_e}'

easyrsa6

这题我猜测是爆破查找两个相邻的大素数 p,q，但是我发现可以利用 factordb 直接分解出来，那么就正常计算即可

from Crypto.Util.number import *

e = 0x10001
n = 26737417831000820542131903300607349805884383394154602685589253691058592906354935906805134188533804962897170211026684453428204518730064406526279112572388086653330354347467824800159214965211971007509161988095657918569122896402683130342348264873834798355125176339737540844380018932257326719850776549178097196650971801959829891897782953799819540258181186971887122329746532348310216818846497644520553218363336194855498009339838369114649453618101321999347367800581959933596734457081762378746706371599215668686459906553007018812297658015353803626409606707460210905216362646940355737679889912399014237502529373804288304270563
c = 18343406988553647441155363755415469675162952205929092244387144604220598930987120971635625205531679665588524624774972379282080365368504475385813836796957675346369136362299791881988434459126442243685599469468046961707420163849755187402196540739689823324440860766040276525600017446640429559755587590377841083082073283783044180553080312093936655426279610008234238497453986740658015049273023492032325305925499263982266317509342604959809805578180715819784421086649380350482836529047761222588878122181300629226379468397199620669975860711741390226214613560571952382040172091951384219283820044879575505273602318856695503917257
p=163515803000813412334620775647541652549604895368507102613553057136855632963322853570924931001138446030409251690646645635800254129997200577719209532684847732809399187385176309169421205833279943214621695444496660249881675974141488357432373412184140130503562295159152949524373214358417567189638680209172147385163
q=163515803000813412334620775647541652549604895368507102613553057136855632963322853570924931001138446030409251690646645635800254129997200577719209532684847732809399187385176309169421205833279943214621695444496660249881675974141488357432373412184140130503562295159152949524373214358417567189638680209172147385801

phi=(p-1)*(q-1)
d=pow(e, -1, phi)
m=pow(c, d, n)
print(long_to_bytes(m))
#b'flag{p&q_4re_t00_c1o5ed}'

这是相邻 p,q 爆破脚本

import gmpy2
from Crypto.Util.number import long_to_bytes

n = 26737417831000820542131903300607349805884383394154602685589253691058592906354935906805134188533804962897170211026684453428204518730064406526279112572388086653330354347467824800159214965211971007509161988095657918569122896402683130342348264873834798355125176339737540844380018932257326719850776549178097196650971801959829891897782953799819540258181186971887122329746532348310216818846497644520553218363336194855498009339838369114649453618101321999347367800581959933596734457081762378746706371599215668686459906553007018812297658015353803626409606707460210905216362646940355737679889912399014237502529373804288304270563
c = 18343406988553647441155363755415469675162952205929092244387144604220598930987120971635625205531679665588524624774972379282080365368504475385813836796957675346369136362299791881988434459126442243685599469468046961707420163849755187402196540739689823324440860766040276525600017446640429559755587590377841083082073283783044180553080312093936655426279610008234238497453986740658015049273023492032325305925499263982266317509342604959809805578180715819784421086649380350482836529047761222588878122181300629226379468397199620669975860711741390226214613560571952382040172091951384219283820044879575505273602318856695503917257

def fermat_factor(n):
    a = gmpy2.isqrt(n)
    if a * a < n:
        a += 1
    
    b2 = a * a - n
    while not gmpy2.is_square(b2):
        a += 1
        b2 = a * a - n
    
    b = gmpy2.isqrt(b2)
    p = a - b
    q = a + b
    return p, q

p, q = fermat_factor(n)
print(f"p = {p}")
print(f"q = {q}")
print(f"p * q == n: {p * q == n}")

phi = (p - 1) * (q - 1)
e = 0x10001
d = gmpy2.invert(e, phi)
m = pow(c, d, n)
flag = long_to_bytes(m)
print(flag)

算法原理如下

如果 n = p × q
那么存在两个数：
    a = (p + q)/2
    b = (q - p)/2

则：n = a² - b²
    → a² - n = b²

用 n=15 进行举例

  • 取 a= ⌈√n⌉

    • √15 ≈ 3.87 → a = 4

  • 计算 b² = a² - n

    • a = 4 → a² = 16
b² = 16 - 15 = 1

  • 检测 b²是否是完全平方数

    • √1 = 1 ✅ 是整数

  • 计算 p,q

    • b = 1
p = a - b = 4 - 1 = 3
q = a + b = 4 + 1 = 5

就这样，可以轻松找到两个相邻的素数，回到我因式分解出来的两个素数，两个数字直接也就差距 638,所以 b=(q-p)/2=319

这意味着我们从 a = ⌈√n⌉开始，最多尝试 319 次就能成功找到 b²，整个时间复杂度最坏也就 O(319)

easyrsa7

这题就是传说中的 RSA 高位已知攻击(Coppersmith)，之前看到就逃了，现在好好学下

首先分析下

题目给了p_high = (p >> 128) << 128 那么完整的p=p_high+x,x 就是未知的低 128bit

Coppersmith 定理

知道 n = p × q，且知道 p 的高位（或低位），当未知比特数 ≤ n 比特数的 1/4 时，可以在多项式时间内恢复完整的 p

本题中 n 是 2048bit，p 是 1024bit，x 是 128bit，那么 128bit<2048/4=512bit，条件成立，可以尝试恢复

解题思路

p = p_high + x
x < 2^k  （k是未知位数）
需要解方程：(p_high + x) 能整除 n
这个方程可以借助LLL格基约化求解
  • exp
from Crypto.Util.number import long_to_bytes

n = 0x79e0bf9b916e59286163a1006f8cefd4c1b080387a6ddb98a3f3984569a4ebb48b22ac36dff7c98e4ebb90ffdd9c07f53a20946f57634fb01f4489fcfc8e402865e152820f3e2989d4f0b5ef1fb366f212e238881ea1da017f754d7840fc38236edba144674464b661d36cdaf52d1e5e7c3c21770c5461a7c1bc2db712a61d992ebc407738fc095cd8b6b64e7e532187b11bf78a8d3ddf52da6f6a67c7e88bef5563cac1e5ce115f3282d5ff9db02278859f63049d1b934d918f46353fea1651d96b2ddd874ec8f1e4b9d487d8849896d1c21fb64029f0d6f47e560555b009b96bfd558228929a6cdf3fb6d47a956829fb1e638fcc1bdfad4ec2c3590dea1ed3
c = 0x1b2b4f9afed5fb5f9876757e959c183c2381ca73514b1918d2f123e386bebe9832835350f17ac439ac570c9b2738f924ef49afea02922981fad702012d69ea3a3c7d1fc8efc80e541ca2622d7741090b9ccd590906ac273ffcc66a7b8c0d48b7d62d6cd6dd4cd75747c55aac28f8be3249eb255d8750482ebf492692121ab4b27b275a0f69b15baef20bf812f3cbf581786128b51694331be76f80d6fb1314d8b280eaa16c767821b9c2ba05dfde5451feef22ac3cb3dfbc88bc1501765506f0c05045184292a75c475486b680f726f44ef8ddfe3c48f75bb03c8d44198ac70e6b7c885f53000654db22c8cee8eb4f65eaeea2da13887aaf53d8c254d2945691
n_int = int(n)
p_high = 0xd1c520d9798f811e87f4ff406941958bab8fc24b19a32c3ad89b0b73258ed3541e9ca696fd98ce15255264c39ae8c6e8db5ee89993fa44459410d30a0a8af700ae3aee8a9a1d6094f8c757d3b79a8d1147e85be34fb260a970a52826c0a92b46cefb5dfaf2b5a31edf867f8d34d2222900000000000000000000000000000000

P.<x> = PolynomialRing(Zmod(n))
f = p_high + x
roots = f.small_roots(X=2**128, beta=0.4)

if roots:
    x0 = roots[0]
    p = int(p_high + x0)
    if n_int % p == 0:
        q = n_int // p
        e = 0x10001
        phi = (p-1)*(q-1)
        d = pow(e, -1, phi)
        m = pow(c, d, n_int)
        flag = long_to_bytes(int(m))
        print(f"Flag: {flag}")
     
 #Flag: b'flag{Kn0wn_Hi9h_Bit5}'

喜欢的话，留下你的评论吧～