Rail Fence cipher là gì

Sau những cryptosystem chỉ mã hóa từng chữ cái mà chúng ta review trong 2 bài viết vừa rồi, như Caesar Cipher và Vigenere Cipher, xuất hiện những hệ thống mới đi xa ý tưởng này, cung cấp độ bảo mật cao hơn [tất nhiên vẫn dễ phá với công nghệ chúng ta hiện có].

Hãy khám phá những ý tưởng đó là gì nhé!

Polygraphic Substitution

Đây là lớp những hệ thống cuối thuộc phạm trù Substitution với những ví dụ điển hình như Playfair Cipher và Hill Cipher: Những hệ thống này mã hóa theo nhóm chữ cái thay vì từng chữ cái.

Ngoài ra, có những cipher như Playfair nhóm theo cặp chữ cái, và chúng được gọi là digraph.

Playfair Cipher

Được phát minh bởi Charles Wheatstone vào 1854 và được truyền bá rộng rãi bởi Nam tước Playfair, cryptosystem này sử dụng rất nhanh chóng, tiện lợi và dễ thực hiện bằng tay mà không cần dụng cụ chuyên dụng nào, vì thế nó được quân đội Anh sử dụng rộng rãi trong những cuộc chiến tranh vào đầu thế kỉ XX.

Key sẽ là một từ khóa, như Vigenere Cipher. Giả sử key = playfair example Ta sẽ xếp bảng chữ cái lại thành 1 ma trận 5x5, đưa những chữ cái trong từ khóa lên trước. p l a y f i/j r e x m b c d g h k n o q s t u v w z [Để ý là bảng chữ cái Tiếng Anh có 26 chữ cái, mà ở đây chỉ có 25, nên thường thì ta sẽ cho 2 chữ i/j vào cùng một chỗ, có phiên bản của Playfair Cipher thì bỏ đi 1 chữ cái.] Lấy ví dụ plaintext = hide the gold in the tree stump Ta sẽ nhóm plaintext thành các cặp chữ cái: hi de th eg ol di nt he tr ex es tu mp ^ [chữ x để tách 2 chữ e đứng cạnh nhau. Nói chung là chỉ cần chữ nào khác chữ e để không có 2 chữ e vào chung 1 cặp] [nếu thừa ra 1 chữ cái sau khi nhóm thì cũng có thể ghép cặp chữ đó với 1 chữ cái bất kì] Sau đây là 2 quy tắc mã hóa: 1] 2 chữ cái nằm ở 2 góc hình chữ nhật * * * * * i * * * m b * * * h * * * * * * * * * * Thay hi -> BM * * * * * * * e x * * * d g * * * * * * * * * * * Thay eg -> XD 2] 2 chữ cái nằm trên cùng 1 hàng/1 cột * * * * * * * e * * * * d * * * * o * * * * * * * Thay de -> OD [tịnh tiến xuống] * * * * * * * e x m * * * * * * * * * * * * * * * Thay ex -> XM [tịnh tiến sang phải] Encrypt phần còn lại, ta sẽ được: CIPHERTEXT = BM OD ZB XD NA BE KU DM UI XM MO UV IF // C++ code để encrypt Playfair Cipher struct table { int row; int col; }; string encryptPlayfairCipher[string plaintext, string key] { string ciphertext; char[5][5] matrix; /* Mình sẽ để phần matrix như một bài tập nhỏ cho các bạn :] Phần dưới coi như là đã xử lí xong cái matrix, có key ở trong rồi */ table posInMat[26] // Lưu position in matrix của mỗi kí tự for [int i = 0; i < 5; ++i] for [int j = 0; j < 5; ++j] posInMat[ int[matrix[i][j]] ].row = i posInMat[ int[matrix[i][j]] ].col = j int n = length[plaintext]; for [int i = 0; i < n; i += 2] { int rowFirst, colFirst; // vị trí của chữ cái đầu tiên int rowSecond, colSecond; // vị trí của chữ cái thứ hai if [i + 1 == n || plaintext[i] == plaintext[i + 1]] { /* xử lí trường hợp plaintext có độ dài lẻ hoặc khi xuất hiện 2 chữ cái giống nhau trong 1 cặp */ rowFirst = posInMat[ int[plaintext[i]] ].row; colFirst = posInMat[ int[plaintext[i]] ].col; rowSecond = posInMat[ int[x] ].row; colSecond = posInMat[ int[x] ].col; --i; } else { rowFirst = posInMat[ int[plaintext[i]] ].row; colFirst = posInMat[ int[plaintext[i]] ].col; rowSecond = posInMat[ int[plaintext[i + 1]] ].row; colSecond = posInMat[ int[plaintext[i + 1]] ].col; } if [rowFirst == rowSecond] ciphertext += matrix[rowFirst][[colFirst + 1] % 5] + matrix[rowSecond][[colSecond + 1] % 5] else if [colFirst == colSecond] ciphertext += matrix[[rowFirst + 1] % 5][colFirst] + matrix[[rowSecond + 1] % 5][colSecond] else ciphertext += matrix[rowFirst][colSecond] + matrix[rowSecond][colFirst] } return ciphertext; }

Playfair Cipher cũng có những biến thể như four-square cipher [sử dụng 4 ma trận 5x5] và two-square cipher [sử dụng 2 ma trận 5x5], cũng nhóm theo cặp chữ cái và với những quy tắc mã hóa tương tự.

Tuy nhiên, khi nhóm theo cặp chữ cái, có khả năng cặp chữ cái này xuất hiện nhiều hơn cặp kia. Đúng vậy, nếu chỉ có ciphertext, và nếu ciphertext đủ dài [để thu được tần số xuất hiện chính xác hơn], ta có thể sử dụng Frequency Analysis.

Còn đối với ciphertext bất kì thì sao? Đến đây thì xin giới thiệu một phương pháp cryptanalysis mạnh hơn Ciphertext Only Attack. Đó là Known Plaintext Attack: Cho trước 1 hay nhiều cặp plaintext - ciphertext tương ứng, ta có thể thu lại được key bí mật, giúp chúng ta phá được bất kì ciphertext nào encrypt bằng key đó.

Lấy vì dụ ở phía trên: plaintext = hide the gold in the tree stump CIPHERTEXT = BM OD ZB XD NA BE KU DM UI XM MO UV IF Xét cặp de -> OD. Do chung 1 chữ d, 3 chữ cái o, d, e nằm trên cùng 1 hàng/cột và cạnh nhau. Ta thậm chí còn có thể thu được thứ tự xuất hiện trong ma trận của chúng. Tương tự với cặp ex -> XM Lưu ý, với cặp hi -> BM, có 2 trường hợp xảy ra. Hoặc là 4 chữ cái này tạo thành 4 góc của 1 hình chữ nhật, hoặc là chúng nằm trên cùng 1 hàng/cột [ví dụ như h b * i m]. Vì vậy, nên xử lí những cặp rơi vào trường hợp đầu tiên trước để tìm key dễ dàng hơn.

Hill Cipher

Được phát minh bởi Lester S. vào năm 1929, đây là một cipher sử dụng đại số tuyến tính [cụ thể hơn là phép nhân ma trận], phức tạp hơn về mặt thực hiện so với những cipher trước, vì thế có những máy chuyên dụng, hay máy tính, để thực hiện cipher này.

Cho plaintext = help. Nó sẽ được chia ra thành những khối n chữ cái. Mỗi khối như vậy sẽ thành vector có độ dài n. Key cũng sẽ là một ma trận, gọi là K. Để encrypt, ta sẽ thực hiện phép nhân ma trận K với từng vector của plaintext để cho ra vector ciphertext tương ứng. Như vậy điều kiện đầu tiên là K phải là ma trận vuông [Thật vậy, nếu K có chiều m x n, mỗi vector của plaintext có chiều n x 1 thì mỗi vector của ciphertext có chiều m x 1. Mà n = m nên K vuông] Mặt khác, giống như Affine Cipher, để đảm bảo encryption và decryption là 1-1, K phải có nghịch đảo mod 26. Giờ ta đã có được điều kiện của K, ta sẽ tạo ma trận K và thực hiện encryption. 1] 1 khối 4 chữ cái K = [13 4 6 10] [16 23 5 9] [ 3 12 9 7] [20 25 1 8] [h] = [ 7] [e] = [ 4] [l] = [11] [p] = [15] [13 4 6 10][ 7] mod 26 = [11] = [L] [16 23 5 9][ 4] [ 4] [E] [ 3 12 9 7][11] [13] [N] [20 25 1 8][15] [ 7] [H] CIPHERTEXT = LENH 2] 2 khối 2 chữ cái K = [3 3] [2 5] [h] = [7]; [l] = [11] [e] [4] [p] [15] [3 3][7] mod 26 = [7] = [H]; [3 3][11] mod 26 = [ 0] = [A] [2 5][4] [8] [I] [2 5][15] [19] [T] CIPHERTEXT = HIAT Đặc biệt, khi sử dụng chỉ 1 khối để encrypt, chỉ cần một thay đổi nhỏ trong plaintext sẽ xáo trộn cả ciphertext. Lấy cụ thể plaintext = hell, encrypt như trong trường hợp 1: CIPHERTEXT = XULB Tính chất trên khiến Hill Cipher có thể đứng vững trước Ciphertext Only Attack.

Tuy nhiên, do tính "tuyến tính" của cipher này, phương pháp Known Plaintext Attack sẽ có tác dụng.

Dẫu vậy, an toàn trước Ciphertext Only Attack là một thứ ít cipher trước đó có thể đạt được.

Transposition Cipher

Đây là một phạm trù cryptography sẽ nghe khá quen kể cả đối với những người không biết về cryptography: Những hệ thống kiểu này đổi vị trí của các chữ cái trong plaintext cho nhau!

Nhìn chung, những cryptosystem này đều rất dễ bị phá, kể cả trước Ciphertext Only Attack, vì thế ta sẽ không đi sâu vào chúng.

Ta sẽ lấy chung một plaintext = we are discovered flee at once 1] Rail fence cipher Sử dụng 3 "rail" thì ta có thể viết lại plaintext như sau: w . . . e . . . c . . . r . . . l . . . t . . . e . e . r . d . s . o . e . e . f . e . a . o . c . . . a . . . i . . . v . . . d . . . e . . . n . . Từ đó ciphertext là: WECRLTE ERDSOEEFEAOC AIVDEN 2] Scytale Đã được dùng từ thời Hy Lạp cổ đại, Scytale có cách sắp xếp như sau: w . . e . . a . . r . . e . . d . . i . . s . . c . o . . v . . e . . r . . e . . d . . f . . l . . . . e . . e . . a . . t . . o . . n . . c . . e . CIPHERTEXT = WOE EVE AEA RRT EEO DDN IFC SLE C Có những cách cũng sử dụng "rail" như 2 cipher trên, nhưng với thứ tự sắp xếp khác nhau và phức tạp hơn. Nhưng cũng có những cipher như sau. 3] Columnar transposition Chép plaintext như sau [với số thứ tự trên các cột là ngẫu nhiên]: 6 3 2 4 1 5 w e a r e d i s c o v e r e d f l e e a t o n c e Chép cipher theo cột và số thứ tự: EVLN ACDT ESEA ROFO DEEC WIREE

Scytale

Rõ ràng, không kí tự nào thực sự bị thay thế trong quá trình encryption, vì thế bằng một chút Frequency Analysis và Anagramming [tìm những phiên bản bị xáo trộn của một từ Tiếng Anh] ta đã có thể phá được nhiều Transposition Cipher.

Tạm kết

Trên đây là discussion cuối về những cryptosystem "cũ và yếu" trong làng crypto.

Bài viết sau vẫn sẽ chưa tiến tới những hệ thống hiện tại, nhưng sẽ về một hệ thống làm nền móng rất quan trọng cho cryptography hiện đại. Hãy đón xem!