# Phần 1: Lỗ hỗng RSA
## A. Lý thuyết RSA
### I. Định nghĩa
RSA là hệ mã hóa bất đối xứng sử dụng cặp khóa bao gồm public key dùng để mã hóa và private key dùng để giải mã. Đảm bảo quá trình trao đổi khóa an toàn và không cần gặp trực tiếp để trao đổi khóa.
### II. Thuật toán
#### 1. Tạo khóa
**Bước 1.** chọn ngẫu nhiên 2 số nguyên tố p và q, $p \neq q\ và\ tính\ n=p.q$.
**Bước 2.** Tính hàm Euler $\varphi(n) = (p-1).(q-1)$
**Bước 3.** Chọn số mũ công khai e sao cho $0 < e < \varphi(n), gcd(e, \varphi(n))= 1$.
**Bước 4.** Tính số mũ bí mật d với d là nghịch đảo modulo $e.d \equiv 1 \bmod \varphi(n)$.
* Sau khi hoàn thành các bước trên ta có cặp khóa gồm Pu(e,n) và Pr(d,n).
#### 2. Mã hóa và giải mã
* **Mã hóa:** sử dụng Pu để mã hóa. plaintext M sẽ được chuyển đổi thành số nguyên m, sau đó tính $c = m^{e} \bmod n$ với c là ciphertext và gửi đi.
* **Giải mã:** sử dụng Pr để giải mã. Số $m = c^d \bmod n$ sau đó chuyển m thành M là có được plaintext.
**Lưu ý:** số mũ d và thừa số nguyên tố p và q đều phải giữ bí mật tuyệt đối, việc để lộ 1 trong 2 là nguy hiểm như nhau. Vì từ d có thể dễ dàng tìm được plaintext. Tương tự, từ p và q có thể tính $\varphi(n)$ từ đó có thể tìm ra d và lộ plaintext.
#### 3. Chữ kí số (DSA)
Chữ ký số là chữ ký điện tử sử dụng thuật toán khóa không đối xứng, gồm khóa bí mật và khóa công khai, trong đó khóa bí mật được dùng để ký số và khóa công khai được dùng để kiểm tra chữ ký số.
* Tạo chữ kí:
Người kí áp dụng các hàm bâm mật mã lên thông điệp (M) cần kí (SHA-256, SHA-3,..) $h = H(M)$
Sau đó dùng private key để mã hóa thông điệp băm đó: $s = h^d \bmod n$ trong đó s chính là signature và gửi đi.
* Xác thực chữ kí:
Người nhận dùng sẽ sử dụng public key để giải mã chữ kí số: $h' = s^e \bmod n$.
Sau đó so sánh $h$ ban đầu vỡi $h'$ đã giải mã, nếu giống nhau nghĩa là thông điệp chưa thay đổi. Ngược lại, nếu kết quả không trùng khớp nghĩa là thông điệp đã bị thay đổi.
## B. Các lỗ hỗng RSA.
[Tài liệu tham khảo](https://crypto.stanford.edu/~dabo/papers/RSA-survey.pdf)
### I. Factoring Large Integers
Mục đích chính là tìm ra được số mũ bí mật $d$ để từ $d$ ta có thể tìm ra được plaintext. Nhưng muốn tìm được $d$ ta cần phải biết được $(e,\varphi(n))$, e đã được công khai, việc còn lại là tìm $\varphi(n)$, muốn tìm được $\varphi(n)$ ta cần phải biết thừa số nguyên tố của n là p và q. Như vậy ta cần phân tích được $n = p.q$.
* Ta sẽ nghĩa đến việc brute-force, nhưng nó có phải là tốt nhất ?
```python=
from sympy import isprime
from math import sqrt
def Is_factor(x, N):
if N % x == 0 and isprime(x):
return True
else:
return False
def Brute_force_N(N):
output = set()
for i in range(2, int(sqrt(N)) + 1):
if Is_factor(i, N):
output.add(i)
output.add(N//i)
return output
return "Cannot analyse"
N = ?
print(Brute_force_N(N))
```
Theo như những gì tham khảo từ ChatGPT, chỉ cần N là một số có độ dài 1024 bit thì thuật toán trên ước trừng mất khoảng $\approx2,12\times10^{137}$ năm để phân tích thừa số nguyên tố N nếu máy tính có thể thực hiện $10^9$ phép kiểm tra mỗi giây. Vì vậy, với một số N có độ dài khóa lớn, thì việc brute-force là không hiệu quả.
* Hiện nay thuật toán phân tích thừa số nguyên tố tốt nhất là General number field sieve (GNFS). Đây là thuật toán có độ phức tạp $exp((c+O(1))n^{1/3}\log^{2/3}n)$ với $c < 2$.
[GNFS wikipedia](https://en.wikipedia.org/wiki/General_number_field_sieve)
[Tài liệu GNFS](https://www.cs.umd.edu/~gasarch/TOPICS/factoring/NFSmadeeasy.pdf)
Mặc dù GNFS là thuật toán phân tích thừa số nguyến tố hiệu quả nhất hiện nay, nhưng theo một nguồn tin tham khảo "năm 2009, một nhóm nghiên cứu gồm nhiều nhà mật mã học đã phân tích RSA-768 (232 chữ số) bằng GNFS, tốn khoảng 2000 năm CPU." tức là nếu chỉ dùng 1 CPU chạy toàn bộ GNFS thì sẽ mất 2000 năm. Tức nhiên, nhóm nghiên cứu đã chạy song song hóa gồm nhiều CPU để giảm thời gian giải. Nhưng đối với máy tính cá nhân thì việc phá RSA là không thể.
### II. Elementary Attacks
#### 1. Command modulus
Trong một hệ thống mã hóa RSA, chuyện gì xảy ra nếu ta cố định số mudulus N ?.
* Giả sử: Một hệ thống RSA sử dụng chung một số mô-đun N và cấp phát các cặp khóa Pu và Pr khác nhau cho các user. Một mối nguy hiểm xảy ra khi một user nào đó có thể dùng chính cặp Pu, Pr của mình để tìm ra được Pr của một user khác và đọc trộm thông điệp.
Ví dụ: Alice được hệ thống cấp phát Pu(7,55) và Pr(23,55). Tương tự Bob cũng được hệ thống cấp phát Pu(3,55) và Pr(27,55). Bây giờ, Bob sẽ tìm Pr của Alice bằng chính Pu và Pr của mình.
> Như vậy, Sau khi phân tích được p và q thì Bob có thể tìm được private key của không chỉ Alice mà còn của các user khác dùng chung mô-đun N với Bob.
* Ngoài ra ta còn kiểu tấn công phục hồi plaintext khi cùng một N và cùng một plaintext m bị mã hóa bằng hai public key $e_1,e_2$ khác nhau, nhưng với điều kiện $gcd(e_1,e_2)=1$.
[Video hướng dẫn chi tiết của một anh Ấn Độ](https://youtu.be/uX2z4fZYYkQ?si=fiO_gLVrZaV1GVN9)
Như vậy: Việc sử dụng chung mô-đun N cho tất cả các user là không khả thi vì thiếu tính bảo mật.
#### 2. Blinding
Đây là kiểu tấn công liên quan đến chữ ký số (DSA). Giả sử, Marwin muốn sử dụng chữ ký của Bob để ký lên một tin nhắn nào đó ($M \in Z^{*}_n$). Marwin đưa M cho Bob ký ?, tức nhiên, Bob sẽ không ngốc nghếch mà ký vào tin nhắn đào lửa. Như vậy, Marwin sẽ sử dụng kỷ thuật Blinding để làm mù tin nhắn.
* Marwin chọn một số ngẫu nhiên $r\in Z^*_n$. Sau đó, Marwin sẽ làm mù tin nhắn $M' = r^eM \bmod N$ và đưa $M'$ cho Bob, nhìn từ phía Bob $M'$ chỉ là một số vô hại và không có ý nghĩa gì. Bob sẽ kí bằng khóa riêng $S' = (M')^d \bmod N$ rồi gửi về cho Marwin.
* Marwin khi có được $S'$ sẽ tính $S = S'r^{-1}\bmod N$ khi đó, S chính là chữ ký trên văn bản gốc M, và như vậy Bob đã ký vào tin nhắn đào lửa mà không hề hay biết.
* Thuật toán trên dựa vào tính chất dưới đây: $S^e = \frac{(S')^e}{r^e} = \frac{(M')^{ed}}{r^e} = \frac{M'}{r^e} = M \bmod N$
[Chi tiết và code ở đây](https://asecuritysite.com/encryption/c_c2)
### III. Low Private Exponent
Nhược điểm số mũ lớn của RSA làm cho tốc độ mã hóa và giải mã bị hạn chế. Nếu như dùng một số mũ d (Pr) nhỏ thay vì một số mũ d ngẫu nhiên và lớn để tăng tốc độ giải mã cũng như thời gian ký số. Điều đó có an toàn ?
* Theo định lý Wiener: Cho số $N=pq$ với $q<p<2p$. chọn $d<\frac{1}{3}N^\frac{1}{4}$ và {e,N} thỏa mãn $ed=1 \bmod \varphi(N)$, ta có thể lấy lại số mũ d từ e,N.
Chứng minh: ta có $ed \equiv 1 \bmod \varphi(N)$, vì vậy sẽ tồn tại một só $k \in Z$ sao cho $ed - k\varphi(N) = 1$
Chia 2 vế cho $d\varphi(N)$ ta được: $|\frac{e}{\varphi(N)}-\frac{k}{d}| = \frac{1}{d\varphi(N)}$ mà $\frac{k}{d} \approx \frac{e}{\varphi(N)}$
Thực vậy, bởi vì $\varphi(N) = N -p - q+1$ và $p+q-1<\sqrt{3}N$, ta có $|N - \varphi(N)| < 3\sqrt{N}$.
Sử dụng N thay cho $\varphi(N)$: $|\frac{e}{N} - \frac{k}{d}| = |\frac{ed - k\varphi(N) - kN + k\varphi(N)}{Nd}| = |\frac{1 - k(N-\varphi(N))}{Nd}|\le |\frac{3k\sqrt{N}}{Nd}| = \frac{3k}{d\sqrt{N}}$.
Bây giờ: $k\varphi(N) = ed - 1 < ed$, bởi vì $e < \varphi(N)$ ta thấy rằng: $k<d<\frac{1}{3}N^{\frac{1}{4}}$
$\implies |\frac{e}{N} - \frac{k}{d}| \le \frac{1}{2d^{2}}$
Đây là một quan hệ xấp xĩ kinh điển. số lượn các phân số $\frac{e}{d}$ với $d<N$ xấp xĩ $\frac{e}{N}$. Ta tính trong khoản $\log N$ phân số hội tụ của phân số liên tục $\frac{e}{N}$, một trong số đó sẽ bằng $\frac{k}{d}$ và $\frac{k}{d}$ là một phân số tối giản.
* Như vậy: Nếu ta vẫn muốn sử dụng d nhỏ để tối ưu ký số mã mã hóa đồng thời ngăn chặn được loại tấn công trên thì phải làm thế nào ? Nếu ta chọn một số mũ e lớn $e' = e + t\varphi(N)$ e' > e và có thể thay thế cho e, vì e tỷ lệ thuận với k, nên e tăng => k tăng, Nhưng nếu e tăng thì tốc độ mã hóa cũng sẽ tăng đáng kể. Vì vậy, cách trên có vẻ không khả thi.
* Nếu sử dụng CTR: chọn một số d thỏa mãn $d_p= d \bmod (p-1)$ và $d_q = d \bmod (q-1)$. Ta thấy, $d_p$ và $d_q$ nhỏ nhưng d vẫn đủ lớn. Ciphertext C sẽ được giải mã như sau: ta tính $M_p = C^{d_p} \bmod p$ và $M_q = C^{d_q} \bmod q$ sau đó sử dụng định lý phần dư trung hoa để giải hệ phương trình modulo và tìm ra M thỏa mã $M = M_p \bmod p$ và $M = M_q \bmod q$ và M chính là ciphertext.
### IV. Low Public Exponent
#### 1. Hastad's Broadcast Attack
#### 2. Franklin-Reiter Related Message Attack
* Giả sử rằng Bob gửi cho Alice những thông điệp được mã hóa sử dụng chung một số modulo và public key. Cho $M_1$ và $M_2$ và 2 thông điệp của Bob gửi và $M_1,M_2 \in Z_n^*$ và thông điệp $M_1 = f(M_2) \bmod N$ cho một đa thức công khai $f \in Z_n[x]$. Nghĩa là, từ thông điệp $M_1,M_2$ ta có thể phân tích thành $M_1 = ax + b$ với $b \neq 0$ và $M_2$ là nghiệm của đa thức đó. Bob khi gửi sẽ sử dụng public key để mã hóa thành $C_1$ và $C_2$. Khi đó, với $C_1,C_2,N,e,f$ Marwin có thể tìm ra $M_1,M_2$. Tuy nhiên, kiểu tấn công này hiệu quả khi số mũ $e$ nhỏ.
**Chứng minh:** Bởi vì $C_1 = M_1^e \bmod N$, và $M_2$ là nghiệm của đa thức $g_1 ( x) = f(x)^e \bmod N$. Tương tự, $M_2$ cũng là nghiệm của $g_2(x) = x^e \bmod N$.
* Chứng minh:
Bởi vì $M_2$ là nghiệm chung của 2 đa thức $g_1(x),g_2(x)$ nên $x - M_2$ là nhân tử chung của 2 đa thức. Hay nói cách khác $g_1(x),g_2(x)$ đều chia hết cho $x-M_2$. Như vậy, Marwin chỉ cần tìm được $\gcd(g_1(x),g_2(x))$ bằng thuật toán euclid là có thể tìm được $M_2$, từ $M_2$ Marwin có thể suy ra lại $M_1$ và biết được thông điệp. Tuy nhiên, $gcd(g_1(x),g_2(x)$ phải là một đa thức bậc nhất.
### V. Implementation Attacks
#### 1. Timing Attacks
Đây là kiểu tấn công dựa trên thuật toán **repeated squaring algorithm**.
Biểu điễn binary của $d = d_nd_{n-1}...d_0$
ta có: $d = \sum_{i=0}^{n}2^id_i$ với $d_i \in {0,1}$
Ta lại có: $C = M^d \bmod N = \prod_{i=0}^{n}M^{2^id_i} \bmod N$.
* Dưới đây là mã giả của thuật toán
```python=
Input: M (base), d (exponent, binary bits d0 is least significant), N (modulus)
Output: C = M^d mod N
z ← M
C ← 1
for i from 0 to n: # n = index of most-significant bit of d
if d[i] == 1:
C ← (C * z) mod N
z ← (z * z) mod N
return C
```
* Nhưng nếu như số mũ d là bí mật, vậy làm sao ta biết được dãy bits của d ?
Để tiến hành tấn công, Marvin yêu cầu smartcard sinh chữ ký cho một lượng lớn các thông điệp ngẫu nhiên $M1,...,M_k \in Z_n^{*}$ và đo thời gian $T_i$ mà thẻ cần để tạo từng chữ ký.
Vì d là một số lẻ, nên ta biết được bit đầu tiên $d_0 = 1$. Ta xem xét đến các bit tiếp theo. Ở vòng lập thứ 2 tương ứng với bit thứ 2, $Z = Z^2 \bmod N = M^2 \bmod N$ và $C = M$ nếu như $d_1 = 1$ ta sẽ tính $C = CZ \bmod N = MM^2 \bmod N$ ngược lại, $d_1 = 0$ thì sẽ không tính bước đó. Ta gọi $t_i$ là thời gian mất để tính $M_iM_i^2 \bmod N$ các $t_i$ khác như vì thời gian tính phụ thuộc vào giá trị của $M_i$. Marwin đo trước các $t_i$ này sau khi có các giá trị vật lý của thẻ như số modulus N. sau đó so sánh và đối chiếu để thu được các bit của d.
* Có hai cách để phòng chống tấn công này. Cách đơn giản nhất là thêm độ trễ thích hợp để phép mũ modular luôn tốn một lượng thời gian cố định. Cách thứ hai, do Rivest đề xuất, dựa trên blinding ở mục trên. chọn ngẫu nhiên số $r\in Z_n^*$ và tính $M' = Mr^e \bmod N$. sau đó áp dụng $d$ lên M' và thu được $C'=(M')^d \bmod N$ và $C = C'r^{-1} \bmod N$. Với cách này, thẻ đang áp dụng d lên một thông điệp ngẫu nhiên $M'$ mà Marvin không biết, nên Marvin không thể thực hiện tấn công.
#### 2. Random Faults
Cũng đúng như tên của nó, đây là một phát sinh ngẫu nhiên hiếm gặp khi sử dụng CRT khi ký thông điệp.
* Trong RSA, để tăng tốc quá trình giải mã hoặc ký số, người ta thường sử dụng Định lý phần dư Trung Hoa (CRT – Chinese Remainder Theorem).
* Thay vì tính trực tiếp $M^d \bmod N$, người kí sẽ tính $C_p = M^{d_p} \bmod p$ và $C_q = M^{d_q} \bmod q$. trong đó $d_p = d \bmod (p-1)$ và $d_q = d \bmod (q-1)$ sau đó tính $C = (T_1C_p + T_2C_q) \bmod N$ với $T_1 = {1 \bmod p\brace 0 \bmod q}$ và $T_2 = {0 \bmod p\brace 1 \bmod q}$
Tuy nhiên, Boneh, DeMillo và Lipton phát hiện rằng:
Nếu trong quá trình tính toán xảy ra lỗi (glitch) — ví dụ do nhiễu điện từ, lỗi phần cứng, hoặc bit bị lật — thì có thể dẫn đến việc chỉ một trong hai giá trị $C_p$ hoặc $C_q$ bị sai.
Giả sử: máy của Bob tính $C_p$ đúng và $C_q$ sai, suy ra chữ kí là $\tilde{C}= T_1C_p + T_2 \tilde{C_q}$. Khi Marwin nhận được $\tilde{C}$ anh ta sẽ biết được chữ kí bị lỗi vì $\tilde{C}^e \ne M \bmod N$. Tuy nhiên, $\tilde{C}^e = M \bmod p$ trong khi $\tilde{C}^e \ne M \bmod q$. Như vậy, chỉ cần tính $\gcd( M, \tilde{C}^e - M)$ thì sẽ biết được một ước của N và tính ươc còn lại là rất đơn giản.
Sign in with Wallet
Connect another wallet