Mã hóa RSA

Trong lĩnh vực mật mã, RSA là một phương pháp mã hóa sử dụng khóa công khai. Đây là thuật toán đầu tiên cho phép tạo chữ ký số đồng thời với mã hóa thông tin. Sự phát triển này đã mở ra một bước tiến lớn trong mật mã học bằng cách áp dụng công nghệ khóa công khai. RSA hiện đang được sử dụng rộng rãi trong thương mại điện tử và được coi là an toàn nếu sử dụng khóa có độ dài đủ lớn.

Lịch sử

Thuật toán RSA được giới thiệu lần đầu tiên vào năm 1977 bởi ba nhà nghiên cứu Ron Rivest, Adi Shamir và Len Adleman tại Học viện Công nghệ Massachusetts (MIT). Tên của thuật toán được lấy từ ba chữ cái đầu của tên của ba tác giả.

Trước đó, vào năm 1973, Clifford Cocks, một nhà toán học người Anh làm việc tại GCHQ, đã phát triển một thuật toán tương tự. Tuy nhiên, do công nghệ tính toán lúc đó chưa đủ phát triển, thuật toán này chưa bao giờ được thử nghiệm thực tế và chỉ được công bố vào năm 1997 do tính chất bảo mật của nó.

Thuật toán RSA được Học viện Công nghệ Massachusetts (MIT) đăng ký bản quyền tại Hoa Kỳ vào năm 1983 (Số đăng ký 4.405.829). Bằng sáng chế này đã hết hạn vào ngày 21 tháng 9 năm 2000. Tuy nhiên, vì thuật toán đã được công khai trước khi có đăng ký bản quyền, sự bảo vệ pháp lý của bằng sáng chế này chủ yếu chỉ có hiệu lực tại Hoa Kỳ. Nếu công trình của Clifford Cocks được công bố trước đó, RSA có thể đã không được cấp bằng sáng chế.

Hoạt động

Mô tả ngắn gọn

Thuật toán RSA sử dụng hai loại khóa: khóa công khai và khóa bí mật. Khóa công khai, được công bố rộng rãi, dùng để mã hóa dữ liệu, trong khi khóa bí mật chỉ được người sở hữu biết, dùng để giải mã dữ liệu. Dữ liệu được mã hóa bằng khóa công khai chỉ có thể được giải mã bằng khóa bí mật tương ứng. Nói cách khác, ai cũng có thể mã hóa thông tin nhưng chỉ người sở hữu khóa bí mật mới có thể đọc được thông tin đó.

Hãy tưởng tượng một ví dụ để dễ hiểu: Bình muốn gửi một thông tin bí mật cho An mà chỉ An mới có thể đọc được. Để làm điều này, An gửi cho Bình một chiếc hộp đã được mở khóa, giữ lại chìa khóa. Bình bỏ thông tin vào hộp và khóa lại (hộp khóa kiểu này không thể mở lại sau khi đã khóa). Bình sau đó gửi hộp lại cho An. An sử dụng chìa khóa của mình để mở hộp và đọc thông tin. Trong ví dụ này, chiếc hộp mở tượng trưng cho khóa công khai, còn chìa khóa là khóa bí mật.

Quá trình tạo khóa

Giả sử An và Bình cần trao đổi thông tin bí mật qua một kênh không an toàn (như Internet). Để thực hiện việc này bằng thuật toán RSA, An cần tạo ra một cặp khóa bao gồm khóa công khai và khóa bí mật theo các bước sau đây:

1. Chọn hai số nguyên tố lớn $p$ và $q$ sao cho $p\ne <!--\; \ne \; -->q$ và chúng là các số nguyên tố độc lập.
2. Tính toán giá trị $n=pq$.
3. Tính giá trị của hàm số Euler $\mathrm{\varphi <!--\; \varphi \; -->}\left(n\right)=(p-<!--\; -\; -->1)(q-<!--\; -\; -->1)$.
4. Chọn một số nguyên $e$ sao cho và số này phải là nguyên tố cùng nhau với $\mathrm{\varphi <!--\; \varphi \; -->}\left(n\right)$.
5. Tính toán giá trị $d$ sao cho $de\equiv <!--\; \equiv \; -->1\left(\mathrm{mod}\mathrm{\varphi <!--\; \varphi \; -->}\right(n\left)\right)$. (Xem về đồng dư để hiểu rõ hơn)

Một số lưu ý:

• Các số nguyên tố thường được chọn thông qua phương pháp thử nghiệm xác suất.
• Các bước 4 và 5 có thể được thực hiện bằng thuật toán Euclid mở rộng (tham khảo số học môđun).
• Bước 5 có thể được viết theo cách khác: Tìm một số nguyên $x$ sao cho $d=\frac{x(p-<!--\; -\; -->1)(q-<!--\; -\; -->1)+1}{e}$ cũng là một số nguyên. Khi đó, dùng giá trị $d\mathrm{mod}(p-<!--\; -\; -->1)($
  q − 1 ) {\displaystyle d\mod {(p-1)(q-1)}\,} .
• Từ bước 3, PKCS#1 v2.1 sử dụng $\mathrm{\lambda <!--\; \lambda \; -->}=LCM(p-<!--\; -\; -->1,q-<!--\; -\; -->1)$ thay vì $\mathrm{\varphi <!--\; \varphi \; -->}=(p-<!--\; -\; -->1)(q-<!--\; -\; -->1)$).

Khóa công khai bao gồm những thành phần sau:

• n, môđun, và
• e, số mũ công khai (hay còn gọi là số mũ mã hóa).

Khóa bí mật bao gồm những thành phần sau:

• n, môđun, được sử dụng cả trong khóa công khai và khóa bí mật, và
• d, số mũ bí mật (hay còn gọi là số mũ giải mã).

Một dạng khác của khóa bí mật là:

• p và q, hai số nguyên tố được chọn ban đầu,
• d mod (p-1) và d mod (q-1) (còn gọi là dmp1 và dmq1),
• (1/q) mod p (còn gọi là iqmp)

Dạng này cho phép thực hiện giải mã và ký số nhanh hơn nhờ vào định lý số dư Trung Quốc (Chinese Remainder Theorem - CRT). Trong dạng này, tất cả các thành phần của khóa bí mật đều phải được giữ kín.

An gửi khóa công khai cho Bình và giữ kín khóa bí mật của mình. Ở đây, p và q đóng vai trò quan trọng. Chúng là các yếu tố của n và giúp tính toán d khi biết e. Nếu không sử dụng dạng khóa bí mật dạng CRT, thì p và q sẽ được xóa ngay sau khi khóa được tạo xong.

Mã hóa

Giả sử Bình muốn gửi thông tin M đến An. Trước tiên, Bình chuyển đổi M thành một số m < n qua một hàm có thể đảo ngược (từ m có thể phục hồi lại M) đã được thỏa thuận trước. Quá trình này được mô tả trong phần #Chuyển đổi văn bản rõ.

Khi đó, Bình đã có m và biết n cùng với e do An cung cấp. Bình sẽ tính toán c là bản mã hóa của m theo công thức sau:

$c=m^e\mathrm{mod}n$

Công thức trên có thể được tính dễ dàng bằng phương pháp hàm mũ (theo môđun) với thuật toán bình phương và nhân. Sau đó, Bình gửi c cho An.

Giải mã

Khi An nhận được c từ Bình và biết khóa bí mật d, An có thể tính toán m từ c theo công thức dưới đây:

$m=c^d\mathrm{mod}n$

Biết được m, An có thể khôi phục lại M theo phương pháp đã thống nhất trước đó. Việc giải mã thành công vì ta có:

$c^d\equiv <!--\; \equiv \; -->(m^e{)}^d\equiv <!--\; \equiv \; -->m^{ed}\left(\mathrm{mod}n\right)$.

Vì ed ≡ 1 (mod p-1) và ed ≡ 1 (mod q-1) (theo Định lý Fermat nhỏ), nên:

$m^{ed}\equiv <!--\; \equiv \; -->m\left(\mathrm{mod}p\right)$

và

$m^{ed}\equiv <!--\; \equiv \; -->m\left(\mathrm{mod}q\right)$

Vì p và q là hai số nguyên tố đồng dư, áp dụng định lý số dư Trung Quốc, ta có:

$m^{ed}\equiv <!--\; \equiv \; -->m\left(\mathrm{mod}pq\right)$.

hoặc:

$c^d\equiv <!--\; \equiv \; -->m\left(\mathrm{mod}n\right)$.

Ví dụ

Dưới đây là một ví dụ với các giá trị cụ thể. Chúng ta chọn các số nhỏ để dễ dàng tính toán, nhưng trong thực tế, các số sẽ có giá trị lớn hơn nhiều.

Xem xét:

Khóa công khai được biểu diễn bằng cặp (e, n) và khóa bí mật là d. Hàm mã hóa được xác định như sau:

Mã hóa(m) = m mod n = m mod 3233

với m là thông tin gốc. Hàm giải mã được xác định như sau:

Giải mã(c) = c mod n = c mod 3233

với c là thông tin đã được mã hóa.

Để mã hóa thông tin có giá trị 123, ta thực hiện phép toán sau:

Mã hóa(123) = 123 mod 3233 = 992

Để giải mã thông tin có giá trị 992, ta thực hiện phép toán sau:

Giải mã(992) = 992 mod 3233 = 123

Cả hai phép toán trên có thể được thực hiện nhanh chóng nhờ vào thuật toán bình phương và nhân.

Chuyển đổi văn bản rõ

Trước khi thực hiện mã hóa, cần chuyển đổi văn bản rõ (từ M sang m) để đảm bảo không có giá trị nào của M dẫn đến văn bản mã không an toàn. Nếu bỏ qua bước này, RSA có thể gặp những vấn đề sau:

• Nếu m bằng 0 hoặc 1, kết quả mã hóa sẽ là 0 hoặc 1 tương ứng.
• Khi sử dụng số mũ nhỏ (như e = 3) và giá trị m nhỏ, giá trị $m^e$ có thể cũng nhỏ hơn n. Trong trường hợp này, phép môđun không hiệu quả và m có thể bị khai thác bằng cách lấy căn bậc e của c (bỏ qua môđun).
• RSA là phương pháp mã hóa xác định (không có yếu tố ngẫu nhiên), nên kẻ tấn công có thể tấn công lựa chọn bản rõ bằng cách tạo bảng tra cứu giữa bản rõ và bản mã. Khi gặp một bản mã, kẻ tấn công dùng bảng tra để xác định bản rõ tương ứng.

Trong thực tế, hai vấn đề đầu tiên thường xuất hiện khi gửi các tin nhắn ASCII ngắn, với m là nhóm ký tự ASCII. Một tin nhắn chỉ có ký tự NUL sẽ có giá trị m = 0 và cho ra bản mã là 0 bất kể giá trị của e và N. Tương tự, ký tự ASCII SOH, có giá trị 1, luôn cho ra bản mã là 1. Với hệ thống dùng giá trị e nhỏ, tất cả ký tự ASCII có thể cho ra bản mã không an toàn vì giá trị lớn nhất của m chỉ là 255, nhỏ hơn giá trị n chấp nhận. Những bản mã này dễ bị giải mã.

Để khắc phục các vấn đề trên, RSA thực tế thường áp dụng phương pháp chuyển đổi ngẫu nhiên hóa m trước khi mã hóa. Quá trình này đảm bảo rằng m không nằm trong các giá trị không an toàn. Sau khi chuyển đổi, mỗi bản rõ khi mã hóa sẽ tạo ra một trong nhiều khả năng trong tập hợp bản mã, giảm tính khả thi của việc tấn công lựa chọn bản rõ (một bản rõ có thể tương ứng với nhiều bản mã tùy thuộc vào cách chuyển đổi).

Một số tiêu chuẩn, như PKCS, được thiết kế để thực hiện chuyển đổi bản rõ trước khi mã hóa bằng RSA. Các phương pháp này bổ sung thêm bít vào M. Các phương pháp chuyển đổi phải được thiết kế cẩn thận để tránh các tấn công phức tạp lợi dụng cấu trúc bản rõ. Phiên bản đầu tiên của PKCS sử dụng phương pháp đặc ứng (ad-hoc) mà sau này được phát hiện là không an toàn trước tấn công lựa chọn bản rõ thích ứng (adaptive chosen ciphertext attack). Các phương pháp chuyển đổi hiện đại áp dụng kỹ thuật như chuyển đổi mã hóa bất đối xứng tối ưu (Optimal Asymmetric Encryption Padding - OAEP) để chống lại các tấn công dạng này. Tiêu chuẩn PKCS còn bổ sung các tính năng khác để đảm bảo an toàn cho chữ ký RSA (Probabilistic Signature Scheme for RSA - RSA-PSS).

Tạo chữ ký số cho tài liệu

Thuật toán RSA cũng được sử dụng để tạo chữ ký số cho tài liệu. Giả sử An muốn gửi cho Bình một tài liệu đã ký của mình. Để làm điều này, An sẽ tính toán giá trị băm (hash) của tài liệu và sau đó tính giá trị mũ d mod n của giá trị băm đó (giống như trong quá trình giải mã). Kết quả là chữ ký điện tử của tài liệu. Khi Bình nhận được tài liệu và chữ ký, anh ấy sẽ tính giá trị mũ e mod n của chữ ký và so sánh với giá trị băm của tài liệu. Nếu hai giá trị này khớp, Bình sẽ biết rằng người ký đã biết khóa bí mật của An và tài liệu không bị thay đổi sau khi ký.

Cần lưu ý rằng các phương pháp chuyển đổi bản rõ (như RSA-PSS) rất quan trọng trong quá trình mã hóa và tạo chữ ký điện tử, và không nên sử dụng cùng một khóa chung cho cả hai mục đích này.

An toàn

Độ bảo mật của hệ thống RSA phụ thuộc vào hai vấn đề toán học chính: phân tích số nguyên lớn thành các yếu tố nguyên tố và bài toán RSA. Nếu cả hai bài toán này đều khó giải quyết (không có thuật toán hiệu quả), việc phá mã toàn bộ RSA sẽ là không khả thi. Các phương pháp chuyển đổi bản rõ an toàn cần được áp dụng để ngăn chặn việc phá mã một phần.

Vào năm 2005, khả năng phân tích số nguyên lớn nhất thành thừa số nguyên tố là 663 bít bằng phương pháp phân tán, trong khi khóa RSA thường có độ dài từ 1024 đến 2048 bít. Một số chuyên gia cho rằng khóa 1024 bít có thể sớm bị phá vỡ, mặc dù vẫn có nhiều ý kiến phản đối. Với khóa 4096 bít, khả năng bị phá vỡ trong tương lai gần là rất thấp. Do đó, RSA được coi là an toàn nếu n đủ lớn. Nếu n có độ dài 256 bít hoặc ngắn hơn, nó có thể bị phân tích trong vài giờ bằng máy tính cá nhân với phần mềm hiện có. Nếu n có độ dài 512 bít, nó đã có thể bị phân tích bởi vài trăm máy tính từ năm 1999. Một thiết bị lý thuyết gọi là TWIRL do Shamir và Tromer mô tả năm 2003 đã đặt ra nghi vấn về độ an toàn của khóa 1024 bít. Vì vậy, hiện nay khuyến cáo nên sử dụng khóa có độ dài tối thiểu 2048 bít.

Năm 1993, Peter Shor công bố thuật toán Shor, chứng minh rằng máy tính lượng tử (trên lý thuyết) có thể giải bài toán phân tích thừa số trong thời gian đa thức. Tuy nhiên, công nghệ máy tính lượng tử vẫn chưa đạt đến mức này trong nhiều năm tới.

Vào năm 2010, các nhà nghiên cứu tại Đại học Michigan đã phát hiện ra một lỗ hổng trong hệ thống mã hóa RSA. Họ cho biết có thể lấy khóa bí mật RSA 1024 bít chỉ trong vài ngày thay vì nhiều năm nếu sử dụng các phương pháp tấn công thông thường như brute force. Họ đã tạo ra một điện thế lớn để gây lỗi hệ thống, từ đó tìm ra khóa bí mật. Cuộc tấn công được thực hiện trên một FPGA và được trình bày tại hội nghị DATE 2010 ở Dresden, Đức vào tháng 3 năm 2010.

Các vấn đề thực tiễn

Quá trình tạo khóa

Để tìm hai số nguyên tố lớn p và q, người ta thường sử dụng phương pháp kiểm tra xác suất trên các số ngẫu nhiên có kích thước phù hợp, kết hợp với phép kiểm tra nguyên tố để loại bỏ các số không phải nguyên tố.

Các số nguyên tố p và q cần được chọn sao cho không quá gần nhau để tránh việc phân tích n bằng phương pháp phân tích Fermat. Nếu p-1 hoặc q-1 có các thừa số nguyên tố nhỏ, thì n cũng có thể bị phân tích dễ dàng. Do đó, cần phải kiểm tra kỹ lưỡng p và q để ngăn chặn khả năng này.

Ngoài ra, cần phải sử dụng các phương pháp tạo số ngẫu nhiên mà không thể bị kẻ tấn công khai thác để dự đoán thông tin. Các số cần được tạo ra một cách hoàn toàn ngẫu nhiên và không thể dự đoán. Một số có thể ngẫu nhiên nhưng nếu có thể dự đoán được một phần thì an ninh của thuật toán sẽ bị đe dọa. Ví dụ, bảng số ngẫu nhiên của Rand vào những năm 1950 dù rất ngẫu nhiên nhưng nếu kẻ tấn công có bảng này thì có thể phá mã dễ dàng. Nếu kẻ tấn công đoán được một nửa chữ số của p hay q, họ có thể tìm nửa còn lại theo nghiên cứu của Donald Coppersmith năm 1997.

Cần lưu ý rằng khóa bí mật d phải đủ lớn. Năm 1990, Wiener chỉ ra rằng nếu p nằm trong khoảng giữa q và 2q (điều này khá phổ biến) và d < n/3, thì có thể suy ra d từ n và e.

Trước đây, giá trị của e thường là 3, nhưng hiện nay các số mũ nhỏ không còn được sử dụng vì chúng có thể tạo ra các lỗ hổng bảo mật (như đã đề cập trong phần chuyển đổi văn bản rõ). Hiện tại, giá trị phổ biến của e là 65537, vì nó đủ lớn để đảm bảo an toàn mà không ảnh hưởng nhiều đến hiệu suất tính toán hàm mũ.

Tốc độ

RSA thực hiện chậm hơn nhiều so với DES và các thuật toán mã hóa đối xứng khác. Thực tế, Bình thường dùng một thuật toán mã hóa đối xứng để mã hóa dữ liệu cần gửi và chỉ dùng RSA để mã hóa khóa để giải mã (vì khóa thường ngắn hơn nhiều so với dữ liệu).

Phương pháp này cũng gây ra những vấn đề an ninh mới. Ví dụ, cần phải tạo khóa đối xứng thật sự ngẫu nhiên. Nếu không, kẻ tấn công (thường gọi là Hắc) có thể bỏ qua RSA và tập trung vào việc đoán khóa đối xứng.

Phân phối khóa

Giống như các thuật toán mã hóa khác, việc phân phối khóa công khai đóng vai trò quan trọng trong bảo mật của RSA. Phân phối khóa cần phải chống lại tấn công kiểu đứng giữa (man-in-the-middle attack). Nếu Hắc có thể gửi một khóa giả cho Bình và khiến Bình tin đó là khóa (công khai) của An, đồng thời Hắc có khả năng đọc thông tin trao đổi giữa Bình và An, thì Hắc có thể lấy tất cả văn bản mã hóa từ Bình, giải mã bằng khóa bí mật của mình, sau đó mã hóa lại bằng khóa công khai của An và gửi cho An. Kết quả là cả Bình và An đều không nhận ra sự can thiệp của Hắc. Các biện pháp chống lại loại tấn công này thường sử dụng chứng thực khóa công khai (digital certificate) hoặc các phần của hạ tầng khóa công khai (public key infrastructure - PKI).

Tấn công theo thời gian

Năm 1995, Paul Kocher đã phát hiện một loại tấn công mới nhắm vào RSA: nếu kẻ tấn công có thông tin đầy đủ về phần cứng mã hóa và đo được thời gian giải mã cho một số bản mã cụ thể, họ có thể nhanh chóng suy ra khóa d. Loại tấn công này cũng có thể áp dụng cho các hệ thống chữ ký điện tử sử dụng RSA. Đến năm 2003, Dan Boneh và David Brumley đã chứng minh một hình thức tấn công thực tế hơn, bằng cách phân tích thừa số RSA qua mạng máy tính (như máy chủ web SSL). Tấn công này khai thác thông tin rò rỉ từ việc tối ưu hóa định lý số dư Trung Quốc, điều mà nhiều ứng dụng đã áp dụng.

Để bảo vệ chống lại tấn công theo thời gian, cần đảm bảo quá trình giải mã xảy ra trong thời gian cố định không phụ thuộc vào bản mã. Tuy nhiên, phương pháp này có thể làm giảm hiệu suất tính toán. Thay vào đó, hầu hết các ứng dụng RSA sử dụng kỹ thuật che mắt. Kỹ thuật này tận dụng tính chất nhân của RSA: thay vì tính c mod n, An chọn một số ngẫu nhiên r và tính (rc) mod n. Kết quả là rm mod n, và tác động của r được loại bỏ bằng cách nhân với nghịch đảo của r. Với mỗi bản mã, giá trị r được chọn riêng biệt, do đó thời gian giải mã không phụ thuộc vào giá trị của bản mã.

Tấn công lựa chọn thích nghi bản mã

Năm 1981, Daniel Bleichenbacher đã phát hiện một loại tấn công lựa chọn thích nghi bản mã (adaptive chosen ciphertext attack) thực tế đối với văn bản mã hóa bằng RSA. Tấn công này dựa trên tiêu chuẩn PKCS #1 v1, một tiêu chuẩn chuyển đổi bản rõ có khả năng kiểm tra tính hợp lệ của văn bản sau khi giải mã. Do những khiếm khuyết trong PKCS #1, Bleichenbacher có thể tấn công RSA trong giao thức SSL để tìm khóa phiên. Phát hiện này dẫn đến việc khuyến nghị sử dụng các mô hình chuyển đổi an toàn hơn như chuyển đổi mã hóa bất đối xứng tối ưu (Optimal Asymmetric Encryption Padding), đồng thời RSA đã cập nhật PKCS #1 với phiên bản mới để chống lại dạng tấn công này.

• Clifford Cocks
• Mật mã lượng tử
• Độ dài của khóa
• Lý thuyết độ phức tạp tính toán

• R. Rivest, A. Shamir, L. Adleman. Phương pháp để đạt được chữ ký số và hệ thống mã hóa công khai Lưu trữ 2007-01-27 tại Wayback Machine. Communications of the ACM, Tập 21 (2), trang 120–126. 1978. Được công bố lần đầu dưới dạng 'Technical Memo' của MIT vào tháng 4 năm 1977. Công bố đầu tiên của sơ đồ RSA.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, và Clifford Stein. Introduction to Algorithms, Ấn bản thứ hai. MIT Press và McGraw-Hill, 2001. ISBN 0262032937. Phần 31.7: Hệ thống mã hóa công khai RSA, trang 881–887.

Liên kết bên ngoài

• Tiêu chuẩn PKCS #1: Mã hóa RSA Lưu trữ 2005-10-29 tại Wayback Machine (Trang web của RSA Laboratories)
  • Tiêu chuẩn PKCS #1 'cung cấp các khuyến nghị cho việc triển khai mã hóa khóa công khai dựa trên thuật toán RSA, bao gồm các yếu tố: các nguyên tắc mã hóa; các phương pháp mã hóa; các phương pháp chữ ký kèm theo; cú pháp ASN.1 để đại diện các khóa và nhận diện các phương pháp'.