# 密碼學數論 / 筆記

###### tags: `資安`

[TOC]

## 費馬小定理 a^(p-1) = 1 (mod p)
p is prime $\implies$ $a^{(p-1)} \equiv 1\ (mod\ p)$

延伸:
### a^p = a (mod p)
$$
\begin{aligned}
a^p &\equiv a^{p-1} \times a &(mod\ p) \\
&\equiv 1 \times a &(mod\ p) &\leftarrow 費馬小定理 \\
&\equiv a &(mod\ p) \\
\end{aligned}
$$

### a^(p-2) = a^(-1) (mod p)
$$
\begin{aligned}
a^{p-2} &\equiv a^{p-1} \times a^{-1} &(mod\ p) \\
&\equiv 1 \times a^{-1} &(mod\ p) &\leftarrow 費馬小定理 \\
&\equiv a^{-1} &(mod\ p) \\
\end{aligned}
$$

### (a+b)^p = a^p + b^p (mod p)
$$
\begin{aligned}
(a+b)^p &\equiv a+b &(mod\ p) &\leftarrow 費馬小定理延伸一 \\
&\equiv a^p + b^p &(mod\ p) &\leftarrow 費馬小定理延伸一
\end{aligned}
$$

## 尤拉定理
$a^{\phi(n)} \equiv 1\ (mod\ n)$

$\phi(n)$: 在 $\leq$ n 的數中與 n 互質 ($\bot$) 的數

### phi(n)
1. p is prime: $\phi(p) = p - 1$
2. $\phi(p^k) = p^{k-1} \times (p-1)$
3. m, n 互質: $\phi(m \times n) = \phi(m) \times \phi(n)$

## 二次殘差 Quadratic Residues
定義: 如存在一數 a 使 $a^2 \equiv n\ (mod\ p)$，則 n 為二次殘差 QR，否則為非二次殘差 QNR

性質:

QR * QR = QR
QR * QNR = QNR
QNR * QNR = QR

QR ^ e = QR

如何判斷一數是否為 QR:
### 勒讓德符號 Legendre Symbol
當 p 為奇數質數

$$
(\frac{n}{p}) \equiv n^{(p-1)/2}\ (mod\ p) = \left\{
\begin{aligned}
+1 &, \ n\ 為\ QR \\
-1 &, \ n\ 為\ QNR \\
0 &, \ n \equiv 0\ (mod\ p) \\
\end{aligned}
\right.
$$

尋找 a 的方式:
### p = 3 (mod 4)
$a = \pm n^{(p+1)/4}$

proof:
$$
\begin{aligned}
(\pm n^{(p+1)/4})^2 & \equiv a^{(p+1)/2} &(mod\ p) \\
& \equiv a^{(p-1+2)/2} &(mod\ p) \\
& \equiv a^{(p-1)/2+1} &(mod\ p) \\
& \equiv a^{(p-1)/2} \times a &(mod\ p) \\
& \equiv 1 \times a &(mod\ p) &\leftarrow 勒讓德符號 \\
& \equiv a &(mod\ p)
\end{aligned}
$$

### Tonelli-Shanks algorithm (p = 1 (mod 4))
[wikipedia: Tonelli–Shanks algorithm](https://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm)

當 p 為質數

def tonelli_shanks(y2:int, p:int) -> int:
    assert pow(y2, (p-1)//2, p) == 1, "Not quadratic residues"
    assert p%2 == 1, 'p is not prime'
    if(p%4 == 3):
        y = pow(y2, (p+1)//4, p)
        return y
    
    # 1
    S = 0
    Q = p-1
    while(Q % 2 == 0):
        Q //= 2
        S += 1
    assert Q*(2**S) == p-1
    # 2
    z = 2
    while(pow(z, (p-1)//2, p) != p-1):
        z += 1
    assert pow(z, (p-1)//2, p) == p-1
    # 3
    M = S
    c = pow(z, Q, p)
    t = pow(y2, Q, p)
    R = pow(y2, (Q+1)//2, p)
    # 4
    while(True):
        if(t == 0):
            return 0
        elif(t == 1):
            return R
        else:
            i = 1
            t2 = pow(t, 2, p)
            for i in range(1, M):
                if((t2-1) % p == 0):
                    break
                t2 = pow(t2, 2, p)
            b = pow(c, pow(2, M-i-1), p)
            M = i
            c = pow(b, 2, p)
            t = (t * c) % p
            R = (R * b) % p
    

if __name__ == "__main__":
    y2 = 5
    p = 41
    y = tonelli_shanks(y2, p)
    assert pow(y,2,p) == y2
    assert pow(-y,2,p) == y2

## 中國餘式定理 CRT
[wikipedia: 中國剩餘定理](https://zh.wikipedia.org/zh-tw/中国剩余定理)

import numpy as np
ai = [2, 3, 5]
ni = [5, 11, 17]

N = np.prod(ni, dtype=np.int)
Mi = [int(N//x) for x in ni]
ti = [pow(m,-1,n) for m, n in zip(Mi, ni)]
ans = sum([a*t*m for a, t, m in zip(ai, ti, Mi)])

print(ans % N)

## 線性同餘方法 LCG
[wikipedia: 線性同餘方法](https://zh.wikipedia.org/wiki/線性同餘方法)

一種產生偽隨機數的方法

公式: $n_{i+1} \equiv (a \times n_i + b)\ (mod\ p)$

特性: 當 $n_i \equiv b \times (1-a)^{-1}\ (mod\ p)$ 時，$n_i = n_{i+1} = n_{i+2} = ...$

proof:
$$
\begin{aligned}
x &\equiv (a \times x + b) &(mod\ p) \\
(x - a \times x) &\equiv b &(mod\ p) \\
(1-a) \times x &\equiv b &(mod\ p) \\
x &\equiv b \times (1-a)^{-1} &(mod\ p) \\
b \times (1-a)^{-1} &\equiv (a \times (b \times (1-a)^{-1}) + b) &(mod\ p)
\end{aligned}
$$

以下破解參考[這篇文章](https://tailcall.net/posts/cracking-rngs-lcgs/)
### 破解 LCG 1: 不知加數 (b)
假設已知 $n_0$、$n_1$、$a$、$p$，不知 $b$

公式: $b \equiv n_1 - a \times n_0\ (mod\ p)$

proof:
$$
\begin{aligned}
n_1 &\equiv a \times n_0 + b &(mod\ p) \\
b &\equiv n_1 - a \times n_0 &(mod\ p)
\end{aligned}
$$

### 破解 LCG 2: 不知加數及乘數 (a, b)
假設已知 $n_0$、$n_1$、$n_2$、$p$，不知 $a$、$b$

公式: $a \equiv (n_2 - n_1) \times (n_1 - n_0)^{-1} (mod\ p)$
退化回上一題目

proof:
$$
\begin{aligned}
n_1 &\equiv a \times n_0 + b &(mod\ p) \\
n_2 &\equiv a \times n_1 + b &(mod\ p) \\
n_2 - n_1 &\equiv a \times (n_1 - n_0) &(mod\ p) &\leftarrow 2 式 - 1 式 \\
a &\equiv (n_2 - n_1) \times (n_1 - n_0)^{-1} &(mod\ p)
\end{aligned}
$$

### 破解 LCG 3: 不知加數、乘數及模數 (a, b, p)
假設已知 $n_0$、$n_1$ ... $n_k$ ($k \ge 4$)，不知 $a$、$b$、$p$

令
$$
\begin{aligned}
d_i &= n_{i+1} - n_i &(0 \le i \le k-1) \\
g_i &= d_{i+1} \times d_{i-1} - d_i \times d_i &(1 \le i \le k-2)
\end{aligned}
$$
公式: $p = GCD(g_1, g_2, ... g_{k-2})$
退化回上一題目

proof:
$$
\begin{aligned}
d_0 \equiv n_1 - n_0 & & & &(mod\ p)\\
d_1 \equiv n_2 - n_1 &\equiv (n_1 \times a + b) - (n_0 \times a + b) &\equiv a \times (n_1 - n_0) &\equiv a \times d_0 &(mod\ p) \\
d_2 \equiv n_3 - n_2 &\equiv (n_2 \times a + b) - (n_1 \times a + b) &\equiv a \times (n_2 - n_1) &\equiv a \times d_1 &(mod\ p) \\
d_3 \equiv n_4 - n_3 &\equiv (n_3 \times a + b) - (n_2 \times a + b) &\equiv a \times (n_3 - n_2) &\equiv a \times d_2 &(mod\ p) \\
...
\end{aligned}
$$

$$
\begin{aligned}
g_1 &\equiv d_2 \times d_0 - d_1 \times d_1 &\equiv ((a \times a \times d_0) \times d_0) - ((a \times d_0) \times (a \times d_0)) &\equiv 0 &(mod\ p) \\
g_2 &\equiv d_3 \times d_1 - d_2 \times d_2 &\equiv ((a \times a \times d_1) \times d_1) - ((a \times d_1) \times (a \times d_1)) &\equiv 0 &(mod\ p) \\
...
\end{aligned}
$$

$g_1 = u_1 \times p$
$g_2 = u_2 \times p$
...

$GCD(g_1, g_2, ...) = p$

## 線性 DES/AES

塊加密不能是線性的，否則可以利用一些公式直接破解，通常相關題目設計時會在 sbox 上搞鬼

### 檢測線性

雖然以下圖片是 DES，但 AES 也是異曲同工之妙

[[source]](https://crypto.stackexchange.com/questions/63693/s-box-and-its-linearity)

$DES(k,m1) \oplus DES(k,m2) \oplus DES(k,m3) = DES(k,m1 \oplus m2 \oplus m3)$

import os
from pwn import *

def test_aes(cipher: AES) -> bool:
    key = os.urandom(16)
    m1 = os.urandom(16)
    m2 = os.urandom(16)
    m3 = os.urandom(16)
    res1 = xor(xor(cipher.encrypt(m1), cipher.encrypt(m2)), cipher.encrypt(m3))
    res2 = cipher.encrypt(xor(xor(m1, m2), m3))
    return res1 == res2

if __name__ == "__main__":
    cipher = AES(key, Sbox=sbox)
    isLinear = test_aes(cipher)

### 利用線性特性

參考[這篇文章](https://crypto.stackexchange.com/questions/20228/consequences-of-aes-without-any-one-of-its-operations/70107#70107)，可知線性 AES 可被 model 成 $ct = A \times pt + k$ 格式，只要求出 A 和 k 的值代表即可任意加解密

- $ct$, $pt$ 屬 GF(2) (i.e. bits)
- $A$ 為一 $128 \times 128$ 的 GF(2) 矩陣，與 key 無關但與結構有關
- $k$ 為一長度 128 的 GF(2) 向量，與 key 相關

#### 求 A

$p_0 = \begin{bmatrix} 0 \\ 0 \\ \vdots \\ 0 \end{bmatrix}$
$p_1 = \begin{bmatrix} 1 \\ 0 \\ \vdots \\ 0 \end{bmatrix}$
$p_2 = \begin{bmatrix} 0 \\ 1 \\ 0 \\ \vdots \\ 0 \end{bmatrix}$
$p_n = \dots$
$p_{128} = \begin{bmatrix} 0 \\ \vdots \\ 0 \\ 1 \end{bmatrix}$
$c_0 = A \times p_0 + k$
$c_1 = A \times p_1 + k$
$...$
$c_{128} = A \times p_{128} + k$
$\begin{aligned}
C &= \begin{bmatrix} c_1 - c_0, c_2-c_0, \dots , c_{128} - c_0 \end{bmatrix} \\
&= \begin{bmatrix} (A \times p_1 + k) - (A \times p_0 + k), \dots , (A \times p_{128} + k) - (A \times p_0 + k) \end{bmatrix} \\
&= \begin{bmatrix} A \times (p_1 - p_0), \dots , A \times (p_{128} - p_0) \end{bmatrix} \\
&= A \times \begin{bmatrix} (p_1 - p_0), \dots , (p_{128} - p_0) \end{bmatrix} \\
&= A \times \begin{bmatrix} p_1, \dots , p_{128} \end{bmatrix} \\
&= A \times P \\
\end{aligned}$

#### 求 k

$c = A \times p + k$
$k = c - A \times p$

#### 腳本

from pwn import xor
from sage.all import GF, matrix, vector

def bits2bytes(x: list) -> bytes:
    return bytes([int("".join(map(str, x[i:i+8])), 2) for i in range(0, len(x), 8)])
def bytes2bits(x: bytes) -> list:
    return list(map(int, "".join(map(lambda x: f"{x:08b}", x))))

def get_A(cipher: AES) -> matrix:
    # c = Ax+k
    # c-c0 = A(x-x0)
    # C = AX
    X = []
    C = []
    base = cipher.encrypt(bits2bytes([0]*128))[:16] # we don't need the cipher of padding
    for i in range(128):
        pt = [0]*i + [1] + [0]*(127-i)
        ct = cipher.encrypt(bits2bytes(pt))[:16] # we don't need the cipher of padding
        X.append(pt)
        C.append(bytes2bits(xor(ct,base)))

    mat_X = matrix(GF(2), X).transpose()
    mat_C = matrix(GF(2), C).transpose()
    mat_A = mat_X.solve_left(mat_C)
    return mat_A

def get_k(cipher: AES, known_pt: bytes, known_ct: bytes) -> vector:
    vec_c = vector(bytes2bits(known_ct))
    vec_x = vector(bytes2bits(known_pt))
    vec_k = vec_c - mat_A * vec_x
    return vec_k

def break_AES(cipher: AES, known_pt: bytes, known_ct: bytes, unknown_ct: bytes) -> bytes:
    pt = b""
    mat_A = get_A(cipher)
    vec_k = get_k(cipher, known_pt, known_ct)
    
    # c = Ax+k
    # c-k = Ax
    for i in range(0, len(unknown_ct), 16):
        curr_ct = vector(bytes2bits(unknown_ct[i:i+16]))
        curr_pt = mat_A.solve_right(curr_ct - vec_k)
        pt += bits2bytes(curr_pt)
    return pt

if __name__ == "__main__":
    cipher = AES(key, Sbox=sbox)
    plainText = bytes.fromhex(input("Input plaintext(hex): "))[:16]
    cipherText = bytes.fromhex(input("Input ciphertext(hex): "))[:16]
    ct_flag = bytes.fromhex(input("Input cipherflag(hex): "))
    pt_flag = break_AES(cipher, plainText, cipherText, ct_flag)
    print(pt_flag)

## DES 特殊性質
### 補數

即 $E_k(P) = C$，$E_\bar{k}(\bar{P}) = \bar{C}$

[Data Encryption Standard - Wikipedia](https://en.wikipedia.org/wiki/Data_Encryption_Standard#Minor_cryptanalytic_properties)

### Weak key

在某些 key 的情況下，$E_{k_1}(E_{k_2}(P)) = P$

[Weak key - Wikipedia](https://en.wikipedia.org/wiki/Weak_key)
[Recommendation for the Triple Data Encryption Algorithm (TDEA) Block Cipher](https://nvlpubs.nist.gov/nistpubs/Legacy/SP/nistspecialpublication800-67r1.pdf) $\S$ 3.4.2

#### single key

即在 $k_1 = k_2$ 的情況下有前者的特性

- `0x0000000000000000`
- `0x0101010101010101`
- `0x1E1E1E1E0F0F0F0F`
- `0x1F1F1F1F0E0E0E0E`
- `0xE0E0E0E0F1F1F1F1`
- `0xE1E1E1E1F0F0F0F0`
- `0xFEFEFEFEFEFEFEFE`
- `0xFFFFFFFFFFFFFFFF`

#### semi-weak key

在 $k_1 \ne k_2$ 的情況

- `0x011F011F010E010E` + `0x1F011F010E010E01`
- `0x01E001E001F101F1` + `0xE001E001F101F101`
- `0x01FE01FE01FE01FE` + `0xFE01FE01FE01FE01`
- `0x1FE01FE00EF10EF1` + `0xE01FE01FF10EF10E`
- `0x1FFE1FFE0EFE0EFE` + `0xFE1FFE1FFE0EFE0E`
- `0xE0FEE0FEF1FEF1FE` + `0xFEE0FEE0FEF1FEF1`

#### possibly weak key

在某些 key 的情況下，切分出來的 subkey 只會產生 4 個 (而非 16 個)

以下為部分範例，詳細部分請參考[Recommendation for the Triple Data Encryption Algorithm (TDEA) Block Cipher](https://nvlpubs.nist.gov/nistpubs/Legacy/SP/nistspecialpublication800-67r1.pdf) $\S$ 3.4.2

- `0x01011F1F01010E0E`
- `0x1F01FEE00E01FEF1`
- `0x1F1F01010E0E0101`
- `0xE0E00101F1F10101`
- `0xE0E01F1FF1F10E0E`
- `0xFEFEE0E0FEFEF1F1`
- ...

## 同態加密 (Paillier cryptosystem)
### 特性
#### encryption

$n = p \times q$
$g = n + 1$
$r = rand(1, n)$
$enc \equiv g^m \times r^n \mod{n^2}$

相當於是 $m^e \mod{n}$，此處 $e$ 為自然指數

#### decyption

$n = p \times q$
$\phi = (p-1) \times (q-1)$
$\mu = \phi^{-1} \mod{n}$
$msg = \lfloor \frac{c^\phi \mod{n^2} - 1}{n} \rfloor \times \mu \mod{n}$

相當於是 $log{(c)} \mod{n}$，此處 $log$ 為以自然指數為基底的 log

### additive homomorphic

同態加密有此特性: $f(x+y) = f(x) \cdot f(y)$

因此可得出 $f(x+1) = f(x) \cdot f(1) = f(x) \cdot g$

有時可搭配 RSA 的 Related Message Attack 進行破解

example: [prsa](https://github.com/maple3142/My-CTF-Challenges/blob/master/AIS3%20EOF%202025/prsa/README.md)