# RSA
## Giới thiệu
RSA là một hệ thống mã hóa khóa công khai, được đặt tên theo 3 nhà khoa học: Rivest, Shamir, và Adleman. Nó dựa trên độ khó của việc phân tích một số nguyên lớn thành các thừa số nguyên tố (bài toán phân tích thừa số). RSA được sử dụng rộng rãi trong:
- Mã hóa dữ liệu.
- Chữ ký số.
- Giao thức bảo mật như SSL/TLS.
## Nguyên lý hoạt động của RSA
### Tạo khóa
Các bước thực hiện.
- Chọn 2 số nguyên tố lớn phân biệt $p$ và $q$.
- Tính $n = p × q$ và tính hàm Euler $φ(n) = (p-1) × (q-1)$.
- Chọn số mũ công khai *e* sao cho $1 < e < φ(n)$ và $gcd(e, φ(n)) = 1$.
- Tính số mũ bí mật $d = e^{-1} \mod φ(n)$.

Khóa công khai: $(e, n)$.
Khóa bí mật: $(d, n)$.
### Mã hóa
Giả sử bạn muốn mã hóa thông điệp *M* (trong đó *M* là một số nguyên thỏa mãn *0 ≤ M < n*).
Công thức mã hóa: **C = M^e^ mod n** - trong đó: *C* là bản mã.
### Giải mã
Để giải mã bản mã *C*, sử dụng khóa bí mật *d*.
Công thức giải mã: **M = C^d^ mod n**

## Các kiểu tấn công RSA

### Factorizing the public key (small n)

Trong RSA, để tối ưu thời gian mã hóa *e* thường được chọn dưới dạng *2^n^ + 1*, nếu *e* được chọn ngẫu nhiên thì cần nhiều phép nhân hơn, làm tăng độ trễ. Trong thực tế, RSA thường dùng *e = 3 (=2^1^ + 1)* hoặc *e = 65537 (=2^16^ + 1)*. Khi *e = 65537* thì chỉ cần 17 phép tính để mã hóa ra ciphertext. Trong kkhi *e = 3* sẽ giúp tăng tốc độ mã hóa và giảm chi phí tính toán cho các thiết bị hạn chế tài nguyên như thẻ thanh toán, IoT,... nhưng cũng có rủi ro dễ bị tấn công.

Nếu *e* quá nhỏ, chẳng hạn *e = 3*, và *M* nhỏ (*M < n^1/3^*) thì lúc này phép toán modulo *C = M^3^ mod n* không có tác dụng và có thể dễ dàng giải mã bằng cách tìm căn bậc 3 của *C*.

Vì vậy, để tránh khỏi cuộc tấn công này chúng ta có thể padding thêm dữ liệu vào thông điệp *M* trược khi mã hóa.

### Commom modulus (same n)

#### As an externel attacker

Trong trường hợp này, giả sử kẻ tấn công nghe lén được 2 ciphertext dùng chung modulo *n* (bởi vì họ không muốn tạo modulo khác nhau cho mỗi người để giảm chi phí tính toán và quản lý khóa) và 2 số mũ *e~1~*, *e~2~* nguyên tố cùng nhau. NếuNếu xác định được 2 thông điệp *M* được gửi giống nhau thì kẻ tấn công có thể dễ dàng khôi phục được thông điệp *M*. $$C_1 = M^{e_1} \mod n$$ $$C_2 = M^{e_2} \mod n$$

Vì *gcd(e~1~, e~2~) = 1* nên chúng ta dùng thuật toán Euclid mở rộng để tìm *a, b* sao cho *a×e~1~ + b×e~2~ = 1*. Lúc này, chúng ta thực hiện phép tính sau: $$C_1^{a}×C_2^{b} = (M^{e_1})^a×(M^{e_2})^b = M^{a×e_1+b×e_2} = M^1 \mod n$$

Như vậy chúng ta đã có thể khôi phục được thông điệp *M*.

#### As an internal ender

Trong trường hợp này, giả sử bạn là một phần của một hệ thống và sở hữu một khóa công khai *e* và một khóa bí mật *d* nhưng chung modulo *n* với người khác. Từ (n, e, d) của mình, bạn có thể dễ dàng tính được φ(n) theo các sau:

- Vì *ed ≡ 1 mod φ(n)* nên *ed - 1 = kφ(n)* với một số nguyên *k*.
- Từ đó, *k = (ed-1)/φ(n) > (ed-1)/n*.
- Do *n* là một số lớn vì vậy *φ(n)* xấp xĩ bằng *n* nên bạn có thể brute-force số nguyên *k* từ *(ed-1)/n* và sau đó tính *φ(n) = (ed-1)/k* cho đến khi tìm được *φ(n)* là số nguyên chính xác.
- Khi đã có được *φ(n)*, bạn có thể factorizing *n* hoặc tính khóa bí mật của người khác một cách dễ dàng.

### Fermat's attack (p and q are too close)

Trong thực tế, *p* và *q* được chọn có cùng độ dài bit để tạo nên 1 RSA mạnh, nhưng nếu 2 số này quá gần cũng có thể dễ dàng factorizing *n*.

Điều kiện để tấn công này thành công là *p* - *q* < 22n^1/4^.

Ý tưởng của cách tấn công này là: $$n = pq = \left(\frac{p+q}{2}\right)^2 - \left(\frac{p-q}{2}\right)^2 = x^2 - y^2$$

Suy ra *n = (x-y)(x+y)* từ đó *p = x - y* và *q = x + y*. Vì vậy, chúng ta chỉ cần dùng giải thuật Fermat để tìm *x* và *y* là có thể factorizing *n*:

1. Tìm số gần với $\sqrt{n}$ $$x = \lceil\sqrt{n}\rceil$$
2. Tính *y^2^ = x^2^ - N*.
3. Kiểm tra *y^2^* có phải số chính phương không:
- Nếu có, thì *p = x - y* và *q = x + y*.
- Nếu không, tăng *x* lên 1 và quay lại bước 2.

### Hastad's Broadcast Attack (same e, small e)

Hastad's Broadcast Attack là một tấn công dựa trên lý thuyết số khi một massage *M* được mã hóa nhiều lần bằng cùng một số mũ công khai *e*, nhưng với nhiều modulo khác nhau (*N1, N2, N3, ...*). Nếu số lượng modulo *N~i~* đủ lớn, ta có thể giải mã trực tiếp mà không cần khóa bí mật.

Giả sử RSA mã hóa: $$C_i = M^e \mod N_i$$

Nhiệm vụ của ta là giải hệ phương trình đồng dư: $$M^e ≡ C_1 \mod n_1$$ $$M^e ≡ C_2 \mod n_2$$ $$\vdots$$ $$M^e ≡ C_e \mod n_ee$$

Bằng cách sử dụng Chinese Remainder Theorem (CRT), ta có thế tính được $$M^e = X \mod N_1N_2...N_e$$

Vì *M^e^ < N~1~N~2~...N~e~* nên ta có giá trị chính xác *M^e^* mà không bị modulo. Bây giờ ta cần tìm *M* bằng cách tính căn bậc *e* của $X$.

### Wiener Attack (small d)

Wiener Attack là một phương pháp tấn công vào hệ mã hóa RSA khi khóa bí mật $d$ được chọn quá nhỏ. Phương pháp này dựa trên việc sử dụng liên phân số để xấp xỉ tỉ số $\frac{e}{n}$và tìm ra khóa bí mật *d*.

**Điều kiện:**
- d < 1/3 n^(1/4)^
- q < p < 2q
- e' < n^(3/2)^ với e' = e mod φ(n) (e không quá lớn)

Nếu thỏa mãn các điều kiện trên (thông qua việc đề cho e rất lớn), ta có thể dễ dàng tìm được *d*.

**Chứng minh:**

Ta có: *ed - kφ(n) = 1*, do đó:

Vì vậy *e/φ(n) ≈ k/d*. Ta có, hàm phi Euler *φ(n) = (p-1)(q-1) = pq-p-q+1*. Vì *p* và *q* nhỏ hơn nhiều so với *n*, nên ta có thể lấy gần đúng *φ(n) ≈ n* ta được:

Bây giờ, *kφ(n) = ed 1 < ed*. Vì e < φ(N) cộng với điều kiện => k < d < 1/3 n^(1/4) ta được:

**Thực hiện:**
Sử dụng phân số liên tục:
- Ta phân tích e/n thành một phân số liên tục và tính các phân số hội tụ (convergents).
- Mỗi phân số hội tụ p~i~/q~i~ là một ứng viên cho k/d.
- Nếu d=q~i~ thỏa mãn điều kiện RSA, ta tìm được khóa bí mật *d*.

## Blinding attack

Blinding Attack (tấn công mù hóa) là một phương pháp tấn công vào hệ thống mã hóa RSA, đặc biệt là khi hệ thống sử dụng chữ ký số RSA mà không áp dụng các biện pháp bảo vệ thích hợp. Tấn công này cho phép kẻ tấn công lấy được chữ ký của một thông điệp mà không cần biết nội dung thực sự của thông điệp đó.

Trong RSA, chữ ký số của một thông điệp *m* được tính bằng cách: $$s = m^d \mod n$$ Kẻ tấn công muốn lấy chữ ký s của một thông điệp m, nhưng không thể trực tiếp yêu cầu hệ thống ký m. Thay vào đó, kẻ tấn công chọn một số ngẫu nhiên r (gọi là blinding factor) GCD(r,n)=1 và tính m' = m*r^e^ mod n để đánh lừa hệ thống ký m' và nhận được s'= (m')^d^ mod n. Sau đó, từ chữ ký s' kẻ tấn công khôi phục chữ ký s = s'⋅r^-1^ mod n.