[Crypto] 03 – Mã Affine - Nhat Truong Blog

Mã hóa

So với mã Caesar, mã Affine phức tạp hơn một chút, và cần có một ít kiến thức về số học. Tôi sẽ bắt đầu luôn với việc định nghĩa sơ đồ hệ mã Affine:

S = (P, C, K, E, D)

Trong đó P = C = Z26 , K = {(a, b) ∈ Z26 x Z26 | gcd(a, 26) = 1} , các hàm lập mã và giải mã được cho bởi:

E(p, k) = (a * p + b) mod 26

D(c, k) = a-1 (c - b) mod 26

Tuy nhiên trước khi hiểu được hệ mã này, chúng ta cùng tìm hiểu qua một số khái niệm.

Mã Nhân (Multiplicative Cipher)

Trong Mã Caesar, để mã hóa ta dịch chuyển từng kí tự của bản rõ lên k bước. Nó được xem là một dạng mã cộng. Hàm lập mã và hàm giải mã được định nghĩa như sau:

E(p, k) = (p + k) mod 26

D(c, k) = (c - k) mod 26

Nếu thay phép cộng trong 2 hàm trên bằng phép nhân, ta sẽ có hệ mã nhân.

E(p, k) = (p * k) mod 26

D(c, k) = (c * k) mod 26

Và Mã Affine chính là sự kết hợp của mã nhân và mã Caesar. Hàm lập mã và hàm giải mã của mã Affine được định nghĩa:

E(p, k) = (a * p + b) mod 26

D(c, k) = a-1 (c - b) mod 26

Trong đó khóa k là một bộ gồm 2 thành phần k = (a, b) và kí hiệu a-1 chỉ module nghịch đảo của a. Vậy module nghịch đảo là gì, tôi sẽ giải thích sau.

Tôi sẽ lấy ví dụ về mã Affine để bạn đọc dễ hình dung:

Giả sử khóa k của tôi là bộ số k = (8, 2) khi đó tập bản rõ P sau khi thực hiện mã hóa với hàm E ở trên sẽ được tập bản mã C như sau (bạn đọc hãy tự thực hiện hàm E này):

P: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

C: C K S A I Q Y G O W E M U C K S A I Q Y G O W E M U

Ta có nhận xét là một số kí tự bản rõ sẽ được mã hóa thành cùng một kí tự bản mã: ví dụ cặp D, Q đều được mã hóa thành A; tương tự cặp J và W cùng được mã hóa thành W. Như vậy nếu ta nhận được một bản mã có chứa kí tự A, ta sẽ không biết bản rõ tương ứng là D hay Q.

Để hạn chế nhược điểm này, có 1 cách đó là ta chọn a sao cho a và m (ở đây m = 26) là hai số nguyên tố cùng nhau, tức là ước số chung lớn nhất của a và m là 1: gcd(a, m) = 1. Nếu chọn k = (8, 2) thì vì gcd(8, 26) ≠ 1 nên sẽ gây hiện tượng trên, thay vào đó nếu ta chọn k = (7, 2) thì sẽ không gặp vấn đề trùng mã. Việc chọn a như vậy cũng đảm bảo tính khả nghịch của a tức là a-1 luôn tồn tại.

Module nghịch đảo của một số

Module nghịch đảo của một số a kí hiệu a-1 theo mod m là một số i sao cho:

(a * i) = 1 (mod m)

tức là (a * i) chia cho m sẽ dư 1.

Để tìm i đơn giản nhất là dùng thuật toán Brute-force với i tăng dần 1, 2, … đến khi nào thỏa mãn hệ thức trên thì thôi. Nhưng với a lớn thì thuật toán Brute-force sẽ rất mất thời gian. Có một cách hiệu quả hơn đó là dùng Giải thuật Euclide mở rộng để tính a-1. Nội dung của thuật toán nằm ngoài phạm vi của bài viết này, ở đây tôi chỉ hướng dẫn cách áp dụng vào bài toán mã hóa của chúng ta.

Thám mã

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.

OK, đã xong mớ lý thuyết lùng bùng, ta bắt tay vào code thôi

Code

LETTERS = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ' # Return Greatest Common Divisor of a and b def gcd(a, b): while a != 0: a, b = b % a, a return b # Return Inverse Module of a with mod m def inverseMod(a, m): if gcd(a, m) != 1: return None u1, u2, u3 = 1, 0, a v1, v2, v3 = 0, 1, m while v3 != 0: q = u3 // v3 v1, v2, v3, u1, u2, u3 = (u1 - q * v1), (u2 - q * v2), (u3 - q * v3), v1, v2, v3 return u1 % m # Return Affine Cipher with MODE encrypt or decrypt def affine_cipher(message, MODE, key): message = message.upper() translated = '' modInverseOfKeyA = inverseMod(key[0], len(LETTERS)) if modInverseOfKeyA == None: return None for symbol in message: if symbol in LETTERS: symIndex = LETTERS.find(symbol) if MODE.upper() == 'ENCRYPT': translated += LETTERS[(symIndex * key[0] + key[1]) % len(LETTERS)] elif MODE.upper() == 'DECRYPT': translated += LETTERS[(symIndex - key[1]) * modInverseOfKeyA % len(LETTERS)] else: translated += symbol return translated message = """"A computer would deserve to be called intelligent if it could deceive a human into believing that it was human." -Alan Turing""" key = (7, 2) cipher = affine_cipher(message, 'ENCRYPT', key) print('nnPlain text: ' + message) print('nnCipher text: ' + cipher) message = affine_cipher(cipher, 'DECRYPT', key) print('nnPlain text after decrypt: ' + message)

Hàm gcd(a, b) tính ước số chung lớn nhất của 2 số a, b theo thuật toán Euclide.

Hàm inverseMod(a, m) tính module nghịch đảo của a theo mod m bằng thuật toán Euclide mở rộng. Nếu a bất khả nghịch thì trả về None.

Hàm affine_cipher(message, MODE, key) thực hiện mã hóa hoặc giải mã message tùy theo MODE được đặt ở chế độ ‘ENCRYPT‘ hay ‘DECRYPT‘. Ở đây key là 1 tupple gồm 2 thành phần key[0] và key[1] đại diện cho a và b. Nếu chọn key không phù hợp, tức a không khả nghịch thì hàm trả về None.

Kết quả chạy chương trình:

Để thám mã, tôi viết hàm affine_crack(cipher), hàm trả về một tupple gồm 3 thành phần (a, b, message). Nếu không thể phá mã, hàm trả về None

import detectEnglish # Crack Affine Cipher def affine_crack(cipher): for a in range(0, len(LETTERS)): if gcd(a, len(LETTERS)) == 1: for b in range(0, len(LETTERS)): message = affine_cipher(cipher, 'DECRYPT', (a, b)) if detectEnglish.isEnglish(message): return (a, b, message) return (None, None) message = """"A computer would deserve to be called intelligent if it could deceive a human into believing that it was human." -Alan Turing""" key = (7, 2) cipher = affine_cipher(message, 'ENCRYPT', key) print('nnPlain text: ' + message) print('nnCipher text: ' + cipher) message = affine_crack(cipher) print('nnKey = ({0}, {1})'.format(message[0], message[1])) print('nPlain text after crack: ' + message[2])

Bạn đọc chú ý, ở đây tôi có import module detechEnglish được giới thiệu trong bài Kiểm tra một đoạn văn bản có phải Tiếng Anh hay không.

Kết quả trả về:

Lời kết

Vậy là chúng ta đã hiểu về hệ mã Affine cũng như cài đặt cách mã hóa, thám mã cụ thể bằng python. Tiếp theo đây, tôi sẽ giới thiệu một hệ mã cổ điển khác: Mã thay thế (Substution Cipher).

Download mã nguồn AffineCipher.py

<< Bài 2 – Mã Caesar

Bài 4 – Mã thay thế (Phần 1)

Chia sẻ:

• X
• Facebook

Thích Đang tải...

Có liên quan