Cryptography Cổ Điển - Mã Thay Thế Phần 1

Cryptography Cổ Điển - Mã Thay Thế Phần 1

Để hiểu những hệ thống Cryptography hiện đại, một ý không tồi là quay sang nhìn lại những hệ thống cũ để tìm hiểu cách thức hoạt động của chúng, từ đó có một cái nhìn chung về cách thức hoạt động của cryptography.

Hôm nay chúng ta sẽ tìm hiểu về một lớp những hệ thống cũ như vậy: Substitution Cipher (Mã Thay thế)

Cryptography cổ điển vỡ lòng

Thông thường, khi chúng ta nhắc tới cryptography cổ điển, ta sẽ thường nghĩ tới những hệ thống mà ta có thể thực hiện encrypt và decrypt bằng tay một cách thuận tiện, không cần tới sự trợ giúp của những thuật toán nhanh siêu tốc mà máy tính ngày nay có thể thực hiện. Đó là bởi vì những hệ thống này được phát minh trong hoàn cảnh chưa có máy tính, nên hầu hết những hệ thống này xuất hiện trước thế kỉ XX.

Những hệ thống cryptography cổ điển có thể được chia làm 2 lớp: Substitution Cipher, lớp chúng ta sẽ tìm hiểu trong blog này, và Transposition Cryptography. 2 lớp này đều thuộc một phạm trù của cryptography được biết đến là symmetric cipher (mã đối xứng).

Những thành phần cơ bản của một hệ thống symmetric cipher bao gồm:

  • Ciphertext (tin nhắn mật)
  • Plaintext (tin nhắn thường)
  • Thuật toán Encryption
  • Thuật toán Decryption
  • Key cho 2 thuật toán trên

Mối quan hệ mật thiết giữa những thành phần trên là:

Ciphertext = Encryption(Plaintext, Key)
Plaintext = Decryption(Ciphertext, Key)

Ngoài ra, 2 thuật toán encryption và decryption tương đồng nhau, dẫn tới việc 2 key tương đồng nhau.

Ta sẽ định nghĩa và phân tích từng hệ thống qua những thành phần trên của chúng, cũng như độ bảo mật của chúng.

Ngoài ra, để thuận tiện cho việc quan sát, toàn bộ plaintext sẽ được viết bằng chữ thường, và toàn bộ ciphertext sẽ được viết bằng chữ hoa.

Hầu hết chúng giờ là lỗi thời do đã bị phá vỡ hoàn toàn và được coi là rất thiếu bảo mật so với những tiêu chuẩn cryptography ngày nay. Tuy nhiên, như đã nói, tìm hiểu về chúng không phải là một ý tồi để có một cái nhìn tổng quát về cách thức vận hành của những thuật toán cryptography.

Simple Substitution Cipher

Phân tích

Đây là dạng Substitution Cipher đơn giản nhất: Xáo trộn bảng chữ cái và viết theo bảng chữ cái mới đó. Như vậy ta sẽ coi bảng chữ cái mới đó là key.

Ta sẽ bắt đầu bằng Caesar Cipher. Nó được đặt tên từ Julius Caesar, người thường xuyên sử dụng cipher này trong những tin mật của ông.

Key của Caesar Cipher rất đơn giản: Bảng chữ cái mới tịnh tiến với khoảng cách là 3, tức là A thành D, B thành E, ..., Z thành C.

Encrryption mẫu của tin nhắn "I Am Julius Caesar"

plaintext:   i am julius caesar
CIPHERTEXT:  L DP MXOLXV FDHVDU

Caesar Cipher cũng bao gồm những cipher với bảng chữ cái được tịnh tiến với khoảng cách khác 3.

ROT 13, một Caesar Cipher với khoảng cách tịnh tiến là 13

Caesar Cipher là dạng đặc biệt của Affine Cipher. Affine Cipher sử dụng hàm bậc nhất để encrypt từng chữ cái.

Cách Affine Cipher vận hành: Mỗi chữ cái được đánh số như sau:
a b c d e ...  z
0 1 2 3 4 ... 25
Affine Cipher sẽ cho từng chữ cái trong plaintext qua hàm f(x) = (ax + b) mod 26,
kết quả là chữ cái tương ứng trong ciphertext
Ví dụ: a = 3, b = 5
plaintext     x     f(x)     CIPHERTEXT
    c         2      11           L
    i         8       3           D
    p        15      24           Y
    h         7       0           A
    e         4      17           R
    r        17       4           E
Tức là encryption(cipher, (3, 5)) = LDYARE
Để ý rằng điều kiện của a là a != 0 và GCD(a, 26) = 1. Vì nếu GCD(a, 26) != 1
thì một ciphertext có thể decrypt ra thành nhiều plaintext.
Ví dụ, khi a = 13, b = 4,
encryption(input, (13, 4)) = encryption(alter, (13, 4)) = ERRER

Bạn có thể thử những ví dụ trên bằng giấy và bút, hoặc bạn có thể thử viết code implement những cipher trên. Dưới đây là pseudocode tiến hành encrypt một tin nhắn bằng Affine Cipher.

encryptAffineCipher(string plaintext, int a, int b) {
    string ciphertext;
    for char c_plain in plaintext {
        char c_cipher = char((a * int(c_plain) + b) mod 26);
        /*
        int(c) trả về số ứng với chữ cái c với a = 0, b = 1, ...
        char(i) trả về chữ cái ứng với số i
        Lưu ý là cách viết trên chỉ để phục vụ cho việc minh họa,
        không đúng với cú pháp
        */
        append c_cipher to ciphertext;
    }
    return ciphertext;
}

Thuật toán decryption của Caesar Cipher cũng như Affine Cipher rất đơn giản: Ta đảo ngược cách tính hàm f(x) lại.

Đối với Caesar Cipher thì đơn giản. Ta tịnh tiến lùi bảng chữ cái. Affine Cipher thì "mệt" hơn một chút. Xem thử bạn có thể tìm ra cách tính hàm ngược để decrypt một ciphertext của Affine Cipher không nhé!

Tấn công trong cryptanalysis

Cho trước một ciphertext mà không biết key, có nhiều phương pháp tấn công trong cryptanalysis có thể giúp ta decrypt ciphertext đó. Tuy nhiên, cách đơn giản nhất và đặc thù với Simple Substitution Cipher chính là Frequency Analysis (phân tích tần số).

Nếu Caesar Cipher đã được sử dụng từ thời La Mã cổ đại thì mãi đến thế kỉ thứ 9, một nhà bác học người Ả Rập mới phát triển lối phân tích ciphertext này nhằm bẻ khóa Caesar Cipher nói riêng và Substitution Cipher nói chung.

Nguyên tắc căn bản là như sau: Lợi dụng việc tần số xuất hiện của mỗi chữ cái là khác nhau, chữ này sẽ thường xuất hiện nhiều hơn chữ khác. Cụ thể hơn, trong những văn bản Tiếng Anh, chữ e xuất hiện nhiều nhất.

Phân bố sự xuất hiện của những chữ cái trong những văn bản Tiếng Anh

Tương tự, ta cũng có thể phân tích tần số xuất hiện theo cặp chữ cái, những cặp xuất hiện nhiều nhất là "th", "er", "on", "an", hoặc theo bộ ba chữ cái, v.v.

Và bằng cách đếm tần số xuất hiện của từng chữ cái trong ciphertext, ta có thể dịch ra thành chữ cái plaintext tương ứng. Ví dụ, giả sử Q là chữ cái xuất hiện nhiều nhất trong ciphertext, khả năng cao decrypt(Q) = e. Làm tương tự lần lượt với chữ cái xuất hiện thường xuyên thứ 2, thứ 3, cho đến khi ta dịch được hết toàn bộ ciphertext.

Điểm yếu nghiêm trọng này của Simple SUbstitution Cipher thôi thúc những nhà mật mã học thời bấy giờ phát triển những Substitution Cipher có tính chất polygraphic, tức là nhiều chữ cái plaintext có thể encrypt thành 1 chữ cái ciphertext duy nhất nhằm chống trả Frequency Analysis, mà ta sẽ bàn cụ thể trong blog sau.

Nhân đây, mình có một ciphertext nhỏ được encrypt bằng Affine Cipher mà chúng ta vừa tìm hiểu ở trên và muốn các bạn decrypt. Hãy thử vận dụng những gì bạn vừa học được ở trên và xem thử bạn decrypt được đoạn tin nhắn dưới đây mà không cần key bí mật nha!

BGUFXCACAOWGAFAOFCANOYFGVEOBDCWLGVFOBFFXCBSFGFXCBMOTGK
FNGVTVKFORCFEUCRRBGFYOBBGFOYYGWLRCAXUXOFOMCBDREDCALGAC
FCGBUCRROBDCNNGRMAYGKRDGBREMBGUXGUQKCYMREOTORMEYXCRDUC
RRFXVGKSXRGPCBSOBDYKDDRCBSSVGUCBFGOYXOVWCBSXOLLEEGKFXW
KYXYXCRDCAXSRGGWOBDAGVVGUUGKRDPOBCAXNGVOWOBGVUGWOBUXGC
AKSREFGOYXCRDCAFGGRGUFGVOBMOAXCSXREOAOUCRDOBCWORNGVBGO
BCWORUCRRAFOBDNGVOBCBAFOBFOBEFXCBSOLLVGOYXCBSOBOFFOYMG
VOBENGVWGNXOVWFGCFAEGKBSTKFUXOFORGFGNFGFANCBDAROLAEOBM
AOBDXOVDUGVDANGVYGBDCFCGBAUXCYXDGBGFYORRNGVAKYXXOVAXFO
YFCYABGYXCRDCABOFKVORREKSREGVYVOBMEOBDTCSSKRLCBSAGTAGV
AODKBXOLLEEGKBSWCBDACBOFCBETGDEAXGKRDBGFGYYKVCBOBEYGWW
KBCFEGNYCPCRCJOFCGBODKRFXGGDXGRDAWOBEOBGLLGVFKBCFENGVA
KYXYGBDCFCGBAYXCRDXGGDAXGKRDBGF

(Hint: Đoạn tin nhắn trên được trích từ Gadsby, một tiểu thuyết hơn 50 000 từ mà không có một chữ e nào, vì thế hãy bắt đầu phân tích tần số bằng chữ cái khác nhé)

Simple Substitution Cipher xuất hiện rất nhiều trong đời sống hàng ngày. Những ví dụ thường thấy là Pigpen Cipher/Tic-Tac-Toe Cipher hay Morse Code. Ngoài ra, trong Microsoft Word cũng có những font chữ kì lạ như Webdings cũng có thể được coi là Substitution Cipher, khi mỗi hình thù riêng thể hiện một chữ cái khác nhau.

An example pigpen message

Pigpen Cipher

Tạm kết

Trên đây là phân tích Simple Substitution Cipher, điểm bắt đầu trong hành trình khám phá những hệ thống Cryptography của chúng ta!

Blog tiếp theo sẽ nghiên cứu Polyalphabetic Substitution, một dạng tiến hóa của loại cipher này. Các bạn hãy đón xem nhé!