Hoàng Thu Phương - Khoa ATTT 2
CHƯƠNG I
LÝ THUYẾT THÔNG TIN
TRONG CÁC HỆ MẬT
Hoàng Thu Phương - Khoa ATTT 3
Giới thiệu môn học
 Nội dung
Chương 1: Nhập môn mật mã học
Chương 2: Mật mã khoá bí mật
Chương 3: Mật mã khoá công khai
Chương 4: Hàm băm, xác thực và chữ kí số
Hoàng Thu Phương - Khoa ATTT 4
Giới thiệu môn học
 Thời lượng
60 tiết = 4 đơn vị học trình
 Hình thức thi và kiểm tra
Thi viết
Sau các bài có thể có bài tập về nhà hoặc có
các hình thức kiểm tra
Hoàng Thu Phương - Khoa ATTT 5
Nội dung chính
 1.1 Một số khái niệm cơ bản trong mật mã
 1.2 Sơ đồ khối đơn giản của một HT thông tin số
 1.3 Thuật toán và độ phức tạp
1.3.1 Khái niệm về thuật toán
1.3.2 Độ phức tạp của thuật toán
 1.4 Độ mật hoàn thiện
1.4.1 Quan điểm về độ an toàn của hệ mật
1.4.2 Nhắc lại một số lí thuyết cơ bản về xác suất
1.4.3 Độ mật hoàn thiện
 1.5 Entropy

 Cho k = 5
Khi đó: bản mã y = e
k
(x) = MJRRTBTWRI
 H: 7 + 5 mod 26 = 12  M;
 E: 4 + 5 mod 26 = 9  J;
 …
Ta
cũng có thể suy ra bản rõ x từ bản mã y từ hàm giải mã:
d
k
(y) = y – k mod 26
Hoàng Thu Phương - Khoa ATTT 9
1.1 Một số khái niệm cơ bản
 Khoa học mật mã (cryptology) gồm:
 Mật mã học (cryptography): là khoa học nghiên cứu cách ghi
bí mật thông tin nhằm biến đổi bản rõ thành bản mã.
 Phân tích mật mã (cryptanalysis): nghiên cứu cách phá các hệ
mật nhằm phục hồi bản rõ ban đầu từ bản mã, nghiên cứu các
nguyên lí và phương pháp giải mã mà không biết khóa.
 Có 3 phương pháp tấn công cơ bản của thám mã:
• Tìm khóa vét cạn
• Phân tích thống kê
• Phân tích toán học
Hoàng Thu Phương - Khoa ATTT 10
1.1 Một số khái niệm cơ bản
Các kiểu tấn công thám mã:
• Tấn công chỉ với bản mã: biết thuật toán, bản mã, dùng phương pháp
thống kê xác định bản rõ
• Tấn công với bản rõ đã biết: biết thuật toán, biết được bản mã/bản rõ,

giải của bài toán được xét sau một số bước
thực hiện.
VD: Thuật toán tìm cực đại
Input: cho n số X[1],…, X[n]
Output: m, j sao cho




 
 
1 k n
m X j max X k
Hoàng Thu Phương - Khoa ATTT 14
1.3. Thuật toán …
Sơ đồ khối của thuật toán tìm cực đại
Hoàng Thu Phương - Khoa ATTT 15
Đ
S
Đ
S
Nhập n và dóy X[1],…, X[n]
j  n; k  n-1m  X[n]
k = 0 ?
X[k]  m ?
j  k; m
i
X[k]
k  k-1
Đưa ra m, j rồi kết thỳc

định trên tập hợp các số nguyên dương. Ta nói f[n]
có bậc O-lớn của g[n] và viết, f[n] = O(g[n]) nếu tồn
tại một số C>0; sao cho với n đủ lớn. Các hàm f[n]
và g[n] đều dương thì f[n] < C(g[n]).
VD: f[n] = 3n
3
+ 5n
2
+ 2n + 8 (n>0)
 Ta nói: f[n] = O(n
3
)
Hoàng Thu Phương - Khoa ATTT 19
1.3. Thuật toán …
 Một số tính chất:
Hoàng Thu Phương - Khoa ATTT 20
1.3. Thuật toán …
 Định nghĩa 2: Một thuật toán được gọi là có độ phức tạp đa
thức hoặc có thời gian đa thức, nếu số các phép tính cần thiết
để thực hiện thuật toán không vượt quá O(log
d
n) , trong đó n là
độ lớn của đầu vào và d là số nguyên dương nào đó.
 Nói cách khác nếu đầu vào là các số k bít thì thời gian thực
hiện thuật toán là O(k
d
), tức là tương đương với một đa thức
của k.
 Khi giải một bài toán không những ta chỉ cố gắng tìm ra một
thuật toán nào đó, mà còn muốn tìm ra thuật toán “tốt nhất”.

mà người giải mã được phép thực hiện.
Hệ mật an toàn không điều kiện nếu nó không
thể bị phá ngay cả khi không hạn chế khả năng
tính toán
 Độ an toàn không điều kiện của một hệ mật
không thể nghiên cứu theo độ phức tạp tính toán
mà sẽ dùng lí thuyết xác suất
Hoàng Thu Phương - Khoa ATTT 25
1.4.2 Một số kiến thức cơ bản về lí thuyết
xác suất
Định nghĩa 1: X và Y là các biến ngẫu nhiên (bnn)
p(x): xác suất (xs) để X nhận giá trị x
p(y): xs để Y nhận giá trị y
p(x, y): xs đồng thời để X nhận giá trị x và Y
nhận giá trị y.
p(x| y): xs để X nhận giá trị x với điều kiện (đk)
Y nhận giá trị y.
Hoàng Thu Phương - Khoa ATTT 26
X và Y được gọi là độc lập nếu
p(x, y) = p(x).p(y), với | x є X và | y є Y.
 Quan hệ giữa xs đồng thời và xs có điều kiện
được biểu thị theo công thức sau:
p(x,y) = p(x).p(y|x) = p(y).p(x|y)
 ĐL1: (ĐL Bayes)
Nếu p(y) > 0 thì: