Cryptography Cổ Điển - Mã Thay Thế Phần 2
Sau khi Simple Substitution Cipher để lộ một điểm yếu chết người, những nhà mật mã học sáng tạo ra những hệ thống cryptography mới hòng chống lại điểm yếu ấy.
Nếu bạn chưa đọc bài viết trước thì bạn nên làm vậy để định hình được cách thức vận hành của một hệ thống cryptography đơn giản. Bài viết này sẽ bàn về những hệ thống được phát minh ra trong thời kì Phục hưng, phức tạp hơn, thông minh hơn, dùng những thuật ngữ bài trước đã sử dụng.
Polyalphabetic Substitution Cipher
Đây là một lớp những hệ thống cipher với cơ chế như sau: Vẫn encrypt lần lượt từng chữ cái trong plaintext, những nhiều chữ cái khác nhau trong plaintext có thể được encrypt thành 1 chữ cái trong ciphertext. Hãy lấy ví dụ sau đây để hiểu rõ hơn.
Vigenere Cipher
Vigenere Cipher xuất hiện vào thế kỉ XVI và là ví dụ tiêu biểu nhất cho lớp cipher loại này. Nó cũng rất đơn giản, làm cho việc encrypt/decrypt bằng tay cũng dễ dàng.
Key của Vigenere Cipher sẽ là 1 từ có độ dài bất kì. Lấy ví dụ key = lemon,
plaintext = attack at dawn. Như thường lệ, trong quá trình encrypt ta muốn
lược bỏ khoảng cách giữa các từ.
Ta lặp lại key cho đến khi nào độ dài key bằng độ dài plaintext:
attackatdawn
lemonlemonle
Việc tiếp theo, ta thực hiện phép cộng mod 26 đối với 2 string trên. String
kết quả sẽ là ciphertext.
plaintext attackatdawn
+
key lemonlemonle
=
CIPHERTEXT LXFOPVEFRNHR
(Cách cộng: Đổi từng chữ cái thành số tương ứng, thực hiện phép cộng mod 26
với 2 số, rồi đổi lại thành chữ cái. Trong ví dụ trên: t = 19, e = 4,
t + e = (19 + 4) mod 26 = 23 = X)
Ta nhận thấy rằng những chữ cái thứ 1, 6, 11 cộng với l, hay tịnh tiến với
khoảng cách là 11; những chữ cái 2, 7, 12 cộng với e, hay tịnh tiến với khoảng
cách là 4; cứ như vậy. Tức là việc encrypt giống như Caesar Cipher ở chỗ tịnh
tiến chữ cái, nhưng tất cả các chữ cái không tịnh tiến cùng một khoảng cách.
Ngoài ra, trong ví dụ trên, encrypt(d) = encrypt(n) = R, tức là nhiều chữ cái
khác nhau trong plaintext có thể có encryption giống nhau.
Decryption thì sẽ ngược lại với quá trình encryption: Lấy ciphertext trừ đi key.
CIPHERTEXT LXFOPVEFRNHR
-
key lemonlemonle
=
plaintext attackatdawnNgoài ra việc encryption và decryption của Vigenere Cipher cũng có thể được thực hiện bằng Vigenere Table.
Vigenere Table
Ta lấy lại ví dụ trên: plaintext = attackatdawn, key = lemon. Với chữ cái đầu tiên của ciphertext, ta thực hiện việc tra chữ cái ở cột A và hàng L. Với chữ cái thứ hai, tra chữ cái ở cột T và hàng E, v.v.
Như vậy code implementation của Vigenere Cipher cũng bao gồm 2 cách. Mình sẽ để cách tra bảng như là một câu đố cho các bạn. Còn sau đây là encryption pseudocode cho cách đầu tiên.
encryptVigenereCipher(string plaintext, string key) {
string ciphertext;
int m = length(plaintext); // độ dài plaintext
int n = length(key); // độ dài key
for i (0 to m - 1) {
int c_cipher = ( int(plaintext[i]) + int(key[i mod n]) ) mod 26;
// i mod n là để lặp lại key
append char(c_cipher) to ciphertext;
}
return ciphertext;
}Tấn công trong Cryptanalysis
Như đã nói, Vigenere Cipher ngụy trang tần suất xuất hiện của mỗi chữ cái trong plaintext, vì vậy không thể tấn công trực tiếp bằng Frequency Analysis được. Trong ví dụ "attack at dawn" trên, 1 chữ cái a có đến 3 encryption: a thành L ở vị trí 1, thành O ở vị trí 4, và thành N ở vị trí 10.
Dẫu vậy, trong trường hợp plaintext dài hơn nhiều so với key, việc lặp lại key trong quá trình encrypt để lộ một điểm yếu của Vigenere Cipher, khiến cho hệ thống này vẫn có thể bị tấn công bằng phương pháp Ciphertext Only Attack.
Tấn công bao gồm 2 bước: Tìm độ dài của từ khóa key (có những cách như Kalsiki examination hay Friedman test), và khi biết được độ dài của key thì việc tìm chính xác từ khóa có nhiều cách. Ta có thể lợi dụng một số chữ cái trong plaintext có khoảng cách tịnh tiến như nhau và sử dụng Frequency Analysis, hoặc là sử dụng một phương pháp mà mình sẽ giải thích sau đây: Key Elimination
Ta lấy ví dụ ciphertext sau: EPSDFQQXMZCJYNCKUCACDWJRCBVRWINLOWU
Ta đã đoán được key có độ dài là 4. Như vậy bước đầu tiên là trừ
ciphertext cho chính nó, tịnh tiến với khoảng cách 4.
CIPHERTEXT (ban đầu) EPSDFQQXMZCJYNCKUCACDWJRCBVRWINLOWU
-
CIPHERTEXT (tịnh tiến) FQQXMZCJYNCKUCACDWJRCBVRWINLOWU____
=
ZZCGTROOOMAZELCIRGRLBVOAGTIGIMT____
Mặt khác, do tính chất của phép cộng modulo, ta có công thức sau:
CIPHERTEXT (ban đầu) - CIPHERTEXT (tịnh tiến)
= plaintext (ban đầu) - plaintext (tịnh tiến)
Để chứng minh công thức trên, các bạn hình dung như thế này. Do
chữ cái thứ 1 và thứ 5 tịnh tiến cùng 1 khoảng cách, khoảng cách
giữa chúng sẽ không đổi. Tương tự với những cặp chữ cái còn lại.
Như vậy, bằng brute force và xem xét những cụm từ có nghĩa, ta có
thể phá được 8 chữ cái đầu tiên là thequick.
Lấy 4 chữ cái đầu, trừ đi từ ciphertext:
EPSDFQQXMZCJYNCKUCACDWJRCBVRWINLOWU
-
THEQ_______________________________
=
LION_______________________________
Như vậy từ khóa key là lion. Việc còn lại là quá trình decrypt Vigenere
Cipher bình thường.
Biến thể
Running key Cipher là một biến thể của Vigenere Cipher. Gọi là biến thể, nhưng chúng hoạt động hoàn toàn giống nhau. Điểm khác nhau nằm ở key, khi Running key Cipher có key rất dài, dài bằng plaintext, thậm chí hơn, nên ta không cần phải lặp lại key. Vì thế, key ở đây có thể là một đoạn văn, thậm chí là cả một quyển sách.
Running key Cipher không thể bị phá bằng phương pháp Cryptanalysis trong ví dụ trên vì key quá dài. Thực chất, nếu key là hoàn toàn ngẫu nhiên (tức key không cần phải là một đoạn văn có nghĩa, chỉ bao gồm những chữ cái ngẫu nhiên), cipher này sẽ có độ bảo mật tuyệt đối.
Ta sẽ bàn về độ bảo mật tuyệt đối cùng với một hệ thống cryptography trong một bài viết tương lai. Tuy nhiên, xin disclaim là độ bảo mật tuyệt đối cũng đi kèm với một cái giá khá đắt: độ dài của key ít nhất phải dài bằng độ dài của plaintext, một điều không mấy thực tế trong cryptography.
Thực ra, nhiều Polyalphabetic Cipher hoạt động dựa trên Vigenere. Một ví dụ nổi bật về lớp hệ thống cipher này mà không sử dụng Vigenere là máy Enigma (hình đầu bài) được Đức Quốc xã sử dụng trong Thế Chiến II.
Tạm kết
Trên đây là phân tích một Polyalphabetic Substitution Cipher tiêu biểu, tuy vậy nó vẫn có những điểm yếu nhất định.
Blog tiếp theo sẽ chuyển sang một lớp hệ thống Substitution Cipher mới, thay vì encrypt từng chữ cái thì nó sẽ encrypt theo nhóm chữ cái. Stay tuned!
