Nghiên cứu & thực hiện Một số TEST để đánh giá độ an toàn của DES

với rất nhiều những mạng mang tính bộ phận( có thể là LAN( Local Area Network- Mạng cục bộ) hoặc WAN( Wide Area Network- Mạng diện rộng) hoặc MAN(Metropolitan Area Network- Mạng vùng Thành phố)). Nhiều dịch vụ của mạng như : thư điện tử, chuyển và nhận tiền, thương mại điện tử… đã được sử dụng rộng rãi. Khi tham gia vào mạng, vấn đề quan trọng đặt ra là làm thế nào để bảo mật thông tin, dữ liệu. Thông tin trên mạng dù đang chuyển hay được lưu trữ đều cần được bảo vệ. Hoặc các thông tin đó cần được giữ bí mật hoặc chúng phải cho phép người ta kiểm tra để tin tưởng rằng chúng không bị sửa đổi so với dạng nguyên thuỷ của mình. Trước yêu cầu đó một số giải pháp kỹ thuật đã được xây dựng nhằm đảm bảo tính an toàn dữ liệu tại nơi lưu trữ cũng như dữ liệu được truyền qua mạng. Các giải pháp đó là người ta sử dụng các hệ mật. Có các hệ mật cổ điển như : mật mã thay thế, mật mã dịch chuyển, mật mã Affine, mật mã Vigenere…, và các hệ mật hiện đại như : mật mã khoá công khai RSA, chữ ký số, chuẩn mã dữ liệu DES… Nhưng khi sử dụng các hệ mật để mã hoá dữ liệu cần phải quan tâm đến độ an toàn của các hệ mật mà mình đã sử dụng. Trong đề tài này tôi nghiên cứu về cách đánh giá độ an toàn của chuẩn mã dữ liệu DES . Để kiểm tra đánh giá độ an toàn của DES ta có hai cách. Đó 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. Sự khác nhau giữa hai phương pháp này là một phương pháp thì tấn công trực tiếp vào DES, nếu phá vỡ DES thì ta có thể nói rằng DES không an toàn và ngược lại; phương pháp đánh giá tính chất thì kiểm tra các tính chất của DES, nếu thoả mãn điều kiện thì có thể nói là an toàn và ngược lại. Và tôi đi sâu nghiên cứu phương pháp đánh giá các tính chất của DES. Chương I TổNG QUAN Về NGÔN NGữ C I.1. Lịch sử hình thành và phát triển Ngôn ngữ C do Brian W.Kernighan và Dennis M.Ritchie phát triển vào đầu những năm 70 tại phòng thí nghiệm BELL ( Hoa Kỳ) với mục đích ban đầu là để phát triển hệ điều hành UNIX. Bối cảnh ra đời xuất phát từ nhu cầu cần phải có một ngôn ngữ lập trình hệ thống thay thế cho hợp ngữ (Assembly) vốn nặng nề, độ tin cậy thấp và khó chuyển đổi giữa các hệ máy tính khác nhau. Ngoài việc C được dùng để viết hệ điều hành UNIX, người ta nhanh chóng nhận ra sức mạnh của C trong việc xử lý các vấn đề hiện đại của tin học: xử lý số, văn bản, cơ sở dữ liệu, lập trình hướng đối tượng. C đã trở thành một chuẩn mặc nhiên. Liên quan đến sự hình thành và phát triển của ngôn ngữ, có thể kể đến một số sự kiện sau: - Năm 1978, cuốn giáo trình dạy lập trình bằng ngôn ngữ C “The C programming langguage” do chính 2 tác giả của ngôn ngữ Brian W.Kernighan và Dennis M.Ritchie biên soạn đã được xuất bản và được phổ biến rộng rãi. - Năm 1983 một tiểu ban của viện tiêu chuẩn quốc gia Mỹ (ANSI) được thành lập nhằm đề xuất ra một chuẩn cho ngôn ngữ C. - Năm 1988 chuẩn ANSI C chính thức được ban hành. Chuẩn này bao gồm các mô tả về ngôn ngữ theo Brian W.Kernighan và Dennis M.Ritchie và quy định các thư viện chuẩn của ngôn ngữ C, nhờ đó tăng tính khả chuyển của chương trình viết bằng C. - Trong thế giới máy vi tính có các hệ chương trình dịch C nổi tiếng như: Turbo C, Borland C của Borland Inc; MSC, VC của Microsoft Corp; Lattice C của Lattice. I. 2. Các tính chất đặc trưng của ngôn ngữ C là một ngôn ngữ lập trình vạn năng được dùng để viết các hệ điều hành như UNIX cũng như các chương trình ứng dụng như quản lý văn bản, cơ sở dữ liệu. C là một ngôn ngữ có mức độ thích nghi cao, gọn và không nhất thiết phải cần tới hợp ngữ. C độc lập với bất kỳ kiến trúc máy đặc thù nào và với một chút thận trọng vẫn dễ dàng viết được các chương trình “khả chuyển” (portability) tức là những chương trình có thể chạy mà không cần phải thay đổi gì khi có sự thay đổi về phần cứng. C được sử dụng rộng rãi trong các lĩnh vực chuyên nghiệp vì đáp ứng được các yêu cầu: hiệu quả cao trong soạn thảo chương trình và dịch ra mã máy; tiếp cận trực tiếp với các thiết bị phần cứng. C không đưa ra các phép toán xử lý trực tiếp các đối tượng hợp thành như là đối tượng toàn vẹn; không xác định bất kỳ một phương tiện cấp phát bộ nhớ nào khác ngoài cấp phát tĩnh, cấp phát động theo nguyên tắc xếp chồng cho các biến cục bộ của hàm; không cung cấp cơ chế I/O, không có phương pháp truy nhập tệp. Tất cả các cơ chế này được thực hiện bằng những lời gọi hàm trong thư viện. C đưa ra các kết cấu điều khiển cơ bản cần cho các chương trình có cấu trúc như: nhóm tuần tự các câu lệnh, chọn quyết định (if); chu trình với phép kiểm tra kết thúc ở đầu (for, while), hoặc ở cuối (do...while); và việc lựa chọn một trong các trường hợp có thể (switch). C cung cấp con trỏ và khả năng định địa chỉ số học. Các đối của hàm được truyền bằng cách sao chép giá trị đối và hàm được gọi không thể thay đổi được giá trị của đối hiện tại. C cho phép hàm được gọi đệ quy và các biến cục bộ của hàm sẽ “tự động” sinh ra hoặc tạo mới với mỗi lần gọi mới. Các định nghĩa hàm không được lồng nhau nhưng các biến có thể được khai báo theo kiểu cấu trúc khối. Các hàm có thể dịch tách biệt. Các biến có thể trong hoặc ngoài hàm. Hàm chỉ biết được các biến ngoài trong cùng một tệp gốc, hoặc biến tổng thể extern. Các biến tự động có thể đặt trong các thanh ghi để tăng hiệu quả, nhưng việc khai bá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 ._.