RSA (mã hóa) – Wikipedia tiếng Việt

Đối với những định nghĩa khác, xem RSA ( khuynh hướng )

Trong mật mã học, RSA là một thuật toán mật mã hóa khóa công khai. Đây là thuật toán đầu tiên phù hợp với việc tạo ra chữ ký điện tử đồng thời với việc mã hóa. Nó đánh dấu một sự tiến bộ vượt bậc của lĩnh vực mật mã học trong việc sử dụng khóa công cộng. RSA đang được sử dụng phổ biến trong thương mại điện tử và được cho là đảm bảo an toàn với điều kiện độ dài khóa đủ lớn.

Thuật toán được Ron Rivest, Adi Shamir và Len Adleman miêu tả lần tiên phong vào năm 1977 tại Học viện Công nghệ Massachusetts ( MIT ). Tên của thuật toán lấy từ 3 vần âm đầu của tên 3 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, đã mô tả một thuật toán tương tự. Với khả năng tính toán tại thời điểm đó thì thuật toán này không khả thi và chưa bao giờ được thực nghiệm. Tuy nhiên, phát minh này chỉ được công bố vào năm 1997 vì được xếp vào loại tuyệt mật.

Bạn đang đọc: RSA (mã hóa) – Wikipedia tiếng Việt

Thuật toán RSA được MIT ĐK văn bằng bản quyền trí tuệ tại Hoa Kỳ vào năm 1983 ( Số Đ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, do thuật toán đã được công bố trước khi có ĐK bảo lãnh nên sự bảo lãnh phần đông không có giá trị bên ngoài Hoa Kỳ. Ngoài ra, nếu như khu công trình của Clifford Cocks đã được công bố trước đó thì văn bằng bản quyền trí tuệ RSA đã không hề được ĐK .

Mục lục nội dung

Mô tả sơ lược[sửa|sửa mã nguồn]

Thuật toán RSA có hai khóa : khóa công khai minh bạch ( hay khóa công cộng ) và khóa bí hiểm ( hay khóa cá thể ). Mỗi khóa là những số cố định và thắt chặt sử dụng trong quy trình mã hóa và giải thuật. Khóa công khai minh bạch được công bố thoáng đãng cho mọi người và được dùng để mã hóa. Những thông tin được mã hóa bằng khóa công khai minh bạch chỉ hoàn toàn có thể được giải thuật bằng khóa bí hiểm tương ứng. Nói cách khác, mọi người đều hoàn toàn có thể mã hóa nhưng chỉ có người biết khóa cá thể ( bí hiểm ) mới hoàn toàn có thể giải thuật được .Ta hoàn toàn có thể mô phỏng trực quan một hệ mật mã khoá công khai minh bạch như sau : Bình muốn gửi cho An một thông tin mật mà Bình muốn duy nhất An hoàn toàn có thể đọc được. Để làm được điều này, An gửi cho Bình một chiếc hộp có khóa đã mở sẵn và giữ lại chìa khóa. Bình nhận chiếc hộp, cho vào đó một tờ giấy viết thư thông thường và khóa lại ( như loại khoá thường thì chỉ cần sập chốt lại, sau khi sập chốt khóa ngay cả Bình cũng không hề mở lại được-không đọc lại hay sửa thông tin trong thư được nữa ). Sau đó Bình gửi chiếc hộp lại cho An. An mở hộp với chìa khóa của mình và đọc thông tin trong thư. Trong ví dụ này, chiếc hộp với khóa mở đóng vai trò khóa công khai minh bạch, chiếc chìa khóa chính là khóa bí hiểm .
Giả sử An và Bình cần trao đổi thông tin bí hiểm trải qua một kênh không bảo đảm an toàn ( ví dụ như Internet ). Với thuật toán RSA, An tiên phong cần tạo ra cho mình cặp khóa gồm khóa công khai minh bạch và khóa bí hiểm theo những bước sau :

Chọn 2 số nguyên tố lớn $p\,$ $q\,$ $p\neq q$
Tính: $n=pq\,$
Tính: giá trị hàm số Euler $\phi (n)=(p-1)(q-1)\,$
Chọn một số tự nhiên $e$ $1<e<\phi (n)\,$
Tính: $d$ $de\equiv 1{\pmod {\phi (n)}}$ Đồng dư để hiểu rõ hơn)

Một số quan tâm :

Các số nguyên tố thường được chọn bằng phương pháp thử xác suất.
Các bước 4 và 5 có thể được thực hiện bằng giải thuật Euclid mở rộng (xem thêm: số học môđun).
Bước 5 có thể viết cách khác: Tìm số tự nhiên $x\,$ $d={\frac {x(p-1)(q-1)+1}{e}}$ $d\mod {(p-1)(q-1)}\,$
Từ bước 3, PKCS#1 v2.1 sử dụng $\lambda =LCM(p-1,q-1)\,$ $\phi =(p-1)(q-1)\,$

Khóa công khai bao gồm:

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

Khóa bí mật bao gồm:

n, môđun, xuất hiện cả trong khóa công khai và khóa bí mật, và
d, số mũ bí mật (cũng gọi là số mũ giải mã).

Một dạng khác của khóa bí hiểm gồm có :

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

Dạng này cho phép thực hiện giải mã và ký nhanh hơn với việc sử dụng định lý số dư Trung Quốc (tiếng Anh: Chinese Remainder Theorem – CRT). Ở dạng này, tất cả thành phần của khóa bí mật phải được giữ bí mật.

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

Giả sử Bình muốn gửi đoạn thông tin M cho An. Đầu tiên Bình chuyển M thành một số m < n theo một hàm có thể đảo ngược (từ m có thể xác định lại M) được thỏa thuận trước. Quá trình này được mô tả ở phần #Chuyển đổi văn bản rõ.

Lúc này Bình có m và biết n cũng như e do An gửi. Bình sẽ tính c là bản mã hóa của m theo công thức:

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

Hàm trên có thể tính dễ dàng sử dụng phương pháp tính hàm mũ (theo môđun) bằng (thuật toán bình phương và nhân) Cuối cùng Bình gửi c cho An.

An nhận c từ Bình và biết khóa bí mật d. An có thể tìm được m từ c theo công thức sau:

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

Biết m, An tìm lại M theo phương pháp đã thỏa thuận trước. Quá trình giải mã hoạt động vì ta có

c^{d}\equiv (m^{e})^{d}\equiv m^{ed}{\pmod {n}}

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

m^{ed}\equiv m{\pmod {p}}

và

Xem thêm: royal tiếng Anh là gì?

m^{ed}\equiv m{\pmod {q}}

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

m^{ed}\equiv m{\pmod {pq}}

hay :

c^{d}\equiv m{\pmod {n}}

Sau đây là một ví dụ với những số đơn cử. Ở đây tất cả chúng ta sử dụng những số nhỏ để tiện thống kê giám sát còn trong thực tiễn phải dùng những số có giá trị đủ lớn .Lấy :
p = 61
— số nguyên tố thứ nhất (giữ bí mật hoặc hủy sau khi tạo khóa)

q = 53
— số nguyên tố thứ hai (giữ bí mật hoặc hủy sau khi tạo khóa)

n = pq = 3233
— môđun (công bố công khai)

e = 17
— số mũ công khai

d = 2753
— số mũ bí mật

Khóa công khai là cặp (e, n). Khóa bí mật là d. Hàm mã hóa là:

encrypt(m) = me mod n = m17 mod 3233

với m là văn bản rõ. Hàm giải mã là:

decrypt(c) = cd mod n = c2753 mod 3233

với c là văn bản mã.

Để mã hóa văn bản có giá trị 123, ta thực thi phép tính :

encrypt(123) = 12317 mod 3233 = 855

Để giải thuật văn bản có giá trị 855, ta thực thi phép tính :

decrypt(855) = 8552753 mod 3233 = 123

Cả hai phép tính trên đều hoàn toàn có thể được thực thi hiệu suất cao nhờ thuật toán bình phương và nhân .

Chuyển đổi văn bản rõ[sửa|sửa mã nguồn]

Trước khi thực hiện mã hóa, ta phải thực hiện việc chuyển đổi văn bản rõ (chuyển đổi từ M sang m) sao cho không có giá trị nào của M tạo ra văn bản mã không an toàn. Nếu không có quá trình này, RSA sẽ gặp phải một số vấn đề sau:

Nếu m = 0 hoặc m = 1 sẽ tạo ra các bản mã có giá trị là 0 và 1 tương ứng
Khi mã hóa với số mũ nhỏ (chẳng hạn e = 3) và m cũng có giá trị nhỏ, giá trị $m^{e}$ n). Như vậy phép môđun không có tác dụng và có thể dễ dàng tìm được m bằng cách khai 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ó thành phần ngẫu nhiên) nên kẻ tấn công có thể thực hiện tấn công lựa chọn bản rõ bằng cách tạo ra một bảng tra giữa bản rõ và bản mã. Khi gặp một bản mã, kẻ tấn công sử dụng bảng tra để tìm ra bản rõ tương ứng.

Trên thực tế, ta thường gặp 2 vấn đề đầu khi gửi các bản tin ASCII ngắn với m là nhóm vài ký tự ASCII. Một đoạn tin chỉ có 1 ký tự NUL sẽ được gán 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ự, một ký tự ASCII khác, SOH, có giá trị 1 sẽ luôn cho ra bản mã là 1. Với các hệ thống dùng giá trị e nhỏ thì tất cả ký tự ASCII đều cho kết quả mã hóa không an toàn vì giá trị lớn nhất của m chỉ là 255 và 2553 nhỏ hơn giá trị n chấp nhận được. Những bản mã này sẽ dễ dàng bị phá mã.

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

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

Tạo chữ ký số cho văn bản[sửa|sửa mã nguồn]

Thuật toán RSA còn được dùng để tạo chữ ký số cho văn bản. Giả sử An muốn gửi cho Bình một văn bản có chữ ký của mình. Để làm việc này, An tạo ra một giá trị băm (hash value) của văn bản cần ký và tính giá trị mũ d mod n của nó (giống như khi An thực hiện giải mã). Giá trị cuối cùng chính là chữ ký điện tử của văn bản đang xét. Khi Bình nhận được văn bản cùng với chữ ký điện tử, anh ta tính giá trị mũ e mod n của chữ ký đồng thời với việc tính giá trị băm của văn bản. Nếu 2 giá trị này như nhau thì Bình biết rằng người tạo ra chữ ký biết khóa bí mật của An và văn bản đã không bị thay đổi sau khi ký.

Cần quan tâm rằng những giải pháp quy đổi bản rõ ( như RSA-PSS ) giữ vai trò quan trọng so với quy trình mã hóa cũng như chữ ký điện tử và không được dùng khóa chung cho đồng thời cho cả hai mục tiêu trên .
Độ bảo đảm an toàn của mạng lưới hệ thống RSA dựa trên 2 yếu tố của toán học : bài toán nghiên cứu và phân tích ra thừa số nguyên tố những số nguyên lớn và bài toán RSA. Nếu 2 bài toán trên là khó ( không tìm được thuật toán hiệu suất cao để giải chúng ) thì không hề triển khai được việc phá mã hàng loạt so với RSA. Phá mã một phần phải được ngăn ngừa bằng những chiêu thức quy đổi bản rõ bảo đảm an toàn .

Bài toán RSA là bài toán tính căn bậc e môđun n (với n là hợp số): tìm số m sao cho me=c mod n, trong đó (e, n) chính là khóa công khai và c là bản mã. Hiện nay phương pháp triển vọng nhất giải bài toán này là phân tích n ra thừa số nguyên tố. Khi thực hiện được điều này, kẻ tấn công sẽ tìm ra số mũ bí mật d từ khóa công khai và có thể giải mã theo đúng quy trình của thuật toán. Nếu kẻ tấn công tìm được 2 số nguyên tố p và q sao cho: n = pq thì có thể dễ dàng tìm được giá trị (p-1)(q-1) và qua đó xác định d từ e. Chưa có một phương pháp nào được tìm ra trên máy tính để giải bài toán này trong thời gian đa thức (polynomial-time). Tuy nhiên người ta cũng chưa chứng minh được điều ngược lại (sự không tồn tại của thuật toán). Xem thêm phân tích ra thừa số nguyên tố về vấn đề này.

Tại thời điểm năm 2005, số lớn nhất có thể được phân tích ra thừa số nguyên tố có độ dài 663 bít với phương pháp phân tán trong khi khóa của RSA có độ dài từ 1024 tới 2048 bít. Một số chuyên gia cho rằng khóa 1024 bít có thể sớm bị phá vỡ (cũng có nhiều người phản đối việc này). Với khóa 4096 bít thì hầu như không có khả năng bị phá vỡ trong tương lai gần. Do đó, người ta thường cho rằng RSA đảm bảo an toàn với điều kiện n được chọ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ờ với máy tính cá nhân dùng các phần mềm có sẵn. 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ại thời điểm năm 1999. Một thiết bị lý thuyết có tên là TWIRL do Shamir và Tromer mô tả năm 2003 đã đặt ra câu hỏi về độ an toàn của khóa 1024 bít. Vì vậy hiện nay người ta khuyến cáo 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ỉ ra rằng : máy tính lượng tử ( trên kim chỉ nan ) hoàn toàn có thể giải bài toán nghiên cứu và phân tích ra thừa số trong thời hạn đa thức. Tuy nhiên, máy tính lượng tử vẫn chưa thể tăng trưởng được tới mức độ này trong nhiều năm nữa .Năm 2010, những nhà khoa học thuộc Đại học Michigan đã công bố phát hiện một kẽ hở trong mạng lưới hệ thống mật mã hoá RSA. Cách phá vỡ mạng lưới hệ thống, lấy khoá bí hiểm RSA 1024 bit chỉ trong vài ngày thay vì vài năm nếu tiến công theo cách thường thì – tiến công bằng brute force ( dò tìm lần lượt ). Các nhà khoa học tạo một điện thế lớn để gây lỗi mạng lưới hệ thống, từ đó giúp tìm ra khoá bí hiểm. Việc tiến công được triển khai trên một FPGA. Báo cáo được trình diễn tại hội nghị DATE 2010 diễn ra tại Dresden, Đức tháng 3 năm 2010 .

Xem thêm: Bài toán phân tích RSA

Các yếu tố đặt ra trong thực tiễn[sửa|sửa mã nguồn]

Quá trình tạo khóa[sửa|sửa mã nguồn]

Việc tìm ra 2 số nguyên tố đủ lớn p và q thường được thực hiện bằng cách thử xác suất các số ngẫu nhiên có độ lớn phù hợp (dùng phép kiểm tra nguyên tố cho phép loại bỏ hầu hết các hợp số).

p và q còn cần được chọn không quá gần nhau để phòng trường hợp phân tích n bằng phương pháp phân tích Fermat. Ngoài ra, nếu p-1 hoặc q-1 có thừa số nguyên tố nhỏ thì n cũng có thể dễ dàng bị phân tích và vì thế p và q cũng cần được thử để tránh khả năng này.

Bên cạnh đó, cần tránh sử dụng các phương pháp tìm số ngẫu nhiên mà kẻ tấn công có thể lợi dụng để biết thêm thông tin về việc lựa chọn (cần dùng các bộ tạo số ngẫu nhiên tốt). Yêu cầu ở đây là các số được lựa chọn cần đồng thời ngẫu nhiên và không dự đoán được. Đây là các yêu cầu khác nhau: một số có thể được lựa chọn ngẫu nhiên (không có kiểu mẫu trong kết quả) nhưng nếu có thể dự đoán được dù chỉ một phần thì an ninh của thuật toán cũng không được đảm bảo. Một ví dụ là bảng các số ngẫu nhiên do tập đoàn Rand xuất bản vào những năm 1950 có thể rất thực sự ngẫu nhiên nhưng kẻ tấn công cũng có bảng này. Nếu kẻ tấn công đoán được một nửa chữ số của p hay q thì chúng có thể dễ dàng tìm ra nửa còn lại (theo nghiên cứu của Donald Coppersmith vào năm 1997)

Một điểm nữa cần nhấn mạnh là khóa bí mật d phải đủ lớn. Năm 1990, Wiener chỉ ra rằng nếu giá trị của p nằm trong khoảng q và 2q (khá phổ biến) và d < n1/4/3 thì có thể tìm ra được d từ n và e.

Mặc dù e đã từng có giá trị là 3 nhưng hiện nay các số mũ nhỏ không còn được sử dụng do có thể tạo nên những lỗ hổng (đã đề cập ở phần chuyển đổi văn bản rõ). Giá trị thường dùng hiện nay là 65537 vì được xem là đủ lớn và cũng không quá lớn ảnh hưởng tới việc thực hiện hàm mũ.

RSA có vận tốc triển khai chậm hơn đáng kể so với DES và những thuật toán mã hóa đối xứng khác. Trên trong thực tiễn, Bình sử dụng một thuật toán mã hóa đối xứng nào đó để mã hóa văn bản cần gửi và chỉ sử dụng RSA để mã hóa khóa để giải thuật ( thường thì khóa ngắn hơn nhiều so với văn bản ) .Phương thức này cũng tạo ra những yếu tố bảo mật an ninh mới. Một ví dụ là cần phải tạo ra khóa đối xứng thật sự ngẫu nhiên. Nếu không, kẻ tiến công ( thường ký hiệu là Hắc ) sẽ bỏ lỡ RSA và tập trung chuyên sâu vào việc đoán khóa đối xứng .

Phân phối khóa[sửa|sửa mã nguồn]

Cũng giống như các thuật toán mã hóa khác, cách thức phân phối khóa công khai là một trong những yếu tố quyết định đối với độ an toàn của RSA. Quá trình phân phối khóa cần chống lại được tấn công đứng giữa (man-in-the-middle attack). Giả sử Hắc có thể gửi cho Bình một khóa bất kỳ và khiến Bình tin rằng đó là khóa (công khai) của An. Đồng thời Hắc có khả năng đọc được thông tin trao đổi giữa Bình và An. Khi đó, Hắc sẽ gửi cho Bình khóa công khai của chính mình (mà Bình nghĩ rằng đó là khóa của An). Sau đó, Hắc đọc tất cả văn bản mã hóa do Bình gửi, giải mã với khóa bí mật của mình, giữ một bản copy đồng thời mã hóa bằng khóa công khai của An và gửi cho An. Về nguyên tắc, cả Bình và An đều không phát hiện ra sự can thiệp của người thứ ba. Các phương pháp chống lại dạng tấn công này thường dựa trên các chứng thực khóa công khai (digital certificate) hoặc các thành phần của hạ tầng khóa công khai (public key infrastructure – PKI).

Tấn công dựa trên thời hạn[sửa|sửa mã nguồn]

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

Để chống lại tấn công dựa trên thời gian là đảm bảo quá trình giải mã luôn diễn ra trong thời gian không đổi bất kể văn bản mã. Tuy nhiên, cách 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 một kỹ thuật gọi là che mắt. Kỹ thuật này dựa trên tính nhân của RSA: thay vì tính cd mod n, An đầu tiên chọn một số ngẫu nhiên r và tính (rec)d mod n. Kết quả của phép tính này là rm mod n và tác động của r sẽ được loại bỏ bằng cách nhân kết quả với nghịch đảo của r. Đối với mỗi văn bản mã, người ta chọn một giá trị của r. Vì vậy, thời gian giải mã sẽ không còn phụ thuộc vào giá trị của văn bản mã.

Xem thêm: Zalo OA – official account là gì? Cách tạo một Zalo OA

Tấn công lựa chọn thích nghi bản mã[sửa|sửa mã nguồn]

Năm 1981, Daniel Bleichenbacher mô tả dạng tiến công lựa chọn thích nghi bản mã ( adaptive chosen ciphertext attack ) tiên phong hoàn toàn có thể triển khai trên thực tiễn so với một văn bản mã hóa bằng RSA. Văn bản này được mã hóa dựa trên tiêu chuẩn PKCS # 1 v1, một tiêu chuẩn quy đổi bản rõ có năng lực kiểm tra tính hợp lệ của văn bản sau khi giải thuật. Do những khiếm khuyết của PKCS # 1, Bleichenbacher hoàn toàn có thể thực thi một tiến công lên bản RSA dùng cho giao thức SSL ( tìm được khóa phiên ). Do phát hiện này, những quy mô quy đổi bảo đảm an toàn hơn như quy đổi mã hóa bất đối xứng tối ưu ( Optimal Asymmetric Encryption Padding ) được khuyến nghị sử dụng. Đồng thời phòng nghiên cứu và điều tra của RSA cũng đưa ra phiên bản mới của PKCS # 1 có năng lực chống lại dạng tiến công nói trên .