扩展欧几里得算法求乘法逆元
扩展的欧几里德算法可用于求解a mod b的逆元，而逆元求解在RSA加密算法中是不可缺少的一步
伪代码如下：
def fangshe_reverse(a,b):
X=[0,1]
Y=[1,0]
X.append(int(a))
Y.append(int(b))
def exgcd(X,Y):
if Y[2] == 0:
pass
#print('gcd(a,b)= %d \n no inverse'%(a,b,Y[2]))
elif Y[2] == 1:
pass
#print('gcd(a,b)=%d\n a mod b的逆元: %d'%(int(Y[2]),int(Y[1])))
else:
Q= X[2] // Y[2]
T1,T2,T3 = [(X[0] - Q * Y[0]),(X[1] - Q * Y[1]),(X[2] - Q * Y[2])]
X[0],X[1],X[2] = Y[0],Y[1],Y[2]
Y[0],Y[1],Y[2] = T1,T2,T3
exgcd(X,Y)
exgcd(X,Y)
return int(Y[1])
#fangshe_reverse(3,17)
仿射密码实现加解密
算法实现核心：
仿射变换加密，并打印加密的结果
c为密文，a和b为密钥（0<=a,b<=25）
加密公式：c = a*m + b%26
仿射变换解密，并打印解密的结果
c为密文，a和b为密钥
0<=a,b<=25，且满足gcd(a,26)=1，a^-1表示a的逆元
解密公式：m = (a^-1)*(c-b)%26
实现代码：
# coding=utf-8
# author : rang
def menu():
'''
菜单
'''
print("-----------------------")
print("| 0. 退出 |")
print("| 1. 仿射加密 |")
print("| 2. 仿射解密 |")
print("-----------------------")
def gcd(a,b):
#欧几里得算法求最大公约数
if b == 0:
return a
else:
return gcd(b , a % b)
def fangshe_reverse(a,b):
X=[0,1]
Y=[1,0]
X.append(int(a))
Y.append(int(b))
def exgcd(X,Y):
if Y[2] == 0:
pass
#print('gcd(a,b)= %d \n no inverse'%(a,b,Y[2]))
elif Y[2] == 1:
pass
#print('gcd(a,b)=%d\n a mod b的逆元: %d'%(int(Y[2]),int(Y[1])))
else:
Q= X[2] // Y[2]
T1,T2,T3 = [(X[0] - Q * Y[0]),(X[1] - Q * Y[1]),(X[2] - Q * Y[2])]
X[0],X[1],X[2] = Y[0],Y[1],Y[2]
Y[0],Y[1],Y[2] = T1,T2,T3
exgcd(X,Y)
exgcd(X,Y)
return int(Y[1])
#fangshe_reverse(3,17)
def fangshe_encode(m,a,b):
'''
仿射变换加密，并打印加密的结果
c为密文，a和b为密钥（0<=a,b<=25）
加密公式：c = a*m + b%26
'''
c = ''
for i in m:
new_i = ord(i) - 97
new_i =((a * new_i) + b ) % 26
c += chr(new_i + 97)
print("密文为：",c)
def fangshe_decode(c,a,b):
'''
仿射变换解密，并打印解密的结果
c为密文，a和b为密钥
0<=a,b<=25，且满足gcd(a,26)=1，a^-1表示a的逆元
解密公式：m = (a^-1)*(c-b)%26
'''
m = ''
for i in c:
new_i = ord(i) - 97
#print(fangshe_reverse(a,26))
new_i = (fangshe_reverse(a,26) * (int(new_i) - b)) % 26
m += chr(new_i + 97)
#print(m)
print("明文为",m)
def input_a_b():
a = int(input("请输入密钥a："))
while True:
if gcd(a,26) != 1:
print("密钥a与26不互素")
a = int(input("请输入密钥a："))
else:
break
b = int(input("请输入密钥b："))
return a,b
if __name__=='__main__':
while True:
menu()
choose = int(input("请选择: "))
if choose == 1:
m = input("请输入明文: ")
a,b = input_a_b()
fangshe_encode(m,a,b)
elif choose == 2:
c = input("请输入密文: ")
a,b = input_a_b()
fangshe_decode(c,a,b)
else:
break
效果：
