Chuẩn mã DỮ liệU
tải về 0.52 Mb.
|
- Điều hướng trang này:
- 3.6.1. Tấn công DES 3 vòng
- Hình 3.9. Cách tấn công DC lên DES 3 vòng.
- 3.6.2. Tấn công DES 6 vòng
- Hình 3.10. Đặc trưng một vòng.
- Hình 3.11. Một đặc trưng một vòng khác.
- Hình 3.12. Một đặc trưng 3 vòng.
- Hình 3.13. DC đối với DES 6 vòng.
Ta viết các E,B, và J là một dãy ghép kế tiếp 8 xâu 6 bít: B = B1 B2 B3 B4 B5 B6 B7 B8 E = E1 E2 E3 E4 E5 E6 E7 E8 J = J1 J2 J3 J4 J5 J6 J7 J8
Ej Jj INj(Ej',Cj' ) trong đó E j' = Ej Ej*. Giả sử ta xác định tập testj như sau: Định nghĩa 3.4. Giả sử Ej và Ej* là các xâu bít độ dài 6 và Cj' là xâu bít độ dài 4. Ta định nghĩa: testj(Ej , Ej*, Cj' ) = {Bj Ej : Bj INj(Ej',Cj')} trong đó Ej' = Ej Ej* Nghĩa là lấy XOR Ej với mỗi phần tử của tập INj(Ej',Cj'). Kết quả sau đây là một hệ quả trực tiếp rút ra từ suy luận ở trên. Định lý 3.1 Giả sử Ej và Ej* là hai xâu vào của hộp Sj còn XOR ra của Sj là Cj. Kí hiệu Ej' = Ej Ej* . Khi đó các bít khoá Jj sẽ nằm trong tập testj (Ej, Ej* , Cj'). Nhận thấy rằng có đúng Nj(Ej',Cj' ) xâu bít độ dài 6 trong tập testj(Ej,Ej*,Cj'); giá trị đúng của Jj phải là một trong các khả năng này. Ví dụ 3.2. Giả sử E1 = 000001, E1* = 110101 và C1' = 1101. Vì N1(110100,1101) = 8 nên có đúng 8 xâu bít trong tập test1(000001,110101,1101). Từ hình 3.8 ta thấy rằng: IN1(110100,1101) = {000110,010000,010110,011100,100010,100100,101000,110010} Bởi vậy test1(000001,110101,1101) = {000111,010001,010111,011101,100011,100101,101001,110011}. Nếu ta có một bộ ba E1,E1*,C1' thứ hai như vậy thì có thể thu được tập test1 thứ hai chứa các giá trị có thể chứa các bít khoá trong J1. Giá trị đúng của J1 phải nằm trong phần giao của hai tập này. Nếu ta có vài bộ ba như vậy thì có thể nhanh chóng xác định được các bít khoá trong J1. Phương pháp đơn giản để làm điều này là tạo một dãy 64 bộ đếm biểu diễn 64 khả năng của 6 bít khoá trong J1 . Bộ đếm sẽ đếm tăng mỗi khi các bít khoá tương ứng xuất hiện trong tập test1 với một bộ ba cụ thể. Với t bộ ba, ta tin rằng sẽ tìm được bộ đếm duy nhất có giá trị t tương ứng với giá trị đúng của các bít khoá trong J1. 3.6.1. Tấn công DES 3 vòng Bây giờ ta xét xem việc ứng dụng các ý tưởng của phần trước trong phép tấn công bản rõ chọn lọc lên một hệ DES 3 vòng. Ta bắt đầu ằng một cặp các bản rõ và bản mã tương ứng L0R0, L0*R0*,L3R3, và L3*R3* . Có thể biểu thị R3 như sau: R3 = L2 f (R2,K3) = R1 f (R2,K3) = L0 f (R0,K1) f (R2,K3)
R3' = L0' f (R0,K1) f(R0*,K1) f (R2,K3) f (R2*,K3) Bây giờ, giả sử ta đã chọn được các bản rõ sao cho R0 = R0* , nghĩa là để R0' = 00. . .0 Khi đó f (R0,K1) = f (R0*,K1) và như vậy:
C' = C C* = P-1(R3' L0') (3.1) Đây là XOR ra của 8 hộp S ở vòng thứ 3.
và E* = E(L3*) (3.3) bằng cách dùng hàm mở rộng E được biết công khai. Đây là các mẫu vào các hột S ở vòng thứ 3. Như thế ta đã biết E và E* và C ' của vòng thứ 3 và có thể thực hiện ( như ở phần trước) để xây dựng các tệp test1, . .., test8 chứa các giá trị có thể của các bít trong J1,. . .,J8 . Mô tả dạng giả mã của thuật toán này được cho ở hình 3.9. Hình 3.9. Cách tấn công DC lên DES 3 vòng.
Trong phương pháp tấn công này sẽ phải dùng một số bộ ba E, E*,C ' như vậy, Ta phải thiết lập 8 dãy bộ đếm và nhờ vậy xác định được 48 bít trong khoá K3 ( khoá của vòng thứ 3). Sau đó tính 56 bít trong khóa theo cách tìm kiếm vét cạn trong 28 = 256 khả năng cho 8 bít khoá còn lại. Ta sẽ xem xét một ví dụ để minh hoạ. Ví dụ 3.3. Giả sử ta có 3 cặp các bản rõ và các bản mã, trong đó các bản rõ có các phép XOR xác định, chúng được mã hoá bằng cùng một khoá. Để cho gọn ta sẽ biểu thị dưới dạng mã Hexa:
Từ cặp đầu tiên, tính các đầu vào của hộp S ( cho vòng 3 ) theo các phương trình (3.2) và (3.3). Ta có: E = 000000000111111000001110100000000110100000001100 E* = 101111110000001010101100000001010100000001010010 XOR ra của các hộp S được tính theo phương trình (3.1) là: C' = 10010110010111010101101101100111 Từ cặp thứ hai, ta tính được các đầu vào của các hộp S là: E = 101000001011111111110100000101010000001011110110 E* = 000001011110100110100010101111110101011000000100 và XOR ra của các hộp S là: C' = 11010101011101011101101100101011 Tiếp theo, lập bảng các giá trị trong 8 dãy bộ đếm cho từng cặp. Minh hoạ thủ tục này với dãy bộ đếm cho J1 theo cặp đầu tiên. Trong cặp này ta có: E' = 101111 và C' = 1001. Khi đó tập: IN1(101111,1001) = {000000,000111,101000,101111} vì E1 = 000000 nê ta có: J1test1(000000,101111,1001) = {000000,000111,101000,101111} Bởi vậy ta sẽ tăng các giá trị 0,7,40 và 47 trong dãy bộ đếm cho J1. Bây giờ sẽ trình bày các bảng cuối cùng. Nếu coi một xâu bít độ dài 6 như biểu diễn nhị phân của một số nguyên nằm giữa 0 và 63 thì 64 giá trị tương ứng là 0,1,. . . ,63. Các mảng bộ đếm sẽ như sau:
Trong số 8 mảng bộ đếm ( trong 8 mangt ở trên) có duy nhất một bộ đếm có giá trị 3, các vị trí của các bộ đếm này sẽ được xác định các bít khoá trong J1,.. ., J8. Các vị trí này tương ứng là 47,5,19,0,24,7,7,49. Đổi các số nguyên sang dạng nhị phân ta nhận được J1, . . .,J8: J 1 = 101111 J2 = 000101 J3 = 010011 J4 = 000000 J5 = 011000 J6 = 000111 J7 = 000111 J8 = 110001 Bây giờ ta có thể xây dựng 48 bít của khoá bằng cách nhìn vào bảng khoá đối với vòng 3. Khi đó K có dạng: 0001101 0110001 01?01?0 1?00100 0101001 0000??0 111?11? ?100011 ở đây ta đã bỏ qua các bít kiểm tra chặn lẻ và"?" chỉ bít khoá chưa biết. Khóa đầy đủ ( ở dạng hexa gồm cả bít kiểm tra chặn lẻ) là: 1A624C89520DEC46 3.6.2. Tấn công DES 6 vòng Trong mục này ta sẽ mở rộng các ý tưởng ở trên cho phép tấn công xác suất đối DES 6 vòng. Ý tưởng ở đây là phải chọn cẩn thận một acặp bản rõ với một phép XOR chỉ ra trước rồi xác định các xác suất của một dãy xác định các XOR qua các vong mã. Bây giờ ta sẽ định nghiã một khái niệm quan trọng. Định nghĩa 3.5. Cho n 1 là một số nguyên. Một đặc trưng n vòng là một danh sách có dạng: L0',R0',L1',R1',p1. . . Ln',Rn',pn thảo mãn các tính chất sau:
2. Cho 1 i n và giả sử Li-1, Ri-1 và Li-1*, Ri-1* được chọn sao cho Li-1Li-1* = Li-1' và Ri-1Ri-1* = Ri-1'. Giả sử Li,Ri và Li*,Ri* được tính bằng cách áp dụng một vòng mã hoá của DES; Khi đó xác suất để Li Li* = Li' và RiRi* = Ri' đúng bằng pi ( chú ý rằng xác suất này được tính trên mọi bộ 48 J = J1. . . J8 có thể). Xác suất của đặc trưng này sẽ được xác định bằng tích: p = p1p2. . . pn Nhận xét: Giả sử ta chọn L0,R0 và L0*,R0* sao cho L0L0* = L0' và R0R0* = R0'. Áp dụng n vòng mã hoá của DES để thu đựơc L1,. . ., Ln và R1,. . .,Rn. Khi đó không thể khẳng định rằng xác xuất để LiLi* = Li' và RiRi* = Ri' vơí mọi i, ( 1 i n )là p = p1. . .pn. Sở dĩ như vậy vì các bộ 48 trong bảng khoá K1. . .Kn không độc lập với nhau ( nếu n bộ 48 này được chọn ngẫu nhiên và độc lập với nhau thì khẳng định trên là đúng). Tuy vậy, ta vẫn hy vọng rằng, p1.. .pn là một ước lượng khá chính xác cho xác suất này. Cũng cần phải thấy rằng, các xác suất pi ở một đặc trưng sẽ xác định theo một cặp bản rõ tuỳ ý ( nhưng cố định) cho phép XOR xác định trước. Tại đây 48 bít khoá cho một vòng mã DES sẽ thay đổi trên toàn bộ 248 khả năng. Tuy nhiên thám mã lại đang cố gắng xác định một khoá cố định ( nhưng chưa biết). Anh ta sẽ chọn ngẫu nhiên các bản rõ ( sao cho chúng có các XOR xác định) với hy vọng rằng, các xác suất để các XOR trong n vòng mã phù hợp với các XOR được xác định trong đặc trưng phải khá gần với các p1,. . . ,pn tương ứng. Ví dụ đơn giản trên hình 3.10 là một đặc trưng một vòng, nó là cơ sở cho phép tấn công lên DES 3 vòng ( cũng như trước kia, ta dùng biểu diễn hexa). Hình 3.11 mô tả một đặc trưng một vòng khác. Hình 3.10. Đặc trưng một vòng.
Hình 3.11. Một đặc trưng một vòng khác.
Ta sẽ xem xét kỹ hơn các đặc trưng trong hình 3.11. Khi f(R0,K1) và f(R0*,K1) được tính, bước đầu tiên là phải mở rộng R0 và R0* . Kết quả của phép XOR hai mở rộng này là: 001100. . .0 Bởi vậy XOR vào của S1 là 001100 và các XOR vào của 7 hộp S khác đều là 000000. Các XOR của S2 tới S8 đều là 0000. XOR ra của S1 sẽ là 1110 với xác suất bằng 14/64 ( vì có thể tính được N1(001100,1110)= 14). Như vậy ta được: C' = 1110000000000000000000000000000 với xác suất bằng 14/64. Sử dụng P ta có : P(C) P(C*) = 00000000100000001000001000000000 dưới dạng hexa giá trị này là 0080820016. Khi giá trị này được XOR với L0' ta sẽ nhận được R1' chỉ ra với xác suất 14/64. Dĩ nhiên ta luôn có L1' = R0'.
Trong tấn công 6 vòng ta sẽ bắt đầu với L0R0, L0*R0*, L6R6, L6*R6*, trong đó đã chọn các bản rõ để L0' = 4008000016 và R0' = 0400000016 . Có thể biểu thị R6 như sau: R6 = L5 f(R5,K6) = R4 f(R5,K6) = L3 f(R3,K4) f(R5,K6)
R6' đã biết. Từ đặc trưng này ta thấy rằng L3' = 0400000016 và R3' = 4008000016 với xác suất1/16. Nếu đây là trường hợp thực tế thì XOR vào của cá hộp S trong vòng 4 có thể tính được theo hàm mở rộng bằng: 001000000000000001010000. . .0 Các XOR vào của S2,S5,S6,S7 và S8 đều là 000000 và bởi vậy ở vòng 4, các XOR ra của 5 hộp này đều là 0000. Điều đó có nghĩa là có thể tính các XOR ra của 5 hộp S này ở vòng 6 theo (3.4). Bởi vậy giả sử ta tính: C1'C2'C3'C4'C5'C6'C7'C8' = P-1(R6' 0400000016) trong đó mỗi Ci' là một xâu bít có độ dài 4. Khi đó, với xác suất 1/16 các xâu bít C2',C5', C6', C7' và C8' tương ứng là các XOR ra của S2,S5,S6,S7 và S8 ở vong 6. Các đầu ra của các hộp S ở vòng 6 có thể được tính là E2, E5, E6, E7, E8 và E2*, E5*, E6*, E7*và E8* , trong đó : E1 E2 E3 E4 E5 E6 E 7 E8 =E(R5) = E(L6) và E1* E2* E3* E4* E5* E6* E 7* E8* =E(R5*) = E(L6*) có thể được tính theo các bản mã như đã mô tả trên hình 3.13. Hình 3.13. DC đối với DES 6 vòng.
Каталог: files -> FileMonHoc FileMonHoc -> NGÂn hàng câu hỏi lập trình cơ BẢn nhóm câu hỏI 2 ĐIỂM FileMonHoc -> CHƯƠng 2 giới thiệu về LÝ thuyết số FileMonHoc -> CÁc hệ MẬt khoá CÔng khai kháC FileMonHoc -> BỘ MÔn duyệt chủ nhiệm Bộ môn FileMonHoc -> Khoa công nghệ thông tin cộng hòa xã HỘi chủ nghĩa việt nam FileMonHoc -> Chủ nhiệm Bộ môn Ngô Thành Long ĐỀ CƯƠng chi tiết bài giảNG FileMonHoc -> Chủ nhiệm Bộ môn Phan Nguyên Hải ĐỀ CƯƠng chi tiết bài giảNG FileMonHoc -> Khoa: CÔng nghệ thông tin cộng hòa xã HỘi chủ nghĩa việt nam FileMonHoc -> MẬt mã khóA ĐỐi xứng lý thuyết cơ bản của Shannon FileMonHoc -> Khoa công nghệ thông tin bài giảng LẬp trình cơ BẢn biên soạn tải về 0.52 Mb. Chia sẻ với bạn bè của bạn:
|