密码学-仿射密码

仿射密码

一.密码体制分析

仿射密码本质上是一种替换密码，使用加密函数对每个字母逐个加密。

加密函数 E(x) = (ax + b)(mod m)

其中m为加密表中字母数量，一般取26。

b一般为常数。

a与m需要互质，即gcd(a,m)==1

解密函数 D(x) = a^-1(x - b)(mod m)

其中a^-1是a在乘法群中的逆元，可以用扩展欧几里得算法求得。

二.加密与解密实例分析

我们可以设置加密函数为E(x) = (3x + 1)(mod 26)，加密表为26个英文字母。

设置明文为 QFNUHELLO,根据加密原理可以得到下面的表格

明文	Q	F	N	U	H	E	L	L	O
x	16	5	13	20	7	4	11	11	14
3x+1	49	16	40	61	22	13	34	34	43
3x+1(mod 26)	23	16	14	9	22	13	8	8	17
密文	X	Q	O	J	W	N	I	I	R

这样我们得到加密后的密文为XQOJWNIIR

利用拓展欧几里得算法可以求得3在模26下的乘法逆元为9。

逐个字母代入解密函数进行解密即可得到解密后明文为QFNUHELLO

三.代码实现与分析

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def mod_inverse(a, m):
    for i in range(1, m):
        if (a * i) % m == 1:
            return i
    return None

def affine_encrypt(text, key):
    result = ""
    a, b = key
    for char in text:
        if char.isalpha():
            if char.isupper():
                result += chr((a * (ord(char) - 65) + b) % 26 + 65)
            else:
                result += chr((a * (ord(char) - 97) + b) % 26 + 97)
        else:
            result += char
    return result

def affine_decrypt(ciphertext, key):
    result = ""
    a, b = key
    a_inv = mod_inverse(a, 26)
    if a_inv is None:
        raise ValueError("密钥错误！！！")
    for char in ciphertext:
        if char.isalpha():
            if char.isupper():
                result += chr((a_inv * (ord(char) - 65 - b)) % 26 + 65)
            else:
                result += chr((a_inv * (ord(char) - 97 - b)) % 26 + 97)
        else:
            result += char
    return result

# 例子
text = "QFNUHELLO"
key = (3, 1)  # 选择合适的a和b值
encrypted_text = affine_encrypt(text, key)
decrypted_text = affine_decrypt(encrypted_text, key)

print("原文:", text)
print("加密后:", encrypted_text)
print("解密后:", decrypted_text)

还是对上面明文“QFNUHELLO”进行加解密，可以得到如下结果

四.仿射密码破解

破解可以采用下面的几种方式

1. 尝试所有可能的密钥组合： 由于仿射密码的密钥是由两个整数（a和b）组成，可以通过尝试所有可能的组合来进行破解。
2. 使用统计信息： 如果无法尝试所有可能的组合，可以利用语言的统计信息。例如，在英语中，字母频率是有规律的，其中 ‘e’ 是最常用的字母。通过分析密文中的字母频率，可以尝试匹配常见的字母频率分布，从而推测可能的密钥。
3. 检查结果的合理性： 解密后的文本应该具有合理的语法和意义。如果得到的结果看起来毫无意义，可能需要调整密钥。

这里用暴力破解法进行仿射密码的破解，依旧采用QFNUHELLO加密后的密文为例：

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def mod_inverse(a, m):
    for i in range(1, m):
        if (a * i) % m == 1:
            return i
    return None

def affine_decrypt(ciphertext, key):
    result = ""
    a, b = key
    a_inv = mod_inverse(a, 26)
    if a_inv is None:
        raise ValueError("The key is not valid for decryption.")
    for char in ciphertext:
        if char.isalpha():
            if char.isupper():
                result += chr((a_inv * (ord(char) - 65 - b)) % 26 + 65)
            else:
                result += chr((a_inv * (ord(char) - 97 - b)) % 26 + 97)
        else:
            result += char
    return result

def brute_force_affine(ciphertext):
    for a in range(1, 26):
        if gcd(a, 26) == 1:
            for b in range(26):
                possible_key = (a, b)
                decrypted_text = affine_decrypt(ciphertext, possible_key)
                print(f"Attempted Key: {possible_key}, Decrypted Text: {decrypted_text}")

# 例子
encrypted_text = "XQOJWNIIR"
brute_force_affine(encrypted_text)

破解后可以得到下面的结果：

参考文章：https://www.cnblogs.com/Mayfly-nymph/p/12394329.html