首页周刊友链关于

ctfshow刷题小记-crypto

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

Yolo avatar

Yolo

CTFer / misc / V&N

16 文章

8 分类

20 标签
首页 周刊
分类 标签 归档
友链 关于
ctfplus-Crypto studyctfshow刷题小记-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}'

easyrsa8

通过这个题，我理解了那些公钥的具体结构了

这里举个例子

-----BEGIN PUBLIC KEY-----
MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgTlUlVTKPIIMNZGz82fqFxZ3UlgR
vFSyYIPIHCJxfSzCsQncqlVyt5QiNoI8b0UhrZesJYexcMdmkb57/4OYKphkT8ok
5CFIOwE4CPE036NYe9OMh8e3uNp2VceEsF5C14m87sB4YmHe9qMGJwb9wjb9eA7s
7+h2HehtD5ZOUeHAEQIDAQAB
-----END PUBLIC KEY-----

可以借助 openssl 工具解开封装

yolo@Yolo /m/c/U/2/D/easyrsa8> openssl rsa -pubin -in public.key  -text -noout                                   (sage)
Public-Key: (1030 bit)
Modulus:
    39:54:95:54:ca:3c:82:0c:35:91:b3:f3:67:ea:17:
    16:77:52:58:11:bc:54:b2:60:83:c8:1c:22:71:7d:
    2c:c2:b1:09:dc:aa:55:72:b7:94:22:36:82:3c:6f:
    45:21:ad:97:ac:25:87:b1:70:c7:66:91:be:7b:ff:
    83:98:2a:98:64:4f:ca:24:e4:21:48:3b:01:38:08:
    f1:34:df:a3:58:7b:d3:8c:87:c7:b7:b8:da:76:55:
    c7:84:b0:5e:42:d7:89:bc:ee:c0:78:62:61:de:f6:
    a3:06:27:06:fd:c2:36:fd:78:0e:ec:ef:e8:76:1d:
    e8:6d:0f:96:4e:51:e1:c0:11
Exponent: 65537 (0x10001)

如果手动处理的话，我们需要先将上下的标签删除，然后删除换行符，进行 base64 解码，然后进行 hex 编码，可以拿到这样的信息

30 81 9f 30 0d 06 09 2a 86 48 86 f7 0d 01 01 01 05 00 03 81 8d 00 30 81 89 02 81 81 39 54 95 54 ca 3c 82 0c 35 91 b3 f3 67 ea 17 16 77 52 58 11 bc 54 b2 60 83 c8 1c 22 71 7d 2c c2 b1 09 dc aa 55 72 b7 94 22 36 82 3c 6f 45 21 ad 97 ac 25 87 b1 70 c7 66 91 be 7b ff 83 98 2a 98 64 4f ca 24 e4 21 48 3b 01 38 08 f1 34 df a3 58 7b d3 8c 87 c7 b7 b8 da 76 55 c7 84 b0 5e 42 d7 89 bc ee c0 78 62 61 de f6 a3 06 27 06 fd c2 36 fd 78 0e ec ef e8 76 1d e8 6d 0f 96 4e 51 e1 c0 11 02 03 01 00 01

这是给机器读的，用到了 ASN.1 标准

这里有个表格可以对照

十六进制片段含义说明
30 81 9fSEQUENCE: 开启一个序列，长度为 0x9f (159 字节)。这是整个公钥的容器。
30 0dSEQUENCE: 内部小序列，记录算法标识。
06 09 2a 86 48 86 f7 0d 01 01 01OID: 对象标识符，这里特指 rsaEncryption。
05 00NULL: 算法参数为空。
03 81 8d 00BIT STRING: 后面包裹的是密钥位串。
30 81 89SEQUENCE: 进入真正的 RSA 核心：包含 nn 和 ee 的序列。
02 81 81INTEGER (n): 声明接下来的 0x81 (129) 字节是模数 nn。
39 54 95 ... c0 11Value of nn: 这就是你用 openssl 看到的那个超长数值。
02 03INTEGER (e): 声明接下来的 0x03 字节是指数 ee。
01 00 01Value of ee: 转换成十进制就是 65537

真的高级，综上，我们获取了 n 和 e

n_hex="39549554ca3c820c3591b3f367ea171677525811bc54b26083c81c22717d2cc2b109dcaa5572b7942236823c6f4521ad97ac2587b170c76691be7bff83982a98644fca24e421483b013808f134dfa3587bd38c87c7b7b8da7655c784b05e42d789bceec0786261def6a3062706fdc236fd780eecefe8761de86d0f964e51e1c011"
n_decimal=int(n_hex,16)
print("n="n_decimal)
#n=10306247299477991196335954707897189353577589618180446614762218980226685668311143526740800444344046158260556585833057716406703213966249956775927205061731821632025483608182881492214855240841820024816859031176291364212054293818204399157346955465232586109199762630150640804366966946066155685218609638749171632685073
#e=0x10001

借助 factordb 工具，可以将 n 分解，获得

p=97
q=106249972159566919549855203174197828387397831115262336234662051342543151219702510584956705611794290291345944183845955839244363030579896461607496959399297130227066841321473005074379950936513608503266587950271044991876848389878395867601515004796212227929894460104645781488319246866661398816686697306692491058609

那么进行 rsa 解密

from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP

n=10306247299477991196335954707897189353577589618180446614762218980226685668311143526740800444344046158260556585833057716406703213966249956775927205061731821632025483608182881492214855240841820024816859031176291364212054293818204399157346955465232586109199762630150640804366966946066155685218609638749171632685073
e=65537
p=97
q=106249972159566919549855203174197828387397831115262336234662051342543151219702510584956705611794290291345944183845955839244363030579896461607496959399297130227066841321473005074379950936513608503266587950271044991876848389878395867601515004796212227929894460104645781488319246866661398816686697306692491058609
phi=(p-1)*(q-1)
d=pow(e,-1,phi)
privatekey=RSA.construct((n,e,d,p,q))
rsa=PKCS1_OAEP.new(privatekey)
m=rsa.decrypt(open('flag.enc','rb').read())
print(m.decode())
#flag{p_1s_5mall_num6er}

这个题目有点特殊，就是那个密文还有层 pkcs1 填充，建议用 rsa 协议库进行解密处理，d 还是用到了的，只是我需要先重构成完整的私钥文件，然后才能解密

funnyrsa1

这个题目的特点是：

  • p1=p2
  • e1,e2 不是质数

这是我的解题思路（哈哈，想起来当初入门 ctf 的时候，密码手告诉我，授课只要带两草稿纸就 ok 了

36d2b2237080ca81b4e302c949f536a9_720 
#exp.sage
from Crypto.Util.number import long_to_bytes
e1 = 14606334023791426
p1 = 121009772735460235364940622989433807619211926015494087453674747614331295040063679722422298286549493698150690694965106103822315378461970129912436074962111424616439032849788953648286506433464358834178903821069564798378666159882090757625817745990230736982709059859613843100974349380542982235135982530318438330859
q1 = 130968576816900149996914427770826228884925960001279609559095138835900329492765336419489982304805369724685145941218640504262821549441728192761733409684831633194346504685627189375724517070780334885673563409259345291959439026700006694655545512308390416859315892447092639503318475587220630455745460309886030186593
c1 = 11402389955595766056824801105373550411371729054679429421548608725777586555536302409478824585455648944737304660137306241012321255955693234304201530700362069004620531537922710568821152217381257446478619320278993539785699090234418603086426252498046106436360959622415398647198014716351359752734123844386459925553497427680448633869522591650121047156082228109421246662020164222925272078687550896012363926358633323439494967417041681357707006545728719651494384317497942177993032739778398001952201667284323691607312819796036779374423837576479275454953999865750584684592993292347483309178232523897058253412878901324740104919248

e2 = 13813369129257838
p2 = 121009772735460235364940622989433807619211926015494087453674747614331295040063679722422298286549493698150690694965106103822315378461970129912436074962111424616439032849788953648286506433464358834178903821069564798378666159882090757625817745990230736982709059859613843100974349380542982235135982530318438330859
q2 = 94582257784130735233174402362819395926641026753071039760251190444144495369829487705195913337502962816079184062352678128843179586054535283861793827497892600954650126991213176547276006780610945133603745974181504975165082485845571788686928859549252522952174376071500707863379238688200493621993937563296490615649
c2 = 7984888899827615209197324489527982755561403577403539988687419233579203660429542197972867526015619223510964699107198708420785278262082902359114040327940253582108364104049849773108799812000586446829979564395322118616382603675257162995702363051699403525169767736410365076696890117813211614468971386159587698853722658492385717150691206731593509168262529568464496911821756352254486299361607604338523750318977620039669792468240086472218586697386948479265417452517073901655900118259488507311321060895347770921790483894095085039802955700146474474606794444308825840221205073230671387989412399673375520605000270180367035526919
phi1 = (p1-1)*(q1-1)
phi2 = (p2-1)*(q2-1)

b=gcd(e1,e2)

a1=e1//b
a2=e2//b

d1=pow(a1, -1, phi1)
d2=pow(a2, -1, phi2)

m1=pow(c1, d1, p1*q1)
m2=pow(c2, d2, p2*q2)

r1 = m1 % p1
r2 = m1 % q1
r3 = m2 % q2

x=crt([r1,r2,r3],[p1,q1,q2])

m=x.nth_root(b)
print(long_to_bytes(m))
#b"flag{gcd_e&\xcf\x86_isn't_1}"

funnyrsa2

这题的特殊地方是 n=pqr,三个素数相乘，不过好在，这里的 n 可以使用 factordb 进行分解，再将 phi 按照欧拉函数多乘一个(r-1)即可

本题 exp

# exp.sage
from Crypto.Util.number import long_to_bytes
n = 897607935780955837078784515115186203180822213482989041398073067996023639
c = 490571531583321382715358426750276448536961994273309958885670149895389968
e = 0x10001

p=876391552113414716726089
q=932470255754103340237147
r=1098382268985762240184333

phi = (p-1)*(q-1)*(r-1)
d=pow(e, -1, phi)

m=pow(c, d, n)
print(long_to_bytes(m))
#b'flag{what_that_fvck_r}'

funnyrsa3

这个题目有点意思，给了 dp，dp 就是d mod(p-1)，dp 泄露的题目，做法一般是爆破处理，将 p 倒推出来,爆破的限制不多，只要保证是整数即可

funnyrsa3 
#exp.sage
from Crypto.Util.number import long_to_bytes
e = 65537
n = 13851998696110232034312408768370264747862778787235362033287301947690834384177869107768578977872169953363148442670412868565346964490724532894099772144625540138618913694240688555684873934424471837897053658485573395777349902581306875149677867098014969597240339327588421766510008083189109825385296069501377605893298996953970043168244444585264894721914216744153344106498382558756181912535774309211692338879110643793628550244212618635476290699881188640645260075209594318725693972840846967120418641315829098807385382509029722923894508557890331485536938749583463709142484622852210528766911899504093351926912519458381934550361
dp = 100611735902103791101540576986246738909129436434351921338402204616138072968334504710528544150282236463859239501881283845616704984276951309172293190252510177093383836388627040387414351112878231476909883325883401542820439430154583554163420769232994455628864269732485342860663552714235811175102557578574454173473
c = 6181444980714386809771037400474840421684417066099228619603249443862056564342775884427843519992558503521271217237572084931179577274213056759651748072521423406391343404390036640425926587772914253834826777952428924120724879097154106281898045222573790203042535146780386650453819006195025203611969467741808115336980555931965932953399428393416196507391201647015490298928857521725626891994892890499900822051002774649242597456942480104711177604984775375394980504583557491508969320498603227402590571065045541654263605281038512927133012338467311855856106905424708532806690350246294477230699496179884682385040569548652234893413

for k in range(1,e):
    if (e*dp-1) % k == 0:
        p=(e*dp-1) // k + 1
        if n % p == 0:
            q=n//p
            break
phi=(p-1)*(q-1)
d=pow(e,-1,phi)
m=pow(c,d,n)
print(long_to_bytes(m))
#b'flag{dp_i5_1eak}'

unusualrsa1

哇，这题难度一下上来了，仔细观察，发现 e=3 是很低的指数了，然后 m 的高位被泄露了，可以联系上面 easyrsa7 用到的 Coppersmith 算法解决

通过 ai 学会了这个题的做法，不得不惊叹，这个和 zip 压缩包的明文攻击有点像，因为都没有求解私钥 d，通过固定已知明文能直接绕过，天呐，好有缘分

#exp.sage
from Crypto.Util.number import long_to_bytes
n=14113948189208713011909396304970377626324044633561155020366406284451614054260708934598840781397326960921718892801653205159753091559901114082556464576477585198060530094478860626532455065960136263963965819002575418616768412539016154873800614138683106056209070597212668250136909436974469812231498651367459717175769611385545792201291192023843434476550550829737236225181770896867698281325858412643953550465132756142888893550007041167700300621499970661661288422834479368072744930285128061160879720771910458653611076539210357701565156322144818787619821653007453741709031635862923191561438148729294430924288173571196757351837
m_high=1520800285708753284739523608878585974609134243280728660335545667177630830064371336150456537012842986526527904043383436211487979254140749228004148347597566264500276581990635110200009305900689510908049771218073767918907869112593870878204145615928290375086195098919355531430003571366638390993296583488184959318678321571278510231561645872308920917404996519309473979203661442792048291421574603018835698487725981963573816645574675640357569465990665689618997534740389987351864738104038598104713275375385003471306823348792559733332094774873827383320058176803218213042061965933143968710199376164960850951030741280074168795136
c=6635663565033382363211849843446648120305449056573116171933923595209656581213410699649926913276685818674688954045817246263487415328838542489103709103428412175252447323358040041217431171817865818374522191881448865227314554997131690963910348820833080760482835650538394814181656599175839964284713498394589419605748581347163389157651739759144560719049281761889094518791244702056048080280278984031050608249265997808217512349309696532160108250480622956599732443714546043439089844571655280770141647694859907985919056009576606333143546094941635324929407538860140272562570973340199814409134962729885962133342668270226853146819

k=315
X=2^k

PR.<x>=PolynomialRing(Zmod(n))
f=(m_high+x)^3-c
roots=f.small_roots(X=X,beta=0.5)
root=roots[0]
m=(m_high+root)
print(long_to_bytes(int(m)))
#b'\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0cflag{r54__c0pp3r5m17h_p4r714l_m_4774ck_15_c00l~}'

unusualrsa2

这题特殊的地方是，又引进了 x,y 两个未知数序列

reduce(lambda x,y:x&y,[(i-5)*i+6==0 for i in x])
  • 对每个 i 计算(i-5)*i+6 是否等于 0，稍微化简下(i-2)(i-3)=0,所以每个 i 都是 2 或 3
  • reduce 是让所有元素都满足上述情况
  • 可以确定 x=[2 或 3,2 或 3,…]这个序列的长度未知，但是可以确定元素是 2 或 3
reduce(lambda x,y:x&y,[(j-15)*j+44==0 for j in y])
  • 对每个 j 进行计算(j-15)j+44=0,解方程，求得 j=11 或 4
  • 那么就确定 y=[11 或 4,11 或 4,…]和上面的 x 序列的情况差不多
print(pow(reduce(lambda x,y:x*m+y,x),17,n))
print(pow(reduce(lambda x,y:x*m+y,y),17,n))

  • reduce(lambda x,y: x*m+y,x)作用

    • 假设 x=[i1,i2,i3]
    • result=((i1*m+i2)*m+i3)...
    • 本质上就是将原来的整数数组编码成一个大整数，类似 m 进制编码，每个元素作为一位

    pow(...,17,n)：指数 17 后mod n

通过上面的分析，emm，可以观察到，这里 m 进制展开的话，理论一定可以整理成 m*(…)+x，那么！我们是不是可以同时构造两个式子？寻找两个式子在多项环中的的 gcd，就可以找到我们需要的 m

但是 m 的范围不好确定，留意到假如设M1=2m+3,M2=4m+11,那么一定存在M2=2(2m+3)+5=2M1+5，可以构造线性关系

but，这里有点点牵强，正式比赛的时候只能做这种尝试，因为如果让 x=[2,2,2,2,…],y=[11,4,11,4,4,11,…]，额，无法建立线性关系，分类讨论吧，但事实证明，本题可以大胆往线性关系上面凑

本题的解决方法有个名称：Franklin-Reiter 攻击（因为是他们两提出来的

我们现在有两个密文：

  • C1≡M1^17(modn)
  • C2≡(2M1+5)^17(modn)

在多项式环 Zn[X]中，我们可以定义两个多项式：

  • f1(X)=X^17-C1
  • f2(X)=(2X+5)^17-C2

很显然，M1 是这两个多项式在模 n 下的共同根，通过计算两个多项式的 GCD，可以直接提取线性因子(X-M1),从而求得 M1

#exp.sage
from Crypto.Util.number import long_to_bytes, inverse
n = 23772599983135215481563178266884362291876571759991288577057472733374903836591330410574958472090396886895304944176208711481780781286891334062794555288959410390926474473859289842654809538435377431088422352076225067494924657598298955407771484146155998883073439266427190212827600119365643065276814044272790573450938596830336430371987561905132579730619341196199420897034988685012777895002554746080384319298123154671447844799088258541911028041717897434816921424155687677867019535399434825468160227242441375503664915265223696139025407768146464383537556265875013085702422829200814612395116961538432886116917063119749068212699
c1 = 10900151504654409767059699202929100225155892269473271859207513720755903691031362539478242920144073599515746938827937863835169270383721094542639011665235593065932998091574636525973099426040452626893461449084383663453549354608769727777329036059746386523843912382289597182615339786437186169811342356085836838520978047561127661777189045888648773949147220411427306098338616422692914110656004863767719312410906124366000507952960331116878197129010412361636679449281808407214524741732730279777729251515759320442591663641984363061618865267606007355576230009922421807527598213455112981354590909603317525854070358390622096569841
c2 = 17298679220717326374674940612143058330715465693318467692839033642321129433471254547497087746971317567301086124779289015934582615377165560688447452762043163082394944604062014490446763247008217251611443338103074143809936437694543761369945095202092750900940979469994907399829695696313513303922266742415376818434932335640062684245008822643258497589196668426788916969378417960200705779461808292296450298558001909603602502604228973101048082095642290047196235959438278631661658312398313171590515776453711432353011579809351076532129444735206408591345372296372378396539831385036814349328459266432393612919118094115543053115450
e = 17

PR.<X> = PolynomialRing(Zmod(n))

f1 = X^e - c1
f2 = (2*X + 5)^e - c2

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a.monic()
res = gcd(f1, f2) #这里拿到的是多项式，并不是一个数
m1 = n - res.coefficients()[0] #coefficients拿的是常数项，然后因为全局要在模n下运算，所以用n减去这个数就得到了m1
m = ((m1 - 3) * inverse(2, n)) % n
print(long_to_bytes(int(m)))
#b'flag{r54__r3l473d_m355463_4774ck_4l50_c4ll3d_fr4nkl1n_r3173r_4774ck~}'

unusualrsa3

本题的特殊点在于，这里不是整数域上的 RSA，而是多项式中的，那么我们就得对应的进行调整，比如说 N(x)=P(x)*Q(x)这样类似的操作,遇到这样的题目，有个特点，就是那个 N 一般来说可以分解成一个常熟项和两个不可分解的多项式，因为常数项可以直接利用逆元消掉，所以我们直接默认两个多项式分别是 p(x),q(x)

p=2470567871
R.<x> =PolynomialRing(GF(p))
N=1932231392*x^255 + 1432733708*x^254 + 1270867914*x^253 + 1573324635*x^252 + 2378103997*x^251 + 820889786*x^250 + 762279735*x^249 + 1378353578*x^248 + 1226179520*x^247 + 657116276*x^246 + 1264717357*x^245 + 1015587392*x^244 + 849699356*x^243 + 1509168990*x^242 + 2407367106*x^241 + 873379233*x^240 + 2391647981*x^239 + 517715639*x^238 + 828941376*x^237 + 843708018*x^236 + 1526075137*x^235 + 1499291590*x^234 + 235611028*x^233 + 19615265*x^232 + 53338886*x^231 + 434434839*x^230 + 902171938*x^229 + 516444143*x^228 + 1984443642*x^227 + 966493372*x^226 + 1166227650*x^225 + 1824442929*x^224 + 930231465*x^223 + 1664522302*x^222 + 1067203343*x^221 + 28569139*x^220 + 2327926559*x^219 + 899788156*x^218 + 296985783*x^217 + 1144578716*x^216 + 340677494*x^215 + 254306901*x^214 + 766641243*x^213 + 1882320336*x^212 + 2139903463*x^211 + 1904225023*x^210 + 475412928*x^209 + 127723603*x^208 + 2015416361*x^207 + 1500078813*x^206 + 1845826007*x^205 + 797486240*x^204 + 85924125*x^203 + 1921772796*x^202 + 1322682658*x^201 + 2372929383*x^200 + 1323964787*x^199 + 1302258424*x^198 + 271875267*x^197 + 1297768962*x^196 + 2147341770*x^195 + 1665066191*x^194 + 2342921569*x^193 + 1450622685*x^192 + 1453466049*x^191 + 1105227173*x^190 + 2357717379*x^189 + 1044263540*x^188 + 697816284*x^187 + 647124526*x^186 + 1414769298*x^185 + 657373752*x^184 + 91863906*x^183 + 1095083181*x^182 + 658171402*x^181 + 75339882*x^180 + 2216678027*x^179 + 2208320155*x^178 + 1351845267*x^177 + 1740451894*x^176 + 1302531891*x^175 + 320751753*x^174 + 1303477598*x^173 + 783321123*x^172 + 1400145206*x^171 + 1379768234*x^170 + 1191445903*x^169 + 946530449*x^168 + 2008674144*x^167 + 2247371104*x^166 + 1267042416*x^165 + 1795774455*x^164 + 1976911493*x^163 + 167037165*x^162 + 1848717750*x^161 + 573072954*x^160 + 1126046031*x^159 + 376257986*x^158 + 1001726783*x^157 + 2250967824*x^156 + 2339380314*x^155 + 571922874*x^154 + 961000788*x^153 + 306686020*x^152 + 80717392*x^151 + 2454799241*x^150 + 1005427673*x^149 + 1032257735*x^148 + 593980163*x^147 + 1656568780*x^146 + 1865541316*x^145 + 2003844061*x^144 + 1265566902*x^143 + 573548790*x^142 + 494063408*x^141 + 1722266624*x^140 + 938551278*x^139 + 2284832499*x^138 + 597191613*x^137 + 476121126*x^136 + 1237943942*x^135 + 275861976*x^134 + 1603993606*x^133 + 1895285286*x^132 + 589034062*x^131 + 713986937*x^130 + 1206118526*x^129 + 311679750*x^128 + 1989860861*x^127 + 1551409650*x^126 + 2188452501*x^125 + 1175930901*x^124 + 1991529213*x^123 + 2019090583*x^122 + 215965300*x^121 + 532432639*x^120 + 1148806816*x^119 + 493362403*x^118 + 2166920790*x^117 + 185609624*x^116 + 184370704*x^115 + 2141702861*x^114 + 223551915*x^113 + 298497455*x^112 + 722376028*x^111 + 678813029*x^110 + 915121681*x^109 + 1107871854*x^108 + 1369194845*x^107 + 328165402*x^106 + 1792110161*x^105 + 798151427*x^104 + 954952187*x^103 + 471555401*x^102 + 68969853*x^101 + 453598910*x^100 + 2458706380*x^99 + 889221741*x^98 + 320515821*x^97 + 1549538476*x^96 + 909607400*x^95 + 499973742*x^94 + 552728308*x^93 + 1538610725*x^92 + 186272117*x^91 + 862153635*x^90 + 981463824*x^89 + 2400233482*x^88 + 1742475067*x^87 + 437801940*x^86 + 1504315277*x^85 + 1756497351*x^84 + 197089583*x^83 + 2082285292*x^82 + 109369793*x^81 + 2197572728*x^80 + 107235697*x^79 + 567322310*x^78 + 1755205142*x^77 + 1089091449*x^76 + 1993836978*x^75 + 2393709429*x^74 + 170647828*x^73 + 1205814501*x^72 + 2444570340*x^71 + 328372190*x^70 + 1929704306*x^69 + 717796715*x^68 + 1057597610*x^67 + 482243092*x^66 + 277530014*x^65 + 2393168828*x^64 + 12380707*x^63 + 1108646500*x^62 + 637721571*x^61 + 604983755*x^60 + 1142068056*x^59 + 1911643955*x^58 + 1713852330*x^57 + 1757273231*x^56 + 1778819295*x^55 + 957146826*x^54 + 900005615*x^53 + 521467961*x^52 + 1255707235*x^51 + 861871574*x^50 + 397953653*x^49 + 1259753202*x^48 + 471431762*x^47 + 1245956917*x^46 + 1688297180*x^45 + 1536178591*x^44 + 1833258462*x^43 + 1369087493*x^42 + 459426544*x^41 + 418389643*x^40 + 1800239647*x^39 + 2467433889*x^38 + 477713059*x^37 + 1898813986*x^36 + 2202042708*x^35 + 894088738*x^34 + 1204601190*x^33 + 1592921228*x^32 + 2234027582*x^31 + 1308900201*x^30 + 461430959*x^29 + 718926726*x^28 + 2081988029*x^27 + 1337342428*x^26 + 2039153142*x^25 + 1364177470*x^24 + 613659517*x^23 + 853968854*x^22 + 1013582418*x^21 + 1167857934*x^20 + 2014147362*x^19 + 1083466865*x^18 + 1091690302*x^17 + 302196939*x^16 + 1946675573*x^15 + 2450124113*x^14 + 1199066291*x^13 + 401889502*x^12 + 712045611*x^11 + 1850096904*x^10 + 1808400208*x^9 + 1567687877*x^8 + 2013445952*x^7 + 2435360770*x^6 + 2414019676*x^5 + 2277377050*x^4 + 2148341337*x^3 + 1073721716*x^2 + 1045363399*x + 1809685811
c=922927962*x^254 + 1141958714*x^253 + 295409606*x^252 + 1197491798*x^251 + 2463440866*x^250 + 1671460946*x^249 + 967543123*x^248 + 119796323*x^247 + 1172760592*x^246 + 770640267*x^245 + 1093816376*x^244 + 196379610*x^243 + 2205270506*x^242 + 459693142*x^241 + 829093322*x^240 + 816440689*x^239 + 648546871*x^238 + 1533372161*x^237 + 1349964227*x^236 + 2132166634*x^235 + 403690250*x^234 + 835793319*x^233 + 2056945807*x^232 + 480459588*x^231 + 1401028924*x^230 + 2231055325*x^229 + 1716893325*x^228 + 16299164*x^227 + 1125072063*x^226 + 1903340994*x^225 + 1372971897*x^224 + 242927971*x^223 + 711296789*x^222 + 535407256*x^221 + 976773179*x^220 + 533569974*x^219 + 501041034*x^218 + 326232105*x^217 + 2248775507*x^216 + 1010397596*x^215 + 1641864795*x^214 + 1365178317*x^213 + 1038477612*x^212 + 2201213637*x^211 + 760847531*x^210 + 2072085932*x^209 + 168159257*x^208 + 70202009*x^207 + 1193933930*x^206 + 1559162272*x^205 + 1380642174*x^204 + 1296625644*x^203 + 1338288152*x^202 + 843839510*x^201 + 460174838*x^200 + 660412151*x^199 + 716865491*x^198 + 772161222*x^197 + 924177515*x^196 + 1372790342*x^195 + 320044037*x^194 + 117027412*x^193 + 814803809*x^192 + 1175035545*x^191 + 244769161*x^190 + 2116927976*x^189 + 617780431*x^188 + 342577832*x^187 + 356586691*x^186 + 695795444*x^185 + 281750528*x^184 + 133432552*x^183 + 741747447*x^182 + 2138036298*x^181 + 524386605*x^180 + 1231287380*x^179 + 1246706891*x^178 + 69277523*x^177 + 2124927225*x^176 + 2334697345*x^175 + 1769733543*x^174 + 2248037872*x^173 + 1899902290*x^172 + 409421149*x^171 + 1223261878*x^170 + 666594221*x^169 + 1795456341*x^168 + 406003299*x^167 + 992699270*x^166 + 2201384104*x^165 + 907692883*x^164 + 1667882231*x^163 + 1414341647*x^162 + 1592159752*x^161 + 28054099*x^160 + 2184618098*x^159 + 2047102725*x^158 + 103202495*x^157 + 1803852525*x^156 + 446464179*x^155 + 909116906*x^154 + 1541693644*x^153 + 166545130*x^152 + 2283548843*x^151 + 2348768005*x^150 + 71682607*x^149 + 484339546*x^148 + 669511666*x^147 + 2110974006*x^146 + 1634563992*x^145 + 1810433926*x^144 + 2388805064*x^143 + 1200258695*x^142 + 1555191384*x^141 + 363842947*x^140 + 1105757887*x^139 + 402111289*x^138 + 361094351*x^137 + 1788238752*x^136 + 2017677334*x^135 + 1506224550*x^134 + 648916609*x^133 + 2008973424*x^132 + 2452922307*x^131 + 1446527028*x^130 + 29659632*x^129 + 627390142*x^128 + 1695661760*x^127 + 734686497*x^126 + 227059690*x^125 + 1219692361*x^124 + 635166359*x^123 + 428703291*x^122 + 2334823064*x^121 + 204888978*x^120 + 1694957361*x^119 + 94211180*x^118 + 2207723563*x^117 + 872340606*x^116 + 46197669*x^115 + 710312088*x^114 + 305132032*x^113 + 1621042631*x^112 + 2023404084*x^111 + 2169254305*x^110 + 463525650*x^109 + 2349964255*x^108 + 626689949*x^107 + 2072533779*x^106 + 177264308*x^105 + 153948342*x^104 + 1992646054*x^103 + 2379817214*x^102 + 1396334187*x^101 + 2254165812*x^100 + 1300455472*x^99 + 2396842759*x^98 + 2398953180*x^97 + 88249450*x^96 + 1726340322*x^95 + 2004986735*x^94 + 2446249940*x^93 + 520126803*x^92 + 821544954*x^91 + 1177737015*x^90 + 676286546*x^89 + 1519043368*x^88 + 224894464*x^87 + 1742023262*x^86 + 142627164*x^85 + 1427710141*x^84 + 1504189919*x^83 + 688315682*x^82 + 1397842239*x^81 + 435187331*x^80 + 433176780*x^79 + 454834357*x^78 + 1046713282*x^77 + 1208458516*x^76 + 811240741*x^75 + 151611952*x^74 + 164192249*x^73 + 353336244*x^72 + 1779538914*x^71 + 1489144873*x^70 + 213140082*x^69 + 1874778522*x^68 + 908618863*x^67 + 1058334731*x^66 + 1706255211*x^65 + 708134837*x^64 + 1382118347*x^63 + 2111915733*x^62 + 1273497300*x^61 + 368639880*x^60 + 1652005004*x^59 + 1977610754*x^58 + 1412680185*x^57 + 2312775720*x^56 + 59793381*x^55 + 1345145822*x^54 + 627534850*x^53 + 2159477761*x^52 + 10450988*x^51 + 1479007796*x^50 + 2082579205*x^49 + 1158447154*x^48 + 126359830*x^47 + 393411272*x^46 + 2343384236*x^45 + 2191577465*x^44 + 1281188680*x^43 + 230049708*x^42 + 539600199*x^41 + 1711135601*x^40 + 1659775448*x^39 + 1716176055*x^38 + 904363231*x^37 + 2385749710*x^36 + 567278351*x^35 + 404199078*x^34 + 372670353*x^33 + 1286079784*x^32 + 1744355671*x^31 + 2316856064*x^30 + 2106475476*x^29 + 614988454*x^28 + 2149964943*x^27 + 1065233185*x^26 + 188130174*x^25 + 540415659*x^24 + 1031409799*x^23 + 1067085678*x^22 + 1005161755*x^21 + 249654085*x^20 + 1816791634*x^19 + 1437500292*x^18 + 448596413*x^17 + 2397497659*x^16 + 2353732701*x^15 + 2068949189*x^14 + 1826419168*x^13 + 1265366199*x^12 + 547031306*x^11 + 1016962374*x^10 + 160089486*x^9 + 2264803979*x^8 + 1081806194*x^7 + 824215340*x^6 + 497731793*x^5 + 45017166*x^4 + 317548920*x^3 + 1391127733*x^2 + 1752881284*x + 1290424106
e=0x10001
q1,q2=N.factor()
q1,q2=q1[0],q2[0]

phi=(p^q1.degree() - 1)*(p^q2.degree() - 1)
assert gcd(e, phi) == 1
d=pow(e, -1, phi)
m=pow(c, d, N)

print(bytes(m.coefficients()))
"""
yolo@Yolo ~/timus> sage exp.sage                                                (sage) 
b'flag{h4v3_y0u_533n_p0lyn0m14l_b453d_r54??}'
"""

unusualrsa4

这个题目的特殊地方是，提供的信息是 inverse(q,p),是 q 在 p 上的模逆元，其余信息正常

必须查看 hint 才能解决问题

Hint1:

ed=1+kφ

  1. 比较 e 与 k 比特位数
  2. 联立两式，尝试化简 (inv(q,p)·φ) mod p

Hint2:

  1. 费马小定理
  2. 对于任意 r,k1,k2，当 k2 为 k1 因子时，r mod k2=(r mod k1) mod k2

这里的 e 和 k 的比特位相近，那么我们可以爆破 k 值，务必从最大值开始爆破，这样可以避免提取不到素数，然后这里还需要考虑下，phi 的大小应该在 2048 上下(p,q 都是 1024bit，p*q 也就是 2048bit 左右了，然后 phi 要更小点)

e = 0x10001
d = 27451162557471435115589774083548548295656504741540442329428952622804866596982747294930359990602468139076296433114830591568558281638895221175730257057177963017177029796952153436494826699802526267315286199047856818119832831065330607262567182123834935483241720327760312585050990828017966534872294866865933062292893033455722786996125448961180665396831710915882697366767203858387536850040283296013681157070419459208544201363726008380145444214578735817521392863391376821427153094146080055636026442795625833039248405951946367504865008639190248509000950429593990524808051779361516918410348680313371657111798761410501793645137
ed_minus_1 = e*d - 1
candidates = []
# 根据 hint：k 与 e 同比特位
upper_bound = 2*e
for k in range(upper_bound, 0, -1):
    if ed_minus_1 % k == 0:
        phi = ed_minus_1 // k
        if 2000 <= phi.bit_length() <= 2048:
            candidates.append((k, phi))

for k, _ in candidates:
    print("k =", k)
"""
yolo@Yolo ~/timus> sage exp.sage                                                                                 (sage)
k = 125352
k = 83568
k = 62676
"""

由于需要 k 和 e 比特位相近，这里应该选取 k=62676 最合适，接下来就是利用公式ed=1+kφ，将φ恢复出来

推导 x

不妨令cf=invert(q,p)，那么我们的已知条件如下

_p=cf=invert(q,p)q⋅cf≡1(modp)ϕ(n)=(p−1)(q−1)=pq−p−q+1\begin{align*} \_p = cf = invert(q, p) \\ q \cdot cf \equiv 1 \pmod p \\ \phi(n) = (p-1)(q-1) = pq - p - q + 1 \end{align*}
  • step1
    phi
ϕ(n)mod  p=(p−1)(q−1)mod  p(p−1)(q−1)=pq−p−q+1pq≡0(modp),−p≡0(modp)⇒ϕ(n)≡−(q−1)(modp)\begin{align*} \phi(n) \mod p = (p-1)(q-1) \mod p \\ (p-1)(q-1) = pq - p - q + 1 \\ pq \equiv 0 \pmod p, \quad -p \equiv 0 \pmod p \\ \Rightarrow \phi(n) \equiv -(q-1) \pmod p \end{align*}
  • step2
    cf
cf⋅ϕ(n)≡cf⋅(−(q−1))=−cf⋅(q−1)(modp)cf \cdot \phi(n) \equiv cf \cdot (-(q-1)) = - cf \cdot (q-1) \pmod p
  • step3
    x，想办法算出 p 的倍数
x=1+cf⋅ϕ(n)−cf⇒x≡1−cf⋅(q−1)−cf=1−cf⋅q(modp)\begin{align*} x = 1 + cf \cdot \phi(n) - cf \\ \Rightarrow x \equiv 1 - cf \cdot (q-1) - cf = 1 - cf \cdot q \pmod p \end{align*}
  • step4
cf⋅q≡1(modp)⇒x≡1−1=0(modp)\begin{align*} cf \cdot q \equiv 1 \pmod p \\ \Rightarrow x \equiv 1 - 1 = 0 \pmod p \end{align*}
  • result
x=1+cf⋅ϕ(n)−cf 是 p 的倍数\boxed{x = 1 + cf \cdot \phi(n) - cf \text{ 是 p 的倍数}}

求解 p

  • 已知条件
x=1+cf⋅ϕ(n)−cfx≡0(modp)x = 1 + cf \cdot \phi(n) - cf \quad x \equiv 0 \pmod p
  • 费马小定理
对于任意整数 r，且 r≢0(modp):rp−1≡1(modp)\begin{align*} \text{对于任意整数 } r \text{，且 } r \not\equiv 0 \pmod p: \\ r^{p-1} \equiv 1 \pmod p \end{align*}
  • 利用定理
rϕ(n)≡1(modp)r^{\phi(n)} \equiv 1 \pmod p
  • 构造 y，这里的 y 是一个可以保证被 p 整除的数(hhh，我傻瓜，刚开始打算 mod p，但是 p 是我们要求的)
y=rϕ(n) mod x−1y = r^{\phi(n)} \bmod x - 1 rϕ(n)≡1(modp)  ⟹  y≡0(modp)r^{\phi(n)} \equiv 1 \pmod p \implies y \equiv 0 \pmod p
  • 用 gcd 提取
取两个不同的 r 值，例如 r1,r2:y1=r1ϕ(n) mod x−1y2=r2ϕ(n) mod x−1p=gcd⁡(y1,y2)\begin{align*} \text{取两个不同的 r 值，例如 } r_1, r_2: \\ y_1 = r_1^{\phi(n)} \bmod x - 1 \\ y_2 = r_2^{\phi(n)} \bmod x - 1 \\ p = \gcd(y_1, y_2) \end{align*}

上述推理的代码实现

e = 0x10001
d = 27451162557471435115589774083548548295656504741540442329428952622804866596982747294930359990602468139076296433114830591568558281638895221175730257057177963017177029796952153436494826699802526267315286199047856818119832831065330607262567182123834935483241720327760312585050990828017966534872294866865933062292893033455722786996125448961180665396831710915882697366767203858387536850040283296013681157070419459208544201363726008380145444214578735817521392863391376821427153094146080055636026442795625833039248405951946367504865008639190248509000950429593990524808051779361516918410348680313371657111798761410501793645137
c=619543409290228183446186073184791934402487500047968659800765382797769750763696880547221266055431306972840980865602729031475343233357485820872268765911041297456664938715949124290204230537793877747551374176167292845717246943780371146830637073310108630812389581197831196039107931968703635129091224513813241403591357678410312272233389708366642638825455844282490676862737715585788829936919637988039113463707959069907015464745700766013573282604376277598510224455044288896809217461295080140187509519005245601483583507547733673523120385089098002298314719617693895392148294399937798485146568296114338393548124451378170302291
k=62676
phi=(e*d-1)//k
cf=113350138578125471637271827037682321496361317426731366252238155037440385105997423113671392038498349668206564266165641194668802966439465128197299073392773586475372002967691512324151673246253769186679521811837698540632534357656221715752733588763108463093085549826122278822507051740839450621887847679420115044512
x=1+cf*phi-cf

r1=5
r2=3
y1=pow(r1,phi,x)-1
y2=pow(r2,phi,x)-1
p=gcd(y1,y2)

print(p)
"""
❯ sage exp.sage
171732509892777162806656543027817624179044398758829371145016435260396582232621695869568991223405812199875059130841499508588172164222373010480535114984619852895214024844343477829378826330105201439334124239909709874526954312203611908068823464475718324350515566693767052582084404828635516115577940913460843090307
"""

既然 p 都求出来了，那么可以直接通过逆元转换，把 q 提取出来,剩下步骤补充到上面的脚本中即可

q=inverse_mod(cf,p)
n=p*q
m=pow(c,d,n)
print(long_to_bytes(int(m)))
#b'flag{wh47_1f_y0u_kn0w_1nv3r7_q_p~?}'

unusualrsa5

仔细观察，这里的 e=0x14=20，挺小的，但是不能使用低指数 RSA 解法，然后观察了 gcd(e,phi)，发现结果刚好是 e=20,然后我们可以这样检测下,可以发现e | p-1 且 e | q-1

if (p-1) % e == 0:
    print("[+] p-1 is divisible by e")
if (q-1) % e == 0:
    print("[+] q-1 is divisible by e")

既然 gcd(e,phi)=20，也就是说 e 和 d 不互素，那么我们就不能利用逆元等定理求解问题了，这里我们需要硬刚 rsa 加密公式 C=m^e (mod n)了，整理下，就是 m^e≡C (mod n)，接下来我们需要强行在模 n 域下对 m^e 开 e 次方(e=20)，根据 n=q*p 以及定理，我可以将模 n 域分解成 p,q 两个素数域，继续开方，预计会有很多项，接下来需要跑嵌套循环，使用 crt 整理，遍历出 flag 对应的解

完整 exp

from Crypto.Util.number import long_to_bytes
e = 0x14
p = 733089589724903586073820965792963746076789390539824437962807679954808310072656817423828613938510684864567664345751164944269489647964227519307980688068059059377123391499328155025962198363435968318689113750910755244276996554328840879221120846257832190569086861774466785101694608744384540722995426474322431441
q = 771182695213910447650732428220054698293987458796864628535794956332865106301119308051373568460701145677164052375651484670636989109023957702790185901445649197004100341656188532246838220216919835415376078688888076677350412398198442910825884505318258393640994788407100699355386681624118606588957344077387058721
n = p * q
c = 406314720119562590605554101860453913891646775958515375190169046313074168423687276987576196367702523895650602252851191274766072774312855212771035294337840170341052016067631007495713764510925931612800335613551752201920460877432379214684677593342046715833439574705829048358675771542989832566579493199671622475225225451781214904100440695928239014046619329247750637911015313431804069312072581674845078940868349474663382442540424342613429896445329365750444298236684237769335405534090013035238333534521759502103604033307768304224154383880727399879024077733935062478113298538634071453067782212909271392163928445051705642
R.<x>=Zmod(p)[] #构建p环上多项式
f=x^e-c
f=f.monic() #这是用来整理多项式的，确保第一项的多项式系数为1
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:
        m=crt(int(i[0]),int(j[0]),p,q)
        flag=long_to_bytes(int(m))
        if b"flag" in flag.lower():
            print("flag:", flag)
            break
"""
❯ sage exp.sage
flag: b'flag{r54__d34l1n6_w17h_3v3n_3 _&_f1nd1n6_n-7h_r0075~~}'
"""

红包四

这个题目很妙，算是那种 Schnorr 签名/验证的题目

审计题目代码，本题的关键信息如下

  • 公钥：y = g^k mod p

  • dododo()

    • t = g^r mod p
s = (r + c*k) mod (p-1)      # c 是自定义的

  • gogogo()

    • g^s ?= t * y^c (mod p)       # c 是服务器随机给的

我们可以发现

  • 在 dododo() 里： g^s = g^{r + c*k} = g^r * (g^k)^c = t * y^c mod p 也就是说，每次 dododo() 都给一条 合法的 Schnorr transcript ： 一对 (t, c, s) ，而且 c 是我们自己选的。

  • r 、 k 都是从 nationalsecret 里 import 进来的， 在每次运行中是固定的，不会变

这个题目的解决思路，出题人已经在 dododo 中给了，在第二轮中，我们需要先自己假设一个r'=randbelow(p-1),可以保证一直使用的 k 是同一个，这样就能算出来合理的 t 值，接下来将 r,c,k,p 代入s=(r+c*k) mod(p-1)即可

94a4e864dc15c3675a2289692c1712f7

exp 如下

from pwn import *
from secrets import randbelow
def egcd(a, b):
    if b == 0: return a, 1, 0
    g, x1, y1 = egcd(b, a % b)
    return g, y1, x1 - (a // b) * y1

def modinv(a, mod):
    a %= mod
    g, x, _ = egcd(a, mod)
    if g != 1: raise ValueError("不存在模逆")
    return x % mod

def recover_k(p, c1, s1, c2, s2):
    mod = p - 1
    dc = (c1 - c2) % mod
    ds = (s1 - s2) % mod
    inv_dc = modinv(dc, mod)
    k = (ds * inv_dc) % mod
    return k
def get_data(c_val):
    io = remote('pwn.challenge.ctf.show', 28193)
    io.recvuntil(b"p = ")
    p = int(io.recvline().strip())
    io.recvuntil(b"t = ")
    t = int(io.recvline().strip())
    io.sendlineafter(b"c = ", str(c_val).encode())
    io.recvuntil(b"s = ")
    s = int(io.recvline().strip())
    return io, p, s

print("第一次连接获取 s1...")
io1, p, s1 = get_data(1)
io1.close()

print("第二次连接获取 s2 并开始挑战...")
io2, p, s2 = get_data(2)

k = recover_k(p, 1, s1, 2, s2)
print(f"k = {k}")
io2.recvuntil(b"Another chance:")

g = 2
r_prime = randbelow(p - 1)
t_new = pow(g, r_prime, p)

print(f"t = {t_new}")
io2.sendlineafter(b"t = ", str(t_new).encode())

io2.recvuntil(b"c = ")
c_new = int(io2.recvline().strip())
print(f"c = {c_new}")
s_new = (r_prime + c_new * k) % (p - 1)
print(f"s = {s_new}")
io2.sendlineafter(b"s = ", str(s_new).encode())
print(io2.recvall(timeout=5).decode())
io2.close()
"""
❯ python exp2.py
第一次连接获取 s1...
[+] Opening connection to pwn.challenge.ctf.show on port 28193: Done
[*] Closed connection to pwn.challenge.ctf.show port 28193
第二次连接获取 s2 并开始挑战...
[+] Opening connection to pwn.challenge.ctf.show on port 28193: Done
k = 2705624984564765868966978366387634364405326655153781810426128366596296442617106894230591261175032719610454635268814651972963281214361478660934331867132842
t = 986431706346513297259217184045670632804964834422049882367897804929798533754894945711252130237557980350690693272687491723773724314709348961868973234738590
c = 3829497968347467440888822108569744588910316079796948631610177595903706612830201728950417149846950945730694055056532152448146720845829616449810376008607345
s = 2203846746804388989168806428353693580717663629416125820026766402879515798020252344093571575954563118019986821343982324446609486502432449852047145907945491
[+] Receiving all data: Done (99B)
[*] Closed connection to pwn.challenge.ctf.show port 28193
FUIYOH! You can get flag: ctfshow{5633ef0f-e05b-458c-811f-0b17e00da08f}

and then go out and play!
"""

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