How does the RSA encryption work?

The question "How does the RSA encryption work?"Can be understood in two ways:

1. What calculations are needed for the RSA-en- and decryption?
2. Why do the corresponding formulas work?

Below I will for the RSA-en- and decryption explain the necessary calculations and then briefly outline, why these formulas work.

1 Calculations for en- and decryption work

Before en- and decrypting, must first be created a corresponding key pair (Section 1.1). In the section thereafter 1.2 is the key pair used, in order to encrypt plain text and then decrypt it back.

1.1 Generating a key pair

To generate a key pair, two large prime are numbers needed, we call them p and q. These prime numbers are only required to generate the key pair, or more accurately, in order to calculate the private from the public key. When this is done, the prime numbers are no longer needed.

From the two prime numbers, the product m calculated, and used as residue class (modulo) .:

(1) m=p*q

Then choose a random number e (encode), which (together with m) is used as a public key. It must be relatively prime and smaller than phi(m) .. In the next step, from this key, the key to decrypt d (dechipher) must be calculated. For this, a d must be found, so that the following formula is satisfied:

(2) e*d mod phi(m) = 1

phi() denotes the Euler function. For large numbers it is so hard to determine , that even modern computers would need decades to do so. There is one exception: If the prime factorization of m known. Since we m have m calculated as the product of two primes, we know the prime factorization: p and q. In this case, phi(m) can be calculated as:

(3) phi(m)=(p-1)*(q-1)

Now (2) is solved using the extended Euclidean algorithm.

Then we have:

(e,m) as a public key and

(d,m) as private key.

All other values ​​are no longer needed.

1.2 En- and decrypt

A number C (Plain text) with the public key can be encrypted as follows:

(4)

V is the encrypted plaintext. This number can be decrypted by the following formula :

(5) V^d mod m = K

2 Why do the formulas for en- and decryption work?

It will be shown, that after the application of the encryption formula (4) on C and then the decryption formula (5) the original number C comes out again.

First, this must be somewhat limited: en- and decryption only works for plain text C, if it is relative prime to the modulo m _.

The RSA system works, because

1. to all m prime numbers modulo m form a group (Assertion 1) and
2. in a group it is always true, that a number obtained from the group exponentiated with the number of elements in the group is always the number one (Assertion 2: Euler-Fermat).

First, I show, that, if these two conditions are met, the RSA method does work. Then I show, that both conditions are met.

En- and decryption is applied in a row:

(6) (C^e)D ^ v m = K

It will be shown here, that this C comes out. In (6) parentheses can be resolved:

(7) C^{e * d} mod m = K

Where possible, a the number of elements (meaning. the number of m prime numbers) called, if so:

(8) C^a *K v m = K,

since according to claim 2 is: C^a v m = 1. Formula (8) can be transformed into

(9) C^{a 1} mod m = K

Since a number raised to the number of elements a the number 1 results, it does this for 2*a, 3*a, 4*a…, general f*a:

(10) C^{a*f 1} mod m = K

Dh. Equation (7) is satisfied, if and only if:

(11) f 1 = a * d * e

This corresponds to the calculation of d the formula (2), because phi(m) is the number of m prime numbers a an (this is the definition of the Euler function):

(12) a = non-(m)

In (11) used, we get:

(11) phi(m)*f + 1= D * and

If in (2) of Module phi(m) removed, by an appropriate factor f selected, obtained exactly (11).

This shows, that - if the assertions 1 and 2 apply - by inserting a number C in formula (4) a coded number V can be calculated, so that by inserting this number in formula (5) the original number C comes out. In the following chapters, therefore, the assertions 1 and 2 are proved.