Chương 3: Hệ mật mã đối xứng

Chương 3Hệ mật mã đối xứngMột hệ mật mã là một bộ 5 (P,C,K,E,D) thoả mãn các điều kiện sau: P là một tập hợp hữu hạn các bản rõ (PlainText), nó được gọi là không gian bản rõ. C là tập các hữu hạn các bản mã (Crypto), nó còn được gọi là không gian các bản mã. K là tập hữu hạn các khoá hay còn gọi là không gian khoá.E: một ánh xạ KxP vào C, gọi là phép lập mật mã.D: một ánh xạ KxC vào P, gọi là phép giải mã. 3.1. Định nghĩa hệ mãDựa vào cách truyền khóa có thể phân thành:Hệ mã đối xứng: dùng chung một khóa cho quá trình mã hóa và giải mã.Hệ mã bất đối xứng: khóa mã hóa và giải mã khác nhau.Ngoài ra còn có: hệ mã cổ điển, hệ mã hiện đại, mã dòng, mã khối. Phân loại hệ mật mãĐể đánh giá hệ mật mã người ta thường đánh giá thông qua các chính sách sau:Độ an toàn: an toàn tính toánChỉ dựa vào khóa, công khai thuật toánBản mã C không có điểm chú ý, gây nghi ngờe(K)=C, d(M)=P. khi không biết dk thì không có khả năng tìm M từ C.Tốc độ mã và giải mãPhân phối khóaTiêu chuẩn đánh giá hệ mãMô hình mã hóa đối xứngKhóa phải giữ bí mật giữa người gởi và người nhận, hay nói cách khác phải có kênh chuyển khóa an toàn.Tính an toàn hệ mã đối xứng: được gọi là an toàn khi không thể phá mã (lý tưởng) hoặc thời gian phá mã là bất khả thi.Đặc điểm hệ mã đối xứngHàm lập mã của mã Ceasar được định nghĩa như sau: Hàm giải mã của mã Ceasar được định nghĩa như sau:3.2. Mã CeasarMã CeasarBảng tương ứng giữa chữ cái và các số dư theo modulo 26.Mã Ceasar(tt)ABCDEFGHIJKLM0123456789101112NOPQRSTUVWXYZ13141516171819202122232425Cho bản rỏ(plaintext): wewillmeetatmidnightDãy số tương ứng là:22 4 22 8 11 11 12 4 4 19 0 19 12 8 3 13 8 6 7 19Nếu mã hóa với k=11 thì bản mã là:7 15 7 19 22 22 23 15 15 4 11 4 23 19 14 24 19 17 18 4 Bản mã cuối cùng có dạng: HPHTWWXPPELEXTOYTRSEVí dụDễ sử dụngThám mã cùng khá dễ dàng.Số khóa cần thử là 25Giải thuật mã hóa và giải mã đã biếtNgôn ngữ plaintext đã biết và dễ đoán.không an toànNhận xét3.3. Mã thay thế đơn bảng (Monoalphabetic Substitution Cipher)Với phép hoán vị  cho bảng sau:Với hệ mật mã thay thế khóa :Bản rỏ: hengapnhauvaochieuthubayBản mã: ghsoxlsgxuexfygzhumgunxdVí dụSố hoán vị khóa: 26!Thám mã bằng duyệt tất cả các khóa không thực tế(26!≈4.1026 ≈6.4x1012 năm).Một phương pháp thám mã dựa vào tần suất xuất hiện của các chữ cái có thể đoán được bản rõ từ bản mã.không được coi là an toànNhận xétKhông gian khóa là các cặp số (a, b)∈Z262 với gcd(a,b)=1.Không gian khóa sẽ có: ∅(26)*26=12*26=312Hàm lập mã:Hàm giải mã:Mã affine(nhân và cộng)Bản rỏ: hengapnhauchieuthubayDãy số tương ứng:Mã hóa với khóa k=(5,6) ta được bản mã:patkgdtpgchgyqpuacxpclgwVí dụMã HillLà mã nhiều ký tựÝ tưởng chính: dùng m ký tự bản rỏ kế tiếp nhau và thay thế m ký tự bản mã. Việc thay thế này được xác định bởi m phương trình tuyến tính, mỗi ký tự được gán cho 1 giá trị số.khóa là ma trận cấp mxm.3.4 Mã thay thế đa ký tựMã Hill được định nghĩa như sau:Mã Hill(tt)Cách tính ma trận nghịch đảoTriển khai theo dòng pHoặc:Triển khai theo cột qVới:Bỏ dòng I, cột jVới m=2, k=Bản rỏ july(9, 20), (11, 24)Bản mã: ek (x1,,xm)=(x1,,xm)*k mod 26Bản mã: DELWVí dụK=Tính det(k)=11*7-8*3=1(mod 26)Tính ma trận nghịch đảodk (y1, ,ym)=(y1,,ym)*k-1 mod 26Giải mãNếu chỉ biết bản mã thì việc thám mã khó khăn.Nếu biết bản rỏ dưới dạng m cặp phân biệt khác nhau của bản rỏ và bản mã.Xj=(xj1,xj2,,xjm)(j=1m)Yj=(yj1,,yjm)Ma trận khóa kmxm có thể được tính từ ma trận x,yK=x-1 *y(x khả đảo)Nếu x không khả đảo thì cố tìm m cặp bản rỏ khácNhận xétThực hiện trên từng bộ m ký tự3.5 Mã thay thế đa bảng vigenereVới m=6, k=(2, 8, 15, 7, 4, 17)Ví dụĐể mã hóa bản tin cần có khóa có chiều dài bằng bản tin.ứng với một chữ cái trong bản rõ có thể có nhiều chữ cái trong bản mã  phá mã bằng thống kê tần suất không thể thực hiện được.Phá mã đối với mã vigenere dựa trên sự lặp lại của cụm từ để đoán chiều dài khóa, từ đó tách bản mã thành các phần mà mỗi phần được mã hóa bằng PP đơn bảng. Không an toànNhận xétXáo trộn thứ tự các chữ cái trong bản rõ để được bản mã.Có thể thực hiện hoán vị nhiều lần để tăng sự phức tạp cho việc phân tích mã.3.6 Mã hoán vịBản rõ được chia thành các đơn vị mã hóa k bit: P p0p1p2.. Pn-1 (pi: k bit)Một bộ sinh số ngẫn nhiên từ khóa K ban đầu có kích thước bằng đơn vị mã hóa: StreamCipher(K) S= s0s1s2 sn-1 (si : k bit)Mỗi số ngẫn ngiên xor với đơi vị mã hóa của bản rõ để được bản mã. Quá trình giả mã được thực hiện ngược lại3.7 Mã dòng (stream cipher)Mô hình mã dòngTương tự như mã Vigenere hay mã One-time Pad.Điểm quan trọng nhất của mã dòng là bộ sinh khóa ngẫn nhiên. Nếu chọn khóa ngăn thì không đảm bảo an toàn, nếu khóa dài thì không thực tế. Do đó, bộ sinh số ngẫn nhiên phải cân bằng điểm này.Nhận xétDùng trong mạng điện thoại GMS đảm bảo bảo mật trong quá trình liên lạc giữa ĐT và trạm thu phát vô tuyến.Đơn vị mã hóa: 1bitBộ sinh số: 0 hoặc 1 để sử dụng trong phép xor.Mã A5/1Bộ sinh số gồm 3 thanh X(6 bit), Y(8 bit), Z(9 bit), khóa có chiều dài 23 bit được phân bố vào thanh ghi: KXYZ.Các thanh ghi được biến đỗi qua qui tắc sau: Ví dụ: x=100101, t=1 x= 110010Tiny A5/1Ta định nghĩa hàm “chiếm đa số” như sau: maj(x1, y3, z3) =0 nếu có hai bit 0, ngược lai.Tại bước sinh số thứ i, Bit si được XOR với bit thứ i trong bản rõ để có được bit thứ i trong bản mã.Ví dụ: P=111, khóa: 100101. 01001110.100110000A5/1Mã dòng A5/1Dùng trong giao thức SSL để bảo mật dữ liệu trong quá trình truyền tải giữa Web Server và trình duyệt webDùng trong mã hóa WEP của mạng Wireless LAN.Mã RC4Đơn vị mã hóa: 3bitDùng 2 mảng S và T, mỗi mảng 8 số nguyên 3bit (từ 0 đến 7).Khóa là một dãy N số 3bit (N từ 1 đến 7).Bộ sinh số: mỗi lần sinh ra 3bit để sử dụng trong phép XOR.Tiny RC4Giai đoạn khởi tạoTiny RC4 (tt)Dựa trên phần tử khóa, các phần tử của S được hoán vị lẫn nhau với mức độ ngẫu nhiên nào đóVí dụ: mã hóa bản rõ: P= 001000110, K={2, 1, 3}Tiny RC4 (tt)Khi i=7 ta được S= 6 0 7 1 2 3 5 4Giai đoạn sinh sốTiny RC4 (tt)Các phần tử S tiếp tục được hoán vị. Tại mỗi bước sinh số hai phần tử của S được chọn để tính ra số k 3bit là số được dùng để XOR với đơn vị mã hóa của bản rõ.Tiny RC4 (tt). Xét ví dụ trướcVậy bản mã C= 001.000.110 ⊕101.001.111 = 100.001.001 (từ EBB)Tượng tự như Tiny RC4 với các đặc tính sau: Đơn vị mã hóa: 1byte Mảng S và T gồm 256 số 8bit Khóa K là một dãy số nguyên 8bit từ 1256. Bộ sinh số mỗi lần sinh 1byte để sử dụng trong phép XOR. RC4Quá trình sinh số trong RC4 là ngẫu nhiên, khó đoán trước nên đạt được độ bảo mật cao theo tinh thần của mã One-Time Pad.Mã RC4 hoàn toàn thực hiện được trên số nguyên 1byte, tốc độ xử lý nhanh hơn mã khốiPhép toán XOR có hạn chế là chỉ cần biết cặp khối bản rõ và bản mã, người ta có thể dễ dàng suy ra khóa và dùng khóa để giải các khối mã khác. ví dụ:Nếu c=1010, p=1111 thì k= 01013.8 Mã khốiĐể chống phá mã trong trường hợp known-plaintext hay choosen-plaintext, chỉ có thể làm cho p và c không có mối liên hệ toán học- Lập bảng tra cứu ngẫn nhiên bản rõ-bản mã.Muốn phá mã cần biết tất cả các cặp bản rõ-bản mã.Nếu chọn khối có kích thước 64bit thì số dòng bảng khóa là 264  không thể nắm hết bảng khóa đối với người phá mã.mã khối an toàn lý tưởngMã khối an toàn lý tưởngTrong thực tế ko thể xd mã khối an toàn tuyệt đối.Dùng khóa có kích thước ngắn + kết hợp nhiều mã hóa đơn giản (phép thế, phép hoán vị)  an toàn sắp xỉ mã khối lý tưởng.Mạng SPNViệc kết hợp các hàm S-box và P-box tạo hai đặc tính quan trọng là: tính khuếch tán và tính gây nhiễu.Tính khuếch tán: 1bit bản rõ là ảnh hưởng đến tất cả các bít bản mã (S-box, P-box).Tính gây nhiễu: là phức tạp hóa mối liên quan giữa bản mã và khóa (S-box).Mạng SPN (tt)Do Horst Feistel đề xuất: kết hợp phép thế và hoán vị.Bản rõ được biết đổi qua một số vòng để cho ra bản mã cuối cùng.Bản rõ P và bản mã C được chia thành hai nữa Li và Ri Khóa ki được sinh ra theo thuật toán sinh khóa conF là hàm mã hóa dùng chung cho tất cả các vòng, F đóng vai trò như phép thay thế, còn việc hoán đổi các nữa trái phải có vai trò như hoán vị.Mô hình mã hóa FeistelMô hình mã hóa FeistelTiền thân là mã Lucifer của IBMLà mã thuộc hệ mã Feistel 3 vòngKích thước khối là 8bitKích thước khóa 8bitMỗi vòng dùng khoa con 6bitMã Tiny DESCác vòng Tiny DESCấu trúc 1 vòng của Tiny DESKhóa K 8 bít ban đầu được chia thành 2 nửa trái phải KL0 và KR0, mỗi nửa có kích thước 4 bít. Tại vòng thứ nhất KL0 và KR0 được dịch vòng trái 1 bít để có được KL1 và KR1. Tại vòng thứ hai KL1 và KR1 được dịch vòng trái 2 bít để có được KL2 và KR2. Tại vòng tại vòng thứ 3 KL2 và KR2 được dịch vòng trái 1 bít để có KL3 và KR3. Cuối cùng khóa Ki của mỗi vòng được tạo ra bằng cách hoán vị và nén (compress) 8 bít của KLi và KRi (k0k1k2k3k4k5k6k7) thành kết quả gồm 6 bít : k5k1k3k2k7k0. Thuật toán sinh khóa conTấn công vét cạn khóa: vì khóa DES có độ dài 56bit, nên để tấn công vét cạn khóa cần kiểm tra 256 khóa khác nhau.Phá mã DES theo PP vi sai: đòi hỏi 247 cặp bản rõ, bản mã lựa chọn bất khả thi.Phá mã theo PP thử tuyến tính: cần biết trước 243 cặp bản rõ-bản mã không khả thi.Độ an toàn của DESSử dụng DES nhiều lần với khóa khác nhau. C=E(D(E(P, K1), K2) K1)Khi K1 = K2 =K thì Triple suy diễn thành DES. Triple DESLà thuật toán mã hóa RijndaelKích thước khối mã 128, 192 hoặc 256 bitCho phép lựa chọn kích thước khóa độc lập với kích thước khối: 128, 192 hay 256 bit.Số vòng có thể thay đổi từ 10 đến 14 vòng tùy thuộc vào kích thước khóa.Advanced Encryption Standard (AES) Mã hóa đối xứng thực hiện tính bảo mật.Đối với tính chứng thực thì sao? Mã hóa đối xứng có thể chống lại tấn công sửa đổi thông điệp, mạo danh hay phát lại thông điệp hay không? ??? Có, giải thíchTính chứng thực của mã hóa đối xứng (authentication)Mã hóa đối xứng đảm bảo tính bảo mật nhưng không đảm bảo tính không từ chối.Nguyên nhân: khóa bí mật KNếu K bị tiết lộ thì không thể qui trách nhiệm cho ai.Tính không từ chối (non-repudiation) của mã hóa đối xứngGiả sử có N người dùng, trao đổi dữ liệu bằng mã hóa đối xứng  cần N(N-1)/2 khóa bí mật.Trao đổi khóa bí mật bằng TTPP khóaMỗi người dùng chỉ cần 1 khóa bí mật với KDC, còn khóa để trao đổi dữ liệu với người dùng do KDC cung cấp.Key Distribution Center – KDCKey Distribution Center – KDCTrao đổi khóa bí mật dùng KDCQ&A