Thuật toán RSA môn Thuật toán ứng dụng | Đại học Bách Khoa Hà Nội

THUẬT TOÁN RSA

1. Định nghĩa

RSA là một hệ mã hóa bất đối xứng (asymmetric cryptography) sử dụng hai khóa khác nhau để mã hóa và giải mã. Public key (khóa công khai) được chia sẻ với bất kỳ ai và dùng để mã hóa thông tin, trong khi private key (khóa bí mật) được giữ kín và chỉ người sở hữu nó mới có thể giải mã thông tin.

Bằng cách sử dụng public key, bất kỳ ai cũng có thể gửi thông tin một cách an toàn, nhưng chỉ người giữ private key mới có thể đọc được thông điệp. Điều này mang lại mức độ bảo mật cao vì dù thông tin có bị chặn, chỉ người có private key mới có thể giải mã.

Dù trên lý thuyết RSA có độ bảo mật rất cao, trong thực tế không có phương pháp nào đảm bảo an toàn tuyệt đối. Với sự phát triển của công nghệ như AI, máy tính lượng tử và siêu máy tính,… các hệ thống mã hóa hiện tại có thể trở nên dễ bị phá vỡ hơn. Hiện tại, các thuật toán khóa như RSA vẫn bảo vệ được thông tin trước các kỹ thuật tấn công thông thường, đặc biệt khi sử dụng máy tính cá nhân, nhưng trong tương lai có thể bị đe dọa bởi các công nghệ tiên tiến hơn.

2. Tìm hiểu chữ ký số

Chữ ký số là một dạng đặc biệt của chữ ký điện tử, được sử dụng để xác thực danh tính người gửi cũng như đảm bảo tính toàn vẹn của dữ liệu. Khác với chữ ký tay truyền thống, chữ ký số tồn tại dưới dạng dữ liệu mã hóa và được tạo ra nhờ các thuật toán mật mã học.

Cơ chế hoạt động của chữ ký số dựa trên hệ mã hóa bất đối xứng, thường sử dụng cặp khóa công khai và khóa riêng. Khóa riêng được dùng để tạo chữ ký, trong khi khóa công khai được dùng để kiểm tra tính hợp lệ. Nhờ đó, chữ ký số không chỉ xác thực nguồn gốc thông tin mà còn giúp phát hiện mọi thay đổi trái phép trên dữ liệu.

3. Cơ chế hoạt động của RSA

Được mô tả lần đầu bởi Ron Rivest, Adi Shamir và Len Adleman vào 1977 tại Học viện Công nghệ Massachusetts (MIT). Hoạt động của RSA dựa trên 4 bước chính: sinh khóa, chia sẻ key, mã hóa và giải mã.

Quá trình sinh khóa

Việc tạo khóa trong RSA dựa trên việc tìm ra bộ ba số tự nhiên: e, d, và n, với yêu cầu rằng khi mã hóa và giải mã thông điệp m, công thức sau được thỏa mãn:

m^e mod n = m^d mod n

Một điểm quan trọng là private key d phải được bảo mật tuyệt đối. Ngay cả khi ai đó biết được e, n, hay thông điệp m, họ cũng không thể tính được d. Cụ thể, quá trình sinh khóa trong RSA gồm các bước như sau:

1. Chọn hai số nguyên tố lớn p và q: Đây là hai số bí mật mà chỉ người tạo khóa mới biết.
2. Tính giá trị n = p * q: Giá trị này sẽ được dùng làm modulus cho cả public key và private key.
3. Tính phi hàm Carmichael λ(n): Đây là một số giả nguyên tố được tính bằng cách lấy bội chung nhỏ nhất (BCNN) của λ(p) và λ(q), với λ(p) = p – 1 và λ(q) = q – 1. Giá trị λ(n) sẽ được giữ bí mật.
4. Chọn số tự nhiên e: Chọn một số e trong khoảng (1, λ(n)) sao cho ƯCLN(e, λ(n)) = 1, nghĩa là e và λ(n) nguyên tố cùng nhau. Số e sẽ được dùng để mã hóa thông điệp.
5. Tính số d: Tìm số d sao cho d * e ≡ 1 mod λ(n), hay nói cách khác, d là nghịch đảo modulo của e theo λ(n). Số d này sẽ được dùng để giải mã thông điệp.
6. Public key: Là bộ số (n, e), và có thể chia sẻ công khai.
7. Private key: Là bộ số (n, d), cần được giữ bí mật.

Ví dụ:

Bước 1: Sinh khóa

1. Chọn p = 3 và q = 11.
2. Tính n = 3 x 11 = 33.
3. Tính = (3-1) x (11-1) = 2 x 10 = 20.
4. Chọn e = 7 (vì 7 và 20 nguyên tố cùng nhau).
   • Khóa công khai: {7, 33}.
5. Tìm d sao cho (d x 7) 1 (mod 20).
   • Ta thấy 3 x 7 = 21. Mà 21 chia 20 dư 1. Vậy d = 3.
   • Khóa bí mật: {3, 33}.

Bước 2: Mã hóa

Giả sử bạn muốn gửi thông điệp là số M = 2.

• Áp dụng công thức: C = M^e mod n = 2^7 mod 33.
• Tính toán: 2^7 = 128.
• Thực hiện phép chia: 128 / 33 = 3 dư 29.
• Vậy bản mã gửi đi là C = 29.

Bước 3: Giải mã

Người nhận nhận được C = 29 và dùng khóa bí mật d = 3 để giải mã.

• Áp dụng công thức: M = C^d mod n = 29^3 mod 33.
• Tính toán: 29^3 = 24,389.
• Thực hiện phép chia: 24,389 / 33 = 739 dư 2.
• Vậy thông điệp gốc thu được là M = 2 (khớp với ban đầu).

Để đảm bảo an toàn, cần bảo mật các số nguyên tố p và q, vì nếu chúng bị lộ, quá trình sinh khóa có thể bị phá vỡ.

4. Cơ chế hoạt động chữ ký số

Chữ ký số dựa trên hệ mã hóa RSA hoạt động tương tự như quá trình mã hóa và giải mã thông tin. Tuy nhiên, vai trò của public key và private key trong chữ ký số có sự thay đổi:

• Tạo chữ ký: Người gửi sử dụng private key của mình để tạo ra chữ ký số.
• Xác thực chữ ký: Người nhận dùng public key của người gửi để xác thực tính hợp lệ của chữ ký.

Cách tạo và xác thực chữ ký số

Vì việc mã hóa toàn bộ bản tin có thể tốn thời gian và không hiệu quả, thay vì mã hóa cả bản tin, chỉ giá trị hash của bản tin được mã hóa. Phương pháp này có nhiều ưu điểm:

• Tính một chiều của hàm hash: Hàm hash là một hàm một chiều, do đó, ngay cả khi biết giá trị hash, cũng không thể khôi phục lại bản tin gốc.
• Độ dài cố định: Giá trị hash có độ dài cố định và nhỏ, giúp giảm dung lượng của chữ ký số.
• Kiểm tra tính toàn vẹn: Hash còn giúp kiểm tra xem bản tin có bị thay đổi trong quá trình truyền tải hay không. Nếu giá trị hash của bản tin không trùng khớp, nghĩa là dữ liệu đã bị thay đổi.

1. Quy trình Tạo chữ ký số (Phía người gửi)

Giả sử người gửi là An muốn gửi một thông điệp M cho Bình.

• Bước 1: Băm thông điệp (Hashing): An không ký trực tiếp lên toàn bộ văn bản dài (vì RSA xử lý số lớn rất chậm). Thay vào đó, An đưa thông điệp M qua một hàm băm (như SHA-256) để tạo ra một chuỗi cố định gọi là giá trị băm H.

H = h(M)

• Bước 2: Ký số (Signing): An dùng Khóa bí mật (Private Key) của mình là d để mã hóa giá trị băm H này, tạo ra chữ ký số S.

S = H^d mod n

• Bước 3: Gửi đi: An gửi cho Bình bộ đôi bao gồm: Thông điệp gốc M, Chữ ký số S.

2. Quy trình Xác thực chữ ký số (Phía người nhận)

Khi Bình nhận được bộ đôi M, S, Bình thực hiện các bước sau:

• Bước 1: Tính lại giá trị băm: Bình dùng đúng hàm băm h mà An đã dùng để tính giá trị băm H1 từ thông điệp gốc M nhận được.

H1 = h(M)

• Bước 2: Giải mã chữ ký (Decryption/Verification): Bình dùng Khóa công khai (Public Key) của An là e để giải mã chữ ký S. Kết quả thu được là H2.

H2 = S^e mod n

• Bước 3: So sánh:
  • Nếu H1 = H2: Chữ ký hợp lệ. Bình tin rằng thông điệp đúng là từ An gửi và nội dung chưa bị ai sửa đổi.
  • Nếu H1 H2: Chữ ký giả mạo hoặc thông điệp đã bị thay đổi trên đường đi.

Ví dụ toán học cụ thể

Khởi tạo hệ thống (Tạo khóa):

1. Chọn 2 số nguyên tố: p = 3, q = 11.
2. Tính n = p x q = 3 x 11 = 3.
3. Tính = (p-1)(q-1) = 2 x 10 = 20.
4. Chọn số e sao cho nguyên tố cùng nhau với 20: Chọn e = 3.
5. Tìm số d sao cho (d x 3) 1 mod 20: Chọn d = 7 (vì 7 x 3 = 21, chia 20 dư 1).
   • Khóa công khai của An: {e=3, n=33}
   • Khóa bí mật của An: {d=7, n=33}

Quá trình Ký số:

• Giả sử thông điệp sau khi băm của An có giá trị là H = 2.
• An tạo chữ ký: S = H^d mod n = 2^7 mod 33.
• Tính toán: 2^7 = 128. Mà 128 chia33 dư 29 (33 x 3 = 99; 128 - 99 = 29).
• Vậy chữ ký số S = 29.

Quá trình Xác thực:

• Bình nhận được thông điệp và chữ ký S = 29.
• Bình thực hiện giải mã chữ ký bằng khóa công khai của An: H2 = S^e mod n = 29^3 mod 33.
• Tính toán: 29^3 = 24389.
• Thực hiện phép chia: 24389 / 33 = 739 dư 2.
• Vậy H2 = 2
• Vì Bình cũng tự băm thông điệp gốc ra H1 = 2, và thấy H1 = H2, nên Bình xác nhận chữ ký này là ĐÚNG.

5. Lợi ích mà chữ ký số mang lại

• Xác định nguồn gốc: Với hệ mã hóa bất đối xứng, chỉ chủ sở hữu private key mới có thể tạo ra chữ ký số hợp lệ. Người nhận dùng public key để giải mã chữ ký và tính lại giá trị hash của bản tin. Nếu giá trị hash khớp với hash trong chữ ký số, chữ ký là hợp lệ và bản tin không bị thay đổi.
• Giữ nguyên tính toàn vẹn của dữ liệu: Chữ ký số đảm bảo rằng tin nhắn không thể bị chỉnh sửa. Nếu một kẻ tấn công thay đổi nội dung, giá trị hash sẽ khác, khiến việc xác thực chữ ký không thành công. Ngay cả khi kẻ tấn công biết giá trị hash và nội dung tin nhắn, hắn không thể thay đổi chữ ký số nếu không có private key.
• Không thể phủ nhận: Chữ ký số trong các giao dịch giúp xác định rõ nguồn gốc. Vì chỉ chủ sở hữu private key mới có thể tạo ra chữ ký, họ không thể phủ nhận rằng mình đã ký bản tin đó. Điều này giúp tăng tính pháp lý và trách nhiệm trong các giao dịch trực tuyến.

6. Một số hàm cần chú ý

• Hàm trapdoor
• Mã hóa RSA hoạt động dựa trên tiền đề rằng thuật toán dễ dàng tính toán theo một hướng. Nhưng hầu như không thể thực hiện ngược lại. Ví dụ nếu cho biết rằng 701,111 là tích của hai số nguyên tố, vậy có thể tìm ra hai số đó là bao nhiêu không?
• Ngay cả với máy tính hay PC thì hầu hết chúng ta cũng sẽ không biết bắt đầu từ đâu chứ đừng nói đến việc tìm ra câu trả lời. Nhưng nếu lật lại mọi thứ thì nó sẽ dễ dàng hơn rất nhiều. Kết quả của:
• 907 x 773
• Nếu dùng máy tính để tính phép toán này thì sẽ phát hiện câu trả lời là 701,111 và nó đã được đề cập trước đó. 907 và 773 này là hai số nguyên tố cần trả lời. Điều này cho chúng ta thấy rằng một số phương trình có thể dễ dàng giải ra một cách dễ dàng, nhưng ngược lại dường như không thể.
• RSA sử dụng số lượng lớn hơn nhiều. Kích thước của các số nguyên tố trong quá trình vận hành RSA là như nhau. Nhưng trong RSA 2048-bit, chúng sẽ kết hợp với nhau để tạo ra các key dài 617 chữ số. Để hình dung nó, một key sẽ là một số có kích thước như sau:

99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999

Tạo số nguyên tố

Các chức năng của hàm trapdoor đã được đề cập ở trên tạo cơ sở cho cách thức hoạt động của các lược đồ mã hóa public key và private key. Các thuộc tính của chúng cho phép chia sẻ public key mà không gây nguy hiểm cho tin nhắn hoặc tiết lộ private key. Chúng cũng cho phép dữ liệu được mã hóa bằng một key theo cách mà chỉ có thể giải mã bằng key khác.

Các số nguyên tố trong RSA cần phải rất lớn và cũng tương đối xa nhau. Các số nhỏ hoặc gần nhau sẽ dễ bị bẻ khóa hơn nhiều. Mặc dù vậy, ví dụ của chúng tôi sẽ sử dụng các số nhỏ hơn để làm cho mọi thứ dễ theo dõi và tính toán hơn.

Giả sử kiểm tra tính nguyên tố cho các số nguyên tố mà chúng ta đã sử dụng ở trên, 907 và 773. Bước tiếp theo là khám phá module (n), sử dụng công thức sau:

n = p x q

Với p = 907 and q = 773

Nên:

• n = 907 x 773
• n = 701,111

Hàm phi Carmichael

• Một khi đã có n, chúng ta sẽ sử dụng hàm phi Carmichael:

λ(n) = lcm (p − 1, q − 1)

λ(n) là ký hiệu của hàm phi Carmichael, còn lcm là lowest common multiple (bội số chung nhỏ nhất) – nghĩa là số thấp nhất mà cả p và q có thể chia được. Có một số cách khác nhau để tìm ra điều này, nhưng cách dễ nhất là tin tưởng một máy tính online để làm phương trình cho bạn. Vì vậy, hãy đặt các con số của chúng ta vào phương trình:

• λ(701,111) = lcm (907 − 1, 773 − 1)
• λ(701,111) = lcm (906, 772)
• Sử dụng máy tính chúng ta sẽ được:
• λ(701,111) = 349,716