# 1. Overview of public cryptography

In the previous chapter we learned about symmetric ciphers. It is clear that the participants need a cryptographic key to encrypt and decrypt. This means exchanging the secret key over the channel. Keeping the secret of a secret key is synonymous with keeping information confidential. So the exchange of keys only takes place on the secret channel to ensure, but this exchange is not easy to ensure high security. From here came the idea of public cryptography. That is, there is no need to exchange a secret key over the channel.

The idea of a public cryptosystem was introduced by Diffie and Hellman in 1976. As for the implementation of a public cryptosystem, first proposed by Rivest, Shamir and Adleman in 1977, they proposed a well-known RSA cryptosystem. And since then there are a number of other cryptosystems published, their densities based on different computations, such as on the difficulty of factor decomposition problems such as RSA cryptosystems, based on discrete logarithm difficulty. discrete as the ElGamal cryptosystem, or based on the Elliptic curve. We will explore these cryptosystems in detail in the following sections. But first let’s look at the scheme and coding and decoding principles of the public cryptosystem.

The schematic diagram of the public cipher system is shown in the following figure:

The public cryptosystem uses two keys that are mathematically related, that is, one key is formed from the other: The person who wants to receive the cipher (Alice) creates a private key and a private key. issuing the public key (public key) with an uncomplicated procedure, while finding the secret key when knowing the public key is a difficult problem to solve. The public key is sent to the sender of the message (Bob) over a public channel. And the message is encrypted by Bob with the public key. The ciphertext travels to Alice, and it is decrypted using the secret key.

# 2. The RSA cryptosystem

## a. History begin

The algorithm was first described by Ron Rivest, Adi Shamir and Len Adleman in 1977 at the Massachusetts Institute of Technology (MIT). The name of the algorithm is taken from the first 3 letters of the names of 3 authors. This is the first algorithm suitable for creating digital signatures at the same time with encryption. It marked a huge advance in the field of cryptography in the use of public keys. RSA is commonly used in e-commerce and is believed to be secure provided the key length is large enough.

The RSA algorithm was patented by MIT in the United States in 1983 (Registration Number 4,405,829). This patent expired on September 21, 2000. However, since the algorithm was published prior to being registered for protection, protection is hardly valid outside the United States. In addition, if the work of Clifford Cocks had been published before, the RSA patent could not be registered.

An algorithm based on the difficulty of the problem decomposes a number into a factor.

## b. Key generation process for the RSA cryptosystem.

Suppose that Alice and Bob need to exchange confidential information over an insecure channel (eg the Internet). With the RSA algorithm, Alice first needs to generate her own key pair including the public and secret keys according to the following 6 steps:

### Encoding process:

### Decoding process:

## c. Some important notes about RSA

Security: The security of the RSA system is based on two mathematical problems: the problem of analyzing the prime factors of large integers and the RSA problem. If the above 2 problems are difficult (can not find an effective algorithm to solve them) then it is not possible to perform complete decoding for RSA. Partial decoding must be prevented by secure plaintext conversion methods. The RSA problem is the computation of the e-root of the module n (where n is the composite number): find the number m such that me = c mod n, where (e, n) is the public key and c is the ciphertext. Currently the most promising way to solve this problem is to decompose n into prime factors. Once this is done, the attacker will find the secret exponent d of the public key and can decrypt it in accordance with the algorithm’s process. If the attacker finds two primes p and q such that: n = pq then it is easy to find the value (p-1) (q-1) and thereby determine d from e. In the chapter of arithmetic we know that no method has been found on the computer to solve this problem in polynomial-time. However, it has not been able to prove the opposite (the non-existence of the algorithm).

Speed: RSA has a significantly slower execution speed than symmetric ciphers. In fact, Bob uses some symmetric cipher algorithm to encrypt the text to be sent and only uses RSA to encrypt the key to decrypt (normally the key is much shorter than the text). This approach also creates new security problems. One example is the need to generate truly random symmetric keys. Otherwise, the attacker (usually denoted Eve) will ignore the RSA and focus on guessing the symmetric key.

Key length: Number n should have a size of no less than 512 bits. In 2006 the RSA cryptosystem is considered effective with the size n must be from 1024. And they recommend that in the future the length n should be 2024 bits.

### Select public parameters:

To improve encoding speed, we should choose e with a small value, usually 3, 7 or 65537. These numbers, when represented in binary form, have only 2 digits 1, so when executing the command the power will decrease the multiplication command.

### Choose your secret parameter.

# 3. Elgama honey system

Elgama cryptosystem is formed on the basis of discrete logarithmic problem. Proposed in 1984. Then the standard electronic signature of the US and Russia was formed on the basis of this cryptosystem.

## a. Key formation:

## b. T message encryption process:

## c. Decoding process:

# 4. Rabin bile system

This is a cryptosystem based on the complexity of calculating the square root of the number. This is a density system that is computationally secure against a selected plaintext attack and cannot be analyzed by n = pq. The algorithm is used a lot in practice.

## a. Rabin cryptosystem algorithm

### Key generation process:

### Encoding process:

### Decoding process:

We prove this xxx algorithm is cryptosystem, which means that the decryption performed by Alice will restore the plaintext encrypted by Bob.

Solving the quadratic equation, we have a common solution:

# 5. Merkle-hellman cryptosystem

The Merkle-hellman three-pack cipher was described by Merkle-hellman in 1978. This cryptosystem was broken in 1980, after which a number of variations emerged. Although it is broken, it shows us a sophistication in cryptographic design. This problem is based on the problem of the sum of subsets. The problem is stated as follows

## a. The problem of the sum of subsets.

Based on this solution Merle-Hellman went to build his algorithm. The algorithm’s idea is, use the super-increment sequence to decode, and decrypt with a non-super-incremental sequence, that is, the hyper-increment chain acts as the secret key, and the non-hyper-increment sequence acts as the public key. From here they come up with a way to turn the super-incremented sequence into the non-countable sequence, and finding the super-increment sequence by public key is a difficult problem. One transformation proposed by Merle-Hellman is to transform the super-increment chain modulo primes, such that:

## b. Herkle-Hellman cryptosystem

### Encoding process:

### Decoding process.

# 6. McEliece honey system

The McEliece cryptosystem was proposed in 1978, by its author Robert McEliece. The idea of this problem is similar to that of the Merkle-Hellman cryptosystem: Decoding is a special case of the complete NP problem.

To understand this cryptosystem, you must have a basic knowledge of the basic theory of information transmission.