Mã khóa đối xứng được dùng để chỉ các hệ mã mà trong đó, khi biết
khóa lập mã ta có thể tìm được khóa giải mã một cách dễ dàng (vì vậy
người ta thường coi chúng là một), đồng thời việc giải mã cũng đòi hỏi
thời gian như việc lập mã. Các hệ mã thuộc loại này có thời gian lập mã
và giải mã tương đối nhanh vì thế các hệ mã đối xứng thường được sử
dụng để mã hóa những dữ liệu lớn. Nhưng các hệ mã đối xứng yêu cầu
phải giữ bí mật hoàn toàn về khóa lập mã.
30 trang |
Chia sẻ: longpd | Lượt xem: 5867 | Lượt tải: 2
Bạn đang xem trước 20 trang tài liệu Giáo trình lý thuyết mật mã và an toàn thông tin phần 2, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
Chương
HỆ MẬT MÃ KHÓA ĐỐI XỨNG
(SYMMETRIC-KEY CRYPTOGRAPHY)
Mã khóa đối xứng được dùng để chỉ các hệ mã mà trong đó, khi biết
khóa lập mã ta có thể tìm được khóa giải mã một cách dễ dàng (vì vậy
người ta thường coi chúng là một), đồng thời việc giải mã cũng đòi hỏi
thời gian như việc lập mã. Các hệ mã thuộc loại này có thời gian lập mã
và giải mã tương đối nhanh vì thế các hệ mã đối xứng thường được sử
dụng để mã hóa những dữ liệu lớn. Nhưng các hệ mã đối xứng yêu cầu
phải giữ bí mật hoàn toàn về khóa lập mã.
Nội dung chính
I. Các hệ mật mã cổ điển (Classical ciphers).
II. Thám mã đối với hệ mật mã cổ điển.
III. Mã dòng (Stream Cipher).
IV. Mã khối (Block cipher)
Trường Đại học Dân lập Hải Phòng
Hiện nay tin học đã được áp dụng vào hầu hết các lĩnh vực
trong cuộc sống và có một ảnh hưởng rất lớn đối với sự tồn tại và phát
triển của các ngành khoa học khác. Trong mọi hệ thống tin học, thông
tin luôn là thành phần cơ bản nhất và quan trọng nhất. Chúng ta không
ai mà không gặp phải những trường hợp khi máy tính bị mất hết
những thông tin quan trọng do nhiều nguyên nhân khác nhau như bị
virus, bị hư hỏng thiết bị, do không biết sử dụng, bị đánh cắp hay xoá
thông tin… Nói chung vấn đề an toàn và bảo mật thông tin rất đa dạng
và phụ thuộc vào nhiều yếu tố chủ quan và khách quan khác nhau
như: con người, môi trường, công nghệ… Hiện nay có rất nhiều công
cụ và phần mềm hỗ trợ an toàn cho hệ thống máy tính. Tuy nhiên vấn
đề đánh giá và chọn lựa một hệ thống an toàn rất phức tạp và chỉ
mang tính tương đối bởi vì một hệ thống được đánh giá là rất an toàn
hôm nay có thể không còn an toàn nữa vào ngày mai. Nếu chúng ta
thường xuyên theo dõi các thông tin bảo mật trên Internet, chúng ta có
thể thấy thông tin về những lỗ hổng bảo mật của các hệ điều hành, các
phần mềm bảo mật, các dịch vụ… Vì vậy an toàn và bảo mật thông tin
là một trong những thành phần quan trọng nhất cần được quan tâm
trong việc duy trì và phát triển của hệ thống.
Lê Thụy 2
Chương 2 - Lý thuyết Mật mã và An toàn thông tin
Mật mã và vấn đề an toàn thông tin ?
Mật mã (Cipher) đã xuất hiện cách đây khoảng 4000 năm tại Ai
cập. Khi mà các cuộc chiến tranh xẩy ra giữa các đế chế. Thông tin
của bên A dưới dạng chữ cái (letter), chữ số (number) hay loại nào đó
trước khi được gửi đi sẽ được mã hoá. Bên B nhận được thông tin mã
hoá này thực hiện việc giải mã để hiểu được nội dung. Một người lấy
được bản mã cũng khó có thể hiểu được nội dung của thông tin vì chỉ
có A và B mới có cách giải mã. Thời kì này các thông tin được bảo
mật bằng các phương pháp khác nhau, hay còn gọi là các hệ mật mã
cổ điển. Các hệ mật mã sớm nhất được biết đến như mật mã Ceazar -
mã dich chuyển (Shift Cipher), mã thế (Substitution Cipher)… Các hệ
mật mã này được sử dụng trong một thời gian dài. Cho đến khi toán
học phát triển. Các hệ mã mới được xây dựng trên các lý thuyết về
toán học hiện đại. Một thế hệ mật mã được xây dựng dựa trên độ phức
tạp tính toán, các hệ mật mã này được gọi là các hệ mã hiện đại. Các
ứng dụng của các hệ mật mã ngày càng được áp dụng trong nhiều lĩnh
vực xã hội. Giúp giải quết hàng loạt các vấn đề về an toàn thông tin
trên các kênh thông tin không bảo mật.
Mật mã cung cấp một giải pháp nhằm mục đích thực hiện biến
một thông tin cụ thể dễ hiểu thành một dạng khác (khó hiểu) có quan
hệ chặt chẽ với thông tin gốc. Giờ đây ta gọi thông tin chưa mã hoá
(tường minh) là “bản rõ”, và thông tin sau khi được mã hoá là “bản
mã”. Vậy mật mã là gì ? Tại sao nó lại bảo vệ đươc bí mật thông tin ?
Cơ sở của nó là gì ?
Định nghĩa : Mật mã học là sự nghiên cứu các phương pháp toán học
liên quan đến một số khía cạnh của thông tin như sự an toàn, sự toàn
vẹn dữ liệu, sự xác nhận tồn tại và sự xác nhận tính nguyên bản của
thông tin.
Lê Thụy 3
Trường Đại học Dân lập Hải Phòng
I. Các hệ mật mã cổ điển (Classical ciphers).
1. Mở đầu:
- Mong muốn được trao đổi thông tin một cách bí mật là một
trong những đòi hỏi của con người xuất hiện từ rất sớm trong lịch sử.
Vì thế lịch sử của việc trao đổi thông tin mật rất phong phú và bao
gồm những phát minh độc đáo mang đầy tính giai thoại. Ngành học
nghiên cứu cách thức che dấu thông tin đối với những đối tượng
không mong muốn được gọi là mật mã học (cryptography)
- Mật mã (cipher) được dùng để bảo vệ bí mật của thông tin
khi thông tin được truyền trên các kênh thông tin không bảo mật như
thư tín, điện thoại, mạng truyền thông máy tính…
- A muốn gửi cho B một văn bản bằng tiếng Việt (gọi là
“bản rõ” - plaintext), muốn được bảo mật thì A phải lập mật mã cho
“bản rõ” đó (gọi là “bản mã” - ciphertext) và gửi “bản mã” cho B. A
và B có một khoá mật mã chung, vừa để A lập “bản mã”, vừa để B
giải “bản mã” thành “bản rõ”. Một người khác không có khoá đó, thì
dù có lấy được “bản mã” từ kênh truyền tin cũng không thể biến thành
“bản rõ” để hiểu được nội dung thông báo mà A gửi cho B.
Bộ mã hoá Bộ giải mã
Phân tích mật mã
Kênh công cộng
Kênh an toàn
Bản tin
gốc (M)
Bản tin
gốc (M)
Các bản tin
mật mã
M’
A☺ B☺
C /
- Các hệ mật mã cổ điển thực hiện việc bảo mật đó đều dùng
một khoá chung cho việc lập mã và giải mã, các bản rõ và bản mã
thường dùng cơ sở là bảng chữ trong ngôn ngữ tự nhiên. Trong phần
này, để tiện trình bầy ta dùng bảng chữ cái tiếng Anh làm ví dụ, và
dùng các số liệu thống kê của tiếng Anh để minh hoạ.
Lê Thụy 4
Chương 2 - Lý thuyết Mật mã và An toàn thông tin
- Dưới đây là một số định nghĩa toán học về hệ thống mật
mã:
Định nghĩa 1.1: Một hệ mật mã là một bộ năm (P, C, K, E, D)
thoả mãn các điều kiện sau đây:
+ P là một tập hữu hạn các bản rõ.
+ C là một tập hưu hạn các bản mã.
+ K là một tập hưu hạn các khoá.
+ Với mỗi k ∈ K, có một hàm lập mã ek ∈ E, ek: P → C, và một
hàm giải mã dk ∈ D, dk: C → P sao cho dk(ek(x)) = x với mọi x ∈ P.
Trong thực tế, P và C thường là bảng chữ cái (hoặc tập các
dãy chữ cái có độ dài cố định)
Nếu bản rõ là (một xâu chữ cái):
x = x1x2x3…xn (xi ∈ P ), và khoá là k ∈ K
thì bản mã sẽ là:
y = y1y2y3…yn (yi ∈ C )
Trong đó yi = ek(xi) (1 ≤ i ≤ n). Nhận được bản mã y, biết khoá
k, sẽ tìm được bản rõ x, vì xi = dk(yi)
Sau đây thay cho bảng chữ cái A, B, C,…,X, Y, Z ta sẽ dùng các
con số 0, 1, 2,…, 24, 25 và dùng các phép toán số học theo modulo 26
để diễn tả các phép biến đổi trên bảng chữ cái.
A B C D E F G H I J K L M N
0 1 2 3 4 5 6 7 8 9 10 11 12 13
O P Q R S T U V W X Y Z
14 15 16 17 18 19 20 21 22 23 24 25
2. Mã dịch chuyển (Shift Cipher).
Kí hiệu ] m là tập các số nguyên từ 0 đến (m-1), ký hiệu đó
cũng dùng cho vành các số nguyên từ 0 đến (m-1) với các phép cộng
Lê Thụy 5
Trường Đại học Dân lập Hải Phòng
và nhân với modulo m. Như vậy, bảng chữ cái tiếng Anh có thể xem là
một vành ] 26 với sự tương ứng kể trên.
Định nghĩa Mã dịch chuyển: (P, C, K, E, D)
P = C = K = ] 26 với k ∈ K, định nghĩa
ek(x) = (x + k) mod 26
dk(y) = (y – k) mod 26
(x, y ∈ ] 26)
Ví dụ: Dùng khoá k = 9 để mã hoá dòng thư:
“hentoithubay”
dòng thư đó tương ứng với dòng số:
h e n t o i t h u b a y
7 4 13 19 14 8 19 7 20 1 0 24
qua phép mã hoá e9 sẽ được:
16 13 22 2 23 17 2 16 3 10 9 7
q n w c x r c q d k j h
bản mã sẽ là:
“qnwcxrcqdkjh”
Nhận được bản mã đó, dùng d9 để nhận được bản rõ.
Cách đây 2000 năm mã dịch chuyển đã được Julius Ceasar sử
dụng, với khoá k=3 mã địch chuyển được gọi là mã Ceasar.
Tập khoá phụ thuộc vào ] m với m là số khoá có thể.
Trong tiếng Anh tập khoá chỉ có 26 khoá có thể, việc thám mã
có thể được thực hiện bằng cách duyệt tuần tự 26 khoá đó, vì vậy độ
an toàn của mã dịch chuyển rất thấp.
Lê Thụy 6
Chương 2 - Lý thuyết Mật mã và An toàn thông tin
3. Mã thay thế (Substitution Cipher).
Khoá của mã thay thế là một hoán vị của bảng chữ cái. Gọi
S(E) là tập hợp tất cả các phép hoán vị các phần tử của E.
Định nghĩa Mã thay thế: (P, C, K, E, D)
P = C = ] 26, K = S (] 26)
Với mỗi л ∈ K, tức là một hoán vị trên ] 26, ta xác định
eл(x) = л(x)
dл(y) = л-1(y)
với x, y ∈] 26, л-1 là nghịch đảo của л
Ví dụ: л được cho bởi (ở đây ta viết chữ cái thay cho các con số
thuộc ] 26):
a b c d e f g h i j k l m n
x n y a h p o g z q w b t s
o p q r s t u v w x y z
f l r c v m u e k j d i
bản rõ:
“hentoithubay”
sẽ được mã hoá thành bản mã (với khoá л):
“ghsmfzmgunxd”
Dễ xác định được л-1, và do đó từ bản mã ta tìm được bản rõ.
Mã thay thế có tập hợp khoá khá lớn - bằng số các hoán vị trên
bảng chữ cái, tức số các hoán vị trên ] 26, hay là 26!, lớn hơn 4.1026.
Việc duyệt toàn bộ các hoán vị để thám mã là rất khó, ngay cả đối với
máy tính. Tuy nhiên, ta sẽ thấy có những phương pháp thám mã khác
dễ dàng thực hiện, và do đó mã thay thế cũng không thể được xem là
an toàn.
Lê Thụy 7
Trường Đại học Dân lập Hải Phòng
4. Mã Apphin (Apphin Cipher).
Phép lập mã được cho bởi một hàm Apphin dạng:
e(x) = ax + b mod 26
trong đó a, b ∈ ] 26 (chú ý: nếu a = 1 ta có mã dịch chuyển)
Để có được phép giải mã tương ứng, tức để cho phương trình
ax + b = y mod 26
có nghiệm x duy nhất (với bất kỳ y ∈ ] 26 cho trước), hay nói
cách khác hàm Apphin phải là đơn ánh. Theo một định lý số học, điều
kiện cần và đủ là a nguyên tố với 26, tức là (a, 26) = 1. Ở đây (a, 26)
ký hiệu cho ước số chung lớn nhất của a và 26.
Khi (a, 26) = 1 thì có số a-1 ∈] 26 sao cho a.a-1 = a-1.a = 1 mod
26, và do đó, Nếu:
y = ax + b mod 26
Ù ax = y – b mod 26
Ù a-1.ax = a-1.(y – b) mod 26
Ù (a-1.a)x = a-1.(y – b) mod 26
Ù x = a-1.(y – b) mod 26
⇒ d(x) = a-1.(y – b) mod 26
Định nghĩa Mã Apphin: (P, C, K, E, D)
P = C = ] 26, K = { (a, b) ∈ ] 26 x ] 26 : (a, 26) = 1 }
với mỗi k = (a, b) ∈ K ta định nghĩa:
ek(x) = ax + b mod 26
dk(y) = a-1(y – b) mod 26
trong đó x, y ∈ ] 26
Lê Thụy 8
Chương 2 - Lý thuyết Mật mã và An toàn thông tin
Có những thuật toán để thử tính chất (a, m) = 1, và tính a-1 mod
m khi (a, m) = 1, ta sẽ trình bầy trong phần sau. Tuy nhiên, với m =
26, ta dễ thử rằng các số a sao cho (a, 26) = 1 là:
a 1 3 5 7 9 11 15 17 19 21 23 25
a-1 1 9 21 15 3 19 7 23 11 5 17 25
Ví dụ: Lấy k = (5, 6).
Bản rõ:
“hentoithubay”
h e n t o i t h u b a y
x 7 4 13 19 14 8 19 7 20 1 0 24
y = 5x + 6 mod 26
y 15 0 19 23 24 20 23 15 2 11 6 22
p a t x y u x p c l g w
Bản mã:
“patxyuxpclgw”
Thuật toán giải mã trong trường hợp này có dạng:
dk(y) = 21(y − 6) mod 26
Với mã Apphin, số các khoá có thể có bằng (số các số ≤ 26 và
nguyên tố với 26) × 26, tức là 12 × 26 = 312. Việc thử tất cả các khoá
để thám mã trong trường hợp này tuy khá mất thì giờ nếu tính bằng
Lê Thụy 9
Trường Đại học Dân lập Hải Phòng
tay, nhưng không khó khăn gì nếu dùng máy tính. Do vậy, mã Apphin
cũng không phải là mã an toàn.
5. Mã Vigenēre (Vigenēre Cipher).
Mã lấy tên của Blaise de Vigenēre, sống vào thế kỷ 16. Khác
với các mã trước, mã Vigenēre không thực hiện trên từng ký tự một,
mà được thực hiện trên từng bộ m ký tự (m là số nguyên dương).
Định nghĩa Mã Vigenēre: (P, C, K, E, D)
Cho m là số nguyên dương.
P = C = K = ] 26m
với mỗi khoá k = (k1, k2,…,km) ∈ K có:
ek(x1, x2,…, xm) = (x1 + k1, x2 + k2,…, xm + km)
dk(y1, y2,…, ym) = (y1 – k1, y2 – k2,…, ym – km)
các phép cộng phép trừ điều lấy theo modulo 26
Ví dụ: Giả sử m = 6 và khoá k là từ CIPHER - tức k=(2, 8, 15,
7, 4, 17).
Bản rõ:
“hentoithubay”
h e n t o i t h u b a y
x 7 4 13 19 14 8 19 7 20 1 0 24
k 2 8 15 7 4 17 2 8 15 7 4 17
y 9 12 2 0 18 25 21 15 9 8 4 15
j m c a s z v p j i e p
Bản mã:
Lê Thụy 10
Chương 2 - Lý thuyết Mật mã và An toàn thông tin
“jmcaszvpjiep”
Từ bản mã đó, dùng phép giải mã dk tương ứng, ta lại thu được
bản rõ.
Chú ý: Mã Vigenēre với m = 1 sẽ trở thành mã Dịch chuyển.
Tập hợp các khoá trong mã Vigenēre mới m ≥ 1 có tất cả là 26m
khoá có thể có. Với m = 6, số khoá đó là 308.915.776, duyệt toàn bộ
chừng ấy khoá để thám mã bằng tính tay thì khó, nhưng với máy tính
thì vẫn là điều dễ dàng.
6. Mã Hill (Hill Cipher).
Mã này được đề xuất bởi Lester S.Hill năm 1929. Mã cũng
được thực hiện trên từng bộ m ký tự, mỗi ký tự trong bản mã là một tổ
hợp tuyến tính (trên vành ] 26) của m ký tự trong bản rõ. Như vậy,
khoá sẽ được cho bởi một ma trận cấp m, tức là một phần tử của
] 26m m× . Để phép biến đổi tuyến tính xác định bởi ma trận k ∈ ] 26m m×
có phép nghịch đảo, ma trận k cũng phải có phần tử nghịch đảo k-1 ∈
] 26m m× . Điều kiện cần và đủ để ma trận k có ma trận nghịch đảo là
định thức của nó - ký hiệu det(k),- nguyên tố với m.
Định nghĩa Mã Hill: (P, C, K, E, D)
Cho m là số nguyên dương.
P = C = ] 26m
K = { k ∈ ] 26m m× : (det(k), 26) = 1 }
với mỗi k ∈ K định nghĩa:
ek(x1, x2,…, xm) = (x1, x2,…, xm).k
dk(y1, y2,…, ym) = (y1, y2,…,ym).k-1
Lê Thụy 11
Trường Đại học Dân lập Hải Phòng
Ví dụ: Lấy m = 2, và 11 8k
3 7
⎛ ⎞= ⎜ ⎟⎝ ⎠
Với bộ 2 ký tự (x1, x2), ta có mã là (y1, y2) = (x1, x2). k được tính
bởi
y1 = 11.x1 + 3.x2
y2 = 8.x1 + 7.x2
Giả sử ta có bản rõ: “tudo”, tách thành từng bộ 2 ký tự, và viết
dưới dạng số ta được 19 20 | 03 14 , lập bản mã theo quy tắc trên, ta
được bản mã dưới dạng số là: 09 06 | 23 18, và dưới dạng chữ là
“fgxs”.
Chú ý:
Để đơn giản cho việc tính toán, thông thường chọn ma trận
vuông 2×2. Khi đó có thể tính ma trận nghịch đảo theo cách sau :
Giả sử: ta có ma trận nghịch đảo
a b
k
c d
⎛= ⎜⎝ ⎠
⎞⎟
1
1 a bk
c d
−
− ⎛ ⎞= ⎜ ⎟⎝ ⎠
được tính :
1
d b
a b ad bc ad bc
c d c a
ad bc ad bc
−
−⎛ ⎞⎜ ⎟⎛ ⎞ − −= ⎜ ⎟⎜ ⎟ −⎝ ⎠ ⎜ ⎟⎜ ⎟− −⎝ ⎠
Một chú ý là để phép chia luôn thực hiện được trên tập ] 26 thì
nhất thiết định thức của k : det(k) = (ad – bc) phải có phần tử nghịch
đảo trên ] 26, nghĩa là (ad – bc) phải là một trong các giá trị : 1, 3, 5,
7, 9, 11, 15, 17, 19, 21, 23, hoặc 25. Đây cũng là điều kiện để ma trận
k tồn tại ma trận nghịch đảo.
Khi đó: k-1.k = I là ma trận đơn vị (đường chéo chính bằng 1)
1
d b
a b a b a b 1 0ad bc ad bc
c d c d c a c d 0 1
ad bc ad bc
−
−⎛ ⎞⎜ ⎟⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎛− −= =⎜ ⎟⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜−⎝ ⎠ ⎝ ⎠ ⎝ ⎠ ⎝⎜ ⎟⎜ ⎟− −⎝ ⎠
⎞⎟⎠
Ví dụ:
Lê Thụy 12
Chương 2 - Lý thuyết Mật mã và An toàn thông tin
Định thức của là 11
11 8
3 7
⎛⎜⎝ ⎠
⎞⎟ ×7 – 8×3 = 1 ≡ 1 mod 26
Khi đó :
111 8
3 7
−⎛ ⎞⎜ ⎟⎝ ⎠ =
7 8
3 11
−⎛ ⎞⎜ ⎟−⎝ ⎠ ≡ mod 26
7 18
23 11
⎛ ⎞⎜⎝ ⎠⎟
Trên đây là một ví dụ đặc biệt vì ma trận có định thức bằng 1,
chúng ta sẽ xem xét một ví dụ tìm nghịch đảo của ma trận 2×2 khác.
Ví dụ:
Định thức của là 9
9 4
5 7
⎛ ⎞⎜ ⎟⎝ ⎠ ×7 – 4×5 = 43 ≡ 17 mod 26
Khi đó : =
19 4
5 7
−⎛ ⎞⎜ ⎟⎝ ⎠
7 4
17 17
5 9
17 17
−⎛ ⎞⎜ ⎟⎜ −⎜ ⎟⎜ ⎟⎝ ⎠
⎟ mod 26
Theo một tính chất toán học ta có: phép chia cho 17 mod 26 sẽ
tương đương với phép nhân với phần tử nghịch đảo của 17 mod 26.
Với thuật toán trình bầy trong chương một ta có thể tính được phần tử
nghịch đảo của 17 trong ] 26 là 23. Do đó :
7 4
17 17
5 9
17 17
−⎛ ⎞⎜ ⎟⎜ −⎜ ⎟⎜ ⎟⎝ ⎠
⎟ mod 26 ≡ 7 23 4 23
5 23 9 23
× − ×⎛ ⎞⎜ ⎟− × ×⎝ ⎠ mod 26
≡ mod 26 ≡ mod 26
161 92
115 207
−⎛ ⎞⎜ ⎟−⎝ ⎠
5 12
15 25
⎛⎜⎝ ⎠
⎞⎟
Kết quả :
19 4
5 7
−⎛ ⎞⎜ ⎟⎝ ⎠ =
5 12
15 25
⎛ ⎞⎜ ⎟⎝ ⎠
Lê Thụy 13
Trường Đại học Dân lập Hải Phòng
Ta không có công thức để đánh giá số khoá k có thể có với m
cho trước. Trong mục sau ta sẽ xét một phương pháp thám mã đối với
mã Hill.
7. Mã hoán vị (Permutation Cipher).
Khác với các mã trước, mã hoán vị không thay đổi các ký tự
trong bản rõ mà chỉ thay đổi vị trí các ký tự trong từng bộ m các ký tự
của bản rõ. Ta ký hiệu Sm là tập hợp tất cả các phép hoán vị của {1,
2,…, m}.
Định nghĩa Mã hoán vị: (P, C, K, E, D)
Cho m là số nguyên dương.
P = C = ] , K = S26m m
với mỗi k = π ∈ Sm , ta có
ek(x1, x2,…, xm) = (xπ(1), xπ(2),…, xπ(m))
dk(y1, y2,…, ym) = π π π-1 -1 -1( 1 ) ( 2 ) ( m )( y , y ,..., y )
trong đó π-1 là hoán vị nghịch đảo của π
Ví dụ: Giả sử m = 6, và khoá k được cho bởi phép hoán vị π
1 2 3 4 5 6
3 5 1 6 4 2
Khi đó phép hoán vị nghịch đảo π-1 là:
1 2 3 4 5 6
3 6 1 5 2 4
Bản rõ:
“hentoithubay”
Lê Thụy 14
Chương 2 - Lý thuyết Mật mã và An toàn thông tin
h e n t o i t h u b a y
vt 1 2 3 4 5 6 1 2 3 4 5 6
π 1→3 2→5 3→1 4→6 5→4 6→2 1→3 2→5 3→1 4→6 5→4 6→2
vt 3 5 1 6 4 2 3 5 1 6 4 2
n o h i t e u a t y b h
Bản mã:
“nohiteuatybh”
Dùng hoán vị nghịch đảo, từ bản mật mã ta lại thu được bản rõ.
Chú ý:
Mã hoán vị là một trường hợp riêng của mã Hill. Thực vậy, cho
phép hoán vị π của {1, 2,…, m}, ta có thể xác định ma trận Kπ=(kij),
với
( )
ij
1 i
k
0
jπ=⎧= ⎨⎩
nÕu
nÕu ng−îc l¹i
thì dễ thấy rằng mã Hill với khoá Kπ trùng với mã hoán vị với khoá π.
Với m cho trước, số các khoá có thể có của mã hoán vị là m!
Dễ nhận thấy với m = 26 ta có số khóa 26! (mã Thay thế)
Lê Thụy 15
Trường Đại học Dân lập Hải Phòng
II. Thám mã đối với hệ mật mã cổ điển.
Như chúng ta đã biết, hệ mã cổ điển là những hệ mã được sử
dụng từ rất lâu, lúc mà khả năng tính toán của các hệ thống chưa phát
triển vì thế các quy tắc được áp dụng trong các hệ mã là rất đơn giản.
Chủ yếu dựa trên hai phương pháp dịch chuyển và thay thế. Độ an
toàn của các hệ mã này không chỉ phụ thuộc vào khoá mà còn phụ
thuộc cả vào sơ đồ mã hoá được sử dụng (dó đó cần giữ bí mật cả sơ
đồ mã hoá và khoá lập mã).
Với sáu loại mã cổ điển chúng ta đã xét, thấy rằng miền giá trị
khoá có thể của các hệ mã đó bị giới hạn, khi đó với khả năng tính
toán của các máy tính hiện nay, miền giá trị khoá có thể được vét cạn
trong một khoảng thời gian rất ngắn. Nhưng phương pháp này không
tối ưu trong nhiều trương hợp vì phải duyệt tất cả các bộ khoá trong
miền khoá.
Một phương pháp được dùng nhiều trong kỹ thuật thám mã đó
là phương pháp sắc xuất thống kê (xác định tần suất xuất hiện của các
ký tự trong bản mã). Trong hầu hết các ngôn ngữ tự nhiên, các văn
bản được trình bầy dưới dạng các chữ cái với tần suất xuất hiện khác
nhau. Ví dụ: trong tiếng Anh tần suất xuất hiện của chữ E là cao nhất
với sắc xuất xuất hiện là 0,127.
Bảng xắc suất xuất hiện của các ký tự trong tiếng Anh
0
0.02
0.04
0.06
0.08
0.1
0.12
0.14
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Xắ
c
su
ất
Từ bảng trên có thể phân 26 chữ cái thành 5 nhóm như sau:
Lê Thụy 16
Chương 2 - Lý thuyết Mật mã và An toàn thông tin
E: có xác suất khoảng 0,127
T, A, O, I, N, S, H, R: có xác suất khoảng 0,06 đến 0,09
D, L: mỗi ký tự có xác suất chừng 0,04
C, U, M, W, F, G, Y, P, B: có xác suất khoảng 0,015 đến 0,023
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.
Có 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.
Có 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.
Tuy nhiên việc thám mã nói chung đều thực hiện qua 4 bước:
- Xác định ngôn ngữ được sử dụng. (bản rõ – bản mã).
- Xác định hệ thống nói chung được sử dụng.
- Xây dựng lại khoá của mật mã sử dụng trong hệ thống.
- Xây dựng lại bản gốc. (bản rõ)
Các hình thức tấn công vào hệ mã:
- Chỉ biết bản mã: Kẻ thám mã chỉ có trong tay bản mã.
- Biết bản rõ: Kẻ thám mã biết được một mẫu của bản rõ
và phần mã tương ứng của bản rõ đó.
- Chọn bản rõ: Kẻ thám mã có thể tạm thời tước quyền
điều khiển hệ thống, rồi chọn bản rõ và xây dựng bản mã
tương ứng.
- Chọn bản mã: Kẻ thám mã tạm thời điều khiển hệ thống,
rồi chọn bản mã và xây dựng lại bản rõ tương ứng.
Lê Thụy 17
Trường Đại học Dân lập Hải Phòng
III. Mã dòng (Stream Cipher).
Trong các hệ mật mã được xét cho đến nay, ta dùng cùng một
khoá k để mã hoá các ký tự (hay các bộ m ký tự) trong bản rõ. Điều
khác cơ bản của mã dòng là sinh ra một dò