Hill cipher is an alternative cipher based on the basic matrix theory, which was invented by Lester S. Hill in 1929. Each letter is regarded as a hexadecimal number: A=0, B= 1, C=2 ... Take a string of letters as an n-dimensional vector, multiply it by an n×n matrix, and then get the result MOD26.

Chinese name

hill password

Foreign name

hill password

principle

Basic matrix theory

kind

Replace password

presenter

Lester hill

quick

navigate by water/air

cause

principle

security analysis

example

brief introduction

Hill cipher is an alternative cipher based on the basic matrix theory, which was invented by Lester S. Hill in 1929.

Each letter is regarded as a hexadecimal number: A=0, B= 1, C=2 ... A string of letters is regarded as an n-dimensional vector, multiplied by an n×n matrix, and then the result is modulo 26.

Note that the matrix used for encryption (that is, the key) must now be reversible, otherwise it cannot be decoded. Only the determinant and 26 coprime of a matrix are reversible.

cause

With the rapid development of science and technology and people's dependence on credit cards and computers, cryptography has become more and more important. Cryptography is a subject about encryption and decryption, ciphertext and plaintext. If the original symbol is replaced by another symbol, it can be called generalized cipher. Narrow password is mainly for confidentiality, which is another kind of symbolic text designed to prevent thieves from knowing the content, and it is also a well-known password.

Passwords are required to use credit cards, online accounts and passwords, e-mails, electronic signatures, etc. In order to facilitate memory, many people use birthdays, telephone numbers and house numbers as passwords, but this is not safe.

In order to make passwords more complicated and more difficult to decrypt, many different forms of passwords have been produced. The functional feature of password is that plaintext and password have a one-to-one or one-to-many relationship, that is, plaintext is a function of password. One of the traditional ciphers is called shift method, and the basic type of shift method is additive encryption system C=P+s(mod m). Generally speaking, A uses 1, B uses 2, ..., Y is 25, Z is 26, and so on. Since s=0 is equivalent to unencrypted, and 0≤s≤m- 1(s≥m can be replaced by 0≤s≤m- 1), only m- 1 changes in the whole system. In other words, as long as you try m- 1 times, confidential information will be leaked.

From this point of view, the reliability of passwords in daily life and traditional passwords is poor, so it is necessary for us to find a safe and reliable encryption method, which is easy to hide or homogenize the natural frequency of letters and is beneficial to statistical analysis. Hill password can basically meet this requirement.

principle

The basic idea of Hill encryption algorithm is to convert D plaintext letters into D secret letters through linear transformation. Decryption requires only one inverse transformation, and the key is the transformation matrix itself. [ 1]

Hill password is a multi-letter alternative password. Multi-letter substitution cipher can be conveniently described by matrix transformation, sometimes called matrix transformation cipher. Let the plaintext alphabet be z, if l letters are used for substitution, then the multicode is replaced by a mapping f:Z→Z → z, if the mapping is linear, then f is a linear transformation, which can be represented by the L×L matrix k on z, if it is full rank, it is transformed into a one-to-one mapping, with an inverse transformation k, and the number of l letters is represented as the L-dimensional vector m on z and the corresponding ciphertext vector c, mK=c, so take.

In military communication, characters (information) often correspond to numbers (for convenience, we correspond characters and numbers in the original order, but in fact this correspondence rule is easy to be cracked);

abcde…x y z

12345…242526

For example, the information "NOSLEEPPING" corresponds to a set of codes 14, 15, 19, 12, 5, 5 16, 16, 9,/kloc-. But if transmitted directly in this way, it will be easily deciphered by the enemy. Therefore, encryption measures must be taken, that is, an agreed encryption matrix K is multiplied by the original signal B, the transmission signal is C=KB (encryption), and the receiving party restores (decodes) the signal to B=KC.