LitCTF2024 Crypto Writeup 详细教学文档

1. Small_e 攻击

题目分析

题目使用了非常小的加密指数e=3，对flag的每个字符单独进行RSA加密。

e = 3
c_list = []
for m in flag:
    c_list.append(pow(ord(m), e, n))

攻击原理

当e很小时，如果明文m的e次方小于模数n，那么直接对密文c开e次方就能恢复明文。

解题步骤

1. 对每个密文c进行直接开立方
2. 将结果转换为对应的ASCII字符

代码实现

import gmpy2
from Crypto.Util.number import *

n = 19041138093915757361446596917618836424321232810490087445558083446664894622882726613154205435993358657711781275735559409274819618824173042980556986038895407758062549819608054613307399838408867855623647751322414190174111523595370113664729594420259754806834656490417292174994337683676504327493103018506242963063671315605427867054873507720342850038307517016687659435974562024973531717274759193577450556292821410388268243304996720337394829726453680432751092955575512372582624694709289019402908986429709116441544332327738968785428501665254894444651547623008530708343210644814773933974042816703834571427534684321229977525229
c_list = [438976, 1157625, 1560896, 300763, 592704, 343000, 1860867, 1771561, 1367631, 1601613, 857375, 1225043, 1331000, 1367631, 1685159, 857375, 1295029, 857375, 1030301, 1442897, 1601613, 140608, 1259712, 857375, 970299, 1601613, 941192, 132651, 857375, 1481544, 1367631, 1367631, 1560896, 857375, 110592, 1061208, 857375, 1331000, 1953125]
e = 3

flag = ''
for i in c_list:
    cc = gmpy2.iroot(i, e)[0]
    flag += chr(cc)
print(flag)

2. Common_primes 攻击

题目分析

两个模数n1和n2共享一个素数因子p。

n1 = p * q1
n2 = p * q2

攻击原理

通过计算gcd(n1, n2)可以找到公共因子p，然后分解n1和n2。

解题步骤

1. 计算p = gcd(n1, n2)
2. 计算q1 = n1 // p
3. 计算私钥d = inverse(e, (p-1)*(q1-1))
4. 解密消息

代码实现

import gmpy2
from Crypto.Util.number import *

n1 = 63306931765261881888912008095340470978772999620205174857271016152744820165330787864800482852578992473814976781143226630412780924144266471891939661312715157811674817013479316983665960087664430205713509995750877665395721635625035356901765881750073584848176491668327836527294900831898083545883834181689919776769
n2 = 73890412251808619164803968217212494551414786402702497903464017254263780569629065810640215252722102084753519255771619560056118922616964068426636691565703046691711267156442562144139650728482437040380743352597966331370286795249123105338283013032779352474246753386108510685224781299865560425114568893879804036573
c1 = 11273036722994861938281568979042367628277071611591846129102291159440871997302324919023708593105900105417528793646809809850626919594099479505740175853342947734943586940152981298688146019253712344529086852083823837309492466840942593843720630113494974454498664328412122979195932862028821524725158358036734514252
c2 = 42478690444030101869094906005321968598060849172551382502632480617775125215522908666432583017311390935937075283150967678500354031213909256982757457592610576392121713817693171520657833496635639026791597219755461854281419207606460025156812307819350960182028395013278964809309982264879773316952047848608898562420
e = 65537

p = gmpy2.gcd(n1, n2)
q1 = n1 // p
d = gmpy2.invert(e, (p-1)*(q1-1))
m = pow(c1, d, n1)
print(long_to_bytes(m))

3. CRT 攻击

题目分析

使用相同的明文m和不同的模数n进行加密，满足中国剩余定理(CRT)的条件。

for i in range(10):
    p = getPrime(1024)
    q = getPrime(1024)
    n = p * q
    c = pow(m, e, n)
    n_list.append(n)
    c_list.append(c)

攻击原理

当e较小且有多组加密时，可以使用中国剩余定理恢复m^e，然后开e次方得到明文。

解题步骤

1. 使用CRT合并所有同余方程
2. 对结果开e次方得到明文

代码实现

from sympy.ntheory.modular import crt
from Crypto.Util.number import *
import gmpy2

n_list = [n1, n2, ..., n10]  # 实际题目中的10个n
c_list = [c1, c2, ..., c10]  # 实际题目中的10个c
e = 10

M = crt(n_list, c_list)[0]
m = gmpy2.iroot(M, e)[0]
print(long_to_bytes(m))

4. Little_Fermat 攻击

题目分析

题目使用了费马小定理的特性，x = p-1满足pow(666666, x, p) == 1。

x = gen_x(p)
assert pow(666666, x, p) == 1
m = m ^ x
c = pow(m, e, n)

攻击原理

根据费马小定理，当a和p互质时，a^(p-1) ≡ 1 mod p。因此x = p-1。

解题步骤

1. 通过n和相邻素数特性找到p和q
2. 计算x = p-1
3. 解密得到m1 = c^d mod n
4. 恢复原始明文m = m1 ^ x

代码实现

from Crypto.Util.number import *
import gmpy2

n = 122719648746679660211272134136414102389555796575857405114496972248651220892565781331814993584484991300852578490929023084395318478514528533234617759712503439058334479192297581245539902950267201362675602085964421659147977335779128546965068649265419736053467523009673037723382969371523663674759921589944204926693
c = 109215817118156917306151535199288935588358410885541150319309172366532983941498151858496142368333375769194040807735053625645757204569614999883828047720427480384683375435683833780686557341909400842874816853528007258975117265789241663068590445878241153205106444357554372566670436865722966668420239234530554168928
e = 65537

# 通过费马分解找到p和q
p = 11077890085511755979659110327492351475443062778113645284455542893506768080495929351346530156720969755021338935044545256776544338408890311881437358607693647
q = 11077890085511755979659110327492351475443062778113645284455542893506768080495929351346530156720969755021338935044545256776544338408890311881437358607694219

d = gmpy2.invert(e, (p-1)*(q-1))
m1 = pow(c, d, n)
x = p - 1
m = m1 ^ x
print(long_to_bytes(m))

5. Polynomial 攻击

题目分析

给出了三个多项式关系，需要解方程找到p, q, r。

Polynomial1 = p**2 + q
Polynomial2 = q**2 + r 
Polynomial3 = r**2 + p

攻击原理

通过多项式关系可以建立关于r的方程，解方程找到r，然后依次求出p和q。

解题步骤

1. 建立关于r的多项式方程
2. 解方程找到r
3. 根据r求出p和q
4. 解密消息

代码实现

# Sage代码
P.<r> = PolynomialRing(RealField(1024))
f = r^4 - 2*P3*r^2 + r + P3^2 - P2
res = f.roots()
r = int(res[0][0])
p = P3 - r**2
q = P1 - p**2
n = p * q * r
d = inverse_mod(e, (p-1)*(q-1)*(r-1))
m = pow(c, d, n)
print(long_to_bytes(int(m)))

6. 真·EasyRSA 攻击

题目分析

模数n = p^4，其中p是256位素数。

p = getPrime(256)
n = p**4
c = pow(m, e, n)

攻击原理

当n = p^k时，可以直接分解n得到p，然后计算欧拉函数φ(n) = p^(k-1)*(p-1)。

解题步骤

1. 对n开四次方得到p
2. 计算φ(n) = p^3*(p-1)
3. 计算私钥d
4. 解密消息

代码实现

from Crypto.Util.number import *
import gmpy2

n = 111880903302112599361822243412777826052651261464069603671228695119729911614927471127031113870129416452329155262786735889603893196627646342615137280714187446627292465966881136599942375394018828846001863354234047074224843640145067337664994314496776439054625605421747689126816804916163793264559188427704647589521
c = 3784701757181065428915597927276042180461070890549646164035543821266506371502690247347168340234933318004928718562990468281285421981157783991138077081303219
e = 65537

p = gmpy2.iroot(n, 4)[0]
phi = p**3 * (p-1)
d = gmpy2.invert(e, phi)
m = pow(c, d, p)  # 因为n=p^4，所以m < p，可以直接模p解密
print(long_to_bytes(m))

7. Small_e_plus 攻击

题目分析

类似Small_e攻击，但e是随机数在1000-2000之间。

e = random.randint(1000, 2000)
c_list = []
for m in flag:
    c_list.append(pow(ord(m), e, n))

攻击原理

通过已知flag格式"LitCTF{"的第一个字符'L'来爆破e。

解题步骤

1. 用'L'的ASCII值爆破e
2. 对每个密文尝试所有可打印字符，找到匹配的明文

代码实现

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

n = 53779688736203933047434881701980151653423802317221115318252054349550528639605402386823698507644560099402835048990108944258111185574422278737617624691459404487383205558495742477348096557609903091073482529108655721238870718736876917084894146112572318162754496404262394399247602930119945411919174294508800616891
c_list = [...]  # 实际题目中的密文列表
e = 65537

flag = ''
m1 = b'L'
m1 = bytes_to_long(m1)
for e in tqdm(range(1000, 2000)):
    if pow(m1, e, n) == c_list[0]:
        print(e)
        break

table = string.printable
for i in c_list:
    c = int(i)
    for m in table:
        if pow(ord(m), e, n) == c:
            flag += m
print(flag)

8. Common_primes_plus 攻击

题目分析

扩展的Common_primes攻击，给出了两个提示hint1和hint2。

hint1 = a*n1 + b*n2
hint2 = c*n1 + d*n2
assert a*c == b*d + 1

攻击原理

通过hint1和hint2的关系可以建立方程，找到n1和n2的关系。

解题步骤

1. 计算k = hint1 * hint2 % n1
2. 计算p = gcd(k, n1)
3. 分解n1
4. 解密消息

代码实现

import gmpy2
from Crypto.Util.number import *

n1 = 72619153900682160072296441595808393095979917106156741746523649725579328293061366133340736822282117284050717527134297532031234706715551253283030119063143935874516054785948327252045453986903379262257406260016876625891582923191913450785482873961282498295762698500898694660964018533698142756095427829906473038053
hint1 = 115150932086321440397498980975794957800400136337062771258224890596200580556053305338941267789684878816176014493153795643655219028833232337281425177163963414534998897852644398384446019097451620742463880027107068960452304016955877225140421899265978792650445328111566277376529454404089066088845864500514742797060500618255170627
hint2 = 166820160267525807953634213157298160399912450930658918773153592459310847514047652216110562360456335336533080444219104489314586122760398361430693763814336759476811490524054588094610387417965626546375189720748660483054863693527537614055954695966458622029711055735399842018236940424665041143785192280089418185085532002136215976
c = 28378912671104261862184597375842174085651209464660064937481961814538145807266472966765374317717522401362019901110151858589886717440587644003368826809403188935808872400614919296641885383025657934630410406898092262104442977722339379234085663757182028529198392480656965957860644395092769333414671609962801212632
e = 65537

kk = hint2 * hint1 % n1
p = gmpy2.gcd(kk, n1)
q = n1 // p
d = inverse(e, (p-1)*(q-1))
m = pow(c, d, n1)
print(long_to_bytes(m))

9. Polynomial_plus 攻击

题目分析

给出了p和q的多项式表达式，需要解方程。

p = k**10 + 22*k**8 + 53*k**6 - 22*k**4 - 39*k**2 + 114514
q = k**9 + 10*k**7 - 13*k**6 - 2*k**4 + 111*k**2 + 1919810
n = p * q

攻击原理

建立关于k的多项式方程，解方程找到k，然后计算p和q。

解题步骤

1. 建立n = p(k)*q(k)的方程
2. 解方程找到k
3. 计算p和q
4. 解密消息

代码实现

# Sage代码
PR.<k> = PolynomialRing(ZZ)
p = k**10 + 22*k**8 + 53*k**6 - 22*k**4 - 39*k**2 + 114514
q = k**9 + 10*k**7 - 13*k**6 - 2*k**4 + 111*k**2 + 1919810
n0 = p * q
f = n - n0
sol = f.roots()
x = sol[0][0]
p = p(x)
q = q(x)
d = inverse_mod(e, (p-1)*(q-1))
m = pow(c, d, n)
print(long_to_bytes(int(m)))

10. CRT_plus 攻击

题目分析

扩展的CRT攻击，加密形式为c = pow(A[i]*m + B[i], e, n)。

for i in range(e):
    c = pow(A[i]*m + B[i], e, n)
    N.append(n)
    C.append(c)

攻击原理

当e较小且有多组加密时，可以使用CRT恢复(A[i]*m + B[i])，然后解线性方程。

解题步骤

1. 对每组密文开e次方
2. 解线性方程恢复m

代码实现

from Crypto.Util.number import *
import gmpy2

A = [126, 48, 16, 72, 118]
B = [1015, 838, 454, 322, 287]
C = [...]  # 实际题目中的密文列表
N = [...]  # 实际题目中的模数列表
e = 5

# 取第一组数据恢复m
c = C[0]
c = gmpy2.iroot(c, e)[0]
res = gmpy2.invert(A[0], N[0])
m = (c - B[0]) * res % N[0]
print(long_to_bytes(m))

11. Mid 攻击 (部分私钥泄露)

题目分析

泄露了p的高位和低位。

leak1 = p >> 924
leak2 = p % (2**500)

攻击原理

使用Coppersmith方法恢复p的中间位。

解题步骤

1. 建立关于p中间位的多项式
2. 使用Coppersmith方法求解
3. 恢复完整的p
4. 分解n并解密

代码实现

# Sage代码
n = 10912724749357317040117295175340915836309117326481842971911576002816136982982366412133127436929465794389631046998036509363047557873155846920275327196471118680559431161116535588318645353317739214770132790445807395653916337747136630775427171105596048281228718048314706544665819996610453587925745842345926654572410324847927833437471701176403031302117052425160845583678182335391697596801106017558494065612842298945201720733418994561321697012416704574891516720606917736854915347853341353358814869449590841870866128113400765492223847582506991200050368263722438854522124807397499067048911261448546634778788867555039834459211
p_high = 749278395841748263310980933893
p_low = 2675756732628494397256285826768672620995252274010849868485475743575097846941007603037228233621038664628877573057336866559545388148568450491606789423985
p_high <<= 924

PR.<x> = PolynomialRing(Zmod(n))
f = p_high + x*2**500 + p_low
f = f.monic()
out_p = f.small_roots(X=2^424, beta=0.4)
p = p_high + out_p[0]*2**500 + p_low
assert n % p == 0
q = n // p
phi = (p-1)*(q-1)
d = inverse_mod(e, phi)
m = pow(c, d, n)
print(long_to_bytes(int(m)))

总结

本教学文档详细分析了LitCTF2024中的各种密码学题目，涵盖了常见的RSA攻击方法：

1. 小指数攻击
2. 共模数攻击
3. 中国剩余定理攻击
4. 费马小定理应用
5. 多项式方程求解
6. 部分密钥泄露攻击
7. Coppersmith方法应用

每种攻击方法都提供了详细的解题步骤和Python/Sage实现代码，帮助读者深入理解各种密码学攻击技术的原理和应用场景。