Đồ án Tìm hiểu một số thuật toán mã hóa dữ liệu và ứng dụng

PHƯƠNG PHÁP Mà HÓA CỔ ĐIỂN 2.1 Hệ mã hóa thay thế 2.1.1 Hệ mã hóa CEASAR Hệ mã hóa CEASAR là một ví dụ điển hình cho hệ mã hóa thay thế. Nó làm việc trong bảng chữ cái tiếng Anh 26 ký tự [1, 7]. Ceasar sử dụng các số nguyên thay cho các ký tự, đánh số các ký tự trong bảng chử cái theo thứ tự bảng sau. Các phép toán số học được thực hiên trên Modul 26 (có nghĩa là 26 tương ứng với 0, 27 tương ứng với 1, 28 tương ứng với 2,…, 79 = 26x3 + 1 tức 79 tương ứng với 1). Hệ CAESAR sử dụng thuật toán mã hóa Ek, trong đó mỗi ký tự được thay thế bởi một ký tự khác được xác định bằng cách dịch ký tự cần mã hóa sang phải k bước theo modul 26. Ek(a) = (a + k) MOD 26. Với a là một ký tự, 0 £ k £ 26, MOD là phép chia lấy phần dư. Thuật toán giải mã tương ứng Dk là lùi lại k bước trong bảng chữ cái theo modul 26. Dk(a) = (a - k) MOD 26 Không gian khóa của hệ CEASAR bao gồm 26 số: 0, 1, 2, …, 25. Ví dụ: Với k = 3, A được thay bằng D, B được thay bằng E,…, W được thay bằng Z,…, Y được thay bằng B và Z được thay bằng C. Ta có: Bảng chữ cái gốc. Bảng chữ cái dùng để mã hóa. Trong trường hợp này bản rõ “DAI HOC VINH” được mã hóa thành “GDL KRF YLQK”, (Chú ý: Các ký tự trống trong bảng mã được bỏ đi để đảm bảo tính an toàn). Thêm một vài ví dụ minh họa: E25(IBM) = HAL, E6(MUPiD) = SAVOJ. E3(HELP) = KHOS, E1(HOME) = IPNF. Hệ CEASAR là hệ mã hóa cũ và không an toàn vì không gian khóa của nó rất nhỏ, do đó có thể thám mã theo phương pháp vét cạn. Khóa giải mã có thể tính ngay ra được từ khóa mã hóa. Do chỉ có 26 khóa nên ta có thể thử lần lượt các khóa cho đến khi tìm được khóa đúng. Hệ mã hóa VIGENERE Hệ mã hóa này được đặt theo tên của một nhà mật mã người Pháp Blaise De Vigenere (1523 – 1596) [1, 7]. Vinegere cũng giống như Caesar, nhưng ở đây khóa được thay đổi theo từng bước. Hình vuông VIGENERE được sử dụng để mã hóa và giải mã. A B C D E F G H I J K L M N O P Q R S T U V W X Y Z B C D E F G H I J K L M N O P Q R S T U V W X Y Z A C D E F G H I J K L M N O P Q R S T U V W X Y Z A B D E F G H I J K L M N O P Q R S T U V W X Y Z A B C E F G H I J K L M N O P Q R S T U V W X Y Z A B C D F G H I J K L M N O P Q R S T U V W X Y Z A B C D E G H I J K L M N O P Q R S T U V W X Y Z A B C D E F H I J K L M N O P Q R S T U V W X Y Z A B C D E F G I J K L M N O P Q R S T U V W X Y Z A B C D E F G H J K L M N O P Q R S T U V W X Y Z A B C D E F G H I K L M N O P Q R S T U V W X Y Z A B C D E F G H I J L M N O P Q R S T U V W X Y Z A B C D E F G H I J K M N O P Q R S T U V W X Y Z A B C D E F G H I J K L N O P Q R S T U V W X Y Z A B C D E F G H I J K L M O P Q R S T U V W X Y Z A B C D E F G H I J K L M N P Q R S T U V W X Y Z A B C D E F G H I J K L M N O Q R S T U V W X Y Z A B C D E F G H I J K L M N O P R S T U V W X Y Z A B C D E F G H I J K L M N O P Q S T U V W X Y Z A B C D E F G H I J K L M N O P Q R T U V W X Y Z A B C D E F G H I J K L M N O P Q R S U V W X Y Z A B C D E F G H I J K L M N O P Q R S T V W X Y Z A B C D E F G H I J K L M N O P Q R S T U W X Y Z A B C D E F G H I J K L M N O P Q R S T U V X Y Z A B C D E F G H I J K L M N O P Q R S T U V W Y Z A B C D E F G H I J K L M N O P Q R S T U V W X Z A B C D E F G H I J K L M N O P Q R S T U V W X Y Hình 2.1: Hình vuông Vigenere Mỗi cột của hình vuông Vigenere có thể xem như là một hệ CEASAR, với các khóa: 0, 1, 2,...., 25. Để mã hóa thì bản rõ được đọc từ các hàng và khóa được đọc từ các cột. Ví dụ: Mã hóa bản “DAI HOC VINH” với từ khóa “ KHOA KINH TE”. Đầu tiên ta tìm điểm giao của hàng D cột K ta được N, tiếp tục ta tìm điểm giao của hàng A cột H ta được H. Cứ như vậy ta được bản mã là “ NHW HYK IPGL” . Ta sẽ thu được bản mã tưng tự nếu ta đọc bản rõ tưng ứng với cột và khóa đọc tưng ứng với hàng. Muốn giải mã thông tin vừa mã hóa trên ta thực hiện bằng cách, ta nhìn vào hàng nào chứa N trong cột K, ta tìm được chữ D, tương tự nhìn vào hàng nào chứa H trong cột H, ta tìm được chữ A. Cứ như vậy ta sẽ tìm được bản rõ là “DAI HOC VINH”. Trong ví dụ trên thì độ dài bản rõ bằng độ dài khóa. Nhưng trong thực tế độ dài bản rõ thường dài hơn rất nhiều so với khóa. Như vậy để mã hóa hay giải mã thì ta phải áp dụng từ khóa một cách tuần hoàn. Nghĩa là từ khóa được lặp đi lặp lại nhiều lần sao cho các ký hiệu trong bản rõ phải được đọc hết. Ta thấy rằng trong hệ mã hóa VIGENERE, với khóa có độ dài d thì sẽ có 26d khóa hợp lệ. Vì vậy chỉ cần với giá trị d nhỏ thì phương pháp thám mã vét cạn cũng đòi hỏi khá nhiều thời gian. Hệ mã hóa hoán vị Hệ mã hóa hoán vị hay còn gọi là hệ mã hóa đổi chỗ. Là hệ mã hóa mà các ký tự của bản rõ vẫn được giữ nguyên, nhưng thứ tự của chúng được đổi chỗ vòng quanh [1, 7]. Phương pháp này có các kỹ thuật mã hóa sau. 2.2.1 Đảo ngược toàn bộ bản rõ Nghĩa là bản gốc được viết theo thứ tự ngược lại từ sau ra trước, để tạo bản mã. Đây là phương pháp mã hóa đơn giản nhất vì vậy không đảm bảo an toàn. Ví dụ: PlainText SECURE EMAIL Bản mã: LIAMEERUCES 2.2.2 Mã hóa theo mẫu hình học Bản gốc được sắp xếp lại theo một mẫu hình học nào đó, thường là một mảng hoặc ma trận hai chiều. Ví dụ: Bản rõ “KHOA CONG NGHE THONG TIN” được viết theo ma trận 4x5 như sau: Nếu lấy các ký tự ra theo số thứ tự cột 3, 1, 4, 2, 5 thì ta thu được bản mã “OGTTKOHNANHIHNEGCGON”. 2.2.3 Đổi chỗ cột Đầu tiên biểu diễn các ký tự trong ban rõ thành dạng hình chữ nhật theo cột, sau đó các cột được sắp xếp lại và các chữ cái được lấy ra theo hàng ngang. Ví dụ: Bản rõ là “KHOA CONG NGHE THONG TIN” được viết dưới dạng ma trận 4x5 theo cột như sau: Vì có 5 cột nên ta có thể sắp xếp lại theo 5!=120 cách khác nhau. Để tăng độ an toàn có thể chọn một trong các cách sắp xếp lại đó. Nếu ta chuyển vị trí các cột theo các cột theo thứ tự 3, 5, 2, 4, 1. Rồi lấy các ký tự ra theo hàng ngang ta sẽ được bản mã là: “NGCTKGTOHHHINOOENGNA”. Lưu ý: Các ký tự cách trống được bỏ đi. Hoán vị các ký tự của bản rõ theo chu kì cố định Nếu hàm f là một hoán vị của một khối gồm d ký tự thì khóa mã hóa được biểu diễn bởi K(d, f). Do vậy, bản rõ: M=m1m2...mdmd+1...m2d. Với mi là các ký tự, và bản mã sẽ được mã hóa thành: Ek(M)= mf(1)mf(2)…mf(d)md+f(1)…md+f(d). Trong đó mf(1)mf(2)…mf(d) là một hoán vị của m1m2...md. Ví dụ: Mã hóa bản rõ “BAO MAT” chọn d=6 và f hoán vị dãy i= 123456 thành f(i)=351462. Theo bảng trên ta thấy ký tự đầu sau khi hoán vị chuyển đến vị trí thứ 3, ký tự thứ 2 chuyển tới vị trí thứ 5, ký tự thứ 3 chuyển tới vị trí thứ 1,… Như vậy sau khi mã hóa ta thu được bản mã là “OABMTA”. Nếu kích thước bản rõ lớn hơn nhiều so với d thì ta sẽ phải chia bản rõ thành các khối d ký tự và tiến hành mã hóa theo từng khối. Ví dụ: Bản rõ “KHOA CONG NGHE THONG TIN”, giả sử d = 6, và f hoán vị dãy i = 12345 thành f(i) = 35142. Ta thu được bản mã “OCKAHGGONNTOHHETNIG” CHƯƠNG 3: MỘT SỐ THUẬT TOÁN Mà HÓA HIỆN ĐẠI 3.1 Thuật toán mã hóa DES 3.1.1 Lịch sử ra đời Khoảng những năm 1970, tiến sĩ Horst Feistel đã đặt nền móng đầu tiên cho chuẩn mã hóa DES với phương pháp mã hóa Feistel Cipher. Vào năm 1976 Cơ quan Bảo mật quốc gia Hoa Kỳ (NSA) đã công nhận DES dựa trên phương pháp Feistel là chuẩn mã hóa dữ liệu. Kích thước khóa ban đầu của DES là 128 bit nhưng tại bản công bố FIPS kích thước được rút xuống 56 bit để tăng tốc độ xử lý và đưa ra các tiêu chuẩn thiết kế một chuẩn mã hóa dữ liệu [4, 6]. Nội dung phương pháp mã hóa DES. DES thực hiện mã hóa dữ liệu qua 16 vòng lặp mã hóa, mỗi vòng sử dụng một khóa chu kỳ 48 bit được tạo ra từ khóa ban đầu có độ dài 56 bit. DES sử dụng 8 bảng hằng số S-box để thao tác. 3.1.2 Mô tả thuật toán DES 3.1.2.1 Sơ đồ tổng quát Phương pháp DES mã hóa khối thông tin x có độ dài 64 bit với khóa k có độ dài 56 bit thành khối y có độ dài 64 bit. Nền tảng để xây dựng khối của DES là sự kết hợp đơn giản của các kỹ thuật thay thế và hoán vị bản rõ dựa trên khóa, đó là vòng lặp. DES sử dụng 16 vòng lặp áp dụng cùng một kiểu kết hợp các kỹ thuật trên khối bản rõ. Thuật toán chỉ sử dụng các phép toán số học và logic thông thường trên các số 16 bit, vì vậy nó dễ dàng thực hiện vào những năm 1970 trong điều kiện về công nghệ phần cứng lúc bấy giờ. Sơ đồ tổng quát : K16 L15=R14 R15=L14Ŧ(R14,K15) Plaintext IP L0 R0 L1=R0 R1=L0Ŧ(R0,K1) ¦ L2=R1 R2=L1Ŧ(R1,K2) ¦ R16=L15Ŧ(R15,K16) L16=R15 ¦ K1 K2 Ciphertext IP -1 Hình 3.1: Sơ đồ tổng quát mã hóa DES Quá trình có 16 vòng thực hiện giống nhau trong quá trình xử lý. Ngoài ra có hai lần hoán vị đầu IP và cuối IP-1, hai hoán vị này được sử dụng với mục đích đưa thông tin vào và lấy thông tin ra. Muốn vào vòng mã hóa thì khối thông tin x ban đầu 64 bit được chia làm hai khối, mỗi khối 32 bit. Hàm f làm biến đổi một nữa của khối đang xử lý với một khóa con tương ứng với vòng mã hóa. Trong đầu ra của hàm có hàm f được kết hợp với nửa khối còn lại bằng phép toán XOR, và hai phần được trao đổi để xử lý trong chu trình kế tiếp. Cứ thực hiện các vòng như vậy cho tới vòng cuối cùng thì hai phần không bị tráo đổi nữa, chính vì điều này mà quá trình mã hóa và giải mã là giống nhau. 3.1.2.2 Tạo khóa Quá trình mã hóa được thực hiện 16 vòng, mỗi vòng cần một khóa. Như vậy từ khóa ban đầu tạo ra 16 khóa con cho 16 vòng lặp tương ứng. Sơ đồ quá trình tạo khóa. Hình 3.2: Sơ đồ tạo khóa Theo sơ đồ ta thấy đầu tiên khóa K có độ dài 64 bit, sau đó được giảm xuống 56 bit bằng cách loại bỏ 8 bit chẵn lẻ. Sự loại bỏ được thực hiên khi đi qua PC1. Bảng PC1 : Như vậy các bit ở vị trí 8, 16, 24, 32, 40, 48, 56, 64 bị loại bỏ. 56 bit thu được chia làm hai phần, mỗi phần 28 bit, các phần được xử lý độc lập nhau. Các phần này được dịch 1 hay 2 bit là phụ thuộc vào vòng đó. Số bit dịch được cho trong bảng sau. Sau khi dịch bit, 56 bit này được chọn ra 48 bit. Bởi vì sự thực hiện đổi chỗ thứ tự các bit như là sự lựa chọn một tập con các bit, nó còn được gọi là hoán vị nén hoặc hoán vị lựa chọn. Sự thực hiện này cung cấp một tập hợp các bit cùng cỡ với đầu ra của hoán vị mở rộng. Bảng PC2 định nghĩa hoán vị nén (cũng gọi là hoán vị lựa chọn). Ví dụ, bit ở vị trí 33 của khóa được dịch chuyển tới vị trí 35 của đầu ra và bit ở vị trí 8 của khóa bị bỏ qua. Bảng PC2( hoán vị nén). Như vậy sau khi đi qua PC2 còn lại 48 bit, 48 bit này sẽ được sử dụng làm khóa K1 để sử dụng trong vòng mã hóa. Hai phần, mỗi phần 28 bit sau khi được dịch bit ở lần thứ nhất, tiếp tục dịch bit ở lần thứ 2 và qua bảng PC2 để hoán vị nén 48 bit và làm K2. Quá trình cứ tiếp tục như vậy ta thu được 16 khóa Ki (i=1…16). 3.1.2.3 Hoán vị khởi đầu Mục đích của hoán vị khởi đầu là đổi chỗ các bit của khối dữ liệu vào thông qua bảng IP. Nó không ảnh hưởng đến sự an toàn của DES. Với khối dữ liêu vào x 64 bit cho trước, một xâu bit x0 sẽ được xây dựng bằng cách hoán vị các bit của x theo phép hoán vị cố định ban đầu IP. Ta viết x0=IP(x)=L0R0 trong đó L0 gồm 32 bit đầu và R0 gồm 32 bit cuối. Hình 3.3: Biểu diễn dãy 64 bit x chia thành 2 thành phần L0,R0 Bảng hoán vị khởi đầu IP. 3.1.2.4 Mã hóa chi tiết một vòng Quá trình xử lý các vòng là giống nhau, ta xét quá trình xử lý của một vòng i với 1£ i £ 16. Hình 3.4: Sơ đồ chi tiết một vòng Ta thấy: Li = Ri-1 Ri =Li-1 Å f(Ri-1,Ki) Hàm f có hai tham số là Ri-1 và Ki. Được thực hiện theo sơ đồ sau : Hình 3.5: Sơ đồ hoạt động của hàm f Ri-1 được mở rộng từ 32 bit thành 48 bit nhờ sự thay đổi thứ tự của các bit bằng cách lặp lại một số bit nào đó, nó được hiểu như là một sự hoán vị mở rộng. Để xác định ở đầu vào có 32 bit, bit nào được lặp lại và xuất hiện tại vị trí nào của đầu ra 48 bit người ta xác định như sau: Đầu vào có 32 bit chia làm 8 bộ, mỗi bộ có 4 bit. Bit đầu tiên và bit cuối cùng của mỗi bộ tương ứng với 2 bit của khối dữ liệu ra, trong khi bit thứ 2 và bit thứ 3 của mỗi bộ tương ứng với một bit ở khối dữ liệu ra. Ví dụ, bit ở vị trí thứ 3 của khối dữ liệu vào được chuyển tới vị trí thứ 4 trong khối dữ liệu ra, bit thứ 8 trong khối dữ liệu vào thì được chuyển tới vị trí 11 và 13 trong khối dữ liệu ra. Hộp E. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 48 32 Hình 3.6: Hoán vị mở rộng Như vậy 16 bit của Ri được hoán vị hai lần. Mặc dù khối dữ liệu ra rộng hơn khối dữ liệu vào, nhưng một khối dữ liệu vào chỉ có duy nhất một khối dữ liệu ra. Như vậy E(Ri-1) là một dãy 48 bit. Thực hiện phép toán XOR cho dãy bit E(Ri-1) với khóa Ki. Ta thu được dãy 48 bit B. Biểu diễn B thành từng nhóm 6 bit B = B1B2B3B4B5B6B7B8. Sử dụng 8 hộp S = S1, S2, S3, S4, S5, S6, S7, S8. Mỗi hộp Si có kích thước 4 x 16. Mỗi dòng của hộp nhận đủ giá trí từ 0à15. Xét dãy 6 bit Bi=b1b2b3b4b5b6. Si(Bi) được xác định bằng giá trị của phần tử tại dòng m cột n. Trong đó m, n được xác định bằng cách. Giá trị m được xác định bằng bit b1 và b6 được kết hợp thành một số 2 bit nhận giá trị từ 0 đến 3, tương ứng với một hàng trong bảng. Giá trị n được xác định bằng cách ghép bit b2b3b4b5 thành một số 4 bit nhận giá trị từ 0 đến 15, tương ứng với cột trong bảng. Ví dụ: B2=111010 ta có m= b1b6 = 10= 2 ; n = b2b3b4b5= 1101= 13. Phần tử ở vị trí hàng 2 cột 13 là 6, sang giá trị nhị phân là 0110. Như vậy 0110 thay cho 111010. Như vậy tập dãy 4 bit thu được C ta có dãy C = C1, C2, C3, C4, C5, C6, C7, C8. Dãy 32 bit thu được bằng cách hoán vị hoán vị C theo quy luật P nhất định. Đây là kết quả của hàm f(Ri-1,Ki) XOR với Li-1 tạo thành khối Ri với 32 bit. Các hộp S. Hộp S thứ 1. Hộp S thứ 2. Hộp S thứ 3. Hộp S thứ 4. Hộp S thứ 5. Hộp S thứ 6. Hộp S thứ 7. Hộp S thứ 8. Hộp hoán vị P chứa khối dữ liệu 32 bit ra của hộp thay thế S được hoán vị tiếp trong hộp P. Sự hoán vị này ánh xạ mỗi bit dữ liệu vào tới một vị trí trong khối dữ liệu ra, không có bit nào được sử dụng hai lần và cũng không bit nào bị bỏ qua. Nó được gọi là hoán vị trực tiếp. Hộp hoán vị P. 3.1.2.5 Hoán vị cuối cùng Hoán vị cuối cùng là nghịch đảo của hoán vị khởi đầu. Được mô tả theo bảng IP-1. Tại vòng cuối cùng của mã hóa DES thì nửa trái và nửa phải không được tráo đổi cho nhau nữa. Khi đó R16L16 được sử dụng như khối dữ liệu ra của hoán vị cuối cùng. Hoán vị cuối cùng IP-1. 3.1.3 Giải mã DES Quá trình giải mã hoàn toàn tương tự với quá trình mã hóa. Nhưng quá trình mã hóa thực hiện hoán vị IP trước hoán vị IP-1, còn giải mã thì thực hiện hoán vị IP-1 trước hoán vị IP. Các khóa phải được thực hiện trái ngược nhau. Tức là nếu mã hóa, khóa thực hiện cho các vòng lần lượt là K1, K2,…, K16, thì giải mã là K16, K15,…, K2, K1. Ngoài ra, sau mỗi chu trình tạo khóa các bit được dịch phải thay vì dịch trái như khi mã hóa, và số bit để dịch được lấy theo chiều ngược lại. 3.1.4 Độ an toàn của thuật toán Đã có rất nhiều nghiên cứu về độ dài của khóa, số vòng lặp và thiết kế hộp S. Trong phương pháp mã hóa này chỉ có hộp S là khó hiểu. Mọi tính toán trong DES đều là tuyến tính ngoại trừ hộp S, các hộp S chứa các thành phần phi tuyến tính của hệ là yếu tố quan trọng nhất đối với sự an toàn của hệ thống. Tính bảo mật của một hệ mã hóa đối xứng phụ thuộc chủ yếu vào hai yếu tố: Độ phức tạp của thuật toán và độ dài của khóa. Giã sử phương pháp này an toàn về độ phức tạp của thuật toán. Có nghĩa là không có phương pháp nào để phá vỡ hệ thống mật mã hơn là cố gắng thử mọi khóa có thể, còn gọi là phương pháp vét cạn. Nếu khóa có độ dài 8 bit thì sẽ có 28= 256 khóa. Như vậy muốn tìm ra khóa thì mất nhiều nhất là 256 lần thử khóa. Thuật toán DES sử dụng khóa có độ dài 56 bit nên có 256 khóa. Đây là con số rất lớn do đó việc tìm kiếm khóa là rất khó khăn. Giả sử có một máy tính có thể thử một triệu khóa trong một giây, thì nó sẽ cần hơn 2000 năm để thử hết khóa. Các thành tựu gần đây chỉ ra rằng thời gian cần thiết để giải một trang mã DES mà không biết khoá là: Sau một vài tháng trên Internet trong năm 1997; một vài ngày trên thiết bị phần cứng tăng cường trong năm 1998; sau 22 giờ nếu kết hợp các biện pháp trong năm 1999. Như vậy vẫn có thể đoán được bản rõ sau một khoảng thời nhất định, nếu có nguồn lực máy tính mạnh. Chính vì vậy bây giờ người ta đã xét một vài biến thể của DES nhằm nâng cao sức mạnh cho DES. Thuật toán mã hóa RSA 2.2.1 Khái quát về RSA 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ả [2, 3]. Trước đó, vào năm 1973, Clifford Cocks, một nhà toán học người Anh, đã 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. 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ý. 3.2.2 Mô tả về thuật toán Thuật toán RSA có hai khóa: Khóa công khai (hay khóa công cộng) và khóa bí mật (hay khóa cá nhân). Mỗi khóa là những số cố định 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 cá nhân (bí mật) mới có thể giải mã được. Ta có thể mô phỏng trực quan một hệ mật mã khoá công khai như sau: Nam muốn gửi cho Nga một thông tin mật mà Nam muốn duy nhất Nga có thể đọc được. Để làm được điều này, Nga gửi cho Nam một chiếc hộp có khóa đã mở sẵn và giữ lại chìa khóa. Nam nhận chiếc hộp, cho vào đó một tờ giấy viết thư bình thường và khóa lại (như loại khoá thông thường chỉ cần sập chốt lại, sau khi sập chốt khóa ngay cả Nam cũng không thể mở lại được. Không đọc lại hay sửa thông tin trong thư được nữa). Sau đó Nam gửi chiếc hộp lại cho Nga. Nga 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, chiếc chìa khóa chính là khóa bí mật. 3.2.2.1 Tạo khóa Giả sử Nga và Nam 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, Nga đầu tiên 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: Chọn 2 số nguyên tố lớn p và q với p≠q, lựa chọn ngẫu nhiên và độc lập. 2. Tính: n= p*q. Tính: giá trị hàm số Ơle f(n)= (p-1)*(q-1). Chọn một số tự nhiên e sao cho 1< e< f(n) và là số nguyên tố cùng nhau với f(n) . Tính: d sao cho (d*e -1)*k = f(n), k là số nguyên dương. Hay d=e-1 mod f(n) (hoặc tìm số tự nhiên x sao cho d= cũng là số tự nhiên). Khóa công khai bao gồm: n, môđun. 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. d, số mũ bí mật (cũng gọi là số mũ giải mã). Nga gửi khóa công khai cho Nam, 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. 3.2.2.2 Mã hóa Giả sử Nam muốn gửi đoạn thông tin M cho Nga. Đầu tiên Nam 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 sau: Lúc này Nam có m và biết n cũng như e do Nga gửi. Nam 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 Nam gửi c cho Nga. 3.2.2.3 Giải mã Nga nhận c từ Nam và biết khóa bí mật d. Nga có thể tìm được m từ c theo công thức sau: Biết m, Nga tìm lại M theo phương pháp đã thỏa thuận trước. 3.2.2.4 Sơ đồ thuật toán Hình 3.7: Sơ đồ thuật toán RSA 3.2.2.5 Ví dụ minh họa. Sau đây là một ví dụ với những số cụ thể. Ở đây 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: p = 5 - số nguyên tố thứ nhất (giữ bí mật hoặc hủy sau khi tạo khóa) q = 7 - số nguyên tố thứ hai (giữ bí mật hoặc hủy sau khi tạo khóa) N = pq = 35 - môđun (công bố công khai) f(n)=(p-1)(q-1)=24. - Giá trị hàm số Ơle e = 5 - số mũ công khai (chọn e thoả điều kiện 1< e< n) d = 29 - số mũ bí mật (tìm d sao cho ed -1 chia hết cho f(n)) Như vậy ta có cặp khóa: Public Key = (e,n) = (5,35) Private Key = (d,n) = (29,35) Áp dụng để mã hoá chuỗi : SECURE Trong bảng chữ cái, có tất cả 26 ký tự, các ký tự ứng với một con số. Do đó, ta có bảng sau: Mã hóa chuổi SECURE. Nếu tại đây, dữ liệu trên đường chuyển đến người nhận bị một người khác bắt được, người đó sẽ không biết được nội dung muốn nói điều gì, mà chỉ nhận được đó chỉ là những con số, không nói lên được điều gì. Nếu muốn đọc được nội dung, người đó phải có Private Key, mà ứng với Public Key dùng để mã hoá dữ liệu trên thì phải có Private Key thích hợp. Do đó, dữ liệu sẽ an toàn. Khi dữ liệu đến tay người nhận, muốn khôi phục lại dữ liệu gốc ban đầu, ta sẽ giải mã lại với n = 35, d = 29. Giải mã chuỗi SECURE. Nội dung bị mã hoá M = cd mod n Dữ liệu gốc 24 19 S 10 5 E 33 3 C 21 21 U 23 18 R 10 5 E 3.2.3 Một số phương pháp tấn công Tính chất an toàn của phương pháp RSA dựa trên cơ sở, chi phí cho việc giải mã bất hợp lệ thông tin đã được mã hóa sẽ quá lớn nên xem như không thể thực hiện được. Vì khóa là công cộng nên việc tấn công bẻ khóa phương pháp RSA thường dựa vào khóa công cộng để xác định khóa riêng tương ứng. Điều quan trọng là dựa vào n để tính p, q, từ đó tính được d. 3.2.3.1 Phương pháp sử dụng φ(n) Giả sử người tấn công biết được giá trị φ(n). Khi đó việc xác định giá trị p, q được đưa về giải hai phương trình sau. n = p*q φ(n) = (p-1)*(q-1) Thay q = n/p ta được phương trình bậc hai: p2 + p*( φ(n) - n - 1) + n = 0. p, q chính là hai nghiệm của phương trình bậc hai này. Tuy nhiên vấn đề phát hiện được φ(n) còn khó hơn việc xác định hai thừa số nguyên tố của n. 3.2.3.2 Áp dụng thuật toán phân tích ra thừa số Có nhiều thuật toán để phân tích ra thừa số. Tuy nhiên thuật toán Pollard p-1, là một trong những thuật toán đơn giải, hiệu quả, dùng để phân tích ra thừa số nguyên tố của các số nguyên lớn, ở đây ta phân tích số nguyên n dựa vào phân tích p-1 với p là một ước nguyên tố của n. Các bước của thuật toán: Bước 1: Xác định đầu vào là hai số n và b ( n là số nguyên lẻ cần phân tích, b là một giá trị giới hạn). Bước 2: Gán a = 2. Bước 3: for j = 2 to b do a = aj mod n Bước 4: Tìm d = gcd(a-1,n). d là ước chung lớn nhất của a-1 và n. Bước 5: Nếu 1< d < n then d là thừa số nguyên tố của n (thành công). Ngược lại Không xác định được thừa số nguyên tố của n. Giải thuật này chỉ hiệu quả khi tấn công phương pháp RSA trong trường hợp n có thừa số nguyên tố p mà p-1 chỉ có các ước số nguyên tố rất nhỏ. Do đó chúng ta có thể dễ dàng xây dựng một hệ mã hóa công cộng RSA an toàn đối với giải thuật tấn công p-1. Cách đơn giản là tìm một số nguyên tố p1 lớn mà p = 2p1+1 cũng là số nguyên tố, tương tự, tìm q1 là số nguyên tố lớn mà q = 2q1+1 là nguyên tố. 3.2.3.3 Bẻ khóa dựa trên tấn công lặp lại Siimons và Norris đã chỉ ra rằng hệ thống RSA có thể bị tổn thương khi sử dụng phương pháp tấn công lặp lại liên tiếp. Đó là khi đối thủ biết cặp khóa công cộng (e,n) và từ khóa C thì họ có thể tính chuổi các từ khóa sau. C1 = Ce mod n. C2 = C1e mod n. ........................ Ci = Ci-1e mod n. Nếu có một phần tử Cj trong chuỗi C1, C2,…, Ci. Sao cho Cj = C thì khi đó kẻ tấn công sẻ tìm được M = Cj-1 bởi vì. Cj = Cej-1 mod n. C = Me mod n. Ví dụ : Giả sử anh ta biết {e, n, C} = {17, 35, 3}. Người ta sẻ tính. C1 = Ce mod n = 317 mod 35 = 33. C2 = C1e mod n = 3317 mod 35 = 3. Vì C2 = C nên M = C1 =33. 3.2.4 Đánh giá thuật toán - RSA đơn giản, dễ hiểu, dễ cài đặt. - Hiệu suất hoạt động: RSA chạy chậm do việc phát sinh khoá công khai, khoá bí mật hay quá trình mã hoá, giải mã tốn nhiều thời gian vì phải tính toán trên các số nguyên dương cực lớn, có chiều dài vượt quá khả năng chứa của thanh ghi nên phải thực hiện lại nhiều lần và sử dụng nhiều đến bộ xử lý. Do đó, RSA không được sử dụng vào mục đích mã hoá các khối lượng dữ liệu lớn mà chỉ ứng dụng trong chữ ký điện tử để mã hoá thông điệp ngắn đã qua hàm băm (hash), giải thuật trao đổi khoá bí mật (khoá dùng cho các hệ