Cơ sở mật mã học - Chương 1: Mật mã cổ điển

 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 yi = xi + zi mod 2. Dòng khóa được tạo từ (z1,z2,. . .,zm) theo quạn hệ đệ quy tuyến tính:
trong đó c0,. . .,cm Î Z2 (và c0 = 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. . .xn và xâu bản mã tương ứng y1y2. . .yn . Sau đó anh ta tính các bít dòng khoá zi = xi+yi 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 c0, . . ., cm-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ó :
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:
Nếu ma trận hệ số có nghịch đảo ( theo modulo 2 )thì ta nhận được nghiệm:
	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 đó, 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:
Từ đó ta có:
 = (1, 0, 0, 1, 0)
Như vậy phép đệ quy được dùng để tạo dòng khoá là:
zi+5 = zi + zi+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 Z26 .
Giả sử p là số nguyên tố. Hãy chứng tỏ số các ma trận khả nghịch cấp 2´2 trên Zp là (p2-1)(p2-p).
Chỉ dẫn: Vì p là số nguyên tố nên Zp 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 Zp.
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 Z26 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 Z26.
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ư sau: Giả sử m là một số nguyên dương và P = C = (Z26)m. Trong hệ mật này, khoá K gồm các cặp (L,b), trong đó L là mọt ma trận khả nghịch cấp m´m trên Z26 và bÎ(Z26)m. Với x = ( x1,. . .,xm)ÎP và K = (L,b) Î K, ta tính y = eK(x) = (y1,. . .,ym) theo công thức y = xL + b. Bởi vậy, nếu L = (li,j) và b = (b1,. . .,bm) thì:
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'
Hãy mô tả cách Bob giải mã một bản mã ( với m, n đã biết)
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 Z2 với c0 = 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:
( z1,. . .,zm) là véc tơ khởi tạo. Với i ³ 1 ta xác định:
vi = (zi,. . .,zi+m-1)
Chú ý rằng, ma trận hệ số có các véc tơ v1,. . .,vm 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:
Với i ³ 1 bất kì:
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ơ v1,. . .,vh có tổng là véc tơ (0, . . . , 0) theo modulo 2. Khi đó:
( Các aj 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 .
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,. . .,km ), ta tạo dòng khoá theo quy tắc zi=ki (1 £ i £ m), zi+m = zi+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.