Bài 9: Mã hoá cổ điển – Hệ mã hoá thay thế (Substitution cipher)

0
13
Mã hoá cổ điển

Ở những bài trước ta đã tìm hiểu về hệ mật mã và cơ sở toán học của mật mã học. Từ bài này ta sẽ tìm hiểu thêm về các thuật toán mã hoá cổ điển nhất.

Hệ thống mật mã cổ điển

Hệ thống mật mã cổ điển bao gồm các loại mật mã được ứng dụng trong thời kỳ đầu của mật mã học. Tuy nhiên, hiện nay hệ thống mật mã cổ điển trở nên lạc hậu do cách thức mã hoá đong giản và có thể dễ dàng bẻ khoả qua nhiều phương thức: tấn công vét cạn hay tấn công thống kê.

Các phương thức mã hoá cổ điển chủ yếu dựa trên mật mã hoán vịmật mã thay thế.

Mật mã hoán vị là loại mật mã mà các kí tự trong bản rõ sẽ được hoán vị theo một cách thức nào đó để tạo nên bản mã. Trong mật mã hoán vị thì các ký tự giữ không đổi, nhưng trật tự của chúng trong bản tin lại thay đổi theo một quy luật nào đó. Cách mã hóa này thường xuất hiện ở những trò chơi đi tìm mật thư trong nhà trường. Hệ thống mã hóa này yếu và ít biến thể,ví dụ như Vigenère.

Mật mã thay thế là loại mật mã mà mỗi kí tự trong bản rõ được thay bằng một kí tự trong bản mã theo một quy tắc nhất định. Thể loại này có nhiều biến thể, và trong các bài tiếp theo chúng ta sẽ đi qua một số loại mã thay thế phổ biến nhất: mã Caesar, mã Affine, mã thay thế đơn giản, mã Vigenere, … Đầu tiên và đơn giản nhất là mã thay thế đơn giản.

Có các thuật toán phức tạp để thực hiện việc mật mã hóa bằng cách tổ hợp hai phương thức trên để tạo ra sản phẩm mã hóa; các phương thức mã hóa khối hiện đại như DES hay AES thực hiện việc lặp đi lặp lại một số bước thay thế và hoán vị.

Hệ mã hoá thay thế (Substitution cipher)

Mã thay thế (Substitution Cipher) là hệ mã trong đó mỗi kí tự của bản rõ được thay thế bởi một kí tự tương ứng trong bản mã theo một cách nào đó.

Trong Shelock Holmes có một vụ án nhắc đến loại mã này, đó là truyện “Những hình nhân nhảy múa”. Thủ phạm đã dùng mã thay thế với mỗi kí tự được thay bằng một hình nhân người nhảy múa. Thám tử Holmes tài ba đã áp dụng phương pháp thám mã phân tích tần suất và phân tích mẫu từ để giải mã các hình nhân này.

“Những hình nhân nhảy múa”
“Những hình nhân nhảy múa”

Có 4 kỹ thuật thay thế sau đây:

  1. Thay thế đơn (A simple substitution cipher): là hệ mã trong đó một ký tự của bản rõ được thay bằng môṭ ký tự tương ứng trong bản mã. Một ánh xạ 1-1 từ bản rõ tới bản mã được sử dụng để mã hoá toàn bộ thông điệp.
  2. Thay thế đồng âm (A homophonic substitution cipher): giống như hệ thống mã hoá thay thế đơn, ngoại trừ một ký tự của bản rõ có thể được ánh xạ tới một trong số một và i ký tự của bản mã : sơ đồ ánh xạ 1-n (one-to-many). Ví dụ, “A” có thể tương ứng với 5, 13, 25, hoăc̣ 56, “B” có thể tương ứng với 7, 19, 31, hoăc̣ 42, v.v.
  3. Thay thế đa mẫu tự (A polyalphbetic substitution cipher): được tạo nên từ nhiều thuật toán mã hoá thay thế đơn. Ánh xạ 1-1 như trong trường hợp thay thế đơn, nhưng có thể thay đổi trong phaṃ vi môṭ thông điệp . Ví dụ, có thể có năm thuật toán mã hoá đơn khác nhau được sử dụng ; đăc̣ biêṭ thuật toán mã hoá đơn được sử dụng thay đổi theo vị trí của mỗi ký tự trong bản rõ.
  4. Thay thế đa sơ đồ (A polygram substitution cipher): là thuật toán trong đó các khối ký tự được mã hoá theo nhóm . Đây là thuật toán tổng quát nhất, cho phép thay thế các nhóm ký tự của văn bản gốc. Ví dụ, “ABA” có thể tương ứng với “RTQ”, “ABB” có thể tương ứng với “SLL”, v.v.