# Cryptography 密码学

# 古典密码

# Rabbit 密码

需要一个密码,解密一个类似 base64 的

BITSCTF2025: The most wanted lagomorph

t
BITSCTF{f3rb_1_kn0w_wh47_w3_4r3_60nn4_d0_70d4y}

加密 key=dennis ,变成

t
U2FsdGVkX1+Kci2LQvPTy06ga66qMTDgoOip6SxH1t7EreImxWCP3RarTyRTU2k3Nrd4vChzcXYKqPZSyl3T

# 梅森旋转算法

python 里的 random , C++ 里的 std::mt19937 都是这个算法,梅森旋转算法(Mersenne Twister Algorithm,简称 MT)

参考博客: https://liam.page/2018/01/12/Mersenne-twister/

如果知道若干个连续生成的随机数,就可预测下一个

BITSCTF2025: Praise Our RNG Gods

# mersenne-twister-predictor

使用 mt19937predictor 这个 python 包

MT19937 介绍 BLOG

先 pip 安装

l
pip install mersenne-twister-predictor

使用:

n
import random
from mt19937predictor import MT19937Predictor
predictor = MT19937Predictor()
for _ in range(624):
    x = random.getrandbits(32)
    predictor.setrandbits(x, 32)  # Submit samples here
# When enough samples are given, you can start predicting:
assert random.getrandbits(32) == predictor.getrandbits(32)

# AES-CBC

# Decryption Oracle

# 得到 IV

在 AES 的 CBC 模式下,如果有 Decryption Oracle,那么可以得到 IV 的值,

参考:https://cedricvanrompay.gitlab.io/cryptopals/challenges/27.html

首先发送 3 个 block, C1,C2,C3C_1, C_2,C_3

其中 C2=0x00C_2=\text{0x00} , C3=C1C_3 = C_1 那么解密得到的第一个是 dec(C1)IVdec(C_1) \oplus IV , 第三个是 dec(C1)dec(C_1) 然后它们异或一下就可以了

Python 例子

n
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
def xor(a,b):
    return bytearray([x ^ y for (x,y) in zip(a,b)])
key = b"A" * 16
iv = b"B" * 16
print(f"{iv.hex() = }")
cipher = AES.new(key, AES.MODE_CBC, iv)
ciphertext = cipher.encrypt(pad((b"C" * 16) * 3, AES.block_size))
cipher = AES.new(key, AES.MODE_CBC, iv)
plaintext = cipher.decrypt(ciphertext[:16] + (b"\x00" * 16) + ciphertext)
iv = xor(plaintext[:16], plaintext[32:48])
print(f"{iv.hex() = }") # iv.hex() = '42424242424242424242424242424242'

# RSA

首先生成 p,qp,q 两个大质数,计算

  • N=pqN=p \cdot q
  • φ(n)=(p1)(q1)\varphi(n)=(p-1)\cdot (q-1)

然后选择 ee 作为公钥,计算

d=e1modφ(n)d = e^{-1}\bmod \varphi(n)

是私钥

# 加密

对于 message mm

c=memodnc= m^{e} \bmod n

# 解密

对于 ciphertext cc

m=cdmodnm = c^{d}\bmod n

正确性:

m=(me)d=mmodnm=(m^e)^d=m \bmod n

# 结论

# 可枚举 z

ed1modφ(n)e\cdot d \equiv 1\bmod \varphi(n)

所以

ed=1+zφ(n)e\cdot d=1+z\cdot \varphi(n)

这个 zz[0,e][0,e] 之间

BITSCTF2025 Noob RSA returns

# ECDSA

全称是 Elliptic Curve Digital Signature Algorithm.

在椭圆曲线

y2x3+ax+bmodpy^2 \equiv x^3 + ax +b \bmod p

其中 n×G=On \times G = O

密钥包括私钥和公钥 (dA,QA)(d_A, Q_A) 私钥是 dAd_A 公钥是 QAQ_A

dAd_A[1,n1][1,n-1] 的整数,QA=dA×GQ_A = d_A \times G

# 签名

输入消息 mm , 计算 z=HASH(m)z = HASH(m) , 随机生成 k=CRNG(1,n1)k = CRNG(1,n-1) 然后计算 k×G=(x1,y1)k \times G = (x_1, y_1)

r=x1modns=k1(z+rdA)modnr = x_1 \bmod n \\ s= k^{-1}(z + rd_A) \bmod n

签名是 (r,s)(r,s)

# 验证签名

已知 (r,s),e,QA(r,s), e, Q_A 先计算

u1=zs1modnu2=rs1modnu_1 =zs^{-1} \bmod n \\ u_2 = rs^{-1} \bmod n

然后计算

u1×G+u2×QA=(zs1)×G+(rs1)×(dA×G)=(z+rdA)s1×G=k×G=(x1,y1)u_1 \times G + u_2 \times Q_A \\ = (zs^{-1})\times G+(rs^{-1})\times (d_A \times G) \\ = (z+rd_A) s^{-1} \times G \\ = k \times G = (x_1,y_1)

如果 rrx1x_1 一样,那么签名合法

# Python 库 ecdsa

首先

l
pip install ecdsa

签名和验证

n
import ecdsa
from hashlib import sha256
import random
private_key = ecdsa.SigningKey.generate(curve=ecdsa.SECP256k1, hashfunc=sha256)
dA = private_key.privkey.secret_multiplier
public_key = private_key.verifying_key
print(dA) # 打印 k
print(public_key.pubkey.point.to_bytes()) # 得到点
k = random.randint(1, ecdsa.SECP256k1.order - 1)  
signature = private_key.sign(b"First msg",hashfunc=sha256 ,k=k)
vk = private_key.get_verifying_key()
sig = private_key.sign(b"Hello msg")
vk.verify(sig, b"Hello msg")
vk.verify(signature, b"First msg") # 如果报错说明验证错误
# 手动签名 1:
priv_key = ecdsa.SigningKey.from_secret_exponent(dA, curve=ecdsa.SECP256k1)
priv_key.sign(b"Hello msg",k=12)
print(sig)
# 得到 r,s
r = int.from_bytes(sig[:32])
s = int.from_bytes(sig[32:])
z = int.from_bytes(sha256(b"Hello msg").digest()) % ecdsa.SECP256k1.order