What is a public key cryptographic algorithm?

In the 1970s, American scholars Diffie and Hellman, and Israeli scholar Merkle independently developed the concept of a completely new cryptographic regime.Diffie and Hellman first published the concept at the 1976 National Computer Conference, and a few months later their seminal paper, "New Directions in Cryptology Directions" was published in the Information Theory volume of the IEEE Journal, Merkle's contribution to this field was not published until 1978 for printing reasons. The new cryptographic theory they created broke with the traditional concept of symmetric keys for cryptographic systems and erected another milestone in modern cryptography.

Unlike previous symmetric cryptographic regimes, which used the same encryption and decryption keys, Diffie and Hellman proposed the use of a dual-key regime, in which each user has a selected pair of keys: one that can be made public, and another that is secret. The public key can be published like a telephone number, hence the name public-key cryptosystem or dual-key system.

The main feature of public key cryptosystems is the separation of the ability to encrypt and decrypt, thus enabling messages from multiple users to be deciphered by only one user; or messages to be encrypted by only one user and deciphered by multiple users; the former can be used in a public **** network to enable confidential communications, while the latter can be used in authentication systems to digitally sign messages.

The basic idea of public key cryptography is to divide the key of a traditional cipher into two, into an encryption key Ke and a decryption key Kd, and control encryption with the encryption key Ke and decryption with the decryption key Kd. Moreover, the computational complexity ensures that the encryption key Ke cannot be computationally deduced from the decryption key Kd. In this way, even if Ke is made public, it will not expose Kd, and will not jeopardize the security of the cipher. It is then possible to make Ke public and keep only Kd secret. Since Ke is public and only Kd is kept secret, the difficulty of traditional ciphers in key distribution is fundamentally overcome.

Conditions satisfied by public key cipher

Based on the basic idea of public key cipher, it can be seen that a public key cipher should satisfy the following three conditions:

The decryption algorithm D and the encryption algorithm E are mutually inversible, i.e., for all the plaintexts M there are, D(E(M,Ke). Kd) = M. Computationally Kd cannot be derived from Ke. Algorithms E and D are both efficient.

Condition 1 is the basic condition that constitutes a cipher, and is the minimum condition that must be present in both traditional and public key ciphers.

Condition 2 is the security condition for public-key ciphers and is the basis for the security of public-key ciphers, and it is the most difficult condition to fulfill. It is not yet possible to prove mathematically that a public-key cipher fully satisfies this condition, but only that it does not.

Condition 3 is the engineering utility condition for public key ciphers. Because the cipher can be practical only if both algorithms E and D are efficient. Otherwise, the cipher has only theoretical significance and cannot be practically applied.

Satisfying the above three conditions can constitute a public key cipher, which can ensure the secrecy of the data. However, it is also necessary to ensure the authenticity of the data, the fourth condition needs to be satisfied.

4. For all plaintexts M there is E(D(M,Kd),Ke)=M.

Condition 4 is the basic condition that a public key cipher can ensure the authenticity of data. If conditions 1, 2, and 4 are satisfied, the same can constitute a public key cipher which can ensure the authenticity of the data.

If the above four conditions are satisfied at the same time, the public key cipher can ensure the secrecy and authenticity of the data at the same time. At this time, for all plaintexts M have D(E(M,Ke),Kd) = E(D(M,Kd),Ke) = M.

The public-key cipher fundamentally overcomes the difficulties of traditional cipher in key distribution, and the use of the public-key cipher for confidential communication requires the establishment of a key management center (KMC), where each user registers his or her name, address, and publicly available encryption key Each user registers his name, address, and public encryption key with the KMC and enters the public key into the public key database that *** enjoys.The KMC is responsible for the management of the key and is trustworthy to the user. In this way, users use the public key cipher for confidential communication is as convenient as checking the telephone directory to make a phone call, no longer need to communicate with both parties to reserve the key, so it is particularly suitable for computer network applications, and the public key cipher is easy to realize the digital signature, so it is particularly popular.

The following figure is a block diagram of a public-key cryptosystem, which is divided into the following steps:

The end system in the network that is required to receive the message, generates a pair of keys used for encryption and decryption, such as receiver B in the figure, and generates a pair of keys, PKB, SKB, in which PKB is the public key and SKB is the secret key. The end system B stores the encryption key (PKB in the figure) in a public register or file, and the other key is kept secret (SKB in the figure). to send a message m to B, A encrypts m using B's public key, denoted as c=EPKB[m] where c is the ciphertext and E is the encryption algorithm. after B receives the ciphertext c, it decrypts it using its own secret key SKB, denoted as m=DSKB [c] where D is the decryption algorithm. Since only B knows SKB, no one else can decrypt c.

This is how the public key works~

(Reprinted with permission from me)