In 1949, Shannon published a famous paper entitled “communication theory of secure systems” in the technical bulletin of Bell laboratory. Based on the mathematical theory of information established by him in 1948 (see Chap. 3), this paper makes a comprehensive discussion on the problem of secure communication and establishes the mathematical theory of secure communication system. It has a great impact on the later development of cryptography. It is generally believed that Shannon transformed cryptography from art (creative ways and methods) to science, so he is also known as the father of modern cryptography. The main purpose of this chapter is to introduce Shannon’s important ideas and results in cryptography theory, which is the cornerstone of the whole modern cryptography.
4.1 Definition and Statistical Characteristics of Cryptosystem
Let \(X=\{a_{1}, a_{2}, \ldots , a_{q}\}\) be the plaintext alphabet and a source. \(\{\xi _{i}\}_{i=1}^{\infty }\) is a set of random variables valued on X, for any given positive integer \(n \ge 1\), we define the plaintext space P as the product information space \(X_{1}X_{2}\cdots X_{n}\), that isIf \(m=m_{1}m_{2}\cdots m_{n} \in P(m_{i}\in X_{i})\), m is called a plaintext information column of alphabet length n, or a plaintext string of length n, the joint probability p(m) is defined asLet \(Z=\{b_{1}, b_{2}, \ldots , b_{s}\}\) be the key alphabet, which is also a memoryless source (see Definition 3.9 of Chap. 3), let \(\{\eta _{i}\}_{i=1}^{\infty }\) be a group of random variables with independent values on Z and equal probability distribution, then for any \(b \in Z\),We define the power space \(Z^{r}\) as a key space, denoted by K, that isEach \(k=k_{1}k_{2}\cdots k_{r} \in K\) is called a key of length r, and the joint probability p(k) isThis shows that the r-dimensional random vector \(\eta =(\eta _{1},\eta _{2}, \ldots , \eta _{r})\) taking value on the key space K is also equally almost distributed on K. Unless otherwise specified, we generally stipulate that the plaintext space P and the key space K are independent information spaces, that isFor every \(k\in K\), k defines or controls an encryption transform \(E_{k}\), denote byE is called encryption algorithm. When \(k\in K\) is given, the encryption transformation \(E_{k}\) acts on the plaintext \(m \in P\) to produce a cryptosystemtext \(E_{k}(m)\), each encryption transformation \(E_{k}\) is an injection, and its left inverse mapping is recorded as \(D_{k}\), which is called decryption transformation. Taking \(1_{P}\) as the identity transformation of plaintext space, that is \(1_{P}(m)=m, \forall ~ m \in P\), then we haveDefine cryptosystemtext space C asThat is, cryptosystemtext space C and plaintext space P have the same alphabet and the same letter length.
$$P=X_{1}X_{2}\cdots X_{n}, \text {where} ~X_{i}=(X, \xi _{i}),~1 \le i \le n.$$
$$\begin{aligned} p(m)=p(m_{1}m_{2}\cdots m_{n})=P\{ \xi _{1}=m_{1}, \xi _{2}=m_{2}, \ldots , \xi _{n}=m_{n} \}. \end{aligned}$$
(4.1)
$$\begin{aligned} p(b)=P\{ \eta _{i}=b \}=\frac{1}{|Z|}=\frac{1}{s},~ \forall ~ i \ge 1. \end{aligned}$$
(4.2)
$$\begin{aligned} K=Z^{r}=\{k=k_{1}k_{2}\cdots k_{r}|k_{i}\in Z, 1 \le i \le r\}. \end{aligned}$$
$$\begin{aligned} p(k)=p(k_{1}k_{2}\cdots k_{r})=\prod _{i=1}^{r}p(k_{i})=\frac{1}{|Z|^{r}}=\frac{1}{|K|}. \end{aligned}$$
(4.3)
$$\begin{aligned} p(mk)=p(m)p(k), \forall ~ m \in P, k\in K. \end{aligned}$$
(4.4)
$$\begin{aligned} E=\{E_{k}|k \in K\}. \end{aligned}$$
$$\begin{aligned} D_{k}E_{k}=1_{P}, \text {or} ~D_{k}(E_{k}(m))=m, \forall ~ m \in P. \end{aligned}$$
(4.5)
$$\begin{aligned} C=\{E_{k}(m)| m \in P, k \in K\} \subset X_{1}X_{2}\cdots X_{n} . \end{aligned}$$
(4.6)
Advertisement
For each cryptosystemtext \(c\in C, c=E_{k}(m)\), then c is uniquely determined by plaintext m and key k, so we can define the occurrence probability p(c) of cryptosystemtext c asObviously,Therefore, the cryptosystemtext space C defined by formula (4.7) is also an information space.
$$\begin{aligned} p(c)=p(E_{k}(m))=p(km)=p(k)p(m). \end{aligned}$$
(4.7)
$$\begin{aligned} \sum _{c\in C}p(c)=\sum _{k\in K}\sum _{m\in P}p(km)=\sum _{k\in K}p(k)\sum _{m\in P}p(m)=1, \end{aligned}$$
When \(k\in K\) is given, we letThen the encryption transformation \(E_{k}\) is the full mapping of \(P\rightarrow A_{k}\), so \(E_{k}\) is a 1–1 correspondence of \(P\rightarrow A_{k}\), and its inverse mapping is the decryption transformation \(D_{k}\), that isWe denote D as all decryption transformations, that isD is called decryption algorithm.
$$\begin{aligned} A_{k}=\{E_{k}(m)| m \in P\}\subset C. \end{aligned}$$
(4.8)
$$\begin{aligned} D_{k}E_{k}=1_{P}, E_{k}D_{k}=1_{A_{k}}, k \in K. \end{aligned}$$
$$\begin{aligned} D=\{D_{k}| k \in K\}. \end{aligned}$$
(4.9)
Definition 4.1
Under the above provisions, \(\mathfrak {R}=\{P, C, K, E, D\}\) is called a cryptosystem, where P, C, K is the information space, K and P are statistically independent, E is the encryption algorithm and D is the decryption algorithm.
The statistical characteristics of a cryptosystem are attributed to the following theorem.
Advertisement
Theorem 4.1
If \(\mathfrak {R}=\{P, C, K, E, D\}\), then
(1)
\(\forall ~ c \in C, \text {we have}\)
$$\begin{aligned} p(c)=\sum _{\begin{array}{c} {k \in K} \\ c \in A_{k} \end{array}}p(k)p(D_{k}(c)). \end{aligned}$$
(4.10)
(2)
\(c \in C, m\in P,\) then
$$\begin{aligned} p(c|m)=\sum _{\begin{array}{c} {k \in K} \\ E_{k}(m)=c \end{array}}p(k). \end{aligned}$$
(4.11)
(3)
\(c \in C, m\in P,\) then where \(A_{k}\) is given by equation (4.8).
$$\begin{aligned} p(m|c)=\frac{p(m)\sum _{\begin{array}{c} {k \in K} \\ D_{k}(c)=m \end{array}}p(k)}{\sum _{\begin{array}{c} {k \in K} \\ c\in A_{k} \end{array}}p(k)p(D_{k}(c))}, \end{aligned}$$
(4.12)
Proof
By (4.7), if \(c \in C\), then(1) holds. (2) is trivial. Because when \(m\in P\) is given, the occurrence probability p(c|m) of cryptosystemtext c hasTo prove (3), by (1.24),the items in the denominator areSo in the endTheorem 4.1 holds!
$$\begin{aligned} \begin{aligned} p(c)=\sum _{\begin{array}{c} {k \in K, m\in P} \\ E_{k}(m)=c \end{array}}p(km)=\sum _{\begin{array}{c} {k \in K, m\in P} \\ E_{k}(m)=c \end{array}}p(k)p(m)\\ =\sum _{k\in K}p(k)\sum _{\begin{array}{c} {m\in P} \\ E_{k}(m)=c \end{array}}p(m)=\sum _{\begin{array}{c} k\in K \\ c\in A_{k} \end{array}}p(k)p(D_{k}(c)). \end{aligned} \end{aligned}$$
$$\begin{aligned} p(c|m)=\sum _{\begin{array}{c} k \in K, \\ E_{k}(m)=c \end{array}}p(k). \end{aligned}$$
$$\begin{aligned} p(m|c)=\frac{p(m)p(c|m)}{\sum _{m'\in P}p(m')p(c|m')}, \end{aligned}$$
$$\begin{aligned} \begin{aligned} \sum _{m'\in P}p(m')p(c|m')&=\sum _{m'\in P}p(m')\sum _{\begin{array}{c} k \in K \\ E_{k}(m')=c \end{array}}p(k)\\&=\sum _{k\in K}p(k)\sum _{\begin{array}{c} {m'\in P} \\ E_{k}(m')=c \end{array}}p(m')\\&=\sum _{\begin{array}{c} k\in K \\ c\in A_{k} \end{array}}p(k)p(D_{k}(c)). \end{aligned} \end{aligned}$$
$$\begin{aligned} p(m|c)=\frac{p(m)\sum _{\begin{array}{c} k \in K \\ E_{k}(m)=c \end{array}}p(k)}{\sum _{\begin{array}{c} k\in K \\ c\in A_{k} \end{array}}p(k)p(D_{k}(c))}, \end{aligned}$$
By Theorem 4.1, the statistical characteristics of a cryptosystem can be summarized as follows: The probability distribution of cryptosystemtext space and the conditional probability distribution of plaintext about cryptosystemtext are completely determined by the probability distribution of plaintext space and key space. That is, anyone who knows the probability distribution of plaintext space and key space will know the probability distribution of cryptosystemtext and the conditional probability distribution of plaintext about cryptosystemtext.
It is assumed that the plaintext space and the key space are statistically independent, by (3.14) of Theorem 3.2 of Chap. 3, we haveIt has been previously specified that the key source alphabet Z is an equal probability information space without memory, and the probability p(k) of the key space \(K=\{k=k_{1}k_{2}\cdots k_{r}|k_{i}\in Z\}\) isTherefore, the key space is also an equal probability information space.
$$\begin{aligned} H(PK)=H(P)+H(K). \end{aligned}$$
(4.13)
$$\begin{aligned} p(k)=\prod _{i=1}^{r}p(k_{i})=\frac{1}{|Z|^{r}}=\frac{1}{|K|}. \end{aligned}$$
(4.14)
From the definition of cryptosystem, when the plaintext space and key space are given, the cryptosystemtext space is completely determined. On the contrary, when the cryptosystemtext space and key space are known, the plaintext space is also known, combined with Lemma 3.3 in the previous chapter, we have
Theorem 4.2
In a cryptosystem \(\mathfrak {R}=\{P, C, K, E, D\}\), we have
$$\begin{aligned} H(P|KC)=0, ~H(C|KP)=0, ~H(K|PC)=0. \end{aligned}$$
Proof
We only prove \(H(P|KC)=0\), similarly to \(H(C|KP)=0\) and \(H(K|PC)=0.\) For given \(m\in P\), letThus \(N_{m}\subset KC\), andBecause assuming \(kc \in N_{m}\) is selected, then \(E_{k}(m)=c\), thus \(m=D_{k}(c)\), m will be determined. Conversely, if \(kc \not \in N_{m}\), when the kc-joint event occurs and m cannot occur, thus \(p(m|kc)=0\). By Lemma 3.3 from the previous chapter, \(H(P|KC)=0\), we complete the proof of Theorem 4.2.
$$\begin{aligned} N_{m}=\{kc| c\in C, k \in K \text {and}~ E_{k}(m)=c\}. \end{aligned}$$
$$\begin{aligned} {\left\{ \begin{aligned}&p(m|kc)=1, \ \ \text {if}~ kc \in N_{m};\\&p(m|kc)=0,\ \ \text {if}~kc \not \in N_{m}. \end{aligned} \right. } \end{aligned}$$
Corollary 4.1
In a cryptosystem \(\mathfrak {R}=\{P, C, K, E, D\}\), we always have
$$\begin{aligned} H(P)\le H(C). \end{aligned}$$
Proof
It is stipulated that P and K are statistically independent, so there areThe Corollary holds.
$$\begin{aligned} \begin{aligned} H(P)&=H(P|K)=H(P|K)+H(C|PK)\\&=H(PC|K)\\&=H(C|K)+H(P|KC)\\&=H(C|K)\\&\le H(C). \end{aligned} \end{aligned}$$
The Corollary shows that the uncertainty of plaintext is less than that of cryptosystemtext in cryptosystem.
4.2 Fully Confidential System
Generally speaking, the mutual information I(P, C) between plaintext space and cryptosystemtext space (see Definition 3.8 in the previous chapter) reflects the information of plaintext space contained in cryptosystemtext space, so I(P, C) minimization is an important design goal of cryptosystem. If the cryptosystemtext does not provide any information about the plaintext, or the analyst cannot obtain any information about the plaintext by observing the cryptosystemtext, such a cryptosystem is called completely confidential.
Definition 4.2
A cryptosystem \(\mathfrak {R}=\{P, C, K, E, D\}\), if \(H(P|C)=H(P)\), or \(I(P, C)=0\), \(\mathfrak {R}\) is called complete secrecy system, or unconditional secrecy system.
Theorem 4.3
For any cryptosystem \(\mathfrak {R}=\{P, C, K, E, D\}\), we have
$$\begin{aligned} I(P, C)\ge H(P)-H(K). \end{aligned}$$
(4.15)
Proof
By Theorem 4.2, we have \(H(P|KC)=0\), andSo we haveBy definition,So the Theorem holds.
$$\begin{aligned} \begin{aligned} H(P|C)&=H(P|C)+H(K|PC)\\&=H(PK|C)\\&=H(K|C)+H(P|KC). \end{aligned} \end{aligned}$$
$$\begin{aligned} H(P|C)=H(K|C)\le H(K). \end{aligned}$$
$$\begin{aligned} I(P, C)=H(P)-H(P|C)\ge H(P)- H(K). \end{aligned}$$
From the previous chapter, we know the amount of mutual information \(I(X, Y)\ge 0\), there is
Corollary 4.2
In a completely confidential cryptosystem \(\mathfrak {R}=\{P, C, K, E, D\}\), there is always
$$\begin{aligned} H(P)\le H(K)= \log _{2}|K|. \end{aligned}$$
(4.16)
Proof
Defined by \(\mathfrak {R}=\{P, C, K, E, D\}\) as a completely confidential system, so \(I(P, C)=0\). From the above theorem, there areThus there is \(H(P)\le H(K)\). By (4.14), K is equipotential distribution, so there is
$$\begin{aligned} H(P)-H(K)\le I(P, C)=0, \end{aligned}$$
$$\begin{aligned} H(P)\le \log _{2}|K|. \end{aligned}$$
It can be seen from the above that the larger the scale |K| of the key space, the better the confidentiality of the system!
Definition 4.3
A cryptosystem \(\mathfrak {R}=\{P, C, K, E, D\}\) is called a “one secret at a time" system, if there is a unique key \(k\in K\) for a given \(m\in P\) and \(c\in C\), such that \(c=E_{k}(m)\).
As can be seen from the above definition, for given \(m\in P\), if \(k\ne k'\), then \(E_{k}(m)\ne E_{k'}(m)\). In other words, we only use a unique key k to encrypt the same set of plaintext and cryptosystemtext. This is also the origin of the concept of “one secret at a time”. Thus, for any given plaintext \(m\in P\) and cryptosystemtext \(c\in C\), there happens to be a unique key \(k\in K\) such that \(E_{k}(m)=c\). Therefore, when k traverses the key space K, m traverses the plaintext space P, and each m appears only once. Thus, for \(c\in C\), we haveThat is to say, in a one-time cryptosystem, the cryptosystemtext space C is also an equal probability information space.
$$\begin{aligned} \begin{aligned} p(c)&=\sum _{\begin{array}{c} k \in K \\ E_{k}(m)=c \end{array}}\sum _{ m\in P}p(k)p(m)\\&=\sum _{\begin{array}{c} k \in K \\ E_{k}(m)=c \end{array}}p(k)\sum _{ m\in P}p(m)\\&=\frac{1}{|K|}\sum _{ m\in P}p(m) =\frac{1}{|K|}. \end{aligned} \end{aligned}$$
(4.17)
Theorem 4.4
The one-time password system is a completely confidential system.
Proof
When c, m given, by (4.11),By (4.12) and (4.17),ThusTherefore, \(\mathfrak {R}=\{P, C, K, E, D\}\) is a completely confidential system.
$$\begin{aligned} p(c|m)=\sum _{\begin{array}{c} k \in K \\ E_{k}(m)=c \end{array}}p(k)=\frac{1}{|K|}. \end{aligned}$$
$$\begin{aligned} \begin{aligned} p(m|c)&=\frac{p(m)}{\sum _{\begin{array}{c} k \in K \\ E_{m'}(k)=c \end{array}}\sum _{ m' \in P}p(m')}\\&=\frac{p(m)}{\sum _{ m' \in P}p(m')}\\&=p(m). \end{aligned} \end{aligned}$$
$$\begin{aligned} \begin{aligned} H(P|C)&=-\sum _{ m \in P}\sum _{ c \in C}p(mc)\log _{2}p(m|c)\\&=-\sum _{ m \in P}\sum _{ c \in C}p(mc)\log _{2}p(m)\\&=-\sum _{ m \in P}p(m)\log _{2}p(m)\\&=H(P). \end{aligned} \end{aligned}$$
4.3 Ideal Security System
In order to introduce Shannon’s concepts of unique solution distance and ideal cryptosystem, we first consider the scenario of secret only attack. In the scenario of secret only attack, when the cryptanalyzer intercepts cryptosystemtext c, he may decrypt c with all decryption keys \(D_{k}\) to obtainTherefore, he records the keys corresponding to all meaningful messages \(m'\), only one of the set of these keys is a correct key, while other incorrect keys are called pseudo keys. A large number of cryptosystemtexts are required as samples in secret only attacks. Therefore, we will consider the product space \(P^{n}\) of plaintext and cryptosystemtext and the joint events in \(C^{n}\), \(P^{n}\) and \(C^{n}\) as plaintext string and cryptosystemtext string.
$$\begin{aligned} m'=D_{k}(c), ~k \in K. \end{aligned}$$
Definition 4.4
For cryptosystemtext string \(y\in C^{n}\) with given length n, letThen the number of pseudo keys is \(|K(y)|-1\). The mathematical expectation \(S_{n}\) of the pseudo key is defined as
$$\begin{aligned} K(y)=\{k \in K| \exists ~ x\in P^{n}~ \text {such that}~ E_{k}(x)=y\}. \end{aligned}$$
(4.18)
$$\begin{aligned} S_{n}=\sum _{y\in C^{n}}p(y)(|K(y)|-1). \end{aligned}$$
(4.19)
Therefore, the mathematical expectation of pseudo key is the weighted average of the number of pseudo keys of each cryptosystemtext string. We first prove the following two theorems.
Theorem 4.5
If \(\mathfrak {R}=\{P, C, K, E, D\}\) is a cryptosystem, there are
$$\begin{aligned} H(K|C)=H(K)+H(P)-H(C). \end{aligned}$$
(4.20)
Proof
From the addition formula of information entropy (see Theorem 3.2 in the previous chapter),By Theorem 4.2, we havethus,Again, from the addition formula and note that K and P are statistically independent, soandSo we haveThe Theorem holds.
$$\begin{aligned} H(KPC)=H(KP)+H(C|KP)=H(KC)+H(P|KC). \end{aligned}$$
$$\begin{aligned} H(C|KP)=H(P|KC)=0. \end{aligned}$$
$$\begin{aligned} H(KP)=H(KC). \end{aligned}$$
$$\begin{aligned} H(KP)=H(P)+H(K|P)=H(P)+H(K) \end{aligned}$$
$$\begin{aligned} H(P)+H(K)=H(KC)=H(C)+H(K|C). \end{aligned}$$
$$\begin{aligned} H(K|C)=H(P)+H(K)-H(C). \end{aligned}$$
Theorem 4.6
Let \(\mathfrak {R}=\{P, C, K, E, D\}\) be a cryptosystem, and \(|C|=|P|\), let r be the redundancy of P, then the pseudo key mathematical expectation \(S_{n}\) of a cryptosystemtext string with a given length of n satisfies
$$\begin{aligned} S_{n}\ge \frac{2^{H(K)}}{|P|^{nr}}-1. \end{aligned}$$
(4.21)
Proof
From the definition and properties of product space,also constitutes a cryptosystem. By Theorem 4.5, thenBy (3.9), we haveReplace information space X with P, then we haveSo we haveCombined with the above formula, we have an estimateBecause of the definition,We getThen by Jensen inequality,Finally, (4.21) can be obtained from form (4.23) to complete the proof!
$$\mathfrak {R}_{n}=\{P^{n}, C^{n}, K, E_{n}, D_{n}\}$$
$$\begin{aligned} H(K|C^{n})=H(K)+H(P^{n})-H(C^{n}). \end{aligned}$$
$$\begin{aligned} H(C^{n})\le n\log _{2}|C|, ~|C|=|P|. \end{aligned}$$
$$\begin{aligned} \begin{aligned} H(P^{n})&=H(P^{n-1})+H(P|P^{n-1})\\&=H(P^{n-1})+H_{n}\\&\ge H(P^{n-1})+H_{\infty }. \end{aligned} \end{aligned}$$
$$\begin{aligned} H(P^{n})\ge nH_{\infty }=n(1-r)H_{0}=n(1-r)\log _{2}|P|. \end{aligned}$$
(4.22)
$$\begin{aligned} H(K|C^{n})\ge H(K)+n(1-r)\log _{2}|P|-n\log _{2}|P|. \end{aligned}$$
(4.23)
$$\begin{aligned} \begin{aligned} H(K|C^{n})&=-\sum _{y\in C^{n}}\sum _{k\in K}p(ky)\log _{2}p(k|y)\\&=-\sum _{y\in C^{n}}p(y)\sum _{k\in K}p(k|y)\log _{2}p(k|y)\\&=-\sum _{y\in C^{n}}p(y)\sum _{k\in K(y)}p(k|y)\log _{2}p(k|y). \end{aligned} \end{aligned}$$
$$\begin{aligned} \sum _{k\in K(y)}p(k|y)=\sum _{k\in K}p(k)=1. \end{aligned}$$
$$\begin{aligned} \begin{aligned} H(K|C^{n})&\le \sum _{y\in C^{n}}p(y)\log _{2}|k(y)|\\&\le \log _{2}\sum _{y\in C^{n}}p(y)|k(y)|\\&=\log _{2}(S_{n}+1). \end{aligned} \end{aligned}$$
When the mathematical expectation of the number of pseudo keys is greater than 0, the secret only attack cannot break the password in theory, so we define the unique solution distance of a cryptosystem as the value of n of \(S_{n}=0\).
Definition 4.5
A cryptosystem whose unique solution distance is infinite is called an ideal security system.
From Theorem 4.6, we can obtain an approximate value of the distance of the unique solution.The unique solution distance indicates the minimum amount of cryptosystemtext that may be decrypted successfully when an exhaustive attack is carried out. Generally speaking, the greater the unique solution distance, the better the confidentiality of the system. However, Shannon only gives the existence of the unique solution distance, but does not give a specific calculation program. In practice, the amount of cryptosystemtext required to decryptosystem a cryptosystemtext is far greater than the theoretical value of the unique solution distance.
$$\begin{aligned} n_{0}\approx \frac{H(k)}{r\log _{2}|P|}. \end{aligned}$$
4.4 Message Authentication
Authentication system, also known as authentication code, is an important tool to ensure the authenticity and integrity of messages. In 1984, Simmons systematically put forward the information theory of authentication system for the first time. He used mathematics to study the theoretical and practical security of authentication system. This paper puts forward the performance limit of authentication system and the mathematical principles that should be followed in the design of authentication code. Although Simmons’ theory is not mature and perfect, its position in authentication system is as important as Shannon’s theory in cryptosystem, which lays a theoretical foundation for the research of mathematical theory of authentication system.
In cryptography, authentication system includes entity authentication and message authentication. We mainly discuss message authentication system. At present, there are two main models of authentication system. One is the arbiter-free authentication system model. In this model, the participants of the system are mainly message sender, message receiver and attacker, in which the message sender and receiver trust each other. They share the same key information; another model is the authentication system model with arbiter. In this model, the participants of the system have arbiters in addition to the information sender, receiver and attacker. At this time, the sender and receiver of the message do not trust each other, but they all trust the arbiter. The arbiter shares the key information with the sender and receiver.
An authentication system without privacy and confidentiality function and without arbiter is composed of four parts: a finite set S of source states, called the source set, a finite set A of authentication tags, called the tag set, a key space composed of all solvable keys, and an authentication rule set \(E=\{e_{k}(s)|k\in K, s \in S\}\), where for any \(k\in K, ~s\in S\), \(e_{k}(s)\) is the authentication rule. It is a mapping of \(S\rightarrow A\).
Definition 4.6
An authentication system is \(T=\{ S, A, K, E \},\) where S, A, K is the information space, S is the source space or source set, A is the label space or label set, and K is the key space, where S and K are statistically independent,Each \(e_{k}(s)\) is an injection of \(S\rightarrow A\), which is called an authentication rule.
$$\begin{aligned} E=\{e_{k}(s)|k\in K, s \in S \}. \end{aligned}$$
Definition 4.7
The product space SA is called the message space, and M represents SA.
Authentication protocol: The sender and receiver of the message use the following protocol to transmit information. First, they secretly select and share the random key \(k\in K\); if the sender wants to transmit an information source state \(s \in S\) to the receiver, the sender calculates \(a=e_{k}(s)\) and sends the message \(sa\in M\) to the receiver. When the receiver receives message sa, he calculates \(a'=e_{k}(s)\) again, if \(a'=a\), he confirms that the message is reliable and receives the message, otherwise he refuses to receive the message sa.
Definition 4.8
Matrix \([e_{k}(s)]_{|K|\times |S|}\) is called authentication matrix. Its rows are marked by key \(k\in K\) and columns by source state \(s \in S\). It is a \(|K|\times |S|\)-order matrix, the element intersecting row k and column s is \(e_{k}(s)\).
Authentication matrix is an important tool in authentication theory research. Our detailed list is as follows:
Let \(K=\{ k_{1}, k_{2}, \ldots , k_{n}\}\), \(S=\{ s_{1}, s_{2}, \ldots , s_{m}\}\). Then the authentication matrix is an \(n\times m\)-order matrix, which is listed as follows:
$$\begin{aligned} \left[ \begin{array}{cccc} e_{k_{1}}(s_{1}) &{} e_{k_{1}}(s_{2}) &{}\cdots &{} e_{k_{1}}(s_{m})\\ e_{k_{2}}(s_{1}) &{} e_{k_{2}}(s_{2}) &{}\cdots &{} e_{k_{2}}(s_{m})\\ \vdots \\ e_{k_{n}}(s_{1}) &{} e_{k_{n}}(s_{2}) &{}\cdots &{} e_{k_{n}}(s_{m})\\ \end{array} \right] _{n\times m}. \end{aligned}$$
4.5 Forgery Attack
In the process of message authentication, the attacker is an intermediate intruder. We usually consider two types of attacks, one is forgery attack and the other is substitution attack, which correspond to secret only attack and plaintext attack in cryptosystem. In forgery attack, the attacker sends message \(sa\in M\) in the channel and wants the receiver to confirm that it is true and receive it; in the substitution attack, the attacker first observes a message \(sa\in M\) in the channel, so he analyzes the coding rules currently used, then he tampers the message sa with \(s'a' \in M\), where \(s'\ne s\), and wants the receiver to receive it as a real message.
We assume that the attacker adopts the optimal deception strategy. \(p_{d_{0}}\) represents the probability that the forgery attacker is most likely to succeed in deception, and \(p_{d_{1}}\) represents the probability that the attacker is most likely to succeed in deception. The probability \(p_{d}\) that the attacker is successful in deception is defined asSimmons’ theory is mainly to estimate the lower bound of \(p_{d}\), so as to provide a theoretical basis for constructing authentication codes with attack success probability \(p_{d}\) as small as possible.
$$\begin{aligned} p_{d}=\max \{ p_{d_{0}}, p_{d_{1}}\}. \end{aligned}$$
(4.24)
First, let’s look at the definition and estimation of the maximum probability \(p_{d_{0}}\) of successful deception by forgery attackers.
\(A=\{a_{1}, a_{2}, \ldots , a_{r}\}\) represents the authentication tag space. The attacker first selects a source state \(s \in S\) and an authentication tag \(a \in A\). Let \(k_{0}\in K\) represent the shared key selected by the sender and receiver, if \(a=e_{k_{0}}(s)\), the forgery attacker can successfully deceive the receiver. We use pay off (s, a) to represent the probability that the message receiver receives sa as a true message, that isIf the attacker adopts the optimal strategy, then
$$\begin{aligned} \text {pay off} ~(s,a) =p(a=e_{k_{0}}(s))=\sum _{\begin{array}{c} k\in K \\ e_{k}(s)=a \end{array}}p(k). \end{aligned}$$
(4.25)
$$\begin{aligned} p_{d_{0}}=\max \{\text {pay off} ~(s,a)| s \in S, a\in A\}. \end{aligned}$$
(4.26)
Theorem 4.7
If the scale of authentication tag space A is set to \(|A|=r\), for any fixed source state \(s \in S\), there will always be an authentication tag \(a \in A\) such that
$$\text {pay off} ~(s,a) \ge \frac{1}{r}, ~\text {thus} ~p_{d_{0}}\ge \frac{1}{r}.$$
Proof
By the definition of pay off (s, a),When a runs through the s column of the authentication matrix, k traverses the whole key space, soTherefore, there is at least one \(a \in A\) such that
$$\begin{aligned} \sum _{a \in A}\text {pay off} ~(s,a) =\sum _{a \in A}\sum _{\begin{array}{c} k\in K \\ e_{k}(s)=a \end{array}}p(k). \end{aligned}$$
$$\begin{aligned} \sum _{a \in A}\text {pay off} ~(s,a) =\sum _{k\in K }p(k)=1. \end{aligned}$$
$$\begin{aligned} \text {pay off} ~(s,a)\ge \frac{1}{|A|}=\frac{1}{r}. \end{aligned}$$
Theorem 4.8
Let \(T=\{ S, A, K, E \}\) be a message authentication system,is the maximum probability of successful forgery attack, thenand
$$\begin{aligned} p_{d_{0}}=\max \{\text {pay off} ~(s,a)| s \in S, a\in A\} \end{aligned}$$
$$\begin{aligned} \log _{2}p_{d_{0}}\ge H(K|SA)-H(K) \end{aligned}$$
$$\begin{aligned} p_{d_{0}}\ge \frac{1}{2^{H(K)-H(K|SA)}}. \end{aligned}$$
Proof
By definition, we know that \(p_{d_{0}}\) is not less than the mathematical expectation of pay off (s, a), that isThen by Jensen inequality, we haveObviously,ThusSoBecause the source space S and the key space K are statistically independent, soAlso, the tag space A is completely determined by the source space S and the key space K, soBy the addition formula of information space,On the other hand,On the whole, we haveThusWe completed the proof of the theorem.
$$\begin{aligned} p_{d_{0}}\ge \sum _{s \in S, a\in A}p(sa)\text {pay off} ~(s,a). \end{aligned}$$
$$\begin{aligned} \begin{aligned} \log _{2}p_{d_{0}}&\ge \log _{2}\sum _{s \in S, a\in A}p(sa)\text {pay off} ~(s,a)\\&\ge \sum _{s \in S, a\in A}p(sa)\log _{2} \text {pay off} ~(s,a). \end{aligned} \end{aligned}$$
$$\begin{aligned} \text {pay off} ~(s,a)=p(a|s). \end{aligned}$$
$$\begin{aligned} p(sa)=p(s)p(a|s)=p(s)\text {pay off} ~(s,a). \end{aligned}$$
(4.27)
$$\begin{aligned} \begin{aligned} \log _{2}p_{d_{0}}&\ge \sum _{s \in S} \sum _{a\in A}p(sa)\log _{2} \text {pay off} ~(s,a)\\&=\sum _{s \in S} \sum _{a\in A}p(sa)\log _{2} p(a|s)\\&=-H(A|S). \end{aligned} \end{aligned}$$
$$\begin{aligned} H(SK)=H(K)+H(S). \end{aligned}$$
$$\begin{aligned} H(A|KS)=0. \end{aligned}$$
$$\begin{aligned} \begin{aligned} H(KAS)&=H(AS)+H(K|AS)\\&=H(S)+H(A|S)+H(K|AS). \end{aligned} \end{aligned}$$
$$\begin{aligned} \begin{aligned} H(KAS)&=H(KS)+H(A|KS)\\&=H(KS)=H(K)+H(S). \end{aligned} \end{aligned}$$
$$\begin{aligned} -H(A|S)=H(K|AS)-H(K). \end{aligned}$$
$$\begin{aligned} \log _{2}p_{d_{0}}\ge -H(A|S)=H(K|AS)-H(K). \end{aligned}$$
\(M=SA\) is called message space, it can be seen from theorem 4.8 that the maximum success probability \(p_{d_{0}}\) of forgery attack satisfieswhere I(K, M) is the average amount of mutual information between the key space and the information space. If the amount of mutual information I(K, M) is larger, the probability of the most successful forgery attack is lower. On the contrary, if the amount of mutual information is smaller, the success rate of forgery attack is higher.
$$\begin{aligned} p_{d_{0}}\ge \frac{1}{2^{I(K,M)}}, \end{aligned}$$
4.6 Substitute Attack
The so-called substitution attack is that the attacker first observes a message (s, a) on the message, and then replaces (s, a) with message \((s', a')\), hoping that the receiver will receive \((s', a')\) as a real message. Considering the maximum success probability \(p_{d_{1}}\) of substitution attack, it is more difficult than forgery attack, the main reason is that \(p_{d_{1}}\) depends on both the probability distribution of source state space S and the probability distribution of key space K.
Let \((s', a')\) and (s, a) be two messages, where \(s\ne s'\). We use pay off \((s', a', s, a)\) to express the probability that using \((s', a')\) instead of (s, a) can cheat success, thenThe above formula represents the conditional probability of \(a'=e_{k_{0}}(s')\) under the condition of \(a=e_{k_{0}}(s)\) under the same key \(k_{0}\), soWhen the message \((s, a)\in M\) is given, the attacker uses the optimal strategy to maximize the success probability of the deceiver, so letTaking \(p_{s,a}\) as a random variable, its mathematical expectation on message set \(M=SA\) isThe above formula is the formal definition of \(p_{d_{1}}\), which is the weighted average of the maximum success probability of pay off \((s', a', s, a)\) in message space M.
$$\begin{aligned} \text {pay off} ~(s', a', s,a) =p(a'=e_{k_{0}}(s')|a=e_{k_{0}}(s)), ~k_{0}\in K. \end{aligned}$$
$$\begin{aligned} \begin{aligned} \text {pay off} ~(s', a', s,a)&= \frac{p(a'=e_{k_{0}}(s'), a=e_{k_{0}}(s))}{p(a=e_{k_{0}}(s))}\\&=\frac{\sum _ {\begin{array}{c} k \in K, \\ e_{k_{0}}(s')=a', e_{k_{0}}(s)=a \end{array}}p(k)}{\text {pay off} ~(s,a)}. \end{aligned} \end{aligned}$$
(4.28)
$$\begin{aligned} p_{s,a}=\max \{\text {pay off} ~(s', a', s,a)| s' \in S, s'\ne s, a'\in A\}, \end{aligned}$$
(4.29)
$$\begin{aligned} p_{d_{1}}\ge \sum _{s \in S, a\in A}p(sa)p_{s,a}. \end{aligned}$$
(4.30)
Like Theorem 4.7, we have
Theorem 4.9
Let \(T=\{ S, A, K, E \}\) be an authentication code, \(|A|=r\), then for any given \(s' \in S\), \(s \in S\), \(s\ne s'\) and \(a \in A\), there is a label \(a' \in A\) such thatSo we have
$$\begin{aligned} \text {pay off} ~(s', a', s,a) \ge \frac{1}{|A|}=\frac{1}{r}. \end{aligned}$$
$$\begin{aligned} p_{d_{1}}\ge \frac{1}{r}. \end{aligned}$$
Proof
By (4.28),So at least one \(a'\in A\) such thatBy the definition of \(p_{s,a}\), for \(\forall ~ s \in S\) and \(a \in A\), we haveThus
$$\begin{aligned} \begin{aligned} \sum _{a' \in A}\text {pay off} ~(s', a', s,a)&=\frac{1}{\text {pay off} ~(s,a)} \sum _{a' \in A}\sum _{\begin{array}{c} k\in K \\ e_{k}(s)=a, e_{k}(s')=a' \end{array}}p(k)\\&=\frac{1}{\text {pay off} ~(s,a)} \sum _{\begin{array}{c} k\in K \\ e_{k}(s)=a \end{array}}p(k)=1. \end{aligned} \end{aligned}$$
$$\begin{aligned} \text {pay off} ~(s', a', s,a) \ge \frac{1}{|A|}=\frac{1}{r}. \end{aligned}$$
$$\begin{aligned} p_{s,a} \ge \frac{1}{|A|}=\frac{1}{r}. \end{aligned}$$
$$\begin{aligned} p_{d_{1}}\ge \sum _{s \in S, a \in A }p(sa) p_{s,a} \ge \frac{1}{r}\sum _{a \in A }p(a)=\frac{1}{r}. \end{aligned}$$
Theorem 4.10
Let \(T=\{ S, A, K, E \}\) be an authentication code, for any \((s, a)\in M\), when using \((s', a')\) instead of attack, let \(p_{d_{1}}\) be the mathematical expectation of \(p_{s,a}\) in space M, thenand
$$\begin{aligned} \log _{2}p_{d_{1}}\ge H(K|M^{2})-H(K|M) \end{aligned}$$
$$\begin{aligned} p_{d_{1}}\ge \frac{1}{2^{H(K|M)-H(K|M^{2})}}. \end{aligned}$$
(4.31)
Proof
By (4.29), \(p_{s,a}\) will not be less than the mathematical expectation of pay off \((s', a', s, a)\) on \(s' \in S\), \(a' \in A\), that isBy (4.30) and Jensen inequality, we haveIn addition,So there areIt can be proved thatSo there areThusThat isThe Theorem holds!
$$\begin{aligned} p_{s,a} \ge \sum _{s' \in S, a'\in A}p(s'a'|sa)\text {pay off} ~(s', a',s,a). \end{aligned}$$
$$\begin{aligned} \begin{aligned} \log _{2}p_{d_{1}}&\ge \sum _{s \in S, a\in A}p(sa)\log _{2}p_{s,a}\\&\ge \sum _{s \in S, a\in A}p(sa)\sum _{s' \in S, a'\in A}p(s'a'|sa)\log _{2} \text {pay off} ~(s', a',s,a)\\&= \sum _{s \in S, a\in A} \sum _{s' \in S, a'\in A}p(sas'a')\log _{2} \text {pay off} ~(s', a', s,a)\\&= \sum _{s \in S, a\in A} \sum _{s' \in S, a'\in A}p(sas'a')\log _{2} p(a's'|as)\\&=-H(M|M). \end{aligned} \end{aligned}$$
$$\begin{aligned} \begin{aligned} H(KM^{2})&=H(M|M)+H(K|M^{2})\\&=H(K|M)+H(M|KM). \end{aligned} \end{aligned}$$
$$\begin{aligned} -H(M|M)=H(K|M^{2})-H(K|M)-H(M|KM). \end{aligned}$$
$$\begin{aligned} H(M|KM)=0. \end{aligned}$$
$$\begin{aligned} -H(M|M)=H(K|M^{2})-H(K|M). \end{aligned}$$
$$\begin{aligned} \log _{2}p_{d_{1}}\ge H(K|M^{2})-H(K|M). \end{aligned}$$
$$\begin{aligned} p_{d_{1}}\ge \frac{1}{2^{H(K|M)-H(K|M^{2})}}. \end{aligned}$$
Definition 4.9
An authentication code \(\{ S, A, K, E \}\) is called perfect if
$$\begin{aligned} p_{d}=2^{H(K|M)-H(K)}. \end{aligned}$$
Theorem 4.11
Perfect certification system exists.
Proof
The theorem is proved directly by the construction method. First, let the source state space be \(S=\{0, 1\}\). Let N be a positive even number, and define the label space A and the key space K as follows:andThe authentication rule \(e_{k}(s)\) determined by \(k=k_{1}k_{2}\cdots k_{\frac{N}{2}}k_{\frac{N}{2}+1}\cdots k_{N}\) is defined asandAssuming that all \(2^{N}\) keys k are equitably selected, so for \(s \in S\) and \(a \in A\), we haveSo there is \(p_{d_{0}}=2^{-\frac{N}{2}}\), similarly to \(p_{d_{1}}=2^{-\frac{N}{2}}\), soEasy to calculateSoTherefore, \(\{ S, A, K, E \}\) is a perfect authentication system.
$$\begin{aligned} A=\mathbb {Z}_{2}^{\frac{N}{2}}=\{a_{1}a_{2}\cdots a_{\frac{N}{2}}|a_{i}\in \mathbb {Z}_{2}, 1\le i \le \frac{N}{2}\} \end{aligned}$$
$$\begin{aligned} K=\mathbb {Z}_{2}^{N}=\{k_{1}k_{2}\cdots k_{N}|k_{i}\in \mathbb {Z}_{2}, 1\le i \le N\}. \end{aligned}$$
$$\begin{aligned} e_{k}(0)=k_{1}k_{2}\cdots k_{\frac{N}{2}} \end{aligned}$$
$$\begin{aligned} e_{k}(1)=k_{\frac{N}{2}+1}\cdots k_{N}. \end{aligned}$$
$$\begin{aligned} \text {pay off} ~(s,a) =p(a=e_{k}(s))=2^{-\frac{N}{2}}. \end{aligned}$$
$$\begin{aligned} p_{d}=2^{-\frac{N}{2}}. \end{aligned}$$
$$\begin{aligned} H(K|M)-H(K)=\frac{N}{2}-N=-H(K|M). \end{aligned}$$
$$\begin{aligned} p_{d}=2^{H(K|M)-H(K)}. \end{aligned}$$
4.7 Basic Algorithm
4.7.1 Affine Transformation
Encryption with matrix comes from the classical \(Vigen\grave{e}re\) password. Let \(X=\{a_{1}, a_{2}, \ldots , a_{N}\}\) be a plaintext alphabet of N characters, we replace the characters in \(\mathbb {Z}_{N}\) and X with numerical values, where \(\mathbb {Z}_{N}\) is the remaining class ring of \({{\,\mathrm{mod}\,}}N\). Let \(P=\mathbb {Z}_{N}^{k}\) be the plaintext space, \(x=x_{1}x_{2}\cdots x_{k} \in P\) is called a plaintext unit or a plaintext message of length k. Let \(M_{k}(\mathbb {Z}_{N})\) be a k-order full matrix ring over \(\mathbb {Z}_{N}\), \(A\in M_{k}(\mathbb {Z}_{N})\) is a invertible matrix of order k, \(b=b_{1}b_{2}\cdots b_{k} \in \mathbb {Z}_{N}^{k}\) is a given directional quantity, each plaintext unit \(x=x_{1}x_{2}\cdots x_{k}\) in P is encrypted by affine transformation (A, b):where \(x=x_{1}x_{2}\cdots x_{k} \) is clear text, \(x^{'}=x_{1}^{'}x_{2}^{'}\cdots x_{k} ^{'}\) is cryptosystemtext. The decryption algorithm is:Because affine transformation (A, b) is a 1–1 correspondence on \(\mathbb {Z}_{N}^{k}\longrightarrow \mathbb {Z}_{N}^{k}\), its inverse transformation is \((A^{-1}, -A^{-1}b)\); therefore, using affine transformation (A, b), we obtain the so-called high-order affine cryptosystem. This cryptosystem was first proposed by mathematician Lester hill in American Mathematics monthly in 1929, so it is also called Hill cryptosystem.
$$\begin{aligned} \left( \begin{array}{cccc} x_{1}^{'}\\ x_{2}^{'}\\ \vdots \\ x_{k}^{'} \end{array}\right) = A \left( \begin{array}{cccc} x_{1}\\ x_{2}\\ \vdots \\ x_{k} \end{array}\right) +\left( \begin{array}{cccc} b_{1}\\ b_{2}\\ \vdots \\ b_{k} \end{array}\right) . \end{aligned}$$
(4.32)
$$\begin{aligned} \left( \begin{array}{cccc} x_{1}\\ x_{2}\\ \vdots \\ x_{k} \end{array}\right) = A^{-1} \left( \begin{array}{cccc} x_{1}^{'}\\ x_{2}^{'}\\ \vdots \\ x_{k}^{'} \end{array}\right) -A^{-1}\left( \begin{array}{cccc} b_{1}\\ b_{2}\\ \vdots \\ b_{k} \end{array}\right) . \end{aligned}$$
(4.33)
Hill cryptosystem divides the plaintext into a group of k characters and then encrypts each plaintext unit in turn by using k-order affine transformation (A, b) on \(\mathbb {Z}_{N}\). The advantage of this password is that it hides the statistical characteristics of a single character (such as 26 letters in English), which can better resist the statistical analysis of the occurrence frequency of characters, and has strong ability to resist cryptosystemtext only attacks. However, on the basis of mastering a large amount of plaintext, it is not difficult to find the key (A, b), so the hill password is not strong against the attack of known plaintext.
The mathematical principles used by Hill cryptosystem are the following two conclusions.
Lemma 4.1
The set of all k-order affine transformations on \(\mathbb {Z}_{N}\) is written as \(G_{k}\), that isThen \(G_{k}\) forms a group under the multiplication of transformation, which is called the k-order affine transformation group of ring \(\mathbb {Z}_{N}\).
$$ G_{k}=\{(A, b)| A \text {is a }k~\text {-order reversible square matrix}, b \in \mathbb {Z}_{N}^{k}\}. $$
Proof
Take A as the k-order identity matrix E and \(b=0\) as the k-dimensional zero vector, then (E, 0) is the identity transformation of \(\mathbb {Z}_{N}^{k}\longrightarrow \mathbb {Z}_{N}^{k}\) and the unit element of \(G_{k}\). Secondly, we look at the product of two affine transformations \((A_{1}, b_{1})\) and \((A_{2}, b_{2})\),Obviously, the inverse transformation of (A, b) isTherefore, \(G_{k}\) is a group. The Lemma holds.
$$(A_{1}, b_{1})(A_{2}, b_{2})=(A_{1}A_{2}, A_{1}b_{2}+b_{1}) \in G_{k}.$$
$$(A, b)^{-1}=(A^{-1}, -A^{-1}b) \in G_{k}.$$
From the above lemma, any group element \((A, b)\in G_{k}\) of affine transformation group will form a Hill cryptosystem. If we select n group elements \((A_{1}, b_{1}), (A_{2}, b_{2})\), \(\ldots \), \((A_{n}, b_{n})\) in \(G_{k}\) and letUsing (A, b) to encrypt, we get a more complex Hill cryptosystem.
$$\begin{aligned} (A, b)=\prod _{i=1}^{n}(A_{i}, b_{i}). \end{aligned}$$
Lemma 4.2
\(A\in M_{k}(\mathbb {Z}_{N})\), \(|A|=D\) is the determinant of A, then A is reversible if and only if D and N are coprime, that is \((D, N)=1\).
Proof
If \((D, N)=1\), then there is \(D_{1}\) such that \(D_{1}D\equiv 1 ({{\,\mathrm{mod}\,}}N)\), letwhere \(A=(a_{ij})_{k \times k}\), \(A_{ij}\) is the algebraic cofactor of \(a_{ij}\). obviously, we haveSo A is reversible, \(A^{-1}=A^{*}\). Let’s take \(k=2\) as an example, if \(|A|=D\), \((D, N)=1\),Conversely, if A is reversible and \(A^{-1}\) is the inverse matrix, because \(A^{-1}A=AA^{-1}=E\), we getSo we have \((D, N)=1\). The Lemma holds.
$$\begin{aligned} A^{*}= D_{1} \left[ \begin{array}{cccc} A_{11} &{} A_{12} &{} \cdots &{} A_{1k}\\ A_{21} &{}A_{22} &{} \cdots &{} A_{2k}\\ \cdots &{} \cdots &{} \cdots &{} \cdots \\ A_{k1} &{} A_{k2} &{} \cdots &{} A_{kk} \end{array}\right] , \end{aligned}$$
(4.34)
$$\begin{aligned} A^{*}A=AA^{*}=\left[ \begin{array}{cccc} 1&{}0 &{} \cdots &{}0\\ 0 &{}1 &{} \cdots &{}0\\ \vdots &{} \vdots &{}~&{}\vdots \\ 0 &{} 0 &{} \cdots &{} 1 \end{array}\right] , \end{aligned}$$
$$A=\left( \begin{array}{cc} a&{}b\\ c &{} d \end{array}\right) \Longrightarrow A^{-1}=\left( \begin{array}{cc} D_{1}d&{}-D_{1}b\\ -D_{1}c &{} D_{1}a \end{array}\right) . $$
$$|AA^{-1}|=|A||A^{-1}| \equiv 1 ({{\,\mathrm{mod}\,}}N).$$
If \(k=1\), first-order affine cryptosystem \(x^{'} \equiv ax+b ({{\,\mathrm{mod}\,}}N)\), where \((a, N)=1\), contains many famous classical passwords, especially when \(a=1\), \(b=3\), \(N=26\), \(x^{'}=x+3({{\,\mathrm{mod}\,}}26)\) is the famous Caesar code in history.
Next, we analyze the computational complexity of affine cryptography. We have the following Lemma.
Lemma 4.3
If \(A=(a_{ij})_{k \times k}\) is a k-order reversible square matrix on \(\mathbb {Z}_{N}\), the bit operation times of \(A^{-1}\) are estimated as followsTherefore, when k is a fixed constant, the algorithm for finding \(A^{-1}\) is polynomial. When N is a fixed constant, the algorithm for finding \(A^{-1}\) is exponential. In other words, the greater the order of the matrix, the higher the computational complexity.
$$\text {Time}(A^{-1})=O(k^{4}k! \log ^{3}N).$$
Proof
Because \(A=(a_{ij})_{k \times k}\) is reversible, then determinantwhere \(j_{1}j_{2}\cdots j_{k}\) is an arrangement of \(1,2, \ldots , k\) and \(\tau (j_{1}j_{2}\cdots j_{k})\) is the reverse order number of the arrangement. The number of bit operations of each summation is \(O(k^{3} \log ^{2}N)\), and there are k! summation terms in total, thusBy Lemma 1.5 of Chapter 1, find the multiplicative inverse of D under \({{\,\mathrm{mod}\,}}N\), \(D^{-1} {{\,\mathrm{mod}\,}}N=D_{1}\) isThe bit operation times of each algebraic cofactor \(A_{ij}\) of the adjoint matrix \(A^{*}\) of formula (4.34) is \(O((k-1)^{3}(k-1)!\log ^{2}N)\), and there are \(k^{2}\) algebraic cofactors, thusSoWhen k is constant, the algorithm for finding \(A^{-1}\) is polynomial. When N is constant and \(k\longrightarrow \infty \), it is obvious that the algorithm for finding \(A^{-1}\) is exponential. The Lemma holds.
$$\begin{aligned} D=|A|=\sum _{j_{1}j_{2}\cdots j_{k}}(-1)^{\tau }(j_{1}j_{2}\cdots j_{k})a_{1j_{1}}a_{2j_{2}}\cdots a_{kj_{k}}, \end{aligned}$$
$$\text {Time}(D)=O(k^{3}k! \log ^{2}N).$$
$$\text {Time}(D_{1})=O(\log ^{3}N).$$
$$\text {Time}(A^{*})=O(k^{4}k! \log ^{2}N).$$
$$\text {Time}(A^{-1})=O(k^{4}k! \log ^{3}N).$$
4.7.2 RSA
In 1976, two mathematicians from Stanford University, Diffie and Hellman, put forward a new idea of cryptosystem design. In short, the encryption algorithm and decryption algorithm are designed based on the principle of asymmetry. We can use the following schematic diagram to illustratewhere P is the plaintext space, C is the cryptosystemtext space, f encryption algorithm and \(f^{-1}\) decryption algorithm. If f and \(f^{-1}\) are the same algorithm, such as the involution operation in binary system, or the encryption algorithm f can easily deduce the decryption algorithm \(f^{-1}\). For example, the matrix encryption algorithm mentioned in the previous section (the matrix order is very small), which is called symmetric cryptosystem. The essence of symmetric cryptosystem is that the encryption key and decryption key have the same confidentiality importance. Diffie and Hellman proposed that if \(f \ne f^{-1}\) and f are encryption algorithms that are easy to implement, while \(f^{-1}\) is a decryption algorithm that is very difficult to calculate, the key can be divided into encryption key and decryption key. Even if the encryption key is made public to the public, the security of decryption key will not be affected. This encryption algorithm f is called asymmetric or trapdoor one-way function. The password using asymmetric f is called asymmetric password or public key cryptosystem. Due to the bold innovation of Diffie and Hellman, cryptography has ushered in a new era—the era of public key cryptography. Its basic feature is that passwords change from few users to many users, which greatly improves the efficiency and social value of passwords.
$$\begin{aligned} P\xrightarrow {f}C\xrightarrow {f^{-1}}P, \end{aligned}$$
(4.35)
How to design asymmetric encryption algorithm? Rivest, Shamir and Adleman jointly put forward the first secure and practical one-way encryption algorithm, which is called RSA algorithm in academic circles. This public key cryptosystem has been widely used in cryptographic design and has become an international standard algorithm. In addition to its simplicity and practicality, its security completely depends on the difficulty of large prime factorization of huge integers.
Let p, q be two large and relatively safe prime numbers, assumeLet \(n=pq\), \(\varphi (n)\) be an Euler function, thenRandomly select a positive integer e to satisfyThe large prime numbers p and q and e satisfying formula (4.37) are randomly generated. The so-called random generation is to randomly select the p, q and e with the help of the computer random number generator (or pseudo-random number generator), and its computational complexity is
$$\begin{aligned} 10^{300}<p,q, ~~~\text {its binary digits}~ k>1024 \text {bits}. \end{aligned}$$
(4.36)
$$\begin{aligned} \varphi (n)=(p-1)(q-1)=n+1-p-q. \end{aligned}$$
$$\begin{aligned} 1<e< \varphi (n), (e, \varphi (n))=1. \end{aligned}$$
(4.37)
Lemma 4.4
Randomly generated large prime number p and q, \(n=pq\), \(\varphi (n)\) is Euler function, \(1<e< \varphi (n), (e, \varphi (n))=1\), then
$$\begin{aligned} {\left\{ \begin{aligned}&\text {Time (select out }n\text {)}=O( \log ^{4}n),\\&\text {Time (find }e\text {)}=O( \log ^{2}n). \end{aligned} \right. } \end{aligned}$$
Proof
Use the random number generator to generate a huge integer m, such as \(m>10^{300}\), and then detect whether \(m, m+1, m+2, \ldots ,\) is a prime number. From the prime number theorem, we know that the frequency of prime numbers adjacent to m is about \(O(\frac{1}{\log m})\), so we only need about \(O(\log m)\) tests to find the required prime number p, by Lemma 1.5 of Chapter 1,Similarly,Because \(n=pq\), son after confirmation, \(\varphi (n)=(p-1)(q-1)\). A positive integer a, \(1<a<\varphi (n)\), is randomly generated by the random number generator, and then whether \(a, a+1, a+2, \ldots \) and \(\varphi (n)\) are mutually prime is detected in turn. Again, according to the prime number theorem, the frequency of the prime factor of \(\varphi (n)\) appearing in the vicinity of a is \(O(\frac{1}{\log a})\), so we only need \(O(\log a)\) tests to get the required e. ThusThe Lemma holds.
$$\text {Time (find prime}~p\text {)}=O( \log ^{2}m)=O( \log ^{2}n).$$
$$\text {Time (find prime}~\text {q)}=O( \log ^{2}n).$$
$$\text {Time (select out}~\text {n)}=O( \log ^{4}n).$$
$$\text {Time (select out}~\text {e)}=O( \log ^{2}a)=O( \log ^{2}n).$$
After randomly selecting p, q, \(n=pq\), and e, because \((e, \varphi (n))=1\), then exist \(d=e^{-1} {{\,\mathrm{mod}\,}}\varphi (n)\), that is
$$\begin{aligned} de \equiv 1 ({{\,\mathrm{mod}\,}}\varphi (n)), 1< d< \varphi (n). \end{aligned}$$
(4.38)
Definition 4.10
After randomly determining \(n=pq\), let \(P_{e}=(n,e)\) be called public key, \(P_{d}=(n,d)\) be called private key, or e be public key and d be private key.
By Lemma 1.5 of chapter 1, calculate the number \(\text {Time} (d)=O( \log ^{3}\varphi (n))=O( \log ^{3}n)\) of bit operations required for \(d=e^{-1} {{\,\mathrm{mod}\,}}\varphi (n)\). By Lemma 4.4, we have
Corollary 4.3
The computational complexity of randomly generated public key \(P_{e}=(n,e)\) and private key \(P_{d}=(n,d)\) is polynomial.
The key mathematical principle used in RSA cryptographic design is the generalized Euler congruence theorem. \(n \ge 1\) is a positive integer, \((m,n)=1\), from Euler theorem, it can be seen thatWe will prove that under the condition that n is a positive integer without square factor, there is formula (4.39) for all positive integers m, whether \((m, n)=1\) or \((m, n)>1\).
$$\begin{aligned} m^{\varphi (n)} \equiv 1 ({{\,\mathrm{mod}\,}}n), \Longrightarrow m^{\varphi (n)+1} \equiv m ({{\,\mathrm{mod}\,}}n) . \end{aligned}$$
(4.39)
Lemma 4.5
If \(n=pq\) is the product of two different prime numbers, then for all positive integers m, k, there are
$$\begin{aligned} m^{k \varphi (n)+1} \equiv m ({{\,\mathrm{mod}\,}}n) . \end{aligned}$$
(4.40)
Proof
If \((m, n)=1\), then by Euler Theorem,We only consider the case of \((m, n)>1\), because \(n=pq\), so \((m, n)=p\), \((m, n)=q\), or \((m, n)=n\). If \((m, n)=n\), then(4.40) holds. Might as well let \((m, n)=p\), then \(m=pt\), where \(1\le t <q\). By Euler theorem, because \((m, q)=1\), soFor \(\forall ~k \ge 1\), there isWe writeBoth sides are multiplied by m,The above formula containsWe have completed the proof of lemma.
$$\begin{aligned} m^{k \varphi (n)} \equiv 1 ({{\,\mathrm{mod}\,}}n), \Longrightarrow m^{k \varphi (n)+1} \equiv m ({{\,\mathrm{mod}\,}}n) . \end{aligned}$$
$$\begin{aligned} m^{ \varphi (q)} \equiv 1 ({{\,\mathrm{mod}\,}}q), \Longrightarrow m^{k \varphi (q)\varphi (p)} \equiv 1 ({{\,\mathrm{mod}\,}}q) . \end{aligned}$$
$$\begin{aligned} m^{k \varphi (n)} \equiv 1 ({{\,\mathrm{mod}\,}}q) . \end{aligned}$$
$$\begin{aligned} m^{k \varphi (n)} = rq+1. \end{aligned}$$
$$\begin{aligned} m^{k \varphi (n)+1} = rtn+m. \end{aligned}$$
$$\begin{aligned} m^{k \varphi (n)+1} \equiv m ({{\,\mathrm{mod}\,}}n). \end{aligned}$$
With the above preparations, the workflow of RSA password can be divided into the following three steps:
(1)
Suppose A is a user of RSA, and A randomly generates two huge prime numbers \(p=p(A)\), \(q=q(A)\), \(n=n(A)\), where \(n=pq, \varphi (n)=(p-1)(q-1)\). Then randomly generate positive integers \(e=e(A)\), satisfies \(1< e < \varphi (n), (e, \varphi (n))=1\), calculated \(d\equiv e^{-1} ({{\,\mathrm{mod}\,}}\varphi (n))\), and \(1<d < \varphi (n)\). User A destroys two prime numbers p and q, and only keeps three numbers n, e, d, after publishing \(P_{e}=(n,e)\) as public key, he has private key \(P_{d}=(n,d)\) and keeps it strictly confidential.
(2)
User B of another RSA sends encrypted information to user A using the known public key (n, e) of user A. B selects \(P=\mathbb {Z}_{n}\) as the plaintext space and encrypts each \(m \in \mathbb {Z}_{n}\). The encryption algorithm \(c=f(m)\) is defined as where c is cryptosystemtext.
$$\begin{aligned} c=f(m) \equiv m ^{e}({{\,\mathrm{mod}\,}}n) ,~ 1 \le c \le n. \end{aligned}$$
(4.41)
(3)
After receiving the cryptosystemtext c sent by user B, user A decrypts it with its own private key (n, d). Decryption algorithm \(f^{-1}\) is defined as: User A gets the plaintext m sent by user B. so far, RSA cryptosystem completes encryption and decryption.
$$\begin{aligned} m=f^{-1}(c)\equiv c ^{d}({{\,\mathrm{mod}\,}}n) ,~ 1 \le m \le n. \end{aligned}$$
(4.42)
The correctness and uniqueness of RSA password are guaranteed by the following Lemma.
Lemma 4.6
Proof
By Lemma 4.5, for all \(m \in \mathbb {Z}_{n}\), k is a positive integer, then there isBecause of \(ed\equiv 1 ({{\,\mathrm{mod}\,}}\varphi (n))\), we can writeBy (4.41), then there isThat is to say, for all \(m \in \mathbb {Z}_{n}\),In the same way, we haveIn other words,By Lemma 1.1 of Chap. 1, f is a 1–1 correspondence of \(\mathbb {Z}_{n}\longrightarrow \mathbb {Z}_{n}\), and \(f f^{-1}=1, f^{-1}f=1\). Th Lemma holds.
$$\begin{aligned} m^{k \varphi (n)+1} \equiv m ({{\,\mathrm{mod}\,}}n). \end{aligned}$$
$$\begin{aligned} ed= k \varphi (n)+1. \end{aligned}$$
$$\begin{aligned} c^{d} \equiv m^{ed}\equiv m^{k \varphi (n)+1} \equiv m ({{\,\mathrm{mod}\,}}n). \end{aligned}$$
$$\begin{aligned} f^{-1}(f(m))=m. \end{aligned}$$
$$\begin{aligned} m^{e} \equiv c^{ed}\equiv c^{k \varphi (n)+1} \equiv c ({{\,\mathrm{mod}\,}}n). \end{aligned}$$
$$\begin{aligned} f( f^{-1}(c))=c. \end{aligned}$$
Another very important application of RSA is for digital signature. From the workflow of RSA password, it can be seen that the encryption algorithm defined in formula (4.41) is based on the public key \((n_{A}, e_{A})\) of user A, and we denote f as \(f_{A}\) and the decryption algorithm defined in formula (4.42) as \(f_{A}^{-1}\). The workflow of RSA digital signature is: User A sends his digital signature to user B, that is, A sends an encrypted message to B. Let \(P_{e}(A)=(n_{A}, e_{A})\) be the public key of A and \(P_{d}(A)=(n_{A}, d_{A})\) the private key of A. Similarly, \(P_{e}(B)=(n_{B}, e_{B})\) is the public key of B and \(P_{d}(B)=(n_{B}, d_{B})\) is the private key of B. Then the digital signature sent by user A to user B iswhere \(m \in \mathbb {Z}_{n_{A}}\) is the digital signature published by user A. After receiving the above digital signature of user A, user B adopts the following two different digital verification according to the two cases of \(n_{A}< n_{B}\) and \(n_{A}> n_{B}\), formula (4.43) is the real signature of user A.
$$\begin{aligned} {\left\{ \begin{aligned}&f_{B} f_{A}^{-1}(m), ~\text {if}~ n_{A}< n_{B}\\&f_{A}^{-1}f_{B}(m), ~\text {if}~ n_{A}> n_{B}. \end{aligned} \right. } \end{aligned}$$
(4.43)
(i)
If \(n_{A}< n_{B}\), user B first decrypts with his private key \(f_{B}^{-1}=(n_{B}, d_{B})\) and then decrypts with user A’s public key \(f_{A}=(n_{A}, e_{A})\), the verification is as follows
$$\begin{aligned} f_{A}f_{B}^{-1}(f_{B} f_{A}^{-1}(m))=f_{A} f_{A}^{-1}(m)=m. \end{aligned}$$
(ii)
If \(n_{A}> n_{B}\), user B uses user A’s public key \(f_{A}=(n_{A}, e_{A})\) first, then decrypt and verify with your own private key \(f_{B}^{-1}=(n_{B}, d_{B})\)
$$\begin{aligned} f_{B}^{-1} f_{A}(f_{A}^{-1}f_{B} (m))= f_{B}^{-1}f_{B}(m)=m. \end{aligned}$$
The security of RSA is the difficulty of large prime factorization based on n. When all users select the large prime numbers p and q, let \(n=pq\), then destroy p and q, only (n, e) and its own secret (n, d) key information are retained, even if (n, e) is published to the public, outsiders only know n and do not know \(\varphi (n)\), so they cannot obtain the information of private key (n, d). Because the calculation of \(\varphi (n)\) must rely on the prime factorization of n, from the product formula of Euler, it is not difficult to seeBecause we have very little knowledge of prime numbers, we have not found a general term formula to give an infinite number of prime numbers, so it is undoubtedly a difficult problem to judge whether a huge integer n is prime, not to mention the prime factorization of n.
$$\begin{aligned} \varphi (n)=n \prod _{p|n}{(1- \frac{1}{p})}. \end{aligned}$$
4.7.3 Discrete Logarithm
Let G be a finite group and \(b,y \in G\) be two group elements of G, let t be the minimum positive integer satisfying \(b^{t}=1\), t is called the order of b, denote as \(t=o(b)\). If there is one x, \(1 \le x \le o(b)\) such that \(y=b^{x}\), x is called the discrete logarithm of y under base b. Known \(b \in G\), \(0\le x \le o(b)\), it’s easy to calculate \(y=b^{x}\). Conversely, for any group element y, it is very difficult to find the discrete logarithm of y under base b. Therefore, using discrete logarithm to encrypt has become the most mainstream encryption algorithm in public key cryptosystem, including the famous ElGamal cryptosystem and elliptic curve cryptosystem. ElGamal cryptosystem uses the discrete logarithm on the multiplication group formed by all \(\mathbb {F}_{q}^{*}\) of nonzero elements in finite field \(\mathbb {F}_{q}\). Elliptic curve cryptography uses the discrete logarithm algorithm of Mordell group on elliptic curve. Here we mainly discuss ElGamal cryptography, and elliptic curve cryptography is discussed in Chap. 6. We first prove several basic conclusions in finite field.
Lemma 4.7
Let \(\mathbb {F}_{q}\) be a finite field of q elements and \(q=p^{n}\) be the power of prime p. \(\mathbb {F}_{q}^{*}=\mathbb {F}_{q}\backslash \{0\}\) is all the nonzero elements in \(\mathbb {F}_{q}\), then \(\mathbb {F}_{q}^{*}\) is a cyclic group of order \((q-1)\) under multiplication, and the generating element g of \(\mathbb {F}_{q}^{*}\) is called the generator of finite field \(\mathbb {F}_{q}\).
Proof
According to Lagrange theorem, the number of zeros of polynomials in any field is not greater than the degree of polynomials. The finite field \(\mathbb {F}_{q}^{*}\) is a finite group of order \((q-1)\) under multiplication. To prove that \(\mathbb {F}_{q}^{*}\) is a cyclic group, it is only proved that for any factor d of \(q-1\), \(d|q-1\), the number of solutions of equation \(x^{d}=1\) in \(\mathbb {F}_{q}^{*}\) is not greater than d. This point can be deduced from Lagrange’s theorem, because the number of zeros of polynomial \(x^{d}-1\) in the whole field \(\mathbb {F}_{q}\) is not greater than d, so the number of zeros in \(\mathbb {F}_{q}^{*}\) is not greater than d. So \(\mathbb {F}_{q}^{*}\) is a finite cyclic group. The Lemma holds.
Lemma 4.8
Let \(\mathbb {F}_{q}\) be a q-element finite field, \(q=p^{n}\), \(\mathbb {F}_{p} \subset \mathbb {F}_{q}\) is a subfield, \(\mathbb {F}_{p}^{*} < \mathbb {F}_{q}^{*}\) is a subgroup of \(\mathbb {F}_{q}^{*}\), if g is the generator of \(\mathbb {F}_{q}^{*}\), then \(g'=g^{\frac{q-1}{p-1}}\) is the generator of \(\mathbb {F}_{p}^{*}\).
Proof
g is the generator of \(\mathbb {F}_{q}^{*}\), then \(o(g)=q-1\). Let \(g'=g^{\frac{q-1}{p-1}}\), thenThus \((g')^{p-1}=1\), that is \((g')^{p}=g'\), so \(g'\in \mathbb {F}_{p}\). Because \(\mathbb {F}_{p}^{*}\) is a cyclic group of order \(p-1\), and \(o(g')=p-1\), so \(\mathbb {F}_{p}^{*}=<g'>\), \(g'\) is the generator of \(\mathbb {F}_{p}^{*}\). The Lemma holds.
$$\begin{aligned} o(g')=\frac{o(g)}{(q-1, \frac{q-1}{p-1})}=p-1. \end{aligned}$$
Lemma 4.9
Let \(\mathbb {F}_{q}\) be a q-element finite field, \(q=p^{n}\), for any d|n, letandThen we have
$$A_{d}=\{p(x) \in \mathbb {F}_{p}[x]|\deg p(x)=d, ~p(x) ~\text {is an irreducible monic polynomial} \}$$
$$\begin{aligned} f_{d}(x)=\prod _{p(x) \in A_{d}}p(x). \end{aligned}$$
$$\begin{aligned} x^{q}-x=x^{p^{n}}-x=\prod _{d|n}f_{d}(x). \end{aligned}$$
(4.44)
Proof
We knowLet \(p(x) \in A_{d}\), that is \( p(x) \in \mathbb {F}_{p}[x], \deg p(x)=d\), p(x) is an irreducible monic polynomial. Let \(\alpha \) be a root of p(x), then add a finite extension field of \(\alpha \) on \(\mathbb {F}_{p}\) and \(\mathbb {F}_{p}(\alpha )\) is a d-th finite extension on \(\mathbb {F}_{p}\). If d|n, thenso there is \(\alpha \in \mathbb {F}_{q}\). Because the zeros of p(x) are all in \(\mathbb {F}_{q}\), so there is \(p(x)|x^{q}-x\). Any p(x) in \(A_{d}\) has \(p(x)|x^{q}-x\), soConversely, p(x) is the first irreducible polynomial, and \(\deg p(x)=d\). If \(p(x)|x^{q}-x\), then the zeros of p(x) are all in \(\mathbb {F}_{q}\). Let \(\alpha \) be a zero point of p(x), then there is \(\mathbb {F}_{p}(\alpha )\subset \mathbb {F}_{q}\), that is \(\mathbb {F}_{p^{d}}\subset \mathbb {F}_{q}=\mathbb {F}_{p^{n}}\), so d|n. Finally,The Lemma holds.
$$\begin{aligned} x^{p^{d}}-x|x^{p^{n}}-x \Longleftrightarrow d|n. \end{aligned}$$
$$\mathbb {F}_{p}(\alpha )=\mathbb {F}_{p^{d}} \subset \mathbb {F}_{q},$$
$$\begin{aligned} f_{d}(x)=\prod _{p(x) \in A_{d}}p(x),~ f_{d}(x)|x^{q}-x. \end{aligned}$$
$$\begin{aligned} x^{q}-x=\prod _{d|n}f_{d}(x). \end{aligned}$$
Lemma 4.10
\(N_{p}(d)\) represents the number of the first irreducible polynomial with degree d in \(\mathbb {F}_{p}[x]\), thenwhere \(\mu \) is Möbius function.
$$\begin{aligned} N_{p}(n)=\frac{1}{n} \sum _{d|n}{\mu (d) p^{\frac{n}{d}}}, \end{aligned}$$
(4.45)
Proof
By Lemma 4.9 and (4.44),Comparing the degree of polynomials on both sides, there isBy the Möbius inverse formula,so there is (4.45), the Lemma holds.
$$\begin{aligned} x^{q}-x=x^{p^{n}}-x=\prod _{d|n}f_{d}(x). \end{aligned}$$
$$\begin{aligned} p^{n}=\sum _{d|n}dN_{p}(d). \end{aligned}$$
$$\begin{aligned} nN_{p}(n)=\sum _{d|n}{\mu (d) p^{\frac{n}{d}}}, \end{aligned}$$
Corollary 4.4
If d is a prime number, the degree in \(\mathbb {F}_{p}[x]\) is d and the number of the first irreducible polynomial is \(\frac{1}{d}(p^{d}-p)\), that is
$$N_{p}(d)=\frac{1}{d}(p^{d}-p), ~ \text {if }d~\text {is a prime number}.$$
Proof
By (4.45),The Corollary holds.
$$\begin{aligned} \begin{aligned} N_{p}(d)&=\frac{1}{d}\sum _{\delta |d}\mu (\delta )p^{\frac{d}{\delta }}\\&=\frac{1}{d}(p^{d}-p). \end{aligned} \end{aligned}$$
Based on the above basic conclusions about finite fields, we introduce two methods for solving discrete logarithms. The first is the Silver–Pohlig–Hellman smoothing method, and the second is the so-called exponential integration method.
Silver–Pohlig–Hellman
Let \(\mathbb {F}_{q}\) be a q-element finite field, b is the generator, that is \(\mathbb {F}_{q}^{*}=<b>\),where \(p_{i}\) is a different prime number. p for each prime factor of \(q-1\), \(p|q-1\), if p is relatively “small", the positive integer \(q-1\) is called a smooth positive integer. Under the condition that \(q-1\) is smooth, for each prime factor p, calculate all p-th unit roots \(r_{p,j}\) in \(\mathbb {F}_{q}^{*}\), whereDenote \(R(p)=\{r_{p,j}|1\le j \le p\}\) is the root of p p subunits in \(\mathbb {F}_{q}^{*}\), then in \(\mathbb {F}_{q}^{*}\), we get a unit root table R.Now let’s look at the calculation method of discrete logarithm in \(\mathbb {F}_{q}^{*}\). Let \(y \in \mathbb {F}_{q}^{*}\), the discrete logarithm of y under base b is m, that is \(y =b^{m}\). When y and b are given, the value of m is desired \((1 \le m \le q-1)\), by the prime factor decomposition of \(q-1\) of formula (4.46), if for each \(p_{i}^{\alpha _{i}}(1 \le i \le s)\), the minimum nonnegative residue of m under \({{\,\mathrm{mod}\,}}p_{i}^{\alpha _{i}}\) is \(m_{i}=m {{\,\mathrm{mod}\,}}p_{i}^{\alpha _{i}} \), according to the Chinese remainder theorem, there is a unique \(m {{\,\mathrm{mod}\,}}q-1\) such thatTherefore, the discrete logarithm m of y is determined. Now the question is: let \(p^{\alpha }|| q-1\), we determine \(m {{\,\mathrm{mod}\,}}p^{\alpha }\). LetA is the minimum nonnegative residue of m \({{\,\mathrm{mod}\,}}p^{\alpha }\), let’s determine each \(m_{i}\). First, we calculate \(m_{0}\). Because \(y=b^{m}\), soThat is, \(y^{\frac{q-1}{p}}\) is a unit root in \(\mathbb {F}_{q}^{*}\), compare the unit root table R in \(\mathbb {F}_{q}^{*}\), then we have \(m_{0}=j, 1\le j \le p\), which determines \(m_{0}\). Next, calculate \(m_{1}\), let \(y_{1}=\frac{y}{b^{m_{0}}}=b^{m-m_{0}}\), therefore, the discrete logarithm of \(y_{1}\) is \(m-m_{0}\), andsoin other words, \(y_{1}^{\frac{q-1}{p^{2}}}\) is a p subunit root of \(\mathbb {F}_{q}^{*}\), comparing the unit root table R, we can determine \(m_{1}\). Continuing with this method, we can calculate \(m_{2}, \ldots , m_{\alpha -1}\) in turn, so \(m {{\,\mathrm{mod}\,}}p^{\alpha }\) is calculated, then by the Chinese remainder theorem, the discrete logarithm m of y under b is calculated.
$$\begin{aligned} o(b)=|\mathbb {F}_{q}^{*}|=q-1=p_{1}^{\alpha _{1}}p_{2}^{\alpha _{2}} \cdots p_{s}^{\alpha _{s}}, \end{aligned}$$
(4.46)
$$\begin{aligned} r_{p,j}=b^{\frac{j(q-1)}{p}},~ 1\le j \le p. \end{aligned}$$
(4.47)
$$\begin{aligned} \text {unit root table}~R=\{R(p_{1}), R(p_{2}), \ldots , R(p_{s})\}. \end{aligned}$$
(4.48)
$$\begin{aligned} m\equiv m_{i}({{\,\mathrm{mod}\,}}(p_{i}^{\alpha _{i}})), \forall ~i, 1 \le i \le s. \end{aligned}$$
$$\begin{aligned} m{{\,\mathrm{mod}\,}}p^{\alpha }=m_{0}+m_{1}p+m_{2}p^{2}+\cdots +m_{\alpha -1}p^{\alpha -1}, 0 \le m_{i} <p \end{aligned}$$
$$\begin{aligned} y^{\frac{q-1}{p}}=b^{\frac{m(q-1)}{p}}=b^{\frac{m_{0}(q-1)}{p}}. \end{aligned}$$
$$\begin{aligned} m-m_{0}\equiv m_{1}p+m_{2}p^{2}+\cdots +m_{\alpha -1}p^{\alpha -1}( {{\,\mathrm{mod}\,}}p^{\alpha }), \end{aligned}$$
$$\begin{aligned} y_{1}^{\frac{q-1}{p^{2}}}=b^{\frac{(m-m_{0})(q-1)}{p^{2}}}=b^{\frac{m_{1}(q-1)}{p}}. \end{aligned}$$
Exponential integral method
Let \(\mathbb {F}_{q}\) be the finite field of q element, \(q=p^{n}\), p be a relatively small prime number, and n be a large positive integer, so that the security of q can meet certain requirements. Let \(\mathbb {F}_{p}\) be the finite field of p element, we can think of \(\mathbb {F}_{q}\) as an n-th extension field of \(\mathbb {F}_{p}\), according to the finite extension theory of the field, \(\mathbb {F}_{q}\) equivalent to (isomorphism) a quotient ring of polynomial ring \(\mathbb {F}_{p}[T]\) over \(\mathbb {F}_{p}\). Let \(f(T) \in \mathbb {F}_{p}[T]\) be the first irreducible polynomial of n degree, thenTherefore, any element a in \(\mathbb {F}_{q}\) is equivalent to a polynomial a(T) on \(\mathbb {F}_{p}\), where \(\deg a(T) \le n-1.\) Let \(b \in \mathbb {F}_{q}\) be the generator of \(\mathbb {F}_{q}\), \(b=b(T)\), if \(a_{0} \in \mathbb {F}_{p}\) is a constant polynomial, \(a_{0}\) is called a constant in \(\mathbb {F}_{q}\).
$$\begin{aligned} \mathbb {F}_{q}=\mathbb {F}_{p}[T]/_{<f(T) >}=\{a_{0}+a_{1}T+\cdots +a_{0}T^{n-1}|\forall ~ a_{i} \in \mathbb {F}_{p}\}. \end{aligned}$$
(4.49)
By Lemma 4.8, the discrete logarithm of the constant in \(\mathbb {F}_{q}\) can be easily determined. Let \(b' \in \mathbb {F}_{p}\) be the generator of \(\mathbb {F}_{p}^{*}\), if \(m'\) is the discrete logarithm of constant \(a_{0} \in \mathbb {F}_{p}\) to base \(b'\), then by Lemma 4.8, \(m=m'\frac{q-1}{p-1}\) is the discrete logarithm of \(a_{0} \in \mathbb {F}_{q}\) under base b. Take \(m'(a_{0})\) as the discrete logarithm of \(a_{0}\) under base \(b'\), since p is small, we can easily calculate and list the discrete logarithms of all constants in \(\mathbb {F}_{q}\):Next, we determine the discrete logarithm of a nonconstant polynomial under base b(T). Let \(1<m<n\), defineThe number of irreducible polynomials in \(L_{m}\) is written as \(h_{m}\), that is \(|L_{m}|=h_{m}\). We first calculate the discrete exponent of irreducible polynomials in \(L_{m}\).
$$\begin{aligned} L_{0}=\{m'(a_{0})\frac{q-1}{p-1}|a_{0} \in \mathbb {F}_{p}\}. \end{aligned}$$
(4.50)
$$\begin{aligned} L_{m}=\{p(x)\in \mathbb {F}_{p}[x]|p(x) ~\text {is monic irreducible polynomial}, \deg p(x) \le m\}, \end{aligned}$$
(4.51)
Let \(b=b(T)\) be the generator of \(\mathbb {F}_{q}^{*}\), \(b(T) \in \mathbb {F}_{p}[T]\), \(\deg b(T) \le n-1\), obviously, when t runs through all positive integers from 1 to \(q-1\), \(b^{t}(T)\) runs through all nonzero polynomials in Eq. (4.49). Appropriate choice t, letSuch thatdenote the discrete logarithm of a(T) under b(T) with \(\text {ind} (a(T))\), which can be obtained from the above formula,Because of \(\text {ind} (c(T))=t\), thus,By (4.50), \(\text {ind} (c_{0})\) is known, therefore, the above formula is a linear equation with \(h_{m}\) variables \(\text {ind} (p(T))\). By continuously selecting the appropriate t, we can obtain \(h_{m}\) independent linear equations, that is, the \(h_{m} \times h_{m}\)-order matrix formed by the coefficients of \(h_{m}\) variables and \(h_{m}\) linear equations is reversible under \({{\,\mathrm{mod}\,}}q-1\), by Lemma 4.2, as long as its determinant and \(q-1\) are coprime. From the knowledge of linear algebra, we can calculate all \(\text {ind} (p(T))\) by solving the above linear equations, the following exponential integral table \(B_{m}\) is obtained,With exponential integral table \(B_{m}\), the discrete logarithm of any element \(a(T) \in \mathbb {F}_{q}^{*}\) can be easily calculated. Let \(a_{1}(T)=a(T)b(T)^{t}\), select the appropriate t such thatOnce the decomposition is established, there areThusThe discrete logarithm of a(T) is obtained.
$$b^{t}(T) \equiv c(T) ({{\,\mathrm{mod}\,}}f(T)),~ \deg c(T) \le n-1.$$
$$c(T)= c_{0} \prod _{p(T) \in L_{m} }p(T)^{\alpha _{c, p}},$$
$$\begin{aligned} \text {ind} (c(T))-\text {ind} (c_{0}) \equiv \sum _{p(T)\in L_{m}}\alpha _{c, p} \text {ind} (p(T))~({{\,\mathrm{mod}\,}}q-1). \end{aligned}$$
$$\begin{aligned} t-\text {ind} (c_{0}) \equiv \sum _{p(T)\in L_{m}}\alpha _{c, p} \text {ind} (p(T))~({{\,\mathrm{mod}\,}}q-1). \end{aligned}$$
(4.52)
$$\begin{aligned} B_{m}=\{\text {ind} (p(T))|p(T)\in L_{m}\}. \end{aligned}$$
(4.53)
$$a_{1}(T)\equiv a_{0} \prod _{p(T) \in L_{m} }p(T)^{\alpha _{a}}~ ({{\,\mathrm{mod}\,}}f(T)).$$
$$\text {ind}(a_{1}(T))=\text {ind} (a_{0})+ \sum _{p(T) \in L_{m} }\alpha _{a}\text {ind}(p(T)).$$
$$\text {ind}(a(T))=\text {ind} (a_{1}(T) )-t.$$
Remark 4.1
The key to the above calculation is to select an appropriate m to obtain the exponential integral table \(B_{m}\). This m cannot be too large, because \(h_{m}\) increases exponentially with m, for example, if m is a prime number, then by Corollary 4.4,When \(h_{m}\) is too large and calculating the exponential integral table \(B_{m}\), a matrix of order \(h_{m} \times h_{m}\) will be solved, and its computational complexity is exponential. Obviously, m cannot be too small, the selection of m depends on p and n, when \(p=2, n=127\), m’s best choice is \(m=17\). Select finite field \(\mathbb {F}_{q}\), \(q=2^{127}\), because \(q-1=2^{127}-1\) is a Mersenne prime. This is a popular option at present.
$$h_{m}=|L_{m}|=\frac{1}{m}(p^{m}-p).$$
ElGamal cryptosystem
Using the computational complexity of discrete logarithm to design asymmetric cryptosystem is the basic idea of ElGamal cryptosystem. Each user randomly selects a finite field \(\mathbb {F}_{q}\), \(q=p^{n}\), p is a sufficiently large prime number, and then calculates the generator g of \(\mathbb {F}_{q}^{*}\), select the positive integer x randomly, \(1<x<q-1,\) and calculate \(y=g^{x}\), to get the public key \(P_{e}=(y, g, q)\), own private key \(P_{d}=(x, g, q)\).
Encryption algorithm: To send an encrypted message to user A, user B first corresponds each plaintext unit of plaintext space P to an element in \(\mathbb {F}_{q}^{*}\), and then encrypts each plaintext unit. Let \(m \in \mathbb {F}_{q}^{*}\) be a plaintext unit, and user B randomly selects an integer k, \(1< k< q-1\), then, the public key (y, g, q) of user A is used to encrypt m, and the encryption algorithm f isGet cryptosystemtext \((c,c')\).
$$\begin{aligned} f(m)=c', \text {where}{\left\{ \begin{aligned}&c'=my^{k},\\&c=g^{k}. \end{aligned} \right. } \end{aligned}$$
(4.54)
Decryption algorithm: After receiving the cryptosystemtext \((c,c')\) sent by user B, user A decrypts \((c,c')\) with its own private key (x, g, q), decryption algorithm \(f^{-1}\) is
$$\begin{aligned} f^{-1}(c')=c'c^{-x}. \end{aligned}$$
(4.55)
Lemma 4.11
Proof
By (4.54), \(c=g^{k}, c'=my^{k},\) thenThat is to say \(f^{-1}(f(m))=m\), conversely,that is \(f(f^{-1}(c'))=c'\), therefore, f is the 1–1 correspondence of \(\mathbb {F}_{q}^{*}\longrightarrow \mathbb {F}_{q}^{*}\) and the inverse mapping of f is \(f^{-1}\). The Lemma holds.
$$\begin{aligned} c'c^{-x}=my^{k}g^{-kx}=mg^{xk}g^{-xk}=m. \end{aligned}$$
$$\begin{aligned} c'c^{-x}y^{k}=c'g^{-xk}g^{xk}=c'. \end{aligned}$$
Finally, we discuss the computational complexity over finite fields.
Lemma 4.12
\(\mathbb {F}_{q}\) is a finite field, \(q=p^{n}\), \(\alpha , \beta \in \mathbb {F}_{q}^{*}, k \ge 1\) is a positive integer, then
$$\text {Time}(\alpha \beta )=O(\log ^{3}q),$$
$$\text {Time}(\frac{\alpha }{\beta })=O(\log ^{3}q),$$
$$\text {Time}(\alpha ^{k})=O(\log k \log ^{3}q).$$
Proof
Let \(f(x)\in \mathbb {F}_{p}[x]\), \(\deg f(x)=n\), f(x) is a monic irreducible polynomial, thenLet \(\alpha , \beta \in \mathbb {F}_{q}^{*}\), thenThe multiplication of two polynomials requires \(n^{2}\) times of \({{\,\mathrm{mod}\,}}p\) operation, and the bit operation times of each \({{\,\mathrm{mod}\,}}p\) operation is \(O(\log ^{2}p)\), so \(\alpha \cdot \beta \) needs \(O(n^{2}\log ^{2}p)=O(\log ^{2}q)\)- bit operation to get a polynomial on \(\mathbb {F}_{p}[x]\). The resulting polynomial is divided by f(x) to obtain a polynomial of degree \(\le n-1\), that is, the final result of \(\alpha \cdot \beta \), the number of bit operations required for this operation is \(O(n\log ^{3}p)\). Therefore,the same can be estimated \(\text {Time}(\frac{\alpha }{\beta })\) and \(\text {Time}(\alpha ^{k})\). The Lemma holds.
$$\mathbb {F}_{q}=\mathbb {F}_{p}[x]/_{<f(x)>}=\{a_{0}+a_{1}x+\cdots +a_{n-1}x^{n-1}| \forall ~ a_{i} \in \mathbb {F}_{p}\}.$$
$$\alpha =a_{0}+a_{1}x+\cdots +a_{n-1}x^{n-1}, ~ \beta =b_{0}+b_{1}x+\cdots +b_{n-1}x^{n-1}.$$
$$\text {Time}(\alpha \beta )=O(\log ^{3}q+n\log ^{3}p)=O(\log ^{3}q),$$
4.7.4 Knapsack Problem
Given a pile of items with different weights, can you put all or several of these items into a backpack to make it equal to a given weight? This is a knapsack problem arising from real life. Abstract into mathematical problems: Suppose \(A=\{a_{0},a_{1}, \ldots , a_{n-1}\}\) are n sets of positive integers, N is a positive integer. Is N the sum of the elements of a subset in A? Using binary system, the knapsack problem in mathematics can be expressed as follows:
Knapsack problem: When N and \(A=\{a_{0},a_{1}, \ldots , a_{n-1}\}\) given, where each \(a_{i} \ge 1\) is a positive integer, whether there is a binary integer \(e=(e_{n-1}e_{n-2} \cdots e_{1}e_{0})_{2}\) makes the following formula true,If e exists, it is called knapsack problem (A, N) solvable, denote as \(\psi (A, N)=e\). If \(N=0\), then \(\psi (A, 0)=0\) (each \(e_{i}=0\)) is called a trivial solution. Therefore, \(N\ge 1\) is assumed to be a positive integer.
$$\sum _{i=0}^{n-1}e_{i}a_{i}=N, ~\text {where}~e_{i}=0 ~\text {or}~e_{i}=1.$$
The above knapsack problem may have solutions, no solutions or multiple solutions. It is very difficult to solve the general knapsack problem (A, N), which belongs to the “NP complete” problem. If the conjecture of \(``P \ne NP\)” holds, there is no general algorithm, and its computational complexity is polynomial of n and \(\log N\). However, under some special conditions, such as the so-called super-increasing sequence, the solution of the problem will be very easy. Next, we introduce the polynomial solution method on the premise of super-increasing sequence.
Definition 4.11
A positive integer sequence \(\{a_{i}\}_{i \ge 0}\) is called a super-increasing sequence, if each \(a_{i}(i \ge 1)\) is greater than the sum of the previous i positive integers, that is
$$\begin{aligned} a_{i}>\sum _{j=0}^{i-1}a_{j},~1 \le i < \infty . \end{aligned}$$
(4.56)
The knapsack problem of super-increasing sequence is actually to find a monotonically decreasing index sequence \(\{i_{k}\}_{k \ge 0}\), where \(i_{k}>i_{k+1},~ 0\le i_{k} \le n-1, ~\forall ~ k \ge 0.\) First, \(i_{0}\) is defined asThen consider \(N-a_{i_{0}}=0,\) then the algorithm is completed, that \(N=a_{i_{0}}.\) If \(N-a_{i_{0}}>0\), then defineFor any \(k \ge 1\), defineIf the equal sign in Eq. (4.58) holds, that is \(a_{i_{k}}=N-a_{i_{0}}-\cdots -a_{i_{k-1}}\), then the algorithm completes and obtains the solution \(N=a_{i_{0}}+a_{i_{1}}\cdots +a_{i_{k}}\) of (A, N). If \(i_{k}\) does not exist, that iscall the algorithm terminated. Obvious indicators \(i_{0}> i_{1}>\cdots> i_{k}>\cdots \). Let I be a set of some indicators, and denote the above algorithm as \(\psi \).
$$\begin{aligned} i_{0}=\max \{i|a_{i} \le N \}. \end{aligned}$$
(4.57)
$$i_{1}=\max \{i|a_{i} \le N-a_{i_{0}} \}.$$
$$\begin{aligned} i_{k}=\max \{i|a_{i} \le N-a_{i_{0}}-\cdots -a_{i_{k-1}}\}. \end{aligned}$$
(4.58)
$$N-a_{i_{0}}-\cdots -a_{i_{k-1}}<a_{i},~\forall ~ i \ne i_{0}, i_{1}, \ldots , i_{k-1},$$
Lemma 4.13
Let \(A=\{a_{0},a_{1}, \ldots , a_{n-1}\}\) be a given set of positive integers, \(a_{i}(i \ge 0)\) is a super-increasing sequence, N is a positive integer. If there is a \(k \ge 0\) that makes \(\psi \) complete at k, that is \(a_{i_{k}}=N-a_{i_{0}}-\cdots -a_{i_{k-1}}\), then the knapsack problem (A, N) has a solution and the solution iswhereIf there is a \(k \ge 0\), \(\psi \) that terminates at k, i.e.,Then the knapsack problem (A, N) has no solution.
$$\psi (A, N)=e=(e_{n-1}e_{n-2} \cdots e_{1}e_{0})_{2},$$
$$\begin{aligned} {\left\{ \begin{aligned}&e_{i}=1, ~\text {if}~i \in I,\\&e_{i}=0, ~\text {if}~i \not \in I. \end{aligned} \right. } \end{aligned}$$
$$N-a_{i_{0}}-\cdots -a_{i_{k-1}}<a_{i}, \forall ~i \not \in \{i_{0},i_{1},\ldots ,i_{k-1}\}.$$
Proof
If \(\psi \) is completed at \(k \ge 0\), thenLet \(e_{i}=1\), when \(i \in I; e_{i}=0\), when\(i \not \in I\), obviously,So \(\psi (A, N)=e=(e_{n-1}e_{n-2} \cdots e_{1}e_{0})_{2}\), if \(k \ge 0\) exists so that \(\psi \) terminates at k, that isThen the knapsack problem (A, N) has no solution. We can prove this conclusion by means of counter-evidence. If (A, N) has a solution, you might as well makeAdjust the order, we can let \(j_{0}>j_{1}>\cdots >j_{t}.\) By the definition of \(i_{0}\), and \(a_{j_{0}} \le N\), know \(j_{0} \le i_{0}\), thuscontradict with \(N=a_{j_{0}}+a_{j_{1}}+\cdots +a_{j_{t}}\), so (A, N) has no solution. The Lemma holds.
$$N=a_{i_{0}}+a_{i_{1}}+\cdots +a_{i_{k}},~ I=\{i_{0},i_{1},\ldots , i_{k}\},$$
$$\sum _{i=0}^{n-1}e_{i}a_{i}=N.$$
$$N-a_{i_{0}}-\cdots -a_{i_{k-1}}<a_{i}, \forall ~ i \not \in \{i_{0},i_{1},\ldots ,i_{k-1}\}.$$
$$N=a_{j_{0}}+a_{j_{1}}+\cdots +a_{j_{t}}.$$
$$N \ge a_{i_{0}} \ge a_{j_{0}} >\sum _{r=0}^{j_{0}-1}a_{r}\ge a_{j_{0}}+a_{j_{1}}+\cdots +a_{j_{t}}$$
MH knapsack public key encryption system
Merkle and Hellman first proposed an encryption method using knapsack problem in 1978, it is the first public key encryption password. Let \(A=\{a_{0},a_{1}, \ldots , a_{n-1}\}\) be a sequence of super-increasing positive integers, take p, b as two prime numbers and satisfyCalculate \(t_{i} \equiv ba_{i}({{\,\mathrm{mod}\,}}p),~0 \le i \le n-1\), then the public key is \(t=(t_{0},t_{1}, \ldots , t_{n-1})\), private key are A and b.
$$\begin{aligned} p>\sum _{i=0}^{n-1}a_{i}, ~1 \le b \le p-1. \end{aligned}$$
(4.59)
Encryption algorithm: The plaintext space \(P=\mathbb {F}_{2}^{n}\), for each plaintext unit \(m=(m_{0}m_{1}\cdots m_{n-1})\in P\), encryption algorithmwhere c is cryptosystemtext.
$$\begin{aligned} c=f(m)\equiv \sum _{i=0}^{n-1}t_{i}m_{i}({{\,\mathrm{mod}\,}}p), ~0\le c \le p, \end{aligned}$$
(4.60)
Decryption algorithm: First, use the private key \(N \equiv b^{-1}c({{\,\mathrm{mod}\,}}p), ~0\le N \le p-1\). Then use the algorithm \(\psi =f^{-1}\) of knapsack problem (A, N) to solveto get plaintext \(m=(m_{0}m_{1}\cdots m_{n-1})\).
$$\begin{aligned} f^{-1}(N)=(m_{0}m_{1}\cdots m_{n-1})\in \mathbb {F}_{2}^{n}, \end{aligned}$$
(4.61)
The correctness of MH knapsack public key cryptography is attributed to the following Lemma.
Lemma 4.14
Proof
If \(m=0\) is the zero vector in \(\mathbb {F}_{2}^{n}\), then \(c=0\), thus \(N=0\). Knapsack problem (A, 0) has a unique trivial solution \(\psi (A, 0)=0 \in \mathbb {F}_{2}^{n}\) is a zero vector. Therefore, the zero vector in \(\mathbb {F}_{2}^{n}\) is a 1–1 correspondence of the zero element in \(\mathbb {F}_{p}\). Let \(m \ne 0\), ifThenBy (4.59) and \(0 \le N < p\), to obtainSo we haveConversely, ifthenSo there is \(N \equiv b^{-1}c({{\,\mathrm{mod}\,}}p),\) that isIt can be seen that f is a 1–1 correspondence of \(\mathbb {F}_{2}^{n}\longrightarrow \mathbb {F}_{p}\) and the inverse mapping is \(f^{-1}= \psi \). The Lemma holds.
$$N \equiv b^{-1}c({{\,\mathrm{mod}\,}}p),~c\equiv \sum _{i=0}^{n-1}t_{i}m_{i}({{\,\mathrm{mod}\,}}p).$$
$$N \equiv \sum _{i=0}^{n-1}m_{i}b^{-1}t_{i} \equiv \sum _{i=0}^{n-1}m_{i}a_{i}({{\,\mathrm{mod}\,}}p).$$
$$N = \sum _{i=0}^{n-1}m_{i}a_{i}, \Longrightarrow \psi (A, N)=m=m_{0}m_{1}\cdots m_{n-1}.$$
$$f^{-1}(f(m))=m, ~\forall ~ m \in \mathbb {F}_{2}^{n}.$$
$$N = \sum _{i=0}^{n-1}m_{i}a_{i},$$
$$bN \equiv \sum _{i=0}^{n-1}m_{i}a_{i}b\equiv \sum _{i=0}^{n-1}m_{i}t_{i}({{\,\mathrm{mod}\,}}p).$$
$$f(f^{-1}(c))=c, ~\forall ~ c \in \mathbb {F}_{p}.$$
It can be seen from the above discussion that if \(A=\{a_{0},a_{1}, \ldots , a_{n-1}\}\) is not a super-increasing sequence, the decryption algorithm \(f^{-1}\) is a difficult problem of “NP complete class", so the encryption and decryption algorithm defined by MH knapsack cryptosystem is the most typical trapdoor single function. Because of this, people believe that MH knapsack public key cryptography is very secure for a long time. However, in 1982, Shamir proved that a class of nonsuper-increasing sequences can be transformed into super-increasing sequences by a simple transformation \(x\longrightarrow ax {{\,\mathrm{mod}\,}}m\), which can be solved by polynomial algorithm. Although this kind of convertible nonsuper-increasing sequence knapsack problem is quite special, it is enough to shake people’s confidence in the security of knapsack problem public key cryptosystem. It is now generally accepted that knapsack public key cryptography is no longer secure.
Shamir transform
Let \(A_{1}=\{\alpha _{0},\alpha _{1}, \ldots , \alpha _{n-1}\}\) is a super-increasing sequence of positive integers. Randomly select four positive integers \(m_{1}, a_{1}, m_{2}, a_{2}\), whereA new positive integer sequence is defined by \(m_{1}\) and \(a_{1}\),Where \(a_{1}\alpha _{i} {{\,\mathrm{mod}\,}}m_{1}\) represents the minimum nonnegative residue of \(a_{1}\alpha _{i}\) \( {{\,\mathrm{mod}\,}}m_{1}\), that isBy the third sequence of positive integers is defined by \(m_{2}\) and \(a_{2}\),that isBecause \(\{u_{i}\}\) is not a super-increasing sequence, if \(A_{3}\) is used for encryption, it seems to be a general knapsack problem. Its difficulty will be NP complete, but Shamir transform will prove that its decryption algorithm is polynomial.
$$\begin{aligned} m_{1}>\sum _{i=0}^{n-1}\alpha _{i}, ~m_{2}>nm_{1}, ~(a_{1}, m_{1})=(a_{2}, m_{2})=1. \end{aligned}$$
(4.62)
$$A_{2}=\{\omega _{0},\omega _{1}, \ldots , \omega _{n-1}\}, ~\text {where}~\omega _{i}=a_{1}\alpha _{i} {{\,\mathrm{mod}\,}}m_{1}.$$
$$\begin{aligned} 0 \le \omega _{i}<m_{1}, ~\text {and}~\omega _{i} \equiv a_{1}\alpha _{i} ({{\,\mathrm{mod}\,}}m_{1}). \end{aligned}$$
(4.63)
$$A_{3}=\{u_{0},u_{1}, \ldots ,u_{n-1}\}, ~u_{i}= a_{2}\omega _{i} {{\,\mathrm{mod}\,}}m_{2},$$
$$\begin{aligned} 0 \le u_{i}<m_{2}, ~u_{i} \equiv a_{2}\omega _{i} ({{\,\mathrm{mod}\,}}m_{2}). \end{aligned}$$
(4.64)
Let \(x=(e_{n-1}e_{n-2}\cdots e_{1}e_{0})_{2}\in \mathbb {F}_{2}^{n}\) be clear text and encrypt with \(A_{3}\),get cryptosystemtext c. If decryption is required after receiving cryptosystemtext c, it is a general knapsack problem, but the problem of using private key \((b_{1}, m_{1}, b_{2}, m_{2})\) will become quite simple, whereFirst, note the minimum nonnegative residue of \(b_{2}c\) under \({{\,\mathrm{mod}\,}}m_{2}\),Because by (4.65),By the assumption \(m_{2}>nm_{1}\) of formula (4.62), and (4.63), there isSo (4.66) holds. Then consider the minimum nonnegative residue \(N=b_{1}N_{0} {{\,\mathrm{mod}\,}}m_{1}(0 \le N <m_{1})\) of \(b_{1}N_{0}\) \({{\,\mathrm{mod}\,}}m_{1}\), by (4.63),So there isSince \(A_{1}\) is a super-increasing sequence, the algorithm of polynomial (see Lemma 4.13), we haveTo get plaintext x.
$$\begin{aligned} c=f(x)=\sum _{i=0}^{n-1}e_{i}u_{i}, \end{aligned}$$
(4.65)
$$\begin{aligned} {\left\{ \begin{aligned}&0 \le b_{1}<m_{1}, \ ~a_{1}b_{1}\equiv 1({{\,\mathrm{mod}\,}}m_{1})\\&0 \le b_{2} <m_{2}, \ ~a_{2}b_{2}\equiv 1({{\,\mathrm{mod}\,}}m_{2}). \end{aligned} \right. } \end{aligned}$$
$$\begin{aligned} N_{0}=b_{2}c {{\,\mathrm{mod}\,}}m_{2}=\sum _{i=0}^{n-1}e_{i}\omega _{i}. \end{aligned}$$
(4.66)
$$b_{2}c \equiv \sum _{i=0}^{n-1}e_{i}b_{2}u_{i}\equiv \sum _{i=0}^{n-1}e_{i}\omega _{i}({{\,\mathrm{mod}\,}}m_{2}). $$
$$ 0 \le \sum _{i=0}^{n-1}e_{i}\omega _{i}< m_{2}. $$
$$N=b_{1}N_{0}\equiv \sum _{i=0}^{n-1}e_{i}b_{1}\omega _{i}\equiv \sum _{i=0}^{n-1}e_{i}\alpha _{i}({{\,\mathrm{mod}\,}}m_{1}). $$
$$N= \sum _{i=0}^{n-1}e_{i}\alpha _{i},~\alpha _{i} \in A_{1}.$$
$$\psi (A_{1},N)=(e_{n-1}e_{n-2}\cdots e_{1}e_{0})_{2}=x.$$
Therefore, Shamir uses simple transformation to transform the general knapsack problem into super-incremental knapsack problem. Although \(A_{3}\) is very special, we have reason to doubt that the public key cryptography based on the general knapsack problem solving algorithm is not as secure as people think.
Exercise 4
1.
Explain the following terms. (1) One secret at a time, (2) Completely confidential system, (3) Unique solution distance, (4) Improve the certification system.
2.
Short answer:
(1)
What are the advantages and disadvantages of symmetric cryptosystem and asymmetric cryptosystem?
(2)
The goal of perfecting the certification system.
3.
It is known that the plaintext is “Friday”, and the cryptosystemtext obtained after encryption with \(m=2\)’s Hill password is “POCFKU”, find the key of Hill password.
4.
Find the inverse matrix \(({{\,\mathrm{mod}\,}}N)\) of the following matrix:
$$A= \left[ \begin{array}{cccc} 1 &{} 3 \\ 4 &{} 3 \end{array}\right] {{\,\mathrm{mod}\,}}5,~ A= \left[ \begin{array}{cccc} 1 &{} 3 \\ 4 &{} 3 \end{array}\right] {{\,\mathrm{mod}\,}}29,$$
$$A= \left[ \begin{array}{cccc} 15 &{} 17 \\ 4 &{} 9 \end{array}\right] {{\,\mathrm{mod}\,}}26,~ A= \left[ \begin{array}{cccc} 197 &{} 62 \\ 603 &{} 271 \end{array}\right] {{\,\mathrm{mod}\,}}841.$$
5.
In number theory, Fibonacci number is defined as \(a_{1}=1,a_{2}=1,a_{3}=2\), when \(n>1\), \(a_{n+1}=a_{n}+a_{n-1}\). Prove and \(a_{n}\) is even if and only if 3|n. More generally, find the law of \(d|a_{n}\).
$$ \left[ \begin{array}{cccc} a_{n+1} &{} a_{n} \\ a_{n} &{} a_{n-1} \end{array}\right] = \left[ \begin{array}{cccc} 1 &{} 1 \\ 1 &{} 0 \end{array}\right] ^{n},$$
6.
Suppose \(N=mn\), and \((n,m)=1\). A second-order matrix \(A\in M_{2}(\mathbb {Z}_{N})\) on n\(\mathbb {Z}_{N}\), can consider \(A\in M_{2}(\mathbb {Z}_{m})\) and \(A\in M_{2}(\mathbb {Z}_{n})\), let \(A_{1}\) and \(A_{2}\) represent the elements of A in \(M_{2}(\mathbb {Z}_{m})\) and \(M_{2}(\mathbb {Z}_{n})\), then prove
(i)
Mapping \(A{\mathop {\longrightarrow }\limits ^{\sigma }}(A_{1},A_{2})\) is a 1–1 correspondence between \(M_{2}(\mathbb {Z}_{N}){\mathop {\longrightarrow }\limits ^{\sigma }}M_{2}(\mathbb {Z}_{m})\times M_{2}(\mathbb {Z}_{n})\).
(ii)
In the corresponding \(\sigma \), A is the invertible matrix \(({{\,\mathrm{mod}\,}}N)\) if and only if \(A_{1}\) is the invertible matrix \(({{\,\mathrm{mod}\,}}m)\) and \(A_{2}\) are the invertible matrix \(({{\,\mathrm{mod}\,}}n)\).
7.
Let p be a prime, \(\alpha \ge 1\), then \(A\in M_{2}(\mathbb {Z}_{p^{\alpha }})\) is a reversible square matrix if and only if \(A\in M_{2}(\mathbb {Z}_{p})\) is a reversible square matrix. By calculate, for \(\forall ~ \alpha \ge 1\), find the number of reversible matrices in \(M_{2}(\mathbb {Z}_{p^{\alpha }})\).
8.
Let \(\varphi (N)\) be Euler function, \(\varphi _{2} (N)\) is the number of invertible matrices in \(M_{2}(\mathbb {Z}_{N})\), calculation formula for \(\varphi _{2} (N)\): that is, write a formula for \(\varphi _{2} (N)\) similar to \(\varphi (N)\). Known \(\varphi (N)=N\prod _{p|N}(1-\frac{1}{p})\), solve \(\varphi _{2} (N)=?\)
9.
Let \(\varphi _{k} (N)\) be the number of k-order reversible matrices in \(M_{k}(\mathbb {Z}_{N})\) and give the calculation formula of \(\varphi _{k} (N)\).
10.
According to exercise 8 and exercise 9, find the order of k-dimensional affine transformation group \(G=(A,b)\) on \(\mathbb {Z}_{N}\).
11.
RSA is used for encryption, the alphabet of plaintext and cryptosystemtext is \(\{0,1,2,\ldots , 39\}\) 40 numbers, of which \(\{0,1,2,\ldots , 25\}\) 26 numbers are equivalent to English 26 letters. Blank \(=26\), \(\bullet =27\), \(?=28\), \(\$=29\), number \(\{0,1,2,\ldots , 9\}=\{30,31,\ldots , 39\}\). Suppose all public keys \(n_{A}\) satisfy \(40^{2}<n_{A}<40^{3}\). Plaintext unit \(m=m_{1}m_{2}\in \mathbb {Z}_{40}^{2}\), cryptosystemtext unit \(c=c_{1}c_{2}c_{3}\in \mathbb {Z}_{40}^{3}\). For any plaintext unit, \(m=m_{1}m_{2}\) corresponds to a number \(m_{2}40+m_{1}\) of \(\mathbb {Z}_{n_{A}}\), any cryptosystemtext \(c=c_{3}40^{2}+c_{2}40+c_{1}\in \mathbb {Z}_{n_{A}}\).
(i)
Encrypting plaintext "\(SEND \$7500\)" with public key \((n_{A},e_{A})=(2047,179)\).
(ii)
Factor \(n_{A}=2047\) to find the private key \((n_{A},d_{A})=?\)
(iii)
A password attacker can quickly find the private key \(d_{A}\) without factoring 2047, so \(n_{A}=2047\) is a pretty bad choice. Why?
12.
The computer attacks the public key \((n_{A},e_{A})=(536813567,3602561)\) and finds the private key \(d_{A}\). It shows that 29-bit \(n_{A}\) is not safe in RSA system.
13.
Assuming that the plaintext alphabet is \(\{0,1,\ldots , 26\}\), and the first 26 numbers are 26 letters in English, blank \(=26\). Cryptosystemtext alphabet adds \(``|"=27\) to the plaintext alphabet, a total of 28 numbers. If the plaintext unit is \(m=m_{1}m_{2}m_{3}\in \mathbb {Z}_{27}^{3}\), Cryptosystemtext unit is \(c=c_{1}c_{2}c_{3}\in \mathbb {Z}_{28}^{3}\). Then in the corresponding number of \(Z_{n_{A}}\) (see exercise 11), we need \(n_{A}\) to meet
$$19683=27^{3}<n_{A}<28^{3}=21952,$$
(i)
If your decryption key is \((n_{A},d_{A})=(21583,20787)\), decrypt cryptosystemtext is “YSNAUOZHXXH" (blank at the end).
(ii)
If you know the Euler function \(\varphi (n)=21280\), calculate \(e=d^{-1} {{\,\mathrm{mod}\,}}\varphi (n)\) and factorize n.
14.
Prove: In RSA, the 35 bit integer \(n=23360947609\) is a particularly bad choice. (Hint: \(n=p\cdot q\) factorization, the size difference between p and q remains unchanged, and Fermat factorization can be used to attack.)
15.
Let n be a square free number, and \(de\equiv 1({{\,\mathrm{mod}\,}}\varphi (n))\). It is proved that there is congruence for all integers a.
$$a^{de}\equiv a({{\,\mathrm{mod}\,}}n)$$
16.
The multiplication group \(\mathbb {F}_{181}^{*}\) of finite field \(\mathbb {F}_{181}\) is generated by \(g=2\), the discrete logarithm of 153 pairs of basis 2 is calculated by smoothing factor method.
17.
In the knapsack problem, determine whether the following sequence is an over increasing sequence, whether the knapsack problem is solvable for a given N, and how many solutions there are:
(i)
\(A=\{2,3,7,20,35,69\}, N=45;\)
(ii)
\(A=\{1,2,5,9,20,49\}, N=73;\)
(iiii)
\(A=\{1,3,7,12,22,45\}, N=67\);
(iv)
\(A=\{2,3,6,11,21,40\}, N=39;\)
(v)
\(A=\{4,5,10,30,50,101\}, N=186.\)
18.
If \(A=\{a_{i}|i=0,1,2,\cdots \}\) is an over increasing sequence and \(a_{0}=1\), \(a_{i}\) is the smallest positive integer satisfies \(a_{i}\ge \sum _{j=0}^{i-1}a_{j}\), then \(a_{i}=2^{i}\) holds for \(\forall ~ i\ge 1\).
19.
Let \(A=\{a_{0},a_{1}, \ldots ,a_{i},\ldots \}\) be a super-increasing sequence, where \(a_{i}=2^{i}(i\ge 1)\), then for any positive integer N, Knapsack problem (A, N) has a unique solution.
20.
Let \(A=\{a_{0},a_{1}, \ldots , a_{i}, \ldots \}\) be a super-increasing sequence, if for any positive integer N, knapsack problem (A, N) always has a solution, prove \(a_{i}=2^{i}(i\ge 1)\).
Open Access This chapter is licensed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made.
The images or other third party material in this chapter are included in the chapter's Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the chapter's Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.