CTFWiki-仿射密码

2021-11-27

最近发现CTFWiki上有系统的一套密码学知识框架，决定跟着过一遍。

第一篇是单表代换，太基础的就不记录了，直接从仿射密码开始。首先介绍一下仿射密码的原理：

仿射密码的加密函数是 E(x)=(ax+b)(modm)E(x)=(ax+b)(modm)，其中

x 表示明文按照某种编码得到的数字
a 和 m互质
m是编码系统中字母的数目（比如英文字符就是26）

解密函数是 D(x)=a−1(x−b)(modm)，其中 a−1 是 a 在 Zm 群的乘法逆元。

仿射密码的密钥空间不大，存在单表替换密码的通有弊病：明文和密文一一对应，即当密文长度足够长时，我们可以使用频率分析的方法来破解。

仿射密码的破解还可以通过已知明文攻击，过程如下：

已知：x1，x2以及y1=(ax1+b)(mod26)，y2=(ax2+b)(mod26)

通过y1，y2两式相减，可得：y1−y2=a(x1−x2)(mod26)

再通过求x1-x2模26的逆，两边相乘，就可得到a，再通过a求出b就破解了密码。

例题

import sys
key = '****CENSORED***************'
flag = 'TWCTF{*******CENSORED********}'

if len(key) % 2 == 1:
    print("Key Length Error")
    sys.exit(1)

n = len(key) / 2
encrypted = ''
for c in flag:
    c = ord(c)
    for a, b in zip(key[0:n], key[n:2*n]):
        c = (ord(a) * c + ord(b)) % 251
    encrypted += '%02x' % c

print encrypted

1	encrypted:805eed80cbbccb94c36413275780ec94a857dfec8da8ca94a8c313a8ccf9 (16进制存储)

虽然题目对于 flag 中的每个字母都加密了 n 次，但仿射密码的特性是，多次加密效果类同于一次加密：

c1=a1c+b1 c2=a2c1+b2=a1a2c+a2b1+b2=kc+d

根据第二行的推导，我们可以得到其实 cn 也是这样的形式，可以看成 cn=xc+ycn=xc+y ，并且，我们可以知道的是，key 是始终不变化的，所以说，其实这个就是普通的仿射密码。解密代码如下：

import gmpy2

key = '****CENSORED****************'
flag = 'TWCTF{*******CENSORED********}'

f = open('encrypted', 'r')
data = f.read().strip('\n')
encrypted = [int(data[i:i + 2], 16) for i in range(0, len(data), 2)]
plaindelta = ord(flag[1]) - ord(flag[0])
cipherdalte = encrypted[1] - encrypted[0]
a = gmpy2.invert(plaindelta, 251) * cipherdalte % 251
b = (encrypted[0] - a * ord(flag[0])) % 251
a_inv = gmpy2.invert(a, 251)
result = ""
for c in encrypted:
    result += chr((c - b) * a_inv % 251)
print (result)

结果为:TWCTF{Faster_Than_Shinkansen!}