<> preface

Recently, I was preparing for the final exam of network security , Review to Hill When encrypting , Remember your previous programming homework , The writing is rough , And I don't understand how to ask Hill Decryption key of cryptosystem , I figured it out today , Just put Hill The password system is implemented and sorted out , The code is attached , For your reference .

<> one ,Hill Encryption Basics
<>1, hill cipher （Hill cipher） It is a multi table substitution cipher based on linear algebra .
Describe it briefly Hill Principle of cryptosystem , For an input plaintext plaintext = 'Hello world!', First plaintext Convert to a numerical matrix P
, This value needs to be indexed by itself , such as H I use this character 1 To represent … Then an encryption key matrix is given K, Through encryption formula , An encrypted numerical matrix can be obtained C
, By decrypting the formula , A decrypted numerical matrix can be obtained P, Finally P Map back to the form of a character , Use your own index to map the numerical matrix into string plaintext .

because Hill The decryption key of the cryptosystem is obtained by some transformation of the encryption key , therefore Hill A password is a symmetric password .
<>2, Hill cipher encryption and decryption formula ：
Encryption formula ：
C = K P m o d m (1) C=KPmodm \tag{1} C=KPmodm(1)
Decryption formula ：
P = K − 1 C m o d m (2) P=K^{-1}Cmodm \tag{2} P=K−1Cmodm(2)
among C Express plaintext ,P Indicates ciphertext , matrix K K K Represents the encryption key , matrix K − 1 K^{-1} K−1
Indicates the decryption key ,m express Hill The cryptosystem is in the module m Implemented under .Hill The difficulty of password is to solve the decryption key .
<>3, Hill password decryption key K − 1 K^{-1} K−1 Formula of ：
Hill Decryption key of password K − 1 K^{-1} K−1 It's not simple, right K K K Inversion , But in the mold m lower , yes K K K Inversion . here , The inverse formula has also changed .
K − 1 = d e t ( K ) − 1 ∗ K ∗ (1) K^{-1}=det(K)^{-1}*K^* \tag{1} K−1=det(K)−1∗
K∗(1) among K ∗ K^* K∗ yes K K K Adjoint matrix of , d e t ( K ) − 1 det(K)^{-1} det(K)−1 yes K K K
The determinant value of is in module m Multiplicative inverse under . For adjoint matrix K ∗ K^* K∗ Solution of , Easier , It is not difficult for us to find out with the following formula . K ∗ = d e t ( K ) ∗ K − 1
(2) K^*=det(K)*K^{-1} \tag{2}K∗=det(K)∗K−1(2)
<>4, Find a number in modulus m Multiplicative inverse under ：
In mold m lower , x x x Multiplicative inverse of y y y The conditions to be met are ：
( x × y ) m o d m = 1 (3) (x×y)modm=1 \tag{3} (x×y)modm=1(3)

notes ： Not any number in a module m There are multiplicative inverses under .
# In mold 26 Find a number x Multiplicative inverse of y, Just need to meet (x×y) mod 26 = 1 x = -939 # y The value range of is [0,26) y = 0 while(y
< 26): res = (x * y) % 26 if res == 1: print(x," The multiplicative inverse of is ：",y) break else: y = y +
1 if y == 26: print(x," In mold 26 lower , There is no multiplicative inverse !") <>5, seek Hill Password decryption key K − 1 K^{-1} K−1：
import numpy as np # this y yes det(K) In mold 26 Multiplicative inverse under , It has been found out that yes 17, Use it directly here y = 17 #K matrix K = np.
array([[17,17,5],[21,18,21],[2,2,19]], dtype=int) # yes K Matrix inversion , obtain K Inverse matrix of K1 K1 = np.
linalg.inv(K) # seek K Determinant value of matrix det(K) K_abs = np.linalg.det(K) print("K The value of the determinant of is ：",K_abs
) # seek K Adjoint matrix of matrix K2 = K1 * K_abs % 26 # Because the adjoint matrix may be a floating-point matrix , Therefore, it needs to be rounded #
And cast each element member to int type K2 = np.around(K2) K2 = K2.astype(np.int) print("K The adjoint matrix is :\n",
K2) # seek Hill Encrypted decryption key K3 = y * K2 % 26 print("Hill The decryption key of the password is :\n",K3)
Operation results ：
K The value of the determinant of is -939.0 K The adjoint matrix is : [[14 25 7] [ 7 1 8] [ 6 26 1]] Hill The decryption key of the password is : [[ 4 9 15
] [15 17 6] [24 0 17]]
<> two ,Hill Encryption and decryption complete code

The code here does not assign an index to letters , Directly alphabetic ascii Code value as index , In order to ensure the uniqueness of each letter after taking the mold , Mode selection in the whole process m The value of is 256, That is to say, below Hill The encryption and decryption code is in the module 256 Completed under , Readers can also according to their actual situation , Test under different modulus values , You can also consider assigning indexes to letters .
import numpy as np # Seeking in module m Multiplicative inverse of any number under def Multi_Inverse(x,m): #
input ： Find a number x In mold m Multiplicative inverse under # y The value range of is [0,m) y = 0 while(y < m): res = (x * y) % m if res ==
1: print(" In mold %d lower , The value of the encryption key determinant is %d, Its multiplicative inverse is %d" % (m,x,y)) break else: y = y + 1 if y ==
m: print(x," In mold ",m," lower , There is no multiplicative inverse !") return 0 return y # Find adjoint matrix def Adjoint_Mat(K,
K_det,m): # input ： matrix K, Determinant value of matrix K_det, model m # yes K Matrix inversion , obtain K Inverse matrix of K1 K1 = np.linalg.inv(K) #
seek K Adjoint matrix of matrix K2 = K1 * K_det % m # Because the adjoint matrix may be a floating-point matrix , Therefore, it needs to be rounded #
And cast each element member to int type K2 = np.around(K2) K2 = K2.astype(np.int) return K2 # Decryption key k
def Decrypt_Key(K,m): # seek K Determinant value of matrix det(K), model m K_det = np.linalg.det(K) K2 =
Adjoint_Mat(K, K_det, m) # seek det(K) In mold 26 Multiplicative inverse under y = Multi_Inverse(K_det, m) #
seek Hill Encrypted decryption key K3 = y * K2 % m return K3 # Will matrix ( Two dimensional array )ascii Code to character def ascii2_char(
array1): plaintext = '' row = array1.shape col = array1.shape for i in
range(row): for j in range(col): plaintext = plaintext + chr(array1[i][j])
return plaintext # Convert plaintext to ascii Code value matrix , The number of lines is consistent with the encryption key def char2ascii2(plaintext,row,m):
# input ： Plaintext plaintext, Number of rows of encryption matrix row, model m l1 = [0,0,0] l2 = [] for i in range(len(plaintext
)): j = i % row if (i > 0 and i % row == 0): l2.append(l1) l1 = [0, 0, 0] l1[j]
= ord(plaintext[i]) l2.append(l1) m1 = np.array(l2) m1 = np.reshape(m1,(m1.shape
,m1.shape)) m1 = m1 % m return m1 if __name__ == "__main__": # K matrix , Encryption key K
= np.array([[17,17,5],[21,18,21],[2,2,19]], dtype=int) # decryption key k, model m m = 256 k =
Decrypt_Key(K,m) print("Hill The decryption key of the password is :\n",k) # Plaintext plaintext = 'Programming is a
happy thing' print(" Original plaintext content :\n",plaintext) # Encryption key matrix K Number of rows row row = K.shape #
Convert plaintext to ascii Code value matrix , The number of lines is consistent with the encryption key # m1 As plaintext ascii Code value matrix m1 = char2ascii2(plaintext,row,m)
# Encryption process ,m2 Is the encrypted matrix m2 = np.dot(K,m1) % 256 Ciphertext = ascii2_char(m2) print(
" Ciphertext content :\n",Ciphertext) # Decryption process ,m3 Is the encrypted matrix m3 = np.dot(k,m2) % 256 decrypt_text =
ascii2_char(m3) print(" Decryption result :\n", decrypt_text)
Operation results ：
In mold 256 lower , The value of the encryption key determinant is -939, Its multiplicative inverse is 253 Hill The decryption key of the password is : [[124 171 223] [ 47 85 244] [238
0 153]] Original plaintext content : Programming is a happy thing Ciphertext content : "d7´oæ¾PÜODO”¼ Decryption result :
Programmingis a happy thing

Technology
Daily Recommendation
views 2