RSA stands for Rivest Shamir Adleman, and it was invented by:
- Ron Rivest
- Adi Shamir
- Leonard Adleman
RSA comes from the first letters of their last names.
There are 2 types of encryption algorithms:
- Symmetric
- Asymmetric
Symmetric encryption algorithms use one key to encrypt and decrypt.
Asymmetric encryption algorithms use two keys — a public key and a private key.
RSA works by creating a pair of “commutative keys” — meaning if you encrypt with one, you can decrypt with the other.
In RSA, if you use the public key to encrypt, you must use the private key to decrypt (and vice versa).
RSA Math
Let's look at the mathematics behind RSA.
Here are the basic math concepts you need to know first:
0. Basic Math Operations
You should know how addition (+), subtraction (-), multiplication (×), and division (÷) work.
1. Factor
A factor — numbers you multiply to get the original number.
If N is the original number, and multiplying a and b gives you N, then a and b are factors of N.
Example:
N = 12
1 * 12 = 12
2 * 6 = 12
3 * 4 = 12
Factors of 12: 1, 2, 3, 4, 6, 12
Now for:
N = 7
1 * 7 = 7
Factors of 7: 1, 7
2. Prime
A prime number is a number that has only two factors: 1 and itself.
So from the example above, 7 is prime because its only factors are 1 and 7.
Other prime numbers: 2, 3, 5, 11, 13, 29, 37, 61, ...
3. Semi-Prime
A semi-prime number is a number whose factors are both prime numbers.
Example:
21 = 3 * 7
Here 3 and 7 are both prime numbers.
So 21 is a semi-prime.
Note:
We exclude 1 and the number itself since they are common factors in every number.
4. Modulo
Modulo just means the remainder after division.
The symbol for modulo is % (or sometimes MOD).
Example:
7 % 3 = 1 → because 3*2=6 and 7-6=1
So 1 is the remainder (modulo).
You can think of it as: what’s left over after dividing.
So that’s the 5 basic math concepts you need.
But as we go along, I’ll introduce another one that combines them.
RSA Algorithm
There are 2 main steps in RSA:
Generating keys
Using them for encryption and decryption
1. Generating Keys
Step a: Select 2 prime numbers (p, q)
Let p = 7 and q = 19.
Step b: Calculate their product
Let this be N.
N = p * q
N = 7 * 19 = 133
Step c: Calculate the Totient (T), also called Euler’s Totient Function.
Euler’s Totient function tells us how many numbers less than N share no common factors with N.
For RSA, since p and q are prime, φ(N) = (p − 1)(q − 1).
This counts how many numbers less than N are coprime (relatively prime) with N — meaning their GCD is 1.
Example:
Let N be 13.
How many numbers less than 13 will produce a GCD of 1 with 13.
Answer is 12
For RSA, you can simply compute:
T = (p - 1) * (q - 1)
T = (7 - 1) * (19 - 1)
T = 6 * 18 = 108
Step d: Choose a Public Key (E)
This value must satisfy:
E must be coprime with T (i.e., gcd(E, T) = 1)
E must be less than T
LetE = 29.
- 29 is less than 108
- gcd(29, 108) = 1 So:
E = 29
Step e: Find the Private Key (D)
D must satisfy the condition:
(D * E) mod T = 1
This means D is the modular multiplicative inverse of E modulo T.
Let D be 41
(41 * 29) mod 108 = 1
(41 * 29) = 1189
1189 % 108 = 11 remainder 1
108 * 11 = 1188
1189 - 1188 = 1
So:
D = 41
2. Encryption and Decryption
Now that we have:
N = 133
E = 29
D = 41
We can encrypt and decrypt messages (which are represented as numbers).
Encryption (using Public Key)
Cipher = Message ^ E mod N
Example:
Message = 60
Cipher = 60^29 mod 133 = 72
Decryption (using Private Key)
Message = Cipher ^ D mod N
Example:
Message = 72^41 mod 133 = 60 (the original)
So we got back our message — RSA works!
Note
RSA only works with numbers.
So if you have a message like "Hello, World!", it’s first converted to numbers using ASCII or UTF-8 before applying RSA.
After decryption, the number is converted back to text.
How Secure Is RSA?
RSA’s security relies on the difficulty of factoring semi-prime numbers.
RSA security depends on how hard it is to factor n = p × q, the larger n (in bits), the harder the math problem.
If you’re given 133, could you easily find 7 and 19? Sure.
But what about a 2048-bit number — something with hundreds of digits?
That’s practically impossible with current computers.
A 2048-bit RSA key means the digit can be as large as (2^2048)-1
Which is roughly a 617-digit decimal number
Here is a table of different key lengths and time it would take to crack them
| RSA Key Size | Approximate Decimal Digits | Factoring Difficulty | Approximate Time to Break (with modern computers) |
|---|---|---|---|
| 256-bit | ~77 digits | Very easy | Few seconds |
| 512-bit | ~155 digits | Still easy | Minutes to hours |
| 768-bit | ~232 digits | Hard, but done in labs | Months (if you use supercomputers) |
| 1024-bit | ~309 digits | Very hard | Thousands of years |
| 2048-bit | ~617 digits | Practically impossible | Longer than universe’s age |
| 4096-bit | ~1234 digits | Even harder | Astronomically impossible |
As you can see it gets harder every time the number gets larger. If you read my blog on how software works-encryption I talked about the goal of modern encryption was to make encryption computationally expensive - so expensive that its useless to even try.
Summary
Public Key = (E, N)
Private Key = (D, N)
Encrypt: Cipher = Message ^ E mod N
Decrypt: Message = Cipher ^ D mod N
Top comments (0)