- vừa được xem lúc

[Cryptography p5] Hệ mật RSA

0 0 2

Người đăng: Hoàng Trường Phước

Theo Viblo Asia

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:

  1. Chọn 2 số nguyên tố khá lớn ( >1024 bit) P và Q, P ≠ Q.
  2. Ta lấy N=PQN = P*Q, N được gọi là modulo mã hóa.
  3. Ta đặt K=(P1)(Q1)K = (P-1)*(Q-1)
  4. Chọn số E sao cho: 1<E<PQ1 < E < P*Q, E và K nguyên tố cùng nhau. E được gọi là số mũ mã hóa.
  5. Tính số D sao cho: DE1(modK)D*E ≡ 1 (mod K). D được gọi là số mũ giải mã.
  6. Public key là cặp số (N,E),Privatekey(N, E), Private key là cặp số (N,D)(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=TEC = {T}^{E} mod N

Công thức giải mã: T=CDT = {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.

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

  • Tốc độ Encryption và Decryption chậm.

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:

  1. An tạo một cặp khóa (Key pair) rồi gửi Public key cho Bình.
  2. Bình sử dụng Public key của An để mã hóa Public key của mình, sau đó gửi cho An.
  3. An nhận được Cypher Public key của Bình, giải mã để được Public key.
  4. 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/

Bình luận

Bài viết tương tự

- vừa được xem lúc

Mật mã học: Phần 1 - Mã hóa Caesar

Khái niệm mã hóa dữ liệu và giải mã. Mã hóa dữ liệu là tiến trình che dấu dữ liệu thật (plaintext), nghĩa là chuyển dữ liệu thật thành dữ liệu không có ý nghĩa hoặc có ý nghĩa khác xa với dữ liệu thật

0 0 50

- vừa được xem lúc

Thực hành mã hóa và giải mã thuật toán Simplified AES

Tương tự bài viết trước về thuật toán Simplified DES, mình sẽ không thảo luận về lý thuyết của tiêu chuẩn mã hóa dữ liệu Advanced Encryption Standard - AES, hay cụ thể là Simplified AES. Thay vào đó,

0 0 168

- vừa được xem lúc

Hệ mã hóa RSA và chữ ký số

Bài viết gốc: https://manhhomienbienthuy.bitbucket.io/2017/Feb/20/rsa-cryptosystem-and-digital-signature.html (đã xin phép tác giả ).

0 0 62

- vừa được xem lúc

Thực hành mã hóa và giải mã thuật toán Simplified DES

Ở bài viết này, mình sẽ không thảo luận về lý thuyết của tiêu chuẩn mã hóa dữ liệu (Data Encryption Standard - DES), hay cụ thể là Simplified DES. Thay vào đó, mình sẽ thực hành mã hóa bằng tay từng b

0 0 154

- vừa được xem lúc

Thuật toán mã hoá khối và một số trường hợp tấn công trong CTF (Phần 1)

Mã hoá luôn là một trong những biện pháp hiệu quả nhất trong việc đảm bảo tính bí mật của thông tin. Các thuật toán mã hoá được ứng dụng rộng rãi, tồn tại trong nhiều sản phẩm công nghệ.

0 0 20

- vừa được xem lúc

Mã hoá thay thế liệu đã hết thời?

Từ xưa rất xưa ấy, theo sự phát triển của văn hoá và tri thức thì tư duy của con người cũng ngày càng phức tạp hơn. Nhưng trong một xã hội nơi có rất nhiều người, rất nhiều nhóm người chung sống cùng

0 0 18