密碼學數論 / 筆記

tags: 資安

• 密碼學數論 / 筆記
  • 費馬小定理 a^(p-1) = 1 (mod p)
    • a^p = a (mod p)
    • a^(p-2) = a^(-1) (mod p)
    • (a+b)^p = a^p + b^p (mod p)
  • 尤拉定理
    • phi(n)
  • 二次殘差 Quadratic Residues
    • 勒讓德符號 Legendre Symbol
    • p = 3 (mod 4)
    • Tonelli-Shanks algorithm (p = 1 (mod 4))
  • 中國餘式定理 CRT
  • 線性同餘方法 LCG
    • 破解 LCG 1: 不知加數 (b)
    • 破解 LCG 2: 不知加數及乘數 (a, b)
    • 破解 LCG 3: 不知加數、乘數及模數 (a, b, p)
  • 線性 DES/AES
    • 檢測線性
    • 利用線性特性
  • DES 特殊性質
    • 補數
    • Weak key
  • 同態加密 (Paillier cryptosystem)
    • 特性
    • additive homomorphic

費馬小定理 a^(p-1) = 1 (mod p)

p is prime

$⟹$

$a^{(p-1)}\equiv 1(modp)$

延伸:

a^p = a (mod p)

$$\begin{array}{rlr}{a}^p& \equiv a^{p-1}\times a& (modp)\\ & \equiv 1\times a& (modp)& \leftarrow \mathrm{費}\mathrm{馬}\mathrm{小}\mathrm{定}\mathrm{理}\\ & \equiv a& (modp)\end{array}$$

a^(p-2) = a^(-1) (mod p)

$$\begin{array}{rlr}{a}^{p-2}& \equiv a^{p-1}\times a^{-1}& (modp)\\ & \equiv 1\times a^{-1}& (modp)& \leftarrow \mathrm{費}\mathrm{馬}\mathrm{小}\mathrm{定}\mathrm{理}\\ & \equiv a^{-1}& (modp)\end{array}$$

(a+b)^p = a^p + b^p (mod p)

$$\begin{array}{rlrl}(a+b{)}^p& \equiv a+b& (modp)& \leftarrow \mathrm{費}\mathrm{馬}\mathrm{小}\mathrm{定}\mathrm{理}\mathrm{延}\mathrm{伸}\mathrm{一}\\ & \equiv a^p+b^p& (modp)& \leftarrow \mathrm{費}\mathrm{馬}\mathrm{小}\mathrm{定}\mathrm{理}\mathrm{延}\mathrm{伸}\mathrm{一}\end{array}$$

尤拉定理

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

$\varphi (n)$: 在

$\le$ n 的數中與 n 互質 (

$\mathrm{\perp }$) 的數

phi(n)

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

二次殘差 Quadratic Residues

定義: 如存在一數 a 使

$a^2\equiv n(modp)$，則 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}(modp)=\{\begin{array}{rl}+1& ,n\mathrm{為}QR\\ -1& ,n\mathrm{為}QNR\\ 0& ,n\equiv 0(modp)\end{array}$$

尋找 a 的方式:

p = 3 (mod 4)

$a=\pm n^{(p+1)/4}$

proof:

$$\begin{array}{rlr}(\pm n^{(p+1)/4}{)}^2& \equiv a^{(p+1)/2}& (modp)\\ & \equiv a^{(p-1+2)/2}& (modp)\\ & \equiv a^{(p-1)/2+1}& (modp)\\ & \equiv a^{(p-1)/2}\times a& (modp)\\ & \equiv 1\times a& (modp)& \leftarrow \mathrm{勒}\mathrm{讓}\mathrm{德}\mathrm{符}\mathrm{號}\\ & \equiv a& (modp)\end{array}$$

Tonelli-Shanks algorithm (p = 1 (mod 4))

wikipedia: Tonelli–Shanks 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: 中國剩餘定理

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: 線性同餘方法

一種產生偽隨機數的方法

公式:

$n_{i+1}\equiv (a\times n_i+b)(modp)$

特性: 當

$n_i\equiv b\times (1-a{)}^{-1}(modp)$ 時，

$n_i=n_{i+1}=n_{i+2}=...$

proof:

$$\begin{array}{rlr}x& \equiv (a\times x+b)& (modp)\\ (x-a\times x)& \equiv b& (modp)\\ (1-a)\times x& \equiv b& (modp)\\ x& \equiv b\times (1-a{)}^{-1}& (modp)\\ b\times (1-a{)}^{-1}& \equiv (a\times (b\times (1-a{)}^{-1})+b)& (modp)\end{array}$$

以下破解參考這篇文章

破解 LCG 1: 不知加數 (b)

假設已知

$n_0$、

$n_1$、

$a$、

$p$，不知

$b$

公式:

$b\equiv n_1-a\times n_0(modp)$

proof:

$$\begin{array}{rlr}{n}_1& \equiv a\times n_0+b& (modp)\\ b& \equiv n_1-a\times n_0& (modp)\end{array}$$

破解 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}(modp)$
退化回上一題目

proof:

$$\begin{array}{rlr}{n}_1& \equiv a\times n_0+b& (modp)\\ n_2& \equiv a\times n_1+b& (modp)\\ n_2-n_1& \equiv a\times (n_1-n_0)& (modp)& \leftarrow 2\mathrm{式}-1\mathrm{式}\\ a& \equiv (n_2-n_1)\times (n_1-n_0{)}^{-1}& (modp)\end{array}$$

破解 LCG 3: 不知加數、乘數及模數 (a, b, p)

假設已知

$n_0$、

$n_1$ …

$n_k$ (

$k\ge 4$)，不知

$a$、

$b$、

$p$

令

$$\begin{array}{rlr}{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{array}$$
公式:

$p=GCD(g_1,g_2,...g_{k-2})$
退化回上一題目

proof:

$$\begin{array}{rlrlr}{d}_0\equiv n_1-n_0& & & & (modp)\\ 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& (modp)\\ 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& (modp)\\ 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& (modp)\\ ...\end{array}$$

$$\begin{array}{rlrlr}{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& (modp)\\ 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& (modp)\\ ...\end{array}$$

$g_1=u_1\times p$

$g_2=u_2\times p$
…

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

線性 DES/AES

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

檢測線性

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

[source]

$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)

利用線性特性

參考這篇文章，可知線性 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=\left[\begin{array}{c}0\\ 0\\ ⋮\\ 0\end{array}\right]$

$p_1=\left[\begin{array}{c}1\\ 0\\ ⋮\\ 0\end{array}\right]$

$p_2=\left[\begin{array}{c}0\\ 1\\ 0\\ ⋮\\ 0\end{array}\right]$

$p_n=\dots$

$p_{128}=\left[\begin{array}{c}0\\ ⋮\\ 0\\ 1\end{array}\right]$

$c_0=A\times p_0+k$

$c_1=A\times p_1+k$

$...$

$c_{128}=A\times p_{128}+k$

$\begin{array}{rl}C& =\left[\begin{array}{c}{c}_1-c_0,c_2-c_0,\dots ,c_{128}-c_0\end{array}\right]\\ & =\left[\begin{array}{c}(A\times p_1+k)-(A\times p_0+k),\dots ,(A\times p_{128}+k)-(A\times p_0+k)\end{array}\right]\\ & =\left[\begin{array}{c}A\times (p_1-p_0),\dots ,A\times (p_{128}-p_0)\end{array}\right]\\ & =A\times \left[\begin{array}{c}(p_1-p_0),\dots ,(p_{128}-p_0)\end{array}\right]\\ & =A\times \left[\begin{array}{c}{p}_1,\dots ,p_{128}\end{array}\right]\\ & =A\times P\end{array}$

求 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_{\overline{k}}(\overline{P})=\overline{C}$

Data Encryption Standard - Wikipedia

Weak key

在某些 key 的情況下，

$E_{k_1}(E_{k_2}(P))=P$

Weak key - Wikipedia
Recommendation for the Triple Data Encryption Algorithm (TDEA) Block Cipher

$\mathrm{\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

$\mathrm{\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\mathrm{mod}{n}^2$

相當於是

$m^e\mathrm{mod}n$，此處

$e$ 為自然指數

decyption

$n=p\times q$

$\varphi =(p-1)\times (q-1)$

$\mu ={\varphi }^{-1}\mathrm{mod}n$

$msg=\lfloor \frac{c^{\varphi }\mathrm{mod}{n}^2-1}{n}\rfloor \times \mu \mathrm{mod}n$

相當於是

$log(c)\mathrm{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