Chuẩn mã DỮ liệU
tải về 0.52 Mb.
|
- Điều hướng trang này:
- Hình 3.15. Phép tối ưu hoá thời gian - bộ nhớ.
- Hình 3.16. Tấn công DC lên DES 4 vong.
|
BÀI TẬP
3.1.Hãy chứng minh rằng phép giải mã DES có thể thực hiện bằng cách áp dụng thuật toán mã hoá DES cho bản rõ với bảng khoá đảo ngược. 3.2.Cho DES(x,K) là phép mã hoá DES của bản rõ x với khoá K. Giả sử y = DES(x,K) và y' = DES(c(x),c(K)) trong đó c(.) kí hiệu là phần bù theo các bít của biến. Hãy chứng minh rằng y' = c(y) ( tức là nếu lấy phần bù của bản rõ và khoá thì bản mã kết quả cũng là phần bù của bản mã ban đầu). Chú ý rằng kết quả trên có thể chứng minh được chỉ bằng cách sử dụng mô tả "mức cao" của DES - cấu trúc thực tế của các hộp S và các thành phần khác của hệ thống không ảnh hưởng tới kết quả này. 3.3.Mã kép là một cách để làm mạnh thêm cho DES: với hai khóa K1 và K2 cho trước, ta xác định y = eK2(eK1(x)) (dĩ nhiên đây chính là tích của DES với chính nó. Nếu hàm mã hoá eK2 giống như hàm giải mã dK1 thì K1 và K2 được gọi là các khoá đối ngẫu ( đây là trường hợp không mong muốn đối với phép mã kép vì bản mã kết quả lại trùng với bản rõ). Một khoá được gọi là tự đối ngẫu nếu nó đối ngẫu với chính nó. a/ Hãy chứng minh rằng nếu C0 gồm toàn các số 0 hoặc gồm toàn các số 1 và D0 cũng vậy thì K là tự đối ngẫu. b/ Hãy tự chứng minh rằng các khoá sau ( cho ở dạng hexa) là tự đối ngẫu: 0101010101010101 FEEFEFEFEFEFEFE 1F1F1F1F0E0E0E0E E0E0E0E0F1F1F1F1
E001E001F101F101 01E001E001F101F1 FE1FFE1FF0EFE0E 1FFE1FFE0EFE0EFE E01FE01FFF10FF10 1FE01FE00EF10EF1 3.4.Có thể tạo một mã xác thực thông báo bằng chế độ CFB cũng như chế độ CBC. Cho dãy các khối bản rõ x1. . .xn , giả sư ta xác định véc tơ khởi đầu IV là x1 . Sau đó mã hoá x2. . .xn bằng khoá K ở chế độ CFB để thu được y1...yn-1 ( chú ý rằng chỉ có n-1 khối bản mã ). Cuối cùng xác định eK(yn-1) làm MAC. Hãy chứng minh rằng MAC này đòng nhất với MAC được tạo trong phần 3.4.1. dùng chế độ CBC. 3.5.Giả sử một dãy các khối bản rõ x1. . .xn được mã hoá bằng DES, tạo ra các khối bản mã y1. . .y2 . Giả sử rằng một khối bản mã ( chẳng hạn yi) bị phát sai ( tức là có một số số 1 bị chuyển thành số 0 và ngược lại). Hãy chỉ ra rằng số các khối bản rõ bị giải mã không đúng bằng một nếu ta dùng các chế độ ECB và OFB để mã hoá; và bằng hai nếu dùng các chế độ CBC và CFB để mã hoá. 3.6.Bài tập này nhằm nghiên cứu một phép tối ưu hoá thời gian - bộ nhớ đơn giản đối với phép tấn công bản rõ chọn lọc. Giả sử có một hệ mật trong đó P = C = K và đạt được độ mật hoàn thiện. Khi đó eK(x) = eK1(x) có nghĩa là K = K1 . Kí hiệu P = Y = {y1,. . .,yN}. Cho x là bản rõ cố định. Định nghĩa hàm g: YY theo quy tắc g(y) = ey(x). Ta xác định một đồ thì có hướng G chứa tập đỉnh Y, trong đó tập cạnh chứa tất cả các cạnh có hướng có dạng (yi,g(yi)), 1 i N. a/ Hãy chứng minh rằng G gồm tất cả các chu trình có hướng không liên thông. b/ Cho T là một tham số thời gian mong muốn. Giả sử ta có một tập các phần tử Z = {z1,. . .,zm} Y sao cho với mỗi phần tử yi Y nằm trong một chu trình có độ dài tối đa là T hoặc tồn tại một phần tử zj yi sao cho khoảng cách tử yi tới zj trong G tối đa là T. Hãy chứng tỏ rằng tồn tại một tập Z như vậy sao cho: | Z | 2N/T và như vậy | Z | = 0(N/T). c/ Với mỗi zj Z ta xác định g-T(zj) là phần tử yi sao cho gT(yi) = zj , trong đó gT là một hàm gồm T phép lặp của g. Hãy xây dựng một bảng X gồm các cặp (zi,g-T(zj)) được sắp xếp theo các toạ độ đầu của chúng. Một mô tả giả mã của một thuật toán tìm K với y = eK(x) cho trước được trình bày ở hình 3.15. Hãy chứng tỏ thuật toán này tìm K trong tối đa là T bước ( bởi vậy cỡ của phép tối ưu hoá thời gian - bộ nhớ là 0(N)). Hình 3.15. Phép tối ưu hoá thời gian - bộ nhớ.
d/ Hãy mô tả thuật toán giải mã để xây dựng một tập Z mong muốn trong thời gian 0(NT) không dùng một mảng có kích thước N. 3.7. Hãy tính các xác suất của đặc trưng 3 vòng sau:
3.8. Sau đây là một phép tấn công vi sai đối với DES 4 vòng sử dụng đặc trưng sau ( đây là một trường hợp đặc biệt của đặc trưng được trình bày ở hình 3.10).
a/ Giả sử rằng thuật toán sau ( được nêu ở hình 3.16) được dùng để tính các tập test2,. . .,test8. Hãy chứng tỏ rằng Jj testj với 2 j 8. Hình 3.16. Tấn công DC lên DES 4 vong.
b/ Với các cặp bản rõ - mã sau, hãy xác định các bít khoá trong J2,...,J8.
c/ Hãy tính toàn bộ khoá ( 14 bít khoá còn lại cần phải xác định có thể tìm theo phương pháp tìm kiếm vét cạn). Каталог: 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:
|