2.9K 221 103

Đã đăng vào thg 5 10, 8:00 SA 3 phút đọc

346

General knowledge in Cryptography - kiến thức tổng quan trong mật mã học (phần 3)

MayFest2024

IV. Giới thiệu một số mật mã cổ điển

1. Mật mã Caesar

Mật mã Caesar là một trong những mật mã cổ điển xuất hiện sớm nhất, được đặt tên theo nhà văn và nhà sử học người La Mã Julius_Caesar - người đã sử dụng nó trong các thư từ bí mật của mình. Mã hóa Caesar còn được biết đến với tên mật mã chuyển vị, biểu thị cho phương thức mã hóa dịch chuyển vị trí chữ cái.

Mật mã Caesar điển hình và thường thấy nhất sử dụng phép dịch chuyển ký tự sang phải $3$ đơn vị. Số vị trí dịch chuyển này có thể được coi là giá trị của secret ket $K=3$ . Đối với bảng chữ cái tiếng anh in hoa $A-Z$ , mã hóa Caesar đang xét có thể hiểu là thay thế các chữ cái bằng chữ cái đứng liền sau nó $3$ vị trí, chẳng hạn $B\rightarrow E$ , $M\rightarrow P$ , đối với các chữ cái cuối cùng $X, Y, Z$ sẽ được thay thế lần lượt bởi $A, B, C$ .

Bởi tính dịch chuyển vòng quanh, chúng ta còn có thể biểu thị cách mã hóa của mật mã Caesar dưới dạng module trong toán học:

$E_n(x) = (x + n)\ \text{mod 26}\\ D_n(x) = (x - n)\ \text{mod 26}$

Trong đó $E_n()$ là hàm mã hóa, $D_n()$ là hàm giải hóa, $n$ là giá trị secret key.

Ví dụ, đối với bản mã VIBLOSECURITY có:

$E_n(\text{VIBLOSECURITY}) = \text{YLEORVHFXULWB}$

Với phạm vi $26$ chữ cái in hoa trong bảng chữ cái, để thực hiện mã hóa Caesar trong lập trình, có thể xét hai trường hợp về ký tự cần mã hóa, sử dụng bảng mã ASCII, ví dụ đối với trường hợp $k=3$ :

k = 3
for i in plaintext:
    if (i < 'X'):
        print(chr(ord(i) + k), end = "")
    else:
        print(chr(ord(i) + k - 26), end = "")

Sử dụng module, chúng ta có chương trình mã hóa tổng quát Caesar như sau:

for i in plaintext:
    print(chr(((ord(i) - 65 + k) % 26) + 65), end = "")

Sử dụng hàm String find(), chúng ta có chương trình rút gọn như sau:

alphabet = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'

for i in plaintext:
    print(alphabet[(alphabet.find(i) - 3) % 26], end = '')

Bài tập dành cho bạn đọc: hãy viết lại hàm giải mã Caesar dựa trên các chương trình trên.

Challenge CTF: King Ceaser Cipher

Văn bản mã hóa từ đề bài: a22W362Z273a40Z22X56357W5268a411 với key có giá trị $48$ .

Quan sát ciphertext nhận thấy các ký tự đã mã hóa có thể là chữ cái in hoa, in thường hoặc chữ số, kết hợp với gợi ý:

King Ceasar II's cipher uses 2 alphabet: 1 has 52 characters and 1 has 10 characters.

Chúng ta có thể dự đoán hai chuỗi alphabet được tác giả sử dụng để mã hóa theo mật mã Caesar lần lượt là:

alpha1 = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz'
alpha2 = '0123456789'

Thông tin về số vị trí dịch chuyển key = 48 áp dụng đối với mỗi dãy alphabet theo tính chất module có thể suy ra quá trình mã hóa:

Nếu ký tự nằm trong dãy thứ nhất sẽ dịch chuyển vòng quanh sang phải $48$ vị trí, hay $E_n(x) = (x + 48)\ \text{mod 52}$ . Khi giải mã ta có: $D_n(x) = (x - 48)\ \text{mod 52} = (x + 4)\ \text{mod 52}$
Tương tự, nếu ký tự thuộc dãy thứ hai sẽ có: $E_n(x) = (x + 48)\ \text{mod 10} = (x + 8)\ \text{mod 10}$ , giải mã: $D_n(x) = (x - 88)\ \text{mod 10} = (x + 2)\ \text{mod 10}$

Từ hướng giải trên, chúng ta có chương trình tham khảo như sau:

ciphertext = 'a22W362Z273a40Z22X56357W5268a411'
key = 48
flag = ''

alpha1 = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz'
alpha2 = '0123456789'

for i in ciphertext:
    if i in alpha1:
        flag += alpha1[(alpha1.find(i) + 4) % 52]
    else:
        flag += alpha2[(alpha2.find(i) + 2) % 10]

print('Flag{%s}' % flag)

2. Mật mã Morse

Mã Morse được đặt theo tên của Samuel Morse - nhà phát minh của điện báo, mật mã thường được sử dụng trong các lĩnh vực viễn thông, quân đội và hàng không. Mã Morse mã hóa văn bản dưới dạng các chuỗi xung điện "ngắn" và "dài", đại diện bởi hai ký tự . và - (dots and dash).

Thông thường, chúng ta ký hiệu dấu khoảng cách bằng ký tự / trong Morse. Ví dụ mã hóa viblo security trong mật mã Morse thu được:

...- .. -... .-.. --- / ... . -.-. ..- .-. .. - -.--

Đối với xây dựng chương trình mã hóa và giải mã mật mã Morse trong Python, chúng ta cần khai báo một dict chứa từng cặp giá trị ký tự và mã hóa của nó.

MORSE_CODE_DICT = {'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':'--..', '1':'.----', '2':'..---', '3':'...--', '4':'....-', '5':'.....', '6':'-....', '7':'--...', '8':'---..', '9':'----.', '0':'-----', ', ':'--..--', '.':'.-.-.-', '?':'..--..', '/':'-..-.', '-':'-....-', '(':'-.--.', ')':'-.--.-'}

Từ đó dựa vào ánh xạ $1-1$ trên để mã hóa và giải mã văn bản. Bạn đọc có thể tham khảo thêm tại https://www.geeksforgeeks.org/morse-code-translator-python/.

Challenge Mã Morse Kì Lạ

Dễ dàng nhận thấy đề bài thực hiện mã hóa flag theo định dạng mã Morse, thay dots và dash thành hai ký tự X và Y.

YYXY YXYY YX XXY { X YYYY Y _ XX XXX YXY YYY Y _ XYXX XXX YYX _ XYX XY XXX YXX _ X YYYY Y _ XX XXX YXY Y _ XYXX XXX YYX _ XYX XY XXX YXX }

Để xác định được thứ tự X và Y tương ứng với dots hay dash, chúng ta lưu ý định dạng của flag là Flag{...}. Suy ra F được mã hóa thành YYXY, mà F trong mật mã Morse là ..-. nên có X = -, Y = .. Hay chúng ta có flag chuyển sang dạng Morse "chuẩn hơn":

ciphertext = 'YYXY YXYY YX XXY { X YYYY Y _ XX XXX YXY YYY Y _ XYXX XXX YYX _ XYX XY XXX YXX _ X YYYY Y _ XX XXX YXY Y _ XYXX XXX YYX _ XYX XY XXX YXX }'

flag = ''

for i in ciphertext:
    if i == 'Y':
        flag += '.'
    elif i == 'X':
        flag += '-'
    else:
        flag += i

print(flag)

Kết quả:

..-. .-.. .- --. { - .... . _ -- --- .-. ... . _ -.-- --- ..- _ -.- -. --- .-- _ - .... . _ -- --- .-. . _ -.-- --- ..- _ -.- -. --- .-- }

Từ đây chúng ta có thể dựa vào bảng mã Morse tìm ra flag hoặc sử dụng một số trang web decode online (chẳng hạn https://morsedecoder.com/):

Bạn đọc có thể thử sức với challenge morse-code trên nền tảng Pico CTF, với mật mã Morse được cho dưới dạng file .wav rất thú vị.

3. Mật mã Vigenère

Mật mã Vigenère được đặt tên theo nhà mật mã học người Pháp Blaise de Vigenère (1523-1596). Mã hóa Vigenère có thể coi là một sự mở rộng của mật mã Caesar bởi nó là sự kết hợp xen kẽ nhiều bước mã hóa Caesar với các khóa dịch chuyển khác nhau.

Mật mã Vigenère sử dụng một bảng vuông $26\times 26$ được tạo thành bởi $26$ bảng mã Caesar, mỗi hàng có thứ tự các chữ cái lệch sang bên trái một vị trí so với hàng trên.

Để mã hóa, mật mã Vigenère sử dụng một từ khóa lặp lại nhiều lần liên tiếp cho tới khi độ dài bằng thông điệp mã hóa. Ví dụ, với thông điệp VIBLOSECURITY và từ khóa TIME, thực hiện lặp thu được: TIMETIMETIMET (độ dài $11$ ). Như vậy mỗi ký tự của plaintext tương ứng với một key trong từ khóa.

Plaintext	V	I	B	L	O	S	E	C	U	R	I	T	Y
The key	T	I	M	E	T	I	M	E	T	I	M	E	T

Quá trình mã hóa thực hiện tìm kiếm lần lượt ký tự ở hàng $\alpha$ và cột $\beta$ với $(\alpha, \beta)$ là cặp ký tự của plaintext và key tương ứng (Không quan trọng thứ tự bởi bảng mã Vigenère đối xứng về hàng và cột). Ví dụ, mã hóa ký tự V trên chúng ta tìm kiếm ký tự hàng V cột T được ký tự O, mã hóa ký tự tiếp theo thu được Q, tiếp tục quá trình thu được ciphertext cuối cùng: OQNPHAQGNZUXR.

Việc giải mã ngược lại chúng ta sẽ tìm trên hàng của key thứ tự cột của ký tự mã hóa (hoặc tìm trên cột của key thứ tự hàng của ký tự mã hóa). Ví dụ: Hàng T, ký tự O thuộc cột V (ký tự plaintext); hàng I, ký tự Q thuộc cột I (ký tự plaintext); ...

Tổng quát, biểu diễn quá trình mã hóa và giải mã Vigenère qua công thức module như sau:

$E_i = (P_i + K_i)\ \text{mod 26}\\ D_i = (E_i - K_i)\ \text{mod 26}$

Trong đó, $E_i$ và $D_i$ lần lượt là hàm mã hóa và giải mã, $P_i$ và $K_i$ chỉ thứ tự thứ $i$ của plaintext và từ khóa.

Thực hiện trong chương trình Python, trước hết chúng ta cần có hàm sinh key cho cùng độ dài với plaintext:

def generateKey(string, key):
    key = list(key)
    if len(string) == len(key):
        return(key)
    else:
        for i in range(len(string) -
                       len(key)):
            key.append(key[i % len(key)])
    return("" . join(key))

Thực hiện mã hóa, ý tưởng tương tự má hóa Caesar:

def cipherText(string, key):
    cipher_text = []
    for i in range(len(string)):
        x = (ord(string[i]) +
             ord(key[i])) % 26
        x += ord('A')
        cipher_text.append(chr(x))
    return("" . join(cipher_text))

Hàm giải mã:

def originalText(cipher_text, key):
    orig_text = []
    for i in range(len(cipher_text)):
        x = (ord(cipher_text[i]) -
             ord(key[i]) + 26) % 26
        x += ord('A')
        orig_text.append(chr(x))
    return("" . join(orig_text))

Bài tập dành cho bạn đọc, hãy hoàn thành challenge CTF Vigenere.

Các tài liệu tham khảo

Cryptography

IV. Giới thiệu một số mật mã cổ điển

1. Mật mã Caesar

2. Mật mã Morse

3. Mật mã Vigenère

Các tài liệu tham khảo

Mục lục