Bài giảng An toàn hệ thống thông tin - Chương 2: Symmetric ciphers (Mã hóa đối xứng) - Nguyễn Thị Hạnh
07/01/2018
Chương 2:
SYMMETRIC CIPHERS
(Mã hóa đối xứng)
Giáo viên: Nguyễn Thị Hạnh
1
Nguyễn Thị Hạnh
Contents
1. Mã cổ điển (Classical Encryption)
2. Mã dòng (Stream Ciphers) và Mã khối (Block Ciphers)
3. Mã DES (Data Encryption Standard)
4. Mã hiện đại AES (Advanced Encryption Standard)
5. Các mô hình ứng dụng mã khối
( Cryptography and Network Security: Principles and
Practices (3rd Ed.) – Chapter 2, 3, 5, 6)
Nguyễn Thị Hạnh
2
1
07/01/2018
1. Mã cổ điển (Classical Encryption)
1.1 Khái niệm về Mã đối xứng (Symmetric Cipher)
1.2 Một số mã đối xứng nổi tiếng
Nguyễn Thị Hạnh
3
1.1 Khái niệm mã đối xứng
˗ Mô hình mã hóa đối xứng
Nguyễn Thị Hạnh
4
2
07/01/2018
1.1 Khái niệm mã đối xứng
˗ Bản rõ X (Plaintext): được gọi là bản tin gốc. Đây là
dữ liệu ban đầu ở dạng rõ. Bản rõ có thể được chia
nhỏ có kích thước phù hợp.
˗ Thuật toán mã hóa (Encryption algorithm): là thuật
toán được sử dụng để mã hóa (thay thế hoặc biến
đổi) bản rõ
˗ Khóa bí mật (Secret key): Khóa bí mật được đưa
vào thuật toán mã hóa. Khóa này là giá trị độc lập với
bản rõ và thuật toán mã hóa. Thuật toán sẽ tạo ra đầu
ra (input) khác nhau tùy thuộc vào khóa đặc biệt được
dùng tại thời điểm đó. Các kỹ thuật thay thế
(substitution) và hoán vị (transformation) được thực
hiện bởi thuật toán tùy thuộc vào khóa (key)
Nguyễn Thị Hạnh
5
1.1 Khái niệm mã đối xứng
˗ Bản mã (Ciphertext): Thông tin, dữ liệu đã được mã
hoá ở dạng mờ. Nó tùy thuộc vào plain text và secret
key. Cho trước một thông điệp, 2 khóa khác nhau thì
sẽ tạo ra được hai bản mã khác nhau. Bản mã là một
dòng dữ liệu ngẫu nhiên và nó bền vững và khó hiểu.
˗ Thuật tóa giải mã (Decryption algorithm): Thuật
toán giải mã (Decryption algorithm): đây là thực chất
là thuật toán mã hóa chạy theo chiều ngược lại. Nó
lấy ciphertext và secret key để tạo ra plaintext gốc.
˗ Người gửi/Người nhận (Sender/recipient): Người
gửi/Người nhận dữ liệu
Nguyễn Thị Hạnh
6
3
07/01/2018
Mô hình mã đối đối xứng
Nguyễn Thị Hạnh
7
Đặc tính của mã đối xứng
˗ Thuật toán mã hóa và giải mã sử dụng chung một
khóa, thuật toán giải mã là phép toán ngược của thuật
toán mã hóa. Vì vậy mô hình trên được gọi là phương
pháp mã hóa đối xứng.
˗ Đặc tính của mã đối xứng:
° Khóa phải được giữ bí mật giữa người gởi và
người nhận, khóa phải được chuyển một cách an
toàn từ người gởi đến người nhận.
° Một hệ mã hóa đối xứng phải có tính an toàn. An
toàn khi và chỉ khi nó không thể bị phá mã (điều
kiện lý tưởng) hoặc thời gian phá mã là bất khả thi.
Nguyễn Thị Hạnh
8
4
07/01/2018
Kỹ thuật mã hóa (Cryptography)
Hệ thống mã hóa được đặc trưng bởi:
˗Kỹ thuật được sử dụng để chuyển đổi bản rõ thành bản
mã. Tất cả các thuật toán được dựa vào 2 kỹ thuật cơ
bản:
(a)Phép thế (substitution): dùng từng ký tự (hay
từng nhóm ký tự) trong bản rõ được thay thế bằng
một ký tự (hay một nhóm ký tự) khác để tạo ra bản
mã. Bên nhận chỉ cần đảo ngược trình tự thay thế
trên bản mã để có được bản rõ ban đầu.
(b)Hoán vị (transposition): Các ký tự trong bản rõ
được giữ nguyên, chúng chỉ được sắp xếp lại vị trí
để tạo ra bản mã. Yêu cầu cơ bản là không có
thông tn nào bị mất (có nghĩa là tất cả các thao
thác có thể đảo ngược).
Nguyễn Thị Hạnh
9
Kỹ thuật mã hóa (Cryptography)
˗ Số khóa được người gửi và người nhận dùng khi mã
hóa.
° Một khóa duy nhất: Mã đối xứng/ Mã khóa đơn/
Mã khóa bí mật khóa/ Mã hóa thông thường
(symmetric, single-key, secret-key, or conventional
encryption)
° Hai khóa: Mã hóa bất đối xứng/ mã hóa hai khóa/
Mã hóa khóa công khai (asymmetric, two-key, or
public-key encryption)
Nguyễn Thị Hạnh
10
5
07/01/2018
Kỹ thuật mã hóa (Cryptography)
˗ Cách mà bản rõ được xử lý:
° Khối (block cipher): dữ liệu được chia thành
từng khối có kích thước xác định và áp dụng thuật
toán mã hóa với tham số cho từng khối.
° Dòng (stream cipher): từng phần tử ở đầu vào
được xử lý liên tục tạo phần tử đầu ra tương ứng.
Nguyễn Thị Hạnh
11
Phá mã (Cryptanalysis)
˗ Hai cách tiếp cận tấn công mã đối xứng:
° Phân tích mật mã (cryptanalysis attack) hay còn
gọi “tấn công dùng thuật toán”: dựa trên thuật
thoán và một số đặc trưng chung về bản rõ hoặc
vài cặp mậu bản rõ – bản mã. Kiểu tấn công này
khai thác các đặc trưng của thuật toán để tìm bản
rõ cụ thể hoặc tìm kiếm khóa.
° Tấn công vén cạn (Brute-force attack): Kẻ tấn
công tìm cách thử mọi khóa có thể trên bản mã cho
đến khi nhận được bản rõ. Trung bình cần thử một
nữa số khóa.
Nguyễn Thị Hạnh
12
6
07/01/2018
Phân tích mật mã (Cryptanalysis)
˗ Các kiểu tấn công phân tích mật mã
° Biết thuật toán và bản mã ‰ xác định bản rõ.
° Biết thuật toán, biết được bản mã/bản rõ ‰ tìm
khóa.
° Chọn bản rõ và nhận được bản mã, biết thuật toán
‰ tìm khóa.
° Chọn bản mã và có được bản rõ tương ứng, biết
thuật toán ‰ tìm khóa
Nguyễn Thị Hạnh
13
Vét cạn (Brute-force)
˗ Về mặt lý thuyết phương pháp này luôn thực hiện
được, do có thể tiến hành thử từng khóa, mà số khóa
là hữu hạn.
˗ Phần lớn công sức của các tấn công đều tỷ lệ thuận
với kích thước khoá. Khóa càng dài thời gian tìm kiếm
càng lâu và thường tăng theo hàm mũ.
˗ Ta có thể giả thiết là kẻ thám mã có thể dựa vào đặc
trưng về ngữ cảnh để nhận biết được bản rõ.
Nguyễn Thị Hạnh
14
7
07/01/2018
Vét cạn (Brute-force)
˗ Thời gian trung bình cần để tìm kiếm toàn bộ
Nguyễn Thị Hạnh
15
1.2 Một số mã đối xứng nổi tiếng
˗ Một số mã áp dụng phép thay thế:
° Mã Caesar (Caesar Cipher)
° Mã hóa đơn bản (Monoalphabetic Ciphers)
° Mã Playfair (Playfair Cipher)
° Mã One-Time Pad (OTP)
˗ Một số mã áp dụng phép hoán vị
Nguyễn Thị Hạnh
16
8
07/01/2018
1.2.1 Caesar Cipher
˗ Thế kỷ thứ 3 trước công nguyên, Julius Ceasar đưa ra
phương pháp mã hóa này.
˗ Thay thế mỗi ký tự trong bản rõ bằng ký tự đứng
sau nó k vị trí trong bảng chữ cái. Giả sử chọn k=3,
ta có bảng chuyển đổi:
° Bản rõ: 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
° Bản mã: 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
˗ Ví dụ:
° Bản rõ: meet me after the toga party
° Bản mã: PHHW PH DIWHU WKH WRJD SDUWB
Nguyễn Thị Hạnh
17
1.2.1 Caesar Cipher
˗ Chúng ta hãy gán cho mỗi chữ cái một con số nguyên
từ 0 đến 25:
đó:
C = (P + k) mod 26 (mod: phép chia lấy số dư)
˗ Và quá trình giải mã đơn giản là:
P = (C – k) mod 26
˗ k được gọi là khóa.
˗ Hiện nay, mã Ceasar không được xem là an toàn.
Nguyễn Thị Hạnh
18
9
07/01/2018
1.2.2 Mã hóa đơn bản (Monoalphabetic
Ciphers)
˗ Phương pháp đơn bảng tổng quát hóa phương pháp
Ceasar bằng cách dòng mã hóa không phải là một
dịch chuyển k vị trí của các chữ cái A, B, C, … nữa mà
là một hoán vị của 26 chữ cái này. Lúc này mỗi hoán
vị được xem như là một khóa.
˗ Việc mã hóa được tiến hành bằng cách thay thế một
chữ cái trong bản rõ thành một chữ cái trong bản mã,
nên phương pháp này được gọi là phương pháp thay
thế.
Plain: abcdefghijklmnopqrstuvwxyz
Cipher: DKVQFIBJWPESCXHTMYAUOLRGZN
Plaintext: ifwewishtoreplaceletters
Ciphertext: WIRFRWAJUHYFTSDVFSFUUFYA
Nguyễn Thị Hạnh
19
1.2.2 Monoalphabetic Ciphers
˗ Số lượng hoán vị của 26 chữ cái là 26! (tương đương
với số khóa).
˗ Vì 26! là một con số khá lớn ‰ tấn công phá mã vét
cạn khóa là bất khả thi (6400 thiên niên kỷ với tốc độ
thử khóa là 109 khóa/giây).
˗ ‰ phương pháp này được xem là một phương pháp
mã hóa an toàn trong suốt 1000 năm sau công
nguyên.
Nguyễn Thị Hạnh
20
10
07/01/2018
1.2.2 Monoalphabetic Ciphers
˗ Tuy nhiên vào thế kỷ thứ 9, một nhà hiền triết người Ả
Rập tên là Al-Kindi đã phát hiện ra một phương pháp
phá mã khả thi khác. Phương pháp phá mã này dựa
trên nhận xét sau:
° Trong ngôn ngữ tiếng Anh, tần suất sử dụng của
các chữ cái không đều nhau, chữ E được sử dụng
nhiều nhất, còn các chữ ít được sử dụng thường là
Z, Q, J. Tương tự như vậy, đối với cụm 2 chữ cái
(digram), cụm chữ TH được sử dụng nhiều nhất.
° Nếu chữ E được thay bằng chữ K thì tần suất xuất
hiện của chữ K trong bản mã là 13.05%. Đây chính
là cơ sở để thực hiện phá mã.
Nguyễn Thị Hạnh
21
1.2.2 Monoalphabetic Ciphers
Tần suất của chữ tiếng anh
Nguyễn Thị Hạnh
22
11
07/01/2018
Ví dụ khám mã
˗ Cho bản mã:
˗ Đếm tần suất ký tự
˗ Đoán P & Z là “e” và “t”
˗ Đoán ZW là “th” và vì vậy ZWP là “the”
Nguyễn Thị Hạnh
23
Ví dụ khám mã
Suy luận tiếp tục ta có được bản rõ
Nguyễn Thị Hạnh
24
12
07/01/2018
1.2.3 Mã Playfair
˗ Được biết như là mã thay thế đa ký tự
˗ Được đề xuất bởi Charles Wheatstone, được mang
tên của người bạn Baron Playfair
˗ Mã hóa Playfair xem hai ký tự đứng sát nhau là
một đơn vị mã hóa, hai ký tự này được thay thế
cùng lúc bằng hai ký tự khác.
Nguyễn Thị Hạnh
25
1.2.3 Playfair Cipher
˗ Dựa trên ma trận 5 ×5 của các ký tự được xây dựng
bằng từ khóa (keyword)
˗ Trong ma trận trên, khóa là từ MONARCHY được điền
vào các dòng đầu của bảng, các chữ cái còn lại của
bảng chữ cái được điền tiếp theo một cách tuần tự.
Riêng hai chữ I, J được điền vào cùng một ô
Nguyễn Thị Hạnh
26
13
07/01/2018
1.2.3 Mã Playfair
˗ Bản rõ được mã hóa một lần 2 ký tự theo quy tắc sau:
1. Cặp hai ký tự giống nhau xuất hiện trong bản rõ sẽ
được tách ra bởi 1 ký tự lọc, chẳng hạn như x. Ví dụ
trước khi mã hóa “balloon” sẽ được biến đổi thành
“balxloxon”.
2. Hai ký tự trong cặp đều rơi vào cùng một hàng, thì mã
mỗi ký tự bằng ký tự bên phải nó trong cùng hàng của
ma trận khóa, nếu nó là phần tử cuối của hàng thì
vòng sang ký tự đầu cùng của hàng, chẳng hạn “ar”
mã hóa thành “rm”
Nguyễn Thị Hạnh
27
1.2.3 Mã Playfair
˗ Bản rõ được mã hóa một lần 2 ký tự theo quy tắc sau:
3. Hai ký tự mà rơi vào cùng một cột thì nó được mã
bằng ký tự ngay dưới, nếu nó ở cuối cột thì vòng
sang ký tự ở đầu cột, chẳng hạn “mu” được mã hóa
thành “CM”.
4. Trong trường hợp khác, mỗi ký tự của bản rõ trong
một cặp được thay bởi ký tự nằm cùng hàng với nó và
cột là cùng cột với ký tự cùng cặp. Chẳng hạn,
“hs”mã thành “bp”, và“ea”mã thành “im”hoặc “jm”
Nguyễn Thị Hạnh
28
14
07/01/2018
1.2.3 Playfair Cipher
˗ An toàn được cải tiếng hơn với mã hóa đơn bản
(simple monoalphabetic ciphers)
˗ Chỉ xét trên 26 ký tự thì mã khóa Playfair có
26x26=676 cặp ký tự.
‰ các cặp ký tự này ít bị chênh lệch về tần suất hơn
so với sự chênh lệnh tần suất của từng ký tự. Ngoài
ra số lượng các cặp ký tự nhiều hơn cũng làm cho
việc phá mã tầnsuất khó khăn hơn. Đây chính là lý do
mà người ta tin rằng mã hóa Playfair không thể bị phá
và được quân đội Anh sử dụng trong chiến tranh thế
giới lần thứ nhất.
˗ Tuy nhiên, nó có thể bị bẻ khoá nếu cho trước vài
trăm chữ, vì bản mã vẫn còn chứa nhiều cấu trúc của
bản rõ.
Nguyễn Thị Hạnh
29
1.2.4 One-Time Pad (OTP)
˗ One-Time Pad – bộ đệm một lần, Được đề xuất bởi
Joseph Mauborgne
˗ Một khóa ngẫu nhiên có chiều dài bằng chiều dài
của bản rõ, mỗi khóa dùng một lần
˗ Khó bẻ khóa vì không có quan hệ nào giữa bản rõ và
bản mã.
˗ Ví dụ mã hóa bản tin “wearediscoveredsaveyourself”
° Bản tin P: wearediscoveredsaveyourself
° Khóa K1: FHWYKLVMKVKXCVKDJSFSAPXZCVP
° Bản mã C: LWPOODEMJFBTZNVJNJQOJORGGU
° Dùng K1 để giải mã thì ta được:
“wearediscoveredsaveyourself”
Nguyễn Thị Hạnh
30
15
07/01/2018
1.2.4 One-Time Pad (OTP)
Xét hai trường hợp giải mã bản mã trên với 2 khóa khác
nhau
˗Trường hợp 1:
° Bản mã C: LWPOODEMJFBTZNVJNJQOJORGGU
° Khóa K2: IESRLKBWJFCIFZUCJLZXAXAAPSY
° Bản giải mã: theydecidedtoattacktomorrow
(they decided to attack tomorrow)
˗Trường hợp 2:
° Bản mã C: LWPOODEMJFBTZNVJNJQOJORGGU
° Khóa K3: FHAHDDRAIQFIASJGJWQSVVBJAZB
° Bản giải mã: wewillmeetatthepartytonight
(we will meet at the party tonight)
Nguyễn Thị Hạnh
31
1.2.5 Mã hàng rào sắt (rail fence cipher)
˗ Đây là một mã dung phép hoán vị hoặc chuyển vị, vì
vậy gọi là mã hoán vị hoặc mã chuyển vị (classical
transposition or permutation ciphers)
˗ Thực hiện xáo trộn thứ tự các ký tự trong bản rõ. Do
thứ tự của các ký tự bị mất đi nên người đọc không
thể hiểu được ý nghĩa của bản tin dù các chữ đó
không thay đổi.
˗ Đơn giản nhất của mã hóa kiểu này là mã rail fence
cipher
Nguyễn Thị Hạnh
32
16
07/01/2018
1.2.5 Rail Fence Cipher
˗ Ghi các ký tự trong bản rõ theo từng hàng rào, sau đó
kết xuất bản mã dựa trên cột.
˗ Ví dụ: bản rõ “meet me after the toga party” với hành
rào sắt độ sâu là 2
° Viết bản rõ như sau:
m e m a t r h t g p r y
e t e f e t e o a a t
° Cho bản mã
MEMATRHTGPRYETEFETEOAAT
Nguyễn Thị Hạnh
33
1.2.5 Rail Fence cipher
˗ Để an toàn hơn nữa, có thể áp dụng phương pháp
hoán vị 2 lần (double transposition), tức sau khi hoán
vị lần 1, ta lại lấy kết quả đó hoán vị thêm một lần nữa.
˗ Để phá mã phương pháp hoán vị 2 lần không phải là
chuyện dễ dàng vì rất khó đoán ra được quy luật hoán
vị.
˗ Ngoài ra không thể áp dụng được phương pháp phân
tích tần suất chữ cái giống như phương pháp thay thế
vì tần suất chữ cái của bản rõ và bản mã là giống
nhau.
Nguyễn Thị Hạnh
34
17
07/01/2018
Tóm tắt
˗ Các phương pháp mã hóa cổ điển thường dựa trên
hai phương thức.
1. Dùng phương pháp thay thế một chữ cái trong
bản rõ thành một chữ cái khác trong bản mã
(substitution). Các mã hóa dùng phương thức này
là mã hóa Ceasar, mã hóa thay thế đơn bảng, đa
bảng, one-time pad.
2. Dùng phương pháp hoán vị để thay đổi thứ tự ban
đầu của các chữ cái trong bản rõ (Rail Fence)
Nguyễn Thị Hạnh
35
2. Mã dòng (Stream Block) và Mã
khối (Block Ciphers)
2.1 Khái niệm
2.2 Mã Feistel (Feistel Cipher)
Nguyễn Thị Hạnh
36
18
07/01/2018
2.1 Khái niệm
˗ Mã dòng (stream cipher) là một kỹ thuật mã hóa mà
mã hóa một dòng dữ liệu số một bit hoặc một byte tại
một thời điểm.
˗ Mã khối (block cipher) là một cơ chế mã hóa/giải mã
mà trong đó một khối của bản rõ được xử lý như một
thổng thể và dùng để tạo ra khối bản mã có độ dài
bằng nhau. Thông thường kích cở khổi là 64 hoặc 128
bit được sử dụng.
Nguyễn Thị Hạnh
37
Stream Ciphers và Block Ciphers
Nguyễn Thị Hạnh
38
19
07/01/2018
2.2 Mã Feistel (Feistel Cipher)
˗ Được đề xuất bởi Horst Feistel
˗ Bản rõ sẽ được biến đổi qua một số vòng để cho ra
bản mã cuối cùng
˗ Trong đó bản rõ P và các bản mã Ci được chia thành
nửa trái và nửa phải:
P = (L0, R0) ;Ci = (Li, Ri) i = 1, 2, …n
Nguyễn Thị Hạnh
39
2.2 Mã Feistel (Feistel Cipher)
˗ Quy tắc biến đổi các nửa trái phải này qua các vòng
được thực hiện như sau:
Li = Ri-1 ; Ri = Li-1 F(Ri-1, Ki)
°Ki là một khóa con cho vòng thứ i. Khóa con này
được sinh ra từ khóa K ban đầu theo một thuật toán
sinh khóa con (key schedule): K ‰ K1 ‰ K2 ‰ … ‰
Kn
°F là một hàm mã hóa dùng chung cho tất cả các
vòng. Hàm F đóng vai trò như là phép thay thế còn
việc hoán đổi các nửa trái phải có vai trò hoán vị.
˗ Bản mã C được tính từ kết xuất của vòng cuối cùng:
C = Cn = (Ln, Rn)
Nguyễn Thị Hạnh
40
20
Tải về để xem bản đầy đủ
34 trang
20220
Free
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng An toàn hệ thống thông tin - Chương 2: Symmetric ciphers (Mã hóa đối xứng) - Nguyễn Thị Hạnh", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_an_toan_he_thong_thong_tin_chuong_2_symmetric_ciph.pdf
