Outline of mathematics of asymmetric(public/private) cryptography or RSA algorithm

Public/private cryptography is complex in detail but simple in outline. This article is an outline that will prep you to deep dive further if you want to.

How it works at a high level:

Asymmetric cryptography

Alice wants to receive a secret message from Bob. Alice has two keys, a public, and a private key. The public key as the name suggests is shared on Alice's website. Alice's private key is not shared with anyone.

Bob encrypts the message with Alice's public key — sends it to Alice → Alice decrypts the message with its private key.

No one can decrypt once the message is encoded with the public key, only the private key can be used to decrypt.

What are the factors of a number?

Factor: It is a number that divides another number evenly i.e with no remainder e.g for 20, 5 is a factor as 5*4 = 20, and similarly 2 is also a factor of 20 as 2x10 = 20.

Here we are talking about all the factors of a number.

What are prime numbers?

Prime numbers are numbers that have only two factors including 1 and themselves e.g 2, 3, 5, 7, 11, 13, 17, etc.

The math of this solution

It is very easy to multiply two numbers but very difficult and time-consuming to find the factors of a number e.g for 1459160519 can you tell me what are the factors of this number given that I got this number by multiplying two numbers? Modern computers can tell you a little faster but it also has to try the most possible combinations. For any number, the computer has to check something that is the order of size of the square root of the number to be factored. The square root of 1459160519 is roughly 38000 so there are 38000 possibilities to try for a computer to find its factors.

Not let us understand the enormity of complexity here. The universe life is supposed to be 10¹⁸ seconds. Assuming a decent modern computer can check about a million(10⁶) factors per second that means in the lifetime of the universe, the computer can check approximately 10²⁴ factors. For a 100 digit number, the number of digits in the square root will be 50. The number of factors a computer has to try in this case is 10⁵⁰. That means a computer will need more than two lifetimes of a universe to find the factors of a number having 100 digits.

In the RSA algorithm, two big prime numbers p and q are chosen. A number N is calculated by p x q. This N becomes a public key that can be shared with the public (you see it is almost impossible to find p and q for fairly large N say 1000 digits by any modern computer). Logic is to encode using p and q and decode using N or vice versa. If someone wants to send you some information securely then they can encode the information using public number N, the owner who has p & q can easily decode the information. No one in the world can decode until they have p & q.

On a little low level this is how it goes if you are interested:

1. Person A selects two prime numbers p & q.
2. Person A gets the public key N by multiplying p & q i.e p x q
3. Person A also chooses e which should be relatively prime to (p-1)x(q-1). This also is shared along with N.
4. Assuming they have both decided to assume the messages are represented in numbers, Person B has enough details to encode a message. If message to be sent is M = 35, then encode message C = M^e(mode N).
5. To decode the message Person A has to find a number d such that e x d = 1(mod(p-1)(q-1)).
6. Decoded message D = C^d(mode N).

Uses of RSA Algorithm

1. Diffie Hellman key exchange — used for sharing secret keys.
2. Digital signatures — Provides a way to digitally sign your documents.
3. Web security — SSL.
4. Email security — PGP

References:

1. https://en.wikipedia.org/wiki/RSA_(cryptosystem)
2. https://math.berkeley.edu/~kpmann/encryption.pdf
3. https://www.geeksforgeeks.org/rsa-algorithm-cryptography/