Giáo trình An toàn bảo mật thông tin - Nguyễn Khánh Văn - Chương 0: Mở đầu

chu kỳ p (độ dài khoá)
2. Chia tách MÃ thành p đoạn phân mã, mỗi đoạn bao gồm các chữ ở vị trí kp+i 
 (k=1,2,3 ... ; i=0,p-1), tức là được mã hoá theo bảng thế với chữ khoá [i].
3. Dùng phương pháp một bảng thế đã biết để giải từng đoạn phân mã
Người ta sử dụng khái niệm IC (Index of Coincidence) để tính chu kỳ p.
Theo định nghĩa, IC xác định qua công thức: 
25i=0 fi (fi-1)
 IC = -----------------
 n(n-1)
Trong đó là xác xuất của phép thử - nhặt ra 2 con chữ ngẫu nhiên bất kỳ từ trong một đoạn văn 
bản - để thu được cùng một chữ  cho trước.
Số bảng thế (p) 1 2 3 4 5 ... 10
IC 0.068 0.052 0.047 0.044 0.043 ... 0.041
IC của văn bản tiếng Anh (p=1) đạt gia trị 0.068. Khi qua mã hoá, IC sẽ giảm dần đi khi tăng dần 
số lượng bảng thế (hay tăng chiều dài khoá). Qua đó ta thấy IC thể hiện độ không đồng đều của 
các tần xuất xuất hiện các chữ cái. Trong văn bản gốc, độ không đồng đều (lồi lõm) là lớn nhất 
nên IC là lớn nhất. Còn khi mã hoá với nhiều bảng thế, đồ thị tần xuất được làm "bằng phẳng 
hoá" nên tất nhiên IC giảm đi.
Phương pháp thực hành.
1. Đặt k=1
2. Kiểm tra xem p có phải nhận giá trị k hay không.
2.a. Chia Mã thành k phân mã và tính IC của các phân mã.
2.b. Nếu như chúng đều xấp xỉ nhau và đều xấp xỉ 0.068 thì p=k
Nếu chúng khác nhau nhiều và nhỏ hơn nhiều so với 0.068 thì p>k
4. Tăng k lên một đơn vị và lặp lại bước 2.
One-time-pad (Vernam cipher)
X: x n t f u h b z t
Z: A s u n n y d a y
Y: Y G O I I G F A S
Nguyễn Khanh Văn Bài mở đầu về ATBM Thông tin HUT-2000
• Đề xuất bởi G. Vernam (1917), sau đó được chứng mình là có perfect secretcy (1949)
– “One-time pad”: khóa viết trên 1 băng (tape) dài, sử dụng đúng 1 lần
– Chuỗi khóa là chuỗi ngẫu nhiên
• Sinh mã Y = X + Z (mod 26)
• Giải mã X = Y - Z (mod 26)
• One-time-pad có thể coi là mã Vigenere với khóa là một chuỗi ngẫu nhiên có độ dài đúng 
bằng văn bản
Nguyễn Khanh Văn Bài mở đầu về ATBM Thông tin HUT-2000
Lý thuyết về sự bí mật tuyệt đối (Shannon)
Ta hãy đứng vào vai người muốn phá mã. Giả sử ta chỉ có khả năng của Eve, tức là chỉ có trong 
tay mã )ciphertext only, tuy nhiên cũng giả sử rằng ta có phương tiện cực kỳ hùng hậu (coi như 
vô hạn) để có thể tiến hành được bất cứ phép tìm kiếm vét cạn nào.
1. Có thể luôn luôn tìm được một TIN (plaintext) duy nhất, tức là khóa duy nhât, không nếu như 
chỉ biết mã ứng với nó (Câu trả lời “có” sẽ có nghĩa là mọi thuật toán mã hoá đều không phải là 
an toàn tuyệt đối và có thể phá được trên lý thuyết).
2. Nêu câu trả lời là có thì có phương pháp nào để đánh giá và so sánh mức độ an toàn của các 
thuật toán mã hoá.
Ví dụ 1.12.
Giả sử chúng ta có một đoạn MÃ (cryptogram) Y được tạo ra từ phép mã hóa một bảng thế. Để 
tìm TIN tương ứng, ta có thể sử dụng tìm kiếm vét cạn. Với Y ngắn ta có thể tìm được nhiều đoạn 
TIN X sinh ra cùng MÃ Y (tất nhiên với các phép thế khác nhau). Ví dụ ta có đoạn MÃ sau:
AZNPTFZHLKZ
Ta có thể tạo ra ít nhất là 2 đoạn TIN tương ứng bằng 2 bảng thế như sau:
Bảng thế một
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
K B C D T E G I J M O L A Q R H S F N P U V W X Z Y
Bảng thế hai
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
L P H N Z K T A F E
MÃ: A Z N P T F Z H L K Z
TIN 1: m y s t e r y p l a y
TIN 2: r e d b l u e c a k e
Nguyễn Khanh Văn Bài mở đầu về ATBM Thông tin HUT-2000
Ví dụ 1.13. Với MÃ ‘HLKZ’ có thể dễ dàng tìm ra 4 TIN tương ứng:
C.text: H L K Z
P.text1: p l a y
P.text2: c a k e
P.text3: m i s t
P.text4: W a s h
bằng các bảng thế như sau:
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
K L H Z
L H Z K
L H K Z
Qua các ví dụ 12 và 13 có thể thấy được rằng đối với monalphabetic, khi MÃ còn tương đối ngắn 
thì luôn luôn tồn tại cùng lúc nhiều đoạn TIN có nghĩa mà có thể mã hoá thành mã đang xét được 
(tất nhiên là khoá dự đoán tương ứng). Tuy nhiên với MÃ có độ dài trên 50 trở lên thì sẽ chỉ có 
duy nhất một plaintext thoả mãn, tức chính nó là TIN cần tìm. Như vậy, nếu như E – nhà phân 
tích giải phá mã (cryptanalyst) – “tóm” được một đoạn MÃ có độ dài đủ lớn, thì nói chung luôn 
luôn có thể phá được mã loại 1-bảng thế này.
Trong ví dụ 14 ta quan sát một quá trình cụ thể giải phá mã cộng tính. Có 26 khoá là 26 khả năng 
để thử. Eve sẽ nghe trộm và lần lượt bắt được từng ký tự mã được phát trên đường truyền. Mỗi 
khi nghe được thêm một từ mã thì E tiến hành thử luôn cả 26 khả năng để tìm TIN có nghĩa luôn. 
Khi mới nghe trộm được từ mã đầu tiên thì khả năng của cả 26 khoá đều ngang ngửa nhau (xác 
xuất đoán đúng đều nhỏ, cỡ nhỏ hơn 0.1), khi nghe trộm được từ khoá 2,3.. thì các xác xuất sẽ 
thay đổi, hầu hết là tiếp tục giảm đi, trừ trường hợp với khoá 15. Khi nghe được từ mã 5 thì xác 
suất ứng với khoá 15 sẽ là 1 trong khi các xác suất khác đều là khoong từ là khoá 15 là khoá đúng 
(chữ consi ứng với nó là đoạn đầu của một số từ có nghĩa trong tiếng Anh như consider, 
consideration...).
Ví dụ 1.14. Hãy xét một hệ mã cộng với 26 khóa khác biệt (“đẩy” 0 – 25 vị trí). Giả sử ta bắt 
được MÃ = “sdchx”. Ta sẽ thử cả 26 khóa để phá mã này. Bảng đưới đây minh họa phép thử vét 
cạn này, với n là độ dài đoạn MÃ “bị tóm” tính đến thời điểm tương ứng.
Shift Decruption N = 1 n = 2 n = 3 n = 4 n = 5
0 rdchx 0.060 0.070
25 sediy 0.063 0.257 0.427 0.182
24 tfejz 0.091 0.003
Nguyễn Khanh Văn Bài mở đầu về ATBM Thông tin HUT-2000
23 ugfka 0.28 0.052
22 vhglb 0.010
21 wihmc 0.024 0.128
20 xjind 0.002
19 ykjoe 0,020
18 zlkpf 0.001 0.001
17 amlqg 0.082 0.072 0.004
16 bnmrh 0.015
15 consi 0.028 0.202 0.515 0.818 1
14 dpotj 0.043
13 eqpuk 0.127 0.044
12 frqvl 0.022 0.058
11 gsrwm 0.020 0.015
10 htsxn 0.061 0.052 0.046
9 iutyo 0.070 0.001
8 jvuzp 0.002
7 kwvaq 0.008
6 lxwbr 0.040
5 myxcs 0.024 0.028
4 nzydt 0.067 0.028
3 oazeu 0.075 0.014
2 pbafv 0.019
1 qcbgw 0.001
Nguyễn Khanh Văn Bài mở đầu về ATBM Thông tin HUT-2000
Lý thuyết về bí mật tuyệt đối.
Trong hệ thống đảm bảo bí mật tuyệt đối, mã dù bị tiết lộ cho kẻ thù cũng không hề đem lại một ý 
nghĩa nào. Nó không làm thay đổi phân phối xác xuất ban đầu của plaintext.
Hay là, một hệ thống là có bí mật tuyệt đối nếu:
P(X) = P(X/Y)  TIN X VÀ MÃ Y
Định lý Shannon:
Trong hệ thống có BMTĐ, số lượng khoá có thể (độ lớn không gian khoá) phải lớn hơn hoặc 
bằng số lượng thông báo có thể (độ lớn không gian TIN). Điều này cho thấy để đạt được BMTĐ 
thì khoá phải rất dài, do đó việc trao chuyển khoa giữa hai bên truyền tin sẽ làm cho hệ thống trở 
nên phi thực tế.
Như vậy, nhìn chung chúng ta không thể đạt được an toàn và bảo mật vô điều kiện mà chỉ có thể 
có được các hệ thống với mức an toàn thực tế (Practical security) được cài đặt tuỳ theo giá trị của 
thông tin cần bảo vệ và thời gian sống của nó.
Đánh giá mức độ bảo mật của một cipher.
Shannon đưa ra một khái niệm, unicity distance, để “đo” mức security của một hệ thống: Unicity 
distance, ký hiệu N0, là số ít nhất các chữ mã “cần tóm được” để có thể xác định được khóa đúng 
duy nhất. Unicity distance có thể được tính theo công thức:
d
E
N 20
log
Trong đó d là độ dư thừa của ngôn ngữ sử dụng của TIN.
Ví dụ 1.15. Câu tốc ký sau đây thực tế có thể “khôi phục” được về dạng đầy đủ một cách duy 
nhất:
Mst ids cn b xprsd n fwr ltrs, bt th xprsn s mst nplsnt  Most ideas can be expressed in fewer 
letters, but the expression is most unpleasant.
Điều này chứng tỏ những chữ đã bị mất trong câu ban đầu là dư thừa về mặt thông tin.
Khái niệm độ dư thừa có thể được định nghĩa thông qua công thức:
d = R - r bits
Trong đó R: absolute rate và r: true rate của ngôn ngữ.
R được định nghĩa như là số lượng bit được sử dụng để biểu thị một chữ cái trong bảng chữ với 
giả sử các chữ có tần xuất xuất hiện như nhau:
R = log2A bits
với A là kích thước của bảng chữ
Ví dụ 1.16. Đối với tiếng Anh ta có R = log226  4.7 bits.
True rate r được định nghĩa như là số lượng bit trung bình để biểu thị một chữ cái khi văn bản 
được xử lý theo kiểu tốc ký, gạt bỏ các chữ không cần thiết (hoặc áp dụng kỹ thuật nén trên cơ sở 
các thuộc tính thống kê của văn bản) mà vẫn không làm mất thông tin chuyển tải.
Ví dụ 1.17. Đối với văn bản tiếng Anh, tính trung bình, r nằm trong khoảng 1 - 1,5 bit
Nguyễn Khanh Văn Bài mở đầu về ATBM Thông tin HUT-2000
Độ dư thừa có thể coi là một thước đo của tính cấu trúc và tính “dễ đoán” (predictability) của 
ngôn ngữ. Độ dư thừa cao hơn chứng tỏ tính cấu trúc và tính “dễ đoán” cao hơn. Một nguồn phát 
tin thực sự ngẫu nhiên sẽ không có dư thừa.
Trong tiếng Anh, độ dư thừa nằm trong khoảng từ 3.2 đến 3.7 bits (gây nên bời biểu đó tần xuất 
“lồi lõm”, các mẫu tự 2-chữ, 3-chữ - bigrams và trigrams - phổ biến)
Sử dụng Unicity distance ta có thể so sánh độ an toàn của các thuật toán mã hóa khác nhau.
Ví dụ 1.18. Với mã 1-bảng thế, ta quan sát thấy
E= |Z| = 26!
P(Z) =1/26!
log2E = log2(26!)  88.4 bits
N0  88.4 / 3.7  23.9 ký tự
Như vậy các MÃ chứa 24 ký tự trở lên sẽ có thể bị giải mã một cách duy nhất.
Ví dụ 1.19. Với mã one-time-pad:
X = không gian khóa = {tập hợp các đoạn văn bản tiếng Anh có độ dài k}
Z = không gian khóa = {tập các chuỗi chữ độ dài k trông bảng chữ cái tiếng Anh}
Giả thiết các khóa được chọn một cách ngẫu nhiên với xác xuất đồng nhất
N0 = log2E/d
E= 26k log2(26k) = k log2264.7k
N0 = (4.7k)/3.7 = 1.37k
Do đó, thậm chí nếu E nghe trộm toàn bộ tất cả các chữ cái của đoạn MÃ, cô ta vẫn không thể 
giải phá mã (tìm được TIN tương ứng duy nhất).
Ta có thể “tăng” tính mật của một hệ mã cho trước hay không?
1. Tăng độ lớn không gian khóa
2. Giảm tính dư thừa của ngôn ngữ văn bản TIN: tiền xử lý qua 1 bước thuật toán nén
Chú ý: một thuật toán nén lý tưởng có thể đem lại độ dư thừa 0, do đó N0  0
3. Có thể chèn thêm một đoạn văn bản ngẫu nhiên để “phẳng hóa“ độ thị tần xuất của văn 
bản TIN. Ta sẽ xét cụ thể biện pháp này dưới đây
Công thức sau cho biết độ dư thừa của văn bản mới (sau khi chèn thêm chuỗi ký tự ngẫu nhiên)
d
ML
M
d 
~
Văn bản TIN gốc Chuỗi ngẫu nhiên chèn 
M L