Mật mã hóa dữ liệu

Chia sẻ: Teo Em | Ngày: | Loại File: PDF | Số trang:30

Thêm vào BST

Báo xấu

202
lượt xem 60
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Cho tới nay, việc mật mã hoá (encryption) dữ liệu là một phương pháp đủ mạnh để bảo vệ những dữ liệu quan trọng hoặc riêng tư không bị xâm phạm bởi sự soi mói tọc mạch hay dụng tâm có ác ý. Tuy nhiên, các phương tiện truyền thông trên thế giới tường thuật khá nhiều về khả năng để rò rỉ những dữ liệu cá nhân của khách hàng như mã số bảo hiểm xã hội, thông tin thẻ tín dụng... ...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Mật mã hóa dữ liệu

2. Mật mã cổ điển a. Các hệ mật thay thế đơn giản b. Các hệ mật mã thay thế đa biểu c. Mật mã hoán vị. d. Các hệ mật mã tích e. Chuẩn mã dữ liệu (DES) Mật mã hoá dữ liệu f. Chuẩn mã dữ liệu tiên tiến (AES) PTIT Lê Thị Thanh Giáo viên Lê Thị Thanh Page 2 1. Giới thiệu Định nghĩa • A cryptosystem is a five-tuple (P,C,K,E, D) where the following conditions are satisfied: Oscar Oscar - 1. P is a finite set of possible plaintexts - 2. C is a finite set of possible ciphertexts Alice Encrypter Decrypter Bob Alice Encrypter Decrypter Bob - 3. K, the keyspace, is a finite set of possible keys - 4. For each K, there is an encryption rule eK Є E. Secure and a corresponding decryption rule dK Є D. Each Secure channel channel eK: P→ C and dK: C→P are functions such that dK(eK(x)) = x for every plaintext Key source Key source Giáo viên Lê Thị Thanh Giáo viên Lê Thị Thanh Page 3 Page 4 1
i. Mật mã dịch vòng a. Mật mã thay thế đơn giản i. Mật mã dịch vòng • Giả sử: P = C = K = Z26 với 0 ≤ k ≤ 25 • ek = x + k mod 26 ii. Mật mã thay thế • dk = y – k mod 26 • x, y ∈ Z26 Ký tự A B C D E F G H I J K L M Mã tương ứng 0 1 2 3 4 5 6 7 8 9 10 11 12 Ký tự N O P Q R S T U V W X Y Z Mã tương ứng 13 14 15 16 17 18 19 20 21 22 23 24 25 Giáo viên Lê Thị Thanh Giáo viên Lê Thị Thanh Page 5 Page 6 ii. Mật mã thay thế ii. Mật mã thay thế • P = C = Z26 và k chứa mọi hoán vị có thể có của 26 • Như vậy eп(a) = X; eп(b) = N, ... ký tự từ 0 tới 25. Với mỗi hoán vị п ∈ K, ta định • Hàm giải mã là phép hoán vị ngược. Điều này thực nghĩa: eп(x) = п(x) và dп(y) = п-1(y) trong đó п-1 là hiện bằng cách viết hàng thứ hai lên trước rồi sắp hoán vị ngược của п xếp theo thứ tự chữ cái. Ký tự bản rõ a b c d e f g h i j k l m Ký tự bản mã A B C D E F G H I J K L M Ký tự bản mã X N Y A H P O G Z Q W B T Ký tự bản rõ d l r y v o h e z x w p t Ký tự bản rõ n o p q r s t u v w x y z Ký tự bản mã N O P Q R S T U V W X Y Z Ký tự mã S F L R C V M U E K J D I Ký tự mã b g f j q n m u s k a c i Giáo viên Lê Thị Thanh Giáo viên Lê Thị Thanh Page 7 Page 8 2
b. Polyalphabetic cipher Polyalphabetic Cipher • The most common method used is Vigenère cipher • MDV và MTT là các loại mật mã thay thế đơn ký tự. • Vigenère cipher starts with a 26 x 26 matrix of • Vigenère là một loại mật mã thay thế đa ký tự. alphabets in sequence. First row starts with ‘A’, • Sử dụng phép thay thế tương ứng: A ↔ 0, B ↔ 1, ..., second row starts with ‘B’, etc. • Z ↔ 25. Like the ADFGVX cipher, this cipher also requires a keyword that the sender and receiver know ahead of • Khoá k = CIPHER ↔ (2, 8, 15, 7, 4, 17) time • Các phép cộng được thực hiện theo modulo 26 • Each character of the message is combined with the characters of the keyword to find the ciphertext character Bản rõ 12 4 4 19 12 4 0 19 18 20 13 18 4 19 Khoá 2 8 15 7 4 17 2 8 15 7 4 17 2 8 Bản mã 14 12 19 0 16 21 2 1 7 1 17 9 6 1 Giáo viên Lê Thị Thanh Giáo viên Lê Thị Thanh Page 9 Page 10 Vigenère Cipher Table Vigenère Cipher Table (cont’d) ABCDEFGHIJKLMNOPQRSTUVWXYZ ABCDEFGHIJKLMNOPQRSTUVWXYZ A ABCDEFGHIJKLMNOPQRSTUVWXYZ N NOPQRSTUVWXYZABCDEFGHIJKLM B BCDEFGHIJKLMNOPQRSTUVWXYAB O OPQRSTUVWXYZABCDEFGHIJKLMN P PQRSTUVWXYZABCDEFGHIJKLMNO C CDEFGHIJKLMNOPQRSTUVWXYZAB Q QRSTUVWXYZABCDEFGHIJKLMNOP D DEFGHIJKLMNOPQRSTUVWXYZABC R RSTUVWXYZABCDEFGHIJKLMNOPQ E EFGHIJKLMNOPQRSTUVWXYZABCD S STUVWXYZABCDEFGHIJKLMNOPQR F FGHIJKLMNOPQRSTUVWXYZABCDE T TUVWXYZABCDEFGHIJKLMNOPQRS G GHIJKLMNOPQRSTUVWXYZABCDEF U UVWXYZABCDEFGHIJKLMNOPQRST H HIJKLMNOPQRSTUVWXYZABCDEFG V VWXYZABCDEFGHIJKLMNOPQRSTU I IJKLMNOPQRSTUVWXYZABCDEFGH W WXYZABCDEFGHIJKLMNOPQRSTUV J JKLMNOPQRSTUVWXYZABCDEFGHI X XYZABCDEFGHIJKLMNOPQRSTUVW K KLMNOPQRSTUVWXYZABCDEFGHIJ Y YZABCDEFGHIJKLMNOPQRSTUVWX L L MLêN ịO P Q R S T U V W X Y Z A B C D E F G H I J K Z Z ALêB ịChanh E F G H I J K L M N O P Q R S T U V W X Y Th T D Giáo viên Th Thanh Giáo viên Page 11 Page 12 OQS C G 3
Polyalphabetic Cipher Polyalphabetic Cipher • To decrypt, the receiver places the keyword • E.g., Message = SEE ME IN MALL characters below each ciphertext character • Take keyword as INFOSEC • Using the table, choose the row • Vigenère cipher works as follows: corresponding to the keyword character and SEEME I NMALL look for the ciphertext character in that row • I NFOSEC I NFO Plaintext character is then at the top of that column ------------------------------------- A RJ AWMPUNQZ Giáo viên Lê Thị Thanh Giáo viên Lê Thị Thanh Page 13 Page 14 Polyalphabetic Cipher Vigenère Cipher • Decryption of ciphertext: • Easiest way to handle Vigenère cipher is to use arithmetic modulo 26 A RJ AWMPUNQZ • This approach dispenses with the need for I NFO S EC I NFO the table ------------------------------------- • Keyword is converted to numbers and S E EMEIN MALL corresponding numbers in message and • Best feature is that same plaintext character keyword are added modulo 26 is substituted by different ciphertext • “thiscryptosystemisnotsecure. “ characters (i.e., polyalphabetic) Giáo viên Lê Thị Thanh Giáo viên Lê Thị Thanh Page 15 Page 16 4
Mã Affine Mã Affine • Phương trình này chỉ có một nghiệm duy • Một trường hợp đặc biệt của mật mã thay thế nhất đối với mỗi y khi và chỉ khi gcd(a,26) = là mật mã Affine Cipher,bản rõ và bản mã là 1. e(x) ≡ ax + b mod 26 (a,b € Z26). • Định lý 3.2: đồng dư thức ax ≡ b mod m chỉ • Các hàm này gọi là hàm Affine có một nghiệm duy nhất x € Zm với mọi b € • Để có thể giải mã: hàm Affine phải đơn ánh Zm khi và chỉ khi gcd(a,m) = 1 • • Tức là đồng nhất thức: ax + b ≡ y mod 26 Định nghĩa3.4: giả sử a ≥ 1 và m ≥ 2 là các phải có nghiệm duy nhất. Vì y thay đổi trên số nguyên. gcd(a,m) = 1 thì ta nói a và m là các số nguyên tố cùng nhau. Số các số Z26 nên y-b cung thay đổi trên Z26. Do vậy, chỉ nguyên trong Zm nguyên tố cùng nhau với m cần xét phương trình: ax ≡ y mod 26 thường được ký hiệu là φ(m)–hàm phi Euler Giáo viên Lê Thị Thanh Giáo viên Lê Thị Thanh Page 17 Page 18 Mã Affine Mã Affine • Xét phương trình đồng dư y ≡ ax + b mod 26 • Định nghĩa 3.5: giả sử a € Zm. Phần tử nghịch • Phương trình tương đương: ax ≡ y –b mod26 đảo (theo phép nhân) của a là phần tử a-1 € • Vì gcd(a,26) = 1 nên a có nghịch đảo theo Zm sao cho a. a-1 = a-1.a = 1 mod m. modulo 26. • Định lý 3.3: giả sử n • m = ∏ piei a-1(ax) ≡ a-1(y-b)(mod 26) • Áp dụng tính kết hợp của phép nhân modulo: i =1 • Trong đó các số nguyên pi khác nhau và ei>0, • a-1(ax) = (a-1a)x = 1.x 1≤ i ≤ n, khi đó: • → x ≡ a-1(y-b)(mod 26) ϕ (m) = ∏ ( pie − pie −1 ) • Như vậy hàm giải mã là: d(y) ≡ a-1(y-b)mod i i 26 i =1 Giáo viên Lê Thị Thanh Giáo viên Lê Thị Thanh Page 19 Page 20 5
Mã Affine Mã Affine • Xét phương trình đồng dư y ≡ ax + b mod 26 • Ví dụ: giả sử k = (7,3) → 7-1 mod 26 = 15 • Phương trình tương đương: ax ≡ y –b mod26 • Hàm mã hoá là: ek(x) ≡ 7x + 3 • Vì gcd(a,26) = 1 nên a có nghịch đảo theo • Và hàm giải mã tương ứng là: modulo 26. • a-1(ax) ≡ a-1(y-b)(mod 26) dk(x) = 15(y-3) = 15y – 19 • • Áp dụng tính kết hợp của phép nhân modulo: dk(ek(x)) = x với mọi x є Z26 ? • a-1(ax) = (a-1a)x = 1.x • dk(ek(x)) = dk(7x + 3) • → x ≡ a-1(y-b)(mod 26) • = 15(7x + 3) – 19 = x + 45 – 19 = x • Như vậy hàm giải mã là: d(y) ≡ a-1(y-b)mod 26 Giáo viên Lê Thị Thanh Giáo viên Lê Thị Thanh Page 21 Page 22 Phân tích mật mã Affine Phân tích mật mã Affine • Các số khả nghịch • Số thứ tự bảng chữ cái Anh ngữ - 15 có 15-1 = 7 trong Z26 - 17 có 17-1 = 23 - 1 có 1-1 = 1 - 19 có 19-1 = 11 0 1 2 3 4 5 6 7 8 9 10 11 12 - 3 có 3-1 = 9 - 21 có 21-1 = 5 ABCDEFGHI JKLM - 5 có 5-1 = 21 - 23 có 23-1 = 17 13 14 15 16 17 18 19 20 21 22 23 24 25 - 7 có 7-1 = 15 NOPQRSTUVWXYZ - 25 có 25-1 = 25 - 9 có 9-1 = 3 - 11 có 11-1 = 19 Giáo viên Lê Thị Thanh Giáo viên Lê Thị Thanh Page 23 Page 24 6
Giải thuật phân tích mã Affine Ví dụ • Thống kê xác suất xuất hiện của các ký tự • Phân tích chuỗi mã: • Tìm ký tự xuất hiện nhiều nhất, thử với suy • FMXVEDKAPHFERBNDKRXRSREFMORUD đoán nó là e (trong Anh ngữ). SDKDVSHVUFEDKAPRKDLYEVLRHHRH • Tìm ký tự xuất hiện nhiều kế tiếp, thử với suy đoán nó là t (trong Anh ngữ). • Giải cặp phương trình trên để tìm a, b với UCLN của a và 26 phải không lớn hơn 1. • Với cặp a, b tìm được kiểm chứng xem bản rõ dịch được có nghĩa hay không. Giáo viên Lê Thị Thanh Giáo viên Lê Thị Thanh Page 25 Page 26 Bảng xác suất xuất hiện Các tần số chữ cái tiếng Anh Letter Frequency Letter Frequency A 2 N 1 B 1 O 1 C 0 P 2 Tần số tương đối (%) D 7 Q 0 E 5 R 8 F 4 S 3 G 0 T 0 H 5 U 2 I 0 V 4 J 0 W 0 K 5 X 2 L 2 Y 1 M 2 Z 0 Giáo viên Lê Thị Thanh Giáo viên Lê Thị Thanh Page 27 Page 28 7
Phép thử 1 • Chữ E thành chữ R: 4a + b = 17 (mod 26)(1) • Chữ T thành chữ D: 19a + b = 3 (mod 26)(2) • Trừ theo vế (2) cho (1): 15a = -14 (mod 26) • Hay a = (-14)15-1 = (-14)7 = 12.7 = 84 = 6 (mod 26). • UCLN(a,m) = UCLN(6,26) = 2 không hợp lệ Giáo viên Lê Thị Thanh Giáo viên Lê Thị Thanh Page 29 Page 30 Phép thử 2 Phép thử 3 • • Chữ E thành chữ R: 4a + b = 17 (mod 26)(1) Chữ E thành chữ R: 4a + b = 17 (mod 26)(1) • • Chữ T thành chữ E: 19a + b = 4 (mod 26)(2) Chữ T thành chữ H: 19a + b = 7 (mod 26)(2) • • Trừ theo vế (2) cho (1): 15a = -13 (mod 26) Trừ theo vế (2) cho (1): 15a = -10 (mod 26) • • Hay a = (-13)15-1 = (-13)7 = 13.7 = 91 = 13 Hay a = (-10)15-1 = (-10)7 = -70 = 8 (mod 26). (mod 26). • UCLN(a,m) = UCLN(13,26) = 2 không hợp lệ • UCLN(a,m) = UCLN(13,26) = 13 không hợp lệ Giáo viên Lê Thị Thanh Giáo viên Lê Thị Thanh Page 31 Page 32 8
Phép thử 4 Phép thử 4 • • Vậy mã hoá: y = 3x + 5 (mod 26) Chữ E thành chữ R: 4a + b = 17 (mod 26)(1) • • Suy ra: 3x = y – 5 (mod 26) Chữ T thành chữ K: 19a + b = 10 (mod 26)(2) • • x = (y – 5)3-1 = (y – 5)9 = 9y – 45 = 9y + 7 Trừ theo vế (2) cho (1): 15a = -7 (mod 26) (mod 26) • Hay a = (-7)15-1 = (-7)7 = -49 = 3 (mod 26). • Giải mã: • UCLN(a,m) = UCLN(13,26) = 1 là hợp lệ • ALGORITHMSAREQUITEGENERALDEFINI • Thế a = 3 vào (1) ta được b = 5. TIONSOFARITHMETICPROCESSES • Đọc là: algorithms are quite general definitions of arithmetic processes Giáo viên Lê Thị Thanh Giáo viên Lê Thị Thanh Page 33 Page 34 c. Mật mã hoán vị c. Mật mã hoán vị • Khi đó phép hoán vị ngược sẽ là: • Ý tưởng của mã hoán vị là giữ các ký tự của bản rõ nhưng không thay đổi nhưng sẽ thay 1 2 3 4 5 6 đổi vị trí của chúng bằng cách sắp xếp lại các 3 6 1 5 2 4 ký tự này. • Giả sử ta có bản rõ: asecondclasscarriageonthetrain • Ví dụ: giả sử m = 6 và khoá là phép hoán vị → asecon|dclass|carria|geonth|etrain sau: • Mỗi nhóm 6 chữ cái lại được sắp xếp theo phép hoán vị п, ta có 1 2 3 4 5 6 EOANCS|LSDSAC|RICARA|OTGHNE|RIENAT • Cuối cùng có bảng mã sau 3 5 1 6 4 2 EOANCSLSDSACRICARAOTGHNERIENAT Giáo viên Lê Thị Thanh Giáo viên Lê Thị Thanh Page 35 Page 36 9
c. Mật mã hoán vị – định nghĩa Ví dụ mật mã hoán vị • Cho m là một số nguyên dương xác định nào đó. • P = C = (Z26)m và cho K là tất cả mọi hoán vị có thể có của { 1,2,..., m }. • Đối với một khoá π (tức là một phép hoán vị nào đó), ta xác định: • eπ = (x1, ..., xm) = (xπ(1), ..., xπ(m)) • dπ = (x1, ..., xm) = (yπ-1(1), ..., yπ-1(m)) Giáo viên Lê Thị Thanh Giáo viên Lê Thị Thanh Page 37 Page 38 Ví dụ: Mật mã Hill • Mã hoá và giải mã theo mật mã hoán vị bản • Do Lester S.Hill đưa ra năm 1929 tin: “Hello my dear” theo khóa K trong sơ đồ • Giả sử m là một số nguyên dương, đặt P=C=(Z26)m • ý tưởng: lấy m tổ hợp tuyến tính của m ký tự trong một phần tử của bản rõ để tạo ra m ký tự ở một phần tử của bản mã. • Ví dụ: m = 2 ta có thể viết một phần tử của bản rõ là: x = (x1, x2) và một phần tử của bản mã là y = (y1, y2). Giáo viên Lê Thị Thanh Giáo viên Lê Thị Thanh Page 39 Page 40 10
Mật mã Hill Mật mã Hill • Ở đây y1, y2 đều là một • Khoá K: ma trận kích tổ hợp tuyến tính của thước m x m x1, x2: ⎡ k11 k12 ... k1m ⎤ - y1=11 x1+ 3 x2 ⎢k k ... k ⎥ - y2= 8 x1+ 7 x2 ( y1 ... ym ) = (x1 ... xm )⎢ 21 22 2m ⎥ • Hoặc: ⎢M M⎥ M ⎢ ⎥ ⎡11 8 ⎤ (y ) y2 = ( x1 x2 )⎢ ⎣km1 km2 ... kmm⎦ ⎥ 1 ⎣ 3 7⎦ Giáo viên Lê Thị Thanh Giáo viên Lê Thị Thanh Page 41 Page 42 Mật mã Hill Mật mã Hill • Vấn đề là làm sao để tính x từ y? • Giả sử cần mã hoá bản rõ “July”. Ta có hai phần tử của bản rõ là: (9,20) (ứng với Ju) và (11,24) ứng với • Dùng ma trận nghịch đảo: x =yk-1 ly • Ví dụ: giả sử khoá ⎛11 8 ⎞ k =⎜ ⎟ ⎜3 7⎟ ⎛11 8 ⎞ (9 20 )⎜ ⎜ 3 7 ⎟ = (99 + 60 72 + 140 ) = (3 4 ) ⎝ ⎠ ⎟ • Ma trận nghịch đảo: ⎝ ⎠ ⎛ 7 18⎞ k −1 = ⎜ ⎜ 23 11⎟ ⎟ ⎝ ⎠ ⎛11 8 ⎞ (11 24)⎜ ⎜ 3 7 ⎟ = (121+ 72 88 + 168) = (11 22) ⎟ ⎝ ⎠ Giáo viên Lê Thị Thanh Giáo viên Lê Thị Thanh Page 43 Page 44 11
Mật mã Hill d. Các hệ mật mã tích • Do vậy bản mã của July là DELW. Để giải mã • Xét C = P, S1 = (P, P, K1, E1, D1), S2 = (P, Bob sẽ tính: P, K2, E2, D2) là hai hệ mật tự đồng cấu có cùng không gian bản mã và bản rõ • (3 4).k-1= (9 20) • S1 X S2 = (P, P, K1 X K2, E, D) • Và (11 22) k-1= (11 24) • Khoá của hệ mật tích có dạng k = (k1, k2) với Lưu ý rằng các phép toán được thực hiện trên k1є K1 và k2є K2. Z26 • Quy tắc mã hoá: Với mỗi k = (k1, k2) ta có một quy tắc mã ek xác định theo công thức: e(k1,k2) (x) = ek2(ek1(x) Giáo viên Lê Thị Thanh Giáo viên Lê Thị Thanh Page 45 Page 46 d. Các hệ mật mã tích d. Các hệ mật mã tích • Quy tắc giải mã: d(k1,k2) (y) = dk1(dk2(y) • Các hệ mật mã đều có các phân bố xác xuất ứng với các không gian khoá của chúng. • Trước tiên mã hoá x bằng ek1 rồi mã lại bản • kết quả bằng ek2. Quá trình giải mã thực hiện Chọn k1 có phân bố xác xuất p(k1) rồi chọn tương tự nhưng theo thứ tự ngược lại. một cách độc lập k2 có phân bố xác xuất p(k2) • • d(k1,k2)(e(k1,k2) (x)) = d(k1,k2)(ek2(ek1(x))) P(k1,k2) = p(k1). p(k2) = dk1(dk2(ek2(ek1(x)))) = dk1(ek1(x)) =x Giáo viên Lê Thị Thanh Giáo viên Lê Thị Thanh Page 47 Page 48 12
d. Các hệ mật mã dòng d. Các hệ mật mã dòng • Trong các hệ mật mã nghiên cứu ở trên, các • Trong các hệ mật mã nghiên cứu ở trên, các phần tử liên tiếp của bản rõ đều được mã phần tử liên tiếp của bản tin đều được mã hóa bằng cùng một khoá k. Chuỗi ký tự mã hóa bằng cùng một khoá k. Chuỗi ký tự mã hoá nhận được có dạng: hoá nhận được có dạng: • • y = y1y2...=ek(x1). ek(x2)... y = y1y2...=ek(x1). ek(x2)... • • Các hệ mật thuộc dạng này thường được gọi Các hệ mật thuộc dạng này thường được gọi là các mã khối. là các mã khối. • Một ý tưởng khác là tạo ra một dòng khoá z = z1z2... để mã hoá một chuỗi ký tự x = x1x2... Giáo viên Lê Thị Thanh Giáo viên Lê Thị Thanh Page 49 Page 50 d. Các hệ thống mật mã dòng d. Các hệ thống mật mã dòng • Một ý tưởng khác là tạo ra một dòng khoá z = • Việc giải mã chuỗi y1,y2 có thể được thực z1z2... để mã hoá một chuỗi ký tự x = x1x2... hiện bằng cách tính liên tiếp z1, x1, z2 ,x2... theo quy tắc: y = y1y2...=ez1(x1). ez2(x2)... • Định nghĩa: mật mã dòng là một bộ (P, C, K, • Hoạt động của mật mã dòng: giả sử k є K L, F, E, D) thoả mãn các điều kiện sau: là khoá và x = x1x2... là chuỗi ký tự mã hoá. - P là một tập hữu hạn các bản tin cần mã hoá. • - C là một tập hữu hạn các bản mã có thể. zi = fi(k, x1,..., xi-1) - K là tập hữu hạn các khoá có thể (hoặc không • zi dùng để mã xi tạo ra yi= eiz(xi). gian khoá) • Do vậy, để mã hoá chuỗi ký tự x1x2... ta phải - L là tập hữu hạn các bộ chữ của dòng khoá. tính liên tiếp z1, y1, z2 ,y2... - F= (f1f2...) là bộ tạo dòng khoá. Với i ≥ 1 Giáo viên Lê Thị Thanh Giáo viên Lê Thị Thanh Page 51 Page 52 13
d. Các hệ thống mật mã dòng e. Chuẩn mã dữ liệu • Định nghĩa (tt): • Vào khoảng 1970, tiến sĩ Horst Feistel đã đặt nền móng đầu tiên cho chuẩn mã hóa dữ liệu - F= (f1f2...) là bộ tạo dòng khoá. Với i ≥ 1 DES với phương pháp mã hóa FeistelCipher. - fi : K x Pi-1 → L • - Với mỗi z є L có một quy tắc mã hoá ez є E và một Vào năm 1976 Cơ quan Bảo mật Quốc gia quy tắc giải mã tương ứng dz є D. ez: P, và dz: C Hoa Kỳ (NSA) đã công nhận DES dựa trên → P là các hàm thoả mãn dz(ez(x)) mọi bản tin x phương pháp Feistel là chuẩn mã hóa dữ liệu thuộc P. [25]. Kích thước khóa của DES ban đầu là Ta có thể coi mã khối là một trường hợp đặc biệt 128 bit nhưng tại bản công bố FIPS kích của mã dòng, trong đó dùng khoá không đổi: thước khóa được rút xuống còn 56 bit. zi = K với mọi i ≥ 1 Giáo viên Lê Thị Thanh Giáo viên Lê Thị Thanh Page 53 Page 54 e. Chuẩn mã dữ liệu e. Chuẩn mã dữ liệu • Kích thước khối văn bản rõ là 64 bit. DES • Giai đoạn 1. Tạo dãy 64 bit 0 x bằng cách thực hiện mã hóa dữ liệu qua 16 vòng lặp mã hoán vị x theo hoán vị IP (Initial Permutation). hóa, mỗi vòng sử dụng một khóa chu kỳ 48 • Biểu diễn x0 =IP(x)=L0R0, L0 gồm 32 bit bên bit được tạo ra từ khóa ban đầu có độ dài 56 trái của x 0, R0 gồm 32 bit bên phải của x0. bit. DES sử dụng 8 bảng hằng số S-box để • Giai đoạn 2: Thực hiện 16 vòng lặp từ 64 bit thao tác. thu được và 56 bit của khoá k (chỉ sử dụng • Biểu diễn thông điệp nguồn n x∈P bằng dãy 48 bit của khoá k trong mỗi vòng lặp). 64bit. Khóa k có 56 bit. Thực hiện mã hóa • 64 bit kết quả thu được qua mỗi vòng lặp sẽ theo ba giai đoạn: là đầu vào cho vòng lặp sau. Giáo viên Lê Thị Thanh Giáo viên Lê Thị Thanh Page 55 Page 56 14
e. Chuẩn mã dữ liệu e. Chuẩn mã dữ liệu • Các cặp từ 32 bit Li, Ri (với i 1≤ i ≤16 ) được • Giai đoạn 3: Áp dụng hoán vị ngược IP−1 đối xác định theo quy tắc sau: với dãy bit R16 L16 , thu được từ y gồm 64 bit. Như vậy, y=IP−1(R16 L16). • Li = Ri-1 • • Ri = Li-1 ⊕ F(Ri-1, Ki) Hàm f được sử dụng ở bước 2 có hai tham • với ⊕ biểu diễn phép toán XOR trên hai dãy số: bit, K1, K2, ..., K16 là các dãy 48 bit phát sinh - Tham số thứ nhất A là một dãy 32 bit, tham số thứ hai J là một dãy 48 bit. Kết quả của hàm f là một từ khóa K cho trước (Trên thực tế, mỗi khóa dãy 32 bit. Các bước xử lý của hàm f (A,J) như Ki được phát sinh sau: • bằng cách hoán vị các bit trong khóa K cho trước). Giáo viên Lê Thị Thanh Giáo viên Lê Thị Thanh Page 57 Page 58 e. Chuẩn mã dữ liệu e. Chuẩn mã dữ liệu • A (32 bit) được mở rộng thành dãy 48 bit bằng hàm mở rộng E, E(A) là một dãy 48 bit được phát sinh từ A bằng cách hoán vị theo một thứ tự nhất định 32 bit của A, trong đó có 16 bit của A được lặp lại hai lần trong E(A). • E(A) ⊕ J = B (48 bit) • Biểu diễn B thành từng nhóm 6 bit như sau: • B = B1B2B3 B4 B5B6 Giáo viên Lê Thị Thanh Giáo viên Lê Thị Thanh Page 59 Page 60 15
Giải thuật DES e. Chuẩn mã dữ liệu • Sử dụng 8 ma trận S1S2 ... S8, kích thước 4x16 • Xét dãy Bj = B1B2B3 B4 B5B6 ; Sj(Bj) = src • r: b1b6 ; c = b2b3 b4 b5 • Cj = Sj(Bj) , 1 ≤ j ≤ 8 • C = C1C2C3 C4 C5C6 C7C8 ; hoán vị P của dãy C cho ta hàm F(A,J) Giáo viên Lê Thị Thanh Giáo viên Lê Thị Thanh Page 61 Page 62 Khả năng phá mã DES 3DES • Khóa 56 bit có 256 = 7,2 x 1016 giá trị có thể • Sử dụng 3 khóa và chạy 3 lần giải thuật DES • Phương pháp vét cạn tỏ ra không thực tế - Mã hóa : C = EK3[DK2[EK1[p]]] - Giải mã : p = DK1[EK2[DK3[C]]] • Tốc độ tính toán cao có thể phá được khóa • Độ dài khóa thực tế là 168 bit - 1997 : 70000 máy tính phá mã DES trong 96 ngày - Không tồn tại K4 = 56 sao cho C = EK4(p) - 1998 : Electronic Frontier Foundation (EFF) phá mã DES • Vì sao 3 lần : tránh “ man-in-the-middle attack " bằng máy chuyên dụng (250000$) trong < 3 ngày - 1999 : 100000 máy tính phá mã trong 22 giờ - C = EK2(EK1(p)) ⇒ X = EK1(p) = DK2(C) • Thực tế DES vẫn được sử dụng không có vấn đề - Nếu biết một cặp (p, C) nhờ các luật an ninh của liên bang. • Mã hóa p với 256 khóa và giải mã C với 256 khóa • • So sánh tìm ra K1 và K2 tương ứng Nếu cần an ninh hơn : 3DES hay chuẩn mới AES • Kiểm tra lại với 1 cặp (p, C) mới; nếu OK thì K1 và K2 là khóa Giáo viên Lê Thị Thanh Giáo viên Lê Thị Thanh Page 63 Page 64 16
f. AES chuẩn mã hoá tiên tiến f. AES – mô tả thuật toán • Advanced encryption standard. • Addround key • Được chấp nhận làm tiêu chuẩn liên bang sau 5 năm tiêu chuẩn hoá bởi NIST • Tác giả: Joan Daemen và Vincent Rijmen • Còn được đặt tên Rijndael • Trên thực tế AES và Rijndael khác nhau. • DES dùng mạng Feistel, Rijndael dùng mạng thay thế – hoán vị Giáo viên Lê Thị Thanh Giáo viên Lê Thị Thanh Page 65 Page 66 f. AES – mô tả thuật toán f. AES – mô tả thuật toán • SubByte • ShiftRows Giáo viên Lê Thị Thanh Giáo viên Lê Thị Thanh Page 67 Page 68 17
f. AES – mô tả thuật toán Chương 3: Mật mã hoá công khai 3.1 Khái niệm về mật mã hoá khoá công khai • MixColumns 3.2 Số học modulo 3.3 Mật mã hoá RSA 3.4 Mật mã hoá Rabin 3.5 Mật mã hoá Diffie – Hellman 3.6 Mật mã hoá Merkle – Hellman 3.7 Mật mã hoá trên đường cong Eliptic 3.8 Mật mã hoá Mc Elice Giáo viên Lê Thị Thanh Giáo viên Lê Thị Thanh Page 69 Page 70 3.1Những khái niệm về mật mã hoá khoá công 3.1 Mã hóa khóa công khai khai • Còn gọi là mật mã hai khóa hay bất đối xứng Các khóa công khai • Các giải thuật khóa công khai sử dụng 2 khóa - Một khóa công khai Ted • Ai cũng có thể biết Joy • Dùng để mã hóa thông báo và thẩm tra chữ ký Alice Mike - Một khóa riêng Khóa công khai Khóa riêng • Chỉ nơi giữ được biết của Alice của Alice • Dùng để giải mã thông báo và ký (tạo ra) chữ ký Bản mã truyền đi • Có tính bất đối xứng - Bên mã hóa không thể giải mã thông báo - Bên thẩm tra không thể tạo chữ ký Bản tin Bản tin Giải thuật Giải thuật gốc gốc giải mã mã hóa Giáo viên Lê Thị Thanh Giáo viên Lê Thị Thanh Page 71 Page 72 18
Mô hình mật mã hoá Hai loại mật mã hoá Giáo viên Lê Thị Thanh Giáo viên Lê Thị Thanh Page 73 Page 74 Mô hình mật mã cổ điển/đối xứng Mô hình mật mã hoá khoá công khai Giáo viên Lê Thị Thanh Giáo viên Lê Thị Thanh Page 75 Page 76 19
3.1 Những khái niệm về mật mã hoá a. Trao đổi khóa công khai • Những hạn chế của mật mã đối xứng Khóa ngẫu nhiên Khóa ngẫu nhiên - Vấn đề phân phối khóa • Khó đảm bảo chia sẻ mà không làm lộ khóa bí mật • Trung tâm phân phối khóa có thể bị tấn công - Không thích hợp cho chữ ký số Alice Bob • Bên nhận có thể làm giả thông báo nói nhận được từ Mã hóa Giải mã bên gửi • Mật mã khóa công khai đề xuất bởi Whitfield Diffie và Martin Hellman vào năm 1976 - Khắc phục những hạn chế của mật mã đối xứng - Có thể coi là bước đột phá quan trọng nhất trong lịch sử của ngành mật mã Khóa công khai của Bob Khóa riêng của Bob - Bổ sung chứ không thay thế mật mã đối xứng Giáo viên Lê Thị Thanh Giáo viên Lê Thị Thanh Page 77 Page 78 3.1.2 Ứng dụng mật mã khóa công khai 3.1.1 Xác thực • Có thể phân ra 3 loại ứng dụng Các khóa công khai - Mã hóa/giải mã • Đảm bảo sự bí mật của thông tin - Chữ ký số Ted Joy • Hỗ trợ xác thực văn bản Bob Mike - Trao đổi khóa Khóa công khai Khóa riêng • Cho phép chia sẻ khóa phiên trong mã hóa đối xứng của Bob của Bob • Một số giải thuật khóa công khai thích hợp cho cả 3 loại Bản mã ứng dụng; một số khác chỉ có thể dùng cho 1 hay 2 loại truyền đi Nguyên bản Nguyên bản Giải thuật Giải thuật đầu ra đầu vào giải mã mã hóa Giáo viên Lê Thị Thanh Giáo viên Lê Thị Thanh Page 79 Page 80 20