Crypto随笔扫盲

ECDLP（椭圆曲线上的离散对数问题）

概念： 给定素数 p 和椭圆曲线 E，对于 Q=k*P，在已知 P,Q 的情况下求出小于 p 的正整数 k。可以证明由 k 和 P 计算 Q 比较容易，而由 Q 和 P 计算 k 则比较困难。

方法：（类似DL问题）

  • 暴力搜索（Brute Force）：适用于小规模，k比较小

  • Pollard’s Rho 算法：适用于群的阶较大。这是一种概率性算法，基于随机游走和生日悖论，复杂度为$O(\sqrt{n})$，其中 n 是群的阶。结合中国剩余定理（CRT）组合结果。

  • Pohlig-Hellman 算法：适用于阶可以分解为多个小素数的幂。

  • Baby-Step Giant-Step 算法（小步大步法）：通过预计算和查找表的方式将问题分解为两个部分，复杂度为$O(\sqrt{n})$，需要较大的存储空间。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
#sage
p = 
a = 
b = 
E = EllipticCurve(GF(p),[a,b]) #Weierstrasss形式（椭圆曲线标准形式）
P = E(, ) 
Q = E(, ) 
k = discrete_log(Q, P, operation='+') 
#或 discrete_log_rho(a,base,ord,operation)
#或 bsgs(base,a,bounds,operation)
#或 k = Q.log(P)

print(k)

TH曲线 (Twisted Hessian Curves)

一般方程：

$ax^3+y^3+1=dxy$

加法：

$$ (x_1,y_1)+(x_2,y_2)=(\frac{x_1-y_1^2x_2y_2}{ax_1y_1x_2^2-y_2},\frac{y_1y_2^2-ax_1^2x_2}{ax_1y_1^3-y_1}) $$

倍乘：

$$ 2(x_1,y_1)=(\frac{x_1-y_1^3x_1}{ay_1x_1^3-y_1},\frac{y_1^3-ax_1^3}{ay_1x_1^3-y_1}) $$

取反：

$$ -(x_1,y_1)=(\frac{x_1}{y_1},\frac{1}{y_1}) $$

构造方法：

将原方程转化成齐次三次方程，令$x=\frac{x’}{z},y=\frac{y’}{z}$，

原式变为$ax’^3+y’^3+z^3=dx’y’z$，

然后利用

1
2
cubic = a*x^3 + y^3 + z^3 - d*x*y*z
E = EllipticCurve_from_cubic(cubic, morphism=True)

便可将三次曲线（cubic）转换为椭圆曲线的标准形式（Weierstrass形式）的函数。

例题：

（Hgame 2025）Intergalactic Bound

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
from Crypto.Util.number import *
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from random import randint
import hashlib
from secrets import flag

def add_THCurve(P, Q):  #曲线加法
    if P == (0, 0):
        return Q
    if Q == (0, 0):
        return P
    x1, y1 = P
    x2, y2 = Q
    x3 = (x1 - y1 ** 2 * x2 * y2) * pow(a * x1 * y1 * x2 ** 2 - y2, -1, p) % p
    y3 = (y1 * y2 ** 2 - a * x1 ** 2 * x2) * pow(a * x1 * y1 * x2 ** 2 - y2, -1, p) % p
    return x3, y3


def mul_THCurve(n, P):  #曲线乘法
    R = (0, 0)
    while n > 0:
        if n % 2 == 1:
            R = add_THCurve(R, P)
        P = add_THCurve(P, P)
        n = n // 2
    return R


p = getPrime(96)
a = randint(1, p)
G = (randint(1,p), randint(1,p))
d = (a*G[0]^3+G[1]^3+1)%p*inverse(G[0]*G[1],p)%p   #d=(a * x0^3 + y0^3 + 1)modp * (x0*y0)^-1 modp 
x = randint(1, p)
Q = mul_THCurve(x, G)   #Q=x*G
print(f"p = {p}")
print(f"G = {G}")
print(f"Q = {Q}")

key = hashlib.sha256(str(x).encode()).digest()  #分析可知，目的就是求出x
cipher = AES.new(key, AES.MODE_ECB)
flag = pad(flag,16)
ciphertext = cipher.encrypt(flag)
print(f"ciphertext={ciphertext}")

"""
p = 55099055368053948610276786301
G = (19663446762962927633037926740, 35074412430915656071777015320)
Q = (26805137673536635825884330180, 26376833112609309475951186883)
ciphertext=b"k\xe8\xbe\x94\x9e\xfc\xe2\x9e\x97\xe5\xf3\x04'\x8f\xb2\x01T\x06\x88\x04\xeb3Jl\xdd Pk$\x00:\xf5"
"""

exp：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#sage
G = (19663446762962927633037926740, 35074412430915656071777015320) 
Q = (26805137673536635825884330180, 26376833112609309475951186883)  
p = 55099055368053948610276786301

ciphertext=b"k\xe8\xbe\x94\x9e\xfc\xe2\x9e\x97\xe5\xf3\x04'\x8f\xb2\x01T\x06\x88\x04\xeb3Jl\xdd Pk$\x00:\xf5"   #密文

Gx,Gy=G     #提取G的x，y坐标
Qx,Qy=Q     #提取Q的x，y坐标

M=matrix(GF(p),[[-Gx**3,Gx*Gy],[-Qx**3,Qx*Qy]]) #构造2*2矩阵
y=vector(GF(p),[Gy**3+1,Qy**3+1])               #构造向量
a,d=M.solve_right(y)                            #求解线性方程组
print(a,d)
a=int(a)
d=int(d)
'''
a = 39081810733380615260725035189
d = 8569490478014112404683314361
'''

R.<xx,yy,zz> = Zmod(p)[]
cubic = a * xx^3 + yy^3 + zz^3 - d * xx * yy * zz
E = EllipticCurve_from_cubic(cubic, morphism=True)

GG = E(G)
QQ = E(Q)
k = QQ.log(GG)  #椭圆曲线离散对数问题（ECDLP）
#k=discrete_log(QQ,GG,operation='+')

from Crypto.Cipher import AES
from hashlib import sha256
key=sha256(str(k).encode()).digest()
aes=AES.new(key,AES.MODE_ECB)
print(aes.decrypt(ciphertext))

背包密码

参考：

https://dexterjie.github.io/2024/07/29/背包密码/

背包密码学 - Kamino’s Blog

其他加密算法 | Lazzaro (lazzzaro.github.io)

背包问题：

已知有n个物体体积分别为${a_1,a_2,a_3,…a_n}$，要恰好装满一个容积为S的背包，抽象为数学公式就是

$$ x_1a_1+x_2a_2+x_3a_3+...+x_na_n=S $$

其中$X={x_1,x_2,x_3,…x_n}$ ($x_i$=0或1)

加密过程：

  • 取明文，转成二进制表示$X={x_1,x_2,x_3,…x_n}$。

  • 取超递增序列作为密钥${a_1,a_2,a_3,…a_n}$。

  • 取一个大于每一个密钥的整数M作为模数。

  • 取一个与$M$互质的整数$B$作为乘数。

  • 生成公钥序列$A={A_1,A_2,A_3,…A_n}$，其中$A_i=Ba_i\mod M$

  • 生成密文

$$ S=\sum_{i=1}^nA_i*x_i $$

解密流程：

  • 求乘数$B$的关于模$M$的模逆$B^{-1}$

  • 计算密文

$$ S'=B^{-1}S\mod M=\sum_{i=1}^nx_ia_i \mod M $$
  • 利用超递增序列特性，从大到小解决背包问题。
1
2
3
4
5
6
7
for i in reversed(key):
    if s > i:
        m += '1'
        s -= i
    else:
        m += '0'
        s -= 1

解密攻击：（不知道乘数）

构造格：

$$ \begin{bmatrix} 2 & 0 & 0 & \cdots & m_1\\ 0 & 2 & 0 & \cdots & m_2\\ 0 & 0 & 2 & \cdots & m_3\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ 1 & 1 & 1 & \cdots & 1 \\ \end{bmatrix} $$

利用LLL或BKZ，栗子如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
sum=492226042629702
nbits=32
M=[19620578458228, 39616682530092, 3004204909088, 6231457508054, 3702963666023, 48859283851499, 4385984544187, 11027662187202, 18637179189873, 29985033726663, 20689315151593, 20060155940897, 46908062454518, 8848251127828, 28637097081675, 35930247189963, 20695167327567, 36659598017280, 10923228050453, 29810039803392, 4443991557077, 31801732862419, 23368424737916, 15178683835989, 34641771567914, 44824471397533, 31243260877608, 27158599500744, 2219939459559, 20255089091807, 24667494760808, 46915118179747]
A=Matrix(ZZ,nbits+1,nbits+1)
for i in range(nbits):
    A[i,i]=2
    A[i,-1]=M[i]
for i in range(nbits+1):
    A[-1,i]=1
A[-1,-1]=sum
r=A.LLL()
print(r[0])
#(-1, -1, 1, -1, 1, -1, -1, -1, -1, 1, 1, -1, -1, -1, -1, 1, -1, -1, -1, 1, -1, -1, -1, -1, 1, -1, -1, 1, 1, -1, 1, 1, 0)

正交格

参考：

HSSP与正交格学习笔记 - 0xFFFF

Hgame25 - huangx607087’s Blog

HSSP问题：

$A\vec{x}\equiv\vec{b}\mod p$，已知$\vec{b}$和$p$，而$A$（0,1矩阵）和$\vec{x}$（向量）未知。

四大基本子空间：

  • 行空间： $A\vec{x}=\vec{b}$中，所有$\vec{b}$构成的空间，此时$A$的每一行构成空间的基底向量。

  • 列空间： $A\vec{x}=\vec{b}$中，所有$\vec{b}$构成的空间，此时$A$的每一列构成空间的基底向量。

  • 左0空间： 满足$\vec{x}A=\vec{0}$的所有$\vec{x}$构成的集合，在sagemath中为 A.left_kernel().matrix()。其个数为$m-r+1$，$r$为$A$中互相线性无关的行向量个数。

  • 右0空间： 满足$\vec{x}A=\vec{0}$的所有$\vec{x}$构成的集合，在sagemath中为 A.right_kernel().matrix()。其个数为$n-r+1$，$r$为$A$中互相线性无关的列向量个数。

性质： 行空间和右0空间正交，列空间和左0空间正交。

问题解法：

  • 对已知给定的向量$\vec{h} \mod M$，首先找与$\vec{h}$垂直的$m-n$个短向量$\vec{\mu_i}$

  • 使用$\mu_i$构造格$L_{\frac{1}{x}}$，用$L_{\frac{1}{x}}$找到$L_x$的正交补$\overline{L_x}$

  • 对$\overline{L_x}$使用BKZ恢复$x_i$

参考代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#正交格
import logging
logging.basicConfig(
    level=logging.DEBUG,
    format="[%(levelname)s] %(message)s"
)

# https://github.com/Neobeo/HackTM2023/blob/main/solve420.sage
# faster LLL reduction to replace `M.LLL()` wiith `flatter(M)`
def flatter(M, **kwds):
    from subprocess import check_output
    from re import findall
    M = matrix(ZZ,M)
    # compile https://github.com/keeganryan/flatter and put it in [imath:0]PATH
    z = '[[' + ']\n['.join(' '.join(map(str,row)) for row in M) + ']]'
    ret = check_output(["flatter"], input=z.encode())
    return matrix(M.nrows(), M.ncols(), map(int,findall(b'-?\\d+', ret)))

def checkMatrix(M, wl=[-1, 1]):
    M = [list(_) for _ in list(M)]
    ml = list(set(flatten(M)))
    logging.debug(ml)
    return sorted(ml) == sorted(wl)

def Nguyen_Stern(h, m, n, M):
    B = matrix(ZZ, m)
    B[0, 0] = M
    h0i = Integer(h[0]).inverse_mod(M)
    for i in range(1, m):
        B[i, 0] = - h[i] * h0i
        B[i, i] = 1
    #L = B.BKZ()    # slooooooow
    L = flatter(B)
    logging.info('flatter done.')

    '''
    vh = vector(Zmod(M), h)
    logging.debug([vector(Zmod(M), list(l)) * vh  for l in L])
    '''

    Lxo = matrix(ZZ, L[:m-n])
    Lxc = Lxo.right_kernel(algorithm='pari').matrix() # faster
    logging.info('right_kernel done.')

    '''
    try:
        Lx_real = matrix(ZZ, [xi + [0] * (m - len(xi)) for xi in X])
        rsc = Lxc.row_space()
        logging.debug([xi in rsc for xi in Lx_real])
    except:
        pass
    '''

    e = matrix(ZZ, [1] * m)
    B = block_matrix([[-e], [2*Lxc]])
    Lx = B.BKZ()
    logging.info('BKZ done.')
    assert checkMatrix(Lx)
    assert len(set(Lx[0])) == 1

    Lx = Lx[1:]
    E = matrix(ZZ, [[1 for c in range(Lxc.ncols())] for r in range(Lxc.nrows())])
    Lx = (Lx + E) / 2

    Lx2 = []
    e = vector(ZZ, [1] * m)
    rsc = Lxc.row_space()
    for lx in Lx:
        if lx in rsc:
            Lx2 += [lx]
            continue
        lx = e - lx
        if lx in rsc:
            Lx2 += [lx]
            continue
        logging.warning('Something wrong?')
    Lx = matrix(Zmod(M), Lx2)

    vh = vector(Zmod(M), h)
    va = Lx.solve_left(vh)
    return Lx, va

m = 200#x是n个m维向量组成
n = 100#n是x_i和a_i的个数
M =    #模数
h =    #给定的最终向量h

Lx, va = Nguyen_Stern(h, m, n, M)
print("向量a:",va)
print("矩阵x:",Lx)

（代码这里先偷了，后续会自己实现的qwq）

附上Arch Linux安装flatter步骤：

1
2
3
4
5
6
7
sudo pacman -S gmp mpfr eigen base-devel gcc git cmake
git clone https://github.com/keeganryan/flatter.git
cd flatter
mkdir build && cd ./build
cmake -DCMAKE_INSTALL_PREFIX=/usr ..
make
sudo make install

DSA

密钥生成

  • 选择一个哈希函数（通常为SHA1）

  • 选择密钥长度L和N

  • 选择N比特的素数q

  • 选择L比特的素数p，使p-1是q的倍数

  • 选择g，使满足$g^k\equiv 1\ mod p$ 的最小正整数k为q。可用$g=h^{\frac {p-1}{q}}$来获得g，其中1 < h <p-1

  • 选择私钥x，0 < x < q,计算$y\equiv g^x \mod p$

公钥为 （p，q，g，y） ，私钥为 （x）

签名

  • 选择随机整数k作为临时密钥，0<k< q

  • 计算$r\equiv(g^k \mod p)\mod q$

  • 计算$s\equiv(H(m)+xr)k^{-1}\mod q$

签名结果为 （r，s） ，与Elgamal 不同，这里使用了哈希函数对消息进行了哈希处理。

验证

  • 计算辅助值$w=s^{-1}\mod q$

  • 计算辅助值$u_1=H(m)w\mod q$

  • 计算辅助值$u_2=rw\mod q$

  • 计算$v=(g^{u_1}y^{u_2}\mod p)\mod q$

  • 检验$v$和$r$是否相等。

攻击方法

1.已知k

  • 利用$s\equiv(H(m)+xr)k^{-1}\mod q$

  • 可以计算$x\equiv(ks-H(m))r^{-1}\mod q$

2.k共享

  • 已知两次签名用了相同的k，即
$$ s_1\equiv(H(m_1)+xr)k^{-1}\mod q \\ s_2\equiv(H(m_2)+xr)k^{-1}\mod q $$
  • 两式相减，得
$$ k(s_1-s_2)\equiv H(m_1)-H(m_2)\mod q \\ k\equiv (H(m_1)-H(m_2))(s_1-s_2)^{-1}\mod q $$

得到k后，同上解出x。

bytes_to_long函数探究

用途： 将字节序列转换成长整数。

转换过程： 每个字节被解释为一个8位无符号整数，从最低位到最高位逐字节累加，每向左移动一位，数值乘以$2^8(即256)$。

（其实应该等价于把字节转换成8位二进制拼接，然后转换成十进制）

示例：b'\x01\x02\x03转换过程如下

$$ 0x01 \times 256^2 + 0x02\times 256^1+0x03\times 256^0 $$

流密码

概念： 以最小单位比特作为一次加密、解密的操作元素。目前都是对称加密。

特点：

  • 流密码的密钥派生自一个较短的密钥，派生算法通常为一个伪随机数生成算法。

  • 流密码的密钥长度会与明文长度相同。

关键： 在于设计好的伪随机数生成器，其基本构造模块为反馈移位寄存器(FSR)。

伪随机数生成器(PRNG)

别称： 确定性随机位生成器（DRBG）

用途： 用来生成接近绝对随机数序列的数字序列的算法。

主要类型：

  • 线性同余生成器（LCG）

    见博客文章《Crypto基础篇-LCG》

  • 线性回归发生器

  • Mersenne Twister

  • xorshift generators

  • WELL family of generators

  • 线性反馈移位寄存器（LFSR）

LFSR线性反馈移位寄存器

用途： 用于产生伪随机数。

概念： LFSR是反馈寄存器中的一种，另一种为NFSR（非线性反馈寄存器）。

结构：

ps：若反馈函数是线性的，则其成为线性反馈移位寄存器（LFSR）

过程表示：

Python中的random函数（MT19937）

介绍： python内置的random方法使用的是梅森旋转算法MT19937，最长周期为一个梅森素数$2^{19937} -1$ 。并且在Python中是基于32位的MT19937-32.
攻击方法：
使用randcrack库进行预测，使用方法也非常简单，
只需将前624个32bit的random生成的随机数提交给randcrack，便可以预测之后的随机数。
代码实现：

1
2
3
4
5
6
7
8
9
from randcrack import RandCrack

rc = RandCrack()
arr=[] #已知的624个32bit随机数
for i in arr:
	rc.submit(i)

rand_next = rc.predict_getrandbits(10000) #改成自己所需要的位数
print(rand_next)

特殊情况： 如果只有312个64bit的random数呢？
首先，我们要理解random库生成随机数的本质，
形象的来说，每个随机数都是从一个长bit数的低位切割下来得到的。
举个例子，如果种子数相同，
第一个序列生成一个64bit数，
第二个序列生成两个32bit数，
结果会怎样呢，事实便是两个32bit数按照先生成的在低位，后生成的在高位拼接，就会得到这个64bit数。
总结： 即使只有312个64bit数，将其拆分成624个32bit数之后，仍然能够进行预测，其他长度也同理，只要长度总和达到624×32就可以预测。

简单的OTP（一次一密）

介绍： 明文、密钥、密文长度均相同
分析： 已知明文、密文，可通过异或获得密钥，如果密钥复用，便可以进行攻击。

Study
#CTF
Crypto随笔扫盲
http://ramoor.github.io/2025/02/28/Crypto随笔扫盲/
作者
Ramoor
发布于
2025年2月28日
许可协议