# RSA và các kiểu tấn công thường gặp

# 1. Giới thiệu
RSA là thuật toán mã hóa công khai, thuật toán được Ron Rivest, Adi Shamir và Len Adleman mô tả lần đầu tiên vào năm 1977. RSA là mã công khai được biết đến nhiều nhất và sử dụng rộng rãi nhất hiện nay.

RSA dựa vào độ khó của bài toán phân tích một số ra thừa số nguyên tố. Trong RSA có khóa công khai và khóa bí mật. Khóa công khai được chia sẻ tự do trong khi khóa bí mật phải được giữ kín.

## Tạo khóa:
- Chọn ra 2 số nguyên tố lớn p và q với p ≠ q, lựa chọn ngẫu nhiên và độc lập.
- Tính n = p * q
- Tính giá trị hàm số Euler $\Phi(n)$ = (p - 1) * (q - 1)
- Chọn 1 số tự nhiên e sao cho 1 < e < φ(n) và GCD(e, φ(n)) = 1
- Tính $d = e^{-1} (mod φ(n))$, số d thỏa mãn ed ≡ 1 (mod φ(n))

Khóa công khai gồm:
- n: module.
- e: số mũ mã hóa.

Khóa bí mật gồm:
- n: module.
- d: số mũ giải mã.

## Mã hóa.
Giả sử Bob gửi đoạn mã thông tin M cho Alice, Bob chuyển M thành 1 số m < n theo 1 hàm có thể đảo ngược (từ m có thể xác định lại M) được thỏa thuận trước.

Lúc này Bob có m và biết n và e do Alice gửi. Từ đó Bob có thể mã hóa được m theo công thức:
- $c=m^{e}\mod {n}$

## Giải mã.

Để giải mã, Alice dùng khóa bí mật để tính ngược lại
- $m = c^{d}\mod {n}$

# Các kiểu tấn công thường gặp của RSA
## 1. Factoring Large Integers
Đây là 1 kiểu tấn công thường gặp của RSA. Để có thể giải mã được RSA thì việc đầu tiên ta cần để ý là có thể tách n ra thành p, q hay không?
Nếu n nhỏ (n < 256 bit), ta có thể dễ dàng tách n bằng cách *brute-force* số p
Nếu n lớn thì chúng ta có thể sử dụng các công cụ online như: http://factordb.com/, https://www.alpertron.com.ar/ECM.HTM .

## 2. Common modulus (giống n)
### 2.1 External Attack
Để tránh việc tạo ra các N khác nhau cho mỗi người dùng khác nhau thay vào đó ta sẽ sử dụng chung 1 N cho tất cả người dùng và các cặp khóa công khai là (n, ei), khóa bí mật (n, di).
Giả sử ta biết được các giá trị khóa công khai (n, e) và biết được các giá trị mã hóa (C1, C2). Từ đó ta có thể giải mã để thu được bản rõ ban đầu bằng cách:
- Do gcd(e1, e2) = 1 nên từ đó ta có thể áp dụng Extended Euclidean algorithm để tìm được a, b:
- a * e1 + b * e2 = 1

- Vì $c^{d}\equiv (m^{e})^{d}\equiv m^{ed}{\pmod {n}}$ nên ta có thể tính được m:
- $m^{e1 * a} * m^{e2 * b} = m^{e1 * a + e2 *b} = m$

### 2.2 Internal Attack.
Giả sử ta có cặp (n, e) và (n, d) từ đó ta cũng có thể tìm được φ(n) theo cách:
- Vì e*d = 1 (mod φ(n)) nên ta sẽ có:
- e * d = k * φ(n) + 1
- Rút k về 1 vế ta sẽ được:
- k = (e*d - 1)/ φ(n)
- Vì n và φ(n) rất lớn nên ta có thể coi k = (e*d - 1)/n
- Ta có thể brute-force k và tính ngược lại φ(n) cho đến khi φ(n) là số nguyên.
- φ(n) = (e*d - 1)/k

## 3. Low Private Exponent (d bé) - Wiener Attack
Điều kiện cần:
- p < q < 2p
- d < $1\over 3 * n^{1/4}$
- e' < n3/2 với e' = e (mod n)hay Public Key không quá lớn

Chứng minh:
- Vì e*d = 1 (mod φ(n)) nên ta sẽ có:

- Từ trên ta có thể thấy được k/d ≈ e/φ(n) mà φ(n) ≈ n nên ta có thể thay φ(n) = N. Từ đó ta thu được:

- k*φ(n) = e*d - 1 < e*d. Bởi vì e < φ(n), ta thấy k < d < $ 1\over 3*n^{1/4}$. Từ đó ta thu được:

- Từ đó ta áp dụng định lý về dãy hội tụ liên phân số, ta tìm được trong dãy hội tụ liên phân số e/n sẽ tìm được k/d. Thử từng cặp k/d, ta tính được φ(n) = (e*d -1)/k
- Mặt khác p+q = n-φ(n)+1 và p*q = n. Ta áp dụng định lý Vi-et để tìm ra p và q.

## 4. Hasted`s Broadcast Attack
Giả sử ta có nhiều n cặp khóa công khai (Ni, e) và n bản mã Ci. Để có thể giải mã, ta sử dụng định lý Phần dư Trung Hoa để giải mã.

**Điều kiện:** các cặp gcd(Ni, Nj) = 1

Giả sử với e = 3, thi ta có thể giải như sau:

$c1=m^{3}(modN1)$
$c2=m^{3}(modN2)$
$c3=m^{3}(modN3)$

Ta đổi chỗ $m^{3}$ và Ci rồi đặt $m^{3}$ = x thì ra sẽ thu được phương trình:

$x = c1(modN1)$
$x = c2(modN2)$
$x = c3(modN3)$

Áp dụng định lý Phần dư Trung Hoa để giải tìm x sau đó khai căn e sẽ thu được bản rõ.

## 5. Fermat`s factorizing algorithm
Trong thực tế, ta cần chọn p, q có cùng độ dài bit để tạo được 1 mã RSA mạnh, tuy nhiên nếu p, q quá gần nhau thì sẽ tạo ra lỗ hổng để có thể tấn công.

**Điều kiện cần:**
- p - q < $N^{1/4}$

Thuật toán Fermat:
$$
N = p*q = {(p - q)\over 2}^{2} - {(p + q)\over 2}^{2} = x^{2} - y^{2}
$$

Ta sử dụng giải thuật Fermat để tìm ra p, q:

# Bài tập: 20 bài đầu của RSA Cryptohack
https://hackmd.io/snNsFsPLT6OlY4ehkbpStg