Bài 12: Mã hóa Vigenère

Trong các loại mã hóa cổ điển được giới thiệu ở bài trước: mã hóa Caesar, mã hóa Affine, được gọi chung là mã thay thế dùng một bảng chữ cái (monoalphabetic substitution cipher). Nghĩa là ta dùng một ánh xạ các chữ cái trong bảng mã thành bản rõ và tất cả các chữ cái trong bản mã đều dùng chung một ánh xạ.

Yếu điểm của loại mã này là bản mã sẽ giữ lại các đặc điểm mẫu từ và tần xuất của văn bản gốc. Để loại bỏ yếu điểm trên, các nhà lập mã đã tạo ra một hệ mã khác gọi là mã thay thế dùng nhiều bảng chữ cái (polyalphabetic substitution cipher).

Hệ mã này được đặt theo tên của một nhà mật mã học người Pháp Blaise de Vigenère (1523-1596). Mật mã Vigenère là một dạng đơn giản của mật mã thay thế dùng nhiều bảng chữ cái.

Mô tả thuật toán mã hóa Vigenère

Sử dụng bảng mã hoá Vigenère

Để mã hóa, ta dùng một hình vuông Vigenère (hình dưới).Gồm 26 hàng, mỗi hàng dịch về bên trái một bước so với hàng phía trên, tạo thành 26 bảng mã Caesar. Trong quá trình mã hóa, tùy theo từ khóa mà mỗi thời điểm ta dùng một dòng khác nhau để mã hóa văn bản.

Ví dụ, ta có văn bản cần mã hóa như sau: ATTACKATDAWN

Người gửi lựa chọn một từ khóa và viết nó lặp lại nhiều lần trên một dòng đến khi số chữ cái trên dòng bằng số chữ cái trong thông điệp, với từ khóa “LEMON” thì: LEMONLEMONLE

Chữ cái đầu tiên của văn bản, A, được mã hóa bằng bảng bắt đầu với L (chữ cái đầu tiên của từ khóa). Nó sẽ được mã hóa thành chữ cái trên dòng L và cột A của hình vuông Vigenère, đó là chữ L. Tương tự như vậy, chữ cái thứ hai của văn bản sẽ được mã hóa bằng chữ cái thứ hai của từ khóa: chữ trên dòng E và cột T là X. Sau đây là bản mã:

Để hiểu rõ hơn về cách tra bảng, bạn có thể theo dõi video sau:

Thuật toán mã hóa Vigenère

Đối với hệ mã hoá này không gian các bản mã và bản rõ là các thông điệp được tạo thành từ một bảng chữ cái A (giống hệ mã Caesar). Các chữ cái được đánh số từ ${ 0 }$ tới ${ n-1 }$ trong đó ${ n }$ là số phần tử của bảng chữ cái.

Không gian khoá ${ K }$ được xác định như sau:

Với ${ m }$ là một số nguyên dương, khoá ${ K }$ là một xâu ký tự có độ dài ${ m }$

Định nghĩa sơ đồ hệ mật mã: $${ P=C=K=(Z_n)^m }$$

Với khoá ${ K=(k_1, k_2, k_3, k_4, …, k_m) }$

Để mã hoá một bản rõ ${P}$, ta chia ${P}$ thành các đoạn có độ dài ${m}$ và chuyển thứ tự tương ứng của chúng trong bảng không gian mã. Chẳng hạn ${X=(x_1, x_2, x_3, …, x_m)}$. Khi đó quá trình mã hoá và giải mã được thực hiện như sau:

${e_{K}(x_1, x_2, x_3, …, x_m)=\{(x_1+k_1){\pmod {n}}, …, (x_m+k_m){\pmod {n}}\}}$

${d_{K}(y_1, y_2, y_3, …, y_m)=\{(y_1-k_1){\pmod {n}}, …, (y_m-k_m){\pmod {n}}\}}$

Với ${n}$ là không gian mã hoá, ${Y=y_1y_2y_3…y_m}$ là một đoạn bảng mã; ${X, Y \in (Z_n)^m}$

Về thực chất hệ mã hoá này là sự kết hợp mã hoá Caesar nhiều lần. Nếu trong Caesar ta thay thế từng ký tự đơn lẻ thì trong hệ mã hoá Vigenere sẽ thay thế từng bộ ${m}$ ký tự liên tiếp. Với mỗi ${m}$ ký tự, ta có số khoá có thể sử dụng là ${n^m}$, cụ thể với bảng chữ cái tiếng anh sẽ có ${26^m}$ khoá có thể sử dụng.

Ví dụ & Chương trình Mã hoá Vigenère

Bài tập ví dụ

Ví dụ: Xét không gian mã hoá là bảng chữ cái tiếng anh, có ${n=26}$. Giả sử khoá K=”CIPHER” có độ dài ${m=6}$, bản rõ P = “THIS CRYPTOSYSTEM IS NOT SECURE”

Ta có K = 2 8 15 7 4 17

P = 19 7 8 18 2 17 | 24 15 19 14 18 23 | 18 19 4 12 8 18 | 13 14 19 18 4 2 | 20 17 4

Quá trình mã hoá ${e_{K}(x_1, x_2, x_3, …, x_m)=\{(x_1+k_1){\pmod {n}}, …, (x_m+k_m){\pmod {n}}\}}$ thực hiện như sau:

Vậy bản mã tương ứng sẽ là: C = “VPXZGI AXIVWO UBTTMJ PWIZIT WZT”

Chương trình cài đặt mã hoá Vigenère

Tham khảo thêm cách cài đặt bằng các ngôn ngữ khác trên: https://www.geeksforgeeks.org/vigenere-cipher/

Thám mã Vigenère

Trước hết, ngoài mật mã thì ta còn cần từ khóa (lấy ví dụ như trên). Đầu tiên, ta lấy chữ cái đầu tiên của từ khóa (ở đây là chữ cái L), sau đó tìm chữ cái đó ở hàng ngang đầu tiên của bảng mã. Từ chữ cái tìm được, ta dóng xuống chữ cái cùng thứ tự của mã (ở đây là chữ cái L). Rồi ta di chuyển tới chữ cái tương ứng ở cột dọc đầu tiên từ trái sang phải. Dần dần ta sẽ giải hết mật mã.

Bài tập Vigenere

Bài tập 1: Mã hóa từ ‘explanation’ bằng phương pháp Vigenere, từ khóa là LEG.

Bài tập 2: Cho hệ mã hoá Vigenere có m=6, K=”CIPHER”.

– Hãy thực hiện mã hoá xâu P = “THIS IS MY TEST”

– Hãy thực hiện giải mã xâu C = “EICJIC RTPUEI GBGLEK CBDUGV”

Bài tập 3: Xét phương pháp Vigenere. Giả sử biết bản mã “PVRLHFMJCRNFKKW” có bản rõ tương ứng là “networksecurity”. Hãy tìm khóa K.

Bài tập 4: Cho hệ mã Vigenere có m=6. Mã hoá xâu P = “THIS IS MY TEST” thu được bản mã “LLKJML ECVVWM”

– Hãy tìm khoá mã hoá đã dùng cho hệ mã trên.

– Dùng khoá tìm được ở trên, giải bản mã “KLGZWT OMBRVW”

Bài tập 5: Cho hệ mã Vigenere có m=6. Mã hoá xâu P = “SPIRIT” thu được bản mã “OXHRZW”

– Hãy tìm khoá mã hoá đã dùng cho hệ mã trên.

– Dùng khoá tìm được ở trên, giải bản mã “BQETYH HMBEEW”

Bài tập 6: Cho hệ mã Vigenere có m=6. Giải mã xâu P = “RANJLV” thu được bản rõ “CIPHER”

– Hãy tìm khoá mã hoá đã dùng cho hệ mã trên.

– Dùng khoá tìm được ở trên, giải bản mã “PLDKCI DUJQJO”

Bài tập 7: Hãy giải mã bản mã được mã hoá bằng hệ mã Vigenere sau, xác định khoá mã hoá và bản rõ. Biết không gian mã hoá gồm các chữ cái trong bảng chữ cái tiếng anh.

IGDLK MJSGC FMGEP PLYRC IGDLA TYBMR KDYVY XJGMR TDSVK ZCCWG ZRRIP
UERXY EEYHE UTOWS ERYWC QRRIP UERXJ QREWQ FPSZC ALDSD ULSWF FFOAM
DIGIY DCSRR AZSRB GNDLC ZYDMM ZQGSS ZBCXM OYBID APRMK IFYWF MJVLY
HCLSP ZCDLC NYDXJ QYXHD APRMQ IGNSU MLNLG EMBTF MLDSB AYVPU TGMLK
MWKGF UCFIY ZBMLC DGCLY VSCXY ZBVEQ FGXKN QYMIY YMXKM GPCIJ HCCEL
PUSXF MJVRY FGYRQ 

Tài liệu tham khảo:

• Giáo trình An toàn và bảo mật thông tin, Trường Đại học Hàng Hải Hải Phòng
• https://vi.wikipedia.org/wiki/Mật_mã_Vigenère