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
i0
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 n1 1 trên vành
như sau:
ai ( x) mod h( x), i 1, 2,..2n1 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 n1 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
n2
thường và chú ý thay thế: x n1 xi .
i0
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
- Xem thêm -