Understanding RSA - The math behind modern encryption

As developers we often come across different encryption algorithms like MD5, AES, DES and so on, however RSA stands out because it is simple yet significant or should I say 'fascinating', so enough chit chats let us dive into how RSA actually works. How Does RSA work ? RSA is an asymmetric encryption algorithm that uses mainly 2 types of keys (public and private) to encrypt the data, the working of the RSA is quite simple, here is an example, so let us assume that Steve needs to send a message to Cathy, so that message is encrypted using Steve's public key and that can only to decrypted by Cathy's private key and vice versa, this is just a vague representation of how it works, but you may think what's so fascinating about this, now let us dive deeper Math does the magic Ok "RSA this! RSA that! what if the keys are compromised?" might be great question, so to answer that let us get our hands on the "Math Problem" which is used to create a public and private key pair, we need constants such as p, q, n, e and d step 1: Select 2 prime numbers (p and q) let p = 61 and q = 53 step 2: Find the modulus (n) n = p * q = 3233 step 3: find the Euler's totient Φ(n) Euler's totient can be found by: Φ(n) = (p - 1) * (q - 1) Φ(n) = (61 - 1) * (53 - 1) = 3120 step 4: Choose the public exponent e e can be any number that satisfies the following 1 < e < Φ(n) e and Φ(n) are co-primes or simply GCD(Φ(n), e) should be 1 so let us assume e = 17 step 5: finding d the private exponent, the secret number d can be arrived by applying euclidean equation such that d * e mod Φ(n) = 1 so applying this will give d * 17 * mod 3120 = 1 the above equation solves to 2753 (note: d is just the multiplicative inverse of e, to make it even simpler d is a number that 'unodoes' the effect of e) step 6: Encryption and decryption now since we have all the required constants, we can see the encryption and decryption. let us assume that we have to encrypt a message (m) '65' Encrypted cipher (c) = m^e mod n so c = 65^17 mod 3233 c = 2790 now let us decrypt the cipher with d message (m) = c^d mod 3233 m = 2790 ^ 2753 mod 3233 which will give us 65 that is our actual message (m) aight !! I know too much math,so to summarize e is public exponent d is private exponent n is modulus so our public key is (e,n) that is (17, 3233) private ley is (d, n) that is (2753, 3233) So how's this math problem difficult to crack ? So here RSA relies on a principle called prime factorization, so to simply say, it is easy to find the product (n) of 2 prime numbers (p and q) but it is very difficult to find out the 2 factors that make up the number (n) so for example: it is easy to calculate the product of 61 and 53 but it is difficult to say the factors of 3233 especially when the size of number n is bigger (note: here we have taken 4 digit number but in real scenario the number would be of 4096 bits) So this mathematical property makes RSA very difficult to crack, and the important thing to note is cracking RSA is not impossible but the computing that is needed to crack is extremely high, even for today's standards and some studies say that the computing time that is needed to crack this problem would take even decades. So, this is how a math problem could solve the need of extremely a strong encryption mechanism and today RSA is one of the widely used encryption algorithms out there.

Apr 19, 2025 - 06:05

Understanding RSA - The math behind modern encryption

As developers we often come across different encryption algorithms like MD5, AES, DES and so on, however RSA stands out because it is simple yet significant or should I say 'fascinating', so enough chit chats let us dive into how RSA actually works.

How Does RSA work ?

RSA is an asymmetric encryption algorithm that uses mainly 2 types of keys (public and private) to encrypt the data, the working of the RSA is quite simple, here is an example,

so let us assume that Steve needs to send a message to Cathy, so that message is encrypted using Steve's public key and that can only to decrypted by Cathy's private key and vice versa, this is just a vague representation of how it works, but you may think what's so fascinating about this, now let us dive deeper

Math does the magic

Ok "RSA this! RSA that! what if the keys are compromised?" might be great question, so to answer that let us get our hands on the "Math Problem" which is used to create a public and private key pair,

we need constants such as p, q, n, e and d

step 1: Select 2 prime numbers (p and q)

let p = 61 and q = 53

step 2: Find the modulus (n)

n = p * q = 3233

step 3: find the Euler's totient Φ(n)

Euler's totient can be found by: Φ(n) = (p - 1) * (q - 1)

Φ(n) = (61 - 1) * (53 - 1) = 3120

step 4: Choose the public exponent e

e can be any number that satisfies the following

1 < e < Φ(n)
e and Φ(n) are co-primes or simply GCD(Φ(n), e) should be 1

so let us assume e = 17

step 5: finding d the private exponent, the secret number

d can be arrived by applying euclidean equation such that d * e mod Φ(n) = 1
so applying this will give d * 17 * mod 3120 = 1

the above equation solves to 2753

(note: d is just the multiplicative inverse of e, to make it even simpler d is a number that 'unodoes' the effect of e)

step 6: Encryption and decryption

now since we have all the required constants, we can see the encryption and decryption.
let us assume that we have to encrypt a message (m) '65'

Encrypted cipher (c) = m^e mod n
so c = 65^17 mod 3233
c = 2790

now let us decrypt the cipher with d message (m) = c^d mod 3233 m = 2790 ^ 2753 mod 3233

which will give us 65 that is our actual message (m)
aight !! I know too much math,so to summarize

e is public exponent
d is private exponent
n is modulus

so our

public key is (e,n) that is (17, 3233)
private ley is (d, n) that is (2753, 3233)

So how's this math problem difficult to crack ?

So here RSA relies on a principle called prime factorization, so to simply say, it is easy to find the product (n) of 2 prime numbers (p and q) but it is very difficult to find out the 2 factors that make up the number (n) so for example:

it is easy to calculate the product of 61 and 53
but it is difficult to say the factors of 3233 especially when the size of number n is bigger

(note: here we have taken 4 digit number but in real scenario the number would be of 4096 bits)

So this mathematical property makes RSA very difficult to crack, and the important thing to note is cracking RSA is not impossible but the computing that is needed to crack is extremely high, even for today's standards and some studies say that the computing time that is needed to crack this problem would take even decades.

So, this is how a math problem could solve the need of extremely a strong encryption mechanism and today RSA is one of the widely used encryption algorithms out there.