[Crypto] 03 – Mã Affine

Mã hóa

So với mã Caesar, mã Affine phức tạp hơn một chút ít, và cần có một chút ít kỹ năng và kiến thức về số học. Tôi sẽ khởi đầ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:

Bạn đang đọc: [Crypto] 03 – Mã Affine

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, tất cả chúng ta cùng tìm hiểu và khám phá qua 1 số ít 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ự phối hợp của mã nhân và mã Caesar. Hàm lập mã và hàm giải thuật 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ễ tưởng tượng :

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ố ít 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ự như 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.

Xem thêm: TOP 5 game tư duy trí tuệ cực hấp dẫn để luyện não

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 lan rộng ra tập kí tự P. và C gồm có cả những kí tự chữ hoa, chữ thường, chữ số, kí tự đặc biệt quan trọng :

 “”” !”#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[]^_`abcdefghijklmnopqrstuvwxyz{|}~”””

Tập này có 95 thành phần, lúc đó a có 75 năng lực nên tập khóa K có 75 x 95 = 7125 thành phần. Với sức mạnh của máy tính, ta vẫn hoàn toàn có thể thuận tiện thử hết những năng lực bằng thuật toán Brute-force .
OK, đã xong mớ triết lý 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à tất cả chúng ta đã hiểu về hệ mã Affine cũng như thiết lập cách mã hóa, thám mã đơn cử bằng python. Tiếp theo đây, tôi sẽ ra mắt một hệ mã cổ xưa khác : Mã thay thế sửa chữa ( Substution Cipher ) .
Download mã nguồn AffineCipher. py
< < Bài 2 – Mã Caesar Bài 4 – Mã thay thế sửa chữa ( Phần 1 ) Advertisement

Chia sẻ:

• Twitter
• Facebook

Thích bài này:

Thích

Xem thêm: Tìm việc Làm Giám đốc Đầu tư và Phát triển Dự án Tuyển Dụng 19/04/2023 | https://thomaygiat.com

Đang tải …

Có liên quan

Source: https://thomaygiat.com
Category : Kỹ Thuật Số