以下python代码用于生成Hill密码的密钥矩阵及其逆矩阵
#@PydevCodeAnalysisIgnore
"""
input : N
output : a pair of matrix which is inverse matrix of another.
"""
import random
import copy
import fractions
def relative_prime_lst(N):
'''
list all relatively prime in range(1,N) with N
@param N: integer
'''
return [m for m in range(1, N) if fractions.gcd(m,N)==1]
def ext_euclid(a,b):
'''
get the result of a*s+b*t = gcd(a,b)
return (s,t,gcd)
@param a: integer >0
@param b: integer >0
'''
r1 = a
r2 = b
s1 = 1
s2 = 0
t1 = 0
t2 = 1
while r2>0:
q = r1/r2
r = r1-r2*q
r1 = r2
r2 = r
s = s1-q*s2
s1 = s2
s2 = s
t = t1-q*t2
t1 = t2
t2 = t
return (s1, t1, r1)
def getInverse(a, N):
#(r,_,_) = ext_euclid(a, N)
#return r%N
if fractions.gcd(m,N)!=1:
return None
return ext_euclid(a, N)[0]%N
def GenMatrix(a, m, N):
'''
Create a m*m Matrix K which |K| mod N =a
@param a:
@param N:
'''
K = [range(i-i,m) for i in range(m)]
K[0][0]=a
for i in range(1,m):
K[i][i]=1
for j in range(0,i):
K[i][j]=0
for j in range(m):
K[i][j]=(K[i-1][j]*(i+1)%N+K[i][j])%N
return K
def inverseMat(K,N):
'''
return a inverse matrix of K in MOD N
@param K:
'''
m =len(K)
E = copy.deepcopy(K)
A = copy.deepcopy(K)
for i in range(m):
for j in range(m):
E[i][j]=0
E[i][i]=1
for j in range(1,m):
PreInv = A[j-1][j-1]
for i in range(j, m):
Inv = A[i][j-1]
for p in range(j-1, m):
A[i][p] = ((PreInv*A[i][p])%N-(Inv*A[j-1][p])%N)%N
for p in range(m):
E[i][p] = ((PreInv*E[i][p])%N-(Inv*E[j-1][p])%N)%N
for j in range(m-2, -1, -1):
PreInv = A[j+1][j+1]
for i in range(j, -1, -1):
Inv = A[i][j+1]
for p in range(j+1, -1, -1):
A[i][p] = (PreInv*A[i][p]%N - Inv*A[j+1][p]%N)%N
for p in range(m-1,-1,-1):
E[i][p] = ((PreInv*E[i][p])%N-(Inv*E[j+1][p])%N)%N
for i in range(0, m):
Inv = getInverse(A[i][i], N);
A[i][i] = (A[i][i]*Inv)%N
for j in range(m):
E[i][j] = (E[i][j]*Inv)%N
return E
def GenRandomMat(m, N):
'''
Create a m*m matrix A which has a inverse matrix MOD N.
Similar to GenMatrix, but get a different result every times.
@param m:
@param N:
'''
# stopped here.
lst = relative_prime_lst(N)
a = random.choice(lst)
K = [range(i-i,m) for i in range(m)]
for i in range(m):
K[i][i]=1
rd = random.randint(0, m-1)
K[rd][rd]=a
for i in range(0,m):
for j in range(0,i):
K[i][j]=0
for j in range(i+1, m):
K[i][j]=random.randint(0,N-1)
print ("a", a)
print ("K", K)
for i in range(m):
rd = i
while rd==i:
rd = random.randint(0,m-1)
rd1 = random.randint(1, N-1)
for j in range(m):
K[i][j] = (K[i][j]+K[rd][j]*rd1)%N
return K
def multiplyMat(mat1, mat2, N):
'''
multiply two matrices, return the result
@param mat1: M*M matrix
@param mat2: M*M matrix
@N: base
'''
M = len(mat1)
R = copy.deepcopy(mat1)
for i in range(M):
for j in range(M):
R[i][j] = 0
for p in range(M):
R[i][j]=(R[i][j]+(mat1[i][p]*mat2[p][j])%N)%N
return R
if __name__ == '__main__':
print ext_euclid(6, 26)
print ext_euclid(7, 256)
print getInverse(7, 256)
print getInverse(183, 256)
print getInverse(21, 26)
print getInverse(5, 7)
# Problem : when N is an even number , the result is wrong(A !=I).
N = 26
mat1 = GenMatrix(5, 4, N)
mat1 = [[9, 7, 11, 13], [4, 7, 5, 6], [2, 21,14, 9], [3, 23, 21, 8]]
#mat1 = [[3, 5, 7, 2], [1, 4, 7, 2], [6, 3, 9, 17], [13, 5, 4, 16]]
print ("MAT1",mat1)
mat2 = inverseMat(mat1, N)
print ("MAT2",mat2)
print ("MAT1*MAT2",multiplyMat(mat1, mat2, N))
mat2 = [[15,21,0,15],[23,9,0,22],[15,16,18,3],[24,7,15,3]]
print ("MAT1*MAT2",multiplyMat(mat1, mat2, N))
mat1 = GenMatrix(21, 4, 26)
mat2 = inverseMat(mat1, 26)
print ("mat1", mat1)
print ("mat2", mat2)
print ("mat1*mat2", multiplyMat(mat1, mat2, 26))
mat1 = GenRandomMat(4, 26)
mat2 = inverseMat(mat1, 26)
print ("mat1", mat1)
print ("mat2", mat2)
print ("mat1*mat2", multiplyMat(mat1, mat2, 26))
mat1 = GenRandomMat(7, 256)
mat2 = inverseMat(mat1, 256)
print ("mat1", mat1)
print ("mat2", mat2)
print ("mat1*mat2", multiplyMat(mat1, mat2, 256))