**Modern cryptography** is based on **prime numbers** to implement their algorithms. This idea assumes that **factoring** large numbers is a **costly** task for any modern computer, because of become inefficient for big numbers. Some of the most important cryptographic protocols and applications like **SSL , 3D-secure, OpenPGP, SSH, SSL** or the modern **TLS** are based on this style algorithms.

This means that there are algorithms like **RSA** public key (Standard IEE) used to encrypt and digitally sign. This algorithm uses **two** 155-digit **prime numbers** to forward (512 bits), obtaining a product of approximately 310 digits (**1024 bits**) that it is practically impossible to decode by current computers.

**RSA DESCRIPTION**

The algorithm uses two keys, one **private** and one **public**. Only send the public key to **encrypt** and the private is used to **decrypt**.

The **public key** is **(n, e)** (which are the modulus and encryption exponent).

The **private key** is **(n, d)** (which are the module and the decryption exponent).

**n = p · q** (primes p and q of 155 randomly generated digits)

**e** = a smaller number than n coprime with f(n)

**d** = a number where d = ed – 1 is divisible by f(n) (calculated with the extended Euclid algorithm)

and** f(n) = (p-1) · (q-1)** where f(n) is the Euler totient’s function and measure the number of coprime with n up to n.

**EXAMPLE**

**Willy** wants to send a message “OK” to **Pam** (depending on the application can be a banking operation, a digital signature, or a simple whatsapp message)

**1. Pam pc calculates the private key and the public key and sends the public key to Willy.**

**p** = 439, **q** = 449 (In this example we used small primes to understand it)

**n** = 439 · 449 = 197111

f(197111) = 196244 = 73 · 7 · 2 · 2 · 2 · 2 · 2 · 2 · 2

**e** = 19 · 11 · 5 = 1045 (a number that does not share factors with 196244)

**d**:

(d · 1045) – 1 = multiple of 196244

d · 1045-1 = k · 196244

d = (k · 196244 + 1) / 1045 (so that d is integer division has to be exact)

k=1, d=187.7 .. **NO**

k=2, d=365.5 .. **NO**

.

.

k=31, **d=5821** **OK**

Pam has the **private key (197111,5821)** and **public key (197111,1045)** and sends the public key to Willy.

**2.The Willy pc receives the public key (n, e) Pam and transforms the message into a number m is less than n.**

Willy gets the public key **(197111,1045)**

OK now transforms the message into a number m:

O: 2

K: 1

(In this example it is a completely arbitrary assignment as this is done with a conversion table.)

**m** = “OK” = 21

**3. pc text willy figure that transforms from mac to the operation c = m ^{e} mod n**

**c** = 21^{1045} mod = 63202 197111

**4.Willy c sends the message to Pam**

Willy sends 63202

**5. Pam receives and decodes c m = c ^{d} mod n**

Pam decrypts the message with the private key

**m** = 63202^{5821} mod 197111 = **21** = “OK”

**WHERE IS THE SAFETY?**

If a **hacker** retrieve the messages sent, could be recover in this case:

- The public key (197111,1045)

- The message “63202”

he would have:

**n = 197111**

**e = 1045**

**c = 63202**

but to decrypt the message m requires d because:

m = 63202^{d} mod 197111

and the only way to get d:

(d · e) – 1 = multiple of f(197111)

(d · 1045) – 1 = k · f(197111)

d = (k · f(197111) + 1) / 1045

The problem is that for f(197111) requires **p **and** q **and doesn’t have it.

The only way is to **factoring** n but 1024 bits are impossible to factorize for the hacker because it would take years to solve.

This is known as the **RSA problem** solving and trouble with big numbers is what guarantees the **security** of the system.

Other encryption algorithms based on primes are:

**DSA**

**ECDSA**

**Diffie-Hellman**

**ElGamal**