Substitution cipher là gì

3 năm trước

Giới thiệu

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.

Trong bài này ta chỉ đề cập đến một nhánh nhỏ của hệ mã thay thế: mã thay thế đơn giản (Simple Substitution Cipher). Trong đó, tập kí tự trong bản mã là một hoán vị của tập kí tự trong bản rõ. Sơ đồ hệ mật mã thay thế được định nghĩa như sau:

S = (P, C, K, E, D)

Trong đóP = C = Z26,K là tập hợp tất cả các hoán vị trên Z26, các hàm lập mã và giải mã được cho bởi:

E(p, k) = k(p)

D(c, k) = k-1(c)

trong đó k() K là một phép hoán vị trên tậpZ26.

Ví dụ với khóa k =XNYAHPOGZQWBTSFLRCVMUEKJDIthì ta sẽ có sơ đồ lập và giải mã như sau:

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

X N Y A H P O G Z Q W B T S F L R C V M U E K J D I

và bản rõSPIDER MANsẽ được mã hóa thành VLZAHC TXS. Để giải mã chỉ cần làm ngược lại.

Có 26! hoán vị của 1 tập 26 phần tử. Nên tổng số key có thể là 26! > 4 x 1026. Không như mã Caesar và mã Affine, con số này quá lớn để có thể thám mã bằng phương pháp vét cạn. Vì thế ở phần sau tôi sẽ giới thiệu một phương pháp thám mã khác phù hợp cho loại mã này: thám mã dựa trên mẫu từ.

Bây giờ ta đi vào cài đặt thuật toán lập mã và giải mã trước.

---

Code

import random LETTERS = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ' # Check if the key is valid def checkValidKey(key): keyList = list(key) lettersList = list(LETTERS) keyList.sort() lettersList.sort() if keyList == lettersList: return True return False # Return Substitution Cipher with Mode 'ENCRYPT' or 'DECRYPT' def substitution_cipher(message, MODE, key): translated = '' charsA = LETTERS charsB = key if MODE.upper() == 'DECRYPT': charsA, charsB = charsB, charsA for symbol in message: if symbol.upper() in charsA: symIndex = charsA.find(symbol.upper()) if symbol.isupper(): translated += charsB[symIndex].upper() else: translated += charsB[symIndex].lower() else: translated += symbol return translated def getRandomKey(): key = list(LETTERS) random.shuffle(key) return ''.join(key) def main(): message = """If a man is offered a fact which goes against his instincts, he will scrutinize it closely, and unless the evidence is overwhelming, he will refuse to believe it. If, on the other hand, he is offered something which affords a reason for acting in accordance to his instincts, he will accept it even on the slightest evidence. The origin of myths is explained in this way. -Bertrand Russell""" key = getRandomKey() cipher = substitution_cipher(message, 'ENCRYPT', key) print('nKey: ' + key) print('nPlain text: ' + message) print('nCipher text: ' + cipher) message = substitution_cipher(cipher, 'DECRYPT', key) print('nPlain text after decrypt: ' + message) if __name__ == '__main__': main()

Đoạn code trên không khó hiểu, chỉ cần lưu ý đoạn

if MODE.upper() == 'DECRYPT': charsA, charsB = charsB, charsA

Câu lệnh này nhằm đổi chiều mã hóa nếu ta cần giải mã.

Kết quả test như sau:

---

Thám mã

Giả sử ta có bản mã:OLQIHXIRCKGNZ PLQRZKBZB MPBKSSIPLC.Làm sao để giải mã đoạn mã này khi mà không thể vét cạn hết 26! key được. Ta sẽ dùng phương pháp phân tích mẫu từ.

Xét từ thứ nhấtOLQIHXIRCKGNZvới 13 kí tự,ta có thể viết lại từ này dưới dạng 0.1.2.3.4.5.3.6.7.8.9.10.11 trong đó mỗi kí tự trong từ được thay thế bằng một con số, các số này tăng dần từ 0, 1, và các kí tự giống nhau sẽ được kí hiệu bằng con số giống nhau. Để ý thấy kí tự thứ 4 và kí tự thứ 7 là giống nhau0.1.2.3.4.5.3.6.7.8.9.10.11.Vậy ta hãy tìm xem trong tiếng anh có từ nào có 13 kí tự mà kí tự thứ 4 và kí tự thứ 7 giống nhau không, tức là cũng có mẫu từ dạng0.1.2.3.4.5.3.6.7.8.9.10.11.Có 2 từ như vậy trong tiếng anh:UNCOMFORTABLE vàUNCOMFORTABLY.Như vậy chữ O chắc chắn phải được giải mã thành U, tương tự L giải mã thành N, và Z có thể giải mã thành E hoặc Y. Đến đây ta có thể lập bảng mapping các khả năng của mỗi kí tự. Trong Python có kiểu dữ liệu Dictionary rất thuận tiện cho nhu cầu này.

{'A': [], 'C': ['T'], 'B': [], 'E': [], 'D': [], 'G': ['B'], 'F': [], 'I':
['O'], 'H': ['M'], 'K': ['A'], 'J': [], 'M': [], 'L': ['N'], 'O': ['U'], 'N':
['L'], 'Q': ['C'], 'P': [], 'S': [], 'R': ['R'], 'U': [], 'T': [], 'W': [],
'V': [], 'Y': [], 'X': ['F'], 'Z': ['E', 'Y']}

Tiếp tục, ta xét từ thứ haiPLQRZKBZB.Mẫu từ tương ứng là 0.1.2.3.4.5.6.4.6.Có 4 từ tiếng anh có dạng mẫu này:CONVERSES, INCREASES, PORTENDED, UNIVERSES.Ta lại lập bảng mapping cho các từ này và được

{'A': [], 'C': [], 'B': ['S', 'D'], 'E': [], 'D': [], 'G': [], 'F': [], 'I':
[], 'H': [], 'K': ['R', 'A', 'N'], 'J': [], 'M': [], 'L': ['O', 'N'], 'O': [],
'N': [], 'Q': ['N', 'C', 'R', 'I'], 'P': ['C', 'I', 'P', 'U'], 'S': [], 'R':
['V', 'R', 'T'], 'U': [], 'T': [], 'W': [], 'V': [], 'Y': [], 'X': [], 'Z':
['E']}

Xét tiếp từ thứ ba với cách tương tự, các từ có thể làADMITTEDLY, DISAPPOINT.Ta lại được 1 bảng mapping khác:

{'A': [], 'C': ['Y', 'T'], 'B': ['M', 'S'], 'E': [], 'D': [], 'G': [], 'F': [],
'I': ['E', 'O'], 'H': [], 'K': ['I', 'A'], 'J': [], 'M': ['A', 'D'], 'L': ['L',
'N'], 'O': [], 'N': [], 'Q': [], 'P': ['D', 'I'], 'S': ['T', 'P'], 'R': [],
'U': [], 'T': [], 'W': [], 'V': [], 'Y': [], 'X': [], 'Z': []}

Vì cả 3 từ này đều dùng chung một khóa, hay một bảng mapping khóa (mà ta chưa biết) nên chúng phải giao nhau, ta lấy giao của 3 bảng mapping này lại. Ví dụ kí tự C trong bảng mapping 1 có giá trị là T, trong bảng 2 trống (có nghĩa là có thể giải mã thành bất cứ ký tự nào), trong bảng 3 có giá trị là Y hoặc T. Vậy C phải tương ứng với T, hay nói cách khác C giải mã thành T. Làm tương tự với 26 chữ cái, ta được bảng mapping giao như sau:

{'A': [], 'C': ['T'], 'B': ['S'], 'E': [], 'D': [], 'G': ['B'], 'F': [], 'I':
['O'], 'H': ['M'], 'K': ['A'], 'J': [], 'M': ['A', 'D'], 'L': ['N'], 'O':
['U'], 'N': ['L'], 'Q': ['C'], 'P': ['I'], 'S': ['T', 'P'], 'R': ['R'], 'U':
[], 'T': [], 'W': [], 'V': [], 'Y': [], 'X': ['F'], 'Z': ['E']}

Như vậy ta đã giải mã được gần hết bảng chữ cái. Áp dụng bảng mapping này vào bản mã ban đầu OLQIHXIRCKGNZ PLQRZKBZB MPBKSSIPLC ta được bản rõUNCOMFORTABLE INCREASES _ISA__OINT.Có 2 kí tự nằm ở từ thứ 3 trong bản mã vẫn chưa được giải: M -> ? và S ->?. Nhìn lại bảng mapping có nhận xét: K -> A và M -> A or D. Vậy M phải được giải mã thành D hay: M -> D. Tương tự C -> T và S -> T or P. Vậy S -> P.
Cuối cùng ta được bản rõ làUNCOMFORTABLE INCREASES DISAPPOINT.

Eureka, bạn đã biết cách thám mã cho mã thay thế rồi đấy. Nhìn chung, bản mã ta có được càng dài thì khả năng giải mã được sẽ càng cao. Giờ vấn đề là chuyển ý tưởng thành code thôi.

.

>> Còn tiếp

---

Download mã nguồn SubstitutionCipher.py

---

<< Bài 3 Mã Affine

Bài 5 Mã thay thế (Phần 2) >>

Danh mục: Crypto

Thẻ: CryptoKhu vực Widget dưới ChânPython

Để lại nhận xét