ISCTF2021 Crypto WP
在reviewctf上面做题，发现isctf2021的crypto的wp很少，然后就用大脑和ai把题目做出来了
最近在攻克rsa,通过这次做题也学到了MT19937,Shamir。
发现数学还得学，下一步先把拉格朗日插值法弄懂。
EasyRsa
n分解为三个素数，phi=(p-1)(q-1)(r-1)
import gmpy2
from libnum import n2s
from Crypto.Util.number import *
e= 65537
c= 31573591986915001857640263466939164206307247748465148395978810720215094970707002043721991055789084518831540652652824225863275289979959264564070907438540016782921324316795681
p= 2514358789
q = 2930880917
r = 10728308687033142242263042720863820844383961098139391476856378846439202568058060175330323889963293720874263174254928466703829537388987357384056877938482683
phi=(p–1)*(q–1)*(r–1)
n=p*q*r
d=gmpy2.invert(e,phi)
m=pow(c,d,n)
print(long_to_bytes(m))
MediumRsa
e,phi不互素
from Crypto.Util.number import *
from gmpy2 import *
p= 135406272915839663948982508259168339196413423033707377351582717408135201161291947411690398070725136534418000750068523816458786100037135542069749803825803176245899663700018918204457909082934286787984577920819722071614325832117549949176386055577917668392717683643933279741971553133044965672217515958006018425207
q= 141499967777554698157827398588073190546048161142442371043319091793202159392937117317909316830021492737369017974252412948824878182004132437165872836769442232191985031274210566004860441962404283572352416239402475111512429494403506484997417885317393735452834730615296387016523054424102807140640940320044291046001
n=p*q
e= 894
c= 285599740642531890154220175592437844999990780403815630307661459001713176317615138628516144325413153232796819897801881107425865913054728954677352027457699314702416360013205027660502210085125607181176890689285963882325311472422689397465349673391413548284592577544566069076266866047930427530566329183924506279416975701558074448835820462125272973167295304050434568652119366359340574659484793805164709585039574539722702352716480226900050322661650017379886614397585534285036799547237613356555628012895080401615470840003601931382810917605930301582006344272146554650976008053460139711071700513559719126632374724028665834623
phi=(p–1)*(q–1)
g=GCD(e//6,phi)
print(GCD(phi,e),g) #6
d=inverse(e//6,phi)
m=pow(c,d,n)
r=gmpy2.iroot(m,6)[0]
print(long_to_bytes(r))
HardRsa1
题目：
from Crypto.Util.number import *
flag=b'****************************'
m1 = bytes_to_long(flag)
N = getPrime(512)*getPrime(512)
e = 19
c1 = pow(m1, e, N)
a = getRandomNBitInteger(512)
b = getRandomNBitInteger(512)
m2 = a*m1 + b
c2 = pow(m2, e, N)
print(N, a, b, c1, c2, sep="\\n")
# N=95587878777633457712771077861034164878218007211732872086703082427025284038734073722525350247252021434969755949232136071401015995927195956787389015816040788670336377590142763231354554070366181264021083507258416574251611662836423194484700341105611819435848709315571900313318932989155213069438624597581376096919
# a=8148274285376731469630646414567940438407613039123927029192149790588715641540606813881834241911738725252707074817442402177237967817804420371483845842902231
# b=9944999010165189354017274928734887652060645960820869672700674403006764312275448509638591901570545531313058741811202384719307206506483462331704719044400878
# c1=1870704366656953386352816295794415188411021228249016204037205250475471490295719163599101603443054766225481004510415813930027376456511655528372027273843117886139717834189065273068836018423957958033253086582500645476025731783186122169863569195566258360470326607481719859396822157309140555156145108464948303484
# c2=73255380295741602810215998117368212335852087176390783730568276178375345944401489472119142216343959193098593837507600341773896221941166940563956033779653381698066185496693623741658031273011213568043342267706206340976896722388323992521780876436269830484416265647861652562217726795508745205674083028929318260061
一开始看到a,b,想到lcg了，但是lcg的seed没那么大
所以使用coppersmith
构造模为n的多项式，然后可以出来
参考了这个：
Franklin-Reiter相关消息攻击-CSDN博客
如果n是素数：
from Crypto.Util.number import long_to_bytes
# 给出的数据
N = 95587878777633457712771077861034164878218007211732872086703082427025284038734073722525350247252021434969755949232136071401015995927195956787389015816040788670336377590142763231354554070366181264021083507258416574251611662836423194484700341105611819435848709315571900313318932989155213069438624597581376096919
a = 8148274285376731469630646414567940438407613039123927029192149790588715641540606813881834241911738725252707074817442402177237967817804420371483845842902231
b = 9944999010165189354017274928734887652060645960820869672700674403006764312275448509638591901570545531313058741811202384719307206506483462331704719044400878
c1 = 1870704366656953386352816295794415188411021228249016204037205250475471490295719163599101603443054766225481004510415813930027376456511655528372027273843117886139717834189065273068836018423957958033253086582500645476025731783186122169863569195566258360470326607481719859396822157309140555156145108464948303484
c2 = 73255380295741602810215998117368212335852087176390783730568276178375345944401489472119142216343959193098593837507600341773896221941166940563956033779653381698066185496693623741658031273011213568043342267706206340976896722388323992521780876436269830484416265647861652562217726795508745205674083028929318260061
e = 19
R.<x> = PolynomialRing(Zmod(N))
f1 = x^e – c1
f2 = (a*x + b)^e – c2
# 计算公因式
g = gcd(f1, f2)
# 提取根：对于一次多项式 A*x + B，根为 -B/A
if g.degree() == 1:
m1 = int(-g[0] / g[1])
print(long_to_bytes(m1))
else:
print("GCD 不为一次多项式，尝试手动提取根：")
print(g)
from sage.all import * # 需要安装 sagemath-standard
from Crypto.Util.number import long_to_bytes
N = 95587878777633457712771077861034164878218007211732872086703082427025284038734073722525350247252021434969755949232136071401015995927195956787389015816040788670336377590142763231354554070366181264021083507258416574251611662836423194484700341105611819435848709315571900313318932989155213069438624597581376096919
a = 8148274285376731469630646414567940438407613039123927029192149790588715641540606813881834241911738725252707074817442402177237967817804420371483845842902231
b = 9944999010165189354017274928734887652060645960820869672700674403006764312275448509638591901570545531313058741811202384719307206506483462331704719044400878
c1 = 1870704366656953386352816295794415188411021228249016204037205250475471490295719163599101603443054766225481004510415813930027376456511655528372027273843117886139717834189065273068836018423957958033253086582500645476025731783186122169863569195566258360470326607481719859396822157309140555156145108464948303484
c2 = 73255380295741602810215998117368212335852087176390783730568276178375345944401489472119142216343959193098593837507600341773896221941166940563956033779653381698066185496693623741658031273011213568043342267706206340976896722388323992521780876436269830484416265647861652562217726795508745205674083028929318260061
e = 19
# 建立多项式环（标准写法）
R = PolynomialRing(Zmod(N), 'x')
x = R.gen()
f1 = x**e – c1
f2 = (a*x + b)**e – c2
g = gcd(f1, f2)
if g.degree() == 1:
coeffs = g.coefficients()
m1 = int(-coeffs[0] / coeffs[1])
print(long_to_bytes(m1))
else:
print("GCD was not linear:", g)
n不是素数，构造gcd
from sage.all import *
import libnum
n = 51296885372346449295388453471330409021784141081351581975478435681552082076338697136130122011636685327781785488670769096434920591920054441921039812310126089859349902066456998315283909435249794317277620588552441456327265553018986591779396701680997794937951231970194353001576159809798153970829987274504038146741
a = 13256631249970000274738888132534852767685499642889351632072622194777502848070957827974250425805779856662241409663031192870528911932663995606616763982320967
b = 12614470377409090738391280373352373943201882741276992121990944593827605866548572392808272414120477304486154096358852845785437999246453926812759725932442170
c1 = 18617698095122597355752178584860764221736156139844401400942959000560180868595058572264330257490645079792321778926462300410653970722619332098601515399526245808718518153518824404167374361098424325296872587362792839831578589407441739040578339310283844080111189381106274103089079702496168766831316853664552253142
c2 = 14091361528414093900688440242152327115109256507133728799758289918462970724109343410464537203689727409590796472177295835710571700501895484300979622506298961999001641059179449655629481072402234965831697915939034769804437452528921599125823412464950939837343822566667533463393026895985173157447434429906021792720
e = 17
def franklinReiter(n, e, c1, c2, a, b):
# 建立模 n 下的多项式环 R[x]
R = PolynomialRing(Zmod(n), 'x')
x = R.gen()
g1 = x ** e – c1
g2 = (a * x + b) ** e – c2
def gcd(g1, g2):
while g2:
g1, g2 = g2, g1 % g2
return g1.monic()
# 返回线性多项式 x + c 的常数项 c 的相反数，即明文 m
return –gcd(g1, g2)[0]
m = franklinReiter(n, e, c1, c2, a, b)
print(libnum.n2s(int(m)))
使用辗转相除法求多项式的最大公因子 在代数中，一个多项式的首项系数通常被称为该多项式的引导系数（leading coefficient），而将多项式变成首项系数为1的形式被称为将多项式化为首一形式（monic form） 调用函数g1.monic()将g1转换为首一多项式（monic polynomial），并返回该多项式。 使用g.monic()[0]，则会返回g(x)除以引导系数后得到的多项式的常数项 比如：g.monic() = x + 32412345 那么：g.monic()[0] = 32412345
HardRsa2
一样
from sage.all import *
import libnum
n = 4204420773617479943564859167286821133009223627804172573263590117785622718525161236597233398439402100826272190957218464786259692632804955516979471884796171
c1 = 2472980534576281392558886476940549411151541741395435035178216067058424274579199860482131340986643214114691172763529231832373323600612645856564185998644266
c2 = 3187049937811823373965320946136219840500070255491222077303817795527750241053576957767965313420456458983759851110615696314773380132732017115202532855996999
e = 3
def franklinReiter(n, e, c1, c2):
# 建立模 n 下的多项式环 R[x]
R = PolynomialRing(Zmod(n), 'x')
x = R.gen()
g1 = x ** e – c1
g2 = (x + 1) ** e – c2
def gcd(g1, g2):
while g2:
g1, g2 = g2, g1 % g2
return g1.monic()
# 返回线性多项式 x + c 的常数项 c 的相反数，即明文 m
return –gcd(g1, g2)[0]
m = franklinReiter(n, e, c1, c2)
print(libnum.n2s(int(m)))
Circular Game
随波逐流：Rot13解码: the password is yunnanuniversity
把kz文件后缀改zip,解压
得到
from Crypto.Util.number import *
from Crypto.PublicKey import RSA
from secret import s, FLAG
def gen_prime(s):
while True:
r = getPrime(s)
R = [r]
t = int(5 * s / 2) + 1
for i in range(0, t):
R.append(r + getRandomRange(0, 4 * s ** 2))
p = reduce(lambda a, b: a * b, R, 2) + 1
if isPrime(p):
if len(bin(p)[2:]) == 1024:
return p
while True:
p = gen_prime(s)
q = gen_prime(s)
n = p * q
e = 65537
d = inverse(e, (p–1)*(q–1))
if len(bin(n)[2:]) == 2048:
break
msg = FLAG
key = RSA.construct((long(n), long(e), long(d), long(p), long(p)))
for _ in xrange(s):
enc = key.encrypt(msg, 0)[0]
msg = enc
print(key.publickey().exportKey())
print('-' * 76)
print(enc.encode('base64'))
print ('-' * 76)
题目在素数生成中作文章，p-1可以被分为许多个大小接近的数字，p-1光滑，使用Pollard's p-1算法
证明见：模数相关攻击 – CTF Wiki
!
from Crypto.Util.number import long_to_bytes
from gmpy2 import powmod, gcd, invert
import base64
n = 21702007965967851183912845012669844623756908507890324243024055496763943595946688940552416734878197459043831494232875785620294668737665396025897150541283087580428261036967329585399916163401369611036124501098728512558174430431806459204349427025717455575024289926516646738721697827263582054632714414433009171634156535642801472435174298248730890036345522414464312932752899972440365978028349224554681969090140541620264972373596402565696085035645624229615500129915303416150964709569033763686335344334340374467597281565279826664494938820964323794098815428802817709142950181265208976166531957235913949338642042322944000000001
e = 65537
# 1. Pollard p-1 分解 n
a = 2
k = 2
while True:
a = powmod(a, k, n) # a = a^k mod n → 指数为 k!
p = gcd(a – 1, n)
if p != 1 and p != n:
break
k += 1
q = n // p
assert p * q == n
print(f"[+] p = {p}")
print(f"[+] q = {q}")
p = 139457081371053313087662621808811891689477698775602541222732432884929677435971504758581219546068100871560676389156360422970589688848020499752936702307974617390996217688749392344211044595211963580524376876607487048719085184308509979502505202804812382023512342185380439620200563119485952705668730322944000000001
q = 155617827023249833340719354421664777126919280716316528121008762838820577123085292134385394346751341309377546683859340593439660968379640585296350265350950535158375685103003837903550191128377455111656903429282868722284520586387794090131818535032744071918282383650099890243578253423157468632973312000000000000001
n = p * q
e = 65537
phi = (p – 1) * (q – 1)
d = pow(e, –1, phi)
c = int.from_bytes(base64.b64decode(open('cipher.txt').read().strip()), 'big')
print(c)
# ── 估算 s（可选，不需要暴力遍历） ──
# p-1 = 2 × r × (r+d₁) × … × (r+dₜ), t = int(5s/2)+1
# (p-1)/2 的非2因子数量 = t+1 = int(5s/2)+2 → s ≈ 2*(count-2)/5
# 这些因子都在 r 附近，最大素因子 ≈ r（s-bit）
from math import gcd
def estimate_s(p_val):
x = p_val – 1
while x % 2 == 0:
x //= 2 # 去掉因子 2
# Pollard rho 分解（p-1 是平滑的，所有素因子 ≤ r+4s²）
def rho(n):
if n == 1: return []
if n % 2 == 0:
return [2] + rho(n // 2)
f = lambda y, c, m: (y*y + c) % m
for c in range(1, 200):
a, b, d = 2, 2, 1
while d == 1:
a, b = f(a, c, n), f(f(b, c, n), c, n)
d = gcd(abs(a – b), n)
if d != n:
return rho(d) + rho(n // d)
return [n] # 素数
factors = sorted(rho(x))
r = factors[–1] # 最大素因子 ≈ r
# count ≈ bit_length(x) / bit_length(r)
count = round(x.bit_length() / r.bit_length())
s = round(2 * (count – 2) / 5)
return s
s_est = estimate_s(p)
print(f'estimated s = {s_est}')
for s in range(1, 51):
m = c
for _ in range(s):
m = pow(m, d, n)
try:
t = m.to_bytes((m.bit_length() + 7) // 8, 'big').decode()
if 'CTF' in t or 'flag' in t:
print(f's={s}: {t}')
break
except:
pass
#ISCTF{Cyc1ic_encrypt10n_4_y0u}
Do_u_know_coding
codex真神了
我感觉有点脑洞
494n4n56453244524n464544475353534q4n5747343644524n5n4q5647544o32495634544o57434n4r563256455253484s464n584153434s47464r46455n3353494q59584o5n4o4r4o424r4755333253494646454q5344594r453q3q3q3q3q3q
import base64
import codecs
s = "494n4n56453244524n464544475353534q4n5747343644524n5n4q5647544o32495634544o57434n4r563256455253484s464n584153434s47464r46455n3353494q59584o5n4o4r4o424r4755333253494646454q5344594r453q3q3q3q3q3q"
# 第 1 层：变体 Base16，n-s 对应 a-f
hex_str = "".join(chr(ord(c) – 13) if "n" <= c <= "s" else c for c in s)
step1 = bytes.fromhex(hex_str).decode()
# 第 2 层：Base32
step2 = base64.b32decode(step1).decode()
# 第 3 层：ROT13
step3 = codecs.decode(step2, "rot_13")
# 第 4 层：Base64
step4 = base64.b64decode(step3 + "=" * ((4 – len(step3) % 4) % 4))
# 第 5 层：Ascii85
flag = base64.a85decode(step4).decode()
print(flag)
ISCTF{W0w_y0u_c4n_rea11y_c0d1ng!}
RdEs
这个还没学喂给ai
import random
from Crypto.Cipher import AES
import base64
def pad(data):
data=data.encode('utf8')
while len(data) % 16 !=0:
data+=b'\\x00'
return data
def jiami(key,m):
mode=AES.MODE_ECB
aes=AES.new(pad(key),mode)
en_m=aes.encrypt(pad(m))
en_m=base64.encodebytes(en_m)
en_m=en_m.decode('utf8')
print(en_m)
with open('output.txt', 'w') as f:
for i in range(624):
f.write(str(random.getrandbits(32)) + "\\n")
f.close()
flag = 'ISCTF{XXXXXXXXXXX}'
key= str(random.getrandbits(32))
jiami(key,flag)
#BYIlzaPnImGZeWVpn+QudBiZEwlaA3H3rl69STD8/tQ=
考察的是MT19937+AES
梅森旋转算法(MT19937)及其逆向详解 – 知乎
1. Python 的随机数生成器：Mersenne Twister (MT19937)
Python random 模块底层使用的是 Mersenne Twister (MT19937) 算法。 它的内部状态由 624 个 32 位无符号整数 组成（外加一个索引位置）。 每次调用 getrandbits(32) 时，生成器会：
- 根据当前状态输出一个新的 32 位随机数；
- 同时更新内部状态（拧转、变换、组合），直到 624 个数全部输出后再进行一次大更新（twist 操作）。
关键性质：只要连续拿到 624 个 32 位输出，就能通过逆变换唯一、完整地恢复出这 624 个内部状态值。这就是著名的“状态克隆”。
2. 题目中的利用过程
题目脚本做了三件事：
因此，output.txt 里保存的 624 个数恰好就是 MT19937 连续的 624 个输出，通过它们可以将生成器状态完全克隆。
所以使用randcrack还原625个随机数，
import base64
from Crypto.Cipher import AES
from randcrack import RandCrack
# 1. 读取 624 个随机数，喂给 RandCrack
rc = RandCrack()
with open('output.txt', 'r') as f:
for _ in range(624):
rc.submit(int(f.readline().strip()))
# 2. 预测下一个 getrandbits(32) 作为密钥
key_int = rc.predict_getrandbits(32)
key = str(key_int)
print(f"[+] 恢复的密钥: {key}")
# 3. 准备密文
enc_b64 = "BYIlzaPnImGZeWVpn+QudBiZEwlaA3H3rl69STD8/tQ="
enc = base64.b64decode(enc_b64)
# 4. 密钥填充（与原脚本完全一致）
def pad(data):
data = data.encode('utf8')
while len(data) % 16 != 0:
data += b'\\x00'
return data
aes = AES.new(pad(key), AES.MODE_ECB)
dec = aes.decrypt(enc)
# 5. 去掉尾部 \\x00 填充
flag = dec.rstrip(b'\\x00').decode('utf8')
print(f"[+] Flag: {flag}")
ISCTF{AE5_AnD_ranD0m}
弯弯曲曲的路
提示里的“5棵树 + 5个银行”按 5 x 5 方阵处理，“上下上下上”“弯弯曲曲的小路”是蛇形路线，“从路的尽头”表示最后要反向/从另一端读。
}I_cFTle_FToneCSWnTC5@0{I
s = "}I_cFTle_FToneCSWnTC5@0{I"
n = 5
grid = [[""] * n for _ in range(n)]
idx = 0
for c in range(n):
rows = range(n) if c % 2 == 0 else range(n – 1, –1, –1)
for r in rows:
grid[r][c] = s[idx]
idx += 1
for row in grid:
print(" ".join(row))
} F T C 5 I _ o T @ _ e n n 0 c l e W { F T C S I
ISCTF{Welc0nne_@To_I5CTF}
鲨米尔
[‘1-12a6bd8768c049913e049a99a707a270’, ‘2-193b4367e502b4881d4ff26443f5c252’, ‘3-1406e4e4c90dbc2df1176fc144339223’, ‘4-309a1fe14e16082b95b12b0a7c111e3’, ‘5-66437ab3c87da186761adb326e9e4191’]
Shamir秘密共享理论基础_shamir secret sharing-CSDN博客
[Crypto学习笔记] shamir共享密钥协议 – 个人主页
方法二：拉格朗日插值法
这是更常用的方法。文章推导了直接代入 x=0 计算秘密S的简化公式：
S = ∑_{i=1}^{t} ( yᵢ · ∏_{j=1, j≠i}^{t} ( xⱼ / (xⱼ – xᵢ) ) )
exp:
"""
Shamir's Secret Sharing – CTF Solution
k is variable (number of shares), use Lagrange interpolation at x=0 to recover f(0) = secret
"""
from fractions import Fraction as F
import math
shares = [
(1, 0x12A6BD8768C049913E049A99A707A270),
(2, 0x193B4367E502B4881D4FF26443F5C252),
(4,0x309a1fe14e16082b95b12b0a7c111e3),
]
# Lagrange interpolation: f(0) = sum(y_i * prod(-x_j / (x_i – x_j)))
n_shares = len(shares)
num, den = 0, 1
for i in range(n_shares):
xi, yi = shares[i]
n, d = yi, 1
for j in range(n_shares):
if i != j:
n *= –shares[j][0]
d *= xi – shares[j][0]
num, den = num * d + n * den, den * d
g = math.gcd(num, den)
num, den = num // g, den // g
secret = num // den
flag = bytes.fromhex(hex(secret)[2:]).decode()
print(flag)
ISCTF{IS5hami2}
