Giáo án an toàn bảo mật 5
- 11 trang
- file .pdf
và xét việc mã hoá yj bảng e0,e1,e2. . . Ta kí hiệu các kết quả bằng yj0,yj1,. . . Dễ
dàng dùng các chỉ số MIc(yi,yjg), 0 ≤ g ≤ 25 theo công thức sau:
Khi g = l thì MIc phải gần với giá trị 0,065 vì độ dịch tương đối của yi và yj
bằng 0. Tuy nhiên, với các giá trị g ≠ l thì MIc 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 yi
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ụ trên để minh hoạ.
Ở 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, dễ dàng tính 260 giá trị MIc(yi,yjg), trong đó 1 ≤ i
≤ j ≤ 5; 0 ≤ g ≤ 25. Các giá trị này được cho trên bảng. Với mỗi cặp ( i,j), ta tìm
các giá trị của MIc(yi,yjg) 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 dưới 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 y1 và y2 bằng 9; độ dịch tương đối của y2 và
y3 bằng 13; độ dịch tương đối của y2 và y5 bằng 7; độ dịch tương đối của y3 và
y5 bằng 20; của y4 và y5 bằng 11. Từ đây có các phương trình theo 5 ẩn số K1,
K2, K3, K4, K5 như sau:
K1 - K2 = 9
K1 - K2 = 16
K2 - K3 = 13
K2 - K5 = 17
K3 - K5 = 20
K4 - K5 = 11
Điều này cho phép biểu thị các Ki theo K1 ;
K2 = K1 + 17
http://www.ebook.edu.vn 45
K3 = K1 + 4
K4 = K1 + 21
K5 = K1 + 10
Như vậy khoá có khả năng là ( K1, K1+17, K1+4, K1+21, K1+10) với giá
trị K1 nào đó ∈ Z26. 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.
. Các chỉ số trùng hợp tương hỗ quan sát được.
Giá trị của MIc(yj,yjg)
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
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
http://www.ebook.edu.vn 46
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
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
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
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
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
http://www.ebook.edu.vn 47
0,026 0,031 0,039
0,040 0,037 0,041 0,046 0,045 0,043
0,035 0,030
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
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
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
2.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 = (x1,j, x2,j, , . . ., xm,j) và yj = (y1,j, y2,j,...,ym,j) (1 ≤ j ≤ m)
http://www.ebook.edu.vn 48
sao cho yj = eK(xj), 1 ≤ j ≤ m. Nếu xác định hai ma trận: X = (xi,j) Y = (yi,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-
1
Y 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ụ
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ó eK(5,17) = (15,16), eK(8,3) = (2,5) và eK(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ý 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.
2.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 quan hệ đệ quy
tuyến tính:
http://www.ebook.edu.vn 49
m −1
z m +1 = ∑ c j z i +1 mod 2
j =0
trong đó c0,. . .,cm ∈ Z2 (và c0 = 1)
Vì tất cả các phép toán này là tuyế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ó :
m −1
z m +1 = ∑ c j z i + j mod 2
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:
⎡ z 1 z2 . . . z m ⎤
⎢ ⎥
z2 z3 . . . zm+1 ⎥
(z m+1 , z m+2 ,...,z 2m ) = (c 0 , c1 ,...,c m−1 )⎢
⎢
⎥
. . . . . .
⎢ ⎥
⎣zm zm+1 . . . z2m-1 ⎦
Nếu ma trận hệ số có nghịch đảo ( theo modulo 2 )thì ta nhận được nghiệm:
−1
⎡ z 1 z2 . . . z m ⎤
⎢ ⎥
z2 z3 . . . zm+1 ⎥
(c 0 , c1 ,...,c m−1 ) = (z m+1 , z m+2 ,...,z 2m )⎢
⎢
⎥
. . . . . .
⎢ ⎥
⎣zm zm+1 . . . z2m-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ụ :
Giả sử Oscar thu được xâu bản mã
101101011110010
http://www.ebook.edu.vn 50
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á):
⎡1 1 0 1 0⎤
⎢1 0 1 0 0 ⎥⎥
⎢
(0,1,0,0,0) = (c 0 , c1 , c 2 , c 3 , c 4 )⎢0 1 0 0 1⎥
⎢ ⎥
⎢1 0 0 1 0⎥
⎢⎣0 0 1 0 0⎥⎦
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 ⎥⎥
⎢
(c 0 , c1 , 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 = zi + zi+3 mod 2
http://www.ebook.edu.vn 51
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].
http://www.ebook.edu.vn 52
dàng dùng các chỉ số MIc(yi,yjg), 0 ≤ g ≤ 25 theo công thức sau:
Khi g = l thì MIc phải gần với giá trị 0,065 vì độ dịch tương đối của yi và yj
bằng 0. Tuy nhiên, với các giá trị g ≠ l thì MIc 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 yi
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ụ trên để minh hoạ.
Ở 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, dễ dàng tính 260 giá trị MIc(yi,yjg), trong đó 1 ≤ i
≤ j ≤ 5; 0 ≤ g ≤ 25. Các giá trị này được cho trên bảng. Với mỗi cặp ( i,j), ta tìm
các giá trị của MIc(yi,yjg) 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 dưới 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 y1 và y2 bằng 9; độ dịch tương đối của y2 và
y3 bằng 13; độ dịch tương đối của y2 và y5 bằng 7; độ dịch tương đối của y3 và
y5 bằng 20; của y4 và y5 bằng 11. Từ đây có các phương trình theo 5 ẩn số K1,
K2, K3, K4, K5 như sau:
K1 - K2 = 9
K1 - K2 = 16
K2 - K3 = 13
K2 - K5 = 17
K3 - K5 = 20
K4 - K5 = 11
Điều này cho phép biểu thị các Ki theo K1 ;
K2 = K1 + 17
http://www.ebook.edu.vn 45
K3 = K1 + 4
K4 = K1 + 21
K5 = K1 + 10
Như vậy khoá có khả năng là ( K1, K1+17, K1+4, K1+21, K1+10) với giá
trị K1 nào đó ∈ Z26. 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.
. Các chỉ số trùng hợp tương hỗ quan sát được.
Giá trị của MIc(yj,yjg)
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
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
http://www.ebook.edu.vn 46
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
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
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
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
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
http://www.ebook.edu.vn 47
0,026 0,031 0,039
0,040 0,037 0,041 0,046 0,045 0,043
0,035 0,030
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
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
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
2.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 = (x1,j, x2,j, , . . ., xm,j) và yj = (y1,j, y2,j,...,ym,j) (1 ≤ j ≤ m)
http://www.ebook.edu.vn 48
sao cho yj = eK(xj), 1 ≤ j ≤ m. Nếu xác định hai ma trận: X = (xi,j) Y = (yi,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-
1
Y 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ụ
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ó eK(5,17) = (15,16), eK(8,3) = (2,5) và eK(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ý 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.
2.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 quan hệ đệ quy
tuyến tính:
http://www.ebook.edu.vn 49
m −1
z m +1 = ∑ c j z i +1 mod 2
j =0
trong đó c0,. . .,cm ∈ Z2 (và c0 = 1)
Vì tất cả các phép toán này là tuyế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ó :
m −1
z m +1 = ∑ c j z i + j mod 2
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:
⎡ z 1 z2 . . . z m ⎤
⎢ ⎥
z2 z3 . . . zm+1 ⎥
(z m+1 , z m+2 ,...,z 2m ) = (c 0 , c1 ,...,c m−1 )⎢
⎢
⎥
. . . . . .
⎢ ⎥
⎣zm zm+1 . . . z2m-1 ⎦
Nếu ma trận hệ số có nghịch đảo ( theo modulo 2 )thì ta nhận được nghiệm:
−1
⎡ z 1 z2 . . . z m ⎤
⎢ ⎥
z2 z3 . . . zm+1 ⎥
(c 0 , c1 ,...,c m−1 ) = (z m+1 , z m+2 ,...,z 2m )⎢
⎢
⎥
. . . . . .
⎢ ⎥
⎣zm zm+1 . . . z2m-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ụ :
Giả sử Oscar thu được xâu bản mã
101101011110010
http://www.ebook.edu.vn 50
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á):
⎡1 1 0 1 0⎤
⎢1 0 1 0 0 ⎥⎥
⎢
(0,1,0,0,0) = (c 0 , c1 , c 2 , c 3 , c 4 )⎢0 1 0 0 1⎥
⎢ ⎥
⎢1 0 0 1 0⎥
⎢⎣0 0 1 0 0⎥⎦
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 ⎥⎥
⎢
(c 0 , c1 , 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 = zi + zi+3 mod 2
http://www.ebook.edu.vn 51
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].
http://www.ebook.edu.vn 52