Giáo trình Mật mã học

ế cho việc sử dụng rộng rãi OTP. Tuy nhiên OTP vẫn đ−ợc áp dụng trong lĩnh vực quân sự vμ ngoại giao, ở những lĩnh vực nμy độ an toμn không điều kiện có tầm quan trọng rất lớn. Lịch sử phát triển của mật mã học lμ quá trình cố gắng tạo các hệ mật có thể dùng một khoá để tạo một xâu bản mã t−ơng đối Giáo trình Mật mã học 298 dμi (tức có thể dùng một khóa để mã nhiều bản tin) nh−ng chí ít vẫn còn giữ đ−ợc độ an toμn tính toán. Chuẩn mã dữ liệu (DES) lμ một hệ mật thuộc loại nμy. PL 1.2. ENTROPI Trong phần tr−ớc ta đã thảo luận về khái niệm độ mật hoμn thiện vμ đặt mối quan tâm vμo một tr−ờng hợp đặc biệt, khi một khoá chỉ đ−ợc dùng cho một lần mã. Bây giờ ta sẽ xét điều sẽ xảy ra khi có nhiều bản rõ đ−ợc mã bằng cùng một khoá vμ bằng cách nμo mμ thám mã có thể thực hiện có kết quả phép tấn công chỉ với bản mã trong thời gian đủ lớn. Công cụ cơ bản trong nghiên cứu bμi toán nμy lμ khái niệm entropi. Đây lμ khái niệm trong lý thuyết thông tin do Shannon đ−a ra vμo năm 1948. Có thể coi entropi lμ đại l−ợng đo thông tin hay còn gọi lμ độ bất định. Nó đ−ợc tính nh− một hμm phân bố xác suất. Giả sử ta có một biến ngẫu nhiên X nhận các giá trị trên một tập hữu hạn theo một phân bố xác suất p(X). Thông tin thu nhận đ−ợc bởi một sự kiện xảy ra tuân theo một phân bố p(X) lμ gì?. T−ơng tự, nếu sự kiện còn ch−a xảy ra thì cái gì lμ độ bất định vμ kết quả? Đại l−ợng nμy đ−ợc gọi lμ entropi của X vμ đ−ợc kí hiệu lμ H(X). Các ý t−ởng nμy có vẻ nh− khá trìu t−ợng, bởi vậy ta sẽ xét một ví dụ cụ thể hơn. Giả sử biến ngẫu nhiên X biểu thị phép tung đồng xu. Phân bố xác suất lμ: p(mặt sấp) = p(mặt ngửa) = 1/2. Có thể nói rằng, thông tin (hay entropi) của phép tung đồng xu lμ một bit vì ta có thể mã hoá mặt sấp bằng 1 vμ mặt ngửa bằng 0. T−ơng tự entropi của n phép tung đồng tiền có thể mã hoá bằng một xâu bít có độ dμi n. Xét một ví dụ phức tạp hơn một chút. Giả sử ta có một biến ngẫu nhiên X có 3 giá trị có thể lμ x1, x2, x3 với các xác suất t−ơng Phần Phụ lục 299 ứng bằng 1/2, 1/4, 1/4. Cách mã hiệu quả nhất của 3 biến cố nμy lμ mã hoá x1 lμ 0, mã của x2 lμ 10 vμ mã của x3 lμ 11. Khi đó số bít trung bình trong phép mã hoá nμy lμ: 1/2 ì 1 +1/4 ì 2 + 1/4 ì 2 = 3/2. Các ví dụ trên cho thấy rằng, một biến cố xảy ra với xác suất n2− có thể mã hoá đ−ợc bằng một xâu bít có độ dμi n. Tổng quát hơn, có thể coi rằng, một biến cố xảy ra với xác suất p có thể mã hoá bằng một xâu bít có độ dμi xấp xỉ 2log p− . Nếu cho tr−ớc phân bố xác suất tuỳ ý p1, p2,. . ., pn của biến ngẫu nhiên X, khi đó độ đo thông tin lμ trọng số trung bình của các l−ợng 2 ilog p− . Điều nμy dẫn tới định nghĩa hình thức hoá sau. Định nghĩa 1.3 Giả sử X lμ một biến ngẫu nhiên lấy các giá trị trên một tập hữu hạn theo phân bố xác suất p(X). Khi đó entropy của phân bố xác suất nμy đ−ợc định nghĩa lμ l−ợng: ( ) n i 2 i i 1 H X p log P = = −∑ Nếu các giá trị có thể của X lμ xi, 1 ≤ i ≤ n thì ta có: ( ) ( ) ( )n i 2 i i 1 H X p X x log P X x = = − = =∑ Nhận xét: Nhận thấy rằng, log2 pi không xác định nếu pi = 0. Bởi vậy đôi khi entropi đ−ợc định nghĩa lμ tổng t−ơng ứng trên tất cả các xác suất khác 0. Vì 2 x 0 lim x log x 0→ = nên trên thực tế cũng không có trở ngại gì nếu cho pi = 0 với giá trị i nμo đó. Tuy nhiên ta sẽ tuân theo giả định lμ khi tính entropy của một phân bố xác suất pi, tổng trên sẽ đ−ợc lấy trên các chỉ số i sao cho pi ≠ 0. Ta cũng thấy rằng việc chọn cơ số của logarit lμ tuỳ ý; cơ số nμy không nhất thiết Giáo trình Mật mã học 300 phải lμ 2. Một cơ số khác sẽ chỉ lμm thay đổi giá trị của entropy đi một hằng số. Chú ý rằng, nếu pi = 1/n với 1 ≤ i ≤ n thì H(X) = log2n. Cũng dễ dμng thấy rằng H(X) ≥ 0 vμ H(X) = 0 khi vμ chỉ khi pi = 1 với một giá trị i nμo đó vμ pj = 0 với mọi j ≠ i. Xét entropi của các thμnh phần khác nhau của một hệ mật. Ta có thể coi khoá lμ một biến ngẫu nhiên K nhận các giá trị tuân theo phân bố xác suất pK vμ bởi vậy có thể tính đ−ợc H(K). T−ơng tự ta có thể tính các entropi H(P) vμ H(C) theo các phân bố xác suất t−ơng ứng của bản mã vμ bản rõ. Ví dụ 1.1: (tiếp) Ta có: ( ) ( ) ( ) 2 2 2 2 H P 1 4 log 1 4 3 4 log 3 4 1 4 2 3 4 log 3 2 2 3 4 log 3 0,81 = − − = − − − − − = − ≈ bằng các tính toán t−ơng tự, ta có H(K) = 1,5 vμ H(C) ≈1,85. PL 1.3. Các tính chất của entropi Trong phần nμy sẽ chứng minh một số kết quả quan trọng liên quan đến entropi. Tr−ớc tiên ta sẽ phát biểu bất đẳng thức Jensen. Đây lμ một kết quả cơ bản vμ rất hữu ích. Bất đẳng thức Jensen có liên quan đến hμm lồi có định nghĩa nh− sau. Định nghĩa 1.4 Một hμm có giá trị thực f lμ lồi trên khoảng I nếu: 2 2 + +⎛ ⎞ ≥⎜ ⎟⎝ ⎠ x y f (x) f (y) f với mọi x,y ∈ I. f lμ hμm lồi thực sự trên khoảng I nếu: Phần Phụ lục 301 2 2 + +⎛ ⎞ >⎜ ⎟⎝ ⎠ x y f (x) f (y) f với mọi x,y ∈ I,x ≠ y. Sau đây ta sẽ phát biểu mμ không chứng minh bất đẳng thức Jensen. Định lý 1.5 (Bất đẳng thức Jensen) Giả sử h lμ một hμm lồi thực sự vμ liên tục trên khoảng l, 1 1 = =∑n i i a vμ ai >0,1 ≤ i ≤ n. Khi đó: 1 1= = ⎛ ⎞≤ ⎜ ⎟⎜ ⎟⎝ ⎠∑ ∑ n n i i i i i i a f (x ) f a x trong đó xi ∈ I,1 ≤ i ≤ n. Ngoμi ra dấu "=" chỉ xảy ra khi vμ chỉ khi x1=. . . = xn. Bây giờ ta sẽ đ−a ra một số kết quả về entropi. Trong định lý sau sẽ sử dụng khẳng định: hμm log2x lμ một hμm lồi thực sự trong khoảng (0, ∞) (Điều nμy dễ dμng thấy đ−ợc từ những tính toán sơ cấp vì đạo hμm cấp 2 của hμm logarith lμ âm trên khoảng (0, ∞)). Định lý 1.6 Giả sử X lμ biến ngẫu nhiên có phân bố xác suất p1, p2,... , pn, trong đó 0>ip , 1 ≤ i ≤ n. Khi đó H(X) ≤ log2n. Dấu "=" chỉ xảy ra khi vμ chỉ khi 1=ip n , 1 ≤ i ≤ n. Chứng minh: áp dụng bất đẳng thức Jensen, ta có: Giáo trình Mật mã học 302 2 2 1 1 2 1 2 1 1 = = = = − = ≤ ì = ∑ ∑ ∑ n n i i i i i i n i i i H(X ) p log p p log ( / p ) log (p / p ) log n Ngoμi ra, dấu "=" chỉ xảy ra khi vμ chỉ khi pi = 1/n, 1 ≤ i ≤ n. Định lý 1.7 H(X,Y) ≤ H(X) + H(Y) Đẳng thức (dấu "=") chỉ xảy ra khi vμ chỉ khi X vμ Y lμ các biến cố độc lập Chứng minh: Giả sử X nhận các giá trị xi,1 ≤ i ≤ m;Y nhận các giá trị yj, 1 ≤ j ≤ n. Kí hiệu: pi = p(X= xi), 1 ≤ i ≤ m vμ qj = p(Y = yj ), 1≤ j ≤ n. Kí hiệu ri j = p(X = xi ,Y = yj ), 1 ≤ i ≤ m, 1 ≤ j ≤ n (Đây lμ phân bố xác suất hợp). Nhận thấy rằng: 1= = ∑ni ij j p r (1 ≤ i ≤ m) vμ 1= = ∑mj ij i q r (1 ≤ j ≤ n) Ta có: m n i i j j i j m n n m ij i ij j i j j i m n ij i j i j H(X ) H(Y) ( p log p q log q ) ( r log p r log q ) r log p q = = = = = = = = + = − + = − + = − ∑ ∑ ∑∑ ∑∑ ∑∑ 2 2 1 1 2 2 1 1 1 1 2 1 1 Phần Phụ lục 303 Mặt khác m n ij ij i j H(X ,Y) r log r = = = −∑∑ 2 1 1 Kết hợp lại ta thu đ−ợc kết quả sau: m n m n ij ij ij i j i j i j m n i j i j H(X ,Y) H(X ) H(Y) r log ( / r ) r log p q log p q log = = = = = = − − = + ≤ = = ∑∑ ∑∑ ∑∑ 2 2 1 1 1 1 2 1 1 2 1 1 0 (ở đây đã áp dụng bất đẳng thức Jensen khi biết rằng các rjj tạo nên một phân bố xác suất). Khi đẳng thức xảy ra, có thể thấy rằng phải có một hằng số c sao cho pjj / rjj = c với mọi i, j. Sử dụng đẳng thức sau: m n ij i j ij i j n m n m ij i j j i j i r log (p q / r ) r p q = = = = = = = = = ∑∑ ∑∑ ∑∑ 2 1 1 1 1 1 1 1 Điều nμy dẫn đến c = 1. Bởi vậy đẳng thức (dấu "=") sẽ xảy ra khi vμ chỉ khi rjj = pjqj, nghĩa lμ: p(X = xj, Y = yj ) = p(X = xj )p(Y = yj ) với 1 ≤ i ≤ m, 1 ≤ j ≤ n. Điều nμy có nghĩa lμ X vμ Y độc lập. Tiếp theo ta sẽ đ−a ra khái niệm entropi có điều kiện Định nghĩa 1.5 Giả sử X vμ Y lμ hai biến ngẫu nhiên. Khi đó với giá trị xác định bất kỳ y của Y, ta có một phân bố xác suất có điều kiện p(X|y). Rõ rμng lμ: Giáo trình Mật mã học 304 x H(X | y) p(x | y) log p(x | y)= −∑ 2 Ta định nghĩa entropi có điều kiện H(X|Y) lμ trung bình có trọng số (ứng với các xác suất p(y)) của entropi H(X|y) trên mọi giá trị có thể y. H(X|y) đ−ợc tính bằng: y x H(X | Y) p(y)p(x | y)log p(x | y)= −∑ ∑ 2 Entropi có điều kiện đo l−ợng thông tin trung bình về X do Y mang lại. Sau đây lμ hai kết quả trực tiếp (Bạn đọc có thể tự chứng minh). Định lý 1.8 H(X,Y) = H(Y) + H(X | Y) Hệ quả 1.9 H(X |Y) ≤ H(X) Dấu bằng chỉ xảy ra khi vμ chỉ khi X vμ Y độc lập. PL 1.4. Các khóa giả vμ khoảng duy nhất Trong phần nμy chúng ta sẽ áp dụng các kết quả về entropi ở trên cho các hệ mật. Tr−ớc tiên sẽ chỉ ra một quan hệ cơ bản giữa các entropi của các thμnh phần trong hệ mật. Entropi có điều kiện H(K|C) đ−ợc gọi lμ độ bất định về khoá. Nó cho ta biết về l−ợng thông tin về khoá thu đ−ợc từ bản mã. Định lý 1.10 Giả sử (P, C, K, E, D) lμ một hệ mật. Khi đó: H(K|C) = H(K) + H(P) - H(C) Chứng minh: Tr−ớc tiên ta thấy rằng ( ) ( ) ( )= +H K,P,C H C K,P H K,P . Do y = eK(x) nên khoá vμ bản rõ sẽ xác định bản mã duy nhất. Điều nμy có nghĩa lμ ( ) =H C K,P 0 . Bởi vậy ( ) ( )=H K, P,C H K, P . Nh−ng K vμ P độc lập nên ( ) ( ) ( )= +H K, P H K H P . Vì thế: Phần Phụ lục 305 ( ) ( ) ( ) ( )+ = +H K,P,C H K,P H K H P T−ơng tự vì khoá vμ bản mã xác định duy nhất bản rõ (tức x = dK(y)) nên ta có H(P | K,C) = 0 vμ bởi vậy H(K,P,C) = H(K,P). Bây giờ ta sẽ tính nh− sau: ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) = − = − = + − H K ,C H K,C H C H K,P,C H C H K H P H C Đây lμ nội dung của định lý. Ta sẽ quay lại ví dụ 2.1 để minh họa kết quả nμy. Ví dụ 1.1 (tiếp) Ta đã tính đ−ợc H(P) ≈ 0,81, H(K) = 1,5 vμ H(C) ≈1,85. Theo định lý 2.10 ta có ( ) ≈ + ≈H K ,C 1,5 0,85 0,46 . Có thể kiểm tra lại kết quả nμy bằng cách áp dụng định nghĩa về entropi có điều kiện nh− sau. Tr−ớc tiên cần phải tính các xác suất xuất p(Kj | j), 1 ≤ i ≤ 3, 1 ≤ j ≤ 4. Để thực hiện điều nμy có thể áp dụng định lý Bayes vμ nhận đ−ợc kết quả nh− sau: P(K1 | 1) = 1 p(K2 | 1) = 0 p(K3 | 1) = 0 P(K1 | 2) = 6/7 p(K2 | 2) = 1/7 p(K3 | 2) = 0 P(K1 | 3) = 0 p(K2 | 3) = 3/4 p(K3 | 3) = 1/4 P(K1 | 4) = 0 p(K2 | 4) = 0 p(K3 | 4) = 1 Bây giờ ta tính: H(K | C) = 1/8 ì 0 +7/16 ì 0,59 + 1/4 ì 0,81 + 3/16 ì 0 = 0,46 Giá trị nμy bằng giá trị đ−ợc tính theo định lý 2.10. Giả sử (P, C, K, E, D) lμ hệ mật đang đ−ợc sử dụng. Một xâu của bản rõ x1x2 . . .xn sẽ đ−ợc mã hoá bằng một khoá để tạo ra bản mã y1y2... yn. Nhớ lại rằng, mục đích cơ bản của thám mã lμ phải xác định đ−ợc khoá. Ta xem xét các ph−ơng pháp tấn công chỉ với bản mã vμ coi Oscar có khả năng tính toán vô hạn. Ta cũng giả sử Giáo trình Mật mã học 306 Oscar biết bản rõ lμ một văn bản theo ngôn ngữ tự nhiên (chẳng hạn văn bản tiếng Anh). Nói chung Oscar có khả năng rút ra một số khoá nhất định (các khoá có thể hay các khoá chấp nhận đ−ợc) nh−ng trong đó chỉ có một khoá đúng, các khoá có thể còn lại (các khoá không đúng) đ−ợc gọi lμ các khoá giả. Ví dụ, giả sử Oscar thu đ−ợc một xâu bản mã WNAJW mã bằng ph−ơng pháp mã dịch vòng. Dễ dμng thấy rằng, chỉ có hai xâu bản rõ có ý nghĩa lμ river vμ arena t−ơng ứng với các khoá F(= 5) vμ W(= 22). Trong hai khoá nμy chỉ có một khoá đúng, khoá còn lại lμ khoá giả. (Trên thực tế, việc tìm một bản mã của MDV có độ dμi 5 vμ 2 bản giải mã có nghĩa không phải quá khó khăn, bạn đọc có thể tìm ra nhiều ví dụ khác). Mục đích của ta lμ phải tìm ra giới hạn cho số trung bình các khoá giả. Tr−ớc tiên, phải xác định giá trị nμy theo entropi (cho một kí tự) của một ngôn ngữ tự nhiên L (kí hiệu lμ HL). HL lμ l−ợng thông tin trung bình trên một kí tự trong một xâu có nghĩa của bản rõ. (Chú ý rằng, một xâu ngẫu nhiên các kí tự của bảng chữ cái sẽ có entropi trên một kí tự bằng log2 26 ≈ 4,76). Ta có thể lấy H(P) lμ xấp xỉ bậc nhất cho HL. Trong tr−ờng hợp L lμ Anh ngữ, ta tính đ−ợc H(P) ≈ 4,19. Dĩ nhiên các kí tự liên tiếp trong một ngôn ngữ không độc lập với nhau vμ sự t−ơng quan giữa các kí tự liên tiếp sẽ lμm giảm entropi. Ví dụ, trong Anh ngữ, chữ Q luôn kéo theo sau lμ chữ U. Để lμm xấp xỉ bậc hai, tính entropi của phân bố xác suất của tất cả các bộ đôi rồi chia cho 2. Một cách tổng quát, ta định nghĩa Pn lμ biến ngẫu nhiên có phân bố xác suất của tất cả các bộ n của bản rõ. Ta sẽ sử dụng tất cả các định nghĩa sau: Định nghĩa 1.6 Giả sử L lμ một ngôn ngữ tự nhiên. Entropi của L đ−ợc xác định lμ đại l−ợng sau: n L n H(P ) H lim n→∞= Phần Phụ lục 307 Độ d− của L lμ: RL = l - (HL / log2 | P | ) Nhận xét: HL đo entropi trên mỗi kí tự của ngôn ngữ L. Một ngôn ngữ ngẫu nhiên sẽ có entropi lμ log2 |P | . Bởi vậy đại l−ợng RL đo phần "kí tự v−ợt trội" lμ phần d−. Trong tr−ờng hợp Anh ngữ, dựa trên bảng chứa một số lớn các bộ đôi vμ các tần số, ta có thể tính đ−ợc H(P2). Ước l−ợng theo cách nμy, ta tính đ−ợc ( )2H P 3,90≈ . Cứ tiếp tục nh− vậy bằng cách lập bảng các bộ ba v.v... ta thu đ−ợc −ớc l−ợng cho HL. Trên thực tế, bằng nhiều thực nghiệm khác nhau, ta có thể đi tới kết quả sau 1,0 ≤ HL ≤1,5. Tức lμ l−ợng thông tin trung bình trong tiếng Anh vμo khoảng 1 bít tới 1,5 bít trên mỗi kí tự!. Giả sử lấy 1,25 lμ giá trị −ớc l−ợng của giá trị của HL. Khi đó độ d− vμo khoảng 0,75. Tức lμ tiếng Anh có độ d− vμo khoảng 75%! (Điều nμy không có nghĩa loại bỏ tuỳ ý 3 trên 4 kí tự của một văn bản tiếng Anh mμ vẫn có khả năng đọc đ−ợc nó. Nó chỉ có nghĩa lμ tìm đ−ợc một phép mã Huffman cho các bộ n với n đủ lớn, phép mã nμy sẽ nén văn bản tiếng Anh xuống còn 1/4 độ dμi của bản gốc). Với các phân bố xác suất đã cho trên K vμ Pn. Có thể xác định phân bố xác suất trên nC lμ tập các bộ n của bản mã. (Ta đã lμm điều nμy trong tr−ờng hợp n =1). Ta đã xác định nP lμ biến ngẫu nhiên biểu diễn bộ n của bản rõ. T−ơng tự nC lμ biến ngẫu nhiên biểu thị bộ n của bản mã. Với y ∈ Cn, định nghĩa: ( ) ( ) ( ){ }KxK y K x ,p 0,e x y= ∈ ∃ ∈ > =nn PK; P nghĩa lμ K(y) lμ tập các khoá K sao cho y lμ bản mã của một xâu bản rõ độ dμi n có nghĩa, tức lμ tập các khoá "có thể" với y lμ bản mã đã cho. Nếu y lμ dãy quan sát đ−ợc của bản mã thì số khoá giả sẽ lμ ( )K y 0 1− vì chỉ Giáo trình Mật mã học 308 có một khoá lμ khoá đúng trong số các khoá có thể. Số trung bình các khoá giả (trên tất cả các xâu bản mã có thể độ dμi n) đ−ợc kí hiệu lμ ns vμ nó đ−ợc tính nh− sau: ( ) ( )( ) ( ) ( ) ( ) ( ) ( ) n n n n n y C y C y C y C s p y K y 1 p y K y p y p y K y 1 ∈ ∈ ∈ ∈ = − = − = − ∑ ∑ ∑ ∑ Từ định lý 1.10 ta có: ( ) ( ) ( ) ( )n n nH K C H K H P H C= + − Có thể dùng −ớc l−ợng sau: ( ) ( )n L L 2H P nH n 1 R log≈ = − P với điều kiện n đủ lớn. Hiển nhiên lμ: ( )n 2H C n log≤ C Khi đó nếu =P C thì: ( ) ( )n L 2H K C H K nR log≥ − P (1.1) Tiếp theo xét quan hệ của l−ợng H(K | Cn) với số khóa giả sn. Ta có: ( ) ( )( ) ( ) ( ) ( ) ( ) ( ) n n n n y C 2 y C y C 2 n H K C p y K y p y log K y p y K y log s 1 ∈ ∈ ∈ = ≤ ≤ = + ∑ ∑ ∑ Phần Phụ lục 309 ở đây ta áp dụng bất đẳng thức Jensen (định lý 1.5) với f(x) = log2x. Bởi vậy ta có bất đẳng thức sau: n 2 nH(K C ) log (s 1)≤ + (1.2) Kết hợp hai bất đẳng thức (1.1) vμ (1.2), ta có : 2 n L 2log (s 1) H(K) nR log P+ ≥ − Trong tr−ờng hợp các khoá đ−ợc chọn đồng xác suất (Khi đó H(K) có giá trị lớn nhất) ta có kết quả sau. Định lý 1.11 Giả sử (P, C, K, E, D ) lμ một hệ mật trong đó |C | = |P|vμ các khoá đ−ợc chọn đồng xác suất. Giả sử RL lμ độ d− của ngôn ngữ gốc. Khi đó với một xâu bản mã độ dμi n cho tr−ớc (n lμ số đủ lớn), số trung bình các khoá giả sn thoả mãn bất đẳng thức nh− sau: ( ){ }n Ls K P nR 1≥ − L−ợng ( )LK P nR 1− tiến tới 0 theo hμm mũ khi n tăng. Ước l−ợng nμy có thể không chính xác với các giá trị n nhỏ. Đó lμ do H(Pn)/ n không phải lμ một −ớc l−ợng tốt cho HL nếu n nhỏ. Ta đ−a ra đây một khái niệm nữa Định nghĩa 1.7 Khoảng duy nhất của một hệ mật đ−ợc định nghĩa lμ giá trị của n mμ ứng với giá trị nμy, số khoá giả trung bình bằng 0 (kí hiệu giá trị nμy lμ n0). Điều đó có nghĩa lμ n0 lμ độ dμi trung bình cần thiết của bản mã để thám mã có thể tính toán khoá một cách duy nhất với thời gian đủ lớn. Nếu đặt sn = 0 trong định lý 1.11 vμ giải theo n ta sẽ nhận đ−ợc −ớc l−ợng cho khoảng duy nhất: 0 2 L 2n log R log≈ K P Giáo trình Mật mã học 310 Ví dụ với MTT, ta có |P| = 26 vμ |K| =26 !. Nếu lấy RL =0,75 thì ta nhận đ−ợc −ớc l−ợng cho khoảng duy nhất bằng: n0 ≈ 88,4/ (0,75 ì4,7) ≈ 25 Điều đó có nghĩa lμ thông th−ờng nếu mã thám có đ−ợc xâu bản mã với độ dμi tối thiểu lμ 25, anh ta có thể nhận đ−ợc bản giải mã duy nhất. Phần Phụ lục 311 Phụ lục 2 Tạo số giả ngẫu nhiên Trong các số ngẫu nhiên, các xâu bit ngẫu nhiên lμ một vấn đề quan trọng trong nhiều bμi toán của mật mã học. Ví dụ các khoá mật cần đ−ợc tạo một cách ngẫu nhiên từ một không gian khoá xác định; nhiều giao thức yêu cầu phải tạo đ−ợc các số ngẫu nhiên trong quá trình thực hiện. Tạo các số ngẫu nhiên bằng cách tung đồng xu hoặc bằng các quá trình vật lý đòi hỏi nhiều thời gian vμ chi phí. Bởi thế trong thực tế ng−ời ta th−ờng dùng các bộ tạo bít giả ngẫu nhiên. (kí hiệu lμ PRBG). PRBG bắt đầu bằng một xâu bit ngắn (đ−ợc gọi lμ mầm) vμ sẽ mở rộng nó thμnh một xâu bit "có vẻ ngẫu nhiên" dμi hơn nhiều rất cần cho các ứng dụng. Sau đây ta sẽ đ−a ra một định nghĩa hình thức hơn. Định nghĩa Cho k, l lμ các số nguyên d−ơng sao cho l ≥ k+1 (trong đó l lμ một hμm đa thức xác định của k). Một bộ tạo bit giả ngẫu nhiên (k,l) (kí hiệu lμ (k,l) - PRBG) lμ một hμm f: (Z2)k ặ (Z2)l, hμm nμy có thể tính đ−ợc trong thời gian đa thức (nh− một hμm của k). Giá trị đầu vμo s0 ∈ (Z2)k đ−ợc gọi lμ mầm vμ đầu ra f(s0) ∈ (Z2)l đ−ợc gọi lμ xâu bit giả ngẫu nhiên. Hμm f lμ một hμm tất định, bởi vậy xâu bit f(s0) chỉ phụ thuộc vμo mầm. Với điều kiện mầm đ−ợc chọn ngẫu nhiên, mục đích đặt ra lμ phải tạo đ−ợc xâu bit giả ngẫu nhiên f(s0) giống nh− các xâu bit ngẫu nhiên thực sự. Rất khó đ−a ra một định nghĩa chính xác, bởi vậy trong phần nμy ta sẽ cố gắng nêu ra một mô tả trực giác cho khái niệm nμy. Sau đây lμ một ví dụ có vai trò thúc đẩy việc nghiên cứu các PRBG thuộc dạng nμy. Ta hãy nhớ lại khái niệm về độ mật hoμn thiện đã đ−ợc nghiên cứu trong phụ lục 1. Một thể hiện của độ Giáo trình Mật mã học 312 mật hoμn thiện lμ hệ khoá dùng một lần OTP trong đó bản rõ vμ khoá lμ hai xâu bit có độ dμi xác định vμ bản mã đ−ợc tạo ra bằng cách cộng modulo 2 bản rõ vμ khoá theo từng bit. Khó khăn trên thực tế của OTP lμ khoá (phải đ−ợc tạo một cách ngẫu nhiên vμ đ−ợc truyền đi trên một kênh bảo mật) phải dμi nh− bản rõ để bảo đảm độ mật hoμn thiện. Các PRBG cho một ph−ơng pháp khả dĩ để giải quyết vấn đề nμy. Giả sử Alice vμ Bob thoả thuận sử dụng một PRBG vμ thông báo mầm khoá trên một kênh bảo mật. Sau đó Alice vμ Bob đều cùng tính một xâu bit giả ngẫu nhiên, xâu nμy đ−ợc dùng nh− một OTP. Nh− vậy, mầm khoá có chức năng nh− một khoá vμ PRBG có thể coi lμ một bộ tạo dòng khoá cho hệ mã dòng. Sau đây ta sẽ mô tả một số PRBG quen thuộc để giải thích vμ minh họa một số khái niệm. Tr−ớc hết ta thấy rằng, một bộ ghi dịch phản hồi tuyến tính (đã mô tả ở phần 3.8) có thể xem nh− một PRBG. Với một mầm khoá k bit, một bộ ghi dịch phản hồi tuyến tính (LFSR) bậc k có thể đ−ợc dùng để tạo ra 2k-k-1 bit tiếp sau tr−ớc khi lặp lại. PRBG nhận đ−ợc từ một bộ ghi dịch phản hồi tuyến tính rất không an toμn. Phần PL 1.4 cho thấy rằng, việc biết 2k bit liên tiếp bất kì đủ để xác định mầm khoá vμ bởi vậy mã thám có thể tái tạo lại toμn bộ dãy khoá (mặc dù ta vẫn còn ch−a nói về độ mật của một PRBG nh−ng rõ rμng lμ phép tấn công nμy cũng cho ta biết rằng bộ tạo kiểu nμy không an toμn). Một PRBG khác (cũng không an toμn) đ−ợc gọi lμ bộ tạo đồng d− tuyến tính (LCG) đ−ợc mô tả trên hình PL 2.1. Cho M ≥ 2 là một số nguyên và cho 1 ≤a,b≤ M-1. Đặt k = ⎣log2M⎦ và cho k+1 ≤ l ≤ M-1. Với một mầm s0, trong đó 0 ≤ s0 ≤ M-1, ta xác định: si = (a si-1+b) mod M với 1 ≤ i ≤ l và xác định: f(s0) = (z1, z2, . . . , zl) trong đó zi = si mod 2 1 ≤ i ≤ l . Khi đó f là bộ tạo đồng d− tuyến tính (k,l)- (LCG) Hình PL 2.1: Bộ tạo đồng d− tuyến tính Phần Phụ lục 313 Sau đây lμ một ví dụ nhỏ để minh họa. Ví dụ 2.1 Ta có thể thu đ−ợc (5,10) - PRBG bằng cách lấy M = 31, a = 3 vμ b = 5 trong LCG. Nếu xét ánh xạ s ặ 3s+5 mod 31 thì 13ặ13 vμ 30 thặng d− khác sẽ đ−ợc hoán vị trong một chu trình có độ dμi 30, cụ thể lμ 0, 5, 20, 3, 14, 16, 22, 9, 1, 8, 29, 30, 2, 11, 7, 26, 21, 6, 23, 12, 10, 4, 17, 25, 18, 28, 27, 24, 15, 19. Nếu mầm không phải lμ 13 thì mầm sẽ xác định điểm xuất phát trong chu trình nμy vμ 10 phần tử tiếp theo khi đ−ợc rút gọn theo modulo 2 sẽ tạo nên dãy giả ngẫu nhiên. 31 xâu bit giả ngẫu nhiên có thể có đ−ợc tạo bởi bộ tạo nμy đ−ợc đ−a ra trên bảng PL 2.1. Có thể sử dụng một số khái niệm đã xây dựng ở các phần tr−ớc để tạo ra các PRBG. Ví dụ, chế độ OFB của DES có thể xem nh− một PRBG, hơn nữa nó tỏ ra lμ có độ an toμn về mặt tính toán. Một quan điểm khác trong việc xây dựng các PRBG tốc độ cao lμ kết hợp các LFSR theo một cách nμo đó để đầu ra ít tuyến tính hơn. Một ph−ơng pháp nh− vậy (do Copersmith, Krawczyk vμ Mansour đ−a ra) đ−ợc gọi lμ bộ tạo kiểu co rút (Shrinking generator). Giả sử có hai bộ LFSR, một bộ có bậc k1, một bộ khác có bậc k2. Ta cần (k1 + k2) bit lμm mầm để khởi tạo cả hai LFSR. LFSR thứ nhất sẽ tạo ra một dãy bit a1, a2,... vμ LFSR thứ hai sẽ tạo ra dãy bit b1, b2,... Sau đó ta xác định dãy bit giả ngẫu nhiên z1, z2,... theo quy tắc: zi = aik, trong đó ik lμ ví trị của số “1” thứ k trong dãy b1, b2, . . . Các bit giả ngẫu nhiên nμy lμ một dãy con của các bit đ−ợc tạo bởi LFSR thứ nhất. Ph−ơng pháp tạo bit giả ngẫu nhiên nμy rất nhanh vμ lμ một ph−ơng pháp đã đ−ợc chứng tỏ lμ an toμn. Giáo trình Mật mã học 314 Bảng PL 2.1: Các xâu bit đ−ợc tạo ra từ một bộ tạo đồng d− tuyến tính Mầm dãy 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 1010001101 0100110101 1101010001 0001101001 1100011010 0100011010 1000110010 0101000110 1001101010 1010011010 0110010110 1101000110 0011001011 1111111111 0011010011 1010100011 0110100110 1001011010 0101101010 0101000110 1000110100 0100011001 1101001101 0001100101 1101010001 0010110101 1010001100 0110101000 1011010100 0011010100 0110101000 Hình PL 2.2 mô tả một PRBG xây dựng trên hμm mã RSA. Cho p, q là hai số nguyên tố (k/2) bit. Ta xác định n = p.q. Cho b đ−ợc chọn sao cho UCLN(b,φ(n)) = 1. Theo thông lệ n và b đ−ợc đem công khai còn p và q đ−ợc giữ kín. Mầm là một phần tử bất kì s0 ∈ Zn* sao cho s0 có k bit. Với i ≥ 0, ta định nghĩa si+1 = si b mod n và f(s0) = (z1, z2,... zl) trong đó zi = si mod 2 1 ≤ i ≤ l. Khi đó f là một bộ tạo RSA -(k,l). Hình PL 2.2: Bộ tạo kiểu RSA Phần Phụ lục 315 D−ới đây lμ một ví dụ về bộ tạo RSA. Ví dụ 2.2 Giả sử n = 91261 = 263 ì 347, b = 1547 vμ s0 = 75364. 20 bit đầu tiên tạo bởi bộ tạo RSA đ−ợc tính theo bảng PL 2.2. Bởi vậy xâu bit tạo từ mầm khóa nμy lμ: 10000111011110011000 Bảng PL 2.2: Các bit đ−ợc tạo bởi bộ tạo RSA i si zi 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 75634 31483 31283 51968 39796 28761 14089 5923 44891 62284 11889 43467 71215 10401 77444 56794 78147 72137 89592 29022 13356 1 0 0 0 0 1 1 1 0 1 1 1 1 0 0 1 1 0 0 0 Giáo trình Mật mã học 316 Phụ lục 3 Mã nguồn DES #define EN0 0 /* MODE == encrypt */ #define DE1 1 /* MODE == decrypt */ typedef struct { unsigned long ek[32]; unsigned long dk[32]; } des_ctx; extern void deskey(unsigned char *, short); /* hexkey[8] MODE * Sets the internal key register according to the hexadecimal * key contained in the 8 bytes of hexkey, according to the DES, * for encryption or decryption according to MODE. */ extern void usekey(unsigned long *); /* cookedkey[32] * Loads the internal key register with the data in cookedkey. */ extern void cpkey(unsigned long *); /* cookedkey[32] * Copies the contents of the internal key register into the storage * located at &cookedkey[0]. */ extern void des(unsigned char *, unsigned char *); /* from[8] to[8] * Encrypts/Decrypts (according to the key currently loaded in the * internal key register) one block of eight bytes at address `from' * into the block at address `to'. They can be the same. */ Phần Phụ lục 317 static void scrunch(unsigned char *, unsigned long *); static void unscrun(unsigned long *, unsigned char *); static void desfunc(unsigned long *, unsigned long *); static void cookey(unsigned long *); static unsigned long KnL[32] = { 0L }; static unsigned long KnR[32] = { 0L }; static unsigned long Kn3[32] = { 0L }; static unsigned char Df_Key[24] = { 0#01,0x23,0x45,0x67,0x89,0xab,0xcd,0xef, 0xfe,0xdc,0xba,0x98,0x76,0x54,0x32,0x10, 0x89,0xab,0xcd,0xef,0#01,0x23,0x45,0x67 }; static unsigned short bytebit[8] = { 0200, 0100, 040, 020, 010, 04, 02, 01 }; static unsigned long bigbyte[24] = { 0x800000L, 0x400000L, 0x200000L, 0x100000L, 0x80000L, 0x40000L, 0x20000L, 0x10000L, 0x8000L, 0x4000L, 0x2000L, 0x1000L, 0x800L, 0x400L, 0x200L, 0x100L, 0x80L, 0x40L, 0x20L, 0x10L, 0x8L, 0x4L, 0x2L, 0x1L }; /* Use the key schedule specified in the Standard (ANSI X3.92-1981). */ static unsigned char pc1[56] = { 56, 48, 40, 32, 24, 16, 8, 0, 57, 49, 41, 33, 25, 17, 9, 1, 58, 50, 42, 34, 26, 18, 10, 2, 59, 51, 43, 35, 62, 54, 46, 38, 30, 22, 14, 6, 61, 53, 45, 37, 29, 21, 13, 5, 60, 52, 44, 36, 28, 20, 12, 4, 27, 19, 11, 3 }; static unsigned char totrot[16] = { 1,2,4,6,8,10,12,14,15,17,19,21,23,25,27,28 }; static unsigned char pc2[48] = { 13, 16, 10, 23, 0, 4, 2, 27, 14, 5, 20, 9, 22, 18, 11, 3, 25, 7, 15, 6, 26, 19, 12, 1, 40, 51, 30, 36, 46, 54, 29, 39, 50, 44, 32, 47, 43, 48, 38, 55, 33, 52, 45, 41, 49, 35, 28, 31 }; Giáo trình Mật mã học 318 void deskey(key, edf) /* Thanks to James Gillogly & Phil Karn! */ unsigned char *key; short edf; { register int i, j, l, m, n; unsigned char pc1m[56], pcr[56]; unsigned long kn[32]; for ( j = 0; j < 56; j++ ) { l = pc1[j]; m = l & 07; pc1m[j] = (key[l >> 3] & bytebit[m]) ? 1 : 0; } for( i = 0; i < 16; i++ ) { if( edf == DE1 ) m = (15 - i) << 1; else m = i << 1; n = m + 1; kn[m] = kn[n] = 0L; for( j = 0; j < 28; j++ ) { l = j + totrot[i]; if( l < 28 ) pcr[j] = pc1m[l]; else pcr[j] = pc1m[l - 28]; } for( j = 28; j < 56; j++ ) { l = j + totrot[i]; if( l < 56 ) pcr[j] = pc1m[l]; else pcr[j] = pc1m[l - 28]; } for( j = 0; j < 24; j++ ) { if( pcr[pc2[j]] ) kn[m] |= bigbyte[j]; if( pcr[pc2[j+24]] ) kn[n] |= bigbyte[j]; } } cookey(kn); return; } static void cookey(raw1) register unsigned long *raw1; { register unsigned long *cook, *raw0; unsigned long dough[32]; register int i; cook = dough; for( i = 0; i < 16; i++, raw1++ ) { Phần Phụ lục 319 raw0 = raw1++; *cook = (*raw0 & 0#00fc0000L) << 6; *cook |= (*raw0 & 0#00000fc0L) << 10; *cook |= (*raw1 & 0#00fc0000L) >> 10; *cook++ |= (*raw1 & 0#00000fc0L) >> 6; *cook = (*raw0 & 0#0003f000L) << 12; *cook |= (*raw0 & 0#0000003fL) << 16; *cook |= (*raw1 & 0#0003f000L) >> 4; *cook++ |= (*raw1 & 0#0000003fL); } usekey(dough); return; } void cpkey(into) register unsigned long *into; { register unsigned long *from, *endp; from = KnL, endp = &KnL[32]; while( from < endp ) *into++ = *from++; return; } void usekey(from) register unsigned long *from; { register unsigned long *to, *endp; to = KnL, endp = &KnL[32]; while( to < endp ) *to++ = *from++; return; } void des(inblock, outblock) unsigned char *inblock, *outblock; { unsigned long work[2]; scrunch(inblock, work); desfunc(work, KnL); unscrun(work, outblock); return; } static void scrunch(outof, into) register unsigned char *outof; register unsigned long *into; { Giáo trình Mật mã học 320 *into = (*outof++ & 0xffL) << 24; *into |= (*outof++ & 0xffL) << 16; *into |= (*outof++ & 0xffL) << 8; *into++ |= (*outof++ & 0xffL); *into = (*outof++ & 0xffL) << 24; *into |= (*outof++ & 0xffL) << 16; *into |= (*outof++ & 0xffL) << 8; *into |= (*outof & 0xffL); return; } static void unscrun(outof, into) register unsigned long *outof; register unsigned char *into; { *into++ = (*outof >> 24) & 0xffL; *into++ = (*outof >> 16) & 0xffL; *into++ = (*outof >> 8) & 0xffL; *into++ = *outof++ & 0xffL; *into++ = (*outof >> 24) & 0xffL; *into++ = (*outof >> 16) & 0xffL; *into++ = (*outof >> 8) & 0xffL; *into = *outof & 0xffL; return; } static unsigned long SP1[64] = { 0#01010400L, 0#00000000L, 0#00010000L, 0#01010404L, 0#01010004L, 0#00010404L, 0#00000004L, 0#00010000L, 0#00000400L, 0#01010400L, 0#01010404L, 0#00000400L, 0#01000404L, 0#01010004L, 0#01000000L, 0#00000004L, 0#00000404L, 0#01000400L, 0#01000400L, 0#00010400L, 0#00010400L, 0#01010000L, 0#01010000L, 0#01000404L, 0#00010004L, 0#01000004L, 0#01000004L, 0#00010004L, 0#00000000L, 0#00000404L, 0#00010404L, 0#01000000L, 0#00010000L, 0#01010404L, 0#00000004L, 0#01010000L, 0#01010400L, 0#01000000L, 0#01000000L, 0#00000400L, 0#01010004L, 0#00010000L, 0#00010400L, 0#01000004L, 0#00000400L, 0#00000004L, 0#01000404L, 0#00010404L, 0#01010404L, 0#00010004L, 0#01010000L, 0#01000404L, 0#01000004L, 0#00000404L, 0#00010404L, 0#01010400L, 0#00000404L, 0#01000400L, 0#01000400L, 0#00000000L, 0#00010004L, 0#00010400L, 0#00000000L, 0#01010004L }; static unsigned long SP2[64] = { 0x80108020L, 0x80008000L, 0#00008000L, 0#00108020L, 0#00100000L, 0#00000020L, 0x80100020L, 0x80008020L, 0x80000020L, 0x80108020L, 0x80108000L, 0x80000000L, Phần Phụ lục 321 0x80008000L, 0#00100000L, 0#00000020L, 0x80100020L, 0#00108000L, 0#00100020L, 0x80008020L, 0#00000000L, 0x80000000L, 0#00008000L, 0#00108020L, 0x80100000L, 0#00100020L, 0x80000020L, 0#00000000L, 0#00108000L, 0#00008020L, 0x80108000L, 0x80100000L, 0#00008020L, 0#00000000L, 0#00108020L, 0x80100020L, 0#00100000L, 0x80008020L, 0x80100000L, 0x80108000L, 0#00008000L, 0x80100000L, 0x80008000L, 0#00000020L, 0x80108020L, 0#00108020L, 0#00000020L, 0#00008000L, 0x80000000L, 0#00008020L, 0x80108000L, 0#00100000L, 0x80000020L, 0#00100020L, 0x80008020L, 0x80000020L, 0#00100020L, 0#00108000L, 0#00000000L, 0x80008000L, 0#00008020L, 0x80000000L, 0x80100020L, 0x80108020L, 0#00108000L }; static unsigned long SP3[64] = { 0#00000208L, 0#08020200L, 0#00000000L, 0#08020008L, 0#08000200L, 0#00000000L, 0#00020208L, 0#08000200L, 0#00020008L, 0#08000008L, 0#08000008L, 0#00020000L, 0#08020208L, 0#00020008L, 0#08020000L, 0#00000208L, 0#08000000L, 0#00000008L, 0#08020200L, 0#00000200L, 0#00020200L, 0#08020000L, 0#08020008L, 0#00020208L, 0#08000208L, 0#00020200L, 0#00020000L, 0#08000208L, 0#00000008L, 0#08020208L, 0#00000200L, 0#08000000L, 0#08020200L, 0#08000000L, 0#00020008L, 0#00000208L, 0#00020000L, 0#08020200L, 0#08000200L, 0#00000000L, 0#00000200L, 0#00020008L, 0#08020208L, 0#08000200L, 0#08000008L, 0#00000200L, 0#00000000L, 0#08020008L, 0#08000208L, 0#00020000L, 0#08000000L, 0#08020208L, 0#00000008L, 0#00020208L, 0#00020200L, 0#08000008L, 0#08020000L, 0#08000208L, 0#00000208L, 0#08020000L, 0#00020208L, 0#00000008L, 0#08020008L, 0#00020200L }; static unsigned long SP4[64] = { 0#00802001L, 0#00002081L, 0#00002081L, 0#00000080L, 0#00802080L, 0#00800081L, 0#00800001L, 0#00002001L, 0#00000000L, 0#00802000L, 0#00802000L, 0#00802081L, 0#00000081L, 0#00000000L, 0#00800080L, 0#00800001L, 0#00000001L, 0#00002000L, 0#00800000L, 0#00802001L, 0#00000080L, 0#00800000L, 0#00002001L, 0#00002080L, 0#00800081L, 0#00000001L, 0#00002080L, 0#00800080L, 0#00002000L, 0#00802080L, 0#00802081L, 0#00000081L, 0#00800080L, 0#00800001L, 0#00802000L, 0#00802081L, 0#00000081L, 0#00000000L, 0#00000000L, 0#00802000L, Giáo trình Mật mã học 322 0#00002080L, 0#00800080L, 0#00800081L, 0#00000001L, 0#00802001L, 0#00002081L, 0#00002081L, 0#00000080L, 0#00802081L, 0#00000081L, 0#00000001L, 0#00002000L, 0#00800001L, 0#00002001L, 0#00802080L, 0#00800081L, 0#00002001L, 0#00002080L, 0#00800000L, 0#00802001L, 0#00000080L, 0#00800000L, 0#00002000L, 0#00802080L }; static unsigned long SP5[64] = { 0#00000100L, 0#02080100L, 0#02080000L, 0x42000100L, 0#00080000L, 0#00000100L, 0x40000000L, 0#02080000L, 0x40080100L, 0#00080000L, 0#02000100L, 0x40080100L, 0x42000100L, 0x42080000L, 0#00080100L, 0x40000000L, 0#02000000L, 0x40080000L, 0x40080000L, 0#00000000L, 0x40000100L, 0x42080100L, 0x42080100L, 0#02000100L, 0x42080000L, 0x40000100L, 0#00000000L, 0x42000000L, 0#02080100L, 0#02000000L, 0x42000000L, 0#00080100L, 0#00080000L, 0x42000100L, 0#00000100L, 0#02000000L, 0x40000000L, 0#02080000L, 0x42000100L, 0x40080100L, 0#02000100L, 0x40000000L, 0x42080000L, 0#02080100L, 0x40080100L, 0#00000100L, 0#02000000L, 0x42080000L, 0x42080100L, 0#00080100L, 0x42000000L, 0x42080100L, 0#02080000L, 0#00000000L, 0x40080000L, 0x42000000L, 0#00080100L, 0#02000100L, 0x40000100L, 0#00080000L, 0#00000000L, 0x40080000L, 0#02080100L, 0x40000100L }; static unsigned long SP6[64] = { 0x20000010L, 0x20400000L, 0#00004000L, 0x20404010L, 0x20400000L, 0#00000010L, 0x20404010L, 0#00400000L, 0x20004000L, 0#00404010L, 0#00400000L, 0x20000010L, 0#00400010L, 0x20004000L, 0x20000000L, 0#00004010L, 0#00000000L, 0#00400010L, 0x20004010L, 0#00004000L, 0#00404000L, 0x20004010L, 0#00000010L, 0x20400010L, 0x20400010L, 0#00000000L, 0#00404010L, 0x20404000L, 0#00004010L, 0#00404000L, 0x20404000L, 0x20000000L, 0x20004000L, 0#00000010L, 0x20400010L, 0#00404000L, 0x20404010L, 0#00400000L, 0#00004010L, 0x20000010L, 0#00400000L, 0x20004000L, 0x20000000L, 0#00004010L, 0x20000010L, 0x20404010L, 0#00404000L, 0x20400000L, 0#00404010L, 0x20404000L, 0#00000000L, 0x20400010L, 0#00000010L, 0#00004000L, 0x20400000L, 0#00404010L, 0#00004000L, 0#00400010L, 0x20004010L, 0#00000000L, 0x20404000L, 0x20000000L, 0#00400010L, 0x20004010L }; Phần Phụ lục 323 static unsigned long SP7[64] = { 0#00200000L, 0#04200002L, 0#04000802L, 0#00000000L, 0#00000800L, 0#04000802L, 0#00200802L, 0#04200800L, 0#04200802L, 0#00200000L, 0#00000000L, 0#04000002L, 0#00000002L, 0#04000000L, 0#04200002L, 0#00000802L, 0#04000800L, 0#00200802L, 0#00200002L, 0#04000800L, 0#04000002L, 0#04200000L, 0#04200800L, 0#00200002L, 0#04200000L, 0#00000800L, 0#00000802L, 0#04200802L, 0#00200800L, 0#00000002L, 0#04000000L, 0#00200800L, 0#04000000L, 0#00200800L, 0#00200000L, 0#04000802L, 0#04000802L, 0#04200002L, 0#04200002L, 0#00000002L, 0#00200002L, 0#04000000L, 0#04000800L, 0#00200000L, 0#04200800L, 0#00000802L, 0#00200802L, 0#04200800L, 0#00000802L, 0#04000002L, 0#04200802L, 0#04200000L, 0#00200800L, 0#00000000L, 0#00000002L, 0#04200802L, 0#00000000L, 0#00200802L, 0#04200000L, 0#00000800L, 0#04000002L, 0#04000800L, 0#00000800L, 0#00200002L }; static unsigned long SP8[64] = { 0x10001040L, 0#00001000L, 0#00040000L, 0x10041040L, 0x10000000L, 0x10001040L, 0#00000040L, 0x10000000L, 0#00040040L, 0x10040000L, 0x10041040L, 0#00041000L, 0x10041000L, 0#00041040L, 0#00001000L, 0#00000040L, 0x10040000L, 0x10000040L, 0x10001000L, 0#00001040L, 0#00041000L, 0#00040040L, 0x10040040L, 0x10041000L, 0#00001040L, 0#00000000L, 0#00000000L, 0x10040040L, 0x10000040L, 0x10001000L, 0#00041040L, 0#00040000L, 0#00041040L, 0#00040000L, 0x10041000L, 0#00001000L, 0#00000040L, 0x10040040L, 0#00001000L, 0#00041040L, 0x10001000L, 0#00000040L, 0x10000040L, 0x10040000L, 0x10040040L, 0x10000000L, 0#00040000L, 0x10001040L, 0#00000000L, 0x10041040L, 0#00040040L, 0x10000040L, 0x10040000L, 0x10001000L, 0x10001040L, 0#00000000L, 0x10041040L, 0#00041000L, 0#00041000L, 0#00001040L, 0#00001040L, 0#00040040L, 0x10000000L, 0x10041000L }; static void desfunc(block, keys) register unsigned long *block, *keys; { register unsigned long fval, work, right, leftt; register int round; leftt = block[0]; right = block[1]; work = ((leftt >> 4) ^ right) & 0#0f0f0f0fL; right ^= work; leftt ^= (work << 4); Giáo trình Mật mã học 324 work = ((leftt >> 16) ^ right) & 0#0000ffffL; right ^= work; leftt ^= (work << 16); work = ((right >> 2) ^ leftt) & 0x33333333L; leftt ^= work; right ^= (work << 2); work = ((right >> 8) ^ leftt) & 0#00ff00ffL; leftt ^= work; right ^= (work << 8); right = ((right > 31) & 1L)) & 0xffffffffL; work = (leftt ^ right) & 0xaaaaaaaaL; leftt ^= work; right ^= work; leftt = ((leftt > 31) & 1L)) & 0xffffffffL; for( round = 0; round < 8; round++ ) { work = (right > 4); work ^= *keys++; fval = SP7[ work & 0x3fL]; fval |= SP5[(work >> 8) & 0x3fL]; fval |= SP3[(work >> 16) & 0x3fL]; fval |= SP1[(work >> 24) & 0x3fL]; work = right ^ *keys++; fval |= SP8[ work & 0x3fL]; fval |= SP6[(work >> 8) & 0x3fL]; fval |= SP4[(work >> 16) & 0x3fL]; fval |= SP2[(work >> 24) & 0x3fL]; leftt ^= fval; work = (leftt > 4); work ^= *keys++; fval = SP7[ work & 0x3fL]; fval |= SP5[(work >> 8) & 0x3fL]; fval |= SP3[(work >> 16) & 0x3fL]; fval |= SP1[(work >> 24) & 0x3fL]; work = leftt ^ *keys++; fval |= SP8[ work & 0x3fL]; fval |= SP6[(work >> 8) & 0x3fL]; fval |= SP4[(work >> 16) & 0x3fL]; fval |= SP2[(work >> 24) & 0x3fL]; right ^= fval; } right = (right > 1); work = (leftt ^ right) & 0xaaaaaaaaL; leftt ^= work; right ^= work; leftt = (leftt > 1); Phần Phụ lục 325 work = ((leftt >> 8) ^ right) & 0#00ff00ffL; right ^= work; leftt ^= (work << 8); work = ((leftt >> 2) ^ right) & 0x33333333L; right ^= work; leftt ^= (work << 2); work = ((right >> 16) ^ leftt) & 0#0000ffffL; leftt ^= work; right ^= (work << 16); work = ((right >> 4) ^ leftt) & 0#0f0f0f0fL; leftt ^= work; right ^= (work << 4); *block++ = right; *block = leftt; return; } /* Validation sets: * * Single-length key, single-length plaintext - * Key : 0123 4567 89ab cdef * Plain : 0123 4567 89ab cde7 * Cipher : c957 4425 6a5e d31d * **********************************************************************/ void des_key(des_ctx *dc, unsigned char *key){ deskey(key,EN0); cpkey(dc->ek); deskey(key,DE1); cpkey(dc->dk); } /* Encrypt several blocks in ECB mode. Caller is responsible for short blocks. */ void des_enc(des_ctx *dc, unsigned char *data, int blocks){ unsigned long work[2]; int i; unsigned char *cp; cp = data; for(i=0;iek); unscrun(work,cp); cp+=8; } } void des_dec(des_ctx *dc, unsigned char *data, int blocks){ unsigned long work[2]; int i; Giáo trình Mật mã học 326 unsigned char *cp; cp = data; for(i=0;idk); unscrun(work,cp); cp+=8; } } void main(void){ des_ctx dc; int i; unsigned long data[10]; char *cp,key[8] = {0#01,0x23,0x45,0x67,0x89,0xab,0xcd,0xef}; char x[8] = {0#01,0x23,0x45,0x67,0x89,0xab,0xcd,0xe7}; cp = x; des_key(&dc,key); des_enc(&dc,cp,1); printf("Enc(0..7,0..7) = "); for(i=0;i<8;i++) printf("%02x ", ((unsigned int) cp[i])&0#00ff); printf("\n"); des_dec(&dc,cp,1); printf("Dec(above,0..7) = "); for(i=0;i<8;i++) printf("%02x ",((unsigned int)cp[i])&0#00ff); printf("\n"); cp = (char *) data; for(i=0;i<10;i++)data[i]=i; des_enc(&dc,cp,5); /* Enc 5 blocks. */ for(i=0;i<10;i+=2) printf("Block %01d = %08lx %08lx.\n", i/2,data[i],data[i+1]); des_dec(&dc,cp,1); des_dec(&dc,cp+8,4); for(i=0;i<10;i+=2) printf("Block %01d = %08lx %08lx.\n", i/2,data[i],data[i+1]); } thuật ngữ viết tắt DES Data Encryption Standard Chuẩn mã dữ liệu LAN Local Area Network Mạng cục bộ MDV Mã dịch vòng MTT Mã thay thế MHV Mã hoán vị ECB Electronic Code Book Chế độ quyển mã điện tử CFB Cripher Feedback Chế độ phản hồi mã CBC Cripher Block Chaining Chế độ liên kết khối mã RSA Rivest - Shamir - Adleman MAC Message Authentication Code Mã xác thực thông báo OWHF Oneway Hash Funtion Hàm băm một chiều CRHF Collision Resistant hash function Hàm băm khó va chạm MDC Manipulation Detection Code Mã phát hiện sự sửa đổi LSB Least Signification Bit Bit thấp nhất (có giá trị nhỏ nhất Header Tiêu đề IDEA International Data Encryption Algorithm Thuật toán mã hóa dữ liệu quốc tế PGP Pretty Good Privacy Thuật toán mã hóa PGP SET Secure Electronic Transaction Giao dịch điện tử an toàn LFSR Linear Feedback Sequence Register Thanh ghi hồi tiếp tuyến tính Firewall Bức t−ờng lửa Server Máy chủ Router Bộ định tuyến tμi liệu tham khảo [1] A. J. Menezes, P. C. Van Oorschot, S. A. Vanstone. Handbook of applied cryptography. CRC Press 1998. [2] B. Schneier. Applied Cryptography. John Wiley Press 1996. [3] D. R. Stinson. Cryptography. Theory and Practice. CRC Press 1995. [4] Nguyen Binh. Crypto-system based on Cyclic Goemetric Progresssions over polynomial ring (Part 1). Circulant crypto- system over polynomial ring (Part 2) 8th VietNam Conference on Radio and Electronics, 11-2002 [5] M. R. A. Huth. Secure Communicating Systems. Cambridge University Press 2001. [6] W. Stallings. Network Security Essentials. Applications and Standards. Prentice Hall. 2000. [7] C. Pfleeger. Security in Computing. Prentice Hall. 1997. [8] R. Needham, M. Schroeder. Using Encryption for Authentication in large Networks of Computers. Comm ACM, v21 n12, Dec 1978. [9] G. Simmons. Contemporary Cryptology. IEEE Press 1992. [10] S. Bellovir, M. Merritt. Encrypted Key Exchange. Proc. IEEE Symp. Security and Privacy IEEE Comp Soc Press 1992. [11] D. Denning, D. Branstad. A Taxonomy of Key Escrow Encryption Systems. Comm ACM, v39 n3, Mar 1996. [12] M. Blum. Coin flipping by Telephone. SIGACT News, 1981. [13] S. Even. A Randomizing Protocol for Signing Contracts. Comm ACM, v28 n6, Jun 1985. [14] R. Merkle, M. Hellman. On the security of Multiple Encryption. Comm ACM, v24 n7, July 1981. [15] W. Tuchman, Hellman Presents No Shortcut Solutions to the DES. IEEE Spectrum, v16 n7, Jun 1979. [16] A.Shamir. Identity-based cryptorytions and signature schemes. Advanced in Cryptology - CRYPTO'84, LNCS196 Springer_Verlag, pp.47-53, 1985 [17] E.Okamoto, K.Tanaka. Key distribution system based on identification information. IEEE J.Selected Areas in communications, Vol.7,pp.481-485, 1989. Mục lục Lời nói đầu ................................................................................................ 5 Phần I. Các kiến thức toán học phụ trợ Ch−ơng 1: Bổ túc về lý thuyết số .......................................................... 9 1.1. Số nguyên ....................................................................................... 9 1.2. Các thuật toán trong Z ................................................................. 12 1.3. Các số nguyên modulo n .............................................................. 15 1.4. Các thuật toán trong Zn ............................................................... 22 1.5. Các ký hiệu Legendre vμ Jacobi .................................................. 24 1.6. Các số nguyên Blum ..................................................................... 30 Bμi tập ................................................................................................. 31 Ch−ơng 2: Đại số trừu t−ợng ............................................................... 35 2.1. Nhóm .............................................................................................. 35 2.2. Vμnh ............................................................................................... 38 2.3. Tr−ờng ............................................................................................ 39 2.4. Vμnh đa thức .................................................................................. 41 Bμi tập ................................................................................................... 53 Phần II. Các thuật toán mật mã Ch−ơng 3: Mật mã cổ điển .................................................................. 57 3.1. Sơ đồ khối một hệ truyền tin mật ................................................. 57 3.2. Mật mã thay thế ............................................................................ 58 3.3. Mật mã hoán vị .............................................................................. 62 3.4. Mật mã Hill .................................................................................... 64 3.5. Hệ mật xây dựng trên các cấp số nhân xyclic trên vμnh đa thức .......................................................................... 70 3.6. Mã Affine ........................................................................................ 81 3.7. Các hệ mật mã tích ........................................................................ 88 3.8. Các hệ mã dòng .............................................................................. 92 3.9. Chuẩn mã dữ liệu .......................................................................... 98 Bμi tập ................................................................................................ 120 Ch−ơng 4: Mật mã khoá công khai .................................................. 127 4.1. Giới thiệu về mật mã khoá công khai ......................................... 127 4.2. Hệ mật RSA ................................................................................. 130 4.3. Hệ mật Rabin .............................................................................. 133 4.4. Hệ mật El Gamal ......................................................................... 136 4.5. Hệ mật Merkle - Hellman ........................................................... 138 4.6. Hệ mật Chor - Rivest................................................................... 141 4.7. Hệ mật Mc Elice .......................................................................... 147 4.8. Các hμm băm vμ tính toμn vẹn của dữ liệu ................................ 153 Bμi tập ................................................................................................. 172 Phần III. Các thủ tục vμ ứng dụng Ch−ơng 5: Các thủ tục vμ các chú ý trong thực tế khi sử dụng mã hoá ....................................................... 177 5.1. Các thủ tục: hμnh vi vμ thứ tự ................................................... 177 5.2. Các thủ tục để giải quyết vấn đề ................................................ 184 5.3. Sử dụng mã hoá nh− thế nμo...................................................... 242 5.4. Cải thiện độ mật của hệ mật ...................................................... 249 5.5. Các chế độ mã hoá ....................................................................... 259 5.6. Tóm l−ợc về các thủ tục vμ các ứng dụng thực tế ...................... 263 Bμi tập ................................................................................................. 265 Ch−ơng 6: Các chuẩn vμ áp dụng ..................................................... 267 6.1. Bảo mật th− điện tử sử dụng PGP ............................................. 267 6.2. Giao dịch điện tử an toμn (set) ................................................... 273 6.3. ứng dụng xác thực - Kerberos .................................................... 279 Bμi tập ................................................................................................. 286 Phần phụ lục Phụ lục 1: Lý thuyết thông tin trong các hệ mật .......................... 289 Phụ lục 2: Tạo số giả ngẫu nhiên ................................................... 311 Phụ lục 3: Mã nguồn DES .............................................................. 316 Thuật ngữ viết tắt ................................................................................ 327 Tμi liệu tham khảo .............................................................................. 329 giáo trình mật mã học Chịu trách nhiệm xuất bản L−u Đức Văn Chịu trách nhiệm bản thảo học viện công nghệ b−u chính viễn thông Biên tập : Đμo thị minh - bùi đức khánh Chế bản : Vũ Hồng Nhung Sửa bản in : bùi đức khánh Trình bày bìa : Bùi ngọc khoa (Giáo trình này đ−ợc ban hành theo Quyết định số 219/QĐ-QLNCKH ngày 29/4/2003 của Giám đốc Học viện Công nghệ B−u chính Viễn thông) nhμ xuất bản b−u điện Trụ sở : 18 Nguyễn Du, TP. Hà Nội Điện thoại : 04-9431283, 04-9432438 Fax: 04-9431285 E-mail : bientap@hn.vnn.vn Chi nhánh : 27 Nguyễn Bỉnh Khiêm, Quận I, TP. Hồ Chí Minh Điện thoại : 08-9100925 Fax: 08-9100924 E-mail : chinhanh-nxbbd@hcm.vnn.vn M∙ số: HV 01 HM 04 M∙ số: HV 01 HM 04 M∙ số: HV 01 HM 04 In 700 cuốn, khổ 16 x 24 cm tại Công ty In Khoa học kỹ thuật Số xuất bản: 1783/521/XB-QLXB do Cục Xuất bản cấp ngày 19/12/2003 In xong và nộp l−u chiểu tháng 02 năm 2004.