CHƯƠNG 03
CÁC GIẢI THUẬT MÃ HÓA DỮ LIỆU
ĐỐI XỨNG
ThS.Nguyễn Duy
9/28/2014
Nội Dung
Giới thiệu về mật mã học
Lịch sử của mật mã học
Giải thuật mã hoá cổ điển
Giải thuật mã hoá hiện đại
Phá mã một hệ thống mật mã
2
9/28/2014
Nội Dung
Giới thiệu về mật mã học
Lịch sử của mật mã học
Giải thuật mã hoá cổ điển
Giải thuật mã hoá hiện đại
Phá mã một hệ thống mật mã
3
9/28/2014
Giới thiệu về mật mã học
Giới thiệu
Mật mã hoá được sử dụng kể từ cổ đại cho đến
tận ngày nay.
Hiện nay, các giao dịch tài chính, chuyển khoản,
mua sắm hàng hoá, thư từ, tài liệu… được thực
hiện nhiều qua môi trường mạng đòi hỏi dữ liệu
phải được bảo mật tốt => phải được mã hoá
4
9/28/2014
Giới thiệu về mật mã học
Giới thiệu - tt
Mã hóa là một dạng của mật mã. Mã hóa cách
thức xáo trộn hay biến thông tin từ dạng có thể
đọc được sang dạng không thể đọc được.
Ví dụ :
Xáo trộn dữ liệu : 2 ký tự đứng cạnh nhau thì hoán
đổi vị trí cho nhau, những ký tự nào lẻ thì giữ nguyên
vị trí
Biến đổi thông tin : tăng giá trị mỗi ký tự lên 1 đơn vị
5
9/28/2014
ABCDEF BADCFE
ABCDEF BCDEFG
Giới thiệu về mật mã học
Mô hình mã hóa đối xứng
6
9/28/2014
Giới thiệu về mật mã học
Mô hình hệ thống mật mã đối xứng
7
9/28/2014
Giới thiệu về mật mã học
Cryptographic Systems
8
9/28/2014
Phụ thuộc vào 3 yếu tố:
The type of
operations used for
transforming
plaintext to
ciphertext
Substitution
Transposition
The number of keys
used
Symmetric,
single-key,
secret-key,
conventional
encryption
Asymmetric,
two-key, or
public-key
encryption
The way in which the
plaintext is processed
Block cipher
Stream cipher
Giới thiệu về mật mã học
Các khái niệm cơ bản
Plaintext: dữ liệu trước khi mã hóa
Ciphertext: dữ liệu sau khi mã hóa
Encryption algorithm: thuật toán mã hóa
Decryption algorithm: thuật toán giải mã
Secret key: khóa được thuật toán mã hóa và
thuật toán giải mã sử dụng để mã hóa và giải
mã dữ liệu
9
9/28/2014
Nội Dung
Giới thiệu về mật mã học
Lịch sử của mật mã học
Giải thuật mã hoá cổ điển
Giải thuật mã hoá hiện đại
Phá mã một hệ thống mật mã
10
9/28/2014
Lịch sử của mật mã học
Mật mã học là ngành có lịch sử hàng ngàn năm.
Mật mã học cổ điển với bút và giấy.
Mật mã học hiện đại với điện cơ, điện tử, máy tính.
Sự phát triển của mật mã học đi liền với sự phát triển
của phá mã (thám mã):
Phát hiện ra bức điện Zimmermann khiến Hoa Kỳ tham gia Thế
chiến I
Việc phá mã thành công hệ thống mật mã của Đức Quốc xã góp
phần đẩy nhanh thời điểm kết thúc thế chiến II.
Hai sự kiện khiến cho mật mã học ứng dụng rộng rãi:
Sự xuất hiện của tiêu chuẩn mật mã hóa DES.
Sự ra đời của các kỹ thuật mật mã hóa khóa công khai.
11
9/28/2014
Nội Dung
Giới thiệu về mật mã học
Lịch sử của mật mã học
Giải thuật mã hoá cổ điển
Giải thuật mã hoá hiện đại
Phá mã một hệ thống mật mã
12
9/28/2014
Giải thuật mã hoá cổ điển
Kĩ thuật Substitution
Substistution hay còn gọi là mã hóa “thay thế”
Những kí tự trong plaintext sẽ được thay thế
bằng những kí tự khác, những con số hoặc
những kí hiệu.
13
9/28/2014
Giải thuật mã hoá cổ điển
Thuật toán Caesar Cipher
14
9/28/2014
Giải thuật mã hoá cổ điển
Thuật toán Caesar Cipher
15
9/28/2014
Can define transformation as:
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
D E F G H I J K L M N O P Q R S T U V W X Y Z A B C
Mathematically give each letter a number
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
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
Algorithm can be expressed as:
c = E(3, p) = (p + 3) mod (26)
A shift may be of any amount, so that the general
Caesar algorithm is:
C = E(k , p ) = (p + k ) mod 26
Where k takes on a value in the range 1 to 25; the
decryption algorithm is simply:
p = D(k , C ) = (C - k ) mod 26
16
9/28/2014
Giải thuật mã hoá cổ điển
Thuật toán Monoalphabetic Cipher
17
9/28/2014
Đối với một số nguyên dương d bất kỳ, chia
thông báo m thành từng khối có chiều dài d. Rồi
lấy một hoán vị h của 1, 2, …, d và áp dụng h
vào mỗi khối.
Ví dụ: nếu d=5 và h=(4 1 3 2 5), hoán vị (1 2 3 4
5) sẽ được thay thế bằng hoán vị mới (4 1 3 2
5).
Ví dụ: ta có thông báo
m = JOHN IS A GOOD ACTOR
Qua phép mã hoá này m sẽ trở thành chuỗi
mật mã c sau:
c = NJHO IO S GAOT DCAOR
Giải thuật mã hoá cổ điển
Thuật toán One-time Pad
18
9/28/2014
h e l p n e e d e d
001 000 010 100 101 000 000 011 000 011
e=000 h=001 l=010 d=011 p=100 n=101 a=110
Encryption: Plaintext Key = Ciphertext
111 101 110 101 111 100 000 101 110 000
110 101 100 001 010 100 000 110 110 011
a n p h l p e a a d
Plaintext:
Key:
Ciphertext:
Giải thuật mã hoá cổ điển
Thuật toán Affine Cipher
19
9/28/2014
Mã tuyến tính là mã thay thế có dạng:
e(x) = ax + b (mod 26), với a, b Z
26
Nếu a = 1 ta có mã dịch chuyển.
Giải mã: Tìm x?
y = ax + b (mod 26)
ax = y – b (mod 26)
x = a
-1
(y – b) (mod 26).
Giải thuật mã hoá cổ điển
Thuật toán Affine Cipher - tt
20
9/28/2014
Ví dụ: y = E(x) = (5x + 8)
a = 5
b = 8
Giải thuật mã hoá cổ điển
Thuật toán Affine Cipher - tt
21
9/28/2014
Ví dụ: y = E(x) = (5x + 8)
a = 5
b = 8
Giải thuật mã hoá cổ điển
Kĩ thuật Transposition
Transposition là cơ chế mã hóa dựa trên kĩ
thuật thay đổi vị trí của dữ liệu
22
9/28/2014
Nội Dung
Giới thiệu về mật mã học
Lịch sử của mật mã học
Giải thuật mã hoá cổ điển
Giải thuật mã hoá hiện đại
Phá mã một hệ thống mật mã
23
9/28/2014
Giải thuật mã hoá hiện đại
Thường sử dụng mã khối kết hợp với các phép
hoán vị và thay thế.
Việc biến đổi văn bản được thực hiện nhiều lần
trong một số vòng lặp.
Khoá con của các vòng lặp sẽ khác nhau và
được sinh ra từ khoá ban đầu.
Phổ biến có DES, AES, RSA
24
9/28/2014
Giải thuật mã hoá hiện đại
Phân loại
Mã hoá khoá đối xứng (symmetric)
Block ciphers: mã hoá các khối có chiều dài cố định
64 bit hoặc 128 bit. Phổ biến có IDEA, RC2, DES,
Triple DES, Rijndael (AES), MARS, RC6, Serpent,
Twofish, DESX, DESL, DESXL.
Stream ciphers: mã hoá từng bit của thông điệp. Đại
diện là RC4.
Mã hoá khoá bất đối xứng (asymmetric): RSA
25
9/28/2014