Đã đăng vào thg 7 25, 2:00 SA 4 phút đọc

[Cryptography p5] Hệ mật RSA

Bài viết được lấy từ https://truongphuoc.wordpress.com/2023/03/14/blockchain-18-he-mat-rsa/

Hi, xin chào các bạn.

Trong bài trước mình đã trình bày về các kiến thức toán học cần thiết cho RSA và Elliptic curve cryptography. Trong bài viết này mình sẽ trình bày về thuật toán mã hóa RSA nhé.

RSA

Thuật toán RSA được Rivest, Shamir và Adleman mô tả lần đầu tiên năm 1977 tại trường đại học MIT. Thuật toán được mô tả như sau:

Chọn 2 số nguyên tố khá lớn ( >1024 bit) P và Q, P ≠ Q.
Ta lấy $N = P*Q$ , N được gọi là modulo mã hóa.
Ta đặt $K = (P-1)*(Q-1)$
Chọn số E sao cho: $1 < E < P*Q$ , E và K nguyên tố cùng nhau. E được gọi là số mũ mã hóa.
Tính số D sao cho: $D*E ≡ 1 (mod K)$ . D được gọi là số mũ giải mã.
Public key là cặp số $(N, E), Private key$ là cặp số $(N, D)$ .

Công thức mã hóa và giải mã với T là Plain text, C là Cypher text như sau:

Công thức mã hóa: $C = {T}^{E}$ mod N

Công thức giải mã: $T = {C}^{D}$ mod N

Trên đây là mô tả thuật toán rồi, cũng không khó lắm phải không ạ, các khái niệm toán học mình đã giải thích ở bài trước rồi, nếu có gì không hiểu các bạn xem lại nhé. Bây giờ chúng ta cùng đến một ví dụ để có thể hình dung rõ hơn về thuật toán này.

Ví dụ cụ thể

Trong thực tế người ta chọn P và Q là hai số nguyên tố rất lớn, nhưng ở đây mình chỉ để ví dụ minh hóa nên sẽ chọn P và Q nhỏ để dễ tính toán nhé.

1. Chọn P = 61, Q = 53.
2. N = P*Q = 61*53 = 3233.
3. K = (P-1)*(Q-1) = (61-1)*(53-1) = 3120.
4. Chọn E = 17.    // 1 < 17 < 3233, 17 và 3120 nguyên tố cùng nhau vì gcd(17, 3120) = 1.
5. D*17 ≡ 1 (mod 3120)
=> Ta thử D sao cho D*17 mod 3120 = 1
Với điều kiện như thế ta có D = [..., 2753, 5873, 8983,...]
Ta chọn D = 2753
Vậy Public Key  = (N,E) = (3233, 17)
    Private Key = (N,D) = (3233, 2753).
Ví dụ với Plain text là T = 123
Encryption: C = T^E mod N = 123^17 mod 3233 = 855
Decryption: T = C^D mod N = 855^2753 mod 3233 = 123

Ưu điểm của RSA:

Có độ bảo mật cao.
Dễ hiểu, dễ triển khai: thuật toán RSA dựa trên các phép tính số học cơ bản như phép nhân và phân tích số nguyên, do đó dễ hiểu và triển khai hơn so với một số thuật toán mật mã khác.

Nhược điểm của RSA:

Tốc độ Encryption và Decryption chậm.
RSA yêu cầu các khóa rất lớn để đạt được mức độ bảo mật cao.

Bài tập về nhà: Các bạn hãy tự làm một ví dụ cụ thể ra giấy nha, đây là một thuật toán mã hóa bất đối xứng rất phổ biến và đơn giản, nếu đã làm được một ví dụ thì bạn sẽ vỡ ra nhiều điều thay vì chỉ đọc vu vơ thôi đó.

Trao đổi Public key

Ta thấy rằng khi Bình dùng khóa công khai nhận từ An để gửi tin nhắn với thuật toán RSA. Khi nhận được Cypher text từ Bình thì An và chỉ An đọc được. Nhưng An không biết tin nhắn đó được gửi từ ai, từ Bình hay một người khác là Công. Vì thế ta phải trao đổi khóa công khai an toàn, quy trình như sau:

An tạo một cặp khóa (Key pair) rồi gửi Public key cho Bình.
Bình sử dụng Public key của An để mã hóa Public key của mình, sau đó gửi cho An.
An nhận được Cypher Public key của Bình, giải mã để được Public key.
An sử dụng Public key đó để mã hóa.

Thế là chỉ An biết được Public key của Bình, Công không biết nên không thể mạo danh An gửi tin cho Bình được.

Kết luận

Như thế là mình đã trình bày xong thuật toán RSA, cũng khá dễ hiểu phải không nào. Nếu bạn đã đọc qua bài về toán học rồi, thì bắt kịp rồi đúng không, nếu không các bạn quay lại bài trước nghe 😁. Nếu có bạn nào thắc mắc về gửi text thì sao, tại vì RSA chỉ làm việc với các con số. Ví dụ với Plain text là "Hello world", ta sẽ chuyển sang số (có thể sử dụng bảng mã ASCII để chuyển) thành: 72 101 108 108 111 32 119 111 114 108 100, rồi sau đó tính toán với con số đó nhé. Trong bài viết tiếp theo mình sẽ trình bày về một thuật toán tiên tiến hơn: Elliptic curve cryptography.

Link bài viết gốc https://truongphuoc.wordpress.com/2023/03/14/blockchain-18-he-mat-rsa/