Giáo trình Lý thuyết mật mã - Chương 1: Mật mã cổ điển

59 trang ngocly 3400

Download

Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Lý thuyết mật mã - Chương 1: Mật mã cổ điển", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

giao_trinh_ly_thuyet_mat_ma_chuong_1_mat_ma_co_dien.pdf

Nội dung text: Giáo trình Lý thuyết mật mã - Chương 1: Mật mã cổ điển

Ch−ơng 1 Mật m cổ điển 1.1 mở đầu - một số hệ mật đơn giản Đối t−ợng cơ bản của mật m là tạo ra khả năng liên lạc trên một kênh không mật cho hai ng−ời sử dụng (tạm gọi là Alice và Bob) sao cho đối ph−ơng (Oscar) không thể hiểu đ−ợc thông tin đ−ợc truyền đi. Kênh này có thể là một đ−ờng dây điện thoại hoặc một mạng máy tính. Thông tin mà Alice muốn gửi cho Bob (bản rõ) có thể là một văn bản tiếng Anh, các dữ liệu bằng số hoặc bất cứ tài liệu nào có cấu trúc tuỳ ý. Alice sẽ m hoá bản rõ bằng một khóa đ đ−ợc xác định tr−ớc và gửi bản m kết quả lên kênh liên lạc . Oscar có bản m thu trộm đ−ợc trên kênh song không thể xác định nội dung của bản rõ, nh−ng Bob (ng−ời đ biết khoá m ) có thể giải m và thu đ−ợc bản rõ. Ta sẽ mô tả hình thức hoá nội dung bằng cách dung khái niệm toán học nh− sau: Định nghĩa 1.1 Một hệ mật là một bộ 5 ( P,C,K,E,D ) thoả mn các điều kiện sau: 1. P là một tập hữu hạn các bản rõ có thể. 2. C là một tập hữu hạn các bản m có thể. 3. K (không gian khoá) là tập hữu hạn các khoá có thể. 4. Đối với mỗi k ∈ K có một quy tắc m ek: P → C và một quy tắcv giải m t−ơng ứng d k ∈ D. Mỗi ek: P → C và dk: C → P là những hàm mà: dk(e k (x)) = x với mọi bản rõ x ∈ P. Tính chất 4 là tính chất chủ yếu ở đây. Nội dung của nó là nếu một bản rõ x đ−ợc m hoá bằng ek và bản m nhận đ−ợc sau đó đ−ợc giải m bằng dk thì ta phải thu đ−ợc
bản rõ ban đầu x. Alice và Bob sẽ áp dụng thủ tục sau dùng hệ mật khoá riêng. Tr−ớc tiên họ chọn một khoá ngẫu nhiên K ∈ K . Điều này đ−ợc thực hiện khi họ ở cùng một chỗ và không bị Oscar theo dõi hoặc khi họ có một kênh mật trong tr−ờng hợp họ ở xa nhau. Sau đó giả sử Alice muốn gửi một thông baó cho Bob trên một kênh không mật và ta xem thông báo này là một chuỗi: x = x 1,x 2 ,. . .,x n với số nguyên n ≥ 1 nào đó. ở đây mỗi ký hiệu của mỗi bản rõ x i ∈ P , 1 ≤ i ≤ n. Mỗi x i sẽ đ−ợc m hoá bằng quy tắc m e k với khoá K xác định tr−ớc đó. Bởi vậy Alice sẽ tính y i = e k(x i), 1 ≤ i ≤ n và chuỗi bản m nhận đ−ợc: y = y 1,y 2 ,. . .,y n sẽ đ−ợc gửi trên kênh. Khi Bob nhận đ−ơc y1,y 2 ,. . .,y n anh ta sẽ giải m bằng hàm giải m d k và thu đ−ợc bản rõ gốc x 1,x 2 ,. . .,x n. Hình 1.1 là một ví dụ về một kênh liên lạc Hình 1.1. Kênh liên lạc Oscar Alic Bộ m Bộ giải Bo Kênh an toàn Nguồn khoá
Rõ ràng là trong tr−ờng hợp này hàm m hoá phải là hàm đơn ánh ( tức là ánh xạ 1-1), nếu không việc giải m sẽ không thực hiện đ−ợc một cách t−ờng minh. Ví dụ y = e k(x1) = e k(x2) trong đó x1 ≠ x2 , thì Bob sẽ không có cách nào để biết liệu sẽ phải giải m thành x1 hay x2 . Chú ý rằng nếu P = C thì mỗi hàm m hoá là một phép hoán vị, tức là nếu tập các bản m và tập các bản rõ là đồng nhất thì mỗi một hàm m sẽ là một sự sắp xếp lại (hay hoán vị ) các phần tử của tập này. 1.1.1 M dịch vòng ( shift cipher) Phần này sẽ mô tả m dịch (MD) dựa trên số học theo modulo. Tr−ớc tiên sẽ điểm qua một số định nghĩa cơ bản của số học này. Định nghĩa 1.2 Giả sử a và b là các số nguyên và m là một số nguyên d−ơng. Khi đó ta viết a ≡ b (mod m) nếu m chia hết cho b-a. Mệnh đề a ≡ b (mod m) đ−ợc gọi là " a đồng d− với b theo modulo m". Số nguyên m đ−ợc gọi là mudulus. Giả sử chia a và b cho m và ta thu đ−ợc th−ơng nguyên và phần d−, các phần d− nằm giữa 0 và m-1, nghĩa là a = q 1m + r 1 và b = q 2m + r 2 trong đó 0 ≤ r1 ≤ m-1 và 0 ≤ r2 ≤ m-1. Khi đó có thể dễ dàng thấy rằng a ≡ b (mod m) khi và chỉ khi r 1 = r 2 . Ta sẽ dùng ký hiệu a mod m (không dùng các dấu ngoặc) để xác định phần d− khi a đ−ợc chia cho m (chính là giá trị r 1 ở trên). Nh− vậy: a ≡ b (mod m) khi và chỉ khi a mod m = b mod m. Nếu thay a bằng a mod m thì ta nói rằng a đ−ợc rút gọn theo modulo m.
Nhận xét: Nhiều ngôn ngữ lập trình của máy tính xác định a mod m là phần d− trong dải - m+1, ., m-1 có cùng dấu với a. Ví dụ -18 mod 7 sẽ là -4, giá trị này khác với giá trị 3 là giá trị đ−ợc xác định theo công thức trên. Tuy nhiên, để thuận tiện ta sẽ xác định a mod m luôn là một số không âm. Bây giờ ta có thể định nghĩa số học modulo m: Z m đ−ợc coi là tập hợp {0,1,. . .,m-1} có trang bị hai phép toán cộng và nhân. Việc cộng và nhân trong Z m đ−ợc thực hiện giống nh− cộng và nhân các số thực ngoài trừ một điểm làcác kết quả đ−ợc rút gọn theo modulo m. Ví dụ tính 11 ì 13 trong Z 16 . T−ơng tự nh− với các số nguyên ta có 11 ì13 = 143. Để rút gọn 143 theo modulo 16, ta thực hiện phép chia bình th−ờng: 143 = 8 ì 16 + 15, bởi vậy 143 mod 16 = 15 trong Z 16 . Các định nghĩa trên phép cộng và phép nhân Z m thảo m n hầu hết các quy tắc quyen thuộc trong số học. Sau đây ta sẽ liệt kê mà không chứng minh các tính chất này: 1. Phép cộng là đóng, tức với bất kì a,b ∈ Z m ,a +b ∈ Zm 2. Phép cộng là giao hoán, tức là với a,b bất kì ∈ Z m a+b = b+a 3. Phép cộng là kết hợp, tức là với bất kì a,b,c ∈ Z m (a+b)+c = a+(b+c) 4. 0 là phần tử đơn vị của phép cộng, có nghĩa là với a bất kì ∈ Z m a+0 = 0+a = a 5. Phần tử nghịch đảo của phép cộngcủa phần tử bất kì (a ∈ Z m ) là m-a, nghĩa là a+(m-a) = (m-a)+a = 0 với bất kì a ∈ Z m .
6. Phép nhân là đóng , tức là với a,b bất kì ∈ Z m , ab ∈ Z m . 7. Phép nhân là giao hoán , nghĩa là với a,b bất kì ∈ Zm , ab = ba 8. Phép nhân là kết hợp, nghĩa là với a,b,c ∈ Z m , (ab)c = a(cb) 9. 1 là phần tử đơn vị của phép nhân, tức là với bất kỳ a ∈ Z m aì1 = 1 ìa = a 10. Phép nhân có tính chất phân phối đối với phép cộng, tức là đối với a,b,c ∈ Z m , (a+b)c = (ac)+(bc) và a(b+c) = (ab) + (ac) Các tính chất 1,3-5 nói lên rằng Z m lâp nên một cấu trúc đại số đ−ợc gọi là một nhóm theo phép cộng. Vì có thêm tính chất 4 nhóm đ−ợc gọi là nhóm Aben (hay nhóm gioa hoán). Các tính chất 1-10 sẽ thiết lập nên một vành Z m . Ta sẽ còn thấy nhiều ví dụ khác về các nhóm và các vành trong cuốn sách này. Một số ví dụ quên thuộc của vành là các số nguyên Z, các số thực R và các số phức C. Tuy nhiên các vành này đều vô hạn, còn mối quan tâm của chúng ta chỉ giới hạn trên các vành hữu hạn. Vì phần tử ng−ợc của phép cộng tồn tại trong Z m nên cũng có thể trừ các phần tử trong Z m . Ta định nghĩa a-b trong Z m là a+m-b mod m. Một cách t−ơng có thể tính số nguyên a-b rồi rút gon theo modulo m. Ví dụ : Để tính 11-18 trong Z 31 , ta tính 11+13 mod 31 = 24. Ng−ợc lại, có thể lấy 11-18 đ−ợc -7 rồid sau đó tính -7 mod 31 = 24.
Ta sẽ mô tả m dịch vòng trên hình 1.2. Nó đ−ợc xác định trên Z 26 (do có 26 chữ cái trên bảng chữ cái tiếng Anh) mặc dù có thể xác định nó trên Z m với modulus m tuỳ ý. Dễ dàng thấy rằng, MDV sẽ tạo nên một hệ mật nh− đ xác định ở trên, tức là d K (e K(x)) = x với mọi x ∈ Z 26 . Hình 1.2: M dịch vòng Giả sử P = C = K = Z26 với 0 ≤ k ≤ 25 , định nghĩa: eK(x) = x +K mod 26 và d K(x) = y -K mod 26 (x,y ∈ Z 26 ) Nhận xét: Trong tr−ờng hợp K = 3, hệ mật th−ờng đ−ợc gọi là m Caesar đ từng đ−ợc Julius Caesar sử dụng. Ta sẽ sử dụng MDV (với modulo 26) để m hoá một văn bản tiếng Anh thông th−ờng bằng cách thiết lập sự t−ơng ứnggiữa các kí tự và các thặng d− theo modulo 26 nh− sau: A ↔ 0,B ↔ 1, . . ., Z ↔ 25. Vì phép t−ơng ứng này còn dùng trong một vài ví dụ nên ta sẽ ghi lại để còn tiện dùng sau này: A B C D E F G H I J K L M 0 1 2 3 4 5 6 7 8 9 10 11 12 N O P Q R S T U V W X Y Z 13 14 15 16 17 18 19 20 21 22 23 24 25 Sau đây là một ví dụ nhỏ để minh hoạ Ví dụ 1.1: Giả sử khoá cho MDV là K = 11 và bản rõ là: wewillmeetatmidnight
Tr−ớc tiên biến đổi bản rõ thành d y các số nguyên nhờ dùng phép t−ơng ứng trên. Ta có: 22 4 22 8 11 11 12 4 4 19 0 19 12 8 3 13 8 6 7 19 sau đó cộng 11 vào mỗi giá trị rồi rút gọn 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 biến đổi d y số nguyên này thành các kí tự thu đ−ợc bản m sau: HPHTWWXPPELEXTOYTRSE Để giả m bản m này, tr−ớc tiên, Bob sẽ biến đổi bản m thành d y các số nguyên rồi trừ đi giá trịcho 11 ( rút gọn theo modulo 26) và cuối cùng biến đổi lại d y nàythành các ký tự. Nhận xét: Trong ví dụ trên , ta đ dùng các chữ in hoa ch o bản m , các chữ th−ờng cho bản rõ đêr tiện phân biệt. Quy tắc này còn tiếp tục sử dụng sau này. Nếu một hệ mật có thể sử dụng đ−ợc trong thực tế thì nó phảo thoả m n một số tính chất nhất định. Ngay sau đây sé nêu ra hai trong số đó: 1. Mỗi hàm m hoá e K và mỗi hàm giải m d K phải có khả năng tính toán đ−ợc một cách hiệu quả. 2. Đối ph−ơng dựa trên xâu bản m phải không có khả năng xác định khoá K đ dùng hoặc không có khả năng xác định đ−ợc xâu bản rõ x. Tính chất thứ hai xác định (theo cách khá mập mờ) ý t−ởng ý t−ởng "bảo mật". Quá trình thử tính khoá K
(khi đ biết bản m y) đ−ợc gọi là m thám (sau này khái niệm này sẽ đực làm chính xác hơn). Cần chú ý rằng, nếu Oscar có thể xác định đ−ợc K thì anh ta có thể giải m đ−ợc y nh− Bob bằng cách dùng d K. Bởi vậy, việc xác định K chí ít cũng khó nh− việc xác định bản rõ x. Nhận xét rằng, MDV (theo modulo 26) là không an toàn vì nó có thể bị thám theo ph−ơng pháp vét cạn. Do chỉ có 26 khoá nên dễ dàng thử mọi khoá d K có thể cho tới khi nhận đ−ợc bản rõ có nghĩa. Điều này đ−ợc minh hoạ theo ví dụ sau: Ví du 1.2 Cho bản m JBCRCLQRWCRVNBJENBWRWN ta sẽ thử liên tiếp các khoá giải m d 0 ,d 1 . và y thu đ−ợc: j b c r c l q r w c r v n b j e n b w r w n i a b q b k p q v b q u m a i d m a v q v m h z a p a j o p u a p t l z h c l z u p u l g y z o z i n o t z o s k y g b k y t o t k j x y n y h m n s y n r j e x f a j x s n s j e w x m x g l m r x m q i w e z i w r m r i d v w l w f k l q w l p h v o d y h v q l q h c u v k v e j k p v k o g u c x g u p k p g b t u j u d i j o u j n f t b w f o j o f a s t i t c h i n t i m e s a v e s n i n e Tới đây ta đ xác định đ−ợc bản rõ và dừng lại. Khoá t−ơng ứng K = 9. Trung bình có thể tính đ−ợc bản rõ sau khi thử 26/2 = 13 quy tắc giải m .
Nh− đ chỉ ra trong ví dụ trên , điều kiện để một hệ mật an toàn là phép tìm khoá vét cạn phải không thể thực hiện đ−ợc; tức không gian khoá phải rất lớn. Tuy nhiên, một không gian khoá lớn vẫn ch−a đủ đảm bảo độ mật. 1.1.2 M thay thế Một hệ mật nổi tiếng khác là hệ m thay thế. Hệ mật này đ đ−ợc sử dụng hàng trăm năm. Trò chơi đố chữ " cryptogram " trong các bài báo là những ví dụ về MTT. Hệ mật này đ−ợc nếu trên hình 1.3. Trên thực tế MTT có thể lấy cả P và C đều là bộ chữ cái tiếng anh, gồm 26 chữ cái. Ta dùng Z 26 trong MDV vì các phép m và giải m đều là các phép toán đại số. Tuy nhiên, trong MTT, thích hợp hơn là xem phép m và giải m nh− các hoán vị của các kí tự. Hình 1.3 M thay thế Cho P = C = Z26 . K chứa mọi hoán vị có thể của 26 kí hiệu 0,1, . . . ,25 Với mỗi phép hoán vị π ∈K , ta định nghĩa: eπ(x) = π(x) và dπ(y) = π -1(y) trong đó π -1 là hoán vị ng−ợc của π. Sau đây là một ví dụ về phép hoán vị ngẫu nhiên π tạo nên một hàm m hoá (cũng nh−b tr−ớc, các kí hiệu của bản rõ đ−ợc viết bằng chữ th−ờng còn các kí hiệu của bản m là chữ in hoa). a b c d e F g h i j k l M X N Y A H P O G Z Q W B T
n o p q r S t u v w x y Z S F L R C V M U E K J D I Nh− vậy, e π (a) = X, eπ (b) = N,. . . . Hàm giải m là phép hoán vị ng−ợc. Điều này đ−ợc thực hiện bằng cách viết hàng thứ hai lên tr−ớc rồi sắp xếp theo thứ tự chữ cái. Ta nhận đ−ợc: A B C D E F G H I J K L M d l r y v O h e z x w p T N O P Q R S T U V W X Y Z b g f j q N m u s k a c I Bởi vậy d π (A) = d, d π(B) = 1, . . . Để làm bài tập, bạn đọc có giải m bản m sau bằng cách dùng hàm giải m đơn giản: M G Z V Y Z L G H C M H J M Y X S S E M N H A H Y C D L M H A. Mỗĩ khoá của MTT là một phép hoán vị của 26 kí tự. Số các hoán vị này là 26!, lớn hơn 4 ì10 26 là một số rất lớn. Bởi vậy, phép tìm khoá vét cạn không thể thực hiện đ−ợc, thậm chí bằng máy tính. Tuy nhiên, sau này sẽ thấy rằng MTT có thể dễ dàng bị thám bằng các ph−ơng pháp khác. 1.1.3 M Affine MDV là một tr−ờng hợp đặc biệt của MTT chỉ gồm 26 trong số 26! các hoán vị có thể của 26 phần tử. Một tr−ờng hợp đặc biệt khác của MTT là m Affine đ−ợc mô tả d−ới đây. trong m Affine, ta giới hạn chỉ xét các hàm m có dạng:
e(x) = ax + b mod 26, a,b ∈ Z 26 . Các hàm này đ−ợc gọi là các hàm Affine (chú ý rằng khi a = 1, ta có MDV). Để việc giải m có thể thực hiện đ−ợc, yêu cầu cần thiết là hàm Affine phải là đơn ánh. Nói cách khác, với bất kỳ y ∈ Z 26 , ta muốn có đồng nhất thức sau: ax + b ≡ y (mod 26) phải có nghiệm x duy nhất. Đồng d− thức này t−ơng đ−ơng với: ax ≡ y-b (mod 26) Vì y thay đổi trên Z 26 nên y-b cũng thay đổi trên Z 26 . Bởi vậy, ta chỉ cần nghiên cứu ph−ơng trình đồng d−: ax ≡ y (mod 26) (y ∈ Z 26 ). Ta biết rằng, ph−ơng tfình này có một nghiệm duy nhất đối với mỗi y khi và chỉ khi UCLN(a,26) = 1 (ở đây hàm UCLN là −ớc chung lớn nhất của các biến của nó). Tr−ớc tiên ta giả sử rằng, UCLN(a,26) = d >1. Khi đó, đồng d− thức ax ≡ 0 (mod 26) sẽ có ít nhất hai nghiệm phân biệt trong Z 26 là x = 0 và x = 26/d. Trong tr−ờng hợp này, e(x) = ax + b mod 26 không phải là một hàm đơn ánh và bởi vậy nó không thể là hàm m hoá hợp lệ. Ví dụ, do UCLN(4,26) = 2 nên 4x +7 không là hàm m hoá hợp lệ: x và x+13 sẽ m hoá thành cùng một giá trị đối với bất kì x ∈ Z 26 . Ta giả thiết UCLN(a,26) = 1. Giả sử với x 1 và x 2 nào đó thảo m n:
ax 1 ≡ ax 2 (mod 26) Khi đó a(x 1- x 2) ≡ 0(mod 26) bởi vậy 26 | a(x 1- x 2) Bây giờ ta sẽ sử dụng một tính chất của phép chia sau: Nếu USLN(a,b)=1 và a bc thì a c. Vì 26  a(x 1- x 2) và USLN(a,26) = 1 nên ta có: 26 (x 1- x 2) tức là x1 ≡ x 2 (mod 26) Tới đây ta chứng tỏ rằng, nếu UCLN(a,26) = 1 thì một đồng d− thức dạng ax ≡ y (mod 26) chỉ có (nhiều nhất) một nghiệm trong Z 26 . Do đó , nếu ta cho x thay đổi trên Z 26 thì ax mod 26 sẽ nhận đ−ợc 26 giá trị khác nhau theo modulo 26 và đồng d− thức ax ≡ y (mod 26) chỉ có một nghiệm y duy nhất. Không có gì đặc biệt đối vơí số 26 trong khẳng định này. Bởi vậy, bằng cách t−ơng tự ta có thể chứng minh đ−ợc kết quả sau: Định lí 1.1 Đồng d− thức ax ≡ b mod m chỉ có một nghiệm duy nhất x ∈ Z m với mọi b ∈ Z m khi và chỉ khi UCLN(a,m) = 1. Vì 26 = 2 ì13 nên các giá trị a ∈ Z 26 thoả m n UCLN(a,26) = 1 là a = 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23 và 25. Tham số b có thể là một phần tử bất kỳ trong Z 26 . Nh− vậy, m Affine có 12 ì 26 = 312 khoá có thể ( dĩ nhiên con số này quá nhỉ để bảo đảm an toàn).
Bây giờ ta sẽ xét bài toán chung với modulo m. Ta cần một định nghĩa khác trong lý thuyết số. Định nghĩa 1.3 Giả sử a ≥ 1 và m ≥ 2 là các số nguyên. UCLN(a,m) = 1 thì ta nói rằng a và m là nguyên tố cùng nhau. Số các số nguyên trong Z m nguyên tố cùng nhau với m th−ờng đ−ợc ký hiệu là φ(m) ( hàm này đ−ợc gọi là hàm Euler). Một kết quả quan trọng trong lý thuyết số cho ta giá trị của φ(m) theo các thừa số trong phép phân tích theo luỹ thừa các số nguyên tố của m. ( Một số nguyên p >1 là số nguyên tố nếu nó không có −ớc d−ơng nào khác ngoài 1 và p. Mọi số nguyên m >1 có thể phân tích đ−ợc thành tích của các luỹ thừa các số nguyên tố theo cách duy nhất. Ví dụ 60 = 2 3 ì 3 ì 5 và 98 = 2 ì 7 2 ). Ta sẽ ghi lại công thức cho φ(m) trong định lí sau: Định lý 1.2. n ei Giả sử m = ∏ pi i=1 Trong đó các số nguyên tố p i khác nhau và ei >0 ,1 ≤ i ≤ n. ei ei −1 φ(m) = ∏ ( pi − pi ) i=1 Khi đó: Định lý này cho thấy rằng, số khoá trong m Affine trên Z m bằng m φ(m), trong đó φ(m) đ−ợc cho theo công thức trên. ( Số các phép chọn của b là m và số các phép chọn của a là φ(m) với hàm m hoá là e(x) = ax + b).
Ví dụ, khi m = 60, φ(60) = 2 ì 2 ì 4 = 16 và số các khoá trong m Affine là 960. Bây giờ ta sẽ xét xem các phép toán giải m trong mật m Affine với modulo m = 26. Giả sử UCLN(a,26) = 1. Để giải m cần giải ph−ơng trình đồng d− y ≡ax+b (mod 26) theo x. Từ thảo luận trên thấy rằng, ph−ơng trình này có một nghiệm duy nhất trong Z26 . Tuy nhiên ta vẫn ch−a biết một ph−ơng pháp hữu hiệu để tìm nghiệm. Điều cần thiết ở đây là có một thuật toán hữu hiệu để làm việc đó. Rất mayb là một số kết quả tiếp sau về số học modulo sẽ cung cấp một thuật toán giải m hữu hiệu cần tìm. Định nghĩa 1.4 Giả sử a ∈ Z m . Phần tử nghịch đảo (theo phép nhân) -1 -1 -1 của a là phần tử a ∈ Z m sao cho aa ≡ a a ≡ 1 (mod m). Bằng các lý luận t−ơng tự nh− trên, có thể chứng tỏ rằng a có nghịch đảo theo modulo m khi và chỉ khi UCLN(a,m) =1, và nếu nghịch đảo này tồn tại thì nó phải là duy nhất. Ta cũng thấy rằng, nếu b = a -1 thì a = b -1 . Nếu p là số nguyên tố thì mọi phần tử khác không của ZP đều có nghịch đảo. Một vành trong đó mọi phần tử đều có nghịch đảo đ−ợc gọi là một tr−ờng. Trong phần sau sẽ mô tả một thuật toán hữu hiệu để tính các nghịch đảo của Z m với m tuỳ ý. Tuy nhiên, trong Z 26 , chỉ bằng ph−ơng pháp thử và sai cũng có thể tìm đ−ợc các nghịch đảo của các phần tử nguyên tố cùng nhau với 26: 1 -1 = 1, 3 -1 = 9, 5 -1 = 21, 7 -1 = 15, 11 -1 = 19, 17 -1 =23, 25 -1 = 25. (Có thể dễ dàng kiểm chứng lại điều này, ví dụ: 7 ì 5 = 105 ≡ 1 mod 26, bởi vậy 7 -1 = 15).
Xét ph−ơng trình đồng d− y ≡ ax+b (mod 26). Ph−ơng trình này t−ơng đ−ơng với ax ≡ y-b ( mod 26) Vì UCLN(a,26) =1 nên a có nghịch đảo theo modulo 26. Nhân cả hai vế của đồng d− thức với a -1 ta có: a-1(ax) ≡ a -1(y-b) (mod 26) áp dụng tính kết hợp của phép nhân modulo: a-1(ax) ≡ (a -1a)x ≡ 1x ≡ x. Kết quả là x ≡ a -1(y-b) (mod 26). Đây là một công thức t−ờng minh cho x. Nh− vậy hàm giải m là: d(y) = a -1(y-b) mod 26 Hình 1.4 cho mô tả đầy đủ về m Affine. Sau đây là một ví dụ nhỏ Cho P = C = Z26 và giả sử P = { (a,b) ∈ Z26 ì Z26 : UCLN(a,26) =1 } Với K = (a,b) ∈K , ta định nghĩa: eK(x) = ax +b mod 26 và -1 dK(y) = a (y-b) mod 26, x,y ∈ Z26 Hình 1.4 Mật mA ffine Ví dụ 1.3 Giả sử K = (7,3). Nh− đ nêu ở trên, 7 -1 mod 26 = 15. Hàm m hoá là
eK(x) = 7x+3 Và hàm giải m t−ơng ứng là: dK(x) = 15(y-3) = 15y -19 ở đây, tất cả các phép toán đều thực hiện trên Z 26 . Ta sẽ kiểm tra liệu d K(e K(x)) = x với mọi x ∈ Z 26 không?. Dùng các tính toán trên Z 26 , ta có dK(e K(x)) =d K(7x+3) =15(7x+3)-19 = x +45 -19 = x. Để minh hoạ, ta h y m hoá bản rõ " hot ". Tr−ớc tiên biến đổi các chữ h, o, t thành các thặng du theo modulo 26. Ta đ−ợc các số t−ơng ứng là 7, 14 và 19. Bây giờ sẽ m hoá: 7 ì 7 +3 mod 26 = 52 mod 26 = 0 7 ì 14 + 3 mod 26 = 101 mod 26 =23 7 ì 19 +3 mod 26 = 136 mod 26 = 6 Bởi vậy 3 ký hiệu của bản m là 0, 23 và 6 t−ơng ứng với xâu ký tự AXG. Việc giải m sẽ do bạn đọc thực hiện nh− một bài tập. 1.1.4 M Vigenère Trong cả hai hệ MDV và MTT (một khi khoá đ đ−ợc chọn) mỗi ký tự sẽ đ−ợc ánh xạ vào một ký tự duy nhất. Vì lý do đó, các hệ mật còn đ−ợc gọi hệ thay thế đơn biểu. Bây giờ ta sẽ trình bày ( trong hùnh 1.5) một hệ mật không phải là bộ chữ đơn, đó là hệ m Vigenère nổi
tiếng. Mật m này lấy tên của Blaise de Vigenère sống vào thế kỷ XVI. Sử dụng phép t−ơng ứng A ⇔ 0, B ⇔ 1, . . . , Z ⇔ 25 mô tả ở trên, ta có thể gắn cho mỗi khoa K với một chuỗi kí tự có độ dài m đ−ợc gọi là từ khoá. Mật m Vigenère sẽ m hoá đồng thời m kí tự: Mỗi phần tử của bản rõ t−ơng đ−ơng với m ký tự. Xét một ví dụ nhỏ Ví dụ 1.4 Giả sử m =6 và từ khoá là CIPHER. Từ khoá này t−ơng ứng với d y số K = (2,8,15,4,17). Giả sử bản rõ là xâu: thiscryptosystemisnotsecure Hình 1.5 Mật m Vigenère Cho m là một số nguyên d−ơng cố định nào đó. Định m nghĩa P = C = K = (Z26 ) . Với khoá K = (k1, k2, . . . ,km) ta xác định : eK(x 1, x2, . . . ,xm) = (x 1+k 1, x2+k2, . . . , x m+km) và dK(y 1, y2, . . . , ym) = (y 1-k1, y2-k2, . . . , y m-km) Ta sẽ biến đổi các phần tử của bản rõ thành các thặng d− theo modulo 26, viết chúng thành các nhóm 6 rồi cộng với từ khoá theo modulo 26 nh− sau:
19 7 8 18 2 17 24 15 19 14 18 24 2 8 15 7 4 17 2 8 15 7 4 17 21 15 23 25 6 8 0 23 8 21 22 15 18 19 4 12 8 18 13 14 19 18 4 2 2 8 15 7 4 17 2 8 15 7 4 17 20 1 19 19 12 9 15 22 8 15 8 19 20 17 4 2 8 15 Bởi vậy, d y ký tự t−ơng ứng của xâu bản m sẽ là: 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 Để giải m ta có thể dùng cùng từ khoá nh−ng thay cho cộng, ta trừ cho nó theo modulo 26. Ta thấy rằng các từ khoá có thể với số độ dài m trong mật m Vigenère là 26 m, bởi vậy, thậm chí với các giá trị m khá nhỏ, ph−ơng pháp tìm kiếm vét cạn cũng yêu cầu thời gian khá lớn. Ví dụ, nếu m = 5 thì không gian khoá cũng có kích th−ớc lớn hơn 1,1 ì 10 7 . L−ợng khoá này đ đủ lớn để ngaen ngừa việc tìm khoá bằng tay( chứ không phải dùng máy tính). Trong hệ mật Vigenère có từ khoá độ dài m,mỗi ký tự có thể đ−ợc ánh xạ vào trong m ký tự có thể có (giả sử rằng từ khoá chứa m ký tự phân biệt). Một hệ mật nh− vậy đ−ợc gọi là hệ mật thay thế đa biểu (polyalphabetic). Nói chung, việc thám m hệ thay thế đa biểu sẽ khó khăn hơn so việc thám m hệ đơn biểu.
1.1.5 Mật m Hill Trong phần này sẽ mô tả một hệ mật thay thế đa biểu khác đ−ợc gọi là mật m Hill. Mật m này do Lester S.Hill đ−a ra năm 1929. Giả sử m là một số nguyên m d−ơng, đặt P = C = (Z26 ) . ý t−ởng ở đây là lấy m tổ hợp tuyến tính của m ký tự trong một phần tử của bản rõ để tạo ra m ký tự ở một phần tử của bản m . Ví dụ nếu m = 2 ta có thể viết một phần tử của bản rõ là x = (x 1,x 2) và một phần tử của bản m là y = (y 1,y 2). ở đây, y 1cũng nh− y 2 đều là một tổ hợp tuyến tính của x1và x 2. Chẳng hạn, có thể lấy y1 = 11x 1+ 3x 2 y2 = 8x 1+ 7x 2 Tất nhiên có thể viết gọn hơn theo ký hiệu ma trận nh− sau 11 8 (y 1 y 2) = (x 1 x ) 3 7 Nói chung, có thể lấy một ma trận K kích th−ớc m ì m làm khoá. Nếu một phần tử ở hàng i và cột j của K là ki,,j thì có thể viết K = (k i,,j ), với x = (x 1, x2, . . . ,xm) ∈ P và K ∈K , ta tính y = e K(x) = (y 1, y2, . . . ,ym) nh− sau: k1,1 k1,2 . k (y 1,. . ., ym) (x 1, . . . 1,m ,x ) k2,1 k2,2 k2,m
Nói một cách khác y = xK. Chúng ta nói rằng bản m nhận đ−ợc từ bản rõ nhờ phép biến đổi tuyến tính. Ta sẽ xét xem phải thực hiện giải m nh− thế nào, tức là làm thế nào để tính x từ y. Bạn đọc đ làm quen với đại số tuyến tính sẽ thấy rằng phải dùng ma trận nghịch đảo K -1 để giả m . Bản m đ−ợc giải m bằng công thức y K -1 . Sau đây là một số định nghĩa về những khái niệm cần thiết lấy từ đại số tuyến tính. Nếu A = (x i,j ) là một ma trận cấp l ì m và B = (b 1,k ) là một ma trận cấp m ì n m c1,k = Σ a i,j bj,k j=1 thì tích ma trận AB = (c 1,k ) đ−ợc định nghĩa theo công thức: Với 1 ≤ i ≤ l và 1 ≤ k ≤ l. Tức là các phần tử ở hàng i và cột thứ k của AB đ−ợc tạo ra bằng cách lấy hàng thứ i của A và cột thứ k của B, sau đó nhân t−ơng ứng các phần tử với nhau và cộng lại. Cần để ý rằng AB là một ma trận cấp l ì n. Theo định nghĩa này, phép nhân ma trận là kết hợp (tức (AB)C = A(BC)) nh−ng noiâ chung là không giao hoán ( không phải lúc nào AB = BA, thậm chí đố với ma trận vuông A và B). Ma trận đơn vị m ì m (ký hiệu là I m ) là ma trận cấp m ì m có các số 1 nằm ở đ−ờng chéo chính và các số 0 ở vị trí còn lại. Nh− vậy ma trận đơn vị 2 ì 2 là: 1 0 0 1
I2 = Im đ−ợc gọi là ma trận đơn vị vì AI m = A với mọi ma trận cấp l ì m và I mB =B với mọi ma trận cấp m ì n. Ma trận nghịch đảo của ma trận A cấp m ì m ( nếu tồn tại) là ma -1 -1 -1 trận A sao cho AA = A A = I m . Không phải mọi ma trận đều có nghịch đảo, nh−ng nếu tồn tại thì nó duy nhất. Với các định nghĩa trên, có thể dễ dàng xây dựng công thức giải m đ nêu: Vì y = xK, ta có thể nhân cả hai vế của đẳng thức với K -1 và nhận đ−ợc: -1 -1 -1 yK = (xK)K = x(KK ) = xI m = x ( Chú ý sử dụng tính chất kết hợp) Có thể thấy rằng, ma trận m hoá ở trên có -1 11 8 7 18 3 7 = 23 11 nghịch đảo trong Z 26 : vì 12 8 8 18 11 7+8 23 11 18+8 11 = ì ì ì ì 3 7 23 11 3 ì7+7 ì23 3 ì18+7 ì11 261 286 1 0 = = 182 131 0 1 (H y nhớ rằng mọi phép toán số học đều đ−ợc thực hiện theo modulo 26).
Sau đây là một ví dụ minh hoạ cho việc m hoá và iải m trong hệ mật m Hill. Via dụ 1.5 11 8 = Giả sử khoá K 3 7 Từ các tính toán trên ta có: 7 18 K-1 = 23 11 Giả sử cần m hoá bản rõ "July". Ta có hai phần tử của bản rõ để m hoá: (9,20) (ứng với Ju) và (11,24) (ứng với ly). 11 8 (9,20) = (99+60, 72+140) = (3,4) 3 7 Ta tính nh− sau: và Bởi vậy bản m của July là DELW. Để giải m Bob sẽ tính và Nh− vậy Bob đ nhận đ−ợc bản đúng. 11 8 (11,24) = (121+72, 88+168) = (11,22) 73 18 7 (3,4) = (9,20) 23 11 Cho tới lúc này ta đ chỉ ra rằng có thể thực hiện 7 18 (11,22) = (11,24) 23 11 phép giải m nếu K có một nghịch đảo. Trên thực tế, để phép giải m là có thể thực hiện đ−ợc, điều kiện cần là K phải có nghịch đảo. ( Điều này dễ dàng rút ra từ đại
số tuyến tính sơ cấp, tuy nhiên sẽ không chứng minh ở đây). Bởi vậy, chúng ta chỉ quan tâm tới các ma trận K khả nghich. Tính khả nghịch của một ma trận vuông phụ thuộc vào giá trị định thức của nó. Để tránh sự tổng quát hoá không cần thiết, ta chỉ giới hạn trong tr−ờng hợp 2 ì2. Định nghĩa 1.5 Định thức của ma trận A = (a ,i j ) cấp 2 ì 2 là giá trị det A = a 1,1 a 2,2 - a 1,2 a 2,1 Nhận xét: Định thức của một ma trận vuông cấp mm có thể đ−ợc tính theo các phép toán hằng sơ cấp: h y xem một giáo trình bất kỳ về đại số tuyến tính. Hai tính chất quan trọng của định thức là det I m = 1 và quy tắc nhân det(AB) = det A ì det B. Một ma trận thức K là có nghịch đảo khi và chỉ khi định thức của nó khác 0. Tuy nhiên, điều quan trọng cần nhớ là ta đang làm việc trên Z 26 . Kết quả t−ơng ứng là ma trận K có nghịch đảo theo modulo 26 khi và chỉ khi UCLN(det K,26) = 1. Sau đây sẽ chứng minh ngắn gọn kết quả này. Tr−ớc tiên, giả sử rằng UCLN(det K,26) = 1. Khi đó det K có nghịch đảo trong Z 26 . Với 1 ≤ i ≤ m, 1 ≤ j ≤ m, định nghĩa K i j ma trận thu đ−ợc từ K bằng cách loại bỏ hàng thứ i và cột thứ j. Và định nghĩa ma trận K * có phần tử * (i,j) của nó nhận giá trị(-1) det K j i (K đ−ợc gọi là ma trận bù đại số của K). Khi đó có thể chứng tỏ rằng:
K-1 = (det K) -1K* . Bởi vậy K là khả nghịch. Ng−ợc lại K có nghịch đảo K -1 . Theo quy tắc nhân của định thức 1 = det I = det (KK -1) = det K det K -1 Bởi vậy det K có nghịch đảo trong Z 26 . Nhận xét: Công thức đối với ở trên không phải là một công thức tính toán có hiệu quả trừ các tr−ờng hợp m nhỏ ( chẳng hạn m = 2, 3). Vớim lớn, ph−ơng pháp thích hợp để tính các ma trận nghịch đảo phải dựa vào các phép toán hằng sơ cấp. Trong tr−ờng hợp 2 ì2, ta có công thức sau: Định lý 1.3 Giả sử A = (a i j ) là một ma trận cấp 2 ì 2 trên Z 26 sao cho det A = a 1,1 a2,2 - a 1,2 a 2,1 có nghịch đảo. Khi đó a2,2 -a1,2 A-1 = (det A) -1 -a2,1 a 1,1 Trở lại ví dụ đ xét ở trên . Tr−ớc hết ta có: det 11 8 = 11 ì 7 - 8 ì3 mod 2 3 7 = 77 - 24 mod 26 = 53 mod 26 Vì 1 -1 mod 26 = 1 nên ma trận nghịch đảo là -1 11 8 7 18 3 7 = 23 11 Đây chính là ma trận đ có ở trên.
Bây giờ ta sẽ mô tả chính xác mật m Hill trên Z 26 (hình 1.6) Hình 1.6 Mật m HILL Cho m là một số nguyên d−ơng có định. Cho P = C = m (Z26 ) và cho K = { các ma trận khả nghịch cấp m ì m trên Z26 } Với một khoá K ∈K ta xác định eK(x) = xK 1.1.5 M hoán vị (MHV) Tất cả các hệ mật thảo luận ở trên ít nhiều đều xoay quanh phép thaythế: các ký tự của bản rõ đ−ợc thay thế bằng các ký tự khác trongbản m . ý t−ởng của MHV là giữ các ký tự của bản rõ không thay đổi nh−ng sẽ thay đôỉi vị trí của chúng bằng cách sắp xếp lại các ký tự này. MHV (còn đ−ợc gọi là m chuyển vị) đ đ−ợc dùng từ hàng trăm năm nay. Thật ra thì sự phân biệt giữa MHV và MTT đ đ−ợc Giovani Porta chỉ ra từ 1563. Định nghĩa hình thức cho MHV đ−ợc nêu ra trên hình 1.7. Không giống nh− MTT, ở đây không có các phép toán đại số nào cần thực hiện khi m hoá và giải m nên thích hợp hơn cả là dùng các ký tự mà không dùng các thặng d− theo modulo 26. D−ới đây là một ví dụ minh hoạ Ví dụ 1.6 Giả sử m = 6 và khoá là phép hoán vị ( π ) sau: 1 2 3 4 5 6 3 5 1 6 4 2
Hình 1.7 M hoán vị Khi đó phép hoán vị ng−ợc π -1 sẽ là: 1 2 3 4` 5 6 Cho m là mộ số nguyên d−ơng xác định nào đó. Cho m P = C = (Z26 ) 3 và 6cho K1 gồm5 tất2 cả các4 hoán vị của {1, . . ., m}. Đối một khoá π ( tức là một hoán vị) ta xác định eπ(x1, . . . , x m ) = (xπ(1) , . . . , xπ(m) ) -1 -1 và dπ(x1, . . . , x m ) = (y π (1) , . . . , y π (m) ) Bây giờ giả sử có bản rõ Shesellsseashellsbytheseashore Tr−ớc tiên ta nhóm bản rõ thành các nhóm 6 ký tự: shesel | lsseas | hellsb | ythese | ashore Bây giờ mỗi nhóm 6 chữ cái đ−ợc sắp xếp lại theo phép hoán vị π, ta có: EESLSH | SALSES | LSHBLE | HSYEET | HRAEOS Nh− vậy bản m là EESLSH SALSES LSHBLE HSYEET HRAEOS Nh− vậy bản m đ đ−ợc m theo cách t−ơng tự banừg phép hoán vị đảo π -1. Thực tế m hoán vị là tr−ờng hợp đặc biệt của mật m Hill. Khi cho phép hoán vị π của tập {1, . . . ,m}, ta có thể xác định một ma trận hoán vị m ì m thích hợp K π = 1 nếu j = π(i) ki,j = 0 với các tr−ờng hợp
{ k i,j } theo công thức: ( ma trận hoán vị là ma trận trong đó mỗi hàng và mỗi cột chỉ có một số "1", còn tất cả các giá trị khác đều là số "0". Ta có thể thu đ−ợc một ma trận hoán vị từ ma trận đơn vị bằng cách hoán vị các hàng hoặc cột). Dễ dàng thấy rằng, phép m Hill dùng ma trận K π trên thực tế t−ơng đ−ơng với phép m hoán vị dùng -1 -1 hoán vị π. Hơn nữa K π= K π tức ma trận nghịch đảo của -1 Kπ là ma trận hoán vị xác định theo hoán vị π . Nh− vậy, phép giải m Hill t−ơng đ−ơng với phép giải m hoán vị. Đối với hoán vị π đ−ợc dung trong ví dun trên, các ma trận hoán vị kết hợp là: 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 0 Kπ = -1 0 0 0 0 1 0 và K π = 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 1 0 0 0 0 Bạn đọc có thể kiểm tra để thấy rằng, tích của hai ma trạn này là một ma trận đơn vị. 1.1.7 Các hệ m dòng Trong các hệ mật nghiên cứu ở trên, cácb phần tử liên tiếp của bản rõ đều đ−ợc m hoá bằng cùng một khoá K. Tức xâu bản m y nhạn đ−ợc có dạng: y = y1y2. . . = eK(x1) e K(x2 ) . . . Các hệ mật thuộc dạng này th−ờng đ−ợc gọi là các m khối. Một quan điểm sử dụng khác là mật m
dòng. ý t−ởng cơ bản ở đây là tạo ra một dòng khoá z = z 1z2 . . . và dùng nó để m hoá một xâu bản rõ x = x1x2 . . . theo quy tắc: y = y1y2. . . = ez1 (x1) e z2 (x1). . . M dòng hoạt động nh− sau. Giả sử K ∈K là khoá và x = x1x2 . . .là xâu bản rõ. Hàm fi đ−ợc dùng để tạo zi (zi là phần tử thứ i của dòng khoá) trong đó fi là một hàm của khoá K và i-1 là ký tự đầu tiên của bản rõ: zi = fi (K, x1 , . . ., xi -1 ) Phần tử zi của dòng khoá đ−ợc dùng để m xi tạo ra yi = eiz (xi). Bởi vậy, để m hoá xâu bản rõ x1 x 2 . . . ta phải tính liên tiếp: z1, y1, z 2 , y 2 Việc giải m xâu bản m y1y2. . . có thể đ−ợc thực hiện bằng cách tính liên tiếp: z1, x1, z 2 , x 2 Sau đây làb định nghĩa d−ới dạng toán học: Định nghĩa 1.6. Mật m dòng là một bộ ( P,C,K,L,F,E,D ) thoả mn d−ợc các điều kiện sau: 1. P là một tập hữu hạn các bản rõ có thể. 2. C là tập hữu hạn các bản m có thể. 3. K là tập hữu hạn các khoá có thể ( không gian khoá) 4. L là tập hữu hạn các bộ chữ của dòng khoá. 5. F = (f1 f 2 ) là bộ tạo dòng khoá. Với i ≥ 1 i -1 fi : K ì P →L 6. Với mỗi z ∈L có một quy tắc m ez ∈ E và một quy tắc giải m t−ơng ứng dz ∈D . ez : P →C và dz : C →P là các hàm thoả mn dz(ez(x))= x với mọi bản rõ x ∈ P.
Ta có thể coi m khối là một tr−ờng hợp đặc biệt của m dòng trong đó dùng khoá không đổi: Zi = K với mọi i ≥1. Sau đây là một số dạng đặc biệt của m dòng cùng với các ví dụ minh hoạ. M dòng đ−ợc gọi là đồng bộ nếu dòng khoá không phụ thuộc vào xâu bản rõ, tức là nếu dòng khoá đựoc tạo ra chỉ là hàm của khoá K. Khi đó ta coi K là một "mần" để mở rộng thành dòng khoá z1z2 . . . Một hệ m dòng đ−ợc gọi là tuần hoàn với chu kỳ d nếu zi+d = zi với số nguyên i ≥ 1. M Vigenère với độ dài từ khoá m có thể coi là m dòng tuần hoàn với chu kỳ m. Trong tr−ờng hợp này, khoá là K = (k1, . . . km ). Bản thân K sẽ tạo m phần tử đầu tiên của dòng khoá: zi = k i, 1 ≤ i ≤ m. Sau đó dòng khoá sẽ tự lặp lại. Nhận thấy rằng, trong m dòng t−ơng ứng với mật m Vigenère, các hàm m và giải m đ−ợc dùng giống nh− các hàm m và giải m đ−ợc dùng trong MDV: ez(x) = x+z và dz(y) = y-z Các m dòng th−ờng đ−ợc mô tả trong các bộ chữ nhi phân tức là P= C=L= Z2. Trong tr−ờng hợp này, các phép toán m và giải m là phép cộng theo modulo 2. ez(x) = x +z mod 2 và dz(x) = y +z mod 2. Nếu ta coi "0" biểu thị giá trị "sai" và "1" biểu thị giá trị "đúng" trong đại số Boolean thì phép cộng theo moulo 2 sẽ ứng với phép hoặc có loại trừ. Bởi vậy phép m (và giải m ) dễ dàng thực hiện bằng mạch cứng. Ta xem xét một ph−ơng pháp tạo một dòng khoá (đồng bộ ) khác. Giả sử bắt đầu với (k1, . . , km ) và zi = ki, 1 ≤ i ≤ m ( cũng giống nh− tr−ớc đây), tuy nhiên bây giờ ta
tạo dòng khoá theo một quan hệ đệ quy tuyến tính cấp m: m-1 zi+m = ∑ cj zi+j mod 2 j=0 trong đó c0, . . , cm-1 ∈ Z2 là các hằng số cho tr−ớc. Nhận xét: Phép đệ quy đ−ợc nói là có bậc m vì mỗi số hạng phụ thuộc vào m số hạng đứng tr−ớc. Phép đệ quy này là tuyến tính bởi vì Z i+m là một hàm tuyến tính của các số hạng đứng tr−ớc. Chú ý ta có thể lấy c0= 1 mà không làm mất tính tổng quát. Trong tr−ờng hợp ng−ợc lại phép đệ quy sẽ là có bậc m-1. ở đây khoá K gồm 2m giá trị k1, . . , km, c 0, . . , cm-1. Nếu (k1, . . , km)= (0, . . . , 0) thì dòng khoá sẽ chứa toàn các số 0. Dĩ nhiên phải tránh điều này vì khi đó bản m sẽ đồng nhất với bản rõ. Tuy nhiên nếu chọn thích hợp các hằng số c0, . . , cm-1 thì một véc tơ khởi đầu bất kì khác m (k1, . . , km) sẽ tạo nên một dòng khoá có chu kỳ 2 -1. Bởi vậy một khoá ngắn sẽ tạo nên một dòng khoá có chu kỳ rất lớn. Đây là một tính chất rất đáng l−u tâm vì ta sẽ thấy ở phần sau, mật m Vigenère có thể bị thám nhờ tận dụng yếu tố dòng khoá có chu kỳ ngắn. Sau đây là một ví dụ minh hoạ: Ví dụ 1.7 Giả sử m = 4 và dòng khoá đ−ợc tạo bằng quy tắc: zi+4 = zi + zi+1 mod 2 Nếu dòng khoá bắt đầu một véc tơ bất kỳ khác với véc tơ (0,0,0,0) thì ta thu đ−ợc dòng khoá có chu kỳ 15. Ví dụ bắt đầu bằng véc tơ (1,0,0,0), dòng khoá sẽ là: 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1 Một véc tơ khởi đầu khác không bất kỳ khác sẽ tạo một hoán vị vòng (cyclic) của cùng dòng khoá.
Một h−ớng đáng quan tâm khác của ph−ơng pháp tạo dòng khoá hiệu quả bằng phần cứng là sử dụng bộ ghi dịch hồi tiếp tuyến tính (hay LFSR). Ta dùng một bộ ghi dịch có m tầng. Véc tơ (k1, . . , km) sẽ đ−ợc dùng để khởi tạo ( đặt các giá trị ban đầu) cho thanh ghi dịch. ở mỗi đơn vị thời gian, các phép toán sau sẽ đ−ợc thực hiện đồng thời. 1. k1 đ−ợc tính ra dùng làm bit tiếp theo của dòng khoá. 2. k2, . . , km sẽ đ−ợc dịch một tầng về phía trái. 3. Giá trị mới của sẽ đ−ợc tính bằng: m-1 ∑ c jkj+1 j=0 (đây là hồi tiếp tuyến tính) Ta thấy rằng thao tác tuyến tính sẽ đ−ợc tiến hành bằng cách lấy tín hiệu ra từ một số tầng nhất định của thanh ghi (đ−ợc xác định bởi các hằng số cj có giá trị "1" ) và tính tổng theo modulo 2 ( là phép hoặc loại trừ ). Hình 1.8 cho mô tả của LFSR dùng để tạo dòng khoá cho ví dụ 1.7. Hình 1.8 Thanh ghi dịch hồi tiếp tuyến tính (LFSR) + k1 k2 k3 k4
Một ví dụ về m dòng không đồng bộ là m khoá tự sinh đ−ợc cho ở hình 1.9. Hình nh− mật m này do Vigenère đề xuất. Hình 1.9. Mật m khoá tự sinh Cho P = C = K = L = Z26 Cho z 1 = K và z i = x i-1 (i ≥ 2) Với 0 ≤ z ≤ 25 ta xác định ez(x) = x + z mod 26 dz(y) = y - z mod 26 (x,y ∈ Z26 ) Lý do sử dụng thuật nghữ "khoá tự sinh" là ở chỗ: bản rõ đ−ợc dùng làm khoá ( ngoài "khoá khởi thuỷ" ban đầu K). Sau đây là một ví dụ minh hoạ Ví dụ 1.8: Giả sử khoá là k = 8 và bản rõ là rendezvous . Tr−ớc tiên ta biến đổi bản rõ thành d y các số nguyên: 17 4 13 3 4 25 21 14 20 18 Dòng khoá nh− sau: 8 17 4 13 3 4 25 21 14 20 Bây giờ ta cộng các phần tử t−ơng ứng rồi rút gọn theo modulo 26: 25 21 17 16 7 3 20 9 8 12
Bản m ở dạng ký tự là: ZVRQHDUJIM Bây giờ ta xem Alice giải m bản m này nh− thế nào. Tr−ớc tiên Alice biến đổi xâu kí tự thành d y số: 25 21 17 16 7 3 20 9 8 12 Sau đó cô ta tính: x1 = d8(25) = 25 - 8 mod 26 = 17 và x 2 = d17 (21) = 21 - 17 mod 26 = 4 và cứ tiếp tục nh− vậy. Mỗi khi Alice nhận đ−ợc một ký tự của bản rõ, cô ta sẽ dùng nó làm phần tử tiếp theo của dòng khoá. Dĩ nhiên là m dùng khoá tự sinh là không an toàn do chỉ có 26 khoá. Trong phần sau sẽ thảo luận các ph−ơng pháp thám các hệ mật m mà ta đ trình bày. 1.2 M thám các hệ m cổ điển Trong phần này ta sẽ bàn tới một vài kỹ thuật m thám. Giả thiết chung ở đây là luôn coi đối ph−ơng Oscar đ biết hệ mật đang dùng. Giả thiết này đ−ợc gọi là nguyên lý Kerekhoff. Dĩ nhiên, nếu Oscar không biết hệ mật đ−ợc dùng thì nhiệm vụ của anh ta sẽ khó khăn hơn. Tuy nhiên ta không muốn độ mật của một hệ mật lại dựa trên một giả thiết không chắc chắn là Oscar không biết hệ mật đ−ợc sử dụng. Do đó, mục tiêu
trong thiết kế một hệ mật là phải đạt đ−ợc độ mật d−ới giả thiết Kerekhoff. Tr−ớc tiên ta phân biệt các mức độ tấn công khác nhau vào các hệ mật. Sau đây là một số loại thông dụng nhất. Chỉ có bản m: Thám m chỉ có xâu bản m y. Bản rõ đ biết: Thám m có xâu bản rõ x và xâu bản m t−ơng ứng y. Bản rõ đ−ợc lựa chọn: Thám m đ nhận đ−ợc quyền truy nhập tạm thời vào cơ chế m hoá. Bởi vậy, thám m có thể chọn một xâu bản rõ x và tạo nên xâu bản m y t−ơng ứng. Bản m đ−ợc lựa chọn: Thám m có đ−ợc quyền truy nhập tạm thời vào cơ chế giải m . Bởi vậy thám m có thể chọn một bản m y và tạo nên xâu bản rõ x t−ơng ứng. Trong mỗi tr−ờng hợp trên, đối t−ợng cần phải xác định chính là khoá đ sử dụng. Rõ ràng là 4 mức tấn công trên đ đ−ợc liệt kê theo độ tăng của sức mạnh tấn công. Nhận thấy rằng, tấn công theo bản m đ−ợc lựa chọn là thích hợp với các hệ mật khoá công khai mà ta sẽ nói tới ở ch−ơng sau.
Tr−ớc tiên, ta sẽ xem xét cách tấn công yếu nhất, đó là tấn công chỉ có bản m . Giả sử rằng, xâu bản rõ là một văn bản tiếng Anh thông th−ờng không có chấm câu hoặc khoảng trống ( m thám sẽ khó khăn hơn nếu m cả dấu chấm câu và khoảng trống). Có nhiều kỹ thuật thám m sử dụng các tính chất thống kê của ngôn ngữ tiếng Anh. Nhiều tác giả đ −ớc l−ợng tần số t−ơng đối của 26 chữ cái theo các tính toán thống kê từ nhiều tiểu thuyết, tạp chí và báo. Các −ớc l−ợng trong bảng 1.1 lấy theo tài liệu của Beker và Piper. Bảng 1.1 Xác suất xuất hiện của 26 chữ cái: Kí tự Xác Kí tự Xác Kí tự Xác suất suất suất A .082 J .002 S .063 B .015 K .008 T .091 C .028 L .040 U .028 D .043 M .024 V .010 E .0127 N .067 W .023 F .022 O .075 X .001 G .020 P .019 Y .020 H .061 Q .001 Z .001 I .070 R .060
Từ bảng trên, Beker và Piper phân 26 chữ cái thành 5 nhóm nh− sau: 1. E: có xác suất khoảng 1,120 2. T, A, O, I, N, S, H, R : mỗi ký tự có xac suất khoảng 0,06 đến 0,09 3. D, L : mỗi ký tự có xác suất chừng 0,04 4. C, U, M, W, F, G, Y, P, B: mỗi ký tự có xác suất khoảng 0,015 đến 0,023 5. V, K, J, X, Q, Z mỗi ký tự có xác suất nhỏ hơn 0,01 Việc xem xét các d y gồm 2 hoặc 3 ký tự liên tiếp ( đ−ợc gọi là bộ đôi - diagrams và bộ ba - Trigrams )cũng rất hữu ích. 30 bộ đôi thông dụng nhất ( theo hứ tự giảm dần ) là: TH, HE, IN, ER, AN, RE, ED, ON, ES, ST, EN, AT, TO, NT, HA, ND, OU, EA, NG, AS, OR, TI, IS, ET, IT, AR, TE, SE, HI và OF. 12 bộ ba thông dụng nhất (theo thứ tự giảm dần ) là: THE, ING, AND, HER, ERE, ENT, THA, NTH, WAS, ETH, FOR và DTH. 1.2.1 Thám hệ m Affine Mật m Affine là một ví dụ đơn giản cho ta thấy cách thám hệ m nhờ dùng các số liệu thống kê. Giả sử Oscar đ thu trộm đ−ợc bản m sau: Bảng 1.2: Tần suất xuất hiện của 26 chữ cái của bản m Kí tự Tần Kí tự Tần Kí tự Tần Kí tự Tần suất suất suất suất A 2 H 5 O 1 U 2 B 1 I 0 P 3 V 4 C 0 J 0 Q 0 W 0 D 6 K 5 R 8 X 2 E 5 L 2 S 3 Y 1 F 4 M 2 T 0 Z 0 G 0 N 1 Ví Dụ 1.9: Bản m nhận đ−ợc từ m Affine:
FMXVEDRAPHFERBNDKRXRSREFMORUDSDKDVSHVUFEDKPKDLYEVLRHHRH Phân tích tần suất của bản m này đ−ợc cho ở bảng 1.2 Bản m chỉ có 57 ký tự. Tuy nhiên độ dài này cũng đủ phân tích thám m đối với hệ Affine. Các ký tự có tần suất cao nhất trong bản m là: R ( 8 lần xuất hiện), D (6 lần xuất hiện ), E, H, K (mỗi ký tự 5 lần ) và F, S, V ( mỗi ký tự 4 lần). Trong phỏng đoán ban đầu, ta giả thiết rằng R là ký tự m của chữ e và D là kí tự m của t, vì e và t t−ơng ứng là 2 chữ cái thông dụng nhất. Biểu thị bằng số ta có: eK(4) = 17 và eK(19) = 3. Nhớ lại rằng eK(x) = ax +b trong đó a và b là các số ch−a biết. Bởi vậy ta có hai ph−ơng trình tuyến tính hai ẩn: 4a +b = 17 19a + b = 3 Hệ này có duy nhất nghiệm a = 6 và b = 19 ( trong Z26 ). Tuy nhiên đây là một khoá không hợp lệ do UCLN(a,26) = 2 1. Bởi vậy giả thiết của ta là không đúng. Phỏng đoán tiếp theo của ta là: R là ký tự m của e và E là m của t. Thực hiện nh− trên, ta thu đ−ợc a =13 và đây cũng là một khoá không hợp lệ. Bởi vậy ta phải thử một lần nữa: ta coi rằng R là m hoá của e và H là m hoá của t. Điều này dẫn tới a = 8 và đây cũng là một khoá không hợp lệ. Tiếp tục, giả sử rằng R là m hoá của e và K là m hoá của t. Theo giả thiết này ta thu đ−ợc a = 3 và b = 5 là khóa hợp lệ. Ta sẽ tính toán hàm giải m ứng với K = (3,5) và gải m bản m để xem liệu có nhận đ−ợc xâu tiếng Anh có nghĩa hay không. Điều này sẽ khẳng định tính hợp lệ
của khoá (3,5). Sau khi thực hiện các phép toán này, ta có d K (y) = 9y - 19 và giải m bản m đ cho, ta đ−ợc: algorithmsarequitegeneraldefinitionsof arithmeticprocesses Nh− vậy khoá xác định trên là khoá đúng. 1.2.2. Thám hệ m thay thế Sau đâyta phân tích một tình huống phức tạp hơn, đó là thay thế bản m sau Ví dụ 1.10 Bản m nhận đ−ợc từ MTT là: YIFQFMZRWQFYVECFMDZPCVMRZWNMDZVEJBTXCDDUMJ NDIFEFMDZCDMQZKCEYFCJMYRNCWJCSZREXCHZUNMXZ NZUCDRJXỷYMTMEYIFZWDYVZVYFZUMRZCRWNZDZJT XZWGCHSMRNMDHNCMFQCHZJMXJZWIEJYUCFWDINZDIR Phân tích tần suất của bản m này đ−ơch cho ở bảng 1.3. Bảng 1.3. Tần suất xuất hiện của 26 ch−z cái trong bản m. Ký tự Tần Ký tự Tần Ký tự Tần Ký tự Tần suất suất suất suất A 0 H 4 O 0 U 5 B 1 I 5 P 1 V 5 C 15 J 11 Q 4 W 8 D 13 K 1 R 10 X 6 E 7 L 0 S 3 Y 10 F 11 M 16 T 2 Z 20 G 1 N 9
Do Z xuất hiện nhiều hơn nhiều so với bất kỳ một ký tự nào khác trong bản m nên có thể phỏng đoán rằng, d Z(Z) = e. các ký tự còn lại xuất hiện ít nhất 10 lần ( mỗi ký tự ) là C, D, F, J, R, M, Y. Ta hy vọng rằng, các ký tự này là m khoá của ( một tập con trong ) t, a, c, o, i, n, s, h, r, tuy nhiên sự khác biệt về tần suất không đủ cho ta có đ−ợc sự phỏng đoán thích hợp. Tới lúc này ta phải xem xét các bộ đôi, đặc biệt là các bộ đôi có dạng -Z hoặc Z- do ta đ giả sử rằng Z sẽ giải m thành e. Nhận thấy rằng các bộ đôi th−ờng gặp nhất ở dạng này là DZ và ZW ( 4 lần mỗi bộ ); NZ và ZU ( 3 lần mỗi bộ ); và RZ, HZ, XZ, FZ, ZR, ZV, ZC, ZD và ZJ ( 2 lần mỗi bộ ). Vì ZW xuất hiện 4 lần còn WZ không xuất hiện lần nào và nói chung W xuất hiện ít hơn so với nhiều ký tự khác, nên ta có thể phỏng đoán là d K(W) = d. Vì DZ xuất hiện 4 lần và ZD xuất hiện 2 lần nên ta có thể nghĩ rằng d K(D) ∈ {r,s,t}, tuy nhiên vẫn còn ch−a rõ là ký tự nào trong 3 ký tự này là ký tự đúng. Nêu tiến hành theo giả thiết d K(Z) = e và d K(W) = d thì ta phải nhìn trở lại bản m và thấy rằng cả hai bộ ba ZRW và RZW xuất hiện ở gần đầu của bản m và RW xuất hiện lại sau đó vì R th−ờng xuất hiện trong bản m và nd là một bộ đôi th−ờng gặp nên ta nên thử d K(R) = n xem là một khả năng thích hợp nhất. Tới lúc này ta có: - - - - - - end - - - - - - - - - e - - - - ned- - - e - - - - - - - - - YIFQFMZRWQFYVECFMDZPCVMRZWNMDZVEJBTXCDDUMJ - - - - - - - - e- - - - e - - - - - - - - n - - d - - - en - - - - e - - - -e NDIFEFMDZCDMQZKCEYFCJMYRNCWJCSZREXCHZUNMXZ - e - - - n - - - - - n - - - - - - ed - - - e - - - - - - ne - nd- e- e - - NZUCDRJXYYSMRTMEYIFZWDYVZVYFZUMRZCRWNZDZJJ - ed - - - - - n - - - - - - - - - - e - - - ed - - - - - - - d - - - e - - n XZWGCHSMRNMDHNCMFQCHZJMXJZWIEJYUCFWDJNZDIR
B−ớc tiếp theo là thử d K(N) = h vì NZ là một bộ đôi th−ờng gặp còn ZN không xuất hiện. Nếu điều này đúng thì đoạn sau của bản rõ ne - ndhe sẽ gợi ý rằng d K(C) = a. Kết hợp các giả định này, ta có: - - - - - -end- - - - - a- - -e -a - - nedh- -e- - - - - -a - - - - - YIFQFMZRWQFYVECFMDZPCVMRZWNMDZVEJBTXCDDUMJ h - - - - - - - a- - - e - a- - - a - - - nhad - a - -en -a - e - h- -e NDIFEFMDZCDMQZKCEYFCJMYRNCWJCSZREXCHZUNMXZ he - a - n- - - - - - n - - - - - - ed - - - e- - - e - - neandhe -e - - NZUCDRJXYYSMRTMEYIFZWDYVZVYFZUMRZCRWNZDZJJ - ed - a - - -nh - - - ha - - - a- e - - - - ed - - - - -a -d - - he- -n XZWGCHSMRNMDHNCMFQCHZJMXJZWIEJYUCFWDJNZDIR Bây giờ ta xét tới M là ký tự th−ờng gặp nhất sau Z. Đoạn bản m RNM mà ta tin là sẽ giải m thành nh- gợi ý rằng h- sẽ bắt đầu một từ, bởi vậy chắc là M sẽ biểu thị môt nguyên âm. Ta đ sử dụng a và e, bởi vậy, phỏng đoán rằng d K(M) = i hoặc o. Vì ai là bộ đôi th−ờng gặp hơn ao nên bộ đôi CM trong bản m gợi ý rằng, tr−ớc tiên nên thử d K(M) = i. Khi đó ta có: - - - - -iend- - - - - a -i - e -a -inedhi - e- - - - - -a - - -i - YIFQFMZRWQFYVECFMDZPCVMRZWNMDZVEJBTXCDDUMJ h - - - - - i - ea - i - e -a - - -a - i -nhad -a - en - -a - e -hi -e NDIFEFMDZCDMQZKCEYFCJMYRNCWJCSZREXCHZUNMXZ he - a - n - - - - -in -i - - - - ed - - -e - - - e - ineandhe - e - - NZUCDRJXYYSMRTMEYIFZWDYVZVYFZUMRZCRWNZDZJJ - ed - a - - inhi - - hai - - a - e - i- -ed- - - - - a - d - - he - -n XZWGCHSMRNMDHNCMFQCHZJMXJZWIEJYUCFWDJNZDIR Tiếp theo thử xác định xem chữ nào đ−ợc m hoá thành o. Vì o là một chữ th−ờng gặp nên giả định rằng chữ cái t−ơng ứng trong bản m là một trong các ký tự D,F,J,Y. Y có vẻ thích hợp nhất, nếu không ta sẽ có các xâu dài các nguyên âm, chủ yếu là aoi ( từ CFM hoặc CJM ). Bởi vậy giả thiết rằng d K(Y) = o.
Ba ký tự th−ờng gặp nhất còn lại trong bản m là D,F,J, ta phán đoán sẽ giải m thành r,s,t theo thứ tự nào đó. Hai lần xuất hiện của bộ ba NMD gợi ý rằng dK(D) = s ứng với bộ ba his trong bản rõ ( điều này phù hợp với giả định tr−ớc kia là d K(D) ∈{r,s,t} ). Đoạn HNCMF có thể là bản m của chair, điều này sẽ cho d K(F) = r (và dK(H) = c ) và bởi vậy (bằng cách loại trừ ) sẽ có d K(J) = t. Ta có: o- r - riend - ro - - arise - a - inedhise - - t - - - ass - it YIFQFMZRWQFYVECFMDZPCVMRZNMDZVEJBTXCDDUMJ hs - r - riseasi - e - a - orationhadta - - en - -ace - hi - e NDIFEFMDZCDMQZKCEYFCJMYRNCWJCSZREZCHZUNMXZ he - asnt - oo - in - i - o - redso - e - ore - ineandhesett NZUCDRJXYYSMRTMEYIFZWDYVZVYFZUMRZCRWNZDZJJ - ed - ac - inhischair - aceti - ted - - to - ardsthes - n XZWGCHSMRNMDHNCMFQCHZJMXJZWIEJYUCFWDJNZDIR Bây giờ việc xác định bản rõ và khoá cho ví dụ 1.10 không còn gì khó khăn nữa. Bản rõ hoàn chỉnh nh− sau: Our friend from Pais examined his empty glass with surprise, as if evaporation had taen place while he wasn't looking. I poured some more wine and he settled back in his chair, face tilted up towards the sun. 1.2.3. Thám hệ m Vigenère Trong phần này chúng ta sẽ mô tả một số ph−ơng pháp thám hệ m Vigenère. B−ớc đầu tiên là phải xác định độ dài từ khoá mà ta ký hiệu là m. ở đây dùng hai kỹ thuật. Kỹ thuật thứ nhất là phép thử Kasiski và kỹ thuật thứ hai sử dụng chỉ số trùng hợp. Phép thử Kasiski lần đầu tiên đ−ợc Kasiski Friendrich mô tả vào năm 1863. Kỹ thuật này đ−ợc xây dựng trên nhận xét là: hai đoạn giống nhau của bản
rõ sẽ đ−ợc m hoá thành cùng một bản m khi chúng xuất hiện trong bản rõ cách nhau x vị trí, trong đó x ≡ o md m. Ng−ợc lại, nếu ta thấy hai đoạn giống nhau của bản m ( mỗi đoạn có độ dài ít nhất là 3 ) thì đó là một dấu hiệu tốt để nói rằng chúng t−ơng ứng với các đoạn bản rõ giống nhau. Phép thử Kasiski nh− sau. Ta tòm trong bản m các cặp gồm các đoạn nh− nhau có độ dài tối thiểu là 3 và ghi lại khoảng cách giữa các vị trí bắt đầu của hai đoạn. Nếu thu đ−ợc một vài giá trị d 1, d 2 ,. . . thì có thể hy vọng rằng m sẽ chia hết cho −ớc chung lớn nhất của các d i. Việc xác minh tiếp cho giá trị của m có thể nhận đ−ợc bằng chỉ số trùng hợp. Khái niệm này đ đ−ợc Wolfe Friedman đ−a ra vào 1920 nh− sau: Định nghĩa 1.7. Giả sử x = x 1x2 . . . x n là một xâu ký tự. Chỉ số trùng hợp của x (ký hiệu là I c(x)) đ−ợc định nghĩa là xác suất để hai phần tử ngẫu nhiên của x là đồng nhất. Nếu ký hiệu các tần suất của A,B,C,. . . ,Z trong x t−ơng ứng là n f0,f 1 ,. . . f 25 , có thể chọn hai phần  tử của x theo 2 cách. Với mỗi i,    f i  0 ≤ i ≤ 25, có   cách chọn hai phần tử là i. Bởi vậy ta 2 có công thức:  25 ∑ fi (fi − 1) I (x) = i=0 c n(n − 1) n n!   = k  k (! n − k)!
Ghi chú: Hệ số nhị thức xác định số cách chọn một tập con k đối t−ợng từ một tập n đối t−ợng. Bây giờ, giả sử x là một xâu văn bản tiếng Anh. Ta kí hiệu các xác suất xuất hiện của các kí tự A,B,. . .,Z trong bảng 1.1 là p 0, p 25 . Khi đó: 25 2 I c (x) ≈ ∑ p i = 0,065 i=0 2 do xác suất để hai phần tử ngẫu nhiên đều là A là p0 , 2 xác suất để cả hai phần tử này đều bằng B bằng p 1 . . . Tình hình t−ơng tự cũng xảy ra nếu x là một bản m nhận đ−ợc theo một hệ m thay thế đơn bất kì. Trong tr−ờng hợp 25 2 này, từng xác suất riêng rẽ sẽ bị hoán∑ p vịi nh−ng tổng i=0 sẽ không thay đổi. Bây giờ giả sử có một bản m y = y 1y2. . .y n đ−ợc cấu trúc theo mật m Vigenère. Ta xác định các xâu con m của y(y 1,y 2,. . .,y m) bằng cách viết ra bản m thành một hình chữ nhật có kích th−ớc m ì(n/m). Các hàng của ma trận này là các xâu con y i, 1 ≤ i ≤ m. Nếu m thực sự là độ dài khoá thì mỗi I c(y i) phải xấp xỉ bằng 0,065. Ng−ợc lại, nếu m không phải là độ dài khoá thì các xâu con y i sẽ có vẻ ngẫu nhiên hơn vì chúng nhận đ−ợc bằng cách m dịch vòng với các khoá khác nhau. Xét thấy rằng, một xâu hoàn toàn ngẫu nhiên sẽ có: 2 Ic ≈ 26(1/26) = 1/26 = 0,038
Hai giá trị 0,065 và 0,038 đủ cách xa nhau để có thể xác định đ−ợc độ dài từ khoá đúng ( hoặc xác nhận giả thuyết đ đ−ợc làm theo phép thử Kasiski). Hai kỹ thuật này sẽ đ−ợc minh hoạ qua ví dụ d−ới đây: Ví dụ 1.11. Bản m nhận đ−ợc từ mật m Vigenère. CHEEVOAHMAERATBTAXXWTNXBEEOPHBSBQMQEQERBW RVXUOAKXAOSXXWEAHBWGJMMQMNKGRFVGXWTRZXWIAK LXFPSKAUTEMNDCMGTSXMXBTUIADNGMGPSRELXNJELX VRVPRTULHDNQWTWDTYGBPHXTFEALJHASVBFXNGLLCHR ZBWELEKMSJIKNBHWRJGNMGJSGLXFEYPHAGNRBIEQJT AMRVLCRRREMNDGLXRRIMGNSNRWCHRQHAEYEVTAQEBBI PEEWEVKAKOEWADREMXMTBHHCHRTKDNVRZCHRCLQOHP WQAIIWXNRMGWOIIFKEE Tr−ớc tiên, ta h y thử bằng phép thử Kasiski xâu bản m CHR xuất hiện ở bốn vị trí trong bản m , bắt đầu ở các vị trí 1, 166,236 và 286. Khoảng cách từ lầ xuất hiện đầu tiên tới 3 lần xuất hiện còn lại t−ơng ứng là 165,235 và 285. UCLN của 3 số nguyên này là 5, bởi vậy giá trị này rất có thể là độ dài từ khoá. Ta h y xét xem liệu việc tính các chỉ số trùng hợp có cho kết luận t−ơng tự không. Với m = 1 chỉ số trùng hợp là 0,045. Với m = 2, có 2 chỉ số là 0,046 và 0,041. Với m = 3 ta có 0,043; 0,050; 0,047. Với m = 4 các chỉ số là 0,042; 0,039; 0,046; 0,040. Với m = 5 ta có các giá trị 0,063; 0,068; 0,069; 0,061 và 0,072. Điều này càng chứng tỏ rằng độ dại từ khoá là 5. Với giả thiết trên, làm nh− thế nào để xác định từ khoá? Ta sẽ sử dụng khái niệm chỉ số trùng hợp t−ơng hỗ của hai xâu sau: Định nghĩa 1.8.
Giả sử x = x 1x2. . .x n và y = y 1y2. . .y n' là các xâu có n và n' kí tự anphabet t−ơng ứng. Chỉ số trùng hợp t−ơng hỗ của x và y ( kí hiệu là MI c(x,y)) đ−ợc xác định là xác suất để một phần tử ngẫu nhiên của x giống với một phần tử ngẫu nhiên của y. Nếu ta kí hiệu các tần suất của A,B,. . .,Z trong x và y t−ơng ứng là f 0,f 1,. . .,f 25 thì MI c(x,y) sẽ đ−ợc tính bằng: 25 ∑ i i 'ff MI (x, y) = i = 0 c n.n' Với các giá trị m đ xác định, các xâu con y i thu đ−ợc bằng m dịch vòng bản rõ. Giả sử K = (k 1,k 2,. . .,k m) là từ khoá. Ta sẽ xem xét có thể đánh giá MI c(y i,y j) nh− thế nào. Xét một kí tự ngẫu nhiên trong y i và một kí tự ngẫu nhiên trong y j . Xác suất để cả hai kí tự là A bằng p-ki p-kj , xác suất để cả hai là B bằng p 1-ki p 1-kj ,. . .( Cần chú ý rằng tất cả các chỉ số d−ới đều đ−ợc rút gọn theo modulo 26). Bởi vậy có thể −ớc l−ợng rằng: 25 25 ∑ ∑ MI c (y i y, i ) ≈ p h−ki p h−kj = p h p h+ki−kj h=0 h=0 Ta thấy rằng, giá trị −ớc l−ợng này chỉ phụ thuộc vào kiếu hiệu k i-kj mod 26 ( đ−ợc gọi là độ dịch t−ơng đối 25 25 ∑ ph ph+1 =∑ ph ph−1 h=0 h=0 của y i và y j). Cũng vậy, ta thấy rằng: Bởi vậy độ dịch t−ơng đối l sẽ dẫn đến cùng một −ớc l−ợng MI c nh− độ dịch t−ơng đối 26-l .
Ta lập bảng các −ớc l−ợng cho độ dịch t−ơng đối trong phạm vi từ 0 đến 13.( Xem bảng 1.4). Bảng 1.4. Các chỉ số trùng hợp t−ơng hỗ tính đ−ợc. Độ dịch Giá trị tính đ−ợc t−ơng đối của MI c 0 0.065 1 0,039 2 0,032 3 0,034 4 0,044 5 0,033 6 0,036 7 0,039 8 0,034 9 0,034 10 0,038 11 0,045 12 0,039 13 0,043 Xét thấy rằng, nếu độ dịch t−ơng đối khác 0 thì các −ớc l−ợng này thay đổi trong khoảng từ 0.031 đến 0,045; ng−ợc lại nếu độ dịch t−ơng đối bằng 0 thì −ớc l−ợng bằng 0,065. Có thể dùng nhận xét này để tạo nên một phỏng đoán thích hợp cho l = k i-kj (độ dịch t−ơng đối của y i và y j) nh− sau: Giả sử cố định y i và xét việc m 25 ∑ f i 'f i −g MI ( y,x g ) = i =0 c n.n'
0 1 hoá y j bảng e 0,e 1,e 2. . . Ta kí hiệu các kết quả bằng y j ,y j ,. . g . Dễ dàng dùng các chỉ số MI c(y i,yj ), 0 ≤ g ≤ 25 theo công thức sau: Khi g = l thì MI c phải gần với giá trị 0,065 vì độ dịch t−ơng đối của y i và y j bằng 0. Tuy nhiên, với các giá trị g ≠ l thì MI c sẽ thay đổi giữa 0,031 và 0,045. Bằng kỹ thuật này, có thể thu đ−ợc các độ dịch t−ơng đối của hai xâu con y i bất kỳ. Vấn đề còn lại chỉ là 26 từ khoá có thể và điều này dễ dàng tìm đ−ợc bằng ph−ơng pháp tìm kiếm vét cạn. Trở lại ví dụ 1.11 để minh hoạ. Ví dụ 1.11( tiếp ): ở trên đ giả định rằng, độ dài từ khoá là 5. Bây giờ ta sẽ thử tính các độ dịch t−ơng đối. Nhờ máy tính, g dễ dàng tính 260 giá trị MI c(y i,y j ), trong đó 1 ≤ i ≤ j ≤ 5; 0 ≤ g ≤ 25. Các giá trị này đ−ợc cho trên bảng 1.5. Với mỗi g cặp ( i,j), ta tìm các giá trị của MI c(y i,y j ) nào gần với 0,065. Nếu có một giá trị duy nhất nh− vậy( Đối với mỗi cặp (i,j) cho tr−ớc), thì có thể phán đoán đó chính là giá trị độ dịch t−ơng đối. Trong bảng 1.5 có 6 giá trị nh− vậy đ−ợc đóng khung. Chúng chứng tỏ khá rõ ràng là độ dịch t−ơng đối của y 1 và y 2 bằng 9; độ dịch t−ơng đối của y 2 và y 3 bằng 13; độ dịch t−ơng đối của y 2 và y 5 bằng 7; độ dịch t−ơng đối của y 3 và y 5 bằng 20; của y 4 và y 5 bằng 11. Từ đây có các ph−ơng trình theo 5 ẩn số K 1, K 2, K 3, K 4, K 5 nh− sau: K1 - K 2 = 9 K1 - K 2 = 16 K2 - K 3 = 13
K2 - K 5 = 17 K3 - K 5 = 20 K4 - K 5 = 11 Điều này cho phép biểu thị các K i theo K 1 ; K2 = K 1 + 17 K3 = K 1 + 4 K4 = K 1 + 21 K5 = K 1 + 10 Nh− vậy khoá có khả năng là ( K 1, K 1+17, K 1+4, K 1+21, K1+10) với giá trị K 1 nào đó ∈ Z 26 . Từ đây ta hy vọng rằng, từ khoá là một dịch vòng nào đó của AREVK. Bây giờ , không tốn nhiều công sức lắm cũng có thể xác định đ−ợc từ khoá là JANET. Giải m bản m theo khoá này, ta thu đ−ợc bản rõ sau: The almond tree was in tentative blossom. The days were longer often ending with magnificient evenings of corrugated pink skies. The hunting seasun was over, with hounds and guns put away for six months. The vineyards were busy again as the well-organized farmers treated their vinesand the more lackadaisical neighbors hurried to do the pruning they have done in November. Bảng 1.5. Các chỉ số trùng hợp t−ơng hỗ quan sát đ−ợc. g i j Giá trị của MI c(y j,y j ) 1 2 0,028 0,027 0,028 0,034 0,039 0,037 0,026 0,025 0,052 0,068 0,044 0,026 0,037 0,043 0,037 0,043 0,037 0,028 0,041 0,041 0,041 0,034 0,037 0,051 0,045 0,042 0,036 1 3 0,039 0,033 0,040 0,034 0,028 0,053 0,048 0,033 0,029 0,056 0,050 0,045 0,039 0,040 0,036 0,037 0,032 0,027 0,037 0,047 0,032 0,027 0,039 0,037 0,039 0,035 1 4 0,034 0,043 0,025 0,027 0,038 0,049 0,040 0,032 0,029 0,034 0,039 0,044 0,044 0,034 0,039 0,045 0,044 0,037 0,055 0,047 0,032 0,027 0,039 0,037 0,039 0,035 1 5 0,043 0,033 0,028 0,046 0,043 0,044 0,039 0,031 0,026
0,030 0,036 0,040 0,041 0,024 0,019 0,048 0,070 0,044 0,028 0,038 0,044 0,043 0,047 0,033 0,026 2 3 0,046 0,048 0,041 0,032 0,036 0,035 0,036 0,020 0,024 0,039 0,034 0,029 0,040 0,067 0,061 0,033 0,037 0,045 0,033 0,033 0,027 0,033 0,045 0,052 0,042 0,030 2 4 0,046 0,034 0,043 0,044 0,034 0,031 0,040 0,045 0,040 0,048 0,044 0,033 0,024 0,028 0,042 0,039 0,026 0,034 0,050 0,035 0,032 0,040 0,056 0,043 0,028 0,028 2 5 0,033 0,033 0,036 0,046 0,026 0,018 0,043 0,080 0,050 0,029 0,031 0,045 0,039 0,037 0,027 0,026 0,031 0,039 0,040 0,037 0,041 0,046 0,045 0,043 0,035 0,030 3 4 0,038 0,036 0,040 0,033 0,036 0,060 0,035 0,041 0,029 0,058 0,035 0,035 0,034 0,053 0,030 0,032 0,035 0,036 0,036 0,028 0,043 0,032 0,051 0,032 0,034 0,030 3 5 0,035 0,038 0,034 0,036 0,030 0,043 0,043 0,050 0,025 0,041 0,051 0,050 0,035 0,032 0,033 0,033 0,052 0,031 0,027 0,030 0,072 0,035 0,034 0,032 0,043 0,027 4 5 0,052 0,038 0,033 0,038 0,041 0,043 0,037 0,048 0,028 0,028 0,036 0,061 0,033 0,033 0,032 0,052 0,034 0,027 0,039 0,043 0,033 0,027 0,030 0,039 0,048 0,035 1.2.4.Tấn công với bản rõ đ biết trên hệ mật Hill. Hệ m Hill là một hệ mật khó pha hơn nếu tấn công chỉ với bản m . Tuy nhiên hệ mật này dễ bị phá nếu tấn công bằng bản rõ đ biết. Tr−ớc tiên, giả sử rằng, thám m đ biết đ−ợc giá trị m đang sử dụng. Giả sử thám m có ít nhất m cặp véc tơ khác nhau xj = (x 1,j , x 2,j , , . . ., x m,j ) và y j = (y 1,j , y 2,j , ,y m,j ) (1 ≤ j ≤ m) sao cho y j = e K(x j), 1 ≤ j ≤ m. Nếu xác định hai ma trận: X = (x i,j ) Y = (y i,j ) cấp m ìm thì ta có ph−ơng trình ma trận Y = XK, trong đó ma trận K cấp m ìm là khoá ch−a biết. Với điều kiện ma trận Y là khả nghịch. Oscar có thể tính K = X -1Y và nhờ vậy phá đ−ợc hệ mật. ( Nếu Y không khả nghịch thì cấn phải thử các tập khác gồm m cặp rõ - m ). Ví dụ 1.12. Giả sử bản rõ Friday đ−ợc m hoá bằng m Hill với m = 2, bản m nhận đ−ợc là PQCFKU. Ta có e K(5,17) = (15,16), e K(8,3) = (2,5) và e K(0,24) = (10,20). Từ hai cặp rõ - m đầu tiên, ta nhận đ−ợc ph−ơng trình ma trận:
15 16  5 17    =  K 2 5  8 3  Dùng định lý 1.3, dễ dàng tính đ−ợc: 1 5 17  − 9 1    =   8 3  2 15  Bởi vậy: 9 1 15 16  7 19  K =    =   2 15 2 5  8 3  Ta có thể dùng cặp rõ - m thứ 3 để kiểm tra kết quả này. Vấn đề ở đây là thám m phải làm gì nếu không biết m?. Giả sử rằng m không quá lớn, khi đó thám má có thể thử với m = 2,3,. . . cho tới khi tìm đ−ợc khoá. Nếu một giá trị giả định của m không đúng thì mà trận mìm tìm đ−ợc theo thuật toán đ mô tả ở trên sẽ không t−ơng thích với các cặp rõ - m khác. Ph−ơng pháp này, có thể xác định giá trị m nếu ch−a biết. 1.2.5. Thám m hệ m dòng xây dựng trên LFSR. Ta nhớ lại rằng, bản m là tổng theo modulo 2 của bản rõ và dòng khoá, tức y i = x i + z i mod 2. Dòng khóa đ−ợc tạo từ (z 1,z 2,. . .,z m) theo quạn hệ đệ quy tuyến tính: m−1 2 zm+1 = ∑c j zi +1 mod j =0 trong đó c 0,. . .,c m ∈ Z 2 (và c 0 = 1) Vì tất cả các phép toán này là tyuến tính nên có thể hy vọng rằng, hệ mật này có thể bị phá theo ph−ơng pháp tấn công với bản rõ đ biết nh− tr−ờng hợp mật m Hill. Giả sử rằng, Oscar có một xâu bản rõ
x1x2. . .x n và xâu bản m t−ơng ứng y 1y2. . .y n . Sau đó anh ta tính các bít dòng khoá z i = x i+y i mod 2, 1 ≤ i ≤ n. Ta cũng giả thiết rằng Oscar cũng đ biết giá trị của m. Khi đó Oscar chỉ cần tính c 0, . . ., c m-1 để có thể tái tạo lại toàn bộ dòng khoá. Nói cách khác, Oscar cần phải có khả năng để xác định các giá trị của m ẩn số. Với i ≥ 1 bất kì ta có : m−1 2 zm+1 = ∑c j zi + j mod j =0 là một ph−ơng trình tuyến tính n ẩn. Nếu n ≥ 2n thì có m ph−ơng trình tuyến tính m ẩn có thể giải đ−ợc. Hệ m ph−ơng trình tuyến tính có thể viết d−ới dạng ma trận nh− sau: z1 z2 . . . zm  z z . . . z   2 3 m+1  ()()z 1 z, 2 , , z2 = c0 c, 1, , c 1 m+ m+ m m− . . . . . .    z z . . . z  m m+1 2m 1-  Nếu ma trận hệ số có nghịch đảo ( theo modulo 2 )thì ta nhận đ−ợc nghiệm: −1 z1 z2 . . . zm  z z . . . z   2 3 m+1  ()()c0 c, 1, , c 1 = z 1 z, 2 , , z2 m− m+ m+ m . . . . . .    z z . . . z  m m+1 2m 1-  Trên thực tế, ma trận sẽ có nghịch đảo nếu bậc của phép đệ quy đ−ợc dùng để tạo dòng khoá là m.(xem bài tập). Minh hoạ điều này qua một ví dụ. Ví dụ 1.13. Giả sử Oscar thu đ−ợc xâu bản m 101101011110010 t−ơng ứng với xâu bản rõ
011001111111001 Khi đó anh ta có thể tính đ−ợc các bít của dòng khoá: 110100100001010 Ta cũng giả sử rằng, Oscar biết dòng khoá đ−ợc tạo từ một thanh ghi dịch phản hồi (LFSR) có 5 tầng. Khi đó, 1 1 0 1 0 1 0 1 0 0    ()()0 1,, 0,0,0 = c0 c, 1 c, 2 c, 3 c, 4 0 1 0 0 1   1 0 0 1 0  0 0 1 0 0 anh ta sẽ giải ph−ơng trình mà trận sau ( nhận đ−ợc từ 10 bít đầu tiên của dòng khoá): Có thể kiểm tra đ−ợc rằng: 1 1 1 0 1 0 − 0 1 0 0 1 1 0 1 0 0  1 0 0 1 0      0 1 0 0 1 = 0 0 0 0 1     1 0 0 1 0  0 1 0 1 1 0 0 1 0 0 1 0 1 1 0 Từ đó ta có: 0 1 0 0 1 1 0 0 1 0    ()()c0 c, 1 c, 2 c, 3 c, 4 = 0 1,, 0,0,0 0 0 0 0 1   0 1 0 1 1 1 0 1 1 0 = (1, 0, 0, 1, 0) Nh− vậy phép đệ quy đ−ợc dùng để tạo dòng khoá là:
zi+5 = z i + z i+3 mod 2 1.3. Các chú giải và tài liệu dẫn Nhiều tài liệu về mật m cổ điển đ có trong các giáo trình, chẳng hạn nh− giáo trình của Beker và Piper [BP82] và Denning [DE82]. Xác suất đánh giá cho 26 kí tự đ−ợc lấy của Beker và Piper. Cũng vậy, việc phân tích m Vigenère đ−ợc sửa đổi theo mô tả của Beker và Piper. Rosen [Ro93] là một tài liệu tham khảo tốt về lý thuyết số. Cơ sở của Đại số tuyến tính sơ cấp có thể tìm thấy trong sách của Anton [AN91]. Cuốn " Những ng−ời m thám " của Kahn [KA67] là một cấu chuyện hấp dẫn và phong phú về mật m cho tới năm 1967, trong đó Kahn khẳng định rằng mật m Vigenère thực sự không phải là phát minh của Vigenère. Mật m Hill lần đầu tiên đ−ợc mô tả trong [HI29]. Các thông tin về mật m dòng có thể tìm đ−ợc trong sách của Rueppel [RU86]. Bài tập 1.1. D−ới đây là 4 bản m thu đ−ợc từ m thay thế. Một bản thu đ−ợc từ m Vigenère, một từ mật m Affine và một bản ch−a xác định. Nhiệm vụ ở đây là xác định bản rõ trong mỗi tr−ờng hợp. H y mô tả các b−ớc cần thực hiện để giải m mỗi bản m ( bao gồm tất cả các phân tích thống kê và các tính toán cần thực hiện).
Hai bản rõ đầu lấy từ cuốn " The diary of samuenl marchbanks " của Robertson Davies, Clack Iriwin,1947; bản rõ thứ t− lấy từ " Lake wobegon days" của Garrison Keillor, Viking Penguin, 1985. a) M thay thế: EMGLXUDCGDNCUSWYXFPHNSFCYKDPUMLWGYICOXYFIPJCK QPKUGKMGOLICGINCGACKFNIFACYKZSCKXECJCKFHYFXCG 0IDPKZCNKSHICGIWYGKKGKGOLDSILKGOIUFIGLEDFPWZU GFZCCNDGYYFFUSZCNXEOJNCGYEOWEUPXEZGACGNFGLKNF ACIGOYCKXCJUCIUZCFZCCNDGYYSFEUEKUZCSOCSZCCNC IACZEJNCFFZEJZEGMXCYHCJUMGKUSI Chỉ dẫn: F sẽ giải m thành W. b) Hệ m Vigenère KCCPKBGUFDPHQTYAVINRRTMVGRKDNBVFDETDGLLTXRGUD DKBTMBPVGEGLTGCKQRACQCWDNAWCRXIZAKSTLEWRPTYC QKYVXCHKFTPONCQQRHJVAJUWETMCMSPKQDYHJVDAHCTRL SVSKCGCZQQDZXGSFRLFWCWSJTBHAFSIASPRJAHKJRJUMP FFSQNRWXCVYCGAONWDDKACKAWBBIKFTIOVKCGGHJVLNHI CWHJVLNHIQIBTKHJVNPIST c) Hệ m Affine. KQEREJEBCPPCJCRKIEACUZBKRVPKRBCIBQCARBJCVFCUP KRIOFKPACUZQEPBKRXPEIIEABDKPBCPFCDCAFIEABDKP BCPFEQPKAZBKRHAIBKAPCCIBURCCDKDCCJCIDFUIXPAFF ERBICZDFKABICBBENEFCUPJCVKABPCYDCCDPKBCOCPERK IVKSCPICBRKIJPKABI d) Hệ m ch−a xác định đ−ợc. BNVSNSIHQCEELSSKKYERISJKXUMBGYKAMQLJTYAVFBKVT DVBPVVRJYYLAOKYMPQSCGDLFLLPROYGEFEBUUALRWXM MASAZLGLEDFJBZAVVPXWYCGJXASCBYEHOSNMULKCEAHTQ OKMFLEBKFXLRRFDTZXCIWBJSICBGAWDVYDHAVFJXZIBKC GJIWEAHTTOEWTUHKRQVVRGZBXYIREMMASCSPBNLHJGBLR FFJELHWEYLWISTFVVYFJCMHYURUFSFMGESIGRLWALSWM NUHSIMYYITCCQPZSICEHBCCMZFEGVJYOCDEMMPGHVAAMU ELCMOEHVLTIPSUYILVGFLMVWDVYDBTHERAYISYSGKVSUU HYHGGCKTMBLRX
1.2. a) Có bao nhiêu ma trận khả nghịch cấp 2 ì2 trên Z 26 . b) Giả sử p là số nguyên tố. H y chứng tỏ số các ma 2 2 trận khả nghịch cấp 2 ì2 trên Z p là (p -1)(p -p). Chỉ dẫn: Vì p là số nguyên tố nên Z p là một tr−ờng. H y sử dụng khẳng định sau: Một ma trận là khả nghịch trên một tr−ờng là khả nghịch khi và chỉ khi các hàng của nó là các véc tơ độc lập tuyến tính ( tức không tồn tại một tổ hợp tuyến tính các hàng khác 0 mà tổng của chúng là một véc tơ toàn số 0). c) Với p là số nguyên tố và m là một số nguyên ≥ 2. H y tìm công thức tính số các ma trận khả nghịch cấp mìm trên Z p. 1.3. Đôi khi chọn một khoá mà phép m và giải m là đồng nhất rất hữu ích. Trong tr−ờng hợp mất m Hill, ta phải tìm các ma trận K sao cho K = K -1 ( ma trận này đ−ợc gọi là ma trận đối hợp). Trên thực tế, Hill đ đề nghị sử dụng các ma trận này làm khoá trong các hệ mật của mình. H y xác định số các ma trận đối hợp trên Z 26 trong tr−ờng hợp m = 2. Chỉ dẫn: H y dùng công thức trong định lý 1.3 và để ý rằng detA = ± với một ma trận đối hợp trên Z 26 . 1.4. Giả sử ta đ biết rằng bản rõ " conversation " sẽ tạo nên bản m " HIARRTNUYTUS " ( đ−ợc m theo hệ m Hill nh−ng ch−a xác định đ−ợc m). H y xác định ma trận m hoá. 1.5. Hệ m Affine - Hill là hệ m Hill đ−ợc sửa đổi nh− m sau: Giả sử m là một số nguyên d−ơng và P = C = (Z 26 ) . Trong hệ mật này, khoá K gồm các cặp (L,b), trong đó L m là mọt ma trận khả nghịch cấp m ìm trên Z 26 và b ∈(Z 26 ) .
Với x = ( x 1,. . .,x m)∈P và K = (L,b) ∈ K, ta tính y = e K(x) = (y 1,. . .,y m) theo công thức y = xL + b. Bởi vậy, nếu L = ( li,j ) và b = (b 1,. . .,b m) thì: . . l 1,1 l 1,2 . l 1,m    . . l 2,1 l 2,2 . l 2,m  y , , y = x , , x . . . . .  +( b , , b ) ()()1 m 1 m   1 m  . . . . .   . .  l m,1 l m,2 . l m,m  Giả sử Oscar đ biết bản rõ là " adisplayedequation " và bản m t−ơng ứng là " DSRMSIOPLXLJBZULLM ". Oscar cũng biết m =3. Hình tính khoá và chỉ ra tất cả các tính toán cần thiết. 1.6. Sau đây là cách thám m hệ m Hill sử dụng ph−ơng pháp tấn công chỉ với bản m . Giả sử ta biết m = 2. Chia các bản m thành các khối có độ dài 2 kí tự ( các bộ đôi). Mỗi bộ đôi này là bản m của một bộ đôi của bản rõ nhờ dùng một ma trận m hoá ch−a biết. H y nhặt ra các bộ đôi th−ờng gặp nhất trong bản m và coi rằng đó là m của một bộ đôi th−ờng gặp trong danh sách ở bảng 1.1 ( ví dụ TH và ST). Với mỗi giả định, h y thực hiện phép tấn công với bản rõ đ biết cho tới khi tìm đ−ợc ma trận giải m đúng. Sau đây là một ví dụ về bản m để bạn giải m theo ph−ơng pháp đ nêu: LMQETXYEAGTXCTUIEWNCTXLZEWUAISPZYVAPEWLMGQWYA XFTCJMSQCADAGTXLMDXNXSNPJQSYVAPRIQSMHNOCVAXFV. 1.7. Ta sẽ mô tả một tr−ờng hợp đặc biệt của m hoán vị. Giả sử m, n là các số nguyên d−ơng. H y viết bản rõ theo thành từng hàng thành một hình chữ nhật m ìn. Sau đó tạo ra bản m bằng cách lấy các cột của hình
chữ nhật này. Ví dụ, nếu m = 4, n = 3 thì ta sẽ m hoá bản rõ " cryptography " bằng cách xây dựng hình chữ nhật : cryp togr aphy Bản m sẽ là: 'CTAROPYGHPRY' a) H y mô tả cách Bob giải m một bản m ( với m, n đ biết) b) H y giải m bản m sau: ( nhận đ−ợc theo ph−ơng pháp đ nêu): MYAMRARUYIQTENCTORAHROYWDSOYEOUARRGDERNOGW 1.8. Có 8 phép đệ quy tuyến tính bậc 4 khác nhau trên Z 2 với c 0 = 1. H y xác định những phép đệ quy nào tạo đ−ợc dòng khoá có chu kỳ 15 ( với véc tơ khởi tạo khác 0). 1.9. Mục đích của bài tập này để chứng minh khẳng định ở phần 1.2.5 là : ma trận hệ số cấp m ìm có nghịch đảo. Điều này t−ơng đ−ơng với khẳng định rằng, các hàng ma trận này là các véc tơ độc lập tuyến tính trên Z2. Giả sử rằng phép đệ quy có dạng: m−1 2 zm+i = ∑c j zi + j mod j =0 ( z 1,. . .,z m) là véc tơ khởi tạo. Với i ≥ 1 ta xác định: vi = (z i,. . .,z i+m-1) Chú ý rằng, ma trận hệ số có các véc tơ v 1,. . .,v m là các hàng của nó. Bởi vậy, nhiệm vụ của ta là chứng tỏ rằng m véc tơ này là độc lập tuyến tính. H y chứng minh hai khẳng định sau: a) Với i ≥ 1 bất kì: m−1 2 v m+i = ∑c j v i + j mod j =0 h−2 h−2 α 2 2 v h z=h∑−1+ic=j v∑j +1 modjz j +i mod j =0 j =0
b)Chọn h là số nguyên nhỏ nhất sao cho tồn tại một tổ hợp tuyến tính không tầm th−ờng của các véc tơ v 1,. . .,v h có tổng là véc tơ (0, . . . , 0) theo modulo 2. Khi đó: ( Các αj không đồng nhất bằng 0). Để ý rằng, h ≤ m+1 vì m+1 là véc tơ bất kỳ trong không gian tuyến tính m chiều đều phụ thuộc tuyến tính . c) H y chứng tỏ rằng dòng khoá phải thảo m n phép đệ quy: với bất kì i ≥ 1. d) Ta nhận thấy rằng, nếu h ≤ m thì dòng khoá thảo m n phép đệ quy tuyến tính có bậc nhỏ hơn m. Điều này mâu thuẫn. Bởi vậy h = m + 1 và ma trận phải là khả nghịch. 1.10. H y giải m bản m sau ( thu đ−ợc từ m khoá tự sinh ) bằng ph−ơng pháp tìm khoá vét cạn. MALVVMAFBHBUQPTSOXALTGVWWRG 1.11. Ta sẽ mô tả một hệ m dòng là biến thể của m Vigenère nh− sau. Với một từ khoá độ dài m cho tr−ớc ( k1,. . .,k m ), ta tạo dòng khoá theo quy tắc z i=k i (1 ≤ i ≤ m), zi+m = z i+1 mod 26 ( i ≥ m+1). Nói cách khác, mỗi lần dùng từ khoá ta sẽ thay mỗi kí tự bằng kí tự đứng sau nó theo modulo 26. Ví dụ, nếu SUMMER là từ khoá thì ta dùng SUMMER để m hoá 6 kí tự đầu.,sau đó dùng TVNNFS để m hoá 6 kí tự tiếp theo và cú tiếp tục nh− vậy. H y mô tả cách có thể dùng khái niệm chỉ số trùng hợp nh− thế nào để tr−ớc hết là xác định độ dài từ khoá và sau đó là tìm từ khoá. H y kiểm tra ph−ơng pháp của bạn bằng cách bằng cách phân tích bản m sau:
IYMYSILONRFNCQXQJEDSHBUIBCJUZBOLFQYSCHATPEQGQ JEJNGNXZWHHGƯFSUKULJQACZKKJOAAHGKEMTAFGMKVRDO PXNEHEKZNKFSKIFRQVHHOVXINPHMRTJPYWQGJWPUUKFP OAWPMRKKQZWLQDYAZDRMLPBJKJOBWIWPSEPVVQMBCRYVC RUZAAOUMBCHDAGDIEMSZFZHALIGKEMJJFPCIWKRMLMPIN AYOFIREAOLDTHITDVRMSE Bản rõ đ−ợc lấy từ "The codebreakers" của D.Kahn, 1967.