CHƯƠNG 3: CÁC HỆ MÃ BÍ MẬT Chương 3: Các hệ mã bí mật 3.1 Một số hệ mã cổ điển Hệ mật mã có khóa đối xứng, tức hệ mật mã mà khóa lập mật mã khóa giải mật mã trùng Thực tế hai khóa (mã hóa, giải mã) khác nhau, trường hợp khóa nhận từ khóa phép tính tốn đơn giản → khóa mật mã chung phải giữ bí mật Chương 3: Các hệ mã bí mật Để mã hóa văn đơn giản sử dụng bảng 26 chữ cái, {A, B, C, …, X, Y, Z}, ta dùng số {0, 1, 2,…, 24, 25} đại diện cho 26 chữ dùng phép toán số học theo modulo 26 để diễn tả phép biến đổi bảng chữ A B C D E F G H I J K L 10 11 12 N O P Q R S T U M V W X Y Z 13 14 15 16 17 18 19 20 21 22 23 24 25 Chương 3: Các hệ mã bí mật 3.1.1 Mã dịch chuyển (Shift Cipher) Mã Ceasar Chương 3: Các hệ mã bí mật 3.1.1 Mã dịch chuyển (Shift Cipher) – mã Ceasar Giả sử bảng chữ tiếng Anh xem vành 𝑍26 ta có mã dịch chuyển định nghĩa sau: ❑ Định nghĩa: Mã dịch chuyển: (𝓟, 𝓒, 𝓚, 𝓔, 𝓓) 𝓟 = 𝓒 = 𝓚 = 𝑍26 với k ∈ 𝓚, định nghĩa 𝑒𝑘 𝑥 = (x + k) mod 26 𝑑𝑘 𝑦 = (y − k) mod 26 (x, y ∈ 𝑍26 ) Chương 3: Các hệ mã bí mật Ví dụ: Dùng khóa k=9 để mã hóa dịng thư: “hentoithubay” Dịng thư tương ứng với dịng số h e n t o i t h u b a y 13 19 14 19 20 24 Qua phép mã hóa 𝑒9 được: 16 13 22 23 17 16 10 q c x c q d k j h n w r Như mã là: “qnwcxrcqdkjh” Dùng 𝑑9 giải mã ta rõ ban đầu Cách 2000 năm mã dịch chuyển Julius Ceasar sử dụng, với khóa k=3 mã dịch chuyển gọi mã Ceasar Chương 3: Các hệ mã bí mật Bài tập: Tìm rõ “RKKRTB” với K = 17 Gợi ý thứ tự ký tự: A B C D E F G H I J K L 10 11 12 N O P Q R S T U M V W X Y Z 13 14 15 16 17 18 19 20 21 22 23 24 25 Chương 3: Các hệ mã bí mật Tính an tồn ✓ Mã hóa thơng điệp biểu diễn chữ từ A đến Z (26 chữ cái), ta sử dụng 𝑍26 ✓ Thơng điệp mã hóa khơng an tồn dễ dàng bị giải mã cách thử 26 giá trị khóa k ✓ Tính trung bình, thơng điệp mã hóa bị giải mã sau khoảng 26/2 = 13 lần thử khóa Chương 3: Các hệ mã bí mật 3.1.2 Mã thay (Subtitution Cipher) Chương 3: Các hệ mã bí mật 3.1.2 Mã thay (Subtitution Cipher) Khóa mã thay hoán vị bảng chữ Gọi S(E) tập hợp tất phép hoán vị phần tử E ❑ Định nghĩa: Mã thay thế: (𝓟, 𝓒, 𝓚, 𝓔, 𝓓) 𝓟 = 𝓒 = 𝑍26 , 𝓚 = S(𝑍26 ) với Π ∈ 𝓚, tức hoán vị 𝑍26 , ta xác định 𝑒Π 𝑥 = Π(x) 𝑑Π 𝑦 = Π−1 (x) với x, y ∈ 𝑍26 , Π−1 nghịch đảo Π 10 Chương 3: Các hệ mã bí mật 3.1.5 Mã hóa Vigenere o o o o o o Trong phương pháp mã hóa thay thế: với khóa k chọn, phần tử x ∈ 𝓟 ánh xạ vào phần tử y ∈ 𝓒 Phương pháp Vigenere sử dụng khóa có độ dài m Được đặt tên theo nhà khoa học Blaise de Vigenere (thế kỷ 16) Có thể xem phương pháp mã hóa Vigenere bao gồm m phép mã hóa dịch chuyển áp dụng luân phiên theo chu kỳ Khơng gian khóa K phương pháp Vigenere có số phần tử 𝑛𝑚 Ví dụ: n=26, m=5 khơng gian khóa ~1.1 x 107 34 Chương 3: Các hệ mã bí mật ❑ Định nghĩa: Mã Vigenere(𝓟, 𝓒, 𝓚, 𝓔, 𝓓) Cho m số nguyên dương 𝓟 = 𝓒 = 𝓚 = 𝑍26 với k=(𝑘1 , 𝑘2 , …, 𝑘𝑚 ) ∈ 𝓚 có 𝑒k (𝑥1 , 𝑥2 , , 𝑥𝑚 ) = (𝑥1 + 𝑘1 , 𝑥2 + 𝑘2 , , 𝑥𝑚 + 𝑘𝑚 ) 𝑑k (𝑦1 , 𝑦2 , , 𝑦𝑚 ) = (𝑦1 − 𝑘1 , 𝑦2 − 𝑘2 , , 𝑦𝑚 − 𝑘𝑚 ) Các phép cộng trừ lấy theo Modulo 26 35 Chương 3: Các hệ mã bí mật ❑ ▪ ▪ ▪ Ví dụ: m = keyword CIPHER Suy ra, khóa k = (2, 8, 15, 7, 4, 17) Cho rõ: thiscryptosystemisnotsecure thiscr yptosy stemis notsec ure Vậy mã là: “vpxzgiaxivwoubttmjpwizitwzt” 36 Chương 3: Các hệ mã bí mật 3.1.6 Mã hóa Hill 37 Chương 3: Các hệ mã bí mật 3.1.6 Mã hóa Hill ▪ ▪ ▪ ▪ Phương pháp Hill (1929) Tác giả: Lester S.Hill Ý tưởng chính: Sử dụng m tổ hợp tuyến tính m ký tự plaintext để tạo m ký tự cyphertext Ví dụ: 𝑦1 = 11𝑥1 + 3𝑥2 𝑦2 = 8𝑥1 + 7𝑥2 (y1, y2) = (x1, x2) = 11 38 Chương 3: Các hệ mã bí mật 3.1.6 Mã hóa Hill Chọn số nguyên dương m Định nghĩa: P = C = (𝑍𝑛 )𝑚 K tập hợp ma trận mxm khả nghịch 𝑘1,1 𝑘 Với khóa k = 2,1 ⋮ 𝑘𝑚,1 𝑘1,2 𝑘2,2 ⋮ 𝑘𝑚,2 … … ⋮ … 𝑘1,1 𝑘 𝑒𝑘 (x) = xk = (𝑥1 , 𝑥2 , …, 𝑥𝑚 ) 2,1 ⋮ 𝑘𝑚,1 𝑘1,𝑚 𝑘2,𝑚 ∈ K, định nghĩa: ⋮ 𝑘𝑚,𝑚 𝑘1,2 𝑘2,2 ⋮ 𝑘𝑚,2 … … ⋮ … 𝑘1,𝑚 𝑘2,𝑚 ⋮ 𝑘𝑚,𝑚 với x = (𝑥1 , 𝑥2 , …, 𝑥𝑚 ) ∈ P Và 𝑑𝑘 (y) = y𝑘 −1 với y ∈ C Mọi phép toán số học thực 𝑍𝑛 39 Chương 3: Các hệ mã bí mật 3.1.6 Mã hóa Hill Ví dụ: cho hệ mã Hill có M=2 (khóa ma trận vuông cấp 2) bảng chữ bảng chữ tiếng Anh, tức N = 26 Cho khóa: K = 3 Hãy mã hóa xâu P = “HELP” giải mã ngược lại mã thu 40 Chương 3: Các hệ mã bí mật 3.1.6 Mã hóa Hill Để mã hóa chia xâu rõ thành vecto hàng chiều “HE” (7 4) “LP” (11 15) tiến hành mã hóa 3 = (3 15) = (D P) ▪ Với 𝑃1 =(7 4) ta có 𝐶1 = 𝑃1 *K = (7 4) ▪ Với 𝑃2 =(11 15) ta có 𝐶2 = 𝑃2 *K = (11 15) 3 = (11 4) = (L E) Vậy mã thu C = “DPLE” 41 Chương 3: Các hệ mã bí mật 3.1.6 Mã hóa Hill Để giải mã ta tính khóa giải mã ma trận nghịch đảo ma trận khóa 𝑍26 theo cơng thức sau: 𝑘11 𝑘12 det(K) = (𝑘11 * 𝑘22 - 𝑘21 * 𝑘12 ) mod N phần tử có 𝑘21 𝑘22 phần tử nghịch đảo 𝑍𝑁 (ký hiệu det(𝐾)−1 ) khóa giải mã là: Với K = 𝒌𝟐𝟐 −𝒌𝟏𝟐 −𝒌𝟐𝟏 𝒌𝟏𝟏 Áp dụng vào trường hợp ta có det(K) = (15 - 6) mod 26 = 𝑲−𝟏 = 𝒅𝒆𝒕(𝑲)−𝟏 * GCD(9, 26) = nên áp dụng thuật tốn Euclid mở rộng tìm det(𝐾)−1 = Vậy 𝐾 −1 = * 24 23 15 = 20 17 42 Chương 3: Các hệ mã bí mật 3.1.6 Mã hóa Hill Giải mã C = “DP” = (3 15), P = C*𝐾 −1 = (3 15) * 15 17 = (7 4) = 20 “HE” Tương tự giải mã xâu C=“LE” kết rõ P=“LP” Chú ý ví dụ sử dụng khóa K có kích thước nhỏ nên dễ dàng tìm khóa để giải mã trường hợp tổng quát điều không dễ dàng 43 Chương 3: Các hệ mã bí mật Giải thích cách tìm khóa 𝑎 Giả sử: k = 𝑐 𝑏 𝑎 ta có ma trận nghịch đảo 𝑘 −1 = 𝑑 𝑐 𝑏 𝑑 −1 tính: 𝑎 𝑐 𝑏 𝑑 −1 = 𝑑 𝑎𝑑−𝑏𝑐 −𝑐 𝑎𝑑−𝑏𝑐 −𝑏 𝑎𝑑−𝑏𝑐 𝑎 𝑎𝑑−𝑏𝑐 44 Chương 3: Các hệ mã bí mật Giải thích cách tìm khóa Một ý để phép chia thực tập 𝑍26 thiết định thức k: det(k) = (ad – bc) phải có phần tử nghịch đảo 𝑍26 Nghĩa (ad - bc) phải giá trị: 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23 25 Đây điều kiện để ma trận k tồn ma trận nghịch đảo 45 Chương 3: Các hệ mã bí mật o Khi đó: 𝑘 −1 k = I ma trận đơn vị (đường chéo 1) 𝑎 𝑐 𝑏 𝑑 −1 𝑎 𝑐 𝑏 = 𝑑 𝑑 𝑎𝑑−𝑏𝑐 −𝑐 𝑎𝑑−𝑏𝑐 −𝑏 𝑎𝑑−𝑏𝑐 𝑎 𝑎𝑑−𝑏𝑐 𝑎 𝑐 𝑏 = 𝑑 46 Chương 3: Các hệ mã bí mật o Định thức o 11 Khi 11 11.7 – 8.3 = ≡ mod 26 −1 = −8 18 ≡ mod 26 −3 11 23 11 47 Chương 3: Các hệ mã bí mật o Vận dụng cho k = o Tìm 𝐾 −1 12 15 25 48 ...Chương 3: Các hệ mã bí mật 3.1 Một số hệ mã cổ điển Hệ mật mã có khóa đối xứng, tức hệ mật mã mà khóa lập mật mã khóa giải mật mã trùng Thực tế hai khóa (mã hóa, giải mã) khác nhau, trường... moscow” 19 Chương 3: Các hệ mã bí mật 3.1.3 Mã thay Playfair 20 Chương 3: Các hệ mã bí mật 3.1.3 Mã Playfair Một hướng khắc phục phương pháp mã bảng mã đơn mã chữ, tức chữ mã số chữ khác tùy thuộc... điệp mã hóa bị giải mã sau khoảng 26/2 = 13 lần thử khóa Chương 3: Các hệ mã bí mật 3.1.2 Mã thay (Subtitution Cipher) Chương 3: Các hệ mã bí mật 3.1.2 Mã thay (Subtitution Cipher) Khóa mã thay