# crypto

**Repository Path**: weiweqi/crypto

## Basic Information

- **Project Name**: crypto
- **Description**: No description available
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2026-01-19
- **Last Updated**: 2026-01-24

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# Crypto


## 一、前置理论


### 1. 初等数论

#### 整数理论

- 整除定义和基本性质
- 带余数除法
- 辗转相除法

### 2. 同余基本知识

- 同余的定义和基本性质

**定义（同余）** 设 $m \neq 0$. 若 $m | a - b$，即 $a - b = km$，则称  $m$ 为**模**，并称 **$a$ 同余于 $b$ 模 $m$** 或 **$b$ 是 $a$ 对模 $m$ 的剩余**，记作
$$
a \equiv b \pmod m
$$
上式称为**模 $m$​** 的同余式，简称**同余式**。转换为等式：$a = km + b$​

**性质 1**  同余式一种等价关系，即有
$$
\begin{align}
& a \equiv a \pmod m \\
& a \equiv b \pmod m \Leftrightarrow b \equiv a \pmod m \\
& a \equiv b \pmod m, \ b \equiv c \pmod m \Rightarrow a \equiv c \pmod m
\end{align}
$$



### 同余式

### 模逆元

非零实数 $a\in\mathbf R$ 的乘法逆元就是它的倒数 $a^{-1}$．类似地，数论中也可以定义一个整数 $a$ 在模 $m$ 意义下的逆元 $a^{-1}\bmod m$，或简单地记作 $a^{-1}$．这就是 模逆元（modular multiplicative inverse），也称作 数论倒数．

**逆元**：对于非零整数 $a,m$，如果存在 $b$ 使得 $ab\equiv 1\pmod m$，就称 $b$ 是 $a$ 在模 $m$ 意义下的 逆元（inverse）.

这相当于说，$b$ 是线性同余方程 $ax\equiv 1\pmod m$ 的解．根据 线性同余方程 的性质可知，当且仅当 $\gcd(a,m)=1$，即 $a,m$ 互素时，逆元 $a^{-1}\bmod m$ 存在，且在模 $m$ 的意义下是唯一的．

### 费马小定理

设 $p$ 是素数．对于任意整数 $p$ 且 $p\nmid a$，都成立 $a^{p-1} \equiv 1 \pmod p$.

设 $p$ 是素数．对于任意整数 $a$，都成立 $a^p \equiv a \pmod p$.

费马小定理的逆命题并不成立．即使对于所有与 $n$ 互素的 $a$，都有 $a^{n-1} \equiv 1 \pmod n$，那么，$n$ 也未必是素数.

### 欧拉函数

欧拉定理（Euler's theorem）将费马小定理推广到了一般模数的情形，但仍然要求底数与指数互素．

对于整数 $m>0$ 和整数 $a$，且 $\gcd(a,m)=1$，有 $a^{\varphi(m)}\equiv 1\pmod{m}$，其中，$\varphi(\cdot)$ 为 **欧拉函数**．

对于素数 $p$，有 $\varphi(p)=p-1$，因此，费马小定理是欧拉定理的一个特例．另外，欧拉定理中的指数 $\varphi(m)$ 在一般情形下并非使得该式成立的最小指数．它可以改进到 $\lambda(m)$，其中，$\lambda(\cdot)$ 是 **Carmichael 函数**．

### 扩展欧拉定理

扩展欧拉定理1进一步将结论推广到了底数与指数不互素的情形．由此，它彻底解决了任意模数下任意底数的幂次计算问题，将它们转化为指数小于 $\varphi(m)$ 的情形，从而可以通过 快速幂 在 $O(\log\varphi(m))$ 时间内计算．

<img style="width:800px" src="./assets/image2.png">

### 欧几里得算法(辗转相除法)

已知两个数 $a$ 和 $b$，计算二者的最大公约数.

$\gcd(a,b)=\gcd(b,a \bmod b)$

```python
# 递归法
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)
  
# 迭代法
def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

# 辗转相减法(更相减损术)
def gcd(a, b):
    while a != b:
        if a > b:
            a = a - b
        else:
            b = b - a
    return a
```
### 扩展欧几里得算法(EXGCD)

扩展欧几里得算法（Extended Euclidean algorithm, EXGCD），常用于求 $ax+by=\gcd(a,b)$ 的一组可行解．

<img style="width:800px" src="./assets/image4.png">

```python
def exgcd(a, b):
    if b == 0:
        return a, 1, 0
    d, x, y = exgcd(b, a % b)
    return d, y, x - (a // b) * y
```

### 线性同余方程


### 中国剩余定理(CRT)

<img style="width:800px" src="./assets/image3.png">

**过程**

1. 计算所有模数的积 $n$；
2. 对于第 $i$ 个方程：
   1. 计算 $m_i=\frac{n}{n_i}$；
   2. 计算 $m_i$ 在模 $n_i$ 意义下的 逆元 $m_i^{-1}$；
   3. 计算 $c_i=m_im_i^{-1}$（不要对 $n_i$ 取模）．
3. 方程组在模 $n$ 意义下的唯一解为：$x=\sum_{i=1}^k a_ic_i \pmod n$．

```python

# 欧几里得算法
def egcd(a, b):
    if a == 0:
        return b, 0, 1
    g, x1, y1 = egcd(b % a, a)
    x = y1 - (b // a) * x1
    y = x1
    return g, x, y

# 模逆运算
def invmod(a, b):
    g, x, y = egcd(a, b)
    if g != 1:
        raise ValueError('模逆不存在')
    else:
        return x % b

# 中国剩余定理
def crt(a, m):
    for i in range(len(m)):
        for j in range(i + 1, len(m)):
            if egcd(m[i], m[j])[0] != 1:
                print(f"m[{i}]和m[{j}]不互素,不能直接利用中国剩余定理")
                sys.exit(1)
    M = 1
    for i in m:
        M *= i
    print(f"m = {M}")
    M_j = [0] * len(m)
    N_j = [0] * len(m)
    x_j = [0] * len(m)
    x_ans = 0
    for j in range(len(m)):
        M_j[j] = M // m[j]
        N_j[j] = invmod(M_j[j], m[j])
        x_j[j] = a[j] * M_j[j] * N_j[j] % M
        print(f"M[{j}] = {M_j[j]}\nM[{j}]^-1 = {N_j[j]}\nx[{j}] = {x_j[j]}")
        x_ans += x_j[j]
        x_ans %= M
    return x_ans % M

```


## 参考文献
1. [OI Wiki 数学部分](https://oi-wiki.org/math/)
2. [CTF Wiki Crypto部分](https://ctf-wiki.org/en/crypto/introduction/)
3. 初等数论（第四版）潘承洞，潘承彪编，北京大学出版社
4. 初等数论（第四版）闵嗣鹤、严士健编，高等教育出版社



## Python库和工具

- `openssl`

### 分解整数工具

- 网站分解：https://factordb.com/

- 命令行分解：https://github.com/ryosan-470/factordb-python

- yafu：https://sourceforge.net/projects/yafu/

- msieve：https://github.com/radii/msieve

### Python 工具

- `sympy`：[SymPy](https://docs.sympy.org/latest/index.html) 是一个用于符号数学的Python库，提供从基本符号算术到微积分、代数、离散数学和量子物理等领域的完整计算机代数系统功能。Crypto中主要使用素数操作、因数分解、最大公约数/最小公倍数等。

- `libnum`：提供整数操作、素数处理、模运算、RSA操作等常见数论和密码学功能，常用于字节转字符串、转数字。

- `pycryptodemo`：用于加解密

- `gmpy2`：

- `RSAtool`：https://github.com/ius/rsatool

```bash
# 安装 rsatool
git clone https://github.com/ius/rsatool.git
cd rsatool
pip install -r requirements.txt
python setup.py install

# 生成私钥
python rsatool.py -o prikey.pem -e 65537 -p 319576316814478949870590164193048041239 -q 275127860351348928173285174381581152299

# RSA爆破
python RsaCtfTool.py --publickey key.pem --uncipherfile cipher.bin
```

```bash
# 生成私钥, PEM output to key.pem:
python rsatool.py -f PEM -o key.pem -n 13826123222358393307 -d 9793706120266356337

# Supplying two primes, DER output to key.der:
python rsatool.py -f DER -o key.der -p 4184799299 -q 3303891593
```

- `RSA Converter`



## RSA

1. 选取两个不同的大素数 $p$ 和 $q$，计算 $N = p \cdot q$。

2. 根据欧拉函数，求得 $\varphi(N) = \varphi(pq) = \varphi(p)\varphi(q) = (p-1)(q-1)$

2. 然后取一个大整数 $e$，满足 $1<e<\varphi(N)$，且 $e$ 与 $\varphi(N)$互素 $(e, \varphi(N)) = 1$，$e$ 用做加密密钥。

3. 取 $e$ 的模反数为 $d$（逆元），计算方法：$ed \equiv 1 \pmod{\varphi(N)}$，$d$ 为脱密密钥。

4. 将 $p$ 和 $q$ 的记录销毁，公钥：$(N,\ e)$，私钥： $(N,\ d)$。

- 加密：$c = m^e \pmod N$

- 脱密：$m = c^d \pmod N$


对明文 $m$ 进行加密：$c = m^e \ \% \ N$，得到的 $c$ 即为密文。

```python
c = pow(m, e, N)
```

对密文 $c$ 进行解密：$m = c^d \ \% \ N$，得到的 $m$ 即为明文。

```python
m = pow(c, d, N)
```

$$
A \xleftrightarrow[\text{} 脱密 m = c^d \pmod N \text{}]{{\quad 加密 c = m^e \pmod N \quad}} B
$$

- $p$ 和 $q$：时大整数N的两个因子（factor）

- $N$：大整数 $N$，成为模数（modulus）

- $e$ 和 $d$：互为模反数的两个指数（exponent），$e \cdot d \equiv 1 \pmod {\varphi(N)}$，即 $e \cdot d = 1 + k \cdot \varphi(N)$

- $c$ 和 $m$：分别是密文和明文，一般指十进制数。

- $(N, e)$：公钥

- $(N, d)$：私钥


### 欧拉函数

$\varphi(n)$ 定义为小于 $n$ 的自然数中与 $n$ 互质的数的个数。

例子：

$p=5$

0，1，2，3，4

$\varphi(5)=4$

任何一个素数 $p$ 的欧拉函数等于 $p - 1$


$\varphi(n) = (p-1) * (q-1)$

### 欧拉定理

若 $n,a$ 为正整数 ，且 $n,a$互素$gcd(n, a)=1$，则

$a^{\varphi(n)} \equiv 1 \pmod n$

转为等式 $a^{\varphi(n)} = 1 + kn$ 或 $a^{\varphi(n)} \mod n = 1$，$k$为任意整数。


### 费马小定理

若 $p$ 是素数，$a$ 与 $p$ 互素，

$a^p \equiv a \pmod p$

$a^{p-1} \equiv 1 \pmod p$


## 模运算

```
(a + b) % p = (a % p + b % p) % p
(a - b) % p = (a % p - b % p) % p
(a * b) % p = (a % p * b % p) % p
a ^ b % p = (a % p) ^ b % p

结合律
((a + b) % p) + c = (a + (b + c) % p) % p
((a * b) % p) * c = (a * (b * c) % p) % p

交换律
(a + b) % p = (b + a) % p
(a * b) % p = (b * a) % p

分配律
(a + b) % p = (a + % p + c% p) % p
((a + b) % p * c) % p = (a * c) % p + (b * c) % p

```

> 重要定理

- 若 $a \equiv b \pmod p$，则对任意的 c，都有 $(a+c) \equiv (b+c) \pmod p$

- 若 $a \equiv b \pmod p$，则对任意的 c，都有 $(a*c) \equiv (b*c) \pmod p$

- 若 $a \equiv b \pmod p$，$c \equiv d \pmod p$，则
  - $(a+c) \equiv (b+d) \pmod p$
  - $(a-c) \equiv (b-d) \pmod p$
  - $(a*c) \equiv (b*d) \pmod p$
  - $(a/c) \equiv (b/d) \pmod p$

### 逆元
在一个给定的模数 $p$ 下，如果存在一个数 $x$，使得数 $a$ 与 $x$ 相乘后对 $p$ 取模的结果为 $1$，那么 $x$ 就被称为 $a$ 的模乘法逆元（Modular Multiplicative Inverse）。公式表示如下：

$$
ax \equiv 1 \pmod p
$$

$x$ 就是 $a$ 在 模 $p$ 意义下的 逆元。

要求：

- $a$ 和 $m$ 互质，否则 $a$ 的逆元不存在。

- $x$ 的值通常在 $1$ 到 $m - 1$ 的范围内。


$a \pmod p$ 的逆元可以写作 $a * a' \pmod p \equiv 1$

### 推导过程

- 加密：式一 $c = m^e \mod N$

- 脱密：式二 $m = c^d \mod N$

将式一导入式二，得 $ m = (m^e \mod N)^d \mod N$

需要证明：$ m = (m^e \mod N)^d \mod N$

$$
\begin{align}
(m^e \mod N)^d \mod N &= (m^{e})^d \mod N \\
&= m^{ed} \mod N \\
&= m^{1 + k*\varphi(N)} \mod N \\
&= m*m^{k*\varphi(N)} \mod N \\
&= (m \mod N * m^{k*\varphi(N)} \mod N) \mod N \\
&= (m \mod N * (m^{\varphi(N)})^k \mod N) \mod N \\
&= (m \mod N * (m^{\varphi(N)} \mod N)^k \mod N) \mod N \\
&= (m \mod N * 1^k \mod N) \mod N \\
&= (m \mod N) \mod N \\
&= m \mod N \\
&= m \\
\end{align}
$$


1. 把 $a$ 看作 $m^e$，a ^ b % p = (a % p) ^ b % p

2. $e*d \equiv 1 \pmod {\varphi(N)}$

3. $e*d = 1 + k*\varphi(N)$

4. (a * b) % p = (a % p * b % p) % p

5. a ^ (b * c) = (a ^ b) ^ c

6. a ^ b % p = (a % p) ^ b % p

7. 欧拉定理 $a^{\varphi(n)} \mod n = 1$ 

8. $1^k \mod N = 1$

9. 因为 $m = c^d \mod N$，m是余数，$N$除数。而余数肯定小于除数，所以 $m < N$，$m \mod N = m$


## RSA攻击类型

模数相关攻击
- 暴力分解 N，条件：N 的比特位数小于 512。
- p 和 q 选取不当分解 N
  - |p - q| 很大
  - |p - q| 很小
  - p - 1 光滑
  - p + 1 光滑
- 模不互素：有两个公钥的 N 不互素，可对这两个数求最大公因数，然后直接获得 p 和 q。
- 共模攻击：有两个相同的 N、两个不同的e时，加密同一明文m。

公钥指数相关攻击
- 小公钥指数攻击：e 特别小，比如 e 为 3
- RSA 衍生算法——Rabin 算法：e = 2

私钥 d 相关攻击
- d 泄露攻击
- Wiener's Attack：在 $d$ 比较小（$d < \frac{1}{3}N^{0.25}$）时，使用 Wiener's Attack 求解出 d。

Coppersmith 相关攻击 

RSA 选择明密文攻击

RSA 侧信道攻击

Bleichenbacher's attack



### 模数相关攻击

#### 共模攻击

漏洞特征：n相同的，有两个e和两个c，两个e互素。

已知 n1,n2,e1,e2,c1,c2，要求n1 = n2，e1 和 e2 互素。

##### 原理

共模攻击基于扩展欧几里得算法。


扩展欧几里得算法：对于不完全为 0 的整数，$a，b，gcd(a, b)$，一定存在整数 x，y，使得 $gcd(a, b) = ax + by$.

```python
c1 = m1^e1 % n
c2 = m2^e2 % n
gcd(e1, e2) = 1
m1 = m2 = m
```
> 证明 ((c1^s1 % n) * (c2^s2 % n)) % n = m

```python
# 先去掉 最里面的 % n，根据：(a * b) % p = (a % p * b % p) % p
= ((c1^s1) * (c2^s2)) % n
# 将c1 和 c2 带入替换
= (((m1^e1 % n)^s1) * ((m2^e2 % n)^s2)) % n
# 最里面的 % n 移外面，根据：a ^ b % p = (a % p) ^ b % p
= (((m1^e1)^s1 % n) * ((m2^e2)^s2 % n)) % n
# 去掉 最里面的 % n，根据：(a * b) % p = (a % p * b % p) % p
= (((m1^e1)^s1) * ((m2^e2)^s2)) % n
# 合并指数幂，根据：(a^m)^n = a^(m*n)
= (m1^(e1*^s1) * m2^(e2*s2)) % n
# 因为 m1 = m2 = m，根据：a^m*a*n=a^(m+n)
= (m^(e1*s1+e2*s2)) % n
# 因为gcd(e1, e2)=1，根据扩展欧几里得算法，gcd(e1, e2)=e1*x+e2*y=1，
# 设x=s1，y=s2，即 gcd(e1, e2)=e1*^s1+e2*s2=1
= (m^1) % n
# 因为 c1 = m1^e1 % n > 0，所以 m < n => m % n = n
= m
```

#### 解题脚本

```python
import libnum
import gmpy2

n = 
e1 = 
e2 = 
c1 = 
c2 = 

def exp_def(e1, e2, c1, c2, n):
    s, s1, s2 = gmpy2.gcdext(e1, e2)
    m = (pow(c1, s1, n) * pow(c2, s2, n)) % n
    return int(m)

m = exp_def(e1, e2, c1, c2, n)
print(libnum.n2s(m))
```


### 维纳攻击(Wiener Attack)

漏洞特征：$e$ 过大或过小。

在 $e$ 过大或过小的情况下，可使用算法从 $e$ 中快速推断出 $d$ 的值。