现代密码¶
RSA 类¶
加密私钥 d¶
话不多说，直接上题（BUUCTF）
from gmpy2 import *
p = 473398607161
q = 4511491
e = 17
phi = (q - 1) * (p - 1)
d = invert(e, phi)
print(d)
Coppersmith 攻击（p 高位泄露）¶
话不多说，直接上题（2024 年楚慧杯湖北省网络与数据安全实践能力竞赛）
from Crypto.Util.number import *
from secret import FLAG
m = bytes_to_long(FLAG)
def getpq(nbit):
p = getPrime(nbit)
q = getPrime(nbit)
if p > q:
return p, q
else:
return q, p
p, q = getpq(512)
P = (p - q) & ((1 << 130) - 1)
n = p * q
leak_p = p >> 256
c = pow((1 + P * n), m, n ** 3)
print('n =', n)
print('leak_p =', leak_p)
print("c =", c)
# n = 135133139540786818977969958456509467902948924003478556140490841984247464940261764739984274397650928404945721248284577232814352745333641188749824519153271662051302477973525156608141358709265683759057060630360909926255299541198485901065352661702656282587105799982740927802530997159098015074633017964344230291287
# leak_p = 115314121469787984258489158421056136177545051135641551928888818017665807264468
# c = 1836794759996264077871820946090708779709415760553736759453665641907562256633157424959089180650539327925671892742819931875681606982615287882656254828326465758462357812873839261469783652663796071814218493268788421243190729887313099383264588659922912876424206670310928514588754069909128149471326084547056385690037197908766053620702238356084124023146075698878494434053246157524775269473152458661801907641122308756667762880284617915774590075511686821816948174618196839335059944389423693187930672934293905608970421003536691336581450927887931599275461176935079227494931457562345640133982771901848553204154760760399724074615092290799119053032875792219794072963200108352944441876206386518960615891547166767499506114294860833404421893612197040731184031783165365621722947731966143226777081983415797778111715332055871302609049501876860012070502369090417942239749695034267695710324328867728296996779
p 高位泄露 256 bit，但是泄露的 bit 不够，我们还需要爆破 8 bit才能 copper 恢复 p
#sage
from tqdm import *
n = 135133139540786818977969958456509467902948924003478556140490841984247464940261764739984274397650928404945721248284577232814352745333641188749824519153271662051302477973525156608141358709265683759057060630360909926255299541198485901065352661702656282587105799982740927802530997159098015074633017964344230291287
p_high = 115314121469787984258489158421056136177545051135641551928888818017665807264468
c = 1836794759996264077871820946090708779709415760553736759453665641907562256633157424959089180650539327925671892742819931875681606982615287882656254828326465758462357812873839261469783652663796071814218493268788421243190729887313099383264588659922912876424206670310928514588754069909128149471326084547056385690037197908766053620702238356084124023146075698878494434053246157524775269473152458661801907641122308756667762880284617915774590075511686821816948174618196839335059944389423693187930672934293905608970421003536691336581450927887931599275461176935079227494931457562345640133982771901848553204154760760399724074615092290799119053032875792219794072963200108352944441876206386518960615891547166767499506114294860833404421893612197040731184031783165365621722947731966143226777081983415797778111715332055871302609049501876860012070502369090417942239749695034267695710324328867728296996779
pbits = 512
for i in trange(2**8, 1, -1):
# 补齐高位，并填充低 8 位
p4 = (p_high << 8) + i
# 计算剩余位数
kbits = pbits - p4.nbits()
# 左移补齐到 512 位
p4 = p4 << kbits
PR.<x> = PolynomialRing(Zmod(n))
f = x + p4
roots = f.small_roots(X = 2^ kbits, beta = 0.4, epsilon = 0.01)
if roots:
p = p4 + int(roots[0])
if n % p == 0:
print(i, p)
break
# i = 197
# p = 13352463043552409670211183534740157814546713901105410408023687926498813469217507846107364405269402732967687839808637375591530105677153038557366731161035343
Coppersmith 攻击（CRT）¶
话不多说，直接上题（2024 年楚慧杯湖北省网络与数据安全实践能力竞赛）
from Crypto.Util.number import *
from gmpy2 import *
import os
flag = b'xxx'
def Mypow(b, e, mod):
a = 1
while e:
e >>= 1
b = (b*b)%mod
if e&1:
a = (a*b)%mod
return a
def Genp(bit_length):
coeff = 2 ** 5 * 3 * 7
while True:
tmp_prime = getRandomNBitInteger(bit_length - 10)
p = coeff * tmp_prime + 1
if is_prime(p):
break
return p
def Genkeys(bit_length):
p,q = Genp(bit_length),Genp(bit_length)
n = p * q
hint = (2 * p + 7 * q) % n
return n, hint
if __name__ == '__main__':
e = next_prime(666)
n, hint = Genkeys(512)
m = bytes_to_long(os.urandom(30) + flag)
ct = Mypow(m,e,n)
print(f'n = {n}')
print(f'hint = {hint}')
print(f'ct = {ct}')
'''
n = 36443283250594259606482132779262570582448178589602577809591307671554949253094255209079689901493052116793388954529442162972106210862341856282788030374324677114528044629385805693771773377070021111949953333360526159026822968061585876873187059674130307295006486032106471182393880915860569773206853864515489855553
hint = 57792516722001523643789088224096258172899052039145876393373730235406451592173971020702024058282699663364267742428240581839287357212741266617791207580236457
ct = 24482128269957355675512496312977308128712253968496848873519792376434347925427116612997489113223781321628516365811583310346553402215907938918891908853234881284620764982626375301219763593402089309909155204943747718536894186749932544428588048770663458669109073657836937287831725958017345747881678942488157429000
'''
\[
\begin{aligned}
&\because\ 2\ *\ p\ +\ 7\ *\ q\\
&\therefore\ 2\ *\ p^2\ +\ 7\ *\ q\ *\ p\\
&\therefore\ p(2p\ +\ 7q)\ =\ p\ *\ hint\\
&\therefore\ f\ =\ 2x^2\ +\ 7n\ -\ x\ *\ hint\\\\
&If\ e \ is\ even\\
&Mypow(b,e,mod)\ =\ pow(m,e,n)\\
&But\ if\ e\ is\ odd\ number\\
&Mypow(b,e,mod)\ =\ pow(m,e-1,n)\\
&\because\ e\ =\ nextprime(666)\\
&\therefore\ e\ is\ odd\ number\\
&\therefore\ e\ =\ next_prime(666)\ -\ 1\\
&\therefore\ gcd(e,phi)\ =\ e\\
\end{aligned}
\]
# 因此演变为有限域下开根问题
# 分别在 GF(p),GF(q) 上开 e 次方根，之后 crt 组合一下，求出所有的 m，再判断字符串中是否含有 DASCTF 即可得到 flag
#sage
import gmpy2
from Crypto.Util.number import *
n = 36443283250594259606482132779262570582448178589602577809591307671554949253094255209079689901493052116793388954529442162972106210862341856282788030374324677114528044629385805693771773377070021111949953333360526159026822968061585876873187059674130307295006486032106471182393880915860569773206853864515489855553
hint = 57792516722001523643789088224096258172899052039145876393373730235406451592173971020702024058282699663364267742428240581839287357212741266617791207580236457
ct = 24482128269957355675512496312977308128712253968496848873519792376434347925427116612997489113223781321628516365811583310346553402215907938918891908853234881284620764982626375301219763593402089309909155204943747718536894186749932544428588048770663458669109073657836937287831725958017345747881678942488157429000
R.<x> = Zmod()[]
f = 2*x^2 + 7*n - hint*x
p = int(f.roots()[0][0])
q = n//p
e = gmpy2.next_prime(666)-1
R.<x> = Zmod(p)[]
f = x^e-ct
f = f.monic()
results1 = f.roots()
R.<x> = Zmod(q)[]
f = x^e-ct
f = f.monic()
results2 = f.roots()
for i in results1:
for j in results2:
param1 = [int(i[0]),int(j[0])]
param2 = [p,q]
m = CRT_list(param1,param2)
flag = long_to_bytes(int(m))
if b'DASCTF' in flag:
print(flag)
break
Coppersmith 攻击（二次剩余）¶
话不多说，直接上题（BUUCTF）
题目代码如下
from sympy import isprime
from sympy.ntheory import legendre_symbol
import random
from Crypto.Util.number import bytes_to_long
k=79 #<-- i couldn't stress more
def get_p():
global k
while True:
r=random.randint(2**69,2**70)
p=2**k*r+1
if isprime(p):
return p
else:
continue
def get_q():
while True:
r=random.randint(2**147,2**148)
q=4*r+3
if isprime(q):
return q
else:
continue
def get_y():
global n,p,q
while True:
y=random.randint(0,n-1)
if legendre_symbol(y,p)==1:
continue
elif legendre_symbol(y,q)==1:
continue
else:
return y
flag=b'DASCTF{redacted:)}'
flag_pieces=[flag[0:10],flag[11:21],flag[22:32],flag[33:43],flag[44:]]
#assert int(bytes_to_long((flag_pieces[i] for i in range(5)))).bit_length()==k
p=get_p()
q=get_q()
n=p*q
print(f'{n=}')
y=get_y()
print(f'{y=}')
def encode(m):
global y,n,k
x = random.randint(1, n - 1)
c=(pow(y,m,n)*pow(x,pow(2,k),n))%n
return c
cs=[]
for i in range(len(flag_pieces)):
ci=encode(bytes_to_long(flag_pieces[i]))
cs.append(ci)
print(f'{cs=}')
'''
n=542799179636839492268900255776759322356188435185061417388485378278779491236741777034539347
y=304439269593920283890993394966761083993573819485737741439790516965458877720153847056020690
cs=[302425991290493703631236053387822220993687940015503176763298104925896002167283079926671604, 439984254328026142169547867847928383533091717170996198781543139431283836994276036750935235, 373508223748617252014658136131733110314734961216630099592116517373981480752966721942060039, 246328010831179104162852852153964748882971698116964204135222670606477985487691371234998588, 351248523787623958259846173184063420603640595997008994436503031978051069643436052471484545]
'''
因为 p = 2 ^ k * r + 1，这个 r 只有 70 位
k = 79
P.<x> = PolynomialRing(Zmod(n))
f = 2^k*x + 1
res = f.monic().small_roots(X=2^70, beta=0.499, epsilon=0.02)
p = int(f(res[0]))
# 628729403897154553626034231171921094272614401
\[
\begin{aligned}
(\frac{y}{p})\ =\ -1,\ (\frac{y}{q})\ =\ -1
\end{aligned}
\]
\[
\begin{aligned}
c\ =\ y^m\ *\ rand^{2^k}\ (mod\ n)
\end{aligned}
\]
由于 rand^2^k 是二次剩余，c 的二次剩余性完全由 y^m 决定
因此，c 的二次剩余性可以直接反映 m 的奇偶性
Jacobi 符号是勒让德符号的推广，用于判断一个数是否是模某个奇数的二次剩余
n = q * p，而 p 和 q 都是素数，因此可以使用 Jacobi 符号来判断 c 是否是模 p 或 q 的二次剩余
通过 Jacobi 符号判断 m 的当前二进制位（0 或 1）
如果是 1 则更新并继续递归
如果是 0，则直接对 c 开平方根，继续递归
当恢复的二进制位长度达到 k = 79 时，递归结束，输出恢复的 m
虽然 c 是模 n 的，但 Jacobi 符号只能用于模素数
因此，需要选择一个因子（如 p）来计算 Jacobi 符号
在模 p 的情况下，方程 x^2 = c (mod p) 有两个解
因此，每次开平方根后，需要递归遍历两个可能的根
from gmpy2 import jacobi,invert
def rabin(c):
P.<x> = PolynomialRing(GF(p))
f1 = x^2 - c
resp = f1.roots()
return [int(i[0]) for i in resp]
def getm(c,m):
global ok,flag
if ok: return
if len(m)>=k:
print('OK',m, long_to_bytes(int(m,2)))
flag += long_to_bytes(int(m,2))
ok = True
return
if jacobi(c, p) == -1:
m = '1'+m
c = int(c*invert(y,p)%p)
else:
m = '0'+m
cs = rabin(c)
for tc in cs:
getm(int(tc),m)
flag = b''
for tc in cs:
ok = False
getm(tc,'')
print(flag)
#DASCTF{go0_j06!let1sm0v31n_t0_th3r_chanlenges~>_<}
费马小定理（离散数学）¶
话不多说，直接上题（BUUCTF）
from Crypto.Util.number import bytes_to_long, getPrime
from sympy import nextprime, gcd
from random import randint
from CustomNiBoLan import get_pDNF, get_pCNF
from secret import flag, random_proposition
import sys
class Godel:
def __init__(self):
self.table = ['﹁', '∨', '∧', '→', '↔', 's', '(', ')', 'p', 'q', 'r', 't']
self.dict = self.generate_dict()
def generate_dict(self, max_value=30):
res = {}
used = set()
for k in self.table:
while True:
r = randint(1, max_value)
if r not in used:
res[k] = r
used.add(r)
break
return res
def generate_primes(self, count, start=2):
primes = []
tmp = start
while len(primes) < count:
primes.append(tmp)
tmp = nextprime(tmp)
return primes
# zip(seq, p) 将序列 seq 和素数列表 p 组合成一个可迭代的对象，每次迭代返回一个元组 (c, prime)，其中 c 是 seq 中的元素，prime 是 p 中对应的素数
def translate(self, seq):
p = self.generate_primes(len(seq))
gn = 1
for c, prime in zip(seq, p):
gn *= prime ** self.dict[c]
return gn
def encrypt(para):
p = nextprime(para)
q = getPrime(512)
e = 65537
n = p * q
m = bytes_to_long(flag)
c = pow(m, e, n)
return c, n
if __name__ == '__main__':
g = Godel()
plaint = input("请输入命题，例p∧q（最多四个变量）：")
conj = get_pCNF(plaint)
disj = get_pDNF(plaint)
reslist = [g.translate(conj), g.translate(disj)]
p = g.translate(random_proposition)
c, n = encrypt(p)
print(random_proposition)
print(f'c: {c}')
print(f'n: {n}')
print(f'tip: {gcd(*reslist)}')
1. 基本概念：布尔逻辑和命题公式
- **命题：**是一个陈述，可以为真（True）或假（False），例如，“今天是星期一”是一个命题
- **命题变量：**通常用字母表示命题，例如 A、B、C 等，每个变量都可以是 True 或 False
布尔逻辑中的基本运算包括
- 与（AND），记作 ∧，表示两个命题同时为真时结果才为真
- 或（OR），记作 ∨，表示至少有一个命题为真时结果为真
- 非（NOT），记作 ¬，表示对命题取反，即真变假，假变真
例如：
- A∧B 只有当 A 和 B 都为真时才为真
- A∨B 只要 A 或 B 其中一个为真，整个表达式就为真
- ¬A 是对命题 A 的取反
2. CNF（合取范式）
合取范式（CNF）是指将一个命题公式转化为一种特定形式，使得整个公式由多个子公式通过“与”（AND）连接组成，并且每个子公式内部是由多个命题变量通过“或”（OR）连接的形式
- **字句：**一个字句是由命题变量或其否定通过“或”连接的表达式。比如，A∨B 或 ¬A∨C∨D 都是字句
- **合取：**就是多个字句通过“与”连接，比如，(A∨B)∧(¬C∨D∨E) 就是一个合取
3. DNF（析取范式）
析取范式（DNF）是指将一个命题公式转化为一种特定形式，使得整个公式由多个子公式通过“或”（OR）连接组成，并且每个子公式内部是由多个命题变量通过“与”（AND）连接的形式
- **合取：**在 DNF 中，子公式内部是通过“与”连接的命题变量。
- **析取：**就是多个合取子公式通过“或”连接。比如，(A∧¬B)∨(C∧D)∨(E∧F) 都是合取，多个合取通过“或”连接就成了析取
首先分析程序逻辑：
-
接受输入后调用
translate方法将每个符号对应的素数进行幂运算，然后将所有结果相乘 -
调用
random_proposition方法生成一个随机命题，并将其转换为整数p -
使用
p作为参数调用encrypt函数进行加密 -
最后，程序输出加密后的密文
c、模数n以及reslist中两个整数的最大公约数（GCD）作为提示
由于 p 是通过 nextprime(para) 生成的，而 para 是 translate 的结果
其方法内部又调用了 generate_primes 从 2 生成连续素数列表
通过构造一个的数 t 为这些素数的幂的乘积，使得 t 是 p-1 的倍数（足够大的指数如 150），从而利用 费马小定理 分解 n
\[
\begin{aligned}
&a^{p-1}\ =\ 1\ (mod\ p)\\
&a^{k(p-1)}\ =\ 1^k\ (mod\ p)
\end{aligned}
\]
from Crypto.Util.number import *
from sympy import nextprime
from pwn import *
t = 1
a = 2
for i in range(20):
t *= a**150
a = nextprime(a)
while(1):
sh = remote("node5.buuoj.cn",28758)
sh.sendline("p".encode('utf-8'))
sh.recvuntil(b"random_pro: ")
random_pro = sh.recvline().decode('utf-8')
print("random_pro", random_pro)
sh.recvuntil(b"c: ")
c = int(sh.recvline().strip().decode())
print("c", c)
sh.recvuntil(b"n: ")
n = int(sh.recvline().strip().decode())
print("n", n)
sh.recvuntil(b"tip: ")
tip = int(sh.recvline().strip().decode())
print("tip", tip)
# 如果结果既不是 1 也不是 n，则说明找到了 n 的一个非平凡因子 p
if(GCD(pow(2,t,n)-1,n) != 1 and GCD(pow(2,t,n)-1,n) != n):
p = GCD(pow(2,t,n)-1,n)
q = n // p
phi = (p-1)*(q-1)
d = inverse(65537,phi)
print(long_to_bytes(pow(c,d,n)))
exit()
sh.close()
拿到 flag
共模攻击（相同 n）¶
话不多说，直接上题（攻防世界）
先从两个公钥文件中提取公钥信息
from Crypto.PublicKey import RSA
f1 = open("F:\\ChromeCommon\\c2d6e7158d7b4cd6a747774f0bdc5f72\\publickey1.pem","rb").read()
f2 = open("F:\\ChromeCommon\\c2d6e7158d7b4cd6a747774f0bdc5f72\\publickey2.pem","rb").read()
pub1 = RSA.importKey(f1)
pub2 = RSA.importKey(f2)
n1 = pub1.n
e1 = pub1.e
n2 = pub2.n
e2 = pub2.e
print(n1)
print(n2)
print(e1)
print(e2)
n1 = 13060424286033164731705267935214411273739909173486948413518022752305313862238166593214772698793487761875251030423516993519714215306808677724104692474199215119387725741906071553437840256786220484582884693286140537492541093086953005486704542435188521724013251087887351409946184501295224744819621937322469140771245380081663560150133162692174498642474588168444167533621259824640599530052827878558481036155222733986179487577693360697390152370901746112653758338456083440878726007229307830037808681050302990411238666727608253452573696904083133866093791985565118032742893247076947480766837941319251901579605233916076425572961
n2 = 13060424286033164731705267935214411273739909173486948413518022752305313862238166593214772698793487761875251030423516993519714215306808677724104692474199215119387725741906071553437840256786220484582884693286140537492541093086953005486704542435188521724013251087887351409946184501295224744819621937322469140771245380081663560150133162692174498642474588168444167533621259824640599530052827878558481036155222733986179487577693360697390152370901746112653758338456083440878726007229307830037808681050302990411238666727608253452573696904083133866093791985565118032742893247076947480766837941319251901579605233916076425572961
e1 = 117
e2 = 65537
发现 n1 == n2，采用共模攻击
由于 e₁ 和 e₂ 互质，可以找到整数 s 和 t 使得
如果 s 为正数
如果 s 为负数
from Crypto.Util.number import long_to_bytes, bytes_to_long
from Crypto.PublicKey import RSA
from gmpy2 import gcd, invert
def extended_gcd(a, b):
"""扩展欧几里得算法，返回(g, x, y)使得ax + by = g = gcd(a, b)"""
if a == 0:
return b, 0, 1
else:
g, y, x = extended_gcd(b % a, a)
return g, x - (b // a) * y, y
# 读取第一个公钥
with open('pic/publickey1.pem', 'rb') as f:
pub1 = RSA.importKey(f.read())
n = pub1.n
e1 = pub1.e
# 读取第二个公钥
with open('pic/publickey2.pem', 'rb') as f:
pub2 = RSA.importKey(f.read())
e2 = pub2.e
# 验证两个公钥使用相同的模数
if pub1.n != pub2.n:
raise ValueError("两个公钥必须使用相同的模数n")
# 读取密文
with open('pic/cipher1.txt', 'rb') as f:
c1 = bytes_to_long(f.read())
with open('pic/cipher2.txt', 'rb') as f:
c2 = bytes_to_long(f.read())
# 计算扩展欧几里得系数
g, s1, s2 = extended_gcd(e1, e2)
# 确保 gcd(e1, e2) = 1
if g != 1:
raise ValueError("指数 e1 和 e2 必须互质")
# 处理负指数情况
if s1 < 0:
s1 = -s1
c1 = invert(c1, n)
elif s2 < 0:
s2 = -s2
c2 = invert(c2, n)
# 计算明文: m = (c1^s1 * c2^s2) mod n
m = pow(c1, s1, n) * pow(c2, s2, n) % n
# 输出结果
print("Recovered message:", long_to_bytes(m).decode())
公共 p（n 均不相同）¶
话不多说，直接上题（攻防世界）
打开附件
给定两个不同的 n 的时候一定要看看 n1，n2 有没有最大公约数（素数）
如果有，那么该最大公约数就是两者共同的 p
import gmpy2, libnum
from Crypto.Util.number import long_to_bytes
# 用于求解a和b的最大公约数
def get_p(a, b):
p = gmpy2.gcd(a, b)
return p
if __name__ == '__main__':
n1 = 23220619839642624127208804329329079289273497927351564011985292026254914394833691542552890810511751239656361686073628273309390314881604580204429708461587512500636158161303419916259271078173864800267063540526943181173708108324471815782985626723198144643256432774984884880698594364583949485749575467318173034467846143380574145455195152793742611717169602237969286580028662721065495380192815175057945420182742366791661416822623915523868590710387635935179876275147056396018527260488459333051132720558953142984038635223793992651637708150494964785475065404568844039983381403909341302098773533325080910057845573898984314246089
c1 = 9700614748413503291260966231863562117502096284616216707445276355274869086619796527618473213422509996843430296526594113572675840559345077344419098900818709577642324900405582499683604786981144099878021784567540654040833912063141709913653416394888766281465200682852378794478801329251224801006820925858507273130504236563822120838520746270280731121442839412258397191963036040553539697846535038841541209050503061001070909725806574230090246041891486506980939294245537252610944799573920844235221096956391095716111629998594075762507345430945523492775915790828078000453705320783486744734994213028476446922815870053311973844961
n2 = 22642739016943309717184794898017950186520467348317322177556419830195164079827782890660385734113396507640392461790899249329899658620250506845740531699023854206947331021605746078358967885852989786535093914459120629747240179425838485974008209140597947135295304382318570454491064938082423309363452665886141604328435366646426917928023608108470382196753292656828513681562077468846105122812084765257799070754405638149508107463233633350462138751758913036373169668828888213323429656344812014480962916088695910177763839393954730732312224100718431146133548897031060554005592930347226526561939922660855047026581292571487960929911
c2 = 20513108670823938405207629835395350087127287494963553421797351726233221750526355985253069487753150978011340115173042210284965521215128799369083065796356395285905154260709263197195828765397189267866348946188652752076472172155755940282615212228370367042435203584159326078238921502151083768908742480756781277358357734545694917591921150127540286087770229112383605858821811640935475859936319249757754722093551370392083736485637225052738864742947137890363135709796410008845576985297696922681043649916650599349320818901512835007050425460872675857974069927846620905981374869166202896905600343223640296138423898703137236463508
e = 65537
# 拿到共同的p，再分别求出各自的素数q
p = get_p(n1, n2)
q1 = n1 // p
q2 = n2 // p
# 求私钥d，另外gmpy2.invert()函数和libnum.invmod()函数等价
d1 = libnum.invmod(e, (p - 1) * (q1 - 1))
d2 = libnum.invmod(e, (p - 1) * (q2 - 1))
# 将密文c用私钥d解密成明文
m1 = gmpy2.powmod(c1, d1, n1)
m2 = gmpy2.powmod(c2, d2, n2)
# 将明文转字符
message = long_to_bytes(m1) + long_to_bytes(m2)
print(message.decode())
Yafu 因式分解（n 过小分解出多个 p）¶
话不多说，直接上题（攻防世界）
给出一串代码，大概看一眼是类似 RSA 的加密算法
但是其 n 的选取并非 2 个素数的乘积，而是 5 个素数的乘积，所以并不是标准的 RSA 加密
import libnum
from Crypto.Util import number
from functools import reduce
from secret import flag
n = 5
size = 64
while True:
ps = [number.getPrime(size) for _ in range(n)]
if len(set(ps)) == n:
break
e = 65537
n = reduce(lambda x, y: x*y, ps)
m = libnum.s2n(flag)
c = pow(m, e, n)
print('n = %d' % n)
print('c = %d' % c)
n = 175797137276517400024170861198192089021253920489351812147043687817076482376379806063372376015921
c = 144009221781172353636339988896910912047726260759108847257566019412382083853598735817869933202168
下载 Yafu，先熟悉下命令
如果因数过长，将因数用文本文件存放在 yafu 目录下
文件最后一行一定要换行，否则 eof; done processing batchfile
这里我们就成功拿到了五个 p
解密算法与 RSA 解密类似，只是 phi 要变为多个（素数-1）的乘积
再利用 e 和 phi 求解逆元 d，最后解密即可
from Crypto.Util.number import long_to_bytes,bytes_to_long,inverse
c = 144009221781172353636339988896910912047726260759108847257566019412382083853598735817869933202168
n = 175797137276517400024170861198192089021253920489351812147043687817076482376379806063372376015921
e = 65537
p1 = 9401433281508038261
p2 = 11855687732085186571
p3 = 13716847112310466417
p4 = 11215197893925590897
p5 = 10252499084912054759
phi = (p1-1)*(p2-1)*(p3-1)*(p4-1)*(p5-1)
d = inverse(e, phi)
m = pow(c, d, n)
print(long_to_bytes(m))
RSA 私钥恢复¶
话不多说，直接上题（攻防世界）
下载附件只给了私钥下半部分
Os9mhOQRdqW2cwVrnNI72DLcAXpXUJ1HGwJBANWiJcDUGxZpnERxVw7s0913WXNtV4GqdxCzG0pG5EHThtoTRbyX0aqRP4U/hQ9tRoSoDmBn+3HPITsnbCy67VkCQBM4xZPTtUKM6Xi+16VTUnFVs9E4rqwIQCDAxn9UuVMBXlX2Cl0xOGUF4C5hItrX2woF7LVS5EizR63CyRcPovMCQQDVyNbcWD7N88MhZjujKuSrHJot7WcCaRmTGEIJ6TkU8NWt9BVjR4jVkZ2EqNd0KZWdQPukeynPcLlDEkIXyaQx
先转为十六进制
3acf6684e41176a5b673056b9cd23bd832dc017a57509d471b024100d5a225c0d41b16699c4471570eecd3dd7759736d5781aa7710b31b4a46e441d386da1345bc97d1aa913f853f850f6d4684a80e6067fb71cf213b276c2cbaed5902401338c593d3b5428ce978bed7a553527155b3d138aeac084020c0c67f54b953015e55f60a5d31386505e02e6122dad7db0a05ecb552e448b347adc2c9170fa2f3024100d5c8d6dc583ecdf3c321663ba32ae4ab1c9a2ded6702691993184209e93914f0d5adf415634788d5919d84a8d77429959d40fba47b29cf70b943124217c9a431
根据 OpenSSL 私钥结构，私钥信息按如下顺序排列：
其中：
x1 = d mod (p-1)x2 = d mod (q-1)x3 = p^(-1) mod q
从解码后的数据中，我们可以识别出三个关键参数（以0241标签头标识）：
- x1 = d mod (p-1)
00d5a225c0d41b16699c4471570eecd3dd7759736d5781aa7710b31b4a46e441d386da1345bc97d1aa913f853f850f6d4684a80e6067fb71cf213b276c2cbaed59
- x2 = d mod (q-1)
1338c593d3b5428ce978bed7a553527155b3d138aeac084020c0c67f54b953015e55f60a5d31386505e02e6122dad7db0a05ecb552e448b347adc2c9170fa2f3
- (q-1) mod p
00d5c8d6dc583ecdf3c321663ba32ae4ab1c9a2ded6702691993184209e93914f0d5adf415634788d5919d84a8d77429959d40fba47b29cf70b943124217c9a431
根据 RSA 私钥的性质，我们知道：
由此可以推导出：
由于 x1 和 x2 的定义，可以得到：
因此：
设：
由于x1 = d mod (p-1)，则 x1 < (p-1)，可以近似认为 x1·e ≈ r1·(p-1)，因此 r1 < e；同理 r2 < e
我们可以假设 e=65537，然后尝试找出 r1 和 r2
import gmpy2
import rsa
from Crypto.Util.number import isPrime
x1 = "0xd5a225c0d41b16699c4471570eecd3dd7759736d5781aa7710b31b4a46e441d386da1345bc97d1aa913f853f850f6d4684a80e6067fb71cf213b276c2cbaed59"
x2 = "0x1338c593d3b5428ce978bed7a553527155b3d138aeac084020c0c67f54b953015e55f60a5d31386505e02e6122dad7db0a05ecb552e448b347adc2c9170fa2f3"
x3 = "0xd5c8d6dc583ecdf3c321663ba32ae4ab1c9a2ded6702691993184209e93914f0d5adf415634788d5919d84a8d77429959d40fba47b29cf70b943124217c9a431"
x1 = int(x1, 16)
x2 = int(x2, 16)
x3 = int(x3, 16)
def genKey(X1, X2):
e = 65537
N1 = X1 * e - 1
N2 = X2 * e - 1
# 寻找 p
for r in range(e):
if N1 % (e - r) == 0:
p = int(N1 // (e - r) + 1
if isPrime(p):
print("r1 =", r)
break
# 寻找 q
for r in range(e):
if N2 % (e - r) == 0:
q = int(N2 // (e - r) + 1
if isPrime(q):
print("r2 =", r)
break
n = p * q
phi = (p - 1) * (q - 1)
d = int(gmpy2.invert(e, phi))
# 验证 x3 是否正确
assert gmpy2.invert(q, p) == x3
privatekey = rsa.PrivateKey(n, e, d, p, q)
with open("flag.enc", "rb") as f:
print(rsa.decrypt(f.read(), privatekey).decode())
genKey(x1, x2)
离散对数（g^m ≡ c mod p）¶
话不多说，直接上题（青少年 CTF 练习平台）
下载附件
这实际上是一个**离散对数问题**（Discrete Logarithm Problem, DLP）：给定 g, p, c，求 m 使得 g^m ≡ c mod p
from Crypto.Util.number import *
from random import *
flag=b'key{xxxxxxx}'
m=bytes_to_long(flag)
p=3006156660704242356836102321001016782090189571028526298055526061772989406357037170723984497344618257575827271367883545096587962708266010793826346841303043716776726799898939374985320242033037
g=3
c=pow(g,m,p)
print(f'c=',c)
#c=2806010417151035336440705514162974780232947158398198485734192667226413654468071006789004899454166950916976496577445879600303537754602011941433695536703970095800594654040421871366147069319806
使用 discrete_log 函数求解离散对数问题：找到 m 使得 g^m ≡ c mod p
Mod(c, p)表示c在模p下的剩余类Mod(g, p)表示g在模p下的剩余类discrete_log函数会返回满足g^m ≡ c mod p的m
# sage
from Crypto.Util.number import *
p = 3006156660704242356836102321001016782090189571028526298055526061772989406357037170723984497344618257575827271367883545096587962708266010793826346841303043716776726799898939374985320242033037
c = 2806010417151035336440705514162974780232947158398198485734192667226413654468071006789004899454166950916976496577445879600303537754602011941433695536703970095800594654040421871366147069319806
g = 3
flag = discrete_log(Mod(c,p),Mod(g,p))
print(long_to_bytes(flag))
Lattice 求解模数 n（存在小量 ，提供多个方程组参数）¶
话不多说，直接上题（青少年 CTF 练习平台）
from Crypto.Util.number import *
from secret import flag
import random
import gmpy2
def generate_Key1(ebits):
e = [getPrime(ebits) for _ in range(4)]
return e
def encrypt1(message,e):
n = gmpy2.next_prime(bytes_to_long(message) << 300)
m = getPrime(256)
c = [int(pow(m,e[i],n)) for i in range(len(e))]
return c
def generate_Key2(nbits):
p = getPrime(nbits // 2)
q = getPrime(nbits // 2)
n = p*q
e = [random.getrandbits(nbits // 4) for _ in range(3)]
return n,e
def encrypt2(message,e,n):
m = bytes_to_long(message)
c = [int(pow(m,e[i],n)) for i in range(len(e))]
return c
assert flag.startswith(b"DRKCTF{")
flag1 = flag[:len(flag)//2]
flag2 = flag[len(flag)//2:]
ebits = 7
e1 = generate_Key1(ebits)
cipher1 = encrypt1(flag1,e1)
print("e1 =",e1)
print("cipher1 =",cipher1)
nbits = 1024
n,e2 = generate_Key2(nbits)
cipher2 = encrypt2(flag2,e2,n)
print("e2 =",e2)
print("cipher2 =",cipher2)
print("n =",n)
"""
e1 = [109, 71, 109, 73]
cipher1 = [36272047346364825234770733058042613197790911431212158822254782055957208837848605160852567043492625692783344073921185227328379941291979083011033, 13421582077901767047291741873622169312010984740586925881415103229648835151589774736786336965745532072099996467445790339749720696886313635920080, 36272047346364825234770733058042613197790911431212158822254782055957208837848605160852567043492625692783344073921185227328379941291979083011033, 41425183140413487232780768389488969603566343428250573532166425276868000949579663990819005141199597640625439816343697426958648927294289659127871]
e2 = [79572758141493570128961125255246129069540961757778793209698370333142346488381, 80555585862127636800866563977080055603517001358195529410497461746213789997225, 44651921320695090688745333790065512192118202496468714141526113242887125432380]
cipher2 = [58600444300331800249882073146233995912287198739549440714207984476331259754331716531491187240053630185776787152600165426285021284302994699108557023545574315706006132536588848833818758624067461985444940651823107522770906474037882323326792755635934081822967331031854184791299228513024491344725765476710816941057, 16511944800191885973496391252612222059697387587833308714567450121364756390806094606646424594583975159634952911600665271092389815248477961923357683297311169260578508157717777465241680062644118354471550223231057620392252324514411927096940875466794869671163453991620492008856178108060167556176019729800517994337, 80885008609388989196377721090246742575908473911131498982960117640742106565184297197238656375198284856442596226398287448931285735903463892735111244609358611618958293002176923706195402338331128766464276441210238388187625107435781170368017908610916585774514676482124401329575553658828115269495158818527164441546]
n = 93468142044831350317940409833603031534515663349871776634867176846669780024082517910566484997161088199091160371537367121403194814422867749777235397168852158723228851090445429617275680206703935781244466363279841409768649097588586494453125840436600639420286950914680651600232197982546122764845043227394567787283
"""
两段 flag，先看第一段，参考文章脚本
一个 64 bit的小量 m，依次产生 20 个 128 bit的素数对其进行类似 RSA 的加密，并且给了我们加密指数的列表以及密文的列表
题目满足两个经典条件：存在小量，提供多个方程组参数
这样的问题在很多 crypto 题目中都是用格方法求解的，所以要想到利用格方法（题目的名字虽然说得很明白，但是如果没有，看到这种形式也应该联想到这个方法）
注意到 m 不变，模数 n 也不变，同时加密指数互素，这其实很像共模攻击的情景，只是 n 未知
回想一下在已知模数 n 的情况下共模攻击的实施方法，不难产生下面这个解题思路
取 20 个方程的前三个如下：
\[
\begin{aligned}
&out1\ =\ m^{e1}\ (mod\ n)\\\\
&out2\ =\ m^{e2}\ (mod\ n)\\\\
&out3\ =\ m^{e3}\ (mod\ n)\\\\
\end{aligned}
\]
\[
\begin{aligned}
&a\ *\ e1\ +\ b\ *\ e2\ =\ 1
\end{aligned}
\]
\[
\begin{aligned}
&out1^a\ *\ out2^b\ \equiv\ m^{a\ *\ e1\ +\ b\ *\ e2}\ \equiv\ m\ (mod\ n)
\end{aligned}
\]
\[
\begin{aligned}
&out1^a\ *\ out2^b\ \equiv\ m\ (mod\ n)\ \ \ \ \ \ \ \ \ --1\\\\
&out1^c\ *\ out2^d\ \equiv\ m\ (mod\ n)\ \ \ \ \ \ \ \ \ --2\\\\
&out1^f\ *\ out2^g\ \equiv\ m\ (mod\ n)\ \ \ \ \ \ \ \ \ --3\\\\
\end{aligned}
\]
\[
\begin{aligned}
&out1^a\ *\ out2^b\ -\ out2^c\ *\ out3^d\ \equiv\ 0\ (mod\ n)\\\\
&out1^f\ *\ out2^g\ -\ out2^c\ *\ out3^d\ \equiv\ 0\ (mod\ n)\\\\
\end{aligned}
\]
而现在等式左侧已经没有未知量了（a,b,c,d,f,g 均能够通过扩展欧几里得求出），那么就可以求解他们的 gcd 得到 n
可以说，想到这个思路的时候我为之一振，可惜实际操作的时候这个方法并不能实施，原因也很简单，我们进行的并非模幂运算，而是普通幂运算，并且 a，b 这些指数数量级很大（注意这一点），所以是完全没有办法照这个思路解下去的
这时候我也没有想到怎么利用格，所以进度也停滞了，一卡卡到了晚上
晚上我反复思考的时候，又想到了我刚刚说的那一点，也就是实施不了共模攻击的原因，在于指数的数量级很大，没有办法幂运算
我也突然联想到了 Lattic e中 LLL 算法的重要应用——求解最短向量
那么一切也就说得通了，之所以给 20 个素数作为加密指数，就是可以应用于格密码中，克服刚才共模攻击中两两组合时计算出的 a，b 过大的问题。所以构造格的思路就来了：
因为 20 个指数 e 均互素，所以一定存在 a1，a2，a3…a20，使得
\[
\begin{aligned}
&a1\ *\ e1\ +\ a2\ *\ e2\ +\ a3\ *\ e3\ +……a20\ *\ e20\ =\ 1
\end{aligned}
\]
\[
\begin{aligned}
&[a1\ a2\ a3……a20]\ *\ []\ =\ [1\ a1\ a2……a20]
\end{aligned}
\]
[ 45 -58 5 -16 12 -7 -27 19 6 14 29 -23 -36 44 -15 1 8 14 -7 11 -9]
[-14 -27 20 6 -40 20 -34 -2 -16 51 35 -23 -51 13 3 -21 0 17 11 -7 1]
[ 15 -36 -21 -13 6 -7 -1 -59 -23 42 -33 15 -30 -4 39 26 41 1 19 10 9]
[-23 4 49 -19 22 -9 24 -20 -20 3 -24 4 -43 -86 40 44 -1 -1 26 25 1]
[ 72 15 -11 -19 26 -31 -56 -25 5 33 -27 -23 12 22 11 -1 21 -17 51 -31 9]
[-35 -73 -8 19 -29 23 -3 20 -10 18 46 29 -9 69 -30 9 -64 13 10 -26 3]
[ 20 46 12 -3 28 -1 -68 15 3 -21 -48 -20 43 54 9 14 -5 0 -44 -24 8]
[ 49 0 -10 0 -46 -47 24 -2 13 10 -3 48 43 -28 -3 53 -15 -6 31 -23 12]
[ -6 0 9 42 -49 -38 8 12 7 39 30 -26 18 37 28 -28 8 2 -67 -21 -15]
[-56 23 22 29 -7 -19 19 -8 6 35 4 -8 22 -2 -44 -69 16 -8 -7 -45 21]
[-21 16 34 -39 36 1 57 -30 -2 -2 -36 -9 9 -27 8 -31 -31 32 12 -2 15]
[ -9 -7 6 40 32 -49 -26 -60 17 0 -13 7 25 57 -19 28 -3 -34 11 -12 -17]
[-30 -13 28 -42 8 -46 56 33 -56 -40 -24 4 10 15 46 50 -13 18 -21 17 16]
[-17 -11 -5 29 14 6 -13 4 42 -69 30 9 3 -37 5 7 -17 50 6 14 -38]
[ 53 -12 16 36 1 38 -52 25 -10 -41 -3 -37 6 -12 1 -4 -25 41 5 1 29]
[ -3 1 36 22 7 -5 -10 15 -10 -27 35 -60 -36 9 -57 33 -21 43 28 -44 8]
[ 32 -26 18 -9 -5 37 -8 2 -36 -28 43 10 -32 37 -24 -70 22 -35 49 -2 31]
[-33 15 -25 1 -40 3 -2 -32 15 9 -20 -27 -27 35 26 -1 -45 -12 45 23 36]
[-17 0 18 -20 -75 -5 55 42 16 8 -45 5 -24 -20 -50 -11 0 27 40 18 8]
[ 11 5 16 37 -2 -6 28 19 -21 5 -8 63 -8 -21 22 -23 -57 13 -5 15 -39]
第一列并不是我们想要的 1，说明第一列是 1 的向量对比起来长度并不小
再想一下规约的目的，其实很容易就能想通第一列是多少并不重要，重要的是短向量的第一列相同（这一点非常容易想通，没理解的话仔细想想）
而要让他们相同，最有效的办法就是让他们均为 0，想到这一点后，就可以在格的第一列乘上一个大数 K，从而有效的调整一下格，如下：
\[
\begin{aligned}
&[a1\ a2\ a3……a20]\ *\ []\ =\ [1\ a1\ a2……a20]
\end{aligned}
\]
这样一来，最短向量的第一列就不太可能不是 0 了（因为会对应的扩大K倍，显著地使规约向量变长）
我测试出取 100 左右即可，然后就可以求解最大公约数（此时还需注意两点小问题：一是规约出的短向量有负数，普通幂运算中会变成分数形式，通分至等式右侧即可；二是求得的公约数仍有可能是 k 倍的 n，需要去除一些小因子），最终得到 n
e= []
c= []
# step1
L = Matrix(ZZ, 20, 21)
for i in range(20):
L[i,0] = e[i]*1000
L[i,i+1] = 1
L = L.LLL()
alist1 = L[0][1:]
k1nl = 1
k1nr = 1
for i in range(20):
if(alist1[i]<0):
k1nr *= c[i]**(-alist1[i])
else:
k1nl *= c[i]**alist1[i]
k1n = k1nl-k1nr
alist2 = L[1][1:]
k2nl = 1
k2nr = 1
for i in range(20):
if(alist2[i]<0):
k2nr *= c[i]**(-alist2[i])
else:
k2nl *= c[i]**alist2[i]
k2n = k2nl-k2nr
n = gcd(k1n,k2n)
for i in range(2,10000):
while(n % i == 0):
n //= i
# 检查一下 n 的长度是否为 1024 bit
print(len(bin(n)[2:]))
print(n)
解密原文 m¶
话不多说，直接上题（BUUCTF）
from gmpy2 import *
from Crypto.Util.number import *
p = 9018588066434206377240277162476739271386240173088676526295315163990968347022922841299128274551482926490908399237153883494964743436193853978459947060210411
q = 7547005673877738257835729760037765213340036696350766324229143613179932145122130685778504062410137043635958208805698698169847293520149572605026492751740223
e = 65537
c = 50996206925961019415256003394743594106061473865032792073035954925875056079762626648452348856255575840166640519334862690063949316515750256545937498213476286637455803452890781264446030732369871044870359838568618176586206041055000297981733272816089806014400846392307742065559331874972274844992047849472203390350
n = q * p
phi = (q - 1) * (p - 1)
d = invert(e, phi)
m = pow(c, d, n)
print(long_to_bytes(m))
爆破还原 p、q（p、q 均较小）¶
话不多说，直接上题（CTFShow）
题目代码如下
from Crypto.Util.number import *
from sympy import *
def givemeprime(x):
''' x < 502'''
p = getPrime(x) # 随机生成一个小素数 p，位数为 x
print(p)
while (p).bit_length() <= 512: # 不断将 p 扩大并取下一个素数
p = nextprime(p*2**10)
return p
p = givemeprime(10) # 初始位数只有 10 位
q = givemeprime(10)
n = p*q
flag=b'?????'
m = bytes_to_long(flag)
e=2**32+1
c=pow(m,e,n)
print('n=',n)
print('c=',c)
'''
n= 9007989895621669259301762739598643626213892494330778168383286295463641223987867033273111296978959160408689408884183780314498828688143466136060628598819311509949865018608092450964012727526450914131409697944090166113416984201622940137239452703698919890772056684013237404520834408811118739546684092365102406400768733
c= 3155015611586304247269005826733691392085437186284673630268852999607965592611252562808748872502491405722341353019602057980123546192900359248245073985988035982837057433789538035295585235536446429172802713235552248615722281314286849930993306403034865999074888279573724168174433746677852218329931104122667029131804586
'''
因为 p 和 q 是通过可控过程生成的（初始为小素数，然后反复乘以 2 的幂再取 nextprime）
我们可以 穷举初始小素数值，复现 givemeprime 函数，再尝试是否存在一组 (p, q) 使得 p * q == n
from Crypto.Util.number import *
from sympy import *
from tqdm import tqdm
def givemeprime(p):
''' x < 502'''
# p = getPrime(x)
while (p).bit_length() <= 512:
p = nextprime(p * 2 ** 10)
return p
n = 9007989895621669259301762739598643626213892494330778168383286295463641223987867033273111296978959160408689408884183780314498828688143466136060628598819311509949865018608092450964012727526450914131409697944090166113416984201622940137239452703698919890772056684013237404520834408811118739546684092365102406400768733
c = 3155015611586304247269005826733691392085437186284673630268852999607965592611252562808748872502491405722341353019602057980123546192900359248245073985988035982837057433789538035295585235536446429172802713235552248615722281314286849930993306403034865999074888279573724168174433746677852218329931104122667029131804586
e = 2 ** 32 + 1
primelist = [521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647,
653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797,
809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941,
947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021]
for i in tqdm(range(len(primelist))):
for j in range(i, len(primelist)):
p = givemeprime(primelist[i])
q = givemeprime(primelist[j])
if p * q == n:
phi = (p - 1) * (q - 1)
d = inverse(e, phi)
m = pow(c, d, n)
print(long_to_bytes(m))
else:
pass
爆破还原 m（已知 m 范围）¶
话不多说，直接上题（CTFShow）
题目代码如下
from Crypto.Util.number import *
from sympy import *
# p 和 q 是 215 位的素数，所以 n = p * q 是一个大整数（430位）
p = getPrime(215)
q = getPrime(215)
n = p*q
e = 73556
flag= b'?????'
m = bytes_to_long(flag)
# nextprime(m) 和 prevprime(m) 输出的是离 m 最近的两个素数
print(nextprime(m))
print(prevprime(m))
# 注意这里的 pow(n,e,m) 看似加密，其实是反常操作
c = pow(n,e,m)
print('n=',n)
print('c=',c)
'''
40913285701005622718863058877533926183158872052161364026817991531
40913285701005622718863058877533926183158872052161364026817991159
n= 1613066479310413323265772296807266781564029043951746766617970255478050198763115133921086056086051610592970427572413404447990142013
c= 34708409030920347254051748353430247487967281837305081753454451319
'''
\[
\begin{aligned}
&c\ =\ n^e\ mod\ m
\end{aligned}
\]
from Crypto.Util.number import *
from sympy import *
e = 73556
m_next = 40913285701005622718863058877533926183158872052161364026817991531
m_priv = 40913285701005622718863058877533926183158872052161364026817991159
n = 1613066479310413323265772296807266781564029043951746766617970255478050198763115133921086056086051610592970427572413404447990142013
c = 34708409030920347254051748353430247487967281837305081753454451319
# 暴力穷举 m 在 prevprime 到 nextprime 之间的所有整数（差值很小，几十个）
for i in range(m_priv, m_next):
if c == pow(n, e, i):
print(i)
print(long_to_bytes(i))
n 为偶数推出 p = 2¶
话不多说，直接上题（PicoCTF）
远程连接发现发现生成的 N 全都是偶数
RSA 的核心公式是：
N = p × q
其中：
- p 和 q 是两个 大素数
- N 是它们的乘积，用作模数
标准 RSA 要求：
- p 和 q 均为大素数
- 且都必须是奇数（因为 2 之外的所有素数都是奇数）
如果 N 为偶数那说明 p 和 q 中有一个是偶数
但唯一的偶数素数是 2
所以 q 或 p 有一个是 2，这样我们就能直接分解 N
from Crypto.Util.number import inverse, long_to_bytes
# 从服务获取的变量（示例）
N = 16749837321344130084550985102003550399956674386743058617704729879577640535719227688593462243296045193929408852118650789506962817745280185510940780886140638 # 从 nc 接口获取 N
e = 65537
c = 1522623953839932043052285485369632549836987965181940792893751469951454437696221766465918033070039098071178026515952768796327963296844494680671840051296757 # 从 nc 接口获取 ciphertext
# 利用 N 是偶数的破绽
p = 2
q = N // p
# 计算私钥 d，并解密
phi = (p - 1) * (q - 1)
d = inverse(e, phi)
m = pow(c, d, N)
flag = long_to_bytes(m).decode()
print(flag)
提公因数 p 构造简易方程求解¶
题目给出代码
from Crypto.Util.number import *
from secret import flag
e = 65537
m = bytes_to_long(flag.encode())
p, q, r = getPrime(512), getPrime(512), getPrime(512)
n = p*q*r
c = pow(m, e, n)
print(c)
print(n)
print(p+q+r)
print(p*q+p*r)
转换成数学公式 $$ \begin{aligned} &n = p q r\ &t = p q + p r = p(q + r)\ &ϕ(n) = (p - 1)(q - 1)(r - 1) \end{aligned} $$ 我们可以清楚地看到，p 是 n 和 t 的公共因子
那 GCD(n, t) 会正好是 p 吗？会不会包含其他因子？ $$ \begin{aligned} &GCD(pqr,p(q + r)) = p * GCD(qr,q + r) \end{aligned} $$ 由于 q 和 r 都是生成的 512 位随机大素数，它们互质，且它们的和 q+r 极大概率与它们的积 qr 互质
因此 GCD(qr, q+r) = 1
结论： 直接计算 GCD(n, t) 就能无痛提取出素数 p
对于 n=pqr，欧拉函数定义为： $$ \begin{aligned} &\phi(n) = (p-1)(q-1)(r-1)\ &\phi(n) = (p-1) [(q-1)(r-1)]\\ &n - t = pqr - pq - pr\ &n - t = p(qr - q - r)\ &(n - t) // p = (qr - q - r)\ &(n - t) // p + 1 = (qr - q - r) + 1\\ &qr - q - r + 1 = q(r - 1) - 1(r - 1)\ &q(r - 1) - 1(r - 1) = (q - 1)(r - 1)\\ &(n - t) // p + 1 = (q - 1)(r - 1)\ &\phi(n) = (p-1) [(q-1)(r-1)]\\ \end{aligned} $$ 观察公因数 是 Crypto 选手的直觉。看到 n 和 t 有明显的公共结构（都含有 p），第一时间想到的就是 GCD
from Crypto.Util.number import *
# ==========================================
# 题目信息与数学关系回顾
# ------------------------------------------
# 已知：
# n = p * q * r (三素数 RSA)
# s = p + q + r (此变量在本脚本中未被使用)
# t = p * q + p * r = p * (q + r)
# ==========================================
# 题目给出的长整数数据（省略部分以保持整洁）
c = 216719040256186298397028655750064798850...
n = 894056034566447301955142597300391580123...
t = 157435908314881832180551915807491465031...
# [第一步]：提取公共素因子 p
# 数学原理：n = p*q*r，t = p*(q+r)
# 显然 p 是 n 和 t 的最大公约数
p = GCD(n, t)
# [第二步]：巧妙构造欧拉函数 phi(n)
# 目标：phi = (p-1) * (q-1) * (r-1)
#
# 1. 括号右边推导：((n - t) // p + 1)
# 分子：n - t = pqr - (pq + pr) = pqr - pq - pr = p(qr - q - r)
# 除法：(n - t) // p = qr - q - r
# 加一：qr - q - r + 1
# 因式分解：q(r-1) - 1(r-1) = (q-1)(r-1)
#
# 2. 最终合并：
# (p-1) * [(q-1)(r-1)] = phi(n)
phi = (p - 1) * ((n - t) // p + 1)
# [第三步]：常规 RSA 私钥计算
# 计算 e 在模 phi 下的乘法逆元 d
d = inverse(65537, phi)
# [第四步]：解密
# m = c^d mod n
m = pow(c, d, n)
# 将解密出的长整数转换为字节串（即明文 Flag）
print(long_to_bytes(m))
利用斐波那契数列周期重复性爆破¶
题目代码如下
from Crypto.Util.number import *
from gmpy2 import next_prime
from functools import reduce
from secret import flag
def F(x):
if x == 1 or x == 2:
return 1
return F(x-1)+F(x-2)
n = reduce(lambda a, b: a*b, [getPrime(4) for _ in range(4)])
r = getRandomNBitInteger(67)
S = sum([F(i) % n for i in range(r)])
p = next_prime(S**16)
q = getPrime(p.bit_length())
m = bytes_to_long(flag)
c = pow(m, 65537, p*q)
print("r =", r)
print("n =", n)
print("c =", c)
print("N =", p*q)
现在分析代码
定义了一个斐波那契数列
斐波那契数列是一个**递推数列**，它的核心规则是：从第三项起，数列中的每一项都等于前两项之和 $$ \begin{aligned} &F_n = F_{n-1} + F_{n-2} (n \geq 3) \end{aligned} $$ 在 CTF 和数论领域，斐波那契数列的**模运算性质**至关重要：
Pisano 周期
- 定义： 斐波那契数列对任何正整数 n 取模后，都会变成一个**循环数列**。这个循环的长度就被称为 Pisano 周期，记作 $$ \begin{aligned} &\pi(n) \end{aligned} $$
小模数 n 的生成
# 2. 小模数 n 的生成
# 生成 4 个 4-bit 的小素数（p_i <= 15）
# n 是这四个小素数的乘积
# n 的大小约为 16 bits (n <= 15^4 = 50625)
n = reduce(lambda a, b: a*b, [getPrime(4) for _ in range(4)])
巨大的求和上限 r
# 3. 巨大的求和上限 r
# r 是一个 67-bit 的大整数 (r 约等于 2^67)
# 注意：r 是计算 S 的唯一输入，且 r 已经泄露给我们
r = getRandomNBitInteger(67)
S 的计算
# 4. 关键泄露信息 S 的计算 (S是 p 的基础)
# S 是前 r 个斐波那契数在模 n 下的和：S = Sum_{i=0}^{r-1} (F(i) mod n)
S = sum([F(i) % n for i in range(r)])
生成巨大的素数 p
# 5. 生成巨大的素数 p
# p 是 S^16 之后的第一个素数
# S 的大小约为 r * n (约 2^67 * 2^16 = 2^83)
# p 的大小约为 (2^83)^16 = 2^1328 bits
p = next_prime(S**16)
生成素数 q
首先要求出 p -> S -> r 这个顺序
先看 S 的计算方式 $$ \begin{aligned} &S = \sum_{i-0}^{r-1}{F((i) (mod n))} \end{aligned} $$ 求和次数 r 太大，但是，求和时使用的模数 n 却非常小（不到 65536）
这是整个解题的关键步骤。我们不能循环 r 次，但 n 很小，所以我们要找规律
Pisano 周期（重复的舞蹈）
当斐波那契数列对一个小数字 n 取模时，它的结果会不断重复，形成一个**循环**。这个循环的长度就是 Pisano 周期 T
- 斐波那契数列 mod n 就像一个**舞者**在一个很小的圆形舞台（模数 n）上跳舞。它跳了一段时间后，姿势和位置一定会回到起点 (1, 1)
- 周期 T 就是这支舞完整跳完一次所需要的步数
通过脚本实现
a, b = 1, 1
while True:
a, b = b, (a + b) % n # 找到下一步的舞步
if a == 1 and b == 1: # 检查是否回到起点
T = period = len(fibs) # 记录步数 T
break
因为 n 很小，这个循环很快就能结束，我们得到了周期 T 和跳一圈舞的总得分 Sum_{cycle}
现在我们有了舞蹈的规律，就可以计算 r 步的总得分 S：
- 完整周期数 k： k = r // T （看看 r 步能跳多少次完整的舞）
- 剩余步数 rem： rem = r \% T （最后多出来没跳完的几步）
\[
\begin{aligned}
&S\ =\ (完整次数\ k\ *\ 一圈的总得分\ Sum_{cycle})\ +\ (剩余几步的得分\ Sum_{cycle})
\end{aligned}
\]
这一步就将天文数字 r 转换成了一个可计算的公式，得到了我们想要的秘密蓝图 S
| 脚本代码 | 作用 | 简单理解 |
|---|---|---|
p = next_prime(S ** 16) |
计算第一个秘密零件 p。 严格按照题目的公式，找到 S^{16} 之后的第一个素数 | |
q = N // p |
计算第二个秘密零件 q。 N 是 p 和 q 的乘积，所以 q = N / p | |
phi = (p - 1) * (q - 1) |
计算制造蓝图 \phi(N) | |
d = inverse(65537, phi) |
计算万能钥匙 d。 inverse 是求一个数在 \pmod{phi} 世界里的“倒数” |
|
m = pow(c, d, N) |
解密！ 使用万能钥匙 d 打开保险箱 N 中的密文 c | |
long_to_bytes(m) |
将解密得到的数字 m 转换回 Flag 文本 |
完整代码如下
from Crypto.Util.number import *
import gmpy2
# ==========================================
# 1. 在此填入题目给出的参数 (从你的题目输出中复制)
# ==========================================
r = 6799657976717333 # 题目给出的 r (67-bit integer)
n = 34969 # 题目给出的 n (小整数，约 16-bit)
c = 182306974283951620352146026941583994848813143690343545292100780435573376889099600153592983212384957591086328477660614034391593564733860826251499298995355977799109267846836211477797049861348446512705981010295182077777939692478140339301301250656211795668782349225298841295102744088295274299888068087536135862146848855194234931032258224223054120694400807261402442809227521150204434199401928373883267697928229945582110688115412960868921538084717338343966490113059627708880297277412143561561837953806960309840302665509500602335832680764801782789278492075478763944213005349707521471401389317139473794212210077629296628421658105048387207038261321205 # 题目给出的密文 c
N = 1885611999537620305525377668936000019248252379006235038175895811710218489750248037027959751027236326639084060685909621893589756343903429224938045802850975926055076789137326688384533999739909152386986919824268841500802585809839133132715892685629871188263336038221503698167753853207939360629026179572549702198037779413041272313618794196167670066872427987596564652249864272782397242041014605617282098654595635031878004275878165728021995744626212185694275937448739806439006047047376363093018124169182873374456718929377731991273039952515054850718253257895996999907977029169396644305213162133388169761391593110121229266422245167572929912914529689341 # 题目给出的公钥 N
# ==========================================
# 2. 核心函数：寻找 Pisano 周期并计算周期和
# 对应思路 2 的优化版：直接在 Python 中实现
# ==========================================
def get_pisano_info(n):
# 斐波那契数列缓存，用于计算余数部分的和
fibs = [1, 1]
# 寻找周期：暴力迭代直到再次出现 "1, 1"
# 因为 n 很小，这个循环会很快结束
a, b = 1, 1
period = 0
while True:
# 下一项 F(i) = F(i-1) + F(i-2)
a, b = b, (a + b) % n
fibs.append(b)
# 检查是否回到了起点 (1, 1)
# 注意：现在的 b 是新的一项，a 是上一项
if a == 1 and b == 1:
# 找到了循环节！
# 此时 fibs 最后两个是 1, 1，属于下一个周期的开始，要去掉
fibs.pop()
fibs.pop()
period = len(fibs)
break
period_sum = sum(fibs)
return period, period_sum, fibs
print(f"[*] Analyzing Pisano period for n = {n}...")
period, period_sum, fibs = get_pisano_info(n)
print(f"[+] Period found: T = {period}")
print(f"[+] Sum of one period: {period_sum}")
# ==========================================
# 3. 计算 S
# 利用公式：S = (完整周期的次数 * 周期和) + (剩余部分的和)
# ==========================================
k = r // period # 完整的周期数
rem = r % period # 剩余的项数
# 剩余部分的和 = 前 rem 项之和
rem_sum = sum(fibs[:rem])
# 计算最终的 S (注意题目中 S 是模 n 后求和，不需要再对 S 取模)
S = k * period_sum + rem_sum
print(f"[+] Calculated S = {S}")
# ==========================================
# 4. 恢复 RSA 密钥 p, q
# 题目逻辑：p = next_prime(S**16)
# ==========================================
# 注意 S**16 很大，需要用 gmpy2 处理大数运算
base_p = gmpy2.mpz(S) ** 16
p = int(gmpy2.next_prime(base_p))
# 验证 p 是否正确
if N % p == 0:
print("[+] Successfully recovered p!")
q = N // p
else:
print("[-] Failed to recover p. Check parameters.")
exit()
# ==========================================
# 5. 标准 RSA 解密
# ==========================================
e = 65537
phi = (p - 1) * (q - 1)
d = inverse(e, phi)
m = pow(c, d, N)
flag = long_to_bytes(m)
print("\n--------------------------------------------------")
print("Flag:", flag.decode())
print("--------------------------------------------------")
利用 p 信息泄露 GCD 攻击¶
解题技巧先放前面：
- **识别 GCD 攻击模式：**看到泄露信息 hint = m^17 (mod p)，必须立刻联想到 p 是 (m^17 - hint) 的因子
from Crypto.Util.number import *
from secret import flag # 目标明文
# 1. 初始化和密钥生成
m = bytes_to_long(flag) # 将 Flag 转换为巨大的整数 m
p = getPrime(1024) # 生成第一个秘密素数 p (1024 bits)
q = getPrime(1024) # 生成第二个秘密素数 q (1024 bits)
n = p * q # RSA 模数 N (2048 bits，安全标准)
# 2. 核心漏洞：Hint 的泄露
# 提示 H 是明文 m 以极小的指数 17 对素数 p 取模的结果。
# 数学关系：hint ≡ m^17 (mod p)
# 这意味着 p 整除 (m^17 - hint)
hint = pow(m, 17, p)
# 3. 标准 RSA 加密
e = 65537 # 公钥指数 e (最常用的 Fermat 素数)
c = pow(m, e, n) # 密文 c ≡ m^e (mod n)
# 4. 泄露给攻击者的信息
print("n =", n) # 公钥模数 N (2048-bit)
print("e =", e) # 公钥指数
print("c =", c) # 密文
print("hint =", hint) # 泄露信息 H (m^17 mod p)
我们从题目提供的两个基本关系开始： $$ \begin{aligned} &1: x = 11 d + 7 \phi(n)\\ &2: e d \equiv 1 (mod {\phi(n)})\\ &将 RSA 关系转化为代数等式，引入一个未知整数 r\\ &e d = 1 + r \phi(n) \end{aligned} $$ 我们的目标是消除未知数 d。最有效的方法是将**等式 1* 的两侧都乘以已知的公钥 e，从而引入 e * d 项，方便进行替换
将**等式 1** 两侧同乘 e： $$ \begin{aligned} &3: x e= 11 (e d)+ 7 e \phi(n) \end{aligned} $$ 现在，我们将**等式 2** 代入**等式 3** 中的 (e * d) 项： $$ \begin{aligned} &3: x e= 11 (1 + r \phi(n))+ 7 e \phi(n) \end{aligned} $$ 现在，等式中已经成功消除了 d。我们进行代数整理，将所有含欧拉函数 n 的项归类，常数项移到左侧 $$ \begin{aligned} &x e= 11 + 11 r \phi(n)+ 7 e \phi(n)\\ &x e - 11 = 11 r \phi(n)+ 7 e \phi(n)\\ &x e - 11 = (11 r + 7 e) \phi(n)\\ &\phi(n) = \frac{x*e-11}{11*r+7*e}\\ \end{aligned} $$ 这个方程中，唯一剩下的未知数是整数 r
由于欧拉函数 n 必须是一个巨大的**整数**（通常 2048 位），因此分子必须能够被分母**整除**
所以直接爆破破解 r
from Crypto.Util.number import *
import gmpy2
import sys
# =========================================================
# 步骤 1: 替换为题目中泄露的参数
# IMPORTANT: 请将这里的占位符替换为你实际的 CTF 数据！
# =========================================================
N = 15321211041844905603734344178124947500324300419514650914959277216026081094496518094622195813971694335738777589926626969243883848477814650916143749322154944235584863085124154540941941026813506509060939499627059712020664731558566028207969260861863294704292014958955493668692256998253634012942569080200336487172402729072437050952572508561453302097971258470685521456512378089846772560530301852104802168974905937732653119166440832834381675710869396094149006807933529429939569477709674581421481769103309376717894952118650888932952440197471338958967318775671821835706884032860123711415773758546392549257375305940969423099611 # RSA 模数 n
E = 65537 # 公钥指数 e (通常是 65537)
C = 14896093236493033914781929755936872928003725648997746598164823180134348743474984136539422027221313199599273430548738399424773586673404519182726589878322104929749149555906399158136445184378100079558203687049497943904275695897824656260657349522646553949766831267321006314984113971129230701131171378457086851261467999754137290017989201512492586108768533159551545321805463224339252886492732021354821330371600069958523522302729848548167244423902572054475396534469987383265867036041513161170273368613864180696427386890714264902686976581317435011139081192227958859641684254938165261747405568369502852705979424383731908971282 # 密文 c
X = 265060901898485540806769085700708185460124724747068797929982044073895401490880169847709049380530156090772787935089173201664711759633269693627724735457902114209008145932150728406880988293457762401679305297063608204632708505031098047582175011825482347052645324085149631658741807382378778694666759557421043250548432429798543553950625554307402164142007388940921309688918410535907564996075660231557340541491155676279511654970843992008027830570227549010293790074386638365293013298327534604995316180405779571245069623638693068707267840181413082202552862853411080755107836252852929279422343700808788459217261282790226013328915 # 泄露信息 x (x = 11*d + 7*phi(n))
# 我们可以从 r=1 开始，因为 r 必须是正整数
R_MAX = 100000
# =========================================================
# 步骤 2: 核心解题函数 - 枚举 r 求解 phi(n)
# =========================================================
def solve_modified_rsa(N, E, C, X, R_MAX):
"""
根据公式 phi(n) = (X*E - 11) / (11*r + 7*E) 枚举 r，
并验证结果是否为合法的 phi(n)。
"""
# 公式分子 C_NUM = X*E - 11
C_NUM = X * E - 11
print(f"[*] 开始枚举 r (r_max={R_MAX})...")
# r 必须为正整数
for r in range(1, R_MAX + 1):
# 公式分母 D_DEN = 11*r + 7*E
D_DEN = 11 * r + 7 * E
# 1. 整除性检查：判断分子是否能被分母整除
if C_NUM % D_DEN == 0:
# 找到潜在的 phi(n)
phi_n = C_NUM // D_DEN
print(f"[+] 找到潜在的 phi(n) 候选项 (r={r})")
# 2. 合理性检查：phi(n) 必须小于 N
if phi_n >= N:
# 理论上不可能，如果出现说明数据有误，或 r_max 设置太小
continue
# 3. RSA 约束检查：判断 phi(n) 是否能用于分解 N
# 我们知道：p + q = N - phi(n) + 1
# 设 S = p + q
S = N - phi_n + 1
# 根据韦达定理，p, q 是二次方程 X^2 - S*X + N = 0 的根
# 判别式 D = S^2 - 4*N 必须是一个完全平方数 (Perfect Square)
D = S * S - 4 * N
# 使用 gmpy2 检查 D 是否为完全平方数
if gmpy2.is_square(D):
print(f"[!!!] 成功找到正确的 phi(n)!")
print(f"[!] r = {r}")
print(f"[!] phi(n) = {phi_n}")
# 4. 最终解密
# 计算私钥 d = E^(-1) mod phi(n)
d = inverse(E, phi_n)
# 解密明文 m = C^d mod N
m = pow(C, d, N)
flag = long_to_bytes(m)
print("\n==============================================")
print(f"p + q = {S}")
print(f"Private Key d = {d}")
print(f"Decrypted Flag: {flag.decode()}")
print("==============================================")
return True # 退出函数
print("[-] 未能在设定的 R_MAX 范围内找到有效的 phi(n)，请尝试增大 R_MAX 或检查输入数据。")
return False
if __name__ == "__main__":
if N == ...:
print("错误：请先在脚本顶部替换 N, C, X 的占位符！")
sys.exit(1)
solve_modified_rsa(N, E, C, X, R_MAX)
在线分解 n¶
话不多说，直接上题（BUUCTF）
打开文件给了 n 和 e
去网站分解得到了 p、q
需要的东西齐了，编写脚本读取每行解密，记得删除 data.txt 的前两行
import gmpy2
n = 920139713
e = 19
# p、q 在线网站分解得到
p = 18443
q = 49891
phi = (p - 1) * (q - 1)
d = gmpy2.invert(e, phi)
result = []
with open("../02c01a13-3a86-47de-8648-f03328a5e5d8/RsaRoll/data.txt", "r") as f:
for line in f.readlines():
line = line.strip('\n')
result.append(chr(pow(int(line), d, n)))
for i in result:
print(i, end='')
n 为素数推出 phi¶
话不多说，直接上题（New Year CTF 2024）
做题的时候网站挂了，这里题目给了 n e c，其中 n 是素数
解题思路：
$$ \begin{aligned} &phi = (q - 1)(p - 1) \end{aligned} $$
$$ \begin{aligned} &phi = n - 1 \end{aligned} $$
import libnum
from gmpy2 import *
# 题目条件
n = 894011376132861406416081994144221048298348543110763436400156707035479762291337096368301340210777912166253392435275663746074998964323198306974285233167719096055553347615918699581765041856450618725024365550285245909593290693757548300976025136185960841538482656726074757217987326418213368306947431668797511869941369363510575799319146232381645606378509284692783439527001482275434870365007864755014763434476875230779298152747668036103797086099448952638933614839186234115539057353208089196503236476069765055958643599622359809306429773621018079928117609961649006558217734057147235098517323614637509521563090769478823258676357262436290835475545437211168106617010859479612214627871047960151415095910992231687737019157788664429412462674876326653667300420128914036327499885103193423178025962079282185227746880809451234195481664650147610375976243181422075319601793906090392759832052648670731266344219250793991957964535801285606036631861341696305110038590888086491568683507575846576623827059055577036404611548224528600604898405714747157240730264673180051312634408192644777331633111950232485559076080686217541095754245034143596485147084607615402187454830802772582891800608645679493263524678084504132604846410243911260803002065871918398725293311473
e = 49999
c = 127990258916322713210704002931365496210647826869578493680557063836772515914303363145985391647430839311330158084206710072455465957218072448099969815961814463831667357474852426061475210363277306704257877402661232669936031043625938011115290529377505573367883714424182150449678726041360949463375982144652910707759221795772350872426009873120527309342093683340576731241704191541296890578962805029558926492259701366885936092059693759354255247540815813052543086204934376066884066060405947003334121725632674642690548675916126384013014552545338699198239765357561083183401525044638243204528501965028598782513999767237563252331767079569128151380305983732341553403814650118788711703476805307790685184506737890913441497269132749881622937761764492015610811577966553776703680435092016590690563200951474073620866158140866931856293211794418637441400021472249887178225738960768608549559781531479910409684884180658879621882231073123533851227894797415625533435081416099549459198508358607887551022339960981663266529984544362524495679204397590064106335341279871204905873532415276380340515150499389237587052633736125460704219829657692767592459700685070039056607335118481257774532132073976558433243315868939654221066341581052013795470559435542389710686098062
d = invert(e, (n - 1))
m = pow(c, d, n)
print(libnum.n2s(int(m)))
低加密指数爆破攻击（e 较小）¶
话不多说，直接上题（BUUCTF）
题目给出了 n c e（较小），可以用低加密指数攻击去解题
$$ \begin{aligned} &\because c = m ^ e mod n\\ First case:\\ &\because m ^ e < n\ &\therefore c = m ^ e\\ Example: \\ &e = 3\ &n = 100\ &m = 4\ &m ^ e = 64\ &\because 64 < 100\ &\therefore c = 64\\ Second case:\\ &\because m ^ e > n\ &\therefore m ^ e =kn + c\\ &(k is a positive integer multiple) \end{aligned} $$
from gmpy2 import iroot
import libnum
e = 0x3
n = 0x52d483c27cd806550fbe0e37a61af2e7cf5e0efb723dfc81174c918a27627779b21fa3c851e9e94188eaee3d5cd6f752406a43fbecb53e80836ff1e185d3ccd7782ea846c2e91a7b0808986666e0bdadbfb7bdd65670a589a4d2478e9adcafe97c6ee23614bcb2ecc23580f4d2e3cc1ecfec25c50da4bc754dde6c8bfd8d1fc16956c74d8e9196046a01dc9f3024e11461c294f29d7421140732fedacac97b8fe50999117d27943c953f18c4ff4f8c258d839764078d4b6ef6e8591e0ff5563b31a39e6374d0d41c8c46921c25e5904a817ef8e39e5c9b71225a83269693e0b7e3218fc5e5a1e8412ba16e588b3d6ac536dce39fcdfce81eec79979ea6872793
c = 0x10652cdfaa6b63f6d7bd1109da08181e500e5643f5b240a9024bfa84d5f2cac9310562978347bb232d63e7289283871efab83d84ff5a7b64a94a79d34cfbd4ef121723ba1f663e514f83f6f01492b4e13e1bb4296d96ea5a353d3bf2edd2f449c03c4a3e995237985a596908adc741f32365
k = 0
while 1:
# iroot: 计算 x 开 e 次方并返回一个二元组
# 1. root 是 x 的 e 次方根
# 2. is_exact 是一个布尔值，表示 x 是否恰好是某个数的 e 次方
# 如果 x 正好是某个数的 e 次方，那么 is_exact 为 True，否则为 False
res = iroot(c + k * n, e)
if res[1]:
print(libnum.n2s(int(res[0])))
break
k += 1
低加密指数分解攻击（e 较小）¶
话不多说，直接上题（New Year CTF 2024）
题目给出 n、c，c 比 n 小，推测要低加密指数攻击，最后可直接分解 n 得到 p、q
$$
\begin{aligned}
&\because c = m ^ e mod n\\
First case:\\
&\because m ^ e < n\
&\therefore c = m ^ e\\
Example: \\
&e = 3\
&n = 100\
&m = 4\
&m ^ e = 64\
&\because 64 < 100\
&\therefore c = 64\\
Second case:\\
&\because m ^ e > n\
&\therefore m ^ e =kn + c\\
&(k is a positive integer multiple)
\end{aligned}
$$
Coppersmith 攻击（p、q 部分位数泄露）¶
话不多说，直接上题（2021 鹤城杯）
from Crypto.Util.number import getPrime, bytes_to_long
from secret import flag
p = getPrime(1024)
q = getPrime(1024)
n = p * q
e = 65537
hint1 = p >> 724
hint2 = q % (2 ** 265)
ct = pow(bytes_to_long(flag), e, n)
print(hint1)
print(hint2)
print(n)
print(ct)
"""
hint1 = 1514296530850131082973956029074258536069144071110652176122006763622293335057110441067910479
hint2 = 40812438243894343296354573724131194431453023461572200856406939246297219541329623
n = 21815431662065695412834116602474344081782093119269423403335882867255834302242945742413692949886248581138784199165404321893594820375775454774521554409598568793217997859258282700084148322905405227238617443766062207618899209593375881728671746850745598576485323702483634599597393910908142659231071532803602701147251570567032402848145462183405098097523810358199597631612616833723150146418889589492395974359466777040500971885443881359700735149623177757865032984744576285054725506299888069904106805731600019058631951255795316571242969336763938805465676269140733371287244624066632153110685509892188900004952700111937292221969
ct = 19073695285772829730103928222962723784199491145730661021332365516942301513989932980896145664842527253998170902799883262567366661277268801440634319694884564820420852947935710798269700777126717746701065483129644585829522353341718916661536894041337878440111845645200627940640539279744348235772441988748977191513786620459922039153862250137904894008551515928486867493608757307981955335488977402307933930592035163126858060189156114410872337004784951228340994743202032248681976932591575016798640429231399974090325134545852080425047146251781339862753527319093938929691759486362536986249207187765947926921267520150073408188188
"""
\[
\begin{aligned}
&Let\ \ q0\ =\ q\ mod\ 2^{265}\\
&\therefore\ q\ =\ q0\ +\ 2^{265}k\\
&\therefore\ n = \ q0\ p\ +\ 2^{265}\ k\ p\\
&\therefore\ n\ q0^{-1}\ =\ p\ +\ 2^{265}\ k\ p\ q0^{-1}\\\\
&Let\ \ k\ =\ k\ p\ q0^{-1}\\
&\therefore\ n\ q0^{-1}\ =\ p\ +\ 2^{265}k\\
&\because\ c\ =\ m ^ e\ mod\ n\\
&\therefore\ m ^ e\ =kn\ +\ c\\
&\therefore\ p0\ =\ n\ q0^{-1}\ mod\ 2^{265}\\\\
&(Here\ p0\ represents\ the\ lower\ 265\ bits\ of\ p)
\end{aligned}
\]
那么 p 的高 300 位和低 265 位之和为：
(hint1 << 724) + p0
其中间的 459 位通过 copperSmith 求解
正常情况下是构造 f = pbar + x * 265，但是因为位数不够所以需要抬高 64 爆破（要求已知位数 >= 570bit）
每次加 2 ^ 265
sage 求解的固定方式：
PR.<x> = PolynomialRing(Zmod(n))
f = ...
f = f.monic()
f.small_roots(X = 2 ^ (sizep-knownbits) - 1, beta = 0.4)
hint1 = 1514296530850131082973956029074258536069144071110652176122006763622293335057110441067910479
hint2 = 40812438243894343296354573724131194431453023461572200856406939246297219541329623
n = 21815431662065695412834116602474344081782093119269423403335882867255834302242945742413692949886248581138784199165404321893594820375775454774521554409598568793217997859258282700084148322905405227238617443766062207618899209593375881728671746850745598576485323702483634599597393910908142659231071532803602701147251570567032402848145462183405098097523810358199597631612616833723150146418889589492395974359466777040500971885443881359700735149623177757865032984744576285054725506299888069904106805731600019058631951255795316571242969336763938805465676269140733371287244624066632153110685509892188900004952700111937292221969
p0 = n * (hint2 ^ -1) % (2 ^ 265)
pbar = (hint1 << 724) + p0
PR.<x> = PolynomialRing(Zmod(n))
# 循环爆破
for i in range(64):
f = pbar + x * (2 ^ 265) * 64 + x * (2 ^ 265)
# f.monic()：将多项式转换为一个单项式化多项式，其最高次项的系数为 1
f = f.monic()
pp = f.small_roots(X = 2 ^ 453, beta = 0.4)
if pp:
break
pbar += 2 ^ 265
p = int(pbar + pp[0] * 32 * (2 ^ 265))
print("p=", p)
去在线网站解出 p
低加密指数广播攻击（n、c 为列表 e 较小）¶
话不多说，直接上题（2021 鹤城杯）
from Crypto.Util.number import *
from Crypto.Util.Padding import *
FLAG = bytes_to_long(pad(b"flag{??????}",64))
def init_key():
p, q = getPrime(512), getPrime(512)
n = p*q
e = 9
while(GCD((p-1)*(q-1),e)!=1):
p, q = getPrime(512), getPrime(512)
n = p*q
d = inverse(e,(p-1)*(q-1))
return n,e,d
n_list=list()
c_list=list()
for i in range(9):
N,e,d=init_key()
n_list.append(N)
c=pow(FLAG,e,N)
c_list.append(pow(FLAG,e,N))
assert(pow(c,d,N)==FLAG)
print("n_list:",n_list)
print("c_list:",c_list)
解题思路：
中国剩余定理是一种求解同余方程组的算法，对于给定的同余方程组：
x ≡ a1 mod m1
x ≡ a2 mod m2
……
x ≡ a3 mod m3
且它们两两互质则存在唯一的解 x 在 [0,M) 范围内，其中 M 是所有模数的乘积：
M = m1 * m2 * …… * mn
对于每个模数 Mi 可这么计算：
Mi = M / mi
求解每个 Mi 的模逆元：
Mi * Mi ^ -1 ≡ 1 mod mi
编写脚本：
from Crypto.Util.number import *
import gmpy2
n_list= [71189786319102608575263218254922479901008514616376166401353025325668690465852130559783959409002115897148828732231478529655075366072137059589917001875303598680931962384468363842379833044123189276199264340224973914079447846845897807085694711541719515881377391200011269924562049643835131619086349617062034608799, 92503831027754984321994282254005318198418454777812045042619263533423066848097985191386666241913483806726751133691867010696758828674382946375162423033994046273252417389169779506788545647848951018539441971140081528915876529645525880324658212147388232683347292192795975558548712504744297104487514691170935149949, 100993952830138414466948640139083231443558390127247779484027818354177479632421980458019929149817002579508423291678953554090956334137167905685261724759487245658147039684536216616744746196651390112540237050493468689520465897258378216693418610879245129435268327315158194612110422630337395790254881602124839071919, 59138293747457431012165762343997972673625934330232909935732464725128776212729547237438509546925172847581735769773563840639187946741161318153031173864953372796950422229629824699580131369991913883136821374596762214064774480548532035315344368010507644630655604478651898097886873485265848973185431559958627423847, 66827868958054485359731420968595906328820823695638132426084478524423658597714990545142120448668257273436546456116147999073797943388584861050133103137697812149742551913704341990467090049650721713913812069904136198912314243175309387952328961054617877059134151915723594900209641163321839502908705301293546584147, 120940513339890268554625391482989102665030083707530690312336379356969219966820079510946652021721814016286307318930536030308296265425674637215009052078834615196224917417698019787514831973471113022781129000531459800329018133248426080717653298100515701379374786486337920294380753805825328119757649844054966712377, 72186594495190221129349814154999705524005203343018940547856004977368023856950836974465616291478257156860734574686154136925776069045232149725101769594505766718123155028300703627531567850035682448632166309129911061492630709698934310123778699316856399909549674138453085885820110724923723830686564968967391721281, 69105037583161467265649176715175579387938714721653281201847973223975467813529036844308693237404592381480367515044829190066606146105800243199497182114398931410844901178842049915914390117503986044951461783780327749665912369177733246873697481544777183820939967036346862056795919812693669387731294595126647751951, 76194219445824867986050004226602973283400885106636660263597964027139613163638212828932901192009131346530898961165310615466747046710743013409318156266326090650584190382130795884514074647833949281109675170830565650006906028402714868781834693473191228256626654011772428115359653448111208831188721505467497494581]
c_list= [62580922178008480377006528793506649089253164524883696044759651305970802215270721223149734532870729533611357047595181907404222690394917605617029675103788705320032707977225447998111744887898039756375876685711148857676502670812333076878964148863713993853526715855758799502735753454247721711366497722251078739585, 46186240819076690248235492196228128599822002268014359444368898414937734806009161030424589993541799877081745454934484263188270879142125136786221625234555265815513136730416539407710862948861531339065039071959576035606192732936477944770308784472646015244527805057990939765708793705044236665364664490419874206900, 85756449024868529058704599481168414715291172247059370174556127800630896693021701121075838517372920466708826412897794900729896389468152213884232173410022054605870785910461728567377769960823103334874807744107855490558726013068890632637193410610478514663078901021307258078678427928255699031215654693270240640198, 14388767329946097216670270960679686032536707277732968784379505904021622612991917314721678940833050736745004078559116326396233622519356703639737886289595860359630019239654690312132039876082685046329079266785042428947147658321799501605837784127004536996628492065409017175037161261039765340032473048737319069656, 1143736792108232890306863524988028098730927600066491485326214420279375304665896453544100447027809433141790331191324806205845009336228331138326163746853197990596700523328423791764843694671580875538251166864957646807184041817863314204516355683663859246677105132100377322669627893863885482167305919925159944839, 2978800921927631161807562509445310353414810029862911925227583943849942080514132963605492727604495513988707849133045851539412276254555228149742924149242124724864770049898278052042163392380895275970574317984638058768854065506927848951716677514095183559625442889028813635385408810698294574175092159389388091981, 16200944263352278316040095503540249310705602580329203494665614035841657418101517016718103326928336623132935178377208651067093136976383774189554806135146237406248538919915426183225265103769259990252162411307338473817114996409705345401251435268136647166395894099897737607312110866874944619080871831772376466376, 31551601425575677138046998360378916515711528548963089502535903329268089950335615563205720969393649713416910860593823506545030969355111753902391336139384464585775439245735448030993755229554555004154084649002801255396359097917380427525820249562148313977941413268787799534165652742114031759562268691233834820996, 25288164985739570635307839193110091356864302148147148153228604718807817833935053919412276187989509493755136905193728864674684139319708358686431424793278248263545370628718355096523088238513079652226028236137381367215156975121794485995030822902933639803569133458328681148758392333073624280222354763268512333515]
e = 9
def CRT(aList, mList):
# 计算模数的乘积 M
M = 1
for i in mList:
M = M * i
#
x = 0
for i in range(len(mList)):
# 计算 Mi = M / mi
Mi = M // mList[i]
# 计算 Mi 在模 mi 下的逆元
Mi_inverse = gmpy2.invert(Mi, mList[i])
# 累加
x += aList[i] * Mi * Mi_inverse
x = x % M
return x
m_e = CRT(c_list, n_list)
m = gmpy2.iroot(m_e, e)[0]
print(long_to_bytes(m))
维纳攻击（e 过大或过小）¶
话不多说，直接上题（2024 年楚慧杯湖北省网络与数据安全实践能力竞赛）
from Crypto.Util.number import *
from gmpy2 import *
from libnum import *
flag = b'DASCTF{******}'
p = getPrime(512)
q = getPrime(512)
n = p*q
d = getPrime(256)
e = inverse(d, (p-1)*(q-1))
m = s2n(flag)
c = pow(m, e, n)
print('n = ' + str(n))
print('e = ' + str(e))
print('c = ' + str(c))
'''
n = 114566998957451783636756389276471274690612644037126335470456866443567982817002189902938330449132444558501556339080521014838959058380963759366933946623103869574657553262938223064086322963492884606713973124514306815995276393344755433548846003574038937940253826360659447735554684257197194046341849089254659225497
e = 35489734227210930185586918984451799765619374486784192218215354633053183935617953856556709715097294481614236703293033675674496036691242573294182072757562322996800390363453350727372642264982749305833933966045097125311467413670410802534093354414115267442785896373815076066721029449240889291057288090241124904705
c = 60503455347700500866544596012233537789678841391057706123172519773588895502922586197178148979273264437566411675346207472455036341903878112074983509557751805365618433536738111588239911292341288514123006967218545943520736254346030465088445419278775539026233686559207400401082452551955780877227801939191694370380
'''
在 e 过大或过小的情况下，可使用算法从 e 中快速推断出 d 的值，原文链接 $$ \begin{aligned} &\because n = pq\ &\because \varphi(n) = (q - 1)(p - 1)\ &\therefore \varphi(n) = pq - (p + q) + 1\ &\therefore \varphi(n) = n - (p + q) + 1\\ &\because p,q are very large\ &\therefore pq >> p + q\ &\therefore \varphi(n) \approx n\\ &\because ed \equiv 1 mod \varphi(n)\\ &(This ed is the theorem.Don't worry about it)\\ &\therefore ed - 1 = k\varphi(n)\ &\therefore \frac{e}{\varphi(n)} - \frac{1}{d\varphi(n)} = \frac{k}{d}\ &\therefore \frac{e}{\varphi(n)} - \frac{k}{d} = \frac{1}{d\varphi(n)}\\ &If \frac{1}{d\varphi(n)} is very small\ &\frac{e}{\varphi(n)} and \frac{k}{d} are very close\\ &\because \varphi(n) \approx n\ &\therefore \frac{e}{n} - \frac{k}{d} = \frac{1}{d\varphi(n)} \end{aligned} $$
from RSAwienerHacker import hack_RSA
import libnum
n = 114566998957451783636756389276471274690612644037126335470456866443567982817002189902938330449132444558501556339080521014838959058380963759366933946623103869574657553262938223064086322963492884606713973124514306815995276393344755433548846003574038937940253826360659447735554684257197194046341849089254659225497
e = 35489734227210930185586918984451799765619374486784192218215354633053183935617953856556709715097294481614236703293033675674496036691242573294182072757562322996800390363453350727372642264982749305833933966045097125311467413670410802534093354414115267442785896373815076066721029449240889291057288090241124904705
c = 60503455347700500866544596012233537789678841391057706123172519773588895502922586197178148979273264437566411675346207472455036341903878112074983509557751805365618433536738111588239911292341288514123006967218545943520736254346030465088445419278775539026233686559207400401082452551955780877227801939191694370380
d=hack_RSA(e,n)
print(libnum.n2s(pow(enc ,d ,n)))
import gmpy2
from Crypto.Util.number import long_to_bytes
def transform(x, y):
"""
将分数 x/y 转为连分数形式。
返回连分数的各项。
"""
res = []
while y:
res.append(x // y)
x, y = y, x % y
return res
def continued_fraction(sub_res):
"""
根据连分数项计算渐进分数的分子和分母。
sub_res: 连分数的部分序列。
返回分母和分子。
"""
numerator, denominator = 1, 0
# 从后往前计算
for i in reversed(sub_res):
denominator, numerator = numerator, i * numerator + denominator
return denominator, numerator
def sub_fraction(x, y):
"""
计算分数 x/y 的所有渐进分数。
返回每个渐进分数的分母和分子。
"""
res = transform(x, y)
return [continued_fraction(res[:i]) for i in range(1, len(res))]
def get_pq(a, b, c):
"""
根据维达定理由 p+q 和 pq 求解 p 和 q。
a, b, c: 二次方程 ax^2 + bx + c = 0 的系数。
返回方程的两个根。
"""
# 判别式的平方根
discriminant = gmpy2.isqrt(b * b - 4 * a * c)
x1 = (-b + discriminant) // (2 * a)
x2 = (-b - discriminant) // (2 * a)
return x1, x2
def wiener_attack(e, n):
"""
实现维纳攻击，用于破解 RSA 私钥。
e: 公钥指数。
n: 公钥模数。
返回找到的私钥 d，如果攻击无效则返回 None。
"""
for d, k in sub_fraction(e, n):
# 跳过无效的渐进分数
if k == 0:
continue
# 检查 (e*d - 1) 是否可以整除 k
if (e * d - 1) % k != 0:
continue
# 计算 φ(n)
phi = (e * d - 1) // k
# 根据 φ(n) 求解 p 和 q
p, q = get_pq(1, n - phi + 1, n)
# 验证分解是否正确
if p * q == n:
# 确保结果为正数
p, q = abs(int(p)), abs(int(q))
# 计算私钥 d
d = gmpy2.invert(e, (p - 1) * (q - 1))
return d
print("维纳攻击无效")
return None
# 示例数据
if __name__ == "__main__":
n = 114566998957451783636756389276471274690612644037126335470456866443567982817002189902938330449132444558501556339080521014838959058380963759366933946623103869574657553262938223064086322963492884606713973124514306815995276393344755433548846003574038937940253826360659447735554684257197194046341849089254659225497
e = 35489734227210930185586918984451799765619374486784192218215354633053183935617953856556709715097294481614236703293033675674496036691242573294182072757562322996800390363453350727372642264982749305833933966045097125311467413670410802534093354414115267442785896373815076066721029449240889291057288090241124904705
c = 60503455347700500866544596012233537789678841391057706123172519773588895502922586197178148979273264437566411675346207472455036341903878112074983509557751805365618433536738111588239911292341288514123006967218545943520736254346030465088445419278775539026233686559207400401082452551955780877227801939191694370380
# 执行维纳攻击
d = wiener_attack(e, n)
if d:
print("找到私钥 d =", d)
# 解密密文
print("解密结果:", long_to_bytes(pow(c, d, n)))
CBC 类¶
填充 Oracle 攻击¶
话不多说，直接上题（Codegate CTF）
先来了解下 CBC 模式
加密过程：
- 初始化向量（Initialization Vector，IV）：加密过程始于一个随机或伪随机生成的 IV，这个 IV 与第一个明文块进行 XOR 操作，然后将结果输入加密算法，生成第一个密文块
- 后续块处理：对于后续的每个明文块，先与前一个密文块进行 XOR 操作，然后将结果输入加密算法，生成新的密文块
数学表达式：C_i = E_K(P_i ⊕ C_{i-1})，其中 C_0 = IV
解密过程：
- 第一块解密：将第一个密文块输入解密算法，得到的结果与 IV 进行 XOR 操作，恢复第一个明文块
- 后续块解密：对于后续的每个密文块，先将其输入解密算法，得到的结果与前一个密文块进行 XOR 操作，恢复对应的明文块
数学表达式：P_i = D_K(C_i) ⊕ C_{i-1}，其中 C_0 = IV
我们可以看到一个有效请求（HTTP 状态代码 200），然后是一系列 500 请求，以及一个 403 请求
图片中显示的 URL 是 base64 URLSafe 编码的，解码后剩下 30 个字节
由于攻击者开始更改第 15 个字节，这意味着这里的块大小也是 15 个字节
500 个服务器错误显然是由不正确的填充序列引起的，但是我们可以看到一个 403 错误
这意味着攻击者猜到了正确的填充序列，攻击者只需从字节 0x00 循环到 0xFF，直到响应不同于 500
当猜出第一个值时，攻击者必须将其与 0x01 进行异或以获得中间值
现在攻击者需要找到中间值的第二个字节，因此填充需要为 0x02
已经找到的值首先与 0x02 进行异或，第二个字节再次从 0x00 循环到 0xFF，直到找到有效序列
这一切都可以在日志文件中看到，因为有 16 个请求导致 HTTP 状态代码 403（在数千个其他请求中）
这里的挑战是猜测攻击者使用第一个（200）请求检索了什么
为了解密，我们需要按照上面描述的过程找到所有中间值
然后我们需要将中间值与 200 请求的初始化向量 (IV) 进行异或 - IV 是请求的前 16 个字节
use MIME::Base64::URLSafe;
$final = "8LU7LaBB_KSe8LmDkGCzRaIeorRgX4RBdRsmYdZzjx0";
# 使用unpack 'c*'将二进制数据解包成字节数组，存储在@final_bytes中
@final_bytes = unpack 'c*', urlsafe_b64decode($final);
$i = 1;
# <> 表示从标准输入或文件中读取行
while (<>) {
@bytes = unpack 'c*', urlsafe_b64decode($_);
printf "step: %d, byte: %x\n", $i, $bytes[16 - $i];
$inter[16 - $i] = $bytes[16 - $i] ^ $i;
printf "intermediate: %x\n", $inter[16 - $i];
$i++;
}
print "Decoding final string:\n";
for ($i = 0; $i < 16; $i++) {
print chr($inter[$i] ^ $final_bytes[$i]);
}
print "\n";
现在我们只需要将 16 个 403 请求作为 STDIN 输入，程序就会为我们解决这个难题
ECC 类¶
公钥 k¶
话不多说，直接上题（攻防世界）
阿贝尔群性质：
阿贝尔群，又称交换群，是代数学中一类重要的代数结构
- 封闭性：∀ a,b ∈ G ⇒ a + b ∈ G
- 结合律：∀ a,b,c ∈ G ⇒ (a + b) + c = a + (b + c)
- 单位元：∃ e ∈ G 使得 ∀ a ∈ G ⇒ a + e = e + a = a，e 就是单位元
- 逆元：∀ a ∈ G ⇒ ∃ b ∈ G 使得 a + b = 0
- 交换律：∀ a,b ∈ G ⇒ a + b = b + a
椭圆曲线的定义：
椭圆曲线的加法：
过曲线上的两点 A、B 画一条直线，找到直线与椭圆曲线的交点，交点关于x轴对称位置的点，定义为 A+B，即为加法
如下图所示：A + B = C
这个加法运算具有阿贝尔群性质
椭圆曲线的二倍运算：
上述方法无法解释 A + A，即两点重合的情况
因此在这种情况下，将椭圆曲线在 A 点的切线，与椭圆曲线的交点，交点关于 x 轴对称位置的点，定义为 A + A，即 2A（二倍运算）
同余运算：
同余就是有相同的余数，两个整数 a、 b
若它们除以正整数 m 所得的余数相等，则称 a， b 对于模 m 同余
有限域：
椭圆曲线是连续的，并不适合用于加密；所以必须把椭圆曲线变成离散的点，要把椭圆曲线定义在有限域上
而椭圆曲线密码所使用的椭圆曲线是定义在有限域内
有限域最常见的例子是有限域 GF(p)，指给定某质数 p，由 0,1,2...p-1 共 p 个元素组成的整数集合中加法、二倍运算
例如 GF(233) 就是
椭圆曲线加解密算法原理：
设私钥、公钥分别为 d、Q，即 Q = dG，其中 G 为基点，椭圆曲线上的已知 G 和 dG，求 d 是非常困难的，也就是说已知公钥和基点，想要算出私钥是非常困难的
公钥加密：选择随机数 r，将消息 M 生成密文 C，该密文是一个点对，C = {rG, M + rQ}，其中 Q 为公钥
私钥解密：M + rQ - d(rG) = M + r(dG) - d(rG) = M，其中 d、Q 分别为私钥、公钥
椭圆曲线签名算法原理：
椭圆曲线签名算法（ECDSA），设私钥、公钥分别为 d、Q，即 Q = dG，其中 G 为基点
私钥签名：
- 选择随机数 r，计算点 rG(x, y)
- 根据随机数 r、消息 M 的哈希 h、私钥 d，计算 s = (h + dx)/r
- 将消息 M、和签名 {rG, s} 发给接收方
公钥验证签名：
- 接收方收到消息 M、以及签名 {rG=(x,y), s}
- 根据消息求哈希 h
- 使用发送方公钥 Q 计算：hG/s + xQ/s，并与 rG 比较，如相等即验签成功
- 原理：hG/s + xQ/s = hG/s + x(dG)/s = (h+xd)G/s = r(h+xd)G / (h+dx) = rG
签名过程：
假设要签名的消息是一个字符串："Hello World!"
DSA 签名的第一个步骤是对待签名的消息生成一个消息摘要，不同的签名算法使用不同的消息摘要算法
而 ECDSA256 使用 SHA256 生成 256 比特的摘要
摘要生成结束后，应用签名算法对摘要进行签名：
- 产生一个随机数 k
- 利用随机数 k，计算出两个大数 r 和s，将 r 和 s 拼在一起就构成了对消息摘要的签名
这里需要注意的是，因为随机数 k 的存在，对于同一条消息，使用同一个算法，产生的签名是不一样的
从函数的角度来理解，签名函数对同样的输入会产生不同的输出
因为函数内部会将随机值混入签名的过程
现在来做题
已知椭圆曲线加密 Ep(a,b) 参数为
p = 15424654874903
a = 16546484
b = 4548674875
G(6478678675,5636379357093)
私钥为 k = 546768
求公钥 K(x,y)
脚本解题如下：
import collections
import random
EllipticCurve = collections.namedtuple('EllipticCurve', 'name p a b g n h')
curve = EllipticCurve(
'secp256k1',
# Field characteristic.
p=int(input('p=')),
# Curve coefficients.
a=int(input('a=')),
b=int(input('b=')),
# Base point.
g=(int(input('Gx=')),
int(input('Gy='))),
# Subgroup order.
n=int(input('k=')),
# Subgroup cofactor.
h=1,
)
# Modular arithmetic ##########################################################
def inverse_mod(k, p):
"""Returns the inverse of k modulo p.
This function returns the only integer x such that (x * k) % p == 1.
k must be non-zero and p must be a prime.
"""
if k == 0:
raise ZeroDivisionError('division by zero')
if k < 0:
# k ** -1 = p - (-k) ** -1 (mod p)
return p - inverse_mod(-k, p)
# Extended Euclidean algorithm.
s, old_s = 0, 1
t, old_t = 1, 0
r, old_r = p, k
while r != 0:
quotient = old_r // r
old_r, r = r, old_r - quotient * r
old_s, s = s, old_s - quotient * s
old_t, t = t, old_t - quotient * t
gcd, x, y = old_r, old_s, old_t
assert gcd == 1
assert (k * x) % p == 1
return x % p
# Functions that work on curve points #########################################
def is_on_curve(point):
"""Returns True if the given point lies on the elliptic curve."""
if point is None:
# None represents the point at infinity.
return True
x, y = point
return (y * y - x * x * x - curve.a * x - curve.b) % curve.p == 0
def point_neg(point):
"""Returns -point."""
assert is_on_curve(point)
if point is None:
# -0 = 0
return None
x, y = point
result = (x, -y % curve.p)
assert is_on_curve(result)
return result
def point_add(point1, point2):
"""Returns the result of point1 + point2 according to the group law."""
assert is_on_curve(point1)
assert is_on_curve(point2)
if point1 is None:
# 0 + point2 = point2
return point2
if point2 is None:
# point1 + 0 = point1
return point1
x1, y1 = point1
x2, y2 = point2
if x1 == x2 and y1 != y2:
# point1 + (-point1) = 0
return None
if x1 == x2:
# This is the case point1 == point2.
m = (3 * x1 * x1 + curve.a) * inverse_mod(2 * y1, curve.p)
else:
# This is the case point1 != point2.
m = (y1 - y2) * inverse_mod(x1 - x2, curve.p)
x3 = m * m - x1 - x2
y3 = y1 + m * (x3 - x1)
result = (x3 % curve.p,
-y3 % curve.p)
assert is_on_curve(result)
return result
def scalar_mult(k, point):
"""Returns k * point computed using the double and point_add algorithm."""
assert is_on_curve(point)
if k < 0:
# k * point = -k * (-point)
return scalar_mult(-k, point_neg(point))
result = None
addend = point
while k:
if k & 1:
# Add.
result = point_add(result, addend)
# Double.
addend = point_add(addend, addend)
k >>= 1
assert is_on_curve(result)
return result
# Keypair generation and ECDHE ################################################
def make_keypair():
"""Generates a random private-public key pair."""
private_key = curve.n
public_key = scalar_mult(private_key, curve.g)
return private_key, public_key
private_key, public_key = make_keypair()
print("private key:", hex(private_key))
print("public key: (0x{:x}, 0x{:x})".format(*public_key))
使用工具解题：
RC4¶
话不多说，直接上题（攻防世界）
RC4 特点：
- 加密解密使用相同的密钥
- 加密过程是将明文与密钥流进行按位异或(XOR)
- 密钥流长度与明文长度相同
算法组成：
- KSA：密钥调度算法
- PRGA ：伪随机生成算法
首先是 KSA：
- S 盒初始化
- 临时数组 T 填充
key = "key" # 示例密钥
t = [key[i % len(key)] for i in range(256)] # 列表推导式，用于生成一个长度为 256 的列表
# Key: 'K'(75), 'E'(69), 'Y'(89)
# T = [75, 69, 89, 75, 69, 89, ..., 75, 69, 89] (重复到 256 字节)
- S 盒置换
j = 0
for i in range(256):
j = (j + s[i] + ord(t[i])) % 256 # 计算交换位置
s[i], s[j] = s[j], s[i] # 交换元素
# 第一轮
# j = (0 + S[0] + T[0]) % 256 = (0 + 0 + 75) % 256 = 75
# 交换 S[0] 和 S[75]：S[0]=75, S[75]=0
# 第二轮
# j = (75 + S[1] + T[1]) % 256 = (75 + 1 + 69) % 256 = 145
# 交换 S[1] 和 S[145]：S[1]=203, S[145]=1 (假设 S[145] 初始为 203)
PRGA 伪随机生成算法：
- 密钥生成过程
i = j = 0
key_stream = []
for _ in range(plaintext_length):
i = (i + 1) % 256
j = (j + s[i]) % 256
s[i], s[j] = s[j], s[i] # 继续交换
k = s[(s[i] + s[j]) % 256]
key_stream.append(k) # 生成密钥流字节
- 加密/解密操作
算法图示：
+-------------------+ +-------------------+
| 密钥K | | 明文P |
+-------------------+ +-------------------+
| |
v v
+-------------------+ +-------------------+
| KSA算法 | | PRGA算法 |
| (初始化S盒) | | (生成密钥流) |
+-------------------+ +-------------------+
| |
v v
+-------------------+ +-------------------+
| 初始化后的S盒 |--->| 密钥流KS |
+-------------------+ +-------------------+
|
v
+-------------------+
| P XOR KS = C |
| (加密/解密) |
+-------------------+
|
v
+-------------------+
| 密文C/明文P |
+-------------------+
下载附件先看加密的伪代码代码
get buf unsign s[256]
get buf t[256]
we have key:hello world
we have flag:????????????????????????????????
for i:0 to 256
set s[i]:i
for i:0 to 256
set t[i]:key[(i)mod(key.lenth)]
for i:0 to 256
set j:(j+s[i]+t[i])mod(256)
swap:s[i],s[j]
for m:0 to 37
set i:(i + 1)mod(256)
set j:(j + S[i])mod(256)
swap:s[i],s[j]
set x:(s[i] + (s[j]mod(256))mod(256))
set flag[m]:flag[m]^s[x]
fprint flagx to file
可以直接复制 16 进制去在线网站解密
由于 RC4 是对称加密算法，所以只需要复现一遍相同算法并作用在密文上即可得出明文
编写脚本解密：
s = list(range(256))
t = []
key = "hello world"
for i in range(256):
t.append(key[i % len(key)]) # fill t with key (by circle
print(t)
j = 0
for i in range(256):
j = (j + s[i] + ord(t[i])) % 256
s[i], s[j] = s[j], s[i]
print(s)
c = open("enc.txt","rb").read()
i = 0
j = 0
flag = ""
for ci in c:
i = (i + 1) % 256
j = (j + s[i]) % 256
s[i], s[j] = s[j], s[i]
x = (s[i] + (s[j] % 256)) % 256
flag += chr(ci ^ s[x])
print(flag)
RC 类¶
RC4¶
话不多说，直接上题（攻防世界）
RC4 特点：
- 加密解密使用相同的密钥
- 加密过程是将明文与密钥流进行按位异或(XOR)
- 密钥流长度与明文长度相同
算法组成：
- KSA：密钥调度算法
- PRGA ：伪随机生成算法
首先是 KSA：
- S 盒初始化
- 临时数组 T 填充
key = "key" # 示例密钥
t = [key[i % len(key)] for i in range(256)] # 列表推导式，用于生成一个长度为 256 的列表
# Key: 'K'(75), 'E'(69), 'Y'(89)
# T = [75, 69, 89, 75, 69, 89, ..., 75, 69, 89] (重复到 256 字节)
- S 盒置换
j = 0
for i in range(256):
j = (j + s[i] + ord(t[i])) % 256 # 计算交换位置
s[i], s[j] = s[j], s[i] # 交换元素
# 第一轮
# j = (0 + S[0] + T[0]) % 256 = (0 + 0 + 75) % 256 = 75
# 交换 S[0] 和 S[75]：S[0]=75, S[75]=0
# 第二轮
# j = (75 + S[1] + T[1]) % 256 = (75 + 1 + 69) % 256 = 145
# 交换 S[1] 和 S[145]：S[1]=203, S[145]=1 (假设 S[145] 初始为 203)
PRGA 伪随机生成算法：
- 密钥生成过程
i = j = 0
key_stream = []
for _ in range(plaintext_length):
i = (i + 1) % 256
j = (j + s[i]) % 256
s[i], s[j] = s[j], s[i] # 继续交换
k = s[(s[i] + s[j]) % 256]
key_stream.append(k) # 生成密钥流字节
- 加密/解密操作
算法图示：
+-------------------+ +-------------------+
| 密钥K | | 明文P |
+-------------------+ +-------------------+
| |
v v
+-------------------+ +-------------------+
| KSA算法 | | PRGA算法 |
| (初始化S盒) | | (生成密钥流) |
+-------------------+ +-------------------+
| |
v v
+-------------------+ +-------------------+
| 初始化后的S盒 |--->| 密钥流KS |
+-------------------+ +-------------------+
|
v
+-------------------+
| P XOR KS = C |
| (加密/解密) |
+-------------------+
|
v
+-------------------+
| 密文C/明文P |
+-------------------+
下载附件先看加密的伪代码代码
get buf unsign s[256]
get buf t[256]
we have key:hello world
we have flag:????????????????????????????????
for i:0 to 256
set s[i]:i
for i:0 to 256
set t[i]:key[(i)mod(key.lenth)]
for i:0 to 256
set j:(j+s[i]+t[i])mod(256)
swap:s[i],s[j]
for m:0 to 37
set i:(i + 1)mod(256)
set j:(j + S[i])mod(256)
swap:s[i],s[j]
set x:(s[i] + (s[j]mod(256))mod(256))
set flag[m]:flag[m]^s[x]
fprint flagx to file
可以直接复制 16 进制去在线网站解密
由于 RC4 是对称加密算法，所以只需要复现一遍相同算法并作用在密文上即可得出明文
编写脚本解密：
s = list(range(256))
t = []
key = "hello world"
for i in range(256):
t.append(key[i % len(key)]) # fill t with key (by circle
print(t)
j = 0
for i in range(256):
j = (j + s[i] + ord(t[i])) % 256
s[i], s[j] = s[j], s[i]
print(s)
c = open("enc.txt","rb").read()
i = 0
j = 0
flag = ""
for ci in c:
i = (i + 1) % 256
j = (j + s[i]) % 256
s[i], s[j] = s[j], s[i]
x = (s[i] + (s[j] % 256)) % 256
flag += chr(ci ^ s[x])
print(flag)
LFSR 类¶
爆破¶
话不多说，直接上题（攻防世界）
基本原理：
LFSR 由一组位（bit）和一个反馈函数组成；每次操作时：
- 最右边的位作为输出
- 所有位向右移动一位
- 最左边的位由反馈函数计算得出
示例：
让我们以一个 4 位 LFSR 为例，使用反馈多项式：x⁴ + x + 1（对应抽头位置为第 4 位和第 1 位）
初始设置：
- 初始状态(种子): 1101
-
反馈函数: 新位 = bit4 ⊕ bit1
-
初始状态: [1, 1, 0, 1]
- 输出: 1
- 计算新位: 1 ⊕ 1 = 0
- 新状态: [0, 1, 1, 0]
- 状态: [0, 1, 1, 0]
- 输出: 0
- 计算新位: 0 ⊕ 0 = 0
- 新状态: [0, 0, 1, 1]
- 状态: [0, 0, 1, 1]
- 输出: 1
- 计算新位: 0 ⊕ 1 = 1
- 新状态: [1, 0, 0, 1]
- 状态: [1, 0, 0, 1]
- 输出: 1
- 计算新位: 1 ⊕ 1 = 0
- 新状态: [0, 1, 0, 0]
- 状态: [0, 1, 0, 0]
- 输出: 0
- 计算新位: 0 ⊕ 0 = 0
- 新状态: [0, 0, 1, 0]
- 状态: [0, 0, 1, 0]
- 输出: 0
- 计算新位: 0 ⊕ 0 = 0
- 新状态: [0, 0, 0, 1]
- 状态: [0, 0, 0, 1]
- 输出: 1
- 计算新位: 0 ⊕ 1 = 1
- 新状态: [1, 0, 0, 0]
- 状态: [1, 0, 0, 0]
- 输出: 0
- 计算新位: 1 ⊕ 0 = 1
- 新状态: [1, 1, 0, 0]
下载附件
from flag import flag
assert flag.startswith("flag{")
assert flag.endswith("}")
assert len(flag)==25
# LFSR 核心函数
def lfsr(R,mask):
output = (R << 1) & 0xffffff # 左移 1 位，保留 24 位
i = (R & mask) & 0xffffff # R & mask 找出所有参与反馈的位（mask 中为 1 的位）
lastbit = 0
while i != 0:
lastbit ^= (i & 1) # 计算所有反馈位的异或
i = i >> 1 # 右移检查下一位
output ^= lastbit # 将计算出的反馈位放入输出的最高位
return (output,lastbit)
# 将 flag 中的二进制字符串转为整数
R = int(flag[5:-1],2)
mask = 0b1010011000100011100
f=open("key","ab")
for i in range(12):
tmp=0
for j in range(8):
(R,out) = lfsr(R,mask) # 调用 LFSR 生成 1 位
tmp=(tmp << 1)^out # 将位拼接到当前字节
f.write(chr(tmp))
f.close()
核心逻辑：
- 将寄存器
R左移 1 位，保留最低的 24 位 - 用
R & mask选出 feedback 位，再对这些位做异或运算（按位累计异或）来生成lastbit - 把
lastbit作为最高位反馈回output - 返回新的寄存器状态
output和生成的位lastbit
这正是一个标准的 24 位 LFSR 反馈函数
后续：
- 共生成 12 个字节 的 key（即 96 位）
- 每个字节由 8 次
lfsr调用产生 8 位out组成 - 最后将 12 字节写入
key文件
解题脚本：
from Crypto.Util.number import*
f = open('key','rb').read()
key = bytes_to_long(f)
bin_out = bin(key)[2:].zfill(12*8) # 补满 12 字节
print(bin_out) # 选取前 19 位作为 key 进行恢复
key = '0101010100111000111' # 示例，实际应为 bin_out 前 19 位
mask = '1010011000100011100'
# 每轮根据后推的 out 和 LFSR 反馈函数，反推出上一个输入位
R = ''
tem = key
for i in range(19):
output = ' ' + key[:18] # ' '占位
ans = int(tem[-1-i]) ^ int(output[-3]) ^ int(output[-4]) ^ int(output[-5]) ^ int(output[-9]) ^ int(output[-13]) ^ int(output[-14]) ^ int(output[-17])
R += str(ans)
key = str(ans) + key[:18] # 将新位插入到前面形成新的 19 位
print('flag{'+R[::-1]+'}')
Sage 求解¶
话不多说，直接上题（攻防世界）
下载附件
from secret import secret
# secret 是一个只包含字符 '0' 和 '1' 的 128 位二进制字符串
for b in secret: assert(b == '0' or b == '1')
assert(len(secret) == 128)
# 把字符串 '010101' 转换为整数列表 [0,1,0,1,0,1]
def string2bits(s):
return [int(b) for b in s]
# 这是一个线性反馈函数（非模 2）
def lfsr(state, mask):
assert(len(state) == 128)
assert(len(mask) == 128)
output = 0
for i in range(128):
# 两个向量点积
output = output + (state[i] * mask[i])
return output
if __name__ == '__main__':
initState = [0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0]
mask = string2bits(secret)
# 1. 取当前位置往后的 128 位作为 state
# 2. 与 mask 点积得到新的 output
# 3. 把这个 output 加到 initState 后面
# 4. 执行 256 次迭代
for i in range(256):
state = initState[i:]
output = lfsr(state, mask)
initState += [output]
outputState = initState[128:]
print('outputState =', outputState)
#
# outputState = [31, 66, 128, 222, 385, 664, 1143, 2000, 3458, 6003, 10379, 17942, 31047, 53687, 92924, 160797, 278304, 481638, 833479, 1442422, 2496163, 4319845, 7475835, 12937561, 22389578, 38746915, 67054735, 116043520, 200822710, 347539886, 601445745, 1040850538, 1801275628, 3117252874, 5394657302, 9335889442, 16156509611, 27960142496, 48387281659, 83738092531, 144915522009, 250787996657, 434008851435, 751087316130, 1299817167363, 2249438425629, 3892834588915, 6736864173067, 11658686709797, 20176297502410, 34916709837729, 60426182042628, 104572380769600, 180970937597032, 313184800936842, 541991553121913, 937960088661442, 1623215570164618, 2809105439634215, 4861383488449105, 8413016146818879, 14559402864389777, 25196220721365800, 43604091771673155, 75460397027739861, 130590302153314191, 225997048627046433, 391106116962451401, 676840674047358730, 1171327366605398299, 2027076463289970382, 3508019282374090135, 6070910253447116278, 10506199749411485204, 18181825882182859769, 31465115864423937634, 54452920337985370536, 94235169707018163674, 163081560265112209496, 282225790871820528073, 488414489680745790033, 845240659945376349091, 1462757121910708796880, 2531419155626961478438, 4380824981460105751921, 7581370898424646092677, 13120173698498971899800, 22705518590912550882405, 39293730885686099313323, 68000969928723717268434, 117681162033195064953557, 203656740661184789826464, 352444412513853856490154, 609933476834387348179796, 1055539066458205919344242, 1826695472762162772755920, 3161243819621244340994611, 5470787351316040252901913, 9467638673598260118507327, 16384512191330329194463349, 28354719587732695891973236, 49070128760035595469947547, 84919814815174884654495265, 146960587438213290271803310, 254327147405947343219170013, 440133637427387650641676733, 761686751771954639615932308, 1318160346062225166536927204, 2281182774793880566386854202, 3947770745464875128215489476, 6831935621711193478803584270, 11823215517979626989252654459, 20461027873324936552011726278, 35409458704049766870463574070, 61278923692217093991616774374, 106048118957748860598268928024, 183524821535095103500935105397, 317604503036094959823791626415, 549640204006492782256703506357, 951196695803666227643791343005, 1646122586216645151673646795131, 2848747878127492747395146497119, 4929987925010971381846789176787, 8531741656523753626888968333475, 14764866932914585711739993009471, 25551792860485990447357753377411, 44219438031623458174827090101591, 76525303351860239321171606062486, 132433208420836012247860425341878, 229186346534231007543300455047052, 396625454174562824696341867974807, 686392332170111774628387415187708, 1187857281228776953526538661167132, 2055682813511567389589959681437591, 3557524878237416677051445431119245, 6156583679200434562674367324375645, 10654464521349051207718915685250792, 18438410026033851006551039004948926, 31909155416202798852780253976608864, 55221366589513932226781115179478434, 95565027912492621164419094117570641, 165382987128929746587819720020389833, 286208595645816231325692474821432127, 495307054513959920117280296979778603, 857168799202977606481906830566592959, 1483399728776458203402121501599814357, 2567142851419860475561591348189292465, 4442647717774532025797522076302827645, 7688360128977964468508623330874749520, 13305327189541069887965447505836108943, 23025941637865784521234444191415083701, 39848248807227476288131461546822173104, 68960607908058729168472941626927516912, 119341892941264496254850267375680858596, 206530769418287872448439164819365157712, 357418151038572249261836365381689027787, 618540932431735991718001801386896334770, 1070434962471260463170389697079661487176, 1852474022011964581139009223827365513544, 3205855677870125101423860144920010424249, 5547991769498476629256700835469967207037, 9601247144996961660705018593534913225922, 16615732425220501988109900409620796156745, 28754864847988594478375696246052761203187, 49762612400465240380187427652132912229336, 86118213596547492163397334421181607606370, 149034513167786192667574788821667110253623, 257916243121530494722068502259305736264048, 446344856986474817826595353109273441918350, 772435768089263602359077702861161388353409, 1336762385595787378549468975393213339116484, 2313375104267880490155624917599100889633507, 4003482167596451918353914186255524345816532, 6928348730257112541629154203810355027525535, 11990066177033590775605142065871666200189459, 20749776393589512464840020374644649655647874, 35909161302935015278730531942138798319507636, 62143699335409560081369603141161471393159562, 107544682943462043814216772302622710407400704, 186114746194704481727730115452186541297539854, 322086576510057527551600558671512063007190557, 557396793585831655018738502556644467159583633, 964620099559052960425720416252526682882655111, 1669352868873354804885622348664567494237803783, 2888949755545809136243688064556192446919868175, 4999560515746991945989073252770067125902428535, 8652142635098861248148452777057412533362877977, 14973230535426489152060521332311783517581989420, 25912382876992006096351135796067625851883928825, 44843468133024591960270046213401958144446811548, 77605237763877474989955856305494246316739147127, 134302122006319171731632762048131880552676359659, 232420652202367984596938247872208285088912788686, 402222680946414142984184322215356821073359953948, 696078784456971603910909918744734815016448573082, 1204620468022900362280402553035290601874308600586, 2084692860035604927076197374205039877760447754956, 3607729103106034863624554004184342562208475089341, 6243466138784576918107250594832177417637788944304, 10804821623826866941723224844111388709787418308073, 18698615116609470739339911758664365362637188157227, 32359461308280335893458609544003265039362932173740, 56000657248244594858300036379967633467510318826268, 96913653239119041752111865895809664169241405330164, 167716892009274048794745102986623447430717183044189, 290247606246426020117292750048691625438809474898504, 502296888062545512718475829352732508523042936581530, 869265269816240261877029457458234318249621243667628, 1504333646627354107869007496936781479204707239575364, 2603370684363759081777877568090078592049534352669947, 4505342904082185194291963661562434728467247085801567, 7796859204598587173314308958000104480418858953375158, 13493093589225451977147040588861591346827624626553088, 23350886533928418622148518003626067086836308029229306, 40410592153292809121198774051487713973447271440824879, 69933788415571610361075397290260005189363125951186151, 121026060286409890014591649872661507384922097295622585, 209445356819655999941471437498154462693217873859873519, 362462079567824464738504374835340908769751488853277318, 627269857492024846036766185061792395514128412691597750, 1085541071185182881358902065797900004206275433304525877, 1878616361292087979017649753948129817575491489985996469, 3251097104102362704835900720328806405351210311448488910, 5626285705844227224482132571164442587287950705132698177, 9736741115435595736854097976874400909429981720207988487, 16850215667245180941552990697851306753178430167486844006, 29160657006948951882262364132481449161390275730087294685, 50464868454466647556267645846637274956572498586114427735, 87333524327649631040132103644841977096784627243509857937, 151137706390139040826448707126591974417399010694640174718, 261555988593488478677610370284679511774525269175612894617, 452643730033345117036459086235348615186246366652477694168, 783336475835524143955537154153262203019092265959952337070, 1355626939379487620769121922144227585175531097052439217983, 2346021735820790423533561047507688175516954900918138334291, 4059979796110323903393797058491537625611005518946149411026, 7026122432346967683382009847205881024752630926437218981740, 12159271452933065576710291263470354882115951853620136774055, 21042599768180623908382939506716338579508214228553692875423, 36415915765826987773364669427220163018133640081486671468436, 63020678797925209300085103082659626905494796721119527734083, 109062366622625198169859916735972641477602693706580750774247, 188741220186912829686057249397861922209555075583934877024777, 326631901551406455092777938653826814900794821912935940782874, 565262845103114204256414747869081614169923740442179762058936, 978232936025018959853100287323851115023773163216042197843195, 1692910980111501346802672231436092377546116455476214539222026, 2929718966760270262844895994547637314231078419236801672684198, 5070114923366815738216357619638190602226980891746062079428250, 8774242726964718704518978915749604855301897112378619823447909, 15184534590503864395968205111669668293209355696392197598100449, 26278061583779512058870924747917968681797893736357134971437061, 45476304623307832769415233578427592641287934525440233150419102, 78700412341998941621862709864667467345902574612843786168968091, 136197409928206718914848388530217366761295027423898231594892758, 235700600786468895717413188934153824796333855958950958366797470]
\[
\begin{aligned}
&First:\ output\ =\ \sum{state_i}\ *\ mask_i\\\\
&Change\ \ to\ \ matrix\ \ multiplication\ \ form\\\\
&out\ =\ \sum{state} * \ Mask\\
&(State\ \ is\ \ 1\ *\ 128\ vector,\ Mask\ \ is\ \ 128\ *\ 1\ vector)\\\\
&256\ \ rounds\ \ of\ \ loops\ \ finally\ \ output\ \ the\ \ last\ \ 256\ \ elements\ \ of\ \ the\ \ initState\ \ array\\
&named\ \ outputState\\
&\therefore\ \ outputState_{0...127}\ *\ Mask\ =\ outputState_{128}\\
&\therefore\ \ outputState_{0...128}\ *\ Mask\ =\ outputState_{129}\\
&\therefore\ \ outputState_{127...254}\ *\ Mask\ =\ outputState_{255}\\
\end{aligned}
\]
解题代码
import hashlib
#sage
outputState = [31, 66, 128, 222, 385, 664, 1143, 2000, 3458, 6003, 10379, 17942, 31047, 53687, 92924, 160797, 278304, 481638, 833479, 1442422, 2496163, 4319845, 7475835, 12937561, 22389578, 38746915, 67054735, 116043520, 200822710, 347539886, 601445745, 1040850538, 1801275628, 3117252874, 5394657302, 9335889442, 16156509611, 27960142496, 48387281659, 83738092531, 144915522009, 250787996657, 434008851435, 751087316130, 1299817167363, 2249438425629, 3892834588915, 6736864173067, 11658686709797, 20176297502410, 34916709837729, 60426182042628, 104572380769600, 180970937597032, 313184800936842, 541991553121913, 937960088661442, 1623215570164618, 2809105439634215, 4861383488449105, 8413016146818879, 14559402864389777, 25196220721365800, 43604091771673155, 75460397027739861, 130590302153314191, 225997048627046433, 391106116962451401, 676840674047358730, 1171327366605398299, 2027076463289970382, 3508019282374090135, 6070910253447116278, 10506199749411485204, 18181825882182859769, 31465115864423937634, 54452920337985370536, 94235169707018163674, 163081560265112209496, 282225790871820528073, 488414489680745790033, 845240659945376349091, 1462757121910708796880, 2531419155626961478438, 4380824981460105751921, 7581370898424646092677, 13120173698498971899800, 22705518590912550882405, 39293730885686099313323, 68000969928723717268434, 117681162033195064953557, 203656740661184789826464, 352444412513853856490154, 609933476834387348179796, 1055539066458205919344242, 1826695472762162772755920, 3161243819621244340994611, 5470787351316040252901913, 9467638673598260118507327, 16384512191330329194463349, 28354719587732695891973236, 49070128760035595469947547, 84919814815174884654495265, 146960587438213290271803310, 254327147405947343219170013, 440133637427387650641676733, 761686751771954639615932308, 1318160346062225166536927204, 2281182774793880566386854202, 3947770745464875128215489476, 6831935621711193478803584270, 11823215517979626989252654459, 20461027873324936552011726278, 35409458704049766870463574070, 61278923692217093991616774374, 106048118957748860598268928024, 183524821535095103500935105397, 317604503036094959823791626415, 549640204006492782256703506357, 951196695803666227643791343005, 1646122586216645151673646795131, 2848747878127492747395146497119, 4929987925010971381846789176787, 8531741656523753626888968333475, 14764866932914585711739993009471, 25551792860485990447357753377411, 44219438031623458174827090101591, 76525303351860239321171606062486, 132433208420836012247860425341878, 229186346534231007543300455047052, 396625454174562824696341867974807, 686392332170111774628387415187708, 1187857281228776953526538661167132, 2055682813511567389589959681437591, 3557524878237416677051445431119245, 6156583679200434562674367324375645, 10654464521349051207718915685250792, 18438410026033851006551039004948926, 31909155416202798852780253976608864, 55221366589513932226781115179478434, 95565027912492621164419094117570641, 165382987128929746587819720020389833, 286208595645816231325692474821432127, 495307054513959920117280296979778603, 857168799202977606481906830566592959, 1483399728776458203402121501599814357, 2567142851419860475561591348189292465, 4442647717774532025797522076302827645, 7688360128977964468508623330874749520, 13305327189541069887965447505836108943, 23025941637865784521234444191415083701, 39848248807227476288131461546822173104, 68960607908058729168472941626927516912, 119341892941264496254850267375680858596, 206530769418287872448439164819365157712, 357418151038572249261836365381689027787, 618540932431735991718001801386896334770, 1070434962471260463170389697079661487176, 1852474022011964581139009223827365513544, 3205855677870125101423860144920010424249, 5547991769498476629256700835469967207037, 9601247144996961660705018593534913225922, 16615732425220501988109900409620796156745, 28754864847988594478375696246052761203187, 49762612400465240380187427652132912229336, 86118213596547492163397334421181607606370, 149034513167786192667574788821667110253623, 257916243121530494722068502259305736264048, 446344856986474817826595353109273441918350, 772435768089263602359077702861161388353409, 1336762385595787378549468975393213339116484, 2313375104267880490155624917599100889633507, 4003482167596451918353914186255524345816532, 6928348730257112541629154203810355027525535, 11990066177033590775605142065871666200189459, 20749776393589512464840020374644649655647874, 35909161302935015278730531942138798319507636, 62143699335409560081369603141161471393159562, 107544682943462043814216772302622710407400704, 186114746194704481727730115452186541297539854, 322086576510057527551600558671512063007190557, 557396793585831655018738502556644467159583633, 964620099559052960425720416252526682882655111, 1669352868873354804885622348664567494237803783, 2888949755545809136243688064556192446919868175, 4999560515746991945989073252770067125902428535, 8652142635098861248148452777057412533362877977, 14973230535426489152060521332311783517581989420, 25912382876992006096351135796067625851883928825, 44843468133024591960270046213401958144446811548, 77605237763877474989955856305494246316739147127, 134302122006319171731632762048131880552676359659, 232420652202367984596938247872208285088912788686, 402222680946414142984184322215356821073359953948, 696078784456971603910909918744734815016448573082, 1204620468022900362280402553035290601874308600586, 2084692860035604927076197374205039877760447754956, 3607729103106034863624554004184342562208475089341, 6243466138784576918107250594832177417637788944304, 10804821623826866941723224844111388709787418308073, 18698615116609470739339911758664365362637188157227, 32359461308280335893458609544003265039362932173740, 56000657248244594858300036379967633467510318826268, 96913653239119041752111865895809664169241405330164, 167716892009274048794745102986623447430717183044189, 290247606246426020117292750048691625438809474898504, 502296888062545512718475829352732508523042936581530, 869265269816240261877029457458234318249621243667628, 1504333646627354107869007496936781479204707239575364, 2603370684363759081777877568090078592049534352669947, 4505342904082185194291963661562434728467247085801567, 7796859204598587173314308958000104480418858953375158, 13493093589225451977147040588861591346827624626553088, 23350886533928418622148518003626067086836308029229306, 40410592153292809121198774051487713973447271440824879, 69933788415571610361075397290260005189363125951186151, 121026060286409890014591649872661507384922097295622585, 209445356819655999941471437498154462693217873859873519, 362462079567824464738504374835340908769751488853277318, 627269857492024846036766185061792395514128412691597750, 1085541071185182881358902065797900004206275433304525877, 1878616361292087979017649753948129817575491489985996469, 3251097104102362704835900720328806405351210311448488910, 5626285705844227224482132571164442587287950705132698177, 9736741115435595736854097976874400909429981720207988487, 16850215667245180941552990697851306753178430167486844006, 29160657006948951882262364132481449161390275730087294685, 50464868454466647556267645846637274956572498586114427735, 87333524327649631040132103644841977096784627243509857937, 151137706390139040826448707126591974417399010694640174718, 261555988593488478677610370284679511774525269175612894617, 452643730033345117036459086235348615186246366652477694168, 783336475835524143955537154153262203019092265959952337070, 1355626939379487620769121922144227585175531097052439217983, 2346021735820790423533561047507688175516954900918138334291, 4059979796110323903393797058491537625611005518946149411026, 7026122432346967683382009847205881024752630926437218981740, 12159271452933065576710291263470354882115951853620136774055, 21042599768180623908382939506716338579508214228553692875423, 36415915765826987773364669427220163018133640081486671468436, 63020678797925209300085103082659626905494796721119527734083, 109062366622625198169859916735972641477602693706580750774247, 188741220186912829686057249397861922209555075583934877024777, 326631901551406455092777938653826814900794821912935940782874, 565262845103114204256414747869081614169923740442179762058936, 978232936025018959853100287323851115023773163216042197843195, 1692910980111501346802672231436092377546116455476214539222026, 2929718966760270262844895994547637314231078419236801672684198, 5070114923366815738216357619638190602226980891746062079428250, 8774242726964718704518978915749604855301897112378619823447909, 15184534590503864395968205111669668293209355696392197598100449, 26278061583779512058870924747917968681797893736357134971437061, 45476304623307832769415233578427592641287934525440233150419102, 78700412341998941621862709864667467345902574612843786168968091, 136197409928206718914848388530217366761295027423898231594892758, 235700600786468895717413188934153824796333855958950958366797470]
OOi = []
Oi = []
# 构造 128 个样本，每个样本是长度为 128 的向量（outputState[i:i+128]），这些向量将组成 128×128 的矩阵 OO
# 每个样本的对应结果是 outputState[i+128]，一共也有 128 个，这些将组成结果向量 O
for i in range(128):
OOi += outputState[i:i+128]
Oi += [outputState[i+128]]
# 创建一个 128×128 的整数矩阵 OO，数据来源于列表 OOi
OO = matrix(ZZ, 128, 128, OOi)
# 创建一个 128×1 的列向量 O，数据来源于列表 Oi
O = matrix(ZZ, 128, 1, Oi)
# 求解线性方程组 OO * x = O，返回满足该等式的向量 x，即 Mask
Mask = OO.solve_right(O)
M = Mask.str().replace('\n','').replace('[','').replace(']','')
# hashlib.md5(...): 创建一个 MD5 哈希对象
# M.encode(encoding="utf-8"): 把字符串 M 按 UTF-8 编码转换为字节串（bytes 类型），因为哈希函数处理的是字节数据而不是字符串
m = hashlib.md5(M.encode(encoding="utf-8"))
# m.hexdigest(): 返回 MD5 哈希值的 十六进制字符串表示
print(m.hexdigest())
AES 类¶
AES-ECB 模式 MTP 攻击¶
话不多说，直接上题（攻防世界）
下载附件
from Crypto.Cipher import AES # 导入 AES 对称加密算法模块
from Crypto.Util.strxor import strxor as xor # 导入按位异或函数，并重命名为 xor
from Crypto.Util.Padding import pad # 导入填充函数，用于将数据填充到指定块大小
from random import * # 导入随机数生成模块的所有函数
from base64 import * # 导入 Base64 编码解码模块的所有函数
from copy import copy # 导入 copy 模块，用于复制对象
from secret import data # 从名为 secret 的模块中导入变量 data（明文数据）
# 生成一个随机的 16 字节初始向量（IV）
iv = bytes([randint(0, 2**8 - 1) for i in range(16)])
iva = copy(iv) # 复制一份 IV，可能在后续中备用
# 生成一个随机的 16 字节 AES 密钥
key = bytes([randint(0, 2**8 - 1) for i in range(16)])
# 使用生成的密钥创建一个 AES ECB 模式的密码对象
cipher = AES.new(key, mode=AES.MODE_ECB)
# 对明文数据进行填充，使其长度为 16 的倍数（AES的块大小）
data = pad(data, 16)
c = b"" # 初始化密文为一个空的字节串
# 对明文数据进行分块处理，每次处理 16 字节（一个块）
for i in range(0, len(data), 16):
# 取出当前的 16 字节块，如果不足 16 字节，用换行符补齐（虽然已经填充过了，这里是双重确保）
s = data[i:i+16].ljust(16, b"\n")
# 将当前的明文块 s 与 IV 进行按位异或，结果作为 AES 加密的输入
# 这一步引入了前一个块的加密结果，形成某种类似于反馈的模式
c += cipher.encrypt(xor(s, iv))
# 更新 IV 为当前的明文块s与刚刚生成的密文块 c[-16:]（最新的 16 字节密文）之间的异或结果
# 这样下一个块的加密会受到当前块的影响，增加了密文的复杂性
iv = xor(s, c[-16:])
# 将密钥进行 Base64 编码，便于以文本形式输出或存储
key = b64encode(key)
# 将密文进行 Base64 编码，同样是为了便于输出或存储
c = b64encode(c)
# 输出 Base64 编码后的密钥和密文
print(key)
print(c)
'''
key_b64 = b'+0zkhmid1PFjVdxSP09zSw=='
c_b64=b'A0bzFxdM95YoXm64g0gZkiTloPsBAq7iV56t1M7Q4zVNxRJSTdZH0lzOMa7QyIQbKN/ftm01iZgQAk+JVgCB6hlCdMPWkdpKYHix8BTq/ClEHUPwMEjUEvgKD4tH3T/thoccBw1jfJ9RjhXbMFByWn5cyA/gHVvEEJRpII/ryKMQkzelioQ5b0MfhSy4INLqQk6yAgLzihip5ho7lDJCbYcaz85bDksOo5n9kjOfjFnjUn9G7jX+AtyhygPlGfrvauTeuPdVxqrJTVHvrzUNAqiqtCElX+BWpicP2mkZLt5B/gpquTv8U+StrdTOcr7UkWuz+YdhXkTJYUZguv7EbEnRy+M64QzqfnNf8Zk0tJQ5xOumbY8hxGTuZ8w3rWxjPKLhdgTGLgMcMYF3hPb2eqG9VZKC3T9zElI5MWPyIdkmqkrLEt6vGT8AxWJy1hl2ApkGhrJFB0DobJircN6kXUXvZXitjXSH+BA48muaRlAwK13re+zIcbI+B7+Tm3LuRT9j5NWD9RBoy+IeAQvR05IKWqEpqXEScmZsQxpAFZCSnbchYaYNAuHvBwMcMW7vTMyxROHRtyZ+gWNUhpd8CcZ9FA6w+cwQLMWW5D4nUCMK+NEsSyTBBm/jTiAp/waq+2dTVyBhbQtmm9pBtZtHJtfeVRKuZRXduNnlWDa7Wlwv0Jk2EIJpAaXxosuZnO0PHW3oX+WO5F9ydIfIJAFUpBrn4fMx3c7IJ08+bKwAfBw/johSs1ieyX/YjOOL1KbE9J6Hz3ZBBR4waQ4p9sdLsJ9UFnNghH0ZuB2F7bGoH7SurvaMglo3FyQAfM+n/EVCGWnax/JGEcw5YZuS2c7y5Gd4oOCmpFO/lVj0IaOlZsFsMgQ3GUsBT2h1yh4yarlYUczvGNyOyfUXfueCDBQJNJ7adbdra/DHpV3LXieADKED2HankT+9ACs8oVYPpZhji0UuCdvs1txytsCqPSf5l7JLDkrGP3/7Ob7UcCA4h/B+6/0xg7h+ZJ6ZR41sDpOR8S4pmPlfJkU/np52QZfplY0sKpKlaYhuhUmMSle2TAcvNUGHobNTReFV/MOfX5/HX6behFAeOwHGI14AvUbDmrmkVvbyU88DzBW2YQ/tTTiSLg/wgggkkhLd17NZAMB3XbKuw3WdkdyJfTTpyiN05DqMwV3q64fpzasFXFNQ7ix8Q/APov/TmBYtgFw4ys2jKC6Yws166RXRkrQXzY4Ey9Xvjp5i5nUgW2HLHRGz2B5lg0jI9oWjj5+89Y0Tcqb81OFD5SfeqTbg7Y2WoW6YjQ/Hzvt1l0+p/lFrnOy3ORfhwl+DFBZi4P9i+Hh7/uC1kCW8Lil2M9oVaAH4YB2yhm61AqEk4NPhSeTuioaFfvUY5lD75QiM6BdDFMTlNkC7crXmuiUpztHTzIS6E1kVARI8xsGeljjmJmuKIfQPPQfvSnnAjGeaxCNmRPDMgFGltFiGy63Pv/tVRWbUWiB27APHPsqM2qcV/nM8IwDx5xmwExl/atQXGzn/LL4xyqzmyzD+2qMeZqfzcKZWOjoWIX+SycPvc62HAQmsKqZK5ZO2JKq5OeuFEovG9oOcRYve1XStbTQYiocEbQ4XX/c6xE0cm9P/I5NM1Mlr6CT6qt3Pqb/m+7s/kwzww59FKOq5R6HmK7SHCQ6gwTQ1ciGWbJF3NLHuOpe08X4xl/l0tJengSfJRJ39Q9WwZbgBlEPf7NYeMlR9zU9QQxvZ+r4LiaJVYrQYSCcDj37Vk9XVRMijBDWDWFbK5sgkDHQYmwGYiwH4hEAqAAXDNj1/f2eRFbIU2GN6Wfj89fEINJjoG/1O/I5Q8S7tHnlWFQNoXJQ2e4r2Aca9RPLVCWz7Nq96YUKBRN3afW/9FSwWLLvjsBptQmoRj4FwmJzJf7Vj6KCOkm6mdaZ4l6FB4/E2Lk9aopD7Q473leULPM1CydXWme/8WKUqEucDwraXS57+Z+iGRMvQ8MABtZboAVFK2B1mzNL4Ba/bxVE4puy4HwvQI+N1tKmeMf99FfR13IA0y+FWL3eCzXKw8gimaJCW1e3QJJWDorDXRRjExeokMGGHzOd8MrTfNNFGWSPqZRTdGJxW7wOWQi3bHT0WSqP1fBpdU9m+WKHIxy57dL/8JFJJ97R56P76rlToRrM825JcTBEfrK0Nb9Q+2RI83vyTA2UxH9s9cSnWd+e7nacrfXjV7EjkGHgblEGHX9LqNETaZpBAL0NG9OAJ0+f+6id4/Ixcee0jx4b8k5xvblujFEdK0q2MRo2uTxSAFMpelt8JY0EZbnF9uT88N4LPms3cNeKBt0KBhx+vshFKMc/b3W7OMCo6m7EyzmcTmMe+Y6CO0x0FF0p6h1bTnJu3MMok1hO27iBSfYusHgKWVmKpgNHjiDfuBYnuBCysa+hHQZW23zxNRqi2OGAy6zCGPOY4E4nyUA6g/jlVOjq6fFv1VHN1tlQlBOCvB9r5B0os1zI2XL/Mlb9eggNuA8nw2igDm+9qkBtLxOXojAGDonAPzBagHXnVd+0kLdUGEoddt45A2fgSSociCx4tVDMd5ag1zR4VxdADAy0lnmW0n8noAT5y60SV7gICvMOphILBRjk365Mu6GNA3C+n8k5YH9sRnS7Z5EVEKdSeYigJs4XNavD50/paKnJcux2l3gzm/1aTUMzLd8tw7vZuUWv1XaYULcez8ieEMeACETyN53+RlcPQefupgszELvwlKz0prl5ydHCPOA7+ZS2zfUZOEmRSBNaIZUCd5euNg+HXMeFa/Qb452+KKEjq7vRthC4hH9gluaYMl/eXboQvvVu4xDhfVW403enI7sxdMR3t2WO1cOaLE8IN5c71W+IqhaRbJ/Prlo/pk/XAtMvimZxIN4y5/oP5vQ/lCt5jM9wAtPKSoQbJxWIYWNrXVfkZUOOwD2tlOmyxMCcKFr8921JHgtWqcYliElNX19hzmYhow+19EV3zhITzsGOX/PP1BHIKz/NJyKcGqx1hlfrDfDVedhJWkQL9sg4clbfguprs3KG5YNbbjclaK9JoEboBY3EGBGHtsWfmIRAREwy1a53y/a/NUDLaQxrMsyV/YnbiyBevGjMVNnqIY5T0YtPLL/s5Wvmq7EU9qoMDIlaosCf616TagcZalGFQumL15q6wx3FxwVB5EAjFa/MKnZNc0CqbFhXgEevp1ZXRnjEAdSK99gyAmwVawWpxIWXZQvQ5w7tIQ+nF8utoG4ab/AdLbZyKCtT8pxjiHifNcCCkLfew8Qq9S2JnrhCUMs9SEiRrLZHiE9JVlwbUJzAQjCM6G4tdeLNEApqDv4eZ7zh2U9K2+Gk9OjBgSk5xMjRkCzKCrNAKgRLoJ1Gu8L4T9LSBp1juhUsyaIaK'
'''
什么是 AES-ECB 模式？
在 ECB 模式下，明文被划分为固定大小的块（对于 AES，通常是 128 位，即 16 字节）
每个明文块独立地使用相同的密钥进行加密，生成对应的密文块
这种方式的加密过程如下：
- 明文分块：将明文数据划分为多个 16 字节的块
- 独立加密：每个明文块使用相同的密钥独立加密，生成相应的密文块
- 密文拼接：将所有密文块拼接成最终的密文数据
由于每个明文块独立加密，相同的明文块在 ECB 模式下会生成相同的密文块。这种特性使得 ECB 模式在某些情况下容易受到攻击
MTP 攻击原理
- 多次加密相同明文：攻击者多次使用相同的密钥对相同的明文进行加密
- 分析密文块关系：由于 ECB 模式的特性，相同的明文块会生成相同的密文块。攻击者可以通过比较不同加密结果中的密文块，找到相同的密文块，从而推测出相应的明文块
- 推测明文内容：通过多次加密和分析，攻击者可以逐步恢复出完整的明文内容
# 导入必要的库
import base64 # 用于 Base64 编码和解码
from Crypto.Cipher import AES # 用于 AES 加密和解密
from Crypto.Util.strxor import strxor as xor # 用于字符串的按位异或操作
import numpy as np # 用于数组操作
# 判断字符是否为字母
def isChr(x):
"""判断字符是否为字母"""
return ord('a') <= x <= ord('z') or ord('A') <= x <= ord('Z')
# 根据推测的空格位置推断其他加密文本中的相应位置
def infer(index, pos, msg, c):
"""根据推测的空格位置推断其他加密文本中的相应位置"""
if msg[index, pos] != 0:
return
msg[index, pos] = ord(' ') # 推测为空格
for x in range(len(c)):
if x != index:
msg[x][pos] = xor(c[x], c[index])[pos] ^ ord(' ')
# 根据已知字符推断其他加密文本中的相应位置
def know(index, pos, ch, msg, c):
"""已知某个位置字符，推断其他加密文本中的相应位置"""
msg[index, pos] = ord(ch) # 设定已知字符
for x in range(len(c)):
if x != index:
msg[x][pos] = xor(c[x], c[index])[pos] ^ ord(ch)
# 获取可能的空格位置
def getSpace(c):
"""获取可能的空格位置"""
dat = []
for index, x in enumerate(c):
res = [xor(x, y) for y in c if x != y] # 计算与其他加密文本的异或结果
f = lambda pos: sum(isChr(s[pos]) for s in res) # 统计每个位置可能是字母的个数
cnt = [f(pos) for pos in range(len(x))] # 获取每个位置可能是字母的数量
for pos in range(len(x)):
dat.append((f(pos), index, pos))
return sorted(dat, reverse=True) # 按可信度排序
# 解密分块数据
def decrypt_blocks(cipher, ciphertext):
"""使用 AES ECB 模式对分块加密数据解密，应用异或操作"""
blocks = []
for i in range(0, len(ciphertext), 16):
if i == 0:
blocks.append(cipher.decrypt(ciphertext[i:i+16])) # 第一块直接解密
else:
blocks.append(xor(cipher.decrypt(ciphertext[i:i+16]), ciphertext[i-16:i]))
return blocks
# MTP 攻击推断文本内容
"""
1.异或传播：通过逐层异或，将前面块的信息传播到后续块中
2.递归推断：每个块的推测结果依赖前面的块，从而形成递归式的逐步推断过程
3.明文特征暴露：最终推断出的 tmp 中存储了各个块可能的明文内容
"""
def mtp_attack(c, blocks):
"""分块异或的结果再两两异或，增加与明文的相似性"""
tmp = [blocks[0]]
for i in range(1, len(blocks)):
block = blocks[i]
for j in range(i):
block = xor(block, blocks[j])
tmp.append(block)
"""
该段代码的核心是逐步推测出每个密文块的明文字符
通过 getSpace 提供的可信度信息，优先在最可能为空格的位置进行推断，infer 函数则利用空格位置将推断信息传播到所有块
msg 数组最终存储了所有块的推测结果，将其转换为字符即可得到明文内容
"""
# 初始化 msg 数组，存储推断的结果
c = tmp
dat = getSpace(c)
msg = np.zeros((len(c), len(c[0])), dtype=int)
for w, index, pos in dat:
infer(index, pos, msg, c) # 推断各个位置的值
return msg
def main():
# 初始化密钥和加密数据
key_base64 = b'+0zkhmid1PFjVdxSP09zSw==' # Base64编码的密钥
encrypted_data_base64 = b'A0bzFxdM95YoXm64g0gZkiTloPsBAq7iV56t1M7Q4zVNxRJSTdZH0lzOMa7QyIQbKN/ftm01iZgQAk+JVgCB6hlCdMPWkdpKYHix8BTq/ClEHUPwMEjUEvgKD4tH3T/thoccBw1jfJ9RjhXbMFByWn5cyA/gHVvEEJRpII/ryKMQkzelioQ5b0MfhSy4INLqQk6yAgLzihip5ho7lDJCbYcaz85bDksOo5n9kjOfjFnjUn9G7jX+AtyhygPlGfrvauTeuPdVxqrJTVHvrzUNAqiqtCElX+BWpicP2mkZLt5B/gpquTv8U+StrdTOcr7UkWuz+YdhXkTJYUZguv7EbEnRy+M64QzqfnNf8Zk0tJQ5xOumbY8hxGTuZ8w3rWxjPKLhdgTGLgMcMYF3hPb2eqG9VZKC3T9zElI5MWPyIdkmqkrLEt6vGT8AxWJy1hl2ApkGhrJFB0DobJircN6kXUXvZXitjXSH+BA48muaRlAwK13re+zIcbI+B7+Tm3LuRT9j5NWD9RBoy+IeAQvR05IKWqEpqXEScmZsQxpAFZCSnbchYaYNAuHvBwMcMW7vTMyxROHRtyZ+gWNUhpd8CcZ9FA6w+cwQLMWW5D4nUCMK+NEsSyTBBm/jTiAp/waq+2dTVyBhbQtmm9pBtZtHJtfeVRKuZRXduNnlWDa7Wlwv0Jk2EIJpAaXxosuZnO0PHW3oX+WO5F9ydIfIJAFUpBrn4fMx3c7IJ08+bKwAfBw/johSs1ieyX/YjOOL1KbE9J6Hz3ZBBR4waQ4p9sdLsJ9UFnNghH0ZuB2F7bGoH7SurvaMglo3FyQAfM+n/EVCGWnax/JGEcw5YZuS2c7y5Gd4oOCmpFO/lVj0IaOlZsFsMgQ3GUsBT2h1yh4yarlYUczvGNyOyfUXfueCDBQJNJ7adbdra/DHpV3LXieADKED2HankT+9ACs8oVYPpZhji0UuCdvs1txytsCqPSf5l7JLDkrGP3/7Ob7UcCA4h/B+6/0xg7h+ZJ6ZR41sDpOR8S4pmPlfJkU/np52QZfplY0sKpKlaYhuhUmMSle2TAcvNUGHobNTReFV/MOfX5/HX6behFAeOwHGI14AvUbDmrmkVvbyU88DzBW2YQ/tTTiSLg/wgggkkhLd17NZAMB3XbKuw3WdkdyJfTTpyiN05DqMwV3q64fpzasFXFNQ7ix8Q/APov/TmBYtgFw4ys2jKC6Yws166RXRkrQXzY4Ey9Xvjp5i5nUgW2HLHRGz2B5lg0jI9oWjj5+89Y0Tcqb81OFD5SfeqTbg7Y2WoW6YjQ/Hzvt1l0+p/lFrnOy3ORfhwl+DFBZi4P9i+Hh7/uC1kCW8Lil2M9oVaAH4YB2yhm61AqEk4NPhSeTuioaFfvUY5lD75QiM6BdDFMTlNkC7crXmuiUpztHTzIS6E1kVARI8xsGeljjmJmuKIfQPPQfvSnnAjGeaxCNmRPDMgFGltFiGy63Pv/tVRWbUWiB27APHPsqM2qcV/nM8IwDx5xmwExl/atQXGzn/LL4xyqzmyzD+2qMeZqfzcKZWOjoWIX+SycPvc62HAQmsKqZK5ZO2JKq5OeuFEovG9oOcRYve1XStbTQYiocEbQ4XX/c6xE0cm9P/I5NM1Mlr6CT6qt3Pqb/m+7s/kwzww59FKOq5R6HmK7SHCQ6gwTQ1ciGWbJF3NLHuOpe08X4xl/l0tJengSfJRJ39Q9WwZbgBlEPf7NYeMlR9zU9QQxvZ+r4LiaJVYrQYSCcDj37Vk9XVRMijBDWDWFbK5sgkDHQYmwGYiwH4hEAqAAXDNj1/f2eRFbIU2GN6Wfj89fEINJjoG/1O/I5Q8S7tHnlWFQNoXJQ2e4r2Aca9RPLVCWz7Nq96YUKBRN3afW/9FSwWLLvjsBptQmoRj4FwmJzJf7Vj6KCOkm6mdaZ4l6FB4/E2Lk9aopD7Q473leULPM1CydXWme/8WKUqEucDwraXS57+Z+iGRMvQ8MABtZboAVFK2B1mzNL4Ba/bxVE4puy4HwvQI+N1tKmeMf99FfR13IA0y+FWL3eCzXKw8gimaJCW1e3QJJWDorDXRRjExeokMGGHzOd8MrTfNNFGWSPqZRTdGJxW7wOWQi3bHT0WSqP1fBpdU9m+WKHIxy57dL/8JFJJ97R56P76rlToRrM825JcTBEfrK0Nb9Q+2RI83vyTA2UxH9s9cSnWd+e7nacrfXjV7EjkGHgblEGHX9LqNETaZpBAL0NG9OAJ0+f+6id4/Ixcee0jx4b8k5xvblujFEdK0q2MRo2uTxSAFMpelt8JY0EZbnF9uT88N4LPms3cNeKBt0KBhx+vshFKMc/b3W7OMCo6m7EyzmcTmMe+Y6CO0x0FF0p6h1bTnJu3MMok1hO27iBSfYusHgKWVmKpgNHjiDfuBYnuBCysa+hHQZW23zxNRqi2OGAy6zCGPOY4E4nyUA6g/jlVOjq6fFv1VHN1tlQlBOCvB9r5B0os1zI2XL/Mlb9eggNuA8nw2igDm+9qkBtLxOXojAGDonAPzBagHXnVd+0kLdUGEoddt45A2fgSSociCx4tVDMd5ag1zR4VxdADAy0lnmW0n8noAT5y60SV7gICvMOphILBRjk365Mu6GNA3C+n8k5YH9sRnS7Z5EVEKdSeYigJs4XNavD50/paKnJcux2l3gzm/1aTUMzLd8tw7vZuUWv1XaYULcez8ieEMeACETyN53+RlcPQefupgszELvwlKz0prl5ydHCPOA7+ZS2zfUZOEmRSBNaIZUCd5euNg+HXMeFa/Qb452+KKEjq7vRthC4hH9gluaYMl/eXboQvvVu4xDhfVW403enI7sxdMR3t2WO1cOaLE8IN5c71W+IqhaRbJ/Prlo/pk/XAtMvimZxIN4y5/oP5vQ/lCt5jM9wAtPKSoQbJxWIYWNrXVfkZUOOwD2tlOmyxMCcKFr8921JHgtWqcYliElNX19hzmYhow+19EV3zhITzsGOX/PP1BHIKz/NJyKcGqx1hlfrDfDVedhJWkQL9sg4clbfguprs3KG5YNbbjclaK9JoEboBY3EGBGHtsWfmIRAREwy1a53y/a/NUDLaQxrMsyV/YnbiyBevGjMVNnqIY5T0YtPLL/s5Wvmq7EU9qoMDIlaosCf616TagcZalGFQumL15q6wx3FxwVB5EAjFa/MKnZNc0CqbFhXgEevp1ZXRnjEAdSK99gyAmwVawWpxIWXZQvQ5w7tIQ+nF8utoG4ab/AdLbZyKCtT8pxjiHifNcCCkLfew8Qq9S2JnrhCUMs9SEiRrLZHiE9JVlwbUJzAQjCM6G4tdeLNEApqDv4eZ7zh2U9K2+Gk9OjBgSk5xMjRkCzKCrNAKgRLoJ1Gu8L4T9LSBp1juhUsyaIaK'
# 处理 Base64 填充
key = base64.b64decode(key_base64 + b'=' * ((4 - len(key_base64) % 4) % 4))
c = base64.b64decode(encrypted_data_base64 + b'=' * ((4 - len(encrypted_data_base64) % 4) % 4))
# 创建 AES 解密器
cipher = AES.new(key, AES.MODE_ECB)
# 分块解密，因为原始的算法每块都要与前面结果异或，所以需要分块解密，虽然这时候不是最终明文，但跟明文有相似性
decrypted_blocks = decrypt_blocks(cipher, c)
# 执行 MTP 攻击推断
msg = mtp_attack(c, decrypted_blocks)
# 输出最终解密结果
print(''.join([''.join([chr(c) for c in row]) for row in msg]))
# 执行主程序
if __name__ == "__main__":
main()
Emoji-AES 解密¶
话不多说，直接上题（BUUCTF）
打卡文件
LOLCODE 是一种诙谐幽默的 怪诞型编程语言（Esoteric Programming Language），诞生于 2007 年，由 Adam Lindsay 设计。灵感来源于早期互联网流行的 LOLCats 文化，那种用滑稽错误英语（Engrish）写出来的迷因图，如 “I CAN HAS CHEEZBURGER?”。
这门语言本质是为了搞笑，语言结构模仿这种“猫语+错别字+网民黑话”，不具备实用性，但具备完整的编程语法特征
| 功能 | C语言写法 | LOLCODE 写法 |
|---|---|---|
| 定义变量 | int x = 5; |
I HAS A X ITZ 5 |
| 输出 | printf("hi"); |
VISIBLE "hi" |
| 条件 | if ... else |
O RLY? YA RLY NO WAI |
| 循环 | while |
IM IN YR LOOP ... IM OUTTA YR LOOP |
| 输入 | scanf |
GIMMEH VAR |
解密得到 Key
解压缩包得到 1.docx，内容提示 AES，无其他内容，尝试将 docx 修改成 .zip 解压发现 fllllllllll1ag.txt
Emoji 符号加上之前提示的 AES，猜测为 Emoji-AES，Key 继续猜测为之前的 Key，有点小脑洞 Rotation=4
国密算法类¶
AES-ECB 模式 MTP 攻击¶
话不多说，直接上题（攻防世界）
下载附件
from Crypto.Cipher import AES # 导入 AES 对称加密算法模块
from Crypto.Util.strxor import strxor as xor # 导入按位异或函数，并重命名为 xor
from Crypto.Util.Padding import pad # 导入填充函数，用于将数据填充到指定块大小
from random import * # 导入随机数生成模块的所有函数
from base64 import * # 导入 Base64 编码解码模块的所有函数
from copy import copy # 导入 copy 模块，用于复制对象
from secret import data # 从名为 secret 的模块中导入变量 data（明文数据）
# 生成一个随机的 16 字节初始向量（IV）
iv = bytes([randint(0, 2**8 - 1) for i in range(16)])
iva = copy(iv) # 复制一份 IV，可能在后续中备用
# 生成一个随机的 16 字节 AES 密钥
key = bytes([randint(0, 2**8 - 1) for i in range(16)])
# 使用生成的密钥创建一个 AES ECB 模式的密码对象
cipher = AES.new(key, mode=AES.MODE_ECB)
# 对明文数据进行填充，使其长度为 16 的倍数（AES的块大小）
data = pad(data, 16)
c = b"" # 初始化密文为一个空的字节串
# 对明文数据进行分块处理，每次处理 16 字节（一个块）
for i in range(0, len(data), 16):
# 取出当前的 16 字节块，如果不足 16 字节，用换行符补齐（虽然已经填充过了，这里是双重确保）
s = data[i:i+16].ljust(16, b"\n")
# 将当前的明文块 s 与 IV 进行按位异或，结果作为 AES 加密的输入
# 这一步引入了前一个块的加密结果，形成某种类似于反馈的模式
c += cipher.encrypt(xor(s, iv))
# 更新 IV 为当前的明文块s与刚刚生成的密文块 c[-16:]（最新的 16 字节密文）之间的异或结果
# 这样下一个块的加密会受到当前块的影响，增加了密文的复杂性
iv = xor(s, c[-16:])
# 将密钥进行 Base64 编码，便于以文本形式输出或存储
key = b64encode(key)
# 将密文进行 Base64 编码，同样是为了便于输出或存储
c = b64encode(c)
# 输出 Base64 编码后的密钥和密文
print(key)
print(c)
'''
key_b64 = b'+0zkhmid1PFjVdxSP09zSw=='
c_b64=b'A0bzFxdM95YoXm64g0gZkiTloPsBAq7iV56t1M7Q4zVNxRJSTdZH0lzOMa7QyIQbKN/ftm01iZgQAk+JVgCB6hlCdMPWkdpKYHix8BTq/ClEHUPwMEjUEvgKD4tH3T/thoccBw1jfJ9RjhXbMFByWn5cyA/gHVvEEJRpII/ryKMQkzelioQ5b0MfhSy4INLqQk6yAgLzihip5ho7lDJCbYcaz85bDksOo5n9kjOfjFnjUn9G7jX+AtyhygPlGfrvauTeuPdVxqrJTVHvrzUNAqiqtCElX+BWpicP2mkZLt5B/gpquTv8U+StrdTOcr7UkWuz+YdhXkTJYUZguv7EbEnRy+M64QzqfnNf8Zk0tJQ5xOumbY8hxGTuZ8w3rWxjPKLhdgTGLgMcMYF3hPb2eqG9VZKC3T9zElI5MWPyIdkmqkrLEt6vGT8AxWJy1hl2ApkGhrJFB0DobJircN6kXUXvZXitjXSH+BA48muaRlAwK13re+zIcbI+B7+Tm3LuRT9j5NWD9RBoy+IeAQvR05IKWqEpqXEScmZsQxpAFZCSnbchYaYNAuHvBwMcMW7vTMyxROHRtyZ+gWNUhpd8CcZ9FA6w+cwQLMWW5D4nUCMK+NEsSyTBBm/jTiAp/waq+2dTVyBhbQtmm9pBtZtHJtfeVRKuZRXduNnlWDa7Wlwv0Jk2EIJpAaXxosuZnO0PHW3oX+WO5F9ydIfIJAFUpBrn4fMx3c7IJ08+bKwAfBw/johSs1ieyX/YjOOL1KbE9J6Hz3ZBBR4waQ4p9sdLsJ9UFnNghH0ZuB2F7bGoH7SurvaMglo3FyQAfM+n/EVCGWnax/JGEcw5YZuS2c7y5Gd4oOCmpFO/lVj0IaOlZsFsMgQ3GUsBT2h1yh4yarlYUczvGNyOyfUXfueCDBQJNJ7adbdra/DHpV3LXieADKED2HankT+9ACs8oVYPpZhji0UuCdvs1txytsCqPSf5l7JLDkrGP3/7Ob7UcCA4h/B+6/0xg7h+ZJ6ZR41sDpOR8S4pmPlfJkU/np52QZfplY0sKpKlaYhuhUmMSle2TAcvNUGHobNTReFV/MOfX5/HX6behFAeOwHGI14AvUbDmrmkVvbyU88DzBW2YQ/tTTiSLg/wgggkkhLd17NZAMB3XbKuw3WdkdyJfTTpyiN05DqMwV3q64fpzasFXFNQ7ix8Q/APov/TmBYtgFw4ys2jKC6Yws166RXRkrQXzY4Ey9Xvjp5i5nUgW2HLHRGz2B5lg0jI9oWjj5+89Y0Tcqb81OFD5SfeqTbg7Y2WoW6YjQ/Hzvt1l0+p/lFrnOy3ORfhwl+DFBZi4P9i+Hh7/uC1kCW8Lil2M9oVaAH4YB2yhm61AqEk4NPhSeTuioaFfvUY5lD75QiM6BdDFMTlNkC7crXmuiUpztHTzIS6E1kVARI8xsGeljjmJmuKIfQPPQfvSnnAjGeaxCNmRPDMgFGltFiGy63Pv/tVRWbUWiB27APHPsqM2qcV/nM8IwDx5xmwExl/atQXGzn/LL4xyqzmyzD+2qMeZqfzcKZWOjoWIX+SycPvc62HAQmsKqZK5ZO2JKq5OeuFEovG9oOcRYve1XStbTQYiocEbQ4XX/c6xE0cm9P/I5NM1Mlr6CT6qt3Pqb/m+7s/kwzww59FKOq5R6HmK7SHCQ6gwTQ1ciGWbJF3NLHuOpe08X4xl/l0tJengSfJRJ39Q9WwZbgBlEPf7NYeMlR9zU9QQxvZ+r4LiaJVYrQYSCcDj37Vk9XVRMijBDWDWFbK5sgkDHQYmwGYiwH4hEAqAAXDNj1/f2eRFbIU2GN6Wfj89fEINJjoG/1O/I5Q8S7tHnlWFQNoXJQ2e4r2Aca9RPLVCWz7Nq96YUKBRN3afW/9FSwWLLvjsBptQmoRj4FwmJzJf7Vj6KCOkm6mdaZ4l6FB4/E2Lk9aopD7Q473leULPM1CydXWme/8WKUqEucDwraXS57+Z+iGRMvQ8MABtZboAVFK2B1mzNL4Ba/bxVE4puy4HwvQI+N1tKmeMf99FfR13IA0y+FWL3eCzXKw8gimaJCW1e3QJJWDorDXRRjExeokMGGHzOd8MrTfNNFGWSPqZRTdGJxW7wOWQi3bHT0WSqP1fBpdU9m+WKHIxy57dL/8JFJJ97R56P76rlToRrM825JcTBEfrK0Nb9Q+2RI83vyTA2UxH9s9cSnWd+e7nacrfXjV7EjkGHgblEGHX9LqNETaZpBAL0NG9OAJ0+f+6id4/Ixcee0jx4b8k5xvblujFEdK0q2MRo2uTxSAFMpelt8JY0EZbnF9uT88N4LPms3cNeKBt0KBhx+vshFKMc/b3W7OMCo6m7EyzmcTmMe+Y6CO0x0FF0p6h1bTnJu3MMok1hO27iBSfYusHgKWVmKpgNHjiDfuBYnuBCysa+hHQZW23zxNRqi2OGAy6zCGPOY4E4nyUA6g/jlVOjq6fFv1VHN1tlQlBOCvB9r5B0os1zI2XL/Mlb9eggNuA8nw2igDm+9qkBtLxOXojAGDonAPzBagHXnVd+0kLdUGEoddt45A2fgSSociCx4tVDMd5ag1zR4VxdADAy0lnmW0n8noAT5y60SV7gICvMOphILBRjk365Mu6GNA3C+n8k5YH9sRnS7Z5EVEKdSeYigJs4XNavD50/paKnJcux2l3gzm/1aTUMzLd8tw7vZuUWv1XaYULcez8ieEMeACETyN53+RlcPQefupgszELvwlKz0prl5ydHCPOA7+ZS2zfUZOEmRSBNaIZUCd5euNg+HXMeFa/Qb452+KKEjq7vRthC4hH9gluaYMl/eXboQvvVu4xDhfVW403enI7sxdMR3t2WO1cOaLE8IN5c71W+IqhaRbJ/Prlo/pk/XAtMvimZxIN4y5/oP5vQ/lCt5jM9wAtPKSoQbJxWIYWNrXVfkZUOOwD2tlOmyxMCcKFr8921JHgtWqcYliElNX19hzmYhow+19EV3zhITzsGOX/PP1BHIKz/NJyKcGqx1hlfrDfDVedhJWkQL9sg4clbfguprs3KG5YNbbjclaK9JoEboBY3EGBGHtsWfmIRAREwy1a53y/a/NUDLaQxrMsyV/YnbiyBevGjMVNnqIY5T0YtPLL/s5Wvmq7EU9qoMDIlaosCf616TagcZalGFQumL15q6wx3FxwVB5EAjFa/MKnZNc0CqbFhXgEevp1ZXRnjEAdSK99gyAmwVawWpxIWXZQvQ5w7tIQ+nF8utoG4ab/AdLbZyKCtT8pxjiHifNcCCkLfew8Qq9S2JnrhCUMs9SEiRrLZHiE9JVlwbUJzAQjCM6G4tdeLNEApqDv4eZ7zh2U9K2+Gk9OjBgSk5xMjRkCzKCrNAKgRLoJ1Gu8L4T9LSBp1juhUsyaIaK'
'''
什么是 AES-ECB 模式？
在 ECB 模式下，明文被划分为固定大小的块（对于 AES，通常是 128 位，即 16 字节）
每个明文块独立地使用相同的密钥进行加密，生成对应的密文块
这种方式的加密过程如下：
- 明文分块：将明文数据划分为多个 16 字节的块
- 独立加密：每个明文块使用相同的密钥独立加密，生成相应的密文块
- 密文拼接：将所有密文块拼接成最终的密文数据
由于每个明文块独立加密，相同的明文块在 ECB 模式下会生成相同的密文块。这种特性使得 ECB 模式在某些情况下容易受到攻击
MTP 攻击原理
- 多次加密相同明文：攻击者多次使用相同的密钥对相同的明文进行加密
- 分析密文块关系：由于 ECB 模式的特性，相同的明文块会生成相同的密文块。攻击者可以通过比较不同加密结果中的密文块，找到相同的密文块，从而推测出相应的明文块
- 推测明文内容：通过多次加密和分析，攻击者可以逐步恢复出完整的明文内容
# 导入必要的库
import base64 # 用于 Base64 编码和解码
from Crypto.Cipher import AES # 用于 AES 加密和解密
from Crypto.Util.strxor import strxor as xor # 用于字符串的按位异或操作
import numpy as np # 用于数组操作
# 判断字符是否为字母
def isChr(x):
"""判断字符是否为字母"""
return ord('a') <= x <= ord('z') or ord('A') <= x <= ord('Z')
# 根据推测的空格位置推断其他加密文本中的相应位置
def infer(index, pos, msg, c):
"""根据推测的空格位置推断其他加密文本中的相应位置"""
if msg[index, pos] != 0:
return
msg[index, pos] = ord(' ') # 推测为空格
for x in range(len(c)):
if x != index:
msg[x][pos] = xor(c[x], c[index])[pos] ^ ord(' ')
# 根据已知字符推断其他加密文本中的相应位置
def know(index, pos, ch, msg, c):
"""已知某个位置字符，推断其他加密文本中的相应位置"""
msg[index, pos] = ord(ch) # 设定已知字符
for x in range(len(c)):
if x != index:
msg[x][pos] = xor(c[x], c[index])[pos] ^ ord(ch)
# 获取可能的空格位置
def getSpace(c):
"""获取可能的空格位置"""
dat = []
for index, x in enumerate(c):
res = [xor(x, y) for y in c if x != y] # 计算与其他加密文本的异或结果
f = lambda pos: sum(isChr(s[pos]) for s in res) # 统计每个位置可能是字母的个数
cnt = [f(pos) for pos in range(len(x))] # 获取每个位置可能是字母的数量
for pos in range(len(x)):
dat.append((f(pos), index, pos))
return sorted(dat, reverse=True) # 按可信度排序
# 解密分块数据
def decrypt_blocks(cipher, ciphertext):
"""使用 AES ECB 模式对分块加密数据解密，应用异或操作"""
blocks = []
for i in range(0, len(ciphertext), 16):
if i == 0:
blocks.append(cipher.decrypt(ciphertext[i:i+16])) # 第一块直接解密
else:
blocks.append(xor(cipher.decrypt(ciphertext[i:i+16]), ciphertext[i-16:i]))
return blocks
# MTP 攻击推断文本内容
"""
1.异或传播：通过逐层异或，将前面块的信息传播到后续块中
2.递归推断：每个块的推测结果依赖前面的块，从而形成递归式的逐步推断过程
3.明文特征暴露：最终推断出的 tmp 中存储了各个块可能的明文内容
"""
def mtp_attack(c, blocks):
"""分块异或的结果再两两异或，增加与明文的相似性"""
tmp = [blocks[0]]
for i in range(1, len(blocks)):
block = blocks[i]
for j in range(i):
block = xor(block, blocks[j])
tmp.append(block)
"""
该段代码的核心是逐步推测出每个密文块的明文字符
通过 getSpace 提供的可信度信息，优先在最可能为空格的位置进行推断，infer 函数则利用空格位置将推断信息传播到所有块
msg 数组最终存储了所有块的推测结果，将其转换为字符即可得到明文内容
"""
# 初始化 msg 数组，存储推断的结果
c = tmp
dat = getSpace(c)
msg = np.zeros((len(c), len(c[0])), dtype=int)
for w, index, pos in dat:
infer(index, pos, msg, c) # 推断各个位置的值
return msg
def main():
# 初始化密钥和加密数据
key_base64 = b'+0zkhmid1PFjVdxSP09zSw==' # Base64编码的密钥
encrypted_data_base64 = b'A0bzFxdM95YoXm64g0gZkiTloPsBAq7iV56t1M7Q4zVNxRJSTdZH0lzOMa7QyIQbKN/ftm01iZgQAk+JVgCB6hlCdMPWkdpKYHix8BTq/ClEHUPwMEjUEvgKD4tH3T/thoccBw1jfJ9RjhXbMFByWn5cyA/gHVvEEJRpII/ryKMQkzelioQ5b0MfhSy4INLqQk6yAgLzihip5ho7lDJCbYcaz85bDksOo5n9kjOfjFnjUn9G7jX+AtyhygPlGfrvauTeuPdVxqrJTVHvrzUNAqiqtCElX+BWpicP2mkZLt5B/gpquTv8U+StrdTOcr7UkWuz+YdhXkTJYUZguv7EbEnRy+M64QzqfnNf8Zk0tJQ5xOumbY8hxGTuZ8w3rWxjPKLhdgTGLgMcMYF3hPb2eqG9VZKC3T9zElI5MWPyIdkmqkrLEt6vGT8AxWJy1hl2ApkGhrJFB0DobJircN6kXUXvZXitjXSH+BA48muaRlAwK13re+zIcbI+B7+Tm3LuRT9j5NWD9RBoy+IeAQvR05IKWqEpqXEScmZsQxpAFZCSnbchYaYNAuHvBwMcMW7vTMyxROHRtyZ+gWNUhpd8CcZ9FA6w+cwQLMWW5D4nUCMK+NEsSyTBBm/jTiAp/waq+2dTVyBhbQtmm9pBtZtHJtfeVRKuZRXduNnlWDa7Wlwv0Jk2EIJpAaXxosuZnO0PHW3oX+WO5F9ydIfIJAFUpBrn4fMx3c7IJ08+bKwAfBw/johSs1ieyX/YjOOL1KbE9J6Hz3ZBBR4waQ4p9sdLsJ9UFnNghH0ZuB2F7bGoH7SurvaMglo3FyQAfM+n/EVCGWnax/JGEcw5YZuS2c7y5Gd4oOCmpFO/lVj0IaOlZsFsMgQ3GUsBT2h1yh4yarlYUczvGNyOyfUXfueCDBQJNJ7adbdra/DHpV3LXieADKED2HankT+9ACs8oVYPpZhji0UuCdvs1txytsCqPSf5l7JLDkrGP3/7Ob7UcCA4h/B+6/0xg7h+ZJ6ZR41sDpOR8S4pmPlfJkU/np52QZfplY0sKpKlaYhuhUmMSle2TAcvNUGHobNTReFV/MOfX5/HX6behFAeOwHGI14AvUbDmrmkVvbyU88DzBW2YQ/tTTiSLg/wgggkkhLd17NZAMB3XbKuw3WdkdyJfTTpyiN05DqMwV3q64fpzasFXFNQ7ix8Q/APov/TmBYtgFw4ys2jKC6Yws166RXRkrQXzY4Ey9Xvjp5i5nUgW2HLHRGz2B5lg0jI9oWjj5+89Y0Tcqb81OFD5SfeqTbg7Y2WoW6YjQ/Hzvt1l0+p/lFrnOy3ORfhwl+DFBZi4P9i+Hh7/uC1kCW8Lil2M9oVaAH4YB2yhm61AqEk4NPhSeTuioaFfvUY5lD75QiM6BdDFMTlNkC7crXmuiUpztHTzIS6E1kVARI8xsGeljjmJmuKIfQPPQfvSnnAjGeaxCNmRPDMgFGltFiGy63Pv/tVRWbUWiB27APHPsqM2qcV/nM8IwDx5xmwExl/atQXGzn/LL4xyqzmyzD+2qMeZqfzcKZWOjoWIX+SycPvc62HAQmsKqZK5ZO2JKq5OeuFEovG9oOcRYve1XStbTQYiocEbQ4XX/c6xE0cm9P/I5NM1Mlr6CT6qt3Pqb/m+7s/kwzww59FKOq5R6HmK7SHCQ6gwTQ1ciGWbJF3NLHuOpe08X4xl/l0tJengSfJRJ39Q9WwZbgBlEPf7NYeMlR9zU9QQxvZ+r4LiaJVYrQYSCcDj37Vk9XVRMijBDWDWFbK5sgkDHQYmwGYiwH4hEAqAAXDNj1/f2eRFbIU2GN6Wfj89fEINJjoG/1O/I5Q8S7tHnlWFQNoXJQ2e4r2Aca9RPLVCWz7Nq96YUKBRN3afW/9FSwWLLvjsBptQmoRj4FwmJzJf7Vj6KCOkm6mdaZ4l6FB4/E2Lk9aopD7Q473leULPM1CydXWme/8WKUqEucDwraXS57+Z+iGRMvQ8MABtZboAVFK2B1mzNL4Ba/bxVE4puy4HwvQI+N1tKmeMf99FfR13IA0y+FWL3eCzXKw8gimaJCW1e3QJJWDorDXRRjExeokMGGHzOd8MrTfNNFGWSPqZRTdGJxW7wOWQi3bHT0WSqP1fBpdU9m+WKHIxy57dL/8JFJJ97R56P76rlToRrM825JcTBEfrK0Nb9Q+2RI83vyTA2UxH9s9cSnWd+e7nacrfXjV7EjkGHgblEGHX9LqNETaZpBAL0NG9OAJ0+f+6id4/Ixcee0jx4b8k5xvblujFEdK0q2MRo2uTxSAFMpelt8JY0EZbnF9uT88N4LPms3cNeKBt0KBhx+vshFKMc/b3W7OMCo6m7EyzmcTmMe+Y6CO0x0FF0p6h1bTnJu3MMok1hO27iBSfYusHgKWVmKpgNHjiDfuBYnuBCysa+hHQZW23zxNRqi2OGAy6zCGPOY4E4nyUA6g/jlVOjq6fFv1VHN1tlQlBOCvB9r5B0os1zI2XL/Mlb9eggNuA8nw2igDm+9qkBtLxOXojAGDonAPzBagHXnVd+0kLdUGEoddt45A2fgSSociCx4tVDMd5ag1zR4VxdADAy0lnmW0n8noAT5y60SV7gICvMOphILBRjk365Mu6GNA3C+n8k5YH9sRnS7Z5EVEKdSeYigJs4XNavD50/paKnJcux2l3gzm/1aTUMzLd8tw7vZuUWv1XaYULcez8ieEMeACETyN53+RlcPQefupgszELvwlKz0prl5ydHCPOA7+ZS2zfUZOEmRSBNaIZUCd5euNg+HXMeFa/Qb452+KKEjq7vRthC4hH9gluaYMl/eXboQvvVu4xDhfVW403enI7sxdMR3t2WO1cOaLE8IN5c71W+IqhaRbJ/Prlo/pk/XAtMvimZxIN4y5/oP5vQ/lCt5jM9wAtPKSoQbJxWIYWNrXVfkZUOOwD2tlOmyxMCcKFr8921JHgtWqcYliElNX19hzmYhow+19EV3zhITzsGOX/PP1BHIKz/NJyKcGqx1hlfrDfDVedhJWkQL9sg4clbfguprs3KG5YNbbjclaK9JoEboBY3EGBGHtsWfmIRAREwy1a53y/a/NUDLaQxrMsyV/YnbiyBevGjMVNnqIY5T0YtPLL/s5Wvmq7EU9qoMDIlaosCf616TagcZalGFQumL15q6wx3FxwVB5EAjFa/MKnZNc0CqbFhXgEevp1ZXRnjEAdSK99gyAmwVawWpxIWXZQvQ5w7tIQ+nF8utoG4ab/AdLbZyKCtT8pxjiHifNcCCkLfew8Qq9S2JnrhCUMs9SEiRrLZHiE9JVlwbUJzAQjCM6G4tdeLNEApqDv4eZ7zh2U9K2+Gk9OjBgSk5xMjRkCzKCrNAKgRLoJ1Gu8L4T9LSBp1juhUsyaIaK'
# 处理 Base64 填充
key = base64.b64decode(key_base64 + b'=' * ((4 - len(key_base64) % 4) % 4))
c = base64.b64decode(encrypted_data_base64 + b'=' * ((4 - len(encrypted_data_base64) % 4) % 4))
# 创建 AES 解密器
cipher = AES.new(key, AES.MODE_ECB)
# 分块解密，因为原始的算法每块都要与前面结果异或，所以需要分块解密，虽然这时候不是最终明文，但跟明文有相似性
decrypted_blocks = decrypt_blocks(cipher, c)
# 执行 MTP 攻击推断
msg = mtp_attack(c, decrypted_blocks)
# 输出最终解密结果
print(''.join([''.join([chr(c) for c in row]) for row in msg]))
# 执行主程序
if __name__ == "__main__":
main()
Emoji-AES 解密¶
话不多说，直接上题（BUUCTF）
打卡文件
LOLCODE 是一种诙谐幽默的 怪诞型编程语言（Esoteric Programming Language），诞生于 2007 年，由 Adam Lindsay 设计。灵感来源于早期互联网流行的 LOLCats 文化，那种用滑稽错误英语（Engrish）写出来的迷因图，如 “I CAN HAS CHEEZBURGER?”。
这门语言本质是为了搞笑，语言结构模仿这种“猫语+错别字+网民黑话”，不具备实用性，但具备完整的编程语法特征
| 功能 | C语言写法 | LOLCODE 写法 |
|---|---|---|
| 定义变量 | int x = 5; |
I HAS A X ITZ 5 |
| 输出 | printf("hi"); |
VISIBLE "hi" |
| 条件 | if ... else |
O RLY? YA RLY NO WAI |
| 循环 | while |
IM IN YR LOOP ... IM OUTTA YR LOOP |
| 输入 | scanf |
GIMMEH VAR |
解密得到 Key
解压缩包得到 1.docx，内容提示 AES，无其他内容，尝试将 docx 修改成 .zip 解压发现 fllllllllll1ag.txt
Emoji 符号加上之前提示的 AES，猜测为 Emoji-AES，Key 继续猜测为之前的 Key，有点小脑洞 Rotation=4
附录¶
模运算¶
\[
\begin{aligned}
&a\ \equiv\ b\ (mod\ m)\ ⟺\ m\ |\ (a\ -\ b)
\end{aligned}
\]
\[
\begin{aligned}
&a\ \equiv\ b\ (mod\ m)\ ⇒\ a\ +\ c\ \equiv\ b\ +\ c\ (mod\ m)\\\\
&a\ \equiv\ b\ (mod\ m)\ ⇒\ a\ *\ c\ \equiv\ b\ *\ c\ (mod\ m)\\\\
&a\ \equiv\ b\ (mod\ m)\ ⇒\ a^k\ \equiv\ b^k\ (mod\ m)\\\\
\end{aligned}
\]
\[
\begin{aligned}
&17\ +\ 3\ =\ 20,\ 5\ +\ 3\ =\ 8\ ⇒\ 20\ \equiv\ 8\ (mod\ 12)
\end{aligned}
\]
\[
\begin{aligned}
&17\ *\ 4\ =\ 68,\ 5\ *\ 4\ =\ 20\ ⇒\ 68\ \equiv\ 20\ (mod\ 12)
\end{aligned}
\]
\[
\begin{aligned}
&17^2\ =\ 289,\ 5^2\ =\ 25\ ⇒\ 289\ \equiv\ 25\ (mod\ 12)
\end{aligned}
\]
线性同余方程¶
\[
\begin{aligned}
&ax\ \equiv\ b\ (mod\ m)
\end{aligned}
\]
\[
\begin{aligned}
&\frac{a}{d}x\ \equiv\ \frac{b}{d}\ (mod\ \frac{m}{d})
\end{aligned}
\]
\[
\begin{aligned}
&x\ \equiv\ x_0\ +\ \frac{m}{d}k\ (k\ \epsilon\ Z)
\end{aligned}
\]
\[
\begin{aligned}
&12x\ \equiv\ 8\ (mod\ 20)
\end{aligned}
\]
\[
\begin{aligned}
&gcd(12,20)\ =\ 4
\end{aligned}
\]
\[
\begin{aligned}
&\frac{12}{4}x\ \equiv\ \frac{8}{4}\ (mod\ \frac{20}{4})\ ⇒\ 3x\ \equiv\ 2\ (mod\ 5)
\end{aligned}
\]
\[
\begin{aligned}
&3x\ \equiv\ 2\ (mod\ 5)
\end{aligned}
\]
\[
\begin{aligned}
&x_0\ =\ 4
\end{aligned}
\]
\[
\begin{aligned}
&x\ \equiv\ 4\ +\ 5k\ (k\ \epsilon\ Z)
\end{aligned}
\]
欧几里得算法（GCD）¶
用于快速计算两个整数的最大公约数：
例如：gcd(48, 18) → gcd(18, 12) → gcd(12, 6) → gcd(6, 0) = 6
扩展欧几里得算法-贝祖定理¶
\[
\begin{aligned}
&a\ *\ e_1\ +\ b\ *\ e_2\ =\ 1
\end{aligned}
\]
\[
\begin{aligned}
&a\ *\ e_1\ \equiv\ 1\ (mod\ e_2)
\end{aligned}
\]
整数线性组合¶
\[
\begin{aligned}
&a\ *\ x\ +\ b\ *\ y\ =\ d\ =\ gcd(a,b)
\end{aligned}
\]
这个概念在求模逆元、解线性同余方程时至关重要
示例：写出 48 和 18 的最大公约数的整数线性组合
Step 1：先用欧几里得算法求 gcd(48,18) = 6
Step 2：回代求出整数 x,y
\[
\begin{aligned}
&6\ =\ 18\ -\ 1\ *\ 12\\
&=\ 18\ -\ 1\ \ *\ (48\ -\ 2\ *\ 18)\\
&=\ 18\ -\ 1\ \ *\ 48\ +\ 2\ *\ 18\\
&=\ 3\ *\ 18\ -\ 1\ *\ 48\\
\end{aligned}
\]
\[
\begin{aligned}
&6\ =\ (-1)\ *\ 48\ +\ 3\ *\ 18\\
\end{aligned}
\]
中国剩余定理（CRT）¶
\[
\begin{aligned}
&\begin{cases}\ x\ \equiv\ a_1\ (mod\ m_1)\\\ x\ \equiv\ a_2\ (mod\ m_2)\\\ x\ \equiv\ a_3\ (mod\ m_3)\end{cases}
\end{aligned}
\]
\[
\begin{aligned}
&x\ mod\ M\\\\
&M\ =\ m_1m_2……m_3
\end{aligned}
\]
\[
\begin{aligned}
&x\ \equiv\ \sum_{i=1}^{k}{a_i\ *\ M_i\ *\ y_i}\ (mod\ N)\\\\
&M\ =\ m_1m_2……m_k\\
&M_i\ =\frac{M}{m_i}\\
&y_i\ ={M_i}^{-1}\ (mod\ m_i)(即\ M_i\ *\ y_i\ \equiv\ 1\ (mod\ m_i))\\
\end{aligned}
\]
\[
\begin{aligned}
&\begin{cases}\ x\ \equiv\ 2\ (mod\ 3)\\\ x\ \equiv\ 3\ (mod\ 5)\\\ x\ \equiv\ 2\ (mod\ 7)\end{cases}
\end{aligned}
\]
\[
\begin{aligned}
&M\ =\ 3\ *\ 5\ *\ 7\ =\ 105
\end{aligned}
\]
| i | m_i | a_i | M_i = M/m_i | y_i = M_i^{-1} mod m_i |
|---|---|---|---|---|
| 1 | 3 | 2 | 105 / 3 = 35 | 35 mod 3 的逆元是 2（因为 35 ⋅ 2 ≡ 1mod 3） |
| 2 | 5 | 3 | 105 / 5 = 21 | 21 mod 5 的逆元是 1（21 ⋅ 1 ≡ 1mod 5） |
| 3 | 7 | 2 | 105 / 7 = 15 | 15 mod 7 的逆元是 1（15 ⋅ 1 ≡ 1mod 7） |
\[
\begin{aligned}
&x\ \equiv\ 2\ *\ 35\ *\ 2\ +\ 3\ *\ 21\ *\ 1\ +\ 2\ *\ 15\ *\ 1\ (mod\ 105)\\\\
&x\ \equiv\ 2\ *\ 70\ +\ 3\ *\ 21\ +\ 2\ *\ 15\ =\ 140\ +\ 63\ +\ 30\ =\ 233
\end{aligned}
\]
\[
\begin{aligned}
&x\ \equiv\ 233\ (mod\ 105)\ =\ 233\ -\ 2\ *\ 105\ =\ 23\\\\
\end{aligned}
\]
\[
\begin{aligned}
&x\ \equiv\ 23\ (mod\ 105)\\\\
\end{aligned}
\]
同余方程组的合并（非互质情况）¶
\[
\begin{aligned}
&\begin{cases}\ x\ \equiv\ a_1\ (mod\ m_1)\\\ x\ \equiv\ a_2\ (mod\ m_2)\end{cases}
\end{aligned}
\]
步骤如下：
1. 求 d = gcd(m1,m2)
2. 判断是否有解
2.1 若 d | (a2 - a1)，则有解
2.2 否则无解
3. 用扩展欧几里得算法解：
m1 * x + m2 * y = a2 - a1
得到通解 x = x0
4. 将两个方程合并为一个新的同余式，再继续合并第三个……
模数的等效性¶
在模运算中，如果两个整数除以同一个模数 M 得到的余数相同，那么它们在模 M 的意义下是**等效的**（或**同余的**）
模数 MOD = 62，这就好比一个只有 62 个刻度的时钟
如果你转了 1 圈（62格），指针回到原点（0）
如果你转了 65 格，指针停在 3 的位置。所以在模 62 的世界里，65 和 3 是完全等价的
斐波那契数列¶
斐波那契数列是一个**递推数列**，它的核心规则是：从第三项起，数列中的每一项都等于前两项之和 $$ \begin{aligned} &F_n = F_{n-1} + F_{n-2} (n \geq 3) \end{aligned} $$ 在 CTF 和数论领域，斐波那契数列的**模运算性质**至关重要：
Pisano 周期
- 定义： 斐波那契数列对任何正整数 n 取模后，都会变成一个**循环数列**。这个循环的长度就被称为 Pisano 周期，记作 $$ \begin{aligned} &\pi(n) \end{aligned} $$
黄金比例
斐波那契数列最著名的性质是它与**黄金比例** 的关系
-
黄金比例的值： $$ \begin{aligned} &\phi = \frac{1 + \sqrt{5}}{2} \approx 1.6180339887\dots \end{aligned} $$
-
收敛性： 当 n 趋近于无穷大时，相邻两项的比值 $$ \begin{aligned} (\frac{F_{n}}{F_{n-1}}) \end{aligned} $$ 会无限接近黄金比例
宾涅公式
斐波那契数列存在一个不依赖于前一项的封闭形式公式，可以直接计算第 n 项： $$ \begin{aligned} F_n = \frac{\phi^n - (-\phi)^{-n}}{\sqrt{5}} \end{aligned} $$ 卢卡斯恒等式
正如我们在上一题中讨论的，斐波那契数列的和也有简洁的公式： $$ \begin{aligned} \sum_{i=1}^{n} F_i = F_{n+2} - 1 \end{aligned} $$