仿射密码

  • 凯撒密码是将明文与密钥相加得到密文，仿射密码则是将明文与密钥的一部分相乘，然后再加上密钥的另一部分
  • 为了便于计算，将26个英文字母用数字表示：a=0，b=1，……，z=25
  • 仿射加密的密钥有两个：a和b，取值范围都是[0,25]
  • a要求与26互质，互质就是者两个数的公因数只有1
    • 26的因数：1、2、13
    • a的因素不包含2或13即可

仿射密码加密

  • x是明文，y是密文

  • 加密公式：y=(ax+b)mod26

  • 加密过程：

    • a=7、b=3

    • 加密：
      $$
      y=(7x+3)mod26
      $$

  • 假设明文为c，那么x的值为2

  • 所以y=17，密文为r

仿射密码解密

  • 解密公式：
    $$
    x=a^{-1}(y-b)mod26
    $$

    • 如果不考虑求模，根据加密公式很容易想到解密公式应该是x=(y-b)/a

    • 因为要求模，除法很可能会得到小数，而小数无法做模运算

    • 解决的方法是将除法转换为乘法

    • $$
      a^{-1}称为a的乘法逆元，((y-b)/a)mod26与a^{-1}(y-b)mod26完全等价
      $$

  • 仿射密码解密的关键就在于如何求乘法逆元

乘法逆元

  • $$
    假设用m表示a的乘法逆元，那么(a*m)mod26=1
    $$

  • a=7，可以写个简单的代码来求m，只要第一个符合条件的值即可：

1
2
3
4
5
6
7
a = 7
m = 0
while 1:
	if a*m%26 == 1:
		print m
		break
	m +=1

image-20231211162734910

  • $$
    解密：x=15(y-3)mod26，x=15*14mod26=2，对应明文为c
    $$

例题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# -*- coding: utf-8 -*-

# 中孚信息杯”- 仿射加密
# 已知仿射加密变换为c=(11m+7)mod26，试对密文dikxourxd解密


c = 'dikxourxd'

a = 11
b = 7
m = ''
t = 0
while 1:
	if t*a%26 == 1:
		print t
		break
	t +=1

for i in c:
	m += chr(97+(ord(i)-97-b)*t%26)
print m

image-20231211163443550

例题2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
# -*- coding: utf-8 -*-

# 科来杯-affine

# 题目描述
# y = 17*x-8，flag{szzyfimhyzd}
# 答案格式:flag(*******]


#解法1,利用公式求解
a = 17
b = -8

t = 0
c = 'szzyfimhyzd'
m = ''
while 1:
	if 17*t%26 == 1:
		print t
		break
	t += 1

for i in c:
	m += chr(97+((ord(i)-97)+8)*t%26)
print m

#解法2,利用爆破

c = 'szzyfimhyzd'
m = ''
a = 17
b = -8
for i in c:
	for j in range(0,26):
		if (j*17+b)%26 == ord(i)-97:
			m += chr(j+97)
print m