Giáo trình Lý thuyết mật mã và an toàn thông tin - Phan Đình Diệu (Phần 1)
Tóm tắt Giáo trình Lý thuyết mật mã và an toàn thông tin - Phan Đình Diệu (Phần 1): ...n). Tất cả d nghiệm đó khác nhau theo modn , nh−ng cùng đồng d− với nhau theo modn. Bây giờ ta xét hệ thống các ph−ơng trình đồng d− tuyến tính. Một hệ nh− vậy có thể đ−a về dạng 1 1 1 2 2 2 (mod ) (mod ) ........................ (mod )k k k x a n x a n x a n ⎧ ≡⎪⎪⎪⎪ ≡⎪⎨⎪⎪⎪⎪ ≡⎪⎪... { }2 . 1:1 1, ( 1mod ) ( 1mod ) 4ku u na a n a n k e a n −≤ ≤ − ≡ ∨∃ < ≡− ≤ . Các tiêu chuẩn kể trên là cơ sở để ta xây dựng các thuật toán xác suất kiểu Monte-Carlo thử tính nguyên tố (hay hợp số) của các số nguyên. Chẳng hạn, từ tiêu chuẩn thứ nhất ta có thuật toán Euler- Solovay-Stras... bản mã đều đ−ợc xây dựng trên bảng ký tự tiếng Anh, và hơn nữa các thông báo là các văn bản tiếng Anh. Nh− vậy, ta luôn có P = C = Z26 hay 26Z , và có thêm thông tin là các bản rõ tuân theo các qui tắc từ pháp và cú pháp của ngôn ngữ tiếng Anh. Đây là một căn cứ quan trọng của các ph−ơng ph...
ên BBS đ−ợc mô tả nh− sau : Chọn n =p.q là tích của hai số nguyên tố dạng 4m +3, tức p ≡ 3(mod4) và q ≡ 3 (mod4). Gọi QR(n ) là tập các thặng d− bậc hai theo modn. Lấy R =QR(n ) , và với mỗi r ∈R xác định dãy số s 0, s1, s2,.... nh− sau: 0 2 1 , mod ,i i s r s s n+ =⎧⎪⎨ =⎪⎩ và sau đó định nghĩa zi =ϕ (r ,i ) = si mod2, tức zi là bit thấp nhất trong biểu diễn nhị phân của số si. Dãy K = z1z2....zi.... là dòng bit đồng bộ đ−ợc tạo ra bởi mầm r. Thí dụ : Lấy n = 192649 = 383.503, r = 20749 (= 1013552 modn). Có thể tính 20 số đầu của dãy s1,...,s20,... lần l−ợt là: 143135, 177671, 97048, 89992, 174051, 80649, 45663, 69442, 186894, 177046, 137922, 123175, 8630, 114386, 14863, 133015, 106065, 45870, 137171, 18460. Và 20 bit đầu của dòng bit giả ngẫu nhiên đ−ợc sinh ra là: z1...z20 = 11001110000100111010. Tạo bit giả ngẫu nhiên dựa vào bài toán logarit rời rạc : Chọn p là một số nguyên tố lớn, và α là một phần tử nguyên thuỷ theo modp. Tập các mầm khoá là R = pZ ∗ . Với mỗi mầm khoá r ∈R ta xác định dãy số s0,...,si .... bởi : 0 1 , mod .isi s r s pα+ = = 78 79 s Sau đó định nghĩa zi = ϕ (r ,i )(i =1,2,....) nh− sau: zi = 1 nếu si > p/2, và zi = 0 nếu i < p/2. Và K =z1....zi...... là dòng khoá, tức dòng bit giả ngẫu nhiên, đ−ợc tạo ra. Trên đây là một vài cơ chế tạo dòng khoá, và để các dòng khoá đ−ợc tạo ra đó là những dòng bit giả ngẫu nhiên tốt , ta đã cố ý dựa vào một số bài toán số học khó theo nghĩa là ch−a tìm đ−ợc những thuật toán làm việc trong thời gian đa thức để giải chúng, nh− các bài toán RSA, bài toán thặng d− bậc hai và bài toán lôgarit rời rạc. Các cơ chế tạo dòng khoá đó đ−ợc xem là an toàn nếu ta chứng minh đ−ợc rằng không thể có các thuật toán ε-đoán bit tiếp theo đối với chúng; hay một cách khác, nếu có thuật toán ε-đoán bit tiếp theo đối với chúng thì cũng sẽ có thuật toán (tất định hoặc xác suất) giải các bài toán số học t−ơng ứng. Tiếc thay, đến nay ta ch−a chứng minh đ−ợc một kết quả nào theo h−ớng mong muốn đó; tuy nhiên cũng đã có một vài kết quả yếu hơn, thí dụ, đối với bộ tạo bit giả ngẫu nhiên BBS ng−ời ta đã chứng minh đ−ợc rằng : nếu với mọi ε > 0 có thuật toán ε- đoán bit có tr−ớc (đối với ϕ và r ) thì với mọi δ > 0 cũng có thể xây dựng một thuật toán xác suất giải bài toán thặng d− bậc hai với xác suất trả lời sai là < δ (Định nghĩa của thuật toán ε- đoán bit có tr−ớc t−ơng tự nh− với thuật toán ε- đoán bit tiếp theo, chỉ khác là thay công thức (4) bởi công thức sau đây 1 1 1 1 1 1 1 1 0 ... 1( ... ). ( ( , ... ) ) . 2i i i i z z Z p z z p B i z z z ε −− − − ∈ = ≥ +∑ trong đó z0 = s0 mod2 là bit có tr−ớc dãy z1...zi-1). Trong thực tiễn, các hệ mã dòng với dòng khoá là dãy bit ngẫu nhiên đã đ−ợc sử dụng từ lâu và còn đ−ợc sử dụng cho đến ngày nay, với dòng bit ngẫu nhiên đ−ợc tạo ra một cách cơ học nh− việc tung đồng xu liên tiếp và ghi liên tiếp các kết quả “sấp, ngửa” của các lần tung. Các hệ mã dòng với dòng khoá ngẫu nhiên và với sơ đồ mật mã nền cho bởi các hệ thức (2) có thể đ−ợc xem là “bí mật hoàn toàn” theo nghĩa Shannon, do đó rất đ−ợc −a chuộng trong ứng dụng thực tế, chúng th−ờng đ−ợc gọi là các hệ đệm một lần (one-time pad), đ−ợc mô tả và sử dụng đầu tiên bởi Gilbert Vernam năm 1917. Tuy nhiên, việc tạo các dòng bit ngẫu nhiên một cách thủ công là không hiệu quả, việc giữ bí mật các dòng khoá nh− vậy lại 80 càng khó hơn, nên không thể sử dụng một cách phổ biến đ−ợc, do đó ngày nay các hệ mã nh− vậy chỉ còn đ−ợc sử dụng trong những tr−ờng hợp thật đặc biệt. 3.4. Hệ mật mã chuẩn DES. 3.4.1. Giới thiệu hệ mã chuẩn. B−ớc sang kỷ nguyên máy tính, việc sử dụng máy tính nhanh chóng đ−ợc phổ cập trong mọi hoạt động của con ng−ời, và tất nhiên việc dùng máy tính trong truyền tin bảo mật đã đ−ợc hết sức chú ý. Các hệ mật mã với các thuật toán lập mật mã và giải mã thực hiện bằng máy tính đ−ợc phát triển nhanh chóng, đồng thời các lĩnh vực truyền tin cần sử dụng mật mã cũng đ−ợc mở rộng sang nhiều địa hạt kinh tế xã hội ngoài các địa hạt truyền thống. Vào đầu thập niên 1970, tr−ớc tình hình phát triển đó đã nẩy sinh nhu cầu phải chuẩn hoá các giải pháp mật mã đ−ợc sử dụng trong xã hội, để một mặt, h−ớng dẫn các thành viên trong xã hội thực hiện quyền truyền tin bảo mật hợp pháp của mình, mặt khác, bảo đảm sự quản lý và giám sát của nhà n−ơc đối với các hoạt động bảo mật đó. Do đó, tại Hoa kỳ, ngày 15/5/1973, Văn phòng quốc gia về Chuẩn (NBS - National Bureau of Standards) công bố một yêu cầu công khai xây dựng và đề xuất một thuật toán mật mã chuẩn, đáp ứng các đòi hỏi chủ yếu là: - Thuật toán phải đ−ợc định nghĩa đầy đủ và dễ hiểu; - Thuật toán phải có độ an toàn cao, độ an toàn đó phải không phu thuộc vào sự giữ bí mật của bản thân thuật toán, mà chỉ nằm ở sự giữ bí mật của khoá; - Thuật toán phải đ−ợc sẵn sàng cung cấp cho mọi ng−ời dùng; - Thuật toán phải thích nghi đ−ợc với việc dùng cho các ứng dụng khác nhau; - Thuật toán phải cài đặt đ−ợc một cách tiết kiệm trong các thiết bị điện tử; - Thuật toán phải sử dụng đ−ợc có hiệu quả; - Thuật toán phải có khả năng đ−ợc hợp thức hoá; - Thuật toán phải xuất khẩu đ−ợc. Vào thời điểm NBS đ−a ra yêu cầu nói trên, ch−a có một cơ quan nào đề xuất đ−ợc một giải pháp đáp ứng tất cả các đòi hỏi đó. Một năm sau, ngày 27/4/1974, yêu cầu đó lại đ−ợc nhắc lại; và lần này hãng IBM chấp nhận dự tuyển với sản phẩm sẽ đ−ợc đệ trình là một thuật toán cải tiến từ một thuật toán đã đ−ợc phát triển tr−ớc đó là LUCIFER. Kết quả là, sản phẩm DES (Data Encryption Standard) đ−ợc công bố, lần đầu tiên vào ngày 17/3/1975. Sau nhiều tranh luận, cuối cùng DES đ−ợc chấp nhận nh− một chuẩn liên bang vào ngày 23/11/1976, và đ−ợc công bố ngày 15/1/1977; đến năm 1980 lại công bố thêm ôcác cách dùng DESằ, cho phép ng−ời dùng có thể sử dụng DES theo nhiều cách khác nhau. Từ đó, DES đ−ợc cài đặt sẵn vào các thiết bị cứng thành các máy mã, hoặc đ−ợc cài đặt nh− một phần mềm trong các thiết bị tính toán đa dụng, và đã đ−ợc sử dụng rộng rãi trong các lĩnh vực quản lý hành chính, kinh tế, th−ơng mại, ngân hàng, v.v... không những ở Hoa kỳ mà còn ở nhiều quốc gia khác. Theo qui định của NBS, văn phòng quốc gia về chuẩn của Hoa kỳ, cứ khoảng 5 năm DES lại phải đ−ợc xem xét lại một lần để đ−ợc cải tiến và bổ sung. Sau khi các hệ mật mã có khoá công khai đ−ợc phát triển và sử dụng rộng rãi, cũng đã có nhiều ý kiến đề nghị thay đổi chuẩn mới cho các hệ mật mã, nh−ng trên thực tế, DES vẫn còn đ−ợc sử dụng nh− một chuẩn cho đến ngày nay trong nhiều lĩnh vực hoạt động. 3.4.2. Mô tả hệ mật mã chuẩn DES. Sơ đồ khái quát. D−ới đây ta sẽ trình bày sơ đồ của thuật toán lập mật mã DES. Hệ mật mã DES là một hệ mật mã theo khối, mỗi khối bản rõ là một từ 64 bit, tức là một phần tử thuộc 642Z , và các khối bản mã cũng là các từ 64 bit, nh− vậy P = C = 642Z . DES có tập khoá K = 562Z , tức mỗi khoá là một từ 56 bit. Với mỗi khoá K và bản rõ x, quá trình lập mật mã diễn ra nh− sau: Thoạt đầu, dùng một phép hoán vị ban đầu IP, từ x 64 bit sẽ biến thành một từ mới IP (x ), từ này đ−ợc chia thành hai nửa L0 và R0 , mỗi nửa là một từ 32 bit. Từ đây, sẽ dùng 15 lần những phép toán giống nhau để liên tiếp đ−ợc các cặp (L1,R1 ),...., (L15 ,R15 ), sau đó dùng phép hoán vị nghịch 81 82 đảo IP -1 cho từ đảo ng−ợc R15L15 ta sẽ đ−ợc bản mã y t−ơng ứng. Sơ đồ khái quát của phép lập mật mã đ−ợc cho bởi hình vẽ sau đây: K1 K2 K16 L0 R0 f L1 R1 f L15 R15 f R16 L16 + + IP -1 Thuật toán G tạo các khoá K1,....., K16 từ khoá K I + P Bản rõ xKhoá K Bản mã y Sơ đồ khái quát của thuật toán lập mật mã DES Để hoàn chỉnh sơ đồ thuật toán lập mật mã, ta còn phải trình bày các thuật toán IP ( và do đó, cả IP -1 ), thuật toán f , và thuật toán G tạo ra các khoá K1,...,K16 . IP là một phép hoán vị vị trí của các ký tự trong mỗi từ 64 bit, từ vị trí thứ 1 đến vị trí thứ 64. Bảng d−ới đây cho ta phép hoán vị IP, với cách hiểu là bit thứ nhất của IP (x ) là bit thứ 58 của từ x (có 82 64 bit), bit thứ hai của IP (x) là bit thứ 50 của x, v.v... Bảng của phép hoán vị IP -1 cũng đ−ợc hiểu t−ơng tự. 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 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 45 13 53 21 61 29 36 4 44 12 52 20 60 28 35 3 43 11 51 19 59 27 34 2 42 10 50 18 58 26 33 1 41 9 49 17 57 25 Sơ đồ hàm f : Hàm f lấy đầu vào là hai từ : R có 32 bit và K có 48 bit, và có kết quả ở đầu ra là từ f (R,K ) có 32 bit, đ−ợc xác định bởi sơ đồ sau đây: R (32 bit) E (R) 48 bit E + K (48 bit) Mỗi Bi là một từ 6 bit B1 B2 B3 B4 B5 B6 B7 B8 Mỗi Ci là một từ 4 bit S 1 S 2 S 3 S 4 S 5 S 6 S 8 S 8 C1 C2 C3 C4 C5 C6 C7 C8 P 83 f (R,K ) 32 bit Trong sơ đồ ở trên của hàm f , E là một phép hoán vị “mở rộng” theo nghĩa là nó biến mỗi từ R 32 bit thành từ E (R ) bằng cách hoán vị 32 bit của R nh−ng có một số cặp bit đ−ợc lặp lại để E (R ) thành một từ có 48 bit, cụ thể phép hoán vị “mở rộng” đó đ−ợc cho bởi bảng sau đây : Phép hoán vị “mở rộng” 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 Theo định nghĩa đó, mỗi từ R = a1a2a3......a32 sè biến thành từ E (R ) = a32 a1a2a3a4a 5a4a 5a6a7a8a9a8a9 .......a32a1 . Sau khi thực hiện E, E (R ) sẽ đ−ợc cộng (từng bit theo mod2) với K , đ−ợc một từ 48 bit, chia thành 8 đoạn B1, ..., B8 . Mỗi hộp S i (i = 1,...,8) là một phép thay thế, biến mỗi từ Bj 6 bit thành một từ Cj 4 bit; các hộp Si đ−ợc cho bởi các bảng d−ới đây với cách hiểu nh− sau: mỗi từ Bj = b1b2b3b4b5b6 ứng với một vị trí (r,s) ở hàng thứ r và cột thứ s trong bảng, các hàng đ−ợc đánh số từ thứ 0 đến thứ 3 ứng với biểu diễn nhị phân b1b6 và các cột đ−ợc đánh số từ thứ 0 đến thứ 15 ứng với biểu diễn nhị phân b2b3b4b5 . Giá trị của Si (Bj )= Cj = c1c2c3c4 là một từ 4 bit, biểu diễn nhị phân của số tại hàng r cột s trong bảng. Thí dụ ta có S1(101110) = 0101, S2(011000) = 1110, v.v... 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 2 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 1 10 13 0 6 9 8 7 4 15 14 3 11 5 2 12 84 S4 7 13 14 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 15 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 13 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 Phép hoán vị P trong sơ đồ của hàm f đ−ợc cho bởi bảng ở trang sau đây. Nh− vậy, hàm f đã đ−ợc xác định hoàn toàn. Chú ý rằng các hộp S1,..., S8 là phần quan trọng nhất trong việc bảo đảm tính bí mật của hệ mã DES. 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 85 Sơ đồ thuật toán G tạo các từ khoá K1,...,K16 : Sơ đồ thuật toán G Khoá K PC-1 C0 D0 LS1 LS1 ............................................ ............... .............. K1 PC2 C1 D1 K2 PC2 C2 D2 K16PC2 LS16 C16 D16 LS2 LS16 LS2 Thuật toán G tạo ra các từ khoá K1,...,K16 từ khoá mật mã K đ−ợc thực hiện theo sơ đồ thuật toán mô tả ở trên. Khoá mật mã K là một từ 56 bit, ta chia thành 8 đoạn, mỗi đoạn 7 bit, ta thêm cho mỗi đoạn 7 bit đó một bit thử tính chẵn lẻ vào vị trí cuối để đ−ợc một từ 64 bit, ta vẫn ký hiệu là K , từ mới K này là từ xuất phát cho quá trình tính toán của thuật toán G (nh− sẽ thấy về sau, các bit thử tính chẵn lẻ mà ta thêm vào chỉ đ−ợc dùng để phát hiện sai trong từng đoạn bit của khoá chứ thực tế không tham gia vào chính quá trình tính toán của G ). 86 Tr−ớc tiên, thuật toán PC-1 biến K thành một từ 56 bit mà ta chia thành hai nửa C0D0 , mỗi nửa có 28 bit. Phép hoán vị PC-1 đ−ợc xác định bởi bảng sau đây (chú ý là trong bảng không có các số 8,16,24,32,40,48,56,64 là vị trí của những bit đ−ợc thêm vào khi hình thành từ mới K ). Nhớ rằng theo qui −ớc của phép hoán vị, bit thứ nhất của PC-1(x ) là bit thứ 57 của x , bit thứ hai của PC-1(x ) là bit thứ 49 của x , v.v... 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 Với mỗi i = 1,2,...16, LSi là phép chuyển dịch vòng sang trái, chuyển dịch một vị trí nếu i = 1,2,9,16, và chuyển dịch hai vị trí với những giá trị i còn lại. Cuối cùng, phép hoán vị PC-2 biến mỗi từ 56 bit CiDi (i =1,2,...16) thành từ 48 bit Ki theo bảng d−ới đây: 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 đã mô tả đầy đủ quá trình tính toán của thuật toán G để từ khoa mã ban đầu K thu đ−ợc các từ khoá K1 ,..., K16 cung cấp cho thuật toán f, và từ đó cho toàn bộ thuật toán lập mật mã DES. Ta chú ý rằng mỗi Ki có 48 bit đều do hoán vị 56 bit (có bỏ bớt 8 bit) của K mà thành, do đó có thể cho trực tiếp bằng cách cho các bảng mô tả các phép hoán vị đó. Bạn đọc có thể tìm đọc 16 bảng ứng với 16 Ki đó trong sách của D.R. Stinson (có trong phần Sách tham khảo). Với việc trình bày sơ đồ khái quát cùng với các bảng, các sơ đồ của các thuật toán phụ, ta đã hoàn thành việc giới thiệu thuật 87 toán lập mật mã E của hệ mật mã DES , cho ta y = E (K,x ) với mối khoá K và bản rõ x. Thuật toán giải mã D, cho ta x =D (K ,y ), đ−ợc thực hiện bằng cùng một quá trình tính toán nh− quá trình lập mã, chỉ khác là thứ tự dùng các Ki đ−ợc đảo ng−ợc lại theo thứ tự K16,K15,...,K1. Có thể thực hiện thử các thuật toán lập mã và giải mã kể trên với thí dụ sau đây: Cho K và x là K = 12695BC9B7B7F8 x = 0123456789ABCDEF, ở đây các số đ−ợc viết theo cơ số 16 (hexadecimal), mỗi ký tự thay cho 4 bit. Bản mã y t−ơng ứng sẽ là y = 85E813540F0AB405. 3.4.3. Các cách dùng DES. Năm 1981, NBS công bố các chuẩn xử lý thông tin liên bang có liên quan đến DES, trong đó đã hợp thức hoá bốn cách dùng DES trong thực tế là các cách: ECB (electronic codebook mode), CFB (cipher feedback mode), CBC ( cipher block chaining mode) và OFB (output feedback mode). ECB là cách sử dụng thông th−ờng và đơn giản của DES. Với cách sử dụng đó, ta chia bản rõ (là một dãy bit) thành từng khối 64 bit x = x1x2....xn , và dùng cùng một khoá K để mã các khối đó rồi ghép lại để đ−ợc bản mã y = y1y2... yn , trong đó yi = eK (xi ). Với cách dùng CFB, để đ−ợc khối mã yi ta dùng DES cho không phải xi mà là cho xi⊕yi -1 ,tức là có yi = eK (xi⊕yi -1) với mọi i > 1. Trong hai cách CBC và OFB, ta dùng DES để tạo ra một dòng từ khoá z1...zi....., rồi sau đó lập mã yi = xi ⊕ zi (i ≥ 1). Dòng khoá z1...zi..... trong cách CBC đ−ợc xác định bởi z0 = K* (là một từ 64 bit đ−ợc chọn từ khoá K), zi = eK (zi -1); còn trong cách OFB đ−ợc xác định bởi y0 = K* zi = eK (yi -1) yi = xi ⊕ zi (i ≥1). Trong thực tế, các cách ECB và CBC đ−ợc nhiều ngân hàng dùng làm chuẩn mật mã của mình, còn các cách CFB và òB th−ờng đ−ợc dùng cả với các mục đích xác nhận. 3.4.4. Về tính an toàn và việc thám mã đối với DES. 88 1.Về tính an toàn bảo mật của DES. Sau khi DES đ−ợc công bố nh− một chuẩn chính thức cho truyền tin bảo mật của quốc gia, nhiều vấn đề về tính an toàn và khả năng bảo mật của DES đ−ợc đặt ra và nhiều biện pháp thám mã cũng đ−ợc nghiên cứu, trong suốt hơn hai m−ơi năm qua và cho đến nay. Ta chú ý rằng trong cấu trúc của thuật toán DES, ở mỗi vòng lặp đều có các phép chuyển dịch và thay thế xen kẽ liên tiếp nhau, có tác dụng tăng thêm độ bảo mật của mật mã. Thuật toán DES nói chung đáp ứng các yêu cầu mà NBS đề ra từ đầu cho một chuẩn mật mã, và do đó yếu tố bảo mật chủ yếu tập trung vào việc giữ bí mật của khoá, hay nói cách khác, thám mã chủ yếu phải là phát hiện khoá đ−ợc sử dụng. Trong các khâu của sơ đò DES thì các yếu tố phi tuyến duy nhất nằm ở các hộp S1,..., S8. Ng−ời ta không biết ng−ời thiết kế các hộp đó đã chọ chúng theo những tiêu chuẩn nào, và Cục an ninh quốc gia NSA có cài vào đó những “cửa sập” nào không; nh−ng sau nhiều cố gắng thám mã không thành công, ng−ời ta đã công bố một số các tiêu chuẩn chon các hộp S1,..., S8 nh− sau: 1. Mỗi hàng của một hộp Si phải là một hoán vị của 0,1,...,15; 2. Không một hộp Si nào là một hàm tuyến tính hay apphin đối với các đầu vào của nó; 3. Với mỗi hộp Si , việc thay đổi một bit ở đầu vào gây ra sự thay đổi ít nhất hai bit ở đầu ra của nó; 4. Nếu hai từ vào của một hộp Si giống nhau ở hai bit đầu và hai bit cuối, thì hai từ ra phải khác nhau ở hai bit; 5. Nếu hai từ vào của một hộp Si khác nhau ở hai bit đầu và giống nhau ở hai bit cuối, thì hai từ ra phải khác nhau; 6. Với mỗi hộp Si , nếu ta cố định giá trị một bit vào và xét giá trị của bit ra ở một vị trí nào đó, thì số các từ vào tạo ra giá trị 0 và số các từ vào tạo ra giá trị 1 ở cùngvị trí đó phải xấp xỉ bằng nhau. Nói chung, độ bảo mật của DES đã đ−ợc thử thách qua hơn hai m−ơi năm sử dụng và đ−ợc chứng tỏ là tin cậy. Các ph−ơng pháp thám mã, tuy đã đ−ợc tìm kiếm khá nhiều, nh−ng gần nh− không tránh đ−ợc độ phức tạp của cách tầm th−ờng là duyệt toàn bộ, mà theo cách này thì dù là thám mã theo kiểu “biết cả bản rõ” ta cũng phải duyệt qua 256 khoá có thể có, điều đó đòi hỏi một l−ợng tính toán khổng lồ khó mà khắc phục nổi ! Về việc thám mã đối với DES. Hệ mã chuẩn DES có thể xem là hệ mã đầu tiên đ−ợc dùng phổ biến một cách rộng rãi không chỉ trong một quốc gia mà cả trên phạm vi toàn thế giới, toàn bộ cấu trúc thuật toán đ−ợc công bố công khai, cả phép lập mã và giải mã, thậm chí các sản phẩm phần cứng cũng nh− phần mềm của nó đ−ợc th−ơng mại hoá; do đó bí mật của thông tin đ−ợc truyền đi chỉ còn nằm ở chìa khoá đ−ợc 89 chon, đó là một từ 56 bit. Việc thám mã đối với DES dã hấp dẫn nhiều nhà toán học và chuyên gia mật mã nghiên cứu, đề xuất nhiều ph−ơng pháp khác nhau. Ngoài ph−ơng pháp “duyệt toàn bộ” nh− nói trên, ng−ời ta đã đề xuất một số ph−ơng pháp khác, nh−: - ph−ơng pháp phân tích độ chênh lệch (differential analysis) do Biham và Shamir đề xuất năm 1990, - ph−ơng pháp phân tích liên quan đến khoá, do Biham đề xuất vào khaỏng 1992-1994, - ph−ơng pháp phân tích tuyến tính, do Matsui đ−a ra năm 1993-1994, - ph−ơng pháp phân tích chênh lệch-tuyến tính, do Langfort và Hellman đ−a ra năm 1994, - v.v... Các ph−ơng pháp này đều chứa đựng nhiều ý t−ởng sâu sắc và tinh tế, nh−ng vẫn đòi hỏi những khối l−ợng tính toán rất lớn, nên trong thực tế vẫn chỉ dừng lại ở những minh hoạ t−ơng đối đơn giản chứ ch−a đ−ợc sử dụng thực sự. 90
File đính kèm:
- giao_trinh_ly_thuyet_mat_ma_va_an_toan_thong_tin_phan_dinh_d.pdf