What is public key encryption 1

Overview of encryption methods

Rivest, Shamir, Adleman (RSA)

RSA is considered to be one of the most secure and best-described public key methods. The idea of ​​implementing encryption using a public encryption key and a secret decryption key goes back to the cryptologists Whitfield Diffie and Martin Hellman. This published in 1976 with the Diffie-Hellman key exchange a process that enables two communication partners to agree on a secret key together over an insecure channel. The researchers relied on the one developed by Ralph Merkle Merkle's puzzle. One therefore speaks of the Diffie-Hellman-Merkle key exchange (DHM).

The cryptogens made more mathematical use One-way functionswhich are easy to perform, but can only be reversed with considerable computational effort. The key exchange named after them is still used today to negotiate secret keys within the framework of symmetrical cryptosystems. Another merit of the research duo is the concept of Trapdoor Already in the publication of the Diffie-Hellman key exchange, hidden abbreviations are addressed that are supposed to make it possible to accelerate the inversion of a one-way function. Diffie and Hellmann did not provide any concrete evidence, but with their theory of the trapdoor they stimulated numerous cryptologists to conduct their own investigations.

Rivest, Shamir, and Adleman also looked Abbreviations for one-way functions - originally with the motivation to refute the trapdoor theory. But their research developed in a different direction and resulted in the encryption process that was finally named after them. Today, RSA is considered to be the first scientifically published algorithm that is a Transmission of encrypted data without exchanging a secret key enables.

The RSA uses an algorithm that is based on the Multiplication of large prime numbers supports. While it is generally not a problem to multiply two prime numbers by 100, 200 or 300 digits, there is still no efficient algorithm that can reverse the result of such an arithmetic operation into its prime factors. That can be clarified Prime factorization using an example:

Multiplying the prime numbers 14,629 and 30,491 gives the product 446,052,839. This has only four factors: 1, itself and the two prime numbers that were multiplied. If you delete the first two factors, since every number is divisible by 1 and by itself, you get the output values ​​14,629 and 30,491.

This scheme is the basis of RSA key generation. Both the public and the private key represent two pairs of numbers:

Public key: (e, N)

Private key: (d, N)

At N it is the so-called RSA module. This is contained in both keys and results from the product of two randomly chosen, very large prime numbers p and q (N = p x q).

You also need to generate the public key e, a number that is chosen randomly with certain restrictions. If you combine N and e you get the public key, which is available to every communication participant in plain text.

In order to generate the private key, besides N also d. At d it is a value that results from the randomly generated prime numbers p and q as well as the random number e results based on the Euler's phi function (φ) be offset against each other.

Which prime numbers are used in the calculation of the private key must remain secret in order to guarantee the security of the RSA encryption. The product of the two prime numbers, on the other hand, can be used in plain text in the public key, since it is assumed that there is no efficient algorithm nowadays that can factor the product of very large prime numbers into its factors in a relevant time. It is therefore not possible p and q out N to calculate. Unless you can shorten the calculation. Such Trapdoor represents the value d that is only known to the owner of the private key.

The security of the RSA algorithm is highly dependent on technical progress. The computing power of computers doubles roughly every two years. It cannot therefore be ruled out that in the foreseeable future an efficient method for prime factorization in the order of magnitude customary today will be available. In this case, RSA offers the option of adapting the algorithm to technical developments by using even larger prime numbers to calculate the key.

For the secure operation of the RSA method, the Federal Network Agency specifies a minimum length of 1,976 bits for the value N (the product of both prime numbers) by the end of 2020, but recommends 2,048 bits. This corresponds to prime numbers on the order of about 300 decimal places.