RSA

Trong mật mã học, RSA là 1 thuật toán 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 giá 1 sự tiến bộ vượt bật của lĩnh vực mật mã học trong việc sử dụng khóa công khai. RSA đượ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.

Lịch sử

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

Trước đó, vào năm 1973, Clifford Cocks, 1 nhà toán học người Anh làm việc tại GCHQ (Goverment Communications Headquarters – 1 cơ quan tình báo của vương quốc Anh), đã mô tả 1 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ử 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.

Thuật toán RSA được MIT đăng ký bằng sáng chế tại Mỹ vào năm 1983 (Số đăng ký 4.105.829). Bằng sáng chế này hết hạn vào ngày 21/09/2000. Tuy nhiên, do thuật toán đã được công bố trước khi có đăng ký bảo hộ nên sự bảo hộ hầu như không có giá trị bên ngoài nước Mỹ. Ngoài ra, nếu công trình của Clifford Cocks đã được công bố trước đó thì bằng sáng chế RSA đã không thể đăng ký.

Hoạt động

Thuật toán RSA có 2 khóa: khóa công khai (public key) và khóa bí mật (private key). Mỗi khóa là những số cố định được sử dụng trong quá trình mã hóa và giải mã. Khóa công khai được công bố rộng rãi 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 chỉ có thể được giải mã bằng khóa bí mật tương ứng. Nói cách khác, mọi người đều có thể mã hóa nhưng chỉ có người biết khóa bí mật mới có thể giải mã được.

Tạo khóa

Với thuật toán RSA, đầu tiên chúng ta cần tạo ra cho mình 1 cặp khóa bao gồm khóa công khai và khóa bí mật theo các bước sau:

  1. Chọn 2 số nguyên tố lớn pq với p ≠ q, p và q được lựa chọn ngẫu nhiên và độc lập nhau.
  2. Tính n = p.q , n được sử dụng trong cả khóa công khai và bí mật. Độ dài của n, tính bằng bit, chính là độ dài khóa.
  3. Tính giá trị của hàm số φ(n) = φ(p)φ(q) =  (p − 1)(q − 1)  với φ làm hàm phi Euler
  4. Chọn 1 số nguyên e sao cho 1 < e < φ(n)gcd(e,φ(n)) =1, tức là ước số chung lớn nhất của e và φ(n) là 1, hay e và φ(n) là 2 số nguyên tố cùng nhau.
  5. Tính d sao cho d.e = 1 (mod φ(n))

Một số lưu ý:

  • Các số nguyên tố thường được chọn bằng phương pháp xác suất.
  • Bước 4 và 5 có thể được thực hiện bằng giải thuật Euclid mở rộng.
  • Bước 5 có thể viết cách khác: Tìm số tự nhiên x sao cho d =
  • Từ bước 3, PKCS#1 (Public-Key Cryptography Standards – PKCS) phiên bản 2.1 sử dụng ⋋ = LCM(p-1,q-1) thay cho φ(n) = (p − 1)(q − 1) (LCM – Bội số chung nhỏ nhất)

Khóa công khai bao gồm n (mô đun) e (số mũ công khai hay số mũ mã hóa)

Khóa bí mật bao gồm n (mô đun)d (số mũ bí mật hay số mũ giải mã)

1 dạng khác của khóa bí mật bao gồm

  • pq, 2 số nguyên tố chọn ban đầu
  • d mod (p-1)d mod (q-1) (thường được gọi là dmp1 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 Hoa (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.

Chúng ta gửi khóa công khai cho mọi người, và giữ khóa bí mật cho mình. Ở đây vai trò của pq 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ì pq sẽ được xóa ngay sau khi thực hiện xong quá trình tạo khóa.

Mã hóa

Gọi M là thông điệp ban đầu (thông điệp rõ – plaintext) và C là thông điệp mã hóa.

Đầu tiên chúng ta cần chuyển M thành 1 số m < n theo 1 hàm có để đả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ả trong phần Chuyển đổi văn bản rõ bên dưới.

Lúc này khi có m và biết n cũng như e, ta tính C theo công thức sau:

rsa_01

Giải mã

Với thông điệp mã hóa C và biết khóa bí mật d. Chúng ta có thể tìm được m từ C theo công thức sau:

rsa_03

Biết m, chúng ta tìm được M theo phương pháp đã thỏa thuận trước.

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

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 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 1 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 như e =3) và m cũng có giá trị nhỏ, giá trị  rsa_02 cũng nhận giá trị nhỏ (so với n). Như vậy phép modun 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 modun).
  • 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 1 bảng tra giữa bản rõ và bản mã. Khi gặp 1 bản mã, kẻ tấn công sử dụng bản tra để tìm ra bản rõ tương ứng.

Trên thực tế, chúng 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. 1 đ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ự, 1 ký tự ASCII khác, SOH, có giá trị 1 sẽ luôn cho bản mã là 1. Với các hệ thống dùng giá trị e nhỏ thì tất cả cá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 1 hình thức chuyển đổi ngẫu nhiên 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 1 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õ (1 bản rõ sẽ có thể tương ứng với nhiều bản mã tùy thuộc vào cách chuyển đổi).

Tạo chữ ký số

Thuật toán RSA còn được dùng để tạo chữ ký số cho văn bản. Để làm được việc này, chúng ta tạo ra 1 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 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 người khác (có khóa công khai) nhận được văn bản cùng với chữ ký điện tử, họ tính ra giá trị mũ (e mod n) của chữ ký đồng thời tính giá trị băm của văn bản. Nếu 2 giá trị này như nhau thì chứng tỏ rằng người tạo chữ ký biết khóa bí mật và văn bản không bị thay đổi sau khi ký.

 An ninh

Độ an toàn của hệ thống RSA dựa trên 2 vấn đề lớn của toán học: bài toàn phân tích ra thừa số nguyên tố các 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 quả để giải chúng) thì không thể thực hiện được việc phá mã toàn bộ đối với RSA. Phá mã một phần phải được ngăn chặn bằng các phương pháp chuyển đổi bản rõ 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 đó (en) 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).

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 lý thuyết) có thể giải bài toán phân tích ra thừa số trong thời gian đa thức. Tuy nhiên, máy tính lượng tử vẫn chưa thể phát triển được tới mức độ này trong nhiều năm nữa.

Năm 2010, các nhà khoa học thuộc Đại học Michigan đã công bố phát hiện một kẻ hở trong hệ thống mã hoá RSA. Cách phá vỡ hệ thống, lấy khoá bí mật RSA 1024 bit chỉ trong vài ngày thay vì vài năm nếu tấn công theo cách thông thường – tấ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 hệ thống, từ đó giúp tìm ra khoá bí mật. Việc tấn công được thực hiện trên một FPGA. Báo cáo được trình bày tại hội nghị DATE 2010 diễn ra tại Dresden, Đức tháng 3 năm 2010.

Leave a Reply