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 = 211045 mod = 63202 197111

4.Willy  c sends the message to Pam

Willy sends 63202

5. Pam receives and decodes c m = cd mod n

Pam decrypts the message with the private key

m = 632025821 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 = 63202d 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