Trang chủ Kỹ Thuật Số Cryptography Cổ Điển – Phần 3

Cryptography Cổ Điển – Phần 3

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 mạng lưới 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 mạng lưới hệ thống này mã hóa theo nhóm vần âm thay vì từng vần âm .

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 ý tưởng bởi Charles Wheatstone vào 1854 và được truyền bá thoáng đãng bởi Nam tước Playfair, cryptosystem này sử dụng rất nhanh gọn, thuận tiện và dễ thực thi bằng tay mà không cần dụng cụ chuyên sử dụng nào, vì vậy nó được quân đội Anh sử dụng thoáng đãng trong những cuộc 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 vần âm và với những quy tắc mã hóa tương tự như .
Tuy nhiên, khi nhóm theo cặp vần âm, có năng lực cặp vần âm này Open 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ố Open đúng mực hơn ), ta hoàn toàn có thể sử dụng Frequency Analysis .
Còn so với ciphertext bất kể thì sao ? Đến đây thì xin ra mắt một giải 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 hoàn toàn có thể thu lại được key bí hiểm, giúp tất cả 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, giải pháp Known Plaintext Attack sẽ có tính năng .
Dẫu vậy, bảo đảm an toàn trước Ciphertext Only Attack là một thứ ít cipher trước đó hoàn toàn có thể đạt được .

Transposition Cipher

Đây là một phạm trù cryptography sẽ nghe khá quen kể cả so với những người không biết về cryptography : Những mạng lưới hệ thống kiểu này đổi vị trí của những vần âm 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ì vậy 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 - Wikipedia

Scytale

Rõ ràng, không kí tự nào thực sự bị thay thế sửa chữa trong quy trình encryption, vì vậy bằng một chút ít Frequency Analysis và Anagramming ( tìm những phiên bản bị trộn lẫn của một từ Tiếng Anh ) ta đã hoàn toàn 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 mạng lưới hệ thống hiện tại, nhưng sẽ về một mạng lưới hệ thống làm nền móng rất quan trọng cho cryptography tân tiến. Hãy đón xem !

Cryptography Cổ Điển – Phần 3
Bài viết liên quan
Sửa máy giặt
Bài Mới Nhất
Hotline 24/7: O984.666.352
Alternate Text Gọi ngay