# BLOG#1: RSA
> BÀI TOÁN VỀ TRAO ĐỔI VÀ BẢO MẬT THÔNG TIN:
> Alice và Bob có nhu cầu trao đổi thông tin với nhau. Thông tin của họ cần được mã hóa để đảm bảo tính bảo mật của công việc. Có rất nhiều người có nhu cầu tương tự, vì thế mà nhiều loại mã hóa, trong đó có mã hóa RSA ra đời.
> Alice và Bob quyết định sử dụng mã hóa RSA, sau khi đã tìm hiểu về loại mã hóa này.

**I. Sơ lược về hệ thống mã hóa RSA:**
1. **Trước tiên, RSA là gì?**
Hệ thống mã hóa RSA (RSA cryptosystem) là hệ thống mã hóa được đặt theo tên ba nhà nghiên cứu: **Rivest – Shamir – Adleman.** Là một hệ thống mật mã được ra đời từ năm 1977, hiện đang vẫn là một hệ mã được sử dụng phổ biến hiện nay, ứng dụng cho việc truyền dữ liệu an toàn qua email hoặc internet. Đây cũng là nền tảng cho nhiều giao thức an toàn thông tin, được ứng dụng trong chữ kí số *Digital Signature*.
2. **RSA hoạt động như thế nào?**
Mình có xem một video youtube khá dễ hiểu, nếu chưa thực sự hiểu rõ thì có thể xem qua video này nha: [RSA Introduction by Pham Van Thanh](https://youtu.be/k71-1A7s8KM?si=hefWgB6hxM6L4nlI)
Nếu tóm tắt lại để thật cô đọng và súc tích, thì hệ mã hóa RSA được cấu thành từ hệ các mã khóa gồm 2 loại: **Khóa Công khai (Public Keys)** và Khóa **Bí mật (Private Keys)**. Hai khóa này cùng cơ chế mã hóa, giải mã đều dùng nền tảng là các phép toán đồng dư (Modular Arithmetics). Cụ thể như sau (*mặc dù đây vẫn chỉ là phiên bản đơn giản, tuy nhiên vẫn sẽ là nền móng của những hệ thống mã hóa lớn, phức tạp hơn*):
* Cho nguyên **N** được cấu thành bởi tích hai số nguyên tố **N = p.q**.
* Lấy hai số **e**, **d** thỏa mãn điều kiện là **e.d = 1 mod (phi N)** *(hay có thể nói e và d là hai nghịch đảo modulo của nhau)*. Trong đó, **phi N** là *phi hàm Euler* của số **N**, và **phi N = (p - 1)(q - 1)**.
* Ta gọi **N** là *số modulo* (hay modulus), **e** là *encryption exponent* (lũy thừa mã hóa) và **d** là *decryption exponent* (lũy thừa giải mã). Cặp **(N,e)** sẽ chính là **Khóa công khai**, được sử dụng cho việc mã hóa thông tin và được công khai; và cặp **(N,d)** sẽ chính là **Khóa bảo mật**,chỉ có duy nhất những người cần biết, được biết nhằm có thể giải mã thông tin được mã hóa.
* Thông tin cần được mã hóa thường sẽ là một số nguyên dương M. Để mã hóa M bằng hệ mã RSA, ta sẽ sử dụng cặp khóa công khai (N, e), thực hiện phép tính **C = M^e mod N**. Để có thể giải mã, khi nhận được cipher, ta sẽ tính toán **C^d mod N**. Cần hiểu rằng **C^d = M^ed = M (mod N)** (theo Euler). Khóa **d** chính là mấu chốt để tạo nên **"cơ chế cửa sập"** của hệ mã khóa RSA.
> Giải thích kĩ hơn về **cơ chế cửa sập**: Cần có khóa bí mật để có thể giải mã. Dù khóa bảo mật là 1 số, tuy nhiên rất khó để có thể "mò" ra được số **d** hay khóa bảo mật bởi việc sử dụng phép toán đồng dư (hay phép toán modulo).

*Có hai kiểu mã hóa chính: mã hóa đối xứng và mã hóa bất đối xứng. Mã hóa RSA thuộc kiểu mã hóa bất đối xứng, cơ chế hoạt động được miêu tả như hình (Source: NordVPN Website)*

> Đặt lại vào bài toán lớn ban đầu, quy trình trao đổi thông tin giữa Alice và Bob sẽ như sau: Alice công khai cho Bob khóa công khai của Alice. Bob sẽ sử dụng khóa công khai đó để mã hóa thông tin mà Bob gửi đi. Khi nhận được mảnh tin mã hóa, Alice sẽ sử dụng khóa bí mật của mình để giải mã, nhận lại thông tin ban đầu.

**II. Phân tích các điểm mạnh và yếu của RSA.**
> Mọi loại hệ thống bảo mật đểu có những điểm mạnh và yếu khác nhau. Nghiên cứu chuyên sâu về điểm mạnh yếu của các loại khóa bảo mật để có thể tìm ra cách tấn công từng loại hệ thống, hoặc đề xuất cách phòng thủ đối với từng hệ thống chuyên biệt và ứng dụng các loại khóa vào nhiều loại hệ thống, thiết bị khác nhau. Blog này sẽ chủ yếu phân tích về điểm yếu của RSA để phục vụ mục đích tìm hiểu các cách tấn công hệ thống mã hóa này.

Sơ qua về điểm mạnh, có thể nói đây là một trong những hệ thống mã hóa thông dụng, cơ bản và dễ hiểu nhất. Cùng với đó chính là khả năng an toàn của mã khóa khi có thể tăng độ bảo mật bằng cách tăng độ dài, độ phức tạp của các khóa bảo mật, khóa công khai có thể chia sẻ rộng rãi. Tuy nhiên, sau gần 50 năm, đã qua quá nhiều cuộc phân tích, mổ xẻ và nghiên cứu, nhiều điểm yếu của mã hóa RSA đã được phát hiện, cùng với đó là nhiều cách tấn công đã được thực hiện.
Điểm yếu thay vì phân tích ở đây, mình sẽ đi sâu vào việc tìm hiểu các cách tấn công để có thể có thêm những giải thích cặn kẽ và ví dụ trực quan.

**III. Các phương thức tấn công với RSA:**
*Phần này sẽ khá là hấp dẫn.*
1. **Phân tích số:**
Mấu chốt của việc tấn công của RSA chính là đi tìm ra khóa bí mật (N,d). Khi đã biết khóa công khai (nó thực sự công khai), một phương án được đề ra là liệu có thể phân tích **N** thành 2 số nguyên tố **p** và **q** hay không, để từ đó tìm ra **phi N**, kết hợp với số **e** từ khóa công khai để tìm lại **d** bằng **e.d = 1 mod (phi N)**.
Với các giá trị **N** có độ dài nhỏ, phương án brute-force có thể được lựa chọn. Cùng với đó, khi các thuật toán phân tích số phức tạp đang ngày càng được phát triển, thì một cách để có thể tăng tính an toàn của hệ thống mã hóa RSA chính là tăng độ dài của các khóa, từ đó tăng độ khó cho việc phân tích, thậm chí vượt quá khả năng tính toán.
Nhận xét: Đây là một cách khả dĩ, có thể cân nhắc áp dụng. Tuy nhiên trong 1 số trường hợp khi mà không thể phân tích số, cần chọn phương án khác.
> Một số công cụ dùng tốt trong việc phân tích số có thể nhắc đến là factordb.com hoặc SageMath. Ưu tiên sử dụng factordb.com trong các trường hợp phân tích số hơn, bởi lẽ qua một số trải nghiệm thì công cụ này tạo output nhanh và tốt hơn so với sagemath trong các số lớn.

2. **Một vài phương pháp tấn công "cổ điển" khác:**
Có một số phương pháp khá "cổ điển" bởi lẽ nó được sử dụng trong những ngày đầu khi mà RSA còn mới mẻ và nhiều lỗ hổng. Qua thời gian, khi mà đã có nhiều nghiên cứu chuyên sâu và có cả những khuyến cáo trong việc sử dụng hệ thống mã hóa này sao cho hiệu quả, các phương án đơn giản này mới trở nên không còn quá nhiều tác dụng. Chúng ta sẽ đề cập 2 phương án tiêu biểu, cũng như 2 điểm yếu có thể bị khai thác dễ dàng của RSA.

**2.1. Chung số modulo**:
Có một số người cực lười để nghĩ ra hay sử dụng các số **N** khác nhau. Họ luôn muốn cố định 1 số N cho tất cả.
Nếu đặt lại trong bài toán lớn về việc mã hóa thông tin giữa Alice và Bob của RSA, thì nếu một người có thể sử dụng khóa công khai của họ, tìm ra khóa công khai và khóa bảo mật của Alice, từ đó đánh cắp được thông tin trao đổi giữa 2 người. Vì thế mà thật không nên reuse những khóa bảo mật RSA.

**2.2. Blindings (Tung hỏa mù):**
Nghe bí ẩn oách xà lách, tóm gọn lại thì như sau:
Một người thư ký muốn Bob ký trên một đoạn mã M để có thể gửi đi với chữ ký điện tử của Bob, và vì nó không valid nên Bob không làm. Người thư ký này dùng cách chọn bất kì một số r và đặt **M' = r^e M mod N**. Và đưa đoạn mã M' cho Bob ký. Bob sẽ hồn nhiên đặt lên đó chữ ký số S' mà không mảy may nghi ngờ. Sau đó người thư kí kia sẽ dùng những gì nhận được để giải mã và tìm ra S', lấy được chữ kí số của Bob.

3. **Những khóa bảo mật kém an toàn với d quá nhỏ (Wiener Attack):**
Nhằm giảm thời gian xử lí công việc giải mã, một số người thường sử dụng giá trị khóa bí mật d nhỏ hoặc đơn giản. Từ đây chính là mấu chốt để tạo nên một phương thức tấn công, là tấn công M.Wiener (hay gọi tắt là Wiener Attack).
Theo định luật (cũng là điều kiện để có thể thực hiện loại hình tấn công này) do M.Wiener đề ra thì:
> Tức đối với các giá trị của d ở mức nhỏ, khi có được khóa công khai (N,e) thì nghiễm nhiên các attacker hoàn toàn có thể có được khóa bảo mật d. Ngoài ra, khi giá trị e lớn so với N thì đây cũng có thể coi là một dấu hiệu cho khả năng sử dụng Weiner Attack.

Thường đối với các khóa bảo mật có độ dài N là 1024 bits, hệ quả là để có thể tránh được các tấn công này thì các trị số d trong khóa bí mật cần phải đạt độ dài tối thiểu tương ứng là 256 bits. Tuy nhiên, đối với một số thiết bị hoặc trường hợp có nguồn cấp điện nhỏ hoặc khả năng xử lí của hệ thống có hạn thì việc sử dụng một khóa bảo mật có giá trị nhỏ có ý nghĩa trong việc nhanh chóng giải mã và ít có khả năng bị tấn công bởi loại tấn công này (Dan Boneh)

4. **Khi e quá nhỏ**:
Khi bên trên ta đã nói về trường hợp khóa **d** mang giá trị quá nhỏ. Tương tự thế, khi giá trị **e** quá nhỏ cũng mang lại một số hệ lụy. Mục đích của việc để giá trị **e** nhỏ cũng nhằm tăng tốc quá trình mã hóa thông tin.
Phương thức tấn công trong trường hợp này mạnh nhất sẽ là phương thức dựa trên định luật được đề ra bởi CopperSmith.
Cụ thể hơn, khi giá trị e quá nhỏ so với N (và M cũng đủ nhỏ), attacker trong trường hợp nếu chặn được đoạn mã C thì có thể tìm được bản rõ M

4.1. **Coppper Smith Theorem**

4.2. **Hastad's Broadcast Attack** (*Ứng dụng của định lí Số dư Trung Hoa - CRT và Copper Smith Theorem*)

Đây là một hình thức tấn công dựa trên **Copper Smith Theorem** vừa được nêu đến ở trên. Giả sử, đặt vào trường hợp Bob muốn mã hóa một bản rõ M đến một số tổ chức P1, P2,... Pk. Mỗi tổ chức có cho mình một khóa riêng (**N**(i), **e**(i)). Và như bình thường, Bob mã hóa gói tin theo các khóa công khai được các tổ chức cung cấp. Attacker chặn được đường truyền của Bob và thu thập thành công một số gói tin sau khi mã hóa.
Cho rằng các khóa bảo mật đều có e = 3, số gói tin thu thập được là k = 3.
Ta sẽ có:

**(C1 ≡ M3 (mod N1) | C2 ≡ M3 (mod N2) | C3 ≡ M3 (mod N3)**

Với C1, C2, C3 lần lượt là bản rõ của bản mã M giải từ khóa bảo mật có modulo N1, N2, N3 và e = 3. Giả như mọi modulo N đều nguyên tố cùng nhau, hoặc không, attacker có thể dễ dàng phân tích được số N. Và, áp dụng CRT vào đây, tạo ra được số C' thỏa mãn **C' ≡ M^3 mod (N1.N2.N3)**. Từ đó với **C' = M^3** thì attacker chỉ đơn giản là tính căn bậc 3 của C' để có thể lấy được bản rõ M. Phương thức tấn công này sẽ hiệu quả đối với các giá trị e nhỏ.

4.3 **Franklin-Reiter Related Message Attack**
Đây là một phương thức tấn công mình đánh giá khá hay và thực tiễn hơn đối với việc đánh cắp thông tin từ hệ thống mã hóa RSA, được phát minh bởi Franklin và Reiter. Cách tấn công này cụ thể như sau:
Khi Bob và Alice trao đổi các gói tin với nhau, sử dụng chung một bộ khóa công khai (N,e). Giả sử M1, M2 là 2 bản rõ; M1 và M2 có liên hệ với nhau bằng phương trình `M2 = f(M1) mod N`, và M1, M2 đều được mã hóa bằng khóa (N,e).
Các bước tấn công như sau:
- **Xác lập MQH đa thức giữa các bản mã**: Ta có thể xây dựng được MQH giữa các bản mã: C2 = f(M1)^e mod N
Giải thích chi tiết: với MQH ban đầu `M2 = f(M1)`, cùng với đó là khi mã hóa M2 với khóa (N,e) thì C2 có dạng C2 = (M2)^e mod N; tiếp đó thay thế M2 = f(M1) để có được MQH trên.
- **Xây dựng các đa thức**: Từ MQH trên ta có thể xác lập được 2 đa thức với nghiệm lần lượt là M1 và M2:
`g1(x) = x^e - C1` và `g2(x) = f(x)^e - C2` (lí do: C = M^e mod N)
- **Tìm nghiệm chung**: Tìm nghiệm chung của g1 và g2, sử dụng thuật toán Euclid để tìm được GCD, từ đó tìm được M2.
5. **Khi p và q có giá trị gần nhau**:
Đây chính là điều kiện để thực hiện **Fermat Attack**. Điều kiện là khi p và q có kích thước tương đương.
*Ý tưởng của phương pháp dựa trên việc bất kì số lẻ nào cũng có thể được biểu diễn dưới dạng hiệu hai bình phương.*

Các bước tiến hành thì sẽ như sau:
- Tìm a = sqrt(N)
- Tính b^2 = a*a - N
- Check b có phải là số chính phương hay không. Nếu có, thì xác lập giá trị của b. Nếu không, tăng tham số a lên 1 đơn vị, lặp lại quá trình cho đến khi tìm được giá trị b^2 chính phương.
- Sau khi tìm được hai giá trị a và b, tính giá trị p và q với `p = a - sqrt(b^2)` và `q = n//p`.

*Cred: Blog này được viết nên, tham khảo dựa trên tài liệu: Twenty Years of Attacks on the RSA Cryptosystem của tác giả Dan Boneh cùng một số trang thông tin khác.*