Tài liệu Nghiên cứu xây dựng cấp số nhân cyclic vào việc tạo khóa cho các mật mã khối

HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG --------------------------------------- ĐẶNG XUÂN ĐIỆP NGHIÊN CỨU SỬ DỤNG CẤP SỐ NHÂN CYCLIC VÀO VIỆC TẠO KHÓA CHO CÁC MẬT MÃ KHỐI Chuyên ngành: Truyền dữ liệu và mạng máy tính Mã số: 60.48.15 Người hướng dẫn khoa học: TS NGÔ ĐỨC THIỆN TÓM TẮT LUẬN VĂN THẠC SĨ HÀ NỘI - 2013 1 MỞ ĐẦU Lý do chọn đề tài Mật mã khóa bí mật hay còn gọi là mật mã cổ điển có lịch sử phát triển từ lâu đời. Cho đến ngày này hệ mật này vẫn được sử dụng rộng rãi với các ưu điểm nổi bật như: Đơn giản (thời gian nhanh, yêu cầu phần cứng không phức tạp); Hiệu quả: (Tỷ lệ mã bằng 1) dễ sử dụng cho các ứng dụng nhạy cảm với độ trễn và các ứng dụng di động. Các phương pháp xây dựng các hệ mật khóa bí mật thường được xây dựng trên các phép thay thế, hoán vị và kết hợp cả thay thế và hoán vị và nổi bật trong các hệ mật này là chuẩn mã dữ liệu DES. Đây là một phương pháp mật mã được tổ chức Tiêu chuẩn Xử lý Thông tin Liên bang Hoa Kỳ chọn làm chuẩn chính thức vào năm 1976, sau đó chuẩn này được sử dụng rộng rãi trên phạm vi thế giới. Phương pháp xử lý thông tin trong DES theo mật mã khối. Khi sử dụng DES ở chế độ bình thường ECB có một nhược điểm là khi các khối bản tin rõ đầu vào giống nhau và sử dụng cùng một khóa thì mã đầu ra sẽ giống nhau, điều này là rất nguy hiểm và thám mã có thể lợi dụng để phá mã. Để giải quyết vấn đề này ta có thể sử dụng DES ở chế độ liên kết mã khối (CBC) nhưng ở chế độ này cũng có nhược điểm là khi giải mã sai một khối thông tin thì toàn bộ các khối thông tin tiếp theo sẽ bị giải mã sai. Một phương pháp khác để khắc phục điểm yếu này là sử dụng các khóa khác nhau cho mỗi khối thông tin đầu vào và các khóa này được tạo một cách ngẫu nhiên là tốt nhất. Tuy nhiên, việc tạo và lưu trữ các khóa kiểu ngẫu nhiên sẽ tốn kém và không hiệu quả. Cấp số nhân cyclic trên vành đa thức đặc biệt là trên vành đa thức có hai lớp kề cyclic có một tính chất là số lượng các phần tử của cấp số nhân rất lớn và xuất hiện có tính gần giống ngẫu nhiên. Việc tạo các cấp số nhân khá đơn giản, chỉ cần một đa thức sinh và có thể thêm một đa thức ban đầu. Với tính chất như vậy ta có thể sử dụng các cấp số nhân cyclic để sinh khóa cho mật mã khối nói chung và hệ mật DES nói riêng. Đây là một hướng nghiên cứu mở mà luận văn sẽ tập trung vào nghiên cứu. Các kết quả của luận văn góp một phần vào việc nâng cao tính bảo mật chống lại khả năng thám mã của các mật mã khối. Mục đích nghiên cứu Đề xuất một phương pháp tạo khóa cho mật mã khối trong các hệ khóa bí mật bằng các cấp số nhân cyclic trên vành đa thức. Mô phỏng so sánh giữa DES tiêu chuẩn với DES có khóa được xây dựng từ các cấp số nhân trên vành đa thức, từ đó đưa ra được ưu điểm của phương pháp đề xuất. 2 Đối tượng và phạm vi nghiên cứu Đối tương nghiên cứu: Mật mã khối; Nhóm nhân và cấp số nhân trên vành đa thức. Phạm vi nghiên cứu: Sử dụng cấp số nhân cyclic trên vành đa thức để tạo khóa cho hệ mật DES Phương pháp nghiên cứu Sử dụng lý thuyết về mật mã học, các cấu trúc đại số trên vành đa thức. Kết hợp với việc tính toán và mô phỏng hệ mật DES với khóa đề xuất. Nội dung của đồ án bao gồm Chương 1: Tổng quan về mật mã học Chương 2: Nghiên cứu sử dụng cấp số nhân Cyclic vào việc tạo khóa cho mật mã khối Chương 3: Một số kết quả mô phỏng đánh giá 3 CHƯƠNG 1. TỔNG QUAN VỀ MẬT MÃ HỌC 1.1. Các khái niệm cơ bản về mật mã học 1.1.1 Sơ lược lịch sử về khoa học mật mã 1.1.2 Giới thiệu về hệ mật mã - Định nghĩa hệ mật mã - Các thuật ngữ 1.1.3 Những yêu cầu đối với hệ mật mã 1.2. Hệ mật mã khóa bí mật 1.2.1 Sơ đồ chức năng của hệ mật khóa bí mật Hình 1.1. Sơ đồ chức năng của hệ mật khóa bí mật [1] 1.2.2 Hệ mật thay thế - Các hệ mật thay thế đơn biểu - Các hệ mật thay thế đa biểu 1.2.3 Các hệ mật hoán vị - Mật mã Rail fence - Mật mã Route - Mật mã Columnar 4 1.2.4 Chuẩn mã dữ liệu DES - Giới thiệu về DES Hình 1.2. Sơ đồ mã DES - Mô tả thuật toán - Hàm mật mã f - Khối tạo khóa 5 K 64 bit PC-1 28 bit 28 bit C0 D0 LS - LS -1 C1 D1 PC-2 C16 D16 PC-2 K1 (48 bit) K16 (48 bit) Hình 1.3. Khối tạo khóa cho các vòng mã hóa của DES - Giải mã DES - Sự an toàn của DES 1.2.5 Chuẩn mã dữ liệu tiên tiến (AES) - Tổng quan về AES - Thiết kế tổng quát của AES Hình 1.4. Thiết kế tổng quát của AES [4] 6 1.3. Hệ mật khóa công khai 1.3.1 Sơ đồ chức năng của hệ mật khóa công khai Thám mã Nguồn M C Mã hóa C Kênh mở M Đích Giải mã A B KCB KRB Hình 1.5. Sơ đồ chức năng của hệ mật khóa công khai KCB: Khóa công khai của B KRB: Khóa bí mật của B Mã hóa: C = E (M,KCB) Giải mã: M = E -1 (C, KRB) = D (C, KRB) [1] 1.3.2 Một số bài toán sử dụng trong hệ mật khóa công khai 1.3.3 Ưu và nhược điểm của hệ mật khóa công khai 1.3.4 Xây dựng các chương trình ứng dụng kiến trúc PGP Hình 1.6. Chương trình ứng dụng kiến trúc PGP Với mô hình này sẽ kết hợp 2 ưu điểm của hai hệ mật khóa bí mật và hệ mật khóa công khai. 1.3.5 Sử dụng mã hóa công khai để truyền khóa bí mật K. 1.3.6 Sử dụng hệ mật mã khóa bí mật để mã hóa bản tin M. 7 1.4. Kết luận chương Khi thiết kế mật mã thì vấn đề đảm bảo độ vững chắc của thuật toán là một vấn đề quan trọng nhất. Đánh giá độ bền vững của thuật toán là một trong các vấn đề lâu nhất và khó nhất. Phương pháp mã hóa cổ điển sử dụng giải thuật đơn giản, không gian khóa nhỏ. Phương pháp mã hoá cổ điển có thể dễ dàng bị giải mã bằng cách đoán chữ dựa trên phương pháp thống kê tần xuất xuất hiện các chữ cái trên mã và so sánh với bảng thống kê quan sát của bản rõ. Để dùng được mã hoá cổ điển thì bên mã hoá và bên giải mã phải thống nhất với nhau về cơ chế mã hoá cũng như giải mã. Việc thay đổi mã là rất khó và dễ bị lộ. Hệ mật mã khóa đối xứng có khóa lập mã và khóa giải mã là trùng nhau cho nên mật mã đó phải được giữ bí mật chỉ có người lập mã và người nhận mã được biết mà thôi. Khóa phải được gửi đi trên kênh an toàn, nếu kẻ địch tấn công trên kênh này có thể sẽ phát hiện ra khóa. Thuật toán mã hóa công khai được thiết kế sao cho khóa sử dụng vào việc mã hóa là khác so với khóa giải mã. Khóa giải mã không thể tính toán được từ khóa mã hóa. Nếu kẻ tấn công cố tình tìm ra khóa giải mã thì sẽ gặp phải khó khăn về thời gian và số phép thử vô cùng lớn, như vậy là không khả thi vì bản tin chỉ có giá trị trong một thời gian ngắn. Khóa mã hóa được gọi là khóa công khai còn khóa giải mã được gọi là khóa riêng. Khóa công khai và bản tin mã hóa đều được gửi đi trên một kênh thông tin không an toàn. 8 CHƯƠNG 2. NGHIÊN CỨU SỬ DỤNG CẤP SỐ NHÂN CYCLIC VÀO VIỆC TẠO KHÓA CHO MẬT MÃ KHỐI 2.1. Những vấn đề cơ bản về cấu trúc đại số Những vấn đề cơ bản được trình bày trong mục này gồm có: - Nhóm - Vành - Trường - Trường hữu hạn 2.2. Vành đa thức 2.2.1 Khái niệm đa thức Nếu R là một vành giao hoán thì một đa thức của biến x trên vành R là một biểu thức có dạng: n 1 f ( x)   f i x i (2.4) i 0 Trong đó: fi – là hệ số thuộc R. Trong trường nhị phân GF(2) nó nhận giá trị 0 hoặc 1. x – biến (ẩn hình thức). 2.2.2 Vành đa thức Nếu R là một vành giao hoán thì vành đa thức R[x] là một vành được tạo bởi tập tất cả các đa thức của biến x có các hệ số trong R. Hai phép toán là phép cộng và phép nhân đa thức thông thường với số học các hệ số được thực hiện trong vành R [1]. Trong trường nhị phân, vành đa thức được ký hiệu: (f(x); f, ) = Z2[x]/xn + 1 e(x) = 0 gọi là phần tử đơn vị, deg e(x) = 0 (f(x), +) là một nhóm đối với phép cộng, thỏa mãn tiên đề của nhóm. (f(x), *) là nửa nhóm đối với phép nhân, không tồn tại f(x), g(x) mà f(x).g(x) = 0 2.2.3 Vành đa thức có hai lớp kề cyclic Vành đa thức theo modulo xn+1 được gọi là vành đa thức có hai lớp kề cyclic nếu phân tích của xn+1 thành tích của các đa thức bất khả quy trên trường GF(2) có dạng sau: xn + 1 = (x + 1) n 1 x i 0 i (2.9) 9 n 1 Trong đó (1+x) và eo(x) = x i là các đa thức bất khả quy [3]. i 0 Căn cứ vào đặc điểm trên của vành đa thức có hai lớp kề cyclic ta có thuật toán xác định điều kiện để vành đa thức có hai lớp kề cyclic. Theo thuật toán ta xác định được một số giá trị n đảm bảo vành đa thức theo mod xn+1 là một vành đa thức có hai lớp kề cyclic. Dưới đây là một số giá trị n thỏa mãn [3]: n = 3 5 11 13 19 29 37 53 59 61 67 83 101 107 131 139 149 163 173 179 181 197 211 227 269 293 317 347 349 373 379 389 419 421 443 461 467 491 509 523 541 547 557 563 587 613 619 653 659 661 677 701 709 757 773 787 797 821 827 829 853 859 877 883 907 941 947 1019 1061 1091 1109 1117 1123 1171 1187 1213 1229 1237 1259 1277 1283 1291 1301 1307 1373 1381 1427 1451 1453 1483 1493 1499 1523 1531 1549 1571 1619 1621 1637 1667 1669 1693 1733 1741 1747 1787 1861 1867 1877 1901 1907 1931 1949 1973 1979 1987 1997 2027 2029 2053 2069 2083 2099 2131 2141 2213 2221 2237 2243 2267 2269 2293 2309 2333 2339 2357 2371 2389 2437 2459 2467 2477 2531 2539 2549 2557 2579 2621 2659 2677 2683 2693 2699 2707 2741 2789 2797 2803 2819 2837 2843 2851 2861 2909 2939 2957 2963 3011 3019 3037 3067 3083 3187 3203 3253 3299 3307 3323 3347 3371 3413 3461 3467 3469 3491 3499 3517 3533 3539 3547 3557 3571 3581 3613 3637 3643 3659 3677 3691 3701 3709 3733 3779 3797 3803 3851 3853 3877 3907 3917 3923 3931 3947 3989 4003 4013 4019 4021 4091 4093 4099 4133 4139 4157 4219 4229 4243 4253 4259 4261 4283 4349 4357 4363 4373 4397 4451 4483 4493 4507 4517 4547 4603 4621 4637 4691 4723 4787 4789 4813 4877 4933 4957 4973 4987 5003 5011 5051 5059 5077 5099 5107 5147 5171 5179 5189 5227 5261 5309 5333 5387 5443 5477 5483 5501 5507 5557 5563 5573 5651 5659 5683 5693 5701 5717 5741 5749 5779 5813 5827 5843 5851 5869 5923 5939 5987 6011 6029 6053 6067 6101 6131 6173 6197 6203 6211 6229 6269 6277 6299 6317 6323 6373 6379 6389 6397 6469 6491 6547 6619 6637 6653 6659 6691 6701 6709 6733 6763 6779 6781 6803 6827 6829 6869 6883 6899 6907 6917 6947 6949 6971 7013 7019 7027 7043 7069 7109 7187 7211 7219 7229 7237 7243 7253 7283 7307 7331 7349 7411 7451 7459 7477 7499 7507 7517 7523 7541 7547 7549 7573 7589 7603 7621 7643 7669 7691 7717 7757 7789 7829 7853 7877 7883 7901 7907 7933 7949 8053 8069 8093 8117 8123 8147 8171 8179 8219 8221 8237 8243 8269 8291 8293 8363 8387 8429 8443 8467 8539 8563 8573 8597 8627 8669 8677 8693 8699 8731 8741 8747 8803 8819 8821 8837 8861 8867 8923 8933 8963 8971 9011 9029 9059 9173 9181 9203 9221 9227 9283 9293 9323 9341 9349 9371 9397 9419 9421 9437 9467 9491 9533 9539 9547 9587 9613 9619 9629 9643 9661 9677 9733 9749 9803 9851 9859 9883 9901 9907 9923 9941 9949 10 2.3. Các nhóm nhân cyclic trên vành đa thức 2.3.1 Nhóm nhân của vành đa thức Tập các đa thức f(x) trong vành đa thức Z2[x]/xn+1 với một phép toán nhân đa thức tạo nên một nhóm nhân G. = G Nếu g(x), f(x)  G thì g(x).f(x) = d(x)  G. Trong nhóm nhân tồn tại phần tử đơn vị e(x) với f(x).e(x) = f(x). Trọng số của đa thức: Trọng số của đa thức a(x) được ký hiệu là W(a(x)) là tổng các hệ số khác 0 trong biểu diễn đa thức đó: n 1 a ( x)   ai xi i 0 (2.10) Với a(x) = 1 + x ta có thể viết a(x) = 1.x0 + 1.x1  W(a(x)) = 2. 2.3.2 Nhóm nhân cyclic trong vành đa thức - Nhóm nhân cyclic (CMG – Cyclic Multiplicate Groups) - Nhóm nhân cyclic đơn vị - Nhóm nhân cyclic với phần tử sinh a(x) - Đa thức đối xứng và các nhóm nhân cyclic đối xứng 2.3.3 Cấp số nhân cyclic trên vành đa thức Xét vành đa thức Z2[x]/ xn + 1 với n lẻ, giả sử a(x) là số hạng đầu tiên của cấp số nhân cyclic và q(x) là công bội của cấp số nhân. Định nghĩa 2.10: Cấp số nhân cyclic (CGP - Cyclic Geometic Progressions) Cấp số nhân cyclic trên vành đa thức là một tập hợp con có dạng sau: A(a,q) = {a(x), a(x).q(x), a(x).q 2(x), ..., a(x).qm -1(x)}. Trong đó: m là số các số hạng của cấp số nhân. A(x) là số hạng đầu của cấp số nhân. q(x) là công bội. a(x).qm(x)  a(x) mod xn + 1 Giá trị của m được xác định bởi cấp của nhóm nhân cyclic [3]. Trong trường hợp ta chọn số hạng đầu a(x) = 1, công bội là q(x) thì: A(1,q) = {1, q(x), q2(x), …, q m-1(x)}; q m(x) = q0(x) =1; (2.16) 11 là cấp số nhân cyclic cấp m. 2.4. Phương pháp tạo khóa cho hệ mật mã khối bằng các cấp số nhân cyclic 2.4.1 Đề xuất sử dụng cấp số nhân cyclic cho việc tạo khoá Ta nhận thấy rằng các hệ mật tuyến tính là không an toàn. Bởi vậy, để sử dụng được chúng ta phải liên tục thay đổi khoá. Để thực hiện điều kiện này ta có thể làm như sau: - Hai bên liên lạc chọn trước một phần tử nguyên thủy a(x) với: ord a(x) = 2n-1–1 (a(x) là phần tử sinh của nhóm nhân cyclic có cấp = 2n-1–1) - Số các phần tử này được xác định bởi công thức sau: M = (2n-1–1) (2.17) Ở đây, (.) là hàm -Euler 2.4.2 Đề xuất sử dụng dãy m lồng ghép cho việc tạo khóa Đối với vành đa thức có hai lớp kề cyclic, phân tích của vành này luôn có phân tích nhị thức ở dạng: n 1 x n  1  1  x  x i i 0 (2.18) Vành đa thức có hai lớp kề cyclic sẽ có hai đa thức h(x) ở dạng như sau: + h(x) = (1+x) và: n 1 + h(x) = x i i0 Cấp lớn nhất trên vành đa thức có hai lớp kề cyclic sẽ là 2n-1 -1. Trên vành này, chúng ta hoàn toàn có thể xây dựng một dãy m có chiều dài L = 2 n-1 -1 đúng bằng cấp lớn nhất của đa thức trên vành. Cách thức xây dựng dãy m lồng ghép ở đây sẽ dựa trên phân hoạch theo modulo h(x), với phương pháp phân hoạch tạo ra cấp số nhân có chiều dài 2 n1  1 trên vành như sau: ai ( x) mod h( x), i  1, 2,..2n1  1 (2.19) (a(x) là công bội của cấp số nhân) Ở đây h(x) đóng vai trò là đa thức sinh để tạo ra dãy m và là đa thức bất khả quy bậc n-1. Muốn để cho phân hoạch có chiều dài cực đại L = 2 n-1 -1 thì đa thức a(x) được chọn làm công bội sẽ phải thỏa mãn: Max(ord (a(x)) = 2n-1 -1 (2.20) 12 Để minh họa cụ thể, ta sẽ sẽ xây dựng dãy m trên vành x13 + 1. Vành này có cấp cực đại là: max(ord (a(x)) = 213-1 -1 = 4095 = 3.3.5.7.13 Vành này có cấp hay chiều dài của các phân hoạch là bội số chung của tổ hợp 3, 5, 7,13. Ta sẽ tạo ra dãy m trên vành này có chiều dài hay chu kỳ là 4095: 212 -1 = 4095. 12 Ở đây, ta thấy: h(x) = x i i 0 Công bội a(x) sẽ được chọn là các đa thức có cấp là 4095, chẳng hạn ta có thể chọn các tam thức ở bảng sau để trở thành công bội a(x) trong phân hoạch tạo dãy m theo modulo h(x). 2.5. Kết luận chương Chương này đã trình bày về một số khái niệm cơ bản về đại số trừu tượng, các khái niệm về: vành đa thức, nhóm nhân, cấp số nhân cyclic trên vành đa thức, đặc biệt là vành đa thức có hai lớp kề cyclic. Đây là một vành đặc biệt không được sử dụng trong xây dựng mã cổ điển, tuy nhiên với cấu trúc của các cấp số nhân cyclic trên các vành đa thức có hai lớp kề ta có thể ứng dụng vào việc xây dựng các hệ mật và việc tọa khóa cho các hệ mật khá lý thú. Cấp số nhân cyclic trên vành đa thức đặc biệt là trên vành đa thức có hai lớp kề cyclic có một tính chất là số lượng các phần tử của cấp số nhân rất lớn và xuất hiện có tính gần giống ngẫu nhiên. Việc tạo các cấp số nhân khá đơn giản, chỉ cần một đa thức sinh và có thể thêm một đa thức ban đầu. Với tính chất như vậy ta có thể sử dụng các cấp số nhân cyclic để sinh khóa cho mật mã khối nói chung. Việc đề xuất sử dụng các cấp số nhân cyclic vào việc tọa khóa cho mật mã khối sẽ được trình bày ở chương 3. 13 CHƯƠNG 3. MỘT SỐ CHƯƠNG TRÌNH TÍNH TOÁN KHÓA VÀ MÃ HÓA 3.1. Tạo khóa mã hóa cho từng khối bản tin của hệ mật khóa bí mật 3.1.2 Sử dụng cấp số nhân có cấp cực đại Sơ đồ mã hóa và giải mã được mô tả như hình 3.1. Các khối bản tin M i Mã hóa Các khối mã Ci Các khóa tương ứng Ki Ci Kênh mở Thám mã Giải mã Các khóa tương ứng Ki Trao đổi và thỏa thuận khóa Tạo khóa K (cấp số nhân cyclic) Các khối bản tin M i Tạo khóa K (cấp số nhân cyclic) Hình 3.1. Sử dụng cấp số nhân cyclic làm khóa mã hóa cho từng khối bản tin Như đã phân tích trong chương 2, trong vành đa thức có hai lớp kề Z 2 [x] / x n  1 có các phần tử có cấp cực đại là: 2 n1  1 , với n lớn thì ta có thể tạo chuỗi khóa rất dài. Dưới đây là một ví dụ tạo khóa cho hệ mật DES. Ví dụ 3.1: Bước 1: Chọn n Vì DES sử dung khóa là 56 bit ta có thể chọn n  59 , sau khi tạo khóa ta loại bớt 3 bit đi. Bước 2: Chọn đa thức sinh: a( x)  1  x9  x18  x 27  x36  x 45  x54  (0 9 18 27 36 45 54) (Chú ý: (0 9 18 27 36 45 54) là biễu diễn dạng số mũ của a( x) ). Bước 3: Chọn đa thức đầu: b( x)  1  x  x 2  (012) . Bước 4: Tính cấp số nhân cyclic: K  b( x) a ( x) i mod x 59  1 ; i  1, 2 58  1 Bảng 3.1 là 32 khóa đầu tiên (phần tử của cấp số nhân cyclic) của K . 14 Bảng 3.1. Các khóa K đầu tiên tạo theo cấp số nhân cyclic Ki Các bit khóa tương ứng Trọng số 1 00000000011100000011100000011100000011100000011100000011100 18 2 00000000000001110011100000000001110011100000000001110011100 18 3 11001110111001110000001110011101110100101110111001110000001 32 4 00011100000001110000000000111000000011111100000001110000000 18 5 00010011110001111001000001001011101110010010011101110100100 28 6 10011100111110111110011100111111000000011100111000000011111 34 7 01101011001101000101100110101100101110011100000011100111010 30 8 00000011100001110001110000111000000000011100000000001110000 18 9 00010010001100001010101000011000100100000101010011001010100 20 10 01110011000100111001101100111001000110011100000110000110000 26 11 10011010110001011101001010010111010001101011001110100001011 30 12 11000011100000001111111110111111111000000011100001111111111 36 13 11111111001001100101110010101010011101001100100111111111001 36 14 00111101000100110111111101011011010111111101100100010111100 36 15 01100011111111100100000101101010101011010000010011111111100 32 16 00000000000011100001110000111000000000111000011100001110000 18 17 10101111010101110100110101101011001010011010110101100101110 34 18 01101000000101101101010000011010000010100000101100000101011 22 19 10110011011011001101000001000011100011000110001110000100000 24 20 00100011011111101100010000001110000111100000111100001110000 26 21 11100001110101101011100001111110110110011000001100110110111 34 22 10101111101110100101110111110101001010000110000011000010100 30 23 01111001000100001111000010001001111011001110010001001110011 28 24 01000111000011100000000001110000111000100100100100010010010 20 25 01100000111000110001011010001100011100000110110110000011011 26 26 00111001001000101101000110001011010001001001110010100000101 24 27 10101010110110111101000110011000101111011011010101011110111 36 28 11001111100111110001111101111110111110001111100111110011101 42 29 01001110101110010110001011001001001101000110100111010111001 30 30 01010000011001001111100011100001100001110001111100100110000 26 31 01100011000111111111001000001011011011010000010011111111100 32 32 00000000000000000111000011100001110000111000011100001110000 18 Tổng số: Với 32 giá trị của K ở bảng 3.1, xác suất xuất hiện của bit 1 là: p (1)  882 882   0, 4672 59  32 1888 882 15 Khi tính toán với số lượng khóa nhiều hơn thì xác suất của bit “1” và bit “0” sẽ tiến đến xấp xỉ bằng 0,5. Tiến hành mã hóa DES với các khóa đề xuất như trong bảng 3.1. Mã hóa 32 khối bản tin đầu vào giống nhau là: M hex  0123456789ABCDEF (16 ký tự Hexa = 64 bit) M bin  000010000 100 110000 10 10 100 1101110000110010101110 1001110 1101111111 Mỗi lần mã hóa ta sử dụng các khóa khác nhau tương ứng từ K1  K 32 . Kết quả tính toán như trong bảng 3.2. Bảng 3.2. Khoảng cách Hamming giữa các từ mã khi dùng các khóa khác nhau mã hóa cùng một bản tin đầu vào Khóa Ki Mã đầu ra tương ứng Ci Khoảng cách Hamming với bản mã đầu tiên d(Ci ,C1 ) 1 BDC3DAA77A681FAD 0 2 AC5D74D6B38EF6BF 32 3 FF5279272F6F6A54 28 4 5081824600E3E19D 33 5 83E9399C8CDCEAB7 37 6 106FFD0B6FA45F25 27 7 49D08D1FE4700085 31 8 018694BB472D38C6 32 9 3BBDE9FF9D6F647E 36 10 FDD34100740B12B3 26 11 97DD8354EE53E146 38 12 5E3EB38E68A692F1 34 13 22448B335BED82D7 31 14 FF34613435986E5E 38 15 7E85C59254CA5EB7 28 16 4F9A95870F915AE6 33 17 A53609C3DC149C7D 31 18 1768B4FA17F15447 37 19 9FBBF3D8E57EDE0D 30 20 FA79FFA616815D21 27 21 92224821F91DB075 33 22 B5DBE6BB67033181 26 16 23 8B7B5E5E4E033529 29 24 FECCA9A2B11A3CAC 27 25 24EC0159B5D7DE97 42 26 BB5EA5287C67452B 32 27 40448AA6D5E2921E 32 28 69C856089CD4029F 33 29 C83EC39274FAA04E 37 30 B097BAF417E0A408 29 31 A0312383DC4A7A41 32 32 D174D0EB96AECFCD 29 Khoảng cách Hamming trung bình: d tb  1 32  d (C ,C )  31,93 31 i  2 1 i 3.1.2 Sử dụng cấp số nhân lấy theo modulo của h(x) Như đã đề cập ở chương 2, ta có thể sử dụng dãy m lồng ghép xây dựng từ các vành đa thức có hai lớp kề lấy theo modulo của đa thức h( x) cho việc tạo khóa. Đối với vành đa thức có hai lớp kề cyclic, phân tích của vành này luôn có phân tích nhị thức ở dạng: n 1 x n  1  1  x   xi i 0 (3.1) Có hai đa thức h( x) thỏa mãn là [3]: n 1 h1 ( x)  (1  x); h2 ( x)   x i i 0 Chọn h2 ( x ) làm đa thức lấy moddulo, tính toán các phần tử của cấp số nhân bình n2 thường và chú ý thay thế: x n1   xi . i0 Ví dụ 3.2: Sử dụng cấp số nhân cyclic trên vành đa thức có hai lớp kề lấy theo modulo h( x) tạo khóa cho DES. Bước 1: Chọn n  59 Bước 2: Chọn đa thức sinh: a( x)  1  x10  x19  x 28  x37  x 46  x55  (0 10 19 28 37 46 55) 17 Bước 3: Chọn đa thức đầu: b( x)  1  x  x 2  (012) . 58 Bước 4: Chọn h( x)   xi i 0 Tính cấp số nhân cyclic: K  b( x ) a ( x ) i mod h( x ) ; i  1, 2 58  1 Bảng 3.2 là 32 khóa đầu tiên (phần tử của cấp số nhân cyclic) của K . Bảng 3.3. Các khóa K đầu tiên tạo từ cấp số nhân lấy theo modulo h(x) Ki Các bit khóa tương ứng Trọng số 1 0000000000111000000111000000111000000111000000111000000111 18 2 1111111111111110001100011111111110001100011111111110001100 41 3 0011100111011100111000000111001110111010010111011100111000 32 4 0000000111000000011100000000001110000000111111000000011100 18 5 1101111101100001110000110111110110100010001101101100010001 31 6 0111111001110011111011111001110011111100000001110011100000 34 7 0111010011010110011010001011001101011001011100111000000111 30 8 0111000000000011100001110001110000111000000000011100000000 18 9 1101010111110110111001111010101011110011101101111101010110 39 10 1111001111100011001110110001100100110001101110011000111110 33 11 0101111010001100101001110100010110101101000101110010100110 29 12 0011111111111100001110000000111111111011111111100000001110 36 13 0111111111001111111110010011001011100101010100111010011001 36 14 1101110100001111000010111011001000000010100100101000000010 23 15 0100111111111000110001111111110010000010110101010101101000 32 16 0011100001110000000000000000111000011100001110000000001110 18 17 1011010110010111010101111010101110100110101101011001010011 34 18 0001011000001010110110100000010110110101000001101000001010 22 19 0110001110000100000101100110110110011010000010000111000110 24 20 1111100001111000111111011100100000010011101111110001111000 33 21 0110000011001101101111110000111010110101110000111111011011 34 22 1111001111100111101011010100000100010110100010000010101101 29 23 1100111001000100111001101111001000100001111000010001001111 28 24 1110110110110111011011011011100011110001111111111000111100 39 25 0011111001001001111100100100111110001110011101001011100111 33 26 1000100100111001010000010100111001001000101101000110001011 24 27 1011110110110101010111101111010101011011011110100011001100 36 28 1000001110000011000001100010001100000110000011100000100000 17 29 0100110100011010011101011100101001110101110010110001011001 30 18 30 0011000011100011111001001100000101000001100100111110001110 26 31 1011011011010000010011111111100011000110001111111110010000 32 32 1111000111100011110001111000111111111111111111111000111100 41 Tổng số: 950 Xác suất xuất hiện của bit 1 của 32 khóa trong bảng 3.3 là: p (1)  950 882   0,5119 58  32 1856 Tương tự ta tiến hành mã hóa DES với các khóa đề xuất như trong bảng 3.3. Mã hóa 32 khối bản tin đầu vào giống nhau là: M hex  0123456789ABCDEF (16 ký tự Hexa = 64 bit) M bin  000010000 100 110000 10 10 100 1101110000110010101110 1001110 1101111111 Mỗi lần mã hóa ta sử dụng các khóa khác nhau tương ứng từ K1  K 32 ; các khóa này có độ dài 58 bit, nên trước khi mã hóa ta sẽ loại bỏ 2 bit cuối đi. Kết quả tính toán như trong bảng 3.4. Bảng 3.4. Khoảng cách Hamming giữa các từ mã khi dùng các khóa là cấp số nhân cyclic lấy theo modulo h(x) Khóa Ki Mã đầu ra tương ứng Ci Khoảng cách Hamming với bản mã đầu tiên d(Ci ,C1 ) 1 D35F50062DD316B2 0 2 A717ED35C53550A7 31 3 FEEB7555FD36D06D 34 4 FD9F239D5E8F85E3 32 5 233E0D88FFF30012 26 6 E72E217470F14BB5 30 7 E13D32E2147451CA 30 8 1AFED435214EF6B6 24 9 6106CE1FB643F2F7 30 10 58DA7F7C4E0A4C39 34 11 D38C0E8E0016F383 28 12 5913EE4312E50C9C 32 13 6BFF04241F981B38 24 14 70BC5F96C29B4A12 30 15 507CA10955BBE09D 33 16 9A16E4D224F43136 26 17 6DC112F8675574A9 33