Bài 10: Mật mã cổ điển – Mã hoá Caesar

0
19
Mã hoá cổ điển

Mật mã Caesar (hay còn được gọi là Mật mã của Caesar, Mật mã chuyển vị, Mã của Caesar hay Chuyển vị Caesar) là một trong những kỹ thuật mã hóa đơn giản và phổ biến nhất. Đây là một dạng mật mã thay thế, trong đó mỗi ký tự trên văn bản thô sẽ được thay bằng một ký tự khác, có vị trí cách nó một khoảng xác định trong bảng chữ cái.

Cũng giống như tất cả các dạng mật mã thay thế một bảng chữ cái khác, mật mã Caesar rất dễ bị phá giải và về cơ bản không đáp ứng đủ khả năng bảo mật thông tin liên lạc trong cuộc sống hiện đại.

Mã hoá caesar bằng cách thay thế các ký tự
Mã hoá caesar bằng cách thay thế các ký tự

Ví dụ về mật mã Caesar

Mã hoá caesar bằng cách thay thế các ký tự trong bản rõ bằng ký tự đứng sau nó ${\displaystyle k}$ vị trí trong bảng chữ cái. Giả sử ${\displaystyle k=3}$, ta có bảng chuyển đổi như sau:

Bảng đánh số các chữ cái tiếng Anh

Giả sử ta có bản rõ: TOIYEUVIETNAM

Như vậy, bản mã chiếu theo bảng chuyển đổi kia sẽ là: WRLBHXYLHWQDP

Để giải mã, ta thực hiện ngược lại bằng cách chuyển dịch từng kí tự của bản mã lùi về ${\displaystyle k}$ vị trí.

Tổng quát về mã hoá Caesar

Về tổng quát, Hệ mã Caesar dùng bảng chữ cái tiếng Anh với 26 (${\displaystyle n=26}$) chữ cái, được đánh số:

Bảng dịch mã Caesar Z26

Phương pháp mã hoá Ceasar được biểu diễn như sau:

Sơ đồ hệ mật mã: ${\displaystyle S = (P, C, K, E, D)}$.

Trong đó ${\displaystyle P=C=K=Z_{26}}$, với mỗi khoá ${\displaystyle k \in K}$ hàm mã hoá một ký tự ${\displaystyle x_{i} \in P}$ và hàm giải mã một ký tự ${\displaystyle y_{i} \in C}$ xác định theo công thức:

Mã hoá: ${\displaystyle y_{i}=e_{K}(x_{i})=(x_{i}+k){\pmod {n}}}$ (n=26)

Giải mã: ${\displaystyle x_{i}=d_{K}(y_{i})=(y_{i}-k){\pmod {n}}}$ (n=26)

Ví dụ và Cài đặt thuật toán mã hoá Caesar

Bài tập ví dụ

Câu 1: Cho ${\displaystyle k=17}$, Bản rõ ${\displaystyle ATTACK}$. Hãy thực hiện mã hóa bằng Caesar theo ${\displaystyle Z_{26}}$.

Đầu tiên, ta biểu diễn bản rõ theo modulo 26: ${\displaystyle X = ATTACK = (0, 19, 19, 0, 2, 10)}$

Dùng thuật toán mã hoá với ${\displaystyle k=17}$ ta có:

${\displaystyle y_{1}=e_{K}(x_{1})=(x_{1}+k){\pmod {n}} = (0+17) {\pmod {26}} = 17}$

${\displaystyle y_{2}=e_{K}(x_{2})=(x_{2}+k){\pmod {n}} = (19+17) {\pmod {26}} = 10}$

Tương tự:

${\displaystyle y_{3}=(x_{3}+k){\pmod {n}} = (19+17) {\pmod {26}} = 10}$

${\displaystyle y_{4}=17}$ , ${\displaystyle y_{5}=19}$ , ${\displaystyle y_{6}=1}$

Bản mã: ${\displaystyle Y=(17, 10, 10, 17, 19, 1)=RKKRTB}$

Câu 2: Cho ${\displaystyle k=12}$, cho bản mã ${\displaystyle Y = ZAFTUZSUYBAEEUNXQ}$. Giải mã dữ liệu và cho ra bản rõ theo mã dịch vòng Caesar

Biểu diễn bản mã theo ${\displaystyle Z_{26}}$:

${\displaystyle Y = ZAFTUZSUYBAEEUNXQ = (25, 0, 5, 19, 20, 25, 18, 20, 24, 1, 0, 4, 4, 20, 13, 23, 16)}$

Dùng thuật toán giải mã ${\displaystyle x_{i}=d_{K}(y_{i})=(y_{i}-k){\pmod {n}}}$

${\displaystyle x_{1}=d_{K}(y_{1})=(y_{1}-k){\pmod {n}} = (25-12) {\pmod {26}} = 13 \to N}$

${\displaystyle x_{2}=(0-12) {\pmod {26}} = 14 \to O}$${\displaystyle x_{3}=(5-12) {\pmod {26}} = 19 \to T}$
${\displaystyle x_{4}=7 \to H}$${\displaystyle x_{5}=8 \to I}$
${\displaystyle x_{6}=13 \to N}$${\displaystyle x_{7}=6 \to G}$
${\displaystyle x_{8}=8 \to I}$${\displaystyle x_{9}=12 \to M}$
${\displaystyle x_{10}=15 \to P}$${\displaystyle x_{11}=14 \to O}$
${\displaystyle x_{12}=18 \to S}$${\displaystyle x_{13}=18 \to S}$
${\displaystyle x_{14}=8 \to I}$${\displaystyle x_{15}=1 \to B}$
${\displaystyle x_{16}=11 \to L}$${\displaystyle x_{17}=4 \to E}$

Bản rõ: X = NOTHING IMPOSSIBLE

Cài đặt chương trình mã hoá Caesar

Chương trình online: https://onlinegdb.com/1QfWGJOiS

// A C++ program to illustrate Caesar Cipher Technique
#include <iostream>
using namespace std;

// This function receives text and shift and
// returns the encrypted text
string encrypt(string text, int s)
{
	string result = "";

	// traverse text
	for (int i=0;i<text.length();i++)
	{
		// apply transformation to each character
		// Encrypt Uppercase letters
		if (isupper(text[i]))
			result += char(int(text[i]+s-65)%26 +65);

	// Encrypt Lowercase letters
	else
		result += char(int(text[i]+s-97)%26 +97);
	}

	// Return the resulting string
	return result;
}

// Driver program to test the above function
int main()
{
	string text="ATTACKATONCE";
	int s = 4;
	cout << "Text : " << text;
	cout << "\nShift: " << s;
	cout << "\nCipher: " << encrypt(text, s);
	return 0;
}

Xem thêm cách cài đặt trên các ngôn ngữ khác: https://www.geeksforgeeks.org/caesar-cipher-in-cryptography/

Thám mã Caesar

Thám mã Caesar khá đơn giản. Xét 2 tình huống:

  1. Người thám mã biết (đoán) rằng đây là một dạng mã hoá thay thế cơ bản nhưng không biết cụ thể nó là Caesar.
  2. Người thám mã biets chính xác mật mã Caesar được sử dụng.

Dù trong tình hướng nào, việc thám mã với hệ mật này cũng khá đơn giản.

Trong trường hợp đầu tiên, mật mã có thể phá giải bằng các phương pháp tương tự như đối với các dạng mật mã thay thế đơn giản nói chung, chẳng hạn như phân tích tần suất hay phân tích các từ mẫu.[16] Khi phân tích, có khả năng người giải mã sẽ nhanh chóng nhận thấy tính quy tắc trong giải pháp thay thế và suy ra rằng kỹ thuật mã hóa được dùng là mật mã Caesar.

Trong trường hợp thứ hai, công việc giải mã thậm chí còn nhẹ nhàng hơn. Vì số khóa mã có khả năng được sử dụng là giới hạn (25 khóa mã đối với bảng chữ cái tiếng Anh), mỗi khóa mã có thể được kiểm tra lần lượt bằng kiểu tấn công vét cạn. Một cách để thực hiện là thử giải một đoạn trích nhỏ của bản mật mã với tất cả các khóa mã có thể, và viết lên trên một bảng,đôi khi gọi là “giải mã một phần bản thô”.

Bài tập

  1. Giải mã bản mã sau, giả sử mã hóa Caesar được sử dụng để mã hóa với k=3: IRXUVFRUHDQGVHYHQBHDUVDJR
  2. Phá mã bản mã sau, giả sử mã hóa Caesar được sử dụng: CSYEVIXIVQMREXIH
  3. Hãy giải mã bản mã được mã hóa bằng hệ mã Caesar sau (sử dụng bảng mã tiếng Anh): WKXPEVXS
  4. Bản rõ “HELPME” được mã hóa thành bản mã “DAHLIA”. Hãy tìm K biết bản mã được hình thành theo Caesar thuộc Z26
  5. Viết chương trình mã hóa và giải mã một file văn bản ASCII trên máy tính bằng phương pháp mã hóa Caesar.