Mật mã Affine là một dạng mật mã thay thế dùng một bảng chữ cái, trong đó mỗi chữ cái được ánh xạ tới một số sau đó mã hóa qua một hàm số toán học đơn giản. Một phép dịch Caesar là mật mã Affine, trong đó các chữ cái được mã hóa với hàm ${(x+b)\mod (26)}$ , với ${b}$ là bước dịch.
Mô tả thuật toán mã hoá Affine
Trong mật mã Affine, đầu tiên bảng chữ cái của thông điệp cần mã hóa có kích thước ${n}$ sẽ được chuyển thành các con số tự nhiên từ ${0..n-1}$. Sau đó dùng một hàm mô đun để mã hóa và chuyển thành bản mã.
Sơ đồ hệ mật mã: ${S = (P, C, K, E, D)}$.
Trong đó ${P=C=Z_{n}}$
${K = \{(a, b) \in Zn*Zn , GCD(a,n) = 1\}}$
Các hàm lập mã và giải mã được xác định bởi:
${e_{k}(x)=(ax+b){\pmod {n}}}$
${d_{k}(y)=(a^{-1}*(y-b)){\pmod {n}}}$
Với ${a^{-1}}$ là nghịch đảo của ${a}$ theo mô đun ${n}$.
Tức là ${1=a*a^{-1}{\pmod {n}}}$
Để tính ${a^{-1}}$ ta dùng Giải thuật Euclide mở rộng
Điều kiện:
- ${e_k}$ phải là song ánh ${\forall y \in Z_n, \exists!x \in Z_n, ax+b \equiv y \pmod n}$
- ${a}$ và ${n}$ là 2 số nguyên tố cùng nhau ${GCD(a, n)=1}$
Chú ý:
Khi ${a=1}$ ta có mã dịch vòng Caesar, Với n=26, a = {3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25}
Ví dụ & Cài đặt chương trình mã hoá Affine
Bài tập ví dụ
Ví dụ 1: Cho bản rõ ${X = ATTACK}$, mã hóa Affine trên ${Z_26}$ với ${K = (5, 3)}$
Biểu diễn bản rõ theo modulo 26:
${X = ATTACK = (0, 19, 19, 0, 2, 10)}$
Dùng thuật toán mã hoá với ${k = (a, b) = (5, 3)}$ ta có:
${y_1 = e_k(x_1) = (ax_1+b) \pmod n = (5*0+3) \pmod {26} = 3}$
${y_2 = e_k(x_2) = (ax_2+b) \pmod n = (5*19+3) \pmod {26} = 20}$
${y_3 = e_k(x_3) = (ax_3+b) \pmod n = (5*19+3) \pmod {26} = 20}$
${y_4 = e_k(x_4) = (ax_4+b) \pmod n = (5*0+3) \pmod {26} = 3}$
${y_5 = e_k(x_5) = (ax_5+b) \pmod n = (5*2+3) \pmod {26} = 13}$
${y_6 = e_k(x_6) = (ax_6+b) \pmod n = (5*10+3) \pmod {26} = 1}$
Bản mã: ${Y=DUUDNB}$
Ví dụ 2: Hãy giải mã thông điệp “AXG” bằng hệ mã Affine với ${K = (a, b) = (7, 3)}$ trên ${Z_{26}}$
Biểu diễn bản mã theo ${\displaystyle Z_{26}}$:
${Y = AXG = (0, 23, 6)}$
Dùng thuật toán Affine giải mã với ${k = (a, b) = (7, 3)}$ ta có:
${x_1=d_k(y_1)=a^{-1}(y_1-b) \pmod n = 7^{-1}(0-3) \pmod {26}}$
${= (7^{-1} \pmod {26} * (-3) \pmod {26})\pmod {26}}$
${= (15*23)\pmod {26} = 7}$
${x_2= 7^{-1}(23-3) \pmod {26}}$
${= (7^{-1} \pmod {26} * (20) \pmod {26})\pmod {26}}$
${= (15*20)\pmod {26} = 14}$
${x_3= 7^{-1}(6-3) \pmod {26}}$
${= (7^{-1} \pmod {26} * (3) \pmod {26})\pmod {26}}$
${= (15*3)\pmod {26} = 19}$
Bản rõ: ${X = HOT}$
Cài đặt chương trình mã hoá Affine
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/implementation-affine-cipher/
//CPP program to illustrate Affine Cipher
#include<bits/stdc++.h>
using namespace std;
//Key values of a and b
const int a = 17;
const int b = 20;
string encryptMessage(string msg)
{
///Cipher Text initially empty
string cipher = "";
for (int i = 0; i < msg.length(); i++)
{
// Avoid space to be encrypted
if(msg[i]!=' ')
/* applying encryption formula ( a x + b ) mod m
{here x is msg[i] and m is 26} and added 'A' to
bring it in range of ascii alphabet[ 65-90 | A-Z ] */
cipher = cipher +
(char) ((((a * (msg[i]-'A') ) + b) % 26) + 'A');
else
//else simply append space character
cipher += msg[i];
}
return cipher;
}
string decryptCipher(string cipher)
{
string msg = "";
int a_inv = 0;
int flag = 0;
//Find a^-1 (the multiplicative inverse of a
//in the group of integers modulo m.)
for (int i = 0; i < 26; i++)
{
flag = (a * i) % 26;
//Check if (a*i)%26 == 1,
//then i will be the multiplicative inverse of a
if (flag == 1)
{
a_inv = i;
}
}
for (int i = 0; i < cipher.length(); i++)
{
if(cipher[i]!=' ')
/*Applying decryption formula a^-1 ( x - b ) mod m
{here x is cipher[i] and m is 26} and added 'A'
to bring it in range of ASCII alphabet[ 65-90 | A-Z ] */
msg = msg +
(char) (((a_inv * ((cipher[i]+'A' - b)) % 26)) + 'A');
else
//else simply append space character
msg += cipher[i];
}
return msg;
}
//Driver Program
int main(void)
{
string msg = "AFFINE CIPHER";
//Calling encryption function
string cipherText = encryptMessage(msg);
cout << "Encrypted Message is : " << cipherText<<endl;
//Calling Decryption function
cout << "Decrypted Message is: " << decryptCipher(cipherText);
return 0;
}
Thám mã Affine
Mã Affine là một hệ mã yếu. Có 12 số a ∈ Z26 thỏa mãn gcd(a, 26) = 1. Như vậy tập khóa K chỉ có 12 x 26 = 312 phần tử. Ta dễ dàng dùng thuật toán Brute-force để thám mã.
Giả sử ta mở rộng tập kí tự P và C bao gồm cả các kí tự chữ hoa, chữ thường, chữ số, kí tự đặc biệt:
“”” !”#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[]^_`abcdefghijklmnopqrstuvwxyz{|}~”””
Tập này có 95 phần tử, lúc đó a có 75 khả năng nên tập khóa K có 75 x 95 = 7125 phần tử. Với sức mạnh của máy tính, ta vẫn có thể dễ dàng thử hết các khả năng bằng thuật toán Brute-force.
Bài tập Affine
- Một trường hợp tổng quát của mã hóa Caesar là mã Affine, trong đó ký tự p được mã hóa thành ký tự c theo công thức:
- C = E(p, [a, b]) = (ap + b) mod 26
- Một yêu cầu của thuật toán mã hóa là tính đơn ánh, tức nếu p≠q thì E(p) ≠E(q). Mã Affine không phải là đơn ánh với mọi a.
- Ví dụ, với a=2, b=3 thì E(0) = E(13) = 3.
- a) Có điều kiện gì đặt ra cho b hay không? Tại sao?
- b) Xác định những giá trị của a làm cho mã Affine không đơn ánh.
- Cho hệ mã Affine được cài đặt trên ${Z_{99}}$. Khi đó khoá là các cặp ${(a, b)}$ trong đó ${a, b \in Z_{99}}$ với ${GCD(a, 99)=1}$. Hàm mã hoá ${e_{k}(x)=(ax+b){\pmod {99}}}$ và giải mã ${d_{k}(y)=(a^{-1}*(y-b)){\pmod {99}}}$
- Hãy xác định số khoá có thể được sử dụng cho hệ mã trên.
- Nếu như khoá giải mã là ${K^{-1}=(16, 7)}$, hãy thực hiện mã hoá xâu m = “DANGER”
- Cho hệ mã Affine được cài đặt trên ${Z_{55}}$.
- Hãy xác định số khoá có thể được sử dụng cho hệ mã trên.
- Nếu như khoá giải mã là ${K^{-1}=(13, 17)}$, hãy xác định khoá mã hoá
- Cho hệ mã Affine được cài đặt trên ${Z_{99}}$.
- Hãy xác định số khoá có thể được sử dụng cho hệ mã trên.
- Nếu như khoá mã hoá là ${K=(16, 7)}$, hãy xác định khoá giải mã
