Giải thuật rsa

TỔNG CÔNG TY BƯU CHÍNH VIỄN THÔNG VIỆT NAM HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG --------------------------------- Báo cáo bài tập lớn GIẢI THUẬT RSA Nhóm biên soạn: Bùi Minh Tuấn Lê Việt Dương Nguyễn Thị Thu Huyền Phan Văn Quân Hà nội tháng 5 năm 2007 LỜI NÓI ĐẦU Thuật toán mã hóa công khai đã ra đời từ lâu. Nhưng trước những nhu cầu về giao dịch an toàn trên mạng Internet ngày nay, những ứng dụng của nó ngày càng tỏ rõ tầm quan trọng. Một trong những thuật toán mã hóa công khai phổ biến đó là RSA. Thuật toán được ứng dụng rộng rãi cho công nghệ VPN. Cuốn tài liệu này được viết ra với mong muốn giúp các bạn hiểu được một cách tổng quát cách hoạt động của RSA. Tài liệu được chia làm 2 phần bao gồm 2 chương, trong đó phần I (chương I) trình bày về tổng quan về thuật toán RSA; phần II tập truy trình bày về những thực tế khi triển khai RSA. MỤC LỤC DANH MỤC HÌNH VẼ Hình 1.1 Mã hóa và giải mã 5 Hình 1.2 Trao đổi khóa bất đối xứng 7 Hình 2.1 Cố gắng phá hoại cặp khóa bất đối xứng 14 RSA HOẠT ĐỘNG NHƯ THẾ NÀO Giới thiệu về RSA 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 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 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, 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. Thuật toán RSA được MIT đăng ký bằng sáng chế 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, 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 Hoa Kỳ. Ngoài ra, nếu như công trình của Clifford Cocks đã được công bố trước đó thì bằng sáng chế RSA đã không thể được đăng ký. Thuật toán RSA Thuật toán Giả sử A và B cần trao đổi thông tin bí mật thông qua một kênh không an toàn (ví dụ như Internet). Với thuật toán RSA, đầu tiên A cần tạo ra cho mình cặp khóa gồm khóa công khai và khóa bí mật theo các bước sau: Bước 1: Chọn 2 số nguyên tố lớn và với , được lựa chọn ngẫu nhiên và độc lập. Bước 2: Tính: . Bước 3: Tính: giá trị hàm số Ơle . Bước 4: Chọn một số tự nhiên e sao cho và là số nguyên tố cùng nhau với . Bước 5: Tính: d sao cho . Một số lưu ý 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. Bước 5 có thể viết cách khác: Tìm số tự nhiên sao cho cũng là số tự nhiên. Khi đó sử dụng giá trị . Ở bước 3 ta có thể sử dụng thay cho . 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í mật bao gồm: p and 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. Ở 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. A gửi khóa công khai cho B 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. Me Hình 1.1 Mã hóa và giải mã Mã hóa Giả sử B muốn gửi đoạn thông tin M cho A. Đầu tiên B 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. Lúc này B có m và biết n cũng như e do A gửi, B sẽ tính c là bản mã hóa của m theo công thức: 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 gửi c cho A. Giải mã A nhận c từ B và biết khóa bí mật d. A có thể tìm được m từ c theo công thức sau: Biết m, A 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ó . Do ed ≡ 1 (mod p-1) và ed ≡ 1 (mod q-1), (theo định lý Fermat nhỏ) nên: và 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ó: . hay: . Các định lý cơ sở Thuật toán RSA dựa trên các định lý sau: Đinh lý 1 (Định lý nhỏ của Fermat): Với p là một số nguyên tố khác 2 thì chia một số a lũy thừa p cho p sẽ có số dư chính bằng a: Mở rộng ta có với là số nguyên tố cùng nhau với m và nhỏ hơn m Đinh lý 2(Định lý Số dư Trung Quốc): Cho hệ phương trình đồng dư bậc nhất trong đó m1,m2,...,mk đôi một nguyên tố cùng nhau. Định lý Hệ phương trình đồng dư nói trên có nghiệm duy nhất theo mođun M = m1.m2...mk là trong đó M1 = M / m1,M2 = M / m2,...,Mk = M / mky1 = (M1) − 1(mod m1), y2 = (M2) − 1(mod m2),..., yk = (Mk) − 1(mod mk) Áp dụng trường hợp đặc biệt: Cho p và q là 2 số nguyên tố cùng nhau. Nếu a= b (mod p) và a = b (mod q) thì a= b (mod pq) Ví dụ Sau đây là một ví dụ với những số cụ thể. Ở đây chúng ta sử dụng những số nhỏ để tiện tính toán còn trong thực tế phải dùng các số có giá trị đủ lớn. Lấy 2 số nguyên tố khác nhau p, q: p = 11 q = 13 Ta tính được số module N là: N= pq = 11 * 13 = 143 Giá trị hàm số Ơ le là: = (p-1) * (q-1) = 10 * 12 = 120 e là số nguyên tố cùng nhau với e = 17 Tìm d sao cho ed = 1 (mod ) 17 * d = 1 (mod 120) => d = 113 vì 7 * 113 = 1921 = 16 * 120 + 1 = 1 (mod 120) Khóa công khai là cặp (e, n). Khóa bí mật là d. Hàm mã hóa là: c = encrypt(m) = me mod n = m17 mod 143 với m là văn bản rõ. Hàm giải mã là: m = decrypt(c) = cd mod n = c113 mod 143 với c là văn bản mã. Để mã hóa văn bản có giá trị m = 50 và có cặp khóa công khai (e,n) là (17,143) ta thực hiện phép tính: encrypt(50) = 5017 mod 143 = 85 Để giải mã văn bản có giá trị c=545 và cặp khóa bí mật (d,n) là (113,1435) ta thực hiện phép tính: decrypt(85) = 85113 mod 143 = 50 Cả hai phép tính trên đều có thể được thực hiện hiệu quả nhờ giải thuật bình phương và nhân. Hình 1.2. Trao đổi khóa bất đối xứng Tạo chữ ký số Giới thiệu chung Ngày nay, có ba hệ mã hóa thông dụng được sử dụng để xây dựng các lược đồ ký điện tử, đó là hệ mã hóa RSA, hệ mã hóa dựa trên bài toán logarit rời rạc và hệ mã hóa dựa trên đường cong elliptic. Các hàm một chiều sử dụng trong các hệ mã này hiện đang được xem là an toàn theo thừa nhận (tức là không có thuật toán nào hữu hiệu để tính hàm ngược của chúng). Tuy nhiên, một vấn đề cơ bản của tính an toàn đối với một lược đồ ký điện tử lại là tính không thể giả mạo được chữ ký và điều này không suy ra được trực tiếp từ tính an toàn của hệ mã mà nó dựa vào. Trong khoảng mười năm gần đây, vấn đề này đang thu hút rất nhiều sự quan tâm của cộng đồng mật mã trên thế giới. Người ta đang cố gắng đưa ra những lược đồ ký sao cho tính không thể giả mạo được của nó có thể được đánh giá thông qua độ an toàn của các hàm một chiều mà nó sử dụng. Trong bài này chúng tôi xem xét một số lược đồ ký sử dụng hàm một chiều của hệ mã RSA (đang được xem là phổ biến nhất hiện nay). Giả sử A muốn gửi cho B một văn bản có chữ ký của mình. Để làm việc này, A 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 A 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ậ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 biết rằng người tạo ra chữ ký biết khóa bí mật của A và văn bản đã không bị thay đổi sau khi ký. Ký điện tử và những mô hình nguyên thủy Hàm băm mật mã Người ta thường sử dụng sự hỗ trợ của các hàm băm mật mã trong quá trình Encoding của các lược đồ ký. Một hàm băm với đầu vào là văn bản (có độ dài bất kỳ), sinh ra cho ta xâu H có độ dài xác định, được gọi là mã băm của . Hàm băm mật mã h phải thỏa mãn các điều kiện sau: • Là hàm một chiều: Tức là nếu cho ta sẽ dễ dàng tính ra H=h(M) . Nhưng nếu chỉ có mã băm H thì rất khó có thể tìm được văn bản M sao cho H=h(M) (rất khó có nghĩa là hiện nay không có thuật toán hữu hiệu nào làm được). • Không tìm được xung đột: Tức là rất khó để tìm ra hai văn bản M và M’ có cùng mã băm. • Không tìm được xung đột của văn bản cho trước: Tức là cho trước văn bản M thì rất khó để tìm được văn bản M’có cùng mã băm với văn bản Mđó. Trong thực tế rất khó có thể tìm ra được một hàm băm thỏa mãn nghiêm ngặt các tính chất trên. Hiện nay, ngày càng có những kết quả thám mã mạnh tấn công vào tính chất thứ hai. Cho nên, các lược đồ ký gần đây thường cố gắng tránh việc dựa trực tiếp vào tính chất này. Lược đồ ký RSA nguyên thủy Lược đồ ký RSA sử dụng thao tác sinh khóa của chính hệ mã RSA. Một hàm băm mật mã (công khai) sẽ được sử dụng trong quá trình Encoding của thao tác ký. Ở đây ta mô tả lược đồ RSA có văn bản kèm theo. Thao tác ký nhận đầu vào là văn bản và khóa bí mật sẽ sinh ra chữ ký là x. Thao tác xác minh, nhận đầu vào là M1x và Ph , sẽ cho ra kết quả là 1 nếu như x đúng là chữ ký trên văn bản M của người có bộ khóa (sh,ph), ngược lại sẽ cho kết quả 0. Thao tác ký RSA-Sign(M) bao gồm các bước như sau: (1) Tính H=h(M): (2) Tính y=0x0001FFFF…FF00\\H; 3) Tính x=f-1(y)=ydmodN, x chính là chữ ký trên văn bản M Ở bước (2) của thao tác ký ta thấy có một số các xâu 0xFF được nối vào mã băm H của M. Mục đích của việc này để tạo ra xâu y có độ dài k bit (là độ dài của N trong chìa khóa). Xâu 0x0001 đầu tiên có ý nghĩa là để cho y luôn nhỏ hơn N . Xâu 00 ngăn cách giữa phần mã băm và phần nối thêm có mục đích giúp ta có thể dễ dàng lấy ra được mã băm H từ xâu y. Ở bước (3) ta giả sử xâu y đã chuyển sang thành số y tương ứng. Thao tác xác min RSA-Verify(M,) Bao gồm các công đoạn sau: (1) Tính H1=h(M); (2) Tính y=f(x)=xe mod N v à lấy ra xâu H từ y là kh bit cuối cùng, với kh là độ dài của mã băm ứng với hàm băm công khai h. (3) Nếu H1=H thì cho ra 1, ngược lại cho ra 0. Theo lược đồ trên, ta thấy mã băm H chỉ là một phần nhỏ của y. Và việc tìm ra xung đột của hàm h sẽ gây ảnh hưởng trực tiếp đến độ an toàn của lược đồ. Cụ thể là, nếu như tìm được hai văn bản M và M’ có cùng mã băm thì chữ ký trên văn bản M cũng chính là chữ ký trên văn bản M'. Hiện nay, đã có những thuật toán tìm ra được một số điểm xung đột của những hàm băm khá phổ biến trước đây (như MD5, SHA-1,...), khiến cho các lược đồ ký nguyên thủy bị “lung lay”. Tuy nhiên, cũng cần ghi nhận rằng các thuật toán tìm xung đột nêu trên chưa cho phép tìm được một văn bản khác với văn bản M cho trước mà có cùng mã băm với M . Như vậy, cho đến nay, việc “mạo chữ ký” của một văn bản cho trước là vẫn chưa thể thực hiện được. Lược đồ ký theo chuẩn PKCS#1 (V2.1) Mô tả lược đồ Thao tác sinh khóa của PSS2000 cũng giống như của PSS96, có một chút sự khác biệt được ở quá trình Encoding. Ta mô tả quá trình Encoding như sau: PSS2000 – Encode (H) bao gồm các bước sau: Như vậy thao tác Encoding ở PSS2000 có sự khác biệt so với phiên bản 96 là ở trong bước (2) hàm băm có nối thêm xâu gồm u chữ số 0 vào trước văn bản được băm. Ở thao tác (4), xâu E được nối vào cuối của xâu kết quả. Xâu E cố định có thể là 0xbc =10111100 hoặc HID\\cc, v ới HID là chỉ số của hàm băm h. Còn bước (3) chẳng qua cách diễn đạt khác của hàm g1, g2 trong phiên bản 96. Lược đồ ký PSS2000-SIGN, cho văn bản M, tính giá trị H=h(M) và tính y=PSS2000-Encode(H), kết quả trả lại là x=f-1(y). Ta có thể nhận thấy có thêm một khác biệt giữa PSS2000 và PSS96, đó là ở PSS2000 có thêm thao tác băm văn bản trước khi đưa vào thao tác encoding. b. Lược đồ ký thu gọn Nhận xét. Lược đồ ký RSA-GenPSS-Reduced như trên chẳng qua là lược đồ ký thông thường như PSS96, chỉ có một vài điểm khác nhau nhỏ như sau: • Thứ nhất: lược đồ trên, độ dài các văn bản đầu vào chỉ cho phép là ; hk • Thứ hai: Một chuỗi gồm u chữ số 0 được nối vào H||r trước khi cho vào băm (bước (2) quá trình GenPSS-Encode) ; • Thứ ba, đó là sự khác nhau giữa hai quá trình Encoding đã nhận xét ở trên, ở sự tham gia của E trong ảnh của quá trình Encoding. Yêu cầu thứ nhất là hiển nhiên do lược đồ thu gọn làm việc trên giá trị băm của hàm băm . Yêu cầu thứ hai được đưa vào nhằm mục đích tạo ra sự tương thích cho lược đồ ký có khôi phục văn bản và cũng góp phần làm giảm xung đột. Bởi lẽ sẽ khó hơn nếu khi tìm kiếm hai văn bản xung đột với nhau khi ta yêu cầu cả hai văn bản đó đều phải có u bit đầu tiên là 0. Sự thay đổi thứ ba có thể góp phần làm tăng thêm độ an toàn cho lược đồ ký. Thật vậy, bài toán tìm đầu vào cho hàm RSA, ta thường gọi là hàm , sao cho đầu ra thỏa mãn điều kiện ràng buộc có bit đầu tiên là 0 và bít sau cùng là cố định, là một bài toán khó hơn so với khi không có ràng buộc này. Như vậy ta có thể thấy RSA-GenPSS-Reduced là lược đồ ký có độ an toàn tương đương (nếu không muốn nói là tốt hơn) PSS96 với độ dài văn bản đầu vào cố định. 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 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ị me cũng nhận giá trị nhỏ (so với 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ã hoá 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, chẳng hạn như PKCS, đã được thiết kế để chuyển đổi bản rõ trước khi mã hóa bằng RSA. Các phương pháp chuyển đổi này bổ sung thêm bít vào M. Các phương pháp chuyển đổi cần được thiết kế cẩn thận để tránh những dạng tấn công phức tạp tận dụng khả năng biết trước được cấu trúc của bản rõ. Phiên bản ban đầu của PKCS dùng một phương pháp đặc ứng (ad-hoc) mà về sau được biết 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 sử dụng các 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 tấn công dạng này. Tiêu chuẩn PKCS còn được 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). TRIỂN KHAI THỰC TẾ Quá trình tạo khóa 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 số nguyên tố cho phép loại bỏ hầu hết các hợp số). Phép kiểm tra số nguyên tố được thực hiện như sau: Các phương pháp thô sơ: Phương pháp đơn giản nhất để kiểm tra một số n có là số nguyên tố không là kiểm tra xem nó có chia hết cho các số m từ 2 đến n − 1 hay không. Nếu n chia hết cho một số m nào đó thì n là hợp số (composite), ngược lại n là số nguyên tố. Kiểm tra theo xác suất: Các phép kiểm tra tính nguyên tố hay dùng nhất là các thuật toán ngẫu nhiên. Giả sử có một mệnh đề Q(p,a) nào đó đúng với mọi số nguyên tố p và một số tự nhiên a <= p. Nếu n là một số tự nhiên lẻ và mệnh đề Q(n,a) đúng với một a<= n được lấy ngẫu nhiên, khi đó a có khả năng là một số nguyên tố. Ta đưa ra một thuật toán, kết luận rằng n là số nguyên tố. Nó là một thuật toán ngẫu nhiên hay thuật toán xác suất. Trong các thuật toán loại này, dùng một kiểm tra ngẫu nhiên không bao giờ kết luận một số nguyên tố là hợp số nhưng có thể kết luận một hợp số là số nguyên tố. Xác suất sai của phép kiểm tra có thể giảm xuống nhờ việc chọn một dãy độc lập các số a; nếu với mỗi số a xác suất để thuật toán kết luận một hợp số là số nguyên tố là nhỏ hơn một nửa thì sau k lần thử độc lập, xác suất sai là nhỏ hơn 2−k, độ tin cậy của thuật toán sẽ tăng lên theo k. Cấu trúc cơ bản của một phép kiểm tra ngẫu nhiên là: Chọn một số ngẫu nhiên a. Kiểm tra một hệ thức nào đó giữa số a và số n đã cho. Nếu hệ thức sai thì chắc chắn n là một hợp số (số a là "bằng chứng" chứng tỏ n là hợp số) và dừng thuật toán. Lặp lại bước 1 cho đến khi đạt được số lần đã định hoặc gặp bước 2. Sau một loạt lần kiểm tra, nếu không tìm được bằng chứng chứng tỏ n là hợp số thì ta kết luận n là số nguyên tố. Các phép kiểm tra tất định Vào năm 2002, Manindra Agrawal, Nitin Saxena và Neeraj Kayal đề xuất một giải thuật tất định kiểm tra tính nguyên tố, là kiểm tra AKS, có khả năng chạy trong O((log n)12). Trên thực tế thuật toán này chạy chậm hơn các phương pháp xác suất. Các phương pháp lý thuyết số Có một vài phương pháp khác trong lý thuyết số để kiểm tra tính nguyên tố như kiểm tra Lucas-Lehmer và kiểm tra Proth. Chúng thường dựa vào việc phân tích n + 1, n − 1, hoặc những số khác. Tuy nhiên các phương pháp này không dừng cho các số tự nhiên n bất kỳ mã chỉ cho các số có một dạng đặc biệt nào đó Kiểm tra Lucas-Lehmer dựa trên tính chất: bậc (multiplicative order) cúa một số a modulo n là n − 1 với n là số nguyên tố và a là căn nguyên thuỷ (primitive root) modulo n. Nếu ta có thể biểu diễn a chỉ theo n, ta có thể thấy n là nguyên tố. 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ũ. Hình 2.1. Cố gắng phá hoại cặp khóa bất đối xứng Tốc độ RSA có tốc độ thực hiện chậm hơn đáng kể so với DES và các thuật toán mã hóa đối xứng khác. Trên thực tế, Bob 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 mã (thông thường 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 vấn đề 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ẻ tấn công (thường ký hiệu là Eve) sẽ bỏ qua RSA và tập trung vào việc đoán khóa đối xứng. Phân phối khóa 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ử Eve có thể gửi cho Bob một khóa bất kỳ và khiến Bob tin rằng đó là khóa (công khai) của Alice. Đồng thời Eve có khả năng đọc được thông tin trao đổi giữa Bob và Alice. Khi đó, Eve sẽ gửi cho Bob khóa công khai của chính mình (mà Bob nghĩ rằng đó là khóa của Alice). Sau đó, Eve đọc tất cả văn bản mã hóa do Bob gửi, giải mã với khóa bí mật của mình, giữ 1 bản copy đồng thời mã hóa bằng khóa công khai của Alice và gửi cho Alice. Về nguyên tắc, cả Bob và Alice đề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 điện tử (digital certificate) hoặc các thành phần của hạ tầng khóa công cộng (public key infrastructure - PKI). Bảo mật Độ an toàn của hệ thống RSA dựa trên 2 vấ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 đó (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 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. Ứng dụng RSA bảo mật trong Internet Banking sử dụng giao thức https ssl RSA được liệt vào một trong các giải thuật mã hóa bất đối xứng được dùng thông dụng nhất cho đến ngày hôm nay (ra đời năm 1977 tại MIT), RSA được đặt tên từ ba nhà khoa học phát minh ra nó: Ron Rivest, Adi Shamir, và Leonard Adleman. Nó được dùng hàng ngày trong các giao dịch thương mại điện tử qua web browser (SSL), PGP, dùng cho digital signature đảm bảo tính toàn vẹn của các thông điệp khi lưu chuyển trên Internet, phân phối & cấp phát các secret keys…Giải thuật trình bày hai khái niệm đó chính là public và private key, tính an toàn và độ phức tạp của giải thuật chính là nhờ phép toán liên quan đến tích số của một cặp số nguyên tố rất cao, tạo ra một số rất rất cao mà hầu như không thể đoán ngược trở lại được hai số nguyên tố ban đầuTrong các kết nối VPN ipsec và ssl, RSA thường được dùng để mã hóa các "session key" (key để mã hóa data dùng cho giải thuật mã hóa đối xứng) giúp cho quá trình trao đổi các secret keys được đơn giản và dễ dàng, bảo đảm được tính xác thực cũng như tính toàn vẹn trong quá trình trao đổi dữ liệuCác giải thuật mã hóa đối xứng (symmetric algorithm) như DES, AES, IDEA, Blowfish... được công khai cách thức và phương pháp mã hóa, như vậy thì độ khó duy nhất để có thể đảm bảo được tính bảo mật của data chỉ có thể nẳm ở chiều dài của secret key, ví dụ DES chỉ có 56 bit key và với các máy PC với CPU cực mạnh như ngày nay thì có thể dò tìm được secret key trong vòng vài giờ nhưng với 3DES thì lại khác nó khó gấp 2^56 lần DES nên bạn cứ yên tâm mà sử dụng, hiện nay AES hầu như được xem là giải thuật mới nhanh và bảo mật hơn đang dần thay thế 3DES cho các kết nối VPN ipsec, bạn có thể chọn chiểu dài key của AES từ 128, 192, cho đến 256-bit . Giải thuật mã hóa đối xứng (symmetric algorithm) có ưu điểm là nhanh hơn mã hóa bất đối xứng rất nhiều (bạn có tin không? 1000 lần nhanh hơn bất đối xứng) nên người ta mới dùng nó để mã hóa các data cần trao đổi với nhau qua các môi trường không an toàn như Internet, nhược điểm của mã hóa đối xứng chính là nó không cho biết được tính xác thực cũng như sự toàn vẹn của data (có thật message đó là của người yêu của mình gởi cho mình không? và nó có bị sửa đổi hay thêm mắm thêm muối gì vào đó hay không?) và nó cũng bất tiện ở chỗ là secret key để mã và giải mã data cần phải được trao đổi riêng qua các phương tiện khác (out of band) chứ không thể gởi đi cùng data đượcMã hóa bất đối xứng ra đời để giúp cho việc trao đổi secret keys được dễ dàng hơn đó các bạn ạ, bạn và người yêu của bạn mỗi người đều có một cặp chìa khóa public và private riêng, cái public thì đưa ra cho mọi người đều biết, chìa còn lại cất kỹ đi để dùng cho NHIỀU việc quan trọng.Bạn viết cho người yêu một lá thư tình sau đó mã hóa nó lại dùng mã hóa đối xứng với một chìa khóa bí mật “secret key” (khác với private key), vì secret key cần được giữ bí mật nên bạn mới lấy public key của người yêu mã hóa nó lại, như vậy bây giở cả hai nội dung lá thư và secret key dùng để đọc lá thư đó cũng đã được mã hóa rồi, cả hai phần này sẽ được gởi đến người yêu của bạn. Sau khi nhận được thông tin trên, người yêu của bạn trước tiên sẽ dùng private key của mỉnh để giải mã ra nội dung của secret key trước, sau khi có secret key rồi cô ta mới dùng nó để giải mã nội dung bức thư tình của người yêu, quá trình như trên được tiến hành tương tự như vậy khi cô ta muốn gởi ngược lại cho bạn một lá thư tình khácDo lấy cái có tốc độ nhanh để mã và giải mã big data và cái tốt độ chậm hơn nhiều để mã và giải mã very small data (secret key) nên cuối cùng tổng cộng quá trình mã và giải mã cho toàn bộ data cũng tương đối nhanh (chỉ chậm một chút xíu lúc thiết lập ban đầu thôi)Private key không chỉ để dùng để giải mã data mà nó còn được dùng để ký (mã hóa) các message digest dùng để bảo đảm tính toàn vẹn của dữ liệu.Trong các giao dịch thương mại điện tử thì việc bảo đảm tính toàn vẹn của data được xem là vô cùng quan trọng (Ví dụ xếp của bạn gởi email nói rằng bạn phải trả cho khách hàng USD 50, nhưng có ai đó đã chặn được message sửa lại nội dung là USD 5000 và gởi cho bạn).Trước tiên chúng ta hay thử đi tìm hiểu cơ chế one-way-hash một chút nhé, với các data có độ dài khác nhau bất kỳ khi được cho qua một thuật toán one-way-hash thì sẽ được "băm" ra thành các chuỗi có chiều dài khá nhỏ và cố định như nhau được gọi là message digest (ví dụ: b90c9054849c187aa681464bb62b9a95, 16cb26421451cc406f5bc111b969c38f) và thuật toán này bảo đảm rằng nếu nội dung data bị thay đổi (dù chỉ là một bit) thì kết quả của message digest cũng sẽ thay đổi, các giải thuật hash dùng 128-bit key: MD2, MD4, MD5, 160 bit-key: SHA, SHA-1... đây chính là yếu tố then chốt để kiểm tra tính toàn vẹn của dữ liệu, và bạn có thắc mắc là tại sao lại phải cần có message digest có chiều dài khá nhỏ như vậy không?Giả sử xếp của bạn gởi cho bạn một message email với nội dung như ví dụ ở trên, nội dung của message sẽ được cho qua một thuật toán one-way-hash MD5 chẳng hạn và kết quả là ta có một message digest tương ứng, sau đó xếp bạn sẽ lấy PRIVATE key của mình để ký (mã hóa) vào message digest đó để tạo thành một cái gọi là DIGITAL SIGNATURE, và chữ ký điện tử này sẽ được gởi kèm theo message ban đầu đến bạn.Khi nhận được email từ xếp thì bạn sẽ lấy PUBLIC key của xếp để giải mã DIGITAL SIGNATURE và có được message digest của xếp, so sánh kết quả này và giá trị tính toán MD5 lại nội dung message ngay tại máy của bạn nếu chúng giống nhau thì có nghĩa là message không bị thay đổi (đơn giản quá phải không các bạn) vì chỉ có xếp của bạn là người giữ PRIVATE key dùng để "ký", và nếu message digest mà có chiều dài quá lớn thì thời gian để mã và giải mã các message digest này rất lâu phải không (1000 lần lâu hơn symmetric algorithm) và cũng tốn nhiều bandwidth để gởi thêm cái "chữ ký" này đi nữa.Cetificate Authority (CA)Một tổ chức tin cậy phát hành các chứng thực điện tử (electronic certificate) cho các đối tác cần trao đổi thông tin, giao dịch với nhau thông qua các phương tiện giao tiếp điện tử như: Internet, Smart card, Security card…CA cung cấp và quản lý các electronic certificates cho các đối tác như: kiểm tra đối tác đăng ký (registration) cấp phát (issue), thu hồi certificate (revocation)CA được cấu trúc theo mô hình phân cấp X.500 và cho phép các phân cấp con có thể tiếp tục chứng thực cho các đối tác khác (intermediate). Các thông tin trong một certificate bao gồm gồm public key của site's server, tên của đối tác đăng ký, Algorithm ID được dùng để ký lên certificate, ngày hết hạn certificate, tên của tổ chức CA cấp phát…Các trusted CA bảo đảm được đầy đủ ba yếu tố cho một đối tác khi sử dụng trusted certificates đó là: CONFIDENTIALITY, INTEGRITY, và AUTHENTICATIONCONFIDENTIALITY: Không ai có thể đọc được nội dung data khi đang giao dịchINTEGRITY: Bảo đảm được tính toàn vẹn của data, không ai có thể sửa đổi lại dataAUTHENTICATION: Bảo đảm được tính xác thực của đối tác đăng ký, không ai có thể giả mạo được Ứng dụng RSA trong Internet banking dùng giao thức https sslRSA được sử dụng rất nhiều trong các giao dịch Internet banking hiện nay:Chúng ta thử tìm hiểu hoạt động của một kết nối https (SSL) một chút nhé:1. Web browser kết nối với web server và yêu cầu một kết nối an toàn và bảo mật2. Web server trả về cho web browser site's certificate3. Web browser kiểm tra các thông tin trong site's certificate xem có trust được hay không (khi certificate không được trust ta sẽ thấy xuất hiện một warning dialogue, và nếu muốn cố tự mình cho rằng nó có thể trust được thì click Yes để kết nối, một khi thấy warning dialogue hiện ra mà vẫn cố chấp nhận giao dịch thì web site mà bạn đang kết nối có thể là web site giả mạo)4. Web browser lúc này mới tạo ra một session key sau đó dùng server's public key để mã hóa (asymmetric) và chuyển session key đã được encrypt này tới web server5. Web server dùng private key của nó để giải mã (asymmetric) và lấy được session key dùng để mã hóa data (symmetric) giửa web server và web browserChúng ta hãy phân tích bước thứ ba kỹ hơn một chút:Như ta đã biết electronic certificate chứa các thông tin bao gồm public key của site's server, tên của đối tác đăng ký, Algorithm ID được dùng để ký lên certificate, ngày hết hạn certificate, tên của tổ chức CA cấp phát…và quan trọng nhất là certificate đó phải được "ký" bởi các CA mà các thực thể (entities) phải hiểu (trust) được CA đó, mà các entities trong trường hợp này ở đây là ai? đó chính là các WEB BROWSER dùng để kết nối giao dịch chứ không phải con người sử dụng web browser đang tiến hành giao dịch, để tránh các tình trạng giả mạo e-banking website bằng cách tạo ra một web site giả có nội dung tương tự giống như web site thật nhằm mục đích dụ users đánh vào các thông tin đăng nhập như username & password, thông tin tài khoản... sau đó xuất ra cho khác hàng những câu thông báo đại loại như server busy, hãy vui lòng đăng nhập lại vào khi khác…để đánh lừa khách hàngBiện pháp dễ dàng và hiệu quả nhất để chống được trò giả mạo này là web browser mặc định (default) phải trust các certificates do các trusted CA ban hành, vì các thông tin như validity dates, name of certificate issuer trên electronic certificate đều có thể giả mạo được ngoại trừ chữ ký lên các certificates, do các trusted CA đó đã dùng RSA Private Key của mình để "ký" (mã hóa) nên không ai có thể giả mạo được.Đa số các loại web browser ngày nay đều có tích hợp sẵn các certificate của các trusted root CA như Verisign, Thawte, Entrust… khi xây dựng các websites mà muốn có được các certificate của các hãng này ký thì ta phải trả tiền, ví dụ như khi sử dụng certificate cho mã hóa ssl 128-bit do Verisign ký thì chi phí một năm vào khoảng USD 900.Đối với các giao dịch Internet banking sử dụng https (ssl) mà không dùng các trusted CA thì sẽ gặp rất nhiều khó khăn trong việc phân phối site’s certificate cho khách hàng để nhúng vào PC của họ (vì khi đó site’s certificate phải được phân phối an toàn đến khách hàng bằng hình thức không thông qua Internet - out of band) và dịch vụ đó sẽ khó được sử dụng rộng rãi ở mọi nơi do gây khó khăn và phiền phức cho khách hàng trong vấn đề import site’s certificate.Giá trị quyết định tính tin cậy (trusted) của mỗi CA sẽ phụ thuộc vào tổng số lượng các loại web browser được cài sẵn các root trusted certificates, khi các CA nào mà có đến 99% các loại web browser hiểu được mình một cách mặc định (trusted by default) thì các CA đó được xếp vào loại High-Assurance SSL Certificate như Verisign, Thawte, Entrust, Baltimore, Comodo… Tấn công Tấn công dựa trên thời gian 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, Alice đầ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ã. Tấn công lựa chọn thích nghi bản mã Năm 1981, Daniel Bleichenbacher mô tả dạng tấn công lựa chọn thích nghi bản mã (adaptive chosen ciphertext attack) đầu tiên có thể thực hiện trên thực tế đối 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 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 của PKCS #1, Bleichenbacher có thể thực hiện một tấ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, 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) được khuyến cáo sử dụng. Đồng thời phòng nghiên cứu của RSA cũng đưa ra phiên bản mới của PKCS #1 có khả năng chống lại dạng tấn công nói trên. KẾT LUẬN Do thời gian có hạn, nên chúng tôi chưa thể đi sâu phân tích các khía cạnh ứng dụng của RSA. Tuy nhiên có thể nói, tài liệu đã nói lên được những phần khái quát nhất và đem lại 1 cái nhìn tổng thể về RSA cho người đọc. Tài liệu đã giải thích được cách thức, quá trình mã hóa RSA cũng các vấn đề thực tế khi triển khai như tốc độ và bảo mật. Nếu có thêm thời gian, chúng tôi hi vọng sẽ hoàn thiện được tài liệu này một cách đầy đủ hơn. Trong quá trình làm tài liệu, chúng tôi rất cảm ơn thầy Nguyễn Việt Hùng đã hưỡng dẫn chúng tôi biết được các quy trình và cách thức làm 1 tài liệu khoa học. Chúng tôi chân thành cảm ơn! TÀI LIỆU THAM KHẢO Cetin Kaya Koc, “RSA hardware Implementation“, RSA Laboratories, RSA Data Security Inc, 1995 Cetin Kaya Koc, “High-speed RSA Implementation“, RSA Laboratories, RSA Data Security Inc, 1994 James Henry Carmouche, “IPsec Virtual Private Network Fundamentals’, Cisco Press, July 19 2006