Nghiên cứu, và thực hiện một số test để đánh giá độ an toàn của Des

áo thanh ghi chỉ là một hướng dẫn cho chương trình dịch và không liên quan gì đến các thanh ghi đặc biệt của máy. C không phải là một ngôn ngữ có kiểu mạnh mẽ theo nghĩa của PASCAL hoặc ALGOL/68. Nó tương đối thoải mái trong chuyển đổi dữ liệu nhưng không tự động chuyển các kiểu dữ liệu một cách phóng túng như của PL/I. Các chương trình dịch hiện có đều không đưa ra cơ chế kiểm tra chỉ số mảng, kiểu đối số… Mặc dù vậy, C vẫn còn tồn tại một số nhược điểm như một số phép toán có thứ tự thực hiện chưa đúng; một số phần cú pháp có thể làm tốt hơn; hiện có nhiều phiên bản của ngôn ngữ, chỉ khác nhau ở một vài chi tiết. Tóm lại, C vẫn tỏ ra là một ngôn ngữ cực kỳ hiệu quả và đầy sức diễn cảm đối với nhiều lĩnh vực ứng dụng lập trình. Hơn nữa, ta biết rằng hệ mật chuẩn hay chữ ký số luôn cần một bộ số rất lớn tức là kích cỡ của không gian khoá rất lớn khoảng trên 300 số thập phân. Do đó, ngôn ngữ C đủ mạnh để có thể đáp ứng được điều đó. Chương II Các hệ mật cổ điển II.1 Các hệ mật Mục tiêu cơ bản của mật mã là cho phép hai người, thường được đề cập đến như Alice và Bob, liên lạc trên kênh không an toàn theo cách mà đối thủ như Oscar không thể hiểu cái gì đang được nói. Kênh này có thể là đường điện thoại hoặc máy tính chẳng hạn. Định nghĩa : Hệ mật là một bộ năm thành phần (P,C,K,E,D) thoả mãn các điều kiện sau: P là tập hữu hạn các bản rõ có thể C là tập hữu hạn các bản mã có thể K là tập hữu hạn các khoá có thể Với mỗi k ẻ K, tồn tại một quy tắc mã ek ẻ E và một quy tắc giải mã tương ứng dk ẻ D. Mỗi ek : P đ C và dk : C đ P thoả mãn : dk(ek(x)) = x với mỗi bản rõ x ẻ P Điều kiện 4 là điều kiện chính. Nó có nghĩa là nếu bản rõ x ( plaintext ) được mã hoá sử ek và sau đó bản mã ( ciphertext ) kết quả được giải mã sử dụng dk thu được kết quả là bản rõ nguyên bản x. Giả sử, Alice muốn gửi cho Bob một thông báo nào đấy mà không cho người khác xem, thông báo đó có thể là bài tiếng Anh, dữ liệu sô v.v…có cấu trúc tuỳ ý. Thông tin đó được gọi là bản rõ. Alice và Bob phải thống nhất chọn một hệ mật và chọn khoá ngẫu nhiên kẻ K. Họ làm điều này một cách an toàn, chẳng hạn khi họ ở cùng một chỗ và không bị Oscar quan sát hoặc họ dùng kênh an toàn khi ở xa nhau. Sau đó, giả sử Alice muốn gửi thông báo cho Bob trên kênh không an toàn. Thông báo đó là dòng: x = x1, x2,…, xn với n ³ 1, xi ẻ P, 1Ê iÊ n Mỗi xi được mã hoá sử dụng quy tắc ek được định rõ bởi khoá định trước K. Từ đó, Alice tính: yi = ek( xi), với 1Ê iÊ n, và bản mã thu được là dòng: y = y1, y2,…, yn Alice gửi nó trên kênh, Oscar dù thấy bản mã này trên kênh không an toàn cũng không thể xác định được bản rõ là gì. Khi Bob nhận được y = y1, y2,…, yn, sẽ sử dụng dk để giả mã, thu được bản rõ ban đầu x = x1,x2,…,xn. Rõ ràng, với x1 ạ x2 thì ek(x1) ạ ek(x2). Nếu y = ek(x1)= ek(x2) khi x1 = x2 thì Bob không biết được y phải gải mã cho x1 hay x2. Chú ý rằng P = C thì mỗi hàm mã hoá ek là một phép hoán vị. Có nghĩa là, nếu tập các bản rõ và bản mã là tương tự thì mỗi hàm mã hóa chỉ sắp xếp ( hay hoán vị ) lại các phần tử của tập này. Oscar Alice Bộ mã hoá Bộ giải mã Bob Kênh an toàn Nguồn khoá X y y x k k Sau đây là các hệ mật mà Alice và Bob có thể dùng. II.1.1 Mật mã dịch chuyển Định nghĩa : Cho P = C = K = Z26 Với 0 Ê k Ê 25, xác định : ek(x) = x + k mod 26 và dk(y) = y + k mod 26 với x,y ẻ Z26 Ví dụ : Giả sử khoá k = 11 và bản rõ là : WEWILLMEETATMIDNIGHT Trước hết, phải số hoá nó thu được như sau 22 4 22 8 11 11 12 4 4 19 0 19 12 8 3 13 8 6 7 19 Tiếp theo, cộng 11 vào mỗi giá trị, rút gọn mỗi tổng theo modulo 26 7 15 7 19 22 22 23 15 15 4 11 4 23 19 14 24 19 17 18 4 Cuối cùng chuyển dãy số thành dãy chữ H P H T W W X T P E L E X T O Y T R S E Để giải mã, Bob thực hiện theo trình tự ngược lại. Trước hết chuyển bản mã thành dãy các số, tiếp theo trừ mỗi giá trị cho 11( rút gọn cho modulo 26) và cuối cùng chuyển dãy số thành dãy chữ. Một hệ mật được sử dụng trong thực tế, nó phải thoả mãn hai tính chất sau: ek và dk khi tác động vào x hoặc y là có hiệu quả tính toán Một đối thủ khi có bản mã y, sẽ không thể xác định khoá k được sử dụng hoặc bản rõ x II.1.2 Mật mã thay thế Định nghĩa : Cho P = C = Z26 , K gồm tất cả các hoán vị trên tập 26 phần tử từ 0,1,…,25. Với mỗi hoán vị p ẻ K, xác định : ep(x) = p(x) và dp(y) = p-1(y) với p-1 là hoán vị ngược của p Ví dụ : Abcdefghij Klmnopqrst Uvwxyz Xnyahpogzq Wbtsflrcvm Uekjdi p = ep(a) = p(a) = x ep(b) = p(b) = n Abcdefghij Klmnopqrst Uvwxyz Dlryvohezx Wptbgfjqnm Uskaci p-1 = dp(x) = p-1(x) = a và dp(n) = p-1(n) = b II.1.3 Mật mã Affine Mật mã dịch chuyể là trường hợp đặc biệt của mật mã thay thế. Mật mã affine cũng là một trường hợp của mật mã thay thế. Trong mật mã affine, hàm mã có dạng : E(x) = ax + b mod 26 với a,b ẻ Z26 Hàm này được gọi là hàm affine Khi a = 1 ta được mật mã dịch chuyển. Để giải mã được, hàm affine phải song ánh, nghĩa là với mọi y ẻ Z26 , phương trình ax + b = y (mod 26) phải có nghiệm duy nhất. Đồng dư thức này tương đối với : ax = y – b (mod 26). Phương trình này có nghiệm duy nhất khi và chỉ khi (a,26) = 1. Để tìm nghiệm x, trước tiên ta tìm số a-1 ẻ a26 thoả mãn : a.a-1 = 1 mod 26 . Khi đó d(y) = a-1(y - b) mod (26) Định nghĩa : Cho P = C = Z26 và K = {(a,b) ẻ Z26 * Z26 : (a,26) = 1} với k = (a,b) ẻ K, xác định : ek(x) = ax + b mod 26 và dk(y) = a-1(y - b) mod 26 với x,y ẻ Z26 II.1.4 Mật mã Vigenere Mật mã Vigenere là mật mã đa biểu, tức là một ký tự mã có thể được ánh xạ thành nhiều ký tự khác. Định nghĩa : Cho m là số nguyên dương cố định, P = C = K = (Z26)m với khoá K = (k1,k2,….,km), chúng ta xác định : ek(x1,x2,….,xm) = (x1+k1,x2+k2,….,xm+km) và dk(y1,y2,….,ym) = (y1- k1,y2- k2,….,ym- km) tất cả các hoạt động được tiến hành trong Z26 Ví dụ : m = 6, khoá k = CIPHER = (2,8,15,7,4,17) Thông báo : THISCRIPTOSYSTEMISNOTSECURE Ta chuyển thành số : 19 7 8 18 2 17 24 15 19 14 19 18 19 4 2 8 15 7 4 17 2 8 15 7 4 2 8 15 21 15 23 25 6 8 0 23 8 21 23 20 1 19 2 8 18 13 14 19 18 4 20 17 4 7 4 17 2 8 15 7 4 2 8 15 19 12 19 15 22 8 25 8 22 25 19 Đưa về chữ : V P X Z G I A X I V W P U B T T M J P W I Z I T W Z T II.1.5 Mật mã hoán vị ý tưởng của mật mã hoán vị là giữ các kí tự trên bản rõ không thay đổi, nhưng thay đổi vị trí của chúng bằng cách sắp xếp lại Định nghĩa : Cho m là số nguyên dương cố định, P = C = (Z26)m và K gồm tất cả các hoán vị của {1,2,….,m}. Với mỗi khoá p, xác định ep(x1,….,xm) = (xp(1),….,xp(m)) và dp(y1,….,ym) = (yp (1),….,yp (m)) với p-1 là hoán vị ngược của p Ví dụ : Giả sử m = 6 và khoá là hoán vị sau: 1 2 3 4 5 6 3 5 1 6 4 2 p = và hoán vị ngược của p 1 2 3 4 5 6 3 6 1 5 2 4 p-1 = Thông báo : H O O F C H I S M I N H Trước tiên gom thành nhóm 6 phần tử : H O O F C H I S M I N H x1 = h, x2 = o, x3 = o, x4 = f, x5 = c, x6 = h khi đó nhóm thứ nhất được mã thành x3 x5 x1 x6 x4 x2 = O C H H F O tương tự, nhóm thứ hai là : M N I H I S Vậy bản mã là : O C H H F O M N I H I S II.1.6 Mật mã dòng ý tưởng cơ bản là sinh dòng khoá z = z1 z2 … và mã dòng rõ x = x1 x2 … theo cách : y = y1 y2… = ez1(x1) ez2(x2)… Mật mã dòng hoạt động như sau : giả sử k là khoá và x1 x2 … là dòng rõ, fi là hàm của k và i là một đặc trưng rõ. zi = fi(k,x1,….,xi-1) (xi được chon trước của hai bên) yi = ezi(xi) i = 2,3,… Do đó, để mã dòng rõ x1 x2 … ta tính liên tiếp : z1,y1,z2,y2,… Việc giải mã được làm tương tự z1,x1,z2,x2,… Nếu zi = k với mọi i thì ta có thể nghĩ mật mã khối như trường hợp đặc biệt của mật mã dòng . Sau đây là một số trường hợp đặc biệt quan trọng của mật mã dòng : Mật mã đồng bộ zi = fi(k) với i = 1,2,… Mật mã tuần hoàn với chu kỳ d : zi+d = zi , "i ³ 1 Mật mã dòng được chú ý nhiều hơn cả là trường hợp P = C = Z2. Khi đó phép mã hoá và giải mã là cộng theo modulo 2. e2(x) = x+z mod 2 d2(y) = y- z mod 2 Mật mã tự động Định nghĩa : P = C = K = Z26, z1 = k,zi = xi-1 (i³2) với 0 Ê z Ê 25, xác định : ez(x) = x+z mod 26 dz(y) = y- z mod 26 với x,y ẻ Z26 Ví dụ : k = 8 , thông báo là : H A I R P H O N G F Trước tiên, chuyển thông báo rõ thành dãy số nguyên 7 0 8 17 15 7 14 13 6 5 Dòng khoá như sau : 8 7 0 8 17 15 7 14 13 6 5 Cộng dãy khoá và dãy rõ : yi = xi + zi mod 26, với i= 1,2,… ta được 15 7 8 25 6 22 21 1 19 11 và chuyển thành chữ : P H I Z G W V B T L Với bản mã này và k = 8, ta giải mã như sau : Chuyển bản mã thành dãy số và trừ lần lượt 15 7 8 25 6 22 21 1 19 11 8 7 0 8 17 15 7 14 13 6 7 0 8 17 15 7 14 13 6 5 chuyển dãy số thành dãy chữ : H A I R P H O N G F Trên đây là các hệ mật cổ điển thường được dùng để mã hoá thông tin khi muốn gửi đi trên các kênh không an toàn hay thông tin đang được lưu trữ cố định. Chương III Chuẩn mã dữ liệu DES ( Data Ecryption STandard ) Chuẩn mã dữ liệu ( Data Ecryption Standard ) được uỷ ban tiêu chuẩn quốc gia Hoa Kỳ ( the National Bureau ò Standard ) chấp nhận và được công bố lần đầu tiên trên công báo liên bang ngày 17 – 03 – 1975. Sau các cuộc thảo luận công khai, DES được chấp nhận như cho các ứng dụng bảo mật vào ngày 15–01- 1977. DES trở thành một hệ bảo mật được sử dụng rộng rãi nhất trên thế giới. III.1 Mô tả DES DES mã hoá một dòng bit rõ x có độ dài 64 với k là dòng 56 bit, đưa ra bản mã y cũng là một dãy bit có độ dài 64. ẵxẵ = 64, ẵyẵ = 64,ẵkẵ = 56 IP 58 50 42 34 26 18 10 2 60 52 44 36 28 20 12 4 62 54 46 38 30 22 14 6 64 56 48 40 32 24 16 8 57 49 41 33 25 17 9 1 59 51 43 35 27 19 11 3 61 53 45 37 29 21 13 5 63 55 47 39 31 23 15 7 III.1.1 Thuật toán mã hoá Gồm ba giai đoạn : Cho bản rõ x, ta tinh được x0 qua việc hoán vị các bit của x theo hoán vị đầu IP : x0 = IP( x ) = L0R0 L0 là 32 bit đầu tiên của x0 còn R0 là 32 bit còn lại, và IP là hoán vị đầu cố định. b. Lặp 16 vòng : Chúng ta tính LiRi với 1 Ê i Ê 16, theo quy tắc sau : Li = Ri-1 Ri = Li-1 ^ f( Ri-1, Ki ) Dấu (^) thể hiện phép toán “hoặc loại trừ” hai dãy bit, f là một hàm mà chúng ta sẽ đề cập đến sau, ki là những dãy dài 48 bit được tạo từ khoá K bởi thuật toán riêng. áp dụng phép hoán vị ngược IP-1 cho L16R16 ta tính được bản mã y : y = IP-1( L16 R16 ) , chú ý đảo ngược vị trí của L16 và R16. Li-1 Ri-1 Li Ri f + ki IP-1 40 8 48 16 56 24 64 32 39 7 47 15 55 23 63 31 38 6 46 14 54 22 62 30 37 5 44 13 53 21 60 29 36 4 43 12 52 20 59 28 35 3 42 11 51 19 58 27 34 2 41 10 50 18 57 26 33 1 40 9 49 17 56 25 III.1.2 Hàm f( A, J ) Đầu vào của hàm f là đối số A, một dãy 32 bit, và đối số thứ hai là J, là dãy 48 bit, kết quả thu được là dãy có độ dài 32 bit. Các bước được thực hiện : E 32 1 2 3 4 5 4 5 6 7 8 9 8 9 10 11 12 13 12 13 14 15 16 17 16 17 18 19 20 21 20 21 22 23 24 25 24 25 26 27 28 29 28 29 30 31 32 1 Mở rộng A từ 32 bit thành 48 bit theo hàm mở rộng E. E( A ) gồm 32 bit của A, được hoán vị theo cách cụ thể và với 16 bit của các bit xuất hiện hai lần. Tính B = E( A ) ^ J và kết quả B được tách thành các khối 6 bit liên tiếp. B = B1 B2 B3 B4 B5 B6 B7 B8 Bước tiếp theo sử dụng 8 hộp S :S1,….,S8. Mỗi hộp Si là một mảng hai chiều 4*16, mỗi dòng chứa các giá trị từ 0 á 15. Ta có đầu vào Bj là một dãy 6 bit Bj = b1 b2 b3 b4 b5 b6 b7 b8. hai bit b1 b6 xác định biểu diễn nhị phân của r là chỉ số dòng của Sj ( 0 Ê r Ê 3), và 4 bit b2 b3 b4 b5 xác định biểu diễn nhị phân của C là chỉ số cột của Sj ( 0 Ê c Ê15 ). Sau đó, Si ( Bj ) là số nằm trong toạ độ ( r, C ) gồm 4 bít. Ta có kí hiệu : Cj = Sj ( Bj ), với 1 Ê j Ê 8 d. Dòng bit C = C1…C8 với độ dài 32 bit được đổi chỗ theo hoán vị P , kết quả dãy P( C ) chính là f( A, J ). F( A, J ) = P( C ) Hàm f được thể hiện trong hình dưới đây : A F(A) J E + B1 B2 B3 B4 B5 B6 B7 B8 S1 S2 S3 S4 S5 S6 S7 S8 C1 C2 C3 C4 C5 C6 C7 C8 P F( A, J ) 8 hộp S và hoán vị P : S1 14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0 15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13 S2 15 1 8 14 6 11 3 4 9 7 2 13 12 0 5 10 3 13 4 7 15 2 8 14 12 0 1 10 6 9 11 5 0 14 7 11 10 4 13 1 5 8 12 6 9 3 2 15 13 8 10 1 3 15 4 2 11 6 7 12 0 5 14 9 S3 10 0 9 14 6 3 15 5 1 13 12 7 11 4 12 8 13 7 0 9 3 4 6 10 2 8 5 14 12 11 15 1 13 6 4 9 8 15 3 0 11 1 2 12 5 10 14 7 3 10 13 0 6 9 8 7 4 15 14 3 11 5 2 12 S4 7 13 4 3 0 6 9 10 1 2 8 5 11 12 4 15 13 8 11 5 6 15 0 3 4 7 2 12 1 10 14 9 10 6 9 0 12 11 7 13 15 1 3 14 5 2 8 4 3 15 0 6 10 1 13 8 9 4 5 11 12 7 2 14 S5 2 12 4 1 7 10 11 6 8 5 3 15 13 0 14 9 14 11 2 12 4 7 13 1 5 0 15 10 3 9 8 6 4 2 1 11 10 13 7 8 15 9 12 5 6 3 0 14 11 8 12 7 1 14 2 13 6 15 0 9 10 4 5 3 S6 12 1 10 14 9 2 6 8 0 13 3 4 14 7 5 11 10 15 4 2 7 12 9 5 6 1 13 14 0 11 3 8 9 14 15 5 2 8 12 3 7 0 4 10 1 13 11 6 4 3 2 12 9 5 15 10 11 14 1 7 6 0 8 13 S7 4 11 2 14 15 0 8 13 3 12 9 7 5 10 6 1 13 0 11 7 4 9 1 10 14 3 5 12 2 15 8 6 1 4 11 13 12 3 7 14 10 15 6 8 0 5 9 2 6 11 13 8 1 4 10 7 9 5 0 15 14 2 3 12 S8 13 2 8 4 6 15 11 1 10 9 3 14 5 0 12 7 1 15 3 8 10 3 7 4 12 5 6 11 0 14 9 2 7 11 4 1 9 12 14 2 0 6 10 13 15 3 5 8 2 1 14 7 4 10 8 13 15 12 9 0 3 5 6 11 P 16 7 20 21 29 12 28 17 1 15 23 26 5 18 31 10 2 8 24 14 32 27 3 9 19 13 30 6 22 11 4 25 Hoán vị P : III.1.3 Lược đồ tạo hệ thống khoá Cuối cùng ta cần mô tả sự tính toán lược đồ khoá từ khoá K. Khoá là một dãy 64 bit với 56 bit đầu vào và 8 bit là các bit kiểm tra (là các bit ở vị trí thứ 8, 16,24,32, 48, 56, 64). Các bit kiểm tra này sẽ được bỏ qua trong quá trình tạo khoá. Cho 56 bit này hoán vị theo bảng PC-1 ta sẽ tìm được C0D0 với C0 là 28 bit đầu tiên của PC-1, D0 là 28 bit còn lại. PC-1( K ) = C0D0, với i = 1á16 ta tính Ci = LSi( Ci- 1) Di = LSi( Di-1 ) LSi thể hiện phép dịch trái quay vòng một hoặc hai bit, phụ thuộc và giá trị của i, dịch một bit nếu i = 1,2,9,16 và dịch hai bit với các giá trị còn lại của i. Ki được tính theo CiDi qua bảng hoán vị PC-2 Ki = PC-2( CiDi ) Ta có các bảng PC-1 và PC-2 : PC-1 57 49 41 33 25 17 9 1 58 50 42 34 26 18 10 2 59 51 43 35 27 19 11 3 60 52 44 36 63 55 47 39 31 23 15 7 62 54 46 38 30 22 14 6 61 53 45 37 29 21 13 5 28 20 12 4 PC-2 14 17 11 24 1 5 3 28 15 6 21 10 23 19 12 4 26 8 16 7 27 20 13 2 41 52 31 37 47 55 30 40 51 45 33 48 44 49 39 56 34 53 46 42 50 36 29 32 Như vậy ta đã có một thuật toán hoàn chỉnh về mã hoá dữ liệu theo tiêu chuẩn DES. III.2 Giải mã DES Tương tự như mã hoá, để giải mã một dãy kí tự đã bị mã hoá ta cũng làm theo trình tự các bước như trên. Tuy nhiên, hệ thống khoá lúc này đã được tạo theo chiều ngược lại. III.2.1 Thuật toán giải mã Có bản mã y và khoá K y0 = IP(y) = R0’ L0’ = R16L16 với i = 1,2,….,16 Thực hiện : Li’ = R’i-1 và Ri = L’i-1 ^ f( R’i-1, k17-i ) x0 = ( R’16, L’16 ) x = IP-1( x0 ) III.2.2 Chứng minh thuật toán Có bản mã y: y0 = IP(y) = IP(IP-1(R16L16)) = R16L16 =L’0 R’0 Vậy L’0 = R16, R’0 = L16, với i = 1 L’1 = R’0 = L16 = R15 R’1 = L’0 ^ f(R’0,k16) = R16 ^ f(L16,k16) = L15 ^ f(R15,k16) = L15 Tóm lại : L’1 = R15, R’1 = L15 Tương tự như vậy cho đến khi I = 16, ta sẽ có L’16 = R’15 = L1 = R0 R’16 = L’15 ^ f(R’15,k1) = R’1 ^ f(L1,k1) = L0 ^ f(R0,k1) ^ f(R0,k1) = L0 L’16 = R0, R’16 = L0 x = IP-1(R’16L’16) = IP-1(R0L0) = IP-1(x0) Từ đó ta thấy, thuật toán giải mã chỉ khác với thuật toán mã hoá ở chỗ tạo hệ thống khoá. Nếu mã hoá tạo từ k1,….,k16 thì giải mã tạo hệ thống khoá từ k16,….,k1 III.3 DES trong thực tế III.3.1 ứng dụng Mặc dù việc mô tả DES khá dài thì DES được thực hiện rất hiệu quả trong cả phần cứng lẫn phần mềm. Những thực hiện phần cứng hiện thời có thể đạt được tốc độ mã hoá cự nhanh. Hãng Digital Equipment Corporation thông báo tại CRYTO’92 rằng họ vừa chế tạo được một chip với 50K transistors có thể mã hoá với tốc độ 1Gb/s nhờ sử dụng đồng hồ tốc độ là 250MHz. Trong năm 1991, có 45 phần cứng và chương trình cài sẵn thi hành DES đã được Uỷ ban tieuu chuẩn quốc gia Mĩ ( the National Bureau of Standards ) tin cậy. Một ứng dụng quan trọng của DES là ứng dụng cho văn bản giao dịch ngân hàng sử dụng các tiêu chuẩn được hiệp hội các ngân hàng Mĩ phát triển, DES được sử dụng để mã hoá các số nhận dạng cá nhân ( PINs ) và văn bản về tàI khoản được máy thu ngân thực hiện ( ATMs ). III.3.2 Các mẫu hoạt động của DES Đầu vào của DES chỉ có 8 byte, vậy mà văn bản cần mã hoá lại có thể rất dài, cỡ vài Kbyte chẳng hạn. Để giải quyết vấn đề này, người ta đẫ đề ra bốn mẫu hoạt động cho DES là : Electronic CodeBook mode ( ECB ), Cipher FeedBack mode ( CFB ), Cipher Block Chaining mode ( CBC ) và Output FeedBack mode ( OFB ). + ECB : Đây là việc sử dụng bình thường mật mã khối. Trước hết chia dãy ký tự trong thông báo thành các khối 8 ký tự liên tiếp x1,x2,…, mỗi xi đều được mã bởi cùng khoá k, cuối cùng được một dãy các khối mã 8 bit là y1,y2,… Việc giải mã được tiến hành theo trình tự ngược lại. + CBC : Ta cũng chia thông báo thành những khối 8 byte như trên để được x1,x2,… Cho IV là vector khởi điểm dàI 64 bit ( 8 byte ). Bắt đầu là việc gán y0 = IV, sau đó tính yi = ek(yi-1 ^ xi), với i = 1,2,… Quá trình giải mã như sau : y0 = IV xi = yi-1 ^ dk(yi), với i = 1,2,… + OFB và CFB : ý tưởng chính là sinh ra một dòng khoá, sau đó XOR nó với thông báo như mật mã dòng. - Đối với OFB, cụ thể như sau : z0 = IV, zi = ek(zi-1), i = 1,2,… yi = xi ^ zi, i = 1,2,… Việc giải mã như đối với mật mã dòng. - Đối với CFB, có sự khác nhau nhất định y0 = IV, zi = ek(y0) yi = xi ^ zi, zi+1 = ek(yi), i= 1,2,… Việc giải mã thực hiện như sau : y0 = IV, z1 = ek(y0) xi = yi ^ zi, zi+1 = ek(yi), i= 1,2,… ECB và OFB : việc thay đổi một khối 64 bit rõ xi khiến cho khối mã yi tương ứng cũng thay đổi theo, nhưng các khối mã khác không bị ảnh hưởng. Trong một vài hoàn cảnh, đây là một tính chất tốt, chẳng hạn OFB thường được dùng để mã thông tinh truyền qua vệ tinh. CBC và CFB : khối rõ xi bị thay đổi thì yi và tất cả các khối mã tiếp theo sẽ bị ảnh hưởng. Tính chất này có nghĩa là CBC, CFB có ích cho mục đích xác thực. Chương IV Đánh giá độ an toàn Khi ta mã hoá thông tin bằng các hệ mật không có nghĩa là ta đã yên tâm thông tin đó không bị mất mát, sai lệch so với ban đầu khi lưu trữ hay truyền qua mạng. Mà ta phải có biện pháp kiểm tra xem hệ mật đó có an toàn không. Đối với mã chuẩn dữ liệu DES cũng vậy, khi mã hoá các thông tin đồng thời ta cũng phải kiểm tra độ an toàn của nó. Có hai cách để kiểm tra độ an toàn của DES, đó là : phương pháp tấn công DES và phương pháp đánh giá các tính chất của DES. Tuy nhiên trong đề tài nay tập trung nghiên cứu phương pháp đánh giá các tính chất của DES để kiểm tra độ an toàn. IV.1 Phương pháp lượng sai tấn công DES 3 vòng Có nghĩa là ta tấn công vào DES, nếu phá vỡ DES thì có nghĩa là không an toàn. Phương pháp lượng sai tấn công DES là phương pháp nổi tiếng do Biham và Shamir giới thiệu. đây là sự tấn công bản rỗ lựa chọn. Mặc dù nó còn đòi hỏi khá nhiều cặp bản rõ lựa chọn trong việc phá vỡ đủ 16 vòng DES thông thường, phương pháp này thành công trong việc phã vỡ DES nếu số vòng giảm xuống. Ví dụ 8 vòng DES có thể bị phá vỡ trong vài phút trên một PC nhỏ với một số không quá nhiều các bản rõ lựa chọn. Để hiểu phương pháp lượng sai, chúng ta nghiên cứu trường hợp đơn giản nhất là tấn công DES 3 vòng. IV.1.1 Một số khái niệm Lượng sai bao gồm việc so sánh XOR hai bản rõ với XOR hai bản mã tuơng ứng. Chúng ta xem xét hai bản rõ L0R0 và L0*R0* với một giá trị XOR đặc biệt L0’ R0’ = L0R0 ^ L0*R0*. Ta có các khái niệm sau: Định nghĩa 1 : Cho Si là một hộp S ( 1 ≤ j ≤ 8 ). Xét cặp có thứ thự ( Bj,Bj*) với | Bj | = | Bj* | = 6. Ta nói rằng XOR đầu vào của Sj là Bj ^ Bj* và XOR đầu ra của Sj là Sj (Bj ) ^ Sj (Bj*) Chú ý rằng XOR đầu vào là một dãy bit có độ dài là 6 còn XOR đầu ra là dãy có độ dài 4 bit. Định nghĩa 2 : Với mọi Bj’ € {Z2}6. ta định nghĩa Δ(Bj’) = {(Bj, Bj*) : Bj ^ Bj* = Bj’ } Với mỗi cặp trong Δ(Bj’), có thể tính XOR đầu ra của Sj và lập bảng kết quả phân phối. Định nghĩa 3 : Với 1 ≤ j ≤ 8, dãy các Bj’ dài 6 bit, Cj’ dài 4 bit, ta định nghĩa : INj(Bj’, Cj’ ) = {Bj € {Z2}6 : Sj (Bj ) ^ Sj(Bj ^ Bj’ ) = Cj’ } Và INj(Bj’, Cj’ ) = | INj(Bj’, Cj’ ) | Thực ra, INj(Bj’, Cj’ ) đếm số cặp XOR đầu vào là Bj’ và có XOR đầu ra tương ứng Cj’ cho mỗi hộp Sj. Từ các tập INj(Bj’, Cj’ ) ta có thể thu được các cặp có XOR đầu vào đặc biệt gây ra các XOR đầu ra đặc biệt. Định nghĩa 4 : Giả sử Ej , Ej* là các dãy 6 bit, Cj’ là dãy 4 bit. Ta định nghĩa : Testj(Ej, Ej*, Cj’) = { Bj ^ Ej : Bj € INj(Ej’, Cj’ ) } trong đó Ej’ = Ej ^ Ej* Hay nói cách khác : Testj(Ej, Ej*, Cj’) = Ej ^INj(Ej’, Cj’ ) Định lý : Giả sử Ej , Ej* là các đầu vào của Sj và XOR đầu ra tương ứng của Sj là Cj’, ký hiệu Ej’ = Ej ^ Ej*. Khi đó, các bit khoá của Jj phải xuất hiện trong tập Testj(Ej, Ej*, Cj’) IV.1.2 Tấn công DES 3 vòng Việc thám mã DES 3 vòng bằng phương pháp lượng sai gắn với việc lựa chọn các bản rõ cho DES. Chúng ta bắt đầu với một cặp bản rõ và bản mã L0R0 , L0* R0*, L3R3 và L3* R3*. R3 sẽ được tính như sau : R3 = L2 ^ f(R2, k3) = R1 ^ f(R2, k3) = L0 ^ f(R0, k1) ^ f(R2, k3) Tương tự ta có : R3* = L0* ^ f(R0*, k1) ^ f(R2*, k3) Do đó : R3’ = R3 ^ R3* = L0’ ^ f(R0, k1) ^ f(R0*, k1) ^ f(R2, k3) ^ f(R2*, k3) Ta chọn x, x* sao cho R0 = R0* có nghĩa là R0’ = 00…0 Khi đó f(R0, k1) = f(R0*, k1) Vì thế R3’ = L0’ ^ f(R2, k3) ^ f(R2*, k3) Mặt khác, R3’ có thể tìm ra được từ hai bản mã và L0’ tìm ra từ hai bản rõ. Từ đó, có thể tính f(R2, k3) ^ f(R2*, k3) như sau : f(R2, k3) ^ f(R2*, k3) = R3’ ^ L0’ Mà f(R2, k3) = P(C) f(R2*, k3) = P(C*) Với C và C* là đầu ra của 8 hộp S. → P(C) ^ P(C*) = R3’ ^ L0’ → P(C ^ C*) = R3’ ^ L0’ P(C’) = R3’ ^ L0’ hay C’ = P-1(R3’ ^ L0’) Đó chính là XOR đầu ra đối với 8 hộp trong 3 vòng. Từ E = E1E2….E8; E = E1 *E2 *….E8 * và C’ = C1’C2’….C8’ ta xây dựng được các tập Testj(Ej, Ej*, Cj’), với j = 1 ữ 8, chứa các giá trị đúng của J1J2….J8( chứa 48 bit của khoá DES ở vòng 3 ). Từ J1J2….J8 đưa qua bảng Round 3 ta sẽ tìm được vị trí chính xác của 48 bit khoá ban đầu. Kiểu tấn công này sẽ dùng một vài bộ ba E, E*, C’. Ta sẽ thiết lập 8 cụm đếm và do đó xác định được 48 bit trong khoá k3 ( khoá của vòng thứ 3 ). Còn lại 8 bit khoá chưa được xác định. Đến đây ta sẽ dùng cách thử toàn bộ 28 = 256 trường hợp có thể cho các bit còn lại. IV.1.3 Thuật toán thám mã DES 3 vòng : Đầu vào là L0R0, L0*R0*, L3R3 và L3*R3* Bước 1 : Tính C’ = P-1(R3’ ^ L3’) Bước 2 : Tính E = E(L3) và E* = E(L3*) Bước 3 : j = 1 ữ 8 tính testj(E, E*, C’) Bước 4 : i = 1ữ255 (giá trị của 8 bit còn đặt dấu ? ) Tìm k (| k | = 56 ) sao cho ek (x) = y và ek (x*) = y* Khi đã tìm được 56 bit khoá, ta cần tìm nốt 8 bit kiểm tra của dãy 64 bit khoá. Tuy nhiên, do mã ASCII mở rộng đã bỏ bit kiểm tra cho nên trong một số trường hợp bít kiểm tra đó không đúng là của khoá cần tìm. Vì DES không dùng đến các bit kiểm tra để mã hoá cho nên khoá tìm ra vẫn là đúng ( đúng chính xác 56 bit ) IV.2 Phương pháp đánh giá tính chất của DES Để đánh giá độ an toàn của DES ta có thể kiểm tra các tính chất của DES, nếu thoả mãn điều kiện thì kết luận là an toàn. Các tính chất đó là: Số trung bình các bit ra thay đổi khi thay đổi một bit vào. Mức độ đầy đủ Mức độ hiệu quả dồn nén Mức độ tiêu chuẩn dồn nén chặt IV.2.1 Các định nghĩa Ta xét: vector x = (x1,…,xn) € (GF(2))n, vector x(i) € (GF(2))n với vector x(i) đạt được bằng cách lấy phần bù bit thứ i của vector x (với i = 1 ữ n ) Trọng số Hamming w(x) của x là số các thành phần khác 0 của vector x - Hàm f : (GF(2))n → (GF(2))m của n bit vào và m bit ra được gọi là đầy đủ (the degree of completeness ) nếu mỗi bit ra phụ thuộc vào mỗi bit vào: với mọi i = 1 ữ n và j = 1 ữ m tồn tại x € (GF(2))n với ( f ( x(i) ))j ≠ ( f ( x))j có nghĩa là tồn tại vector x € (GF(2))n sao cho khi thay đổi bit vào thứ i thì sẽ làm thay đổi bit ra thứ j ( bit ra thứ j phụ thuộc vào bit vào thứ i ) - Hàm f : (GF(2))n → (GF(2))m có hiệu quả dồn nén ( the avalanche effect ) nếu trung bình của ẵ các bit ra thay đổi mỗi khi một bit vào đơn được thay đổi: với i = 1ữ n - Hàm f : (GF(2))n → (GF(2))m thoả mãn tiêu chuẩn dồn nén chặt ( the strict avalanche criterion ) nếu mỗi bit ra thay đổi với xác suât ẵ mỗi khi một bit vào đơn được thay đổi: Với mọi i = 1 ữ n và j = 1 ữ m Pr( ( f (x(i)))j ≠ ( f (x))j ) = ẵ - Ma trận phụ thuộc của hàm f : (GF(2))n → (GF(2))m là ma trận A cỡ n*m mà phần tử ai j biểu thị số các dữ liệu vào mà khi thay đổi bit vào thứ i dẫn đến sự thay đổi của bit ra thứ j : ai j = # { x € GF(2))n | ( f (x(i)))j ≠ ( f (x))j } với i = 1 ữ n và j = 1 ữ m - Ma trận khoảng cách của hàm f : (GF(2))n → (GF(2))m là ma trận B cỡ n*(m+1) mà phần tử bi j biểu thị số các dữ liệu vào mà khi thay đổi bit vào thứ i dẫn đến sự thay đổi j bit ra. bi j = # { x € GF(2))n | w( f (x(i)) - f (x) ) = j } với i = 1 ữ n và j = 1 ữ m Tuy nhiên, việc tính toán ma trận khoảng cách và ma trận phụ thuộc cho tất cả các dữ liệu vào là không thể được, trừ khi số các dữ liệu vào nhỏ . Vì