RSA Encryption : Beginners guide

.

What the heck is Encryption anyway?

Before we even jump into RSA, let’s take one small step back and talk about encryption itself. Think of encryption as a secret language for computers. It’s the process of scrambling information into gibberish so that only the right person (with the right key) can unscramble it back into the original message. So, back in the 1970s, three really smart guys ieRon Rivest, Adi Shamir, and Leonard Adleman(RSA) came up with an idea that completely changed digital security. They built an algorithm that didn’t rely on one secret key (like old-school symmetric encryption) but instead used a pair of keys(2).

How does asymmetric encryptions work ?

The diagram illustrates how asymmetric encryption works using two different keys: a public key and a private key. In this method, the sender first takes the recipient’s public key and uses it to encrypt the message. Once encrypted, the message becomes unreadable to anyone except the intended recipient. On the other end, the recipient uses their private key which is kept secret and never shared — to decrypt the message and restore it to its original form.

This process ensures confidentiality because even if an attacker intercepts the message, they cannot decrypt it without the private key. The beauty of asymmetric encryption is that while the public key can be openly shared, the private key remains secure, providing a strong foundation for secure communication. This method is widely used in technologies like SSL/TLS certificates, email encryption, and digital signatures, making it a cornerstone of modern cybersecurity.

RSA Algorithm

RSA (Rivest–Shamir–Adleman) is one of the most widely used public-key cryptosystems. It’s based on asymmetric encryption, where two keys are used: a public key (shared with everyone) and a private key (kept secret). The security of RSA relies on the mathematical difficulty of factoring very large prime numbers. RSA uses large primesets and uses functions such and mod and mod inverse and totient for the encryption process .

Understanding math terms

1.Prime Numbers → A prime number is a number greater than 1 that has no divisors other than 1 and itself.

• Example: 2, 3, 5, 7, 11, …

2.Modulo (mod) → The modulo operation finds the remainder after dividing one number by another.

• Example: 17 mod 5 = 2 (since 17 ÷ 5 = 3 remainder 2)

3.Euler’s Totient Function (ϕ) → If n is a product of two primes p and q, then: ϕ(n)=(p−1)(q−1) Example: ϕ(91) = (7−1)(13−1) = 6×12 = 72.

4. Coprime Numbers → Two numbers are coprime if their greatest common divisor (GCD) = 1.

• Example: 8 and 15 are coprime (GCD = 1). RSA needs the encryption exponent e to be coprime with ϕ(n).

5.Modular Inverse →Given numbers a and m, the modular inverse of a is a number b such that: (a×b)mod m=1

• Example: The modular inverse of 3 mod 11 is 4, since (3×4) mod 11 = 12 mod 11 = 1.

So How Does RSA Actually Work?

Okay, let’s roll up our sleeves. RSA sounds scary at first (big numbers, math, primes blah blah), but the core idea is surprisingly elegant.

RSA has 3 main steps:

1. Key Generation (making the secret keys)
2. Encryption (locking up your message)
3. Decryption (unlocking it again)

1. Key Generation

Step 1: Picking Two Prime Numbers

RSA starts with something simple: two prime numbers.

Let’s pick small primes for illustration:

p = 61 
q = 53

These primes are kept secret. The security of RSA depends on the fact that while multiplying two primes is easy, factoring their product back into primes is extremely hard when the numbers are large (hundreds of digits long).

Step 2: Multiplying the Primes

We compute:

n = p×q
n = 61×53 = 3233

/*NOTE : Keep 3233 in mind */

This number n becomes part of the public key and is used in both encryption and decryption. Think of it as the “playground” where all the math happens.

Step 3: Calculating Euler’s Totient Function

Next, we calculate Euler’s Totient function:

ϕ(n) = (p−1)(q−1)
ϕ(3233)=(61−1)(53−1)=60×52=3120 

/*NOTE = Keep 3120 in mind */

ϕ(n), plays a crucial role in ensuring that the encryption and decryption process works correctly.

Step 4: Choosing a Public Exponent e

Now we must pick a public exponnt e such that

1. Must be an integer greater than 1 and less than ϕ(n):

• Rule: 1 < e < φ(n)
• Ensures e lies within a valid range.

2. Must be coprime with ϕ(n):

• Meaning gcd ( e, φ(n) ) = 1.
• This ensures there exists a modular inverse and without this, decryption would not be possible.

3. Commonly chosen as a small prime (like 3, 5, 17, 257, 65537):

• Using a prime makes it easier to check coprimality.
• 65537 is widely used in practice because it balances efficiency and security.

4. Must not divide ϕ(n):

👉 Example with ϕ(n) = 288:

• Valid candidates for eee include 17, 37, 41, etc. (since they are less than 288, prime, and coprime with 288)

Step 5: Calculating the Private Exponent ( d )

Here’s the interesting part: we need to find a number d such that:

d × e = 1(modϕ(n))
d × 17 = 1(mod3120)  /*3120 found from step 3  */

d = 2753

This d becomes the private key.

Step 6: Final Key Pairs

Now we have:

• Public Key (n, e) → (3233,17)
• Private Key (n, d) → (3233,2753)

Anyone can encrypt a message using the public key, but only the private key holder can decrypt it.

2. Encryption

let’s think plaintext=65 now let’s encrypt it using our public key which is e=17, now let’s calculate the cypher using the formula. our ciphertext = 2790

Values:

• plaintext = 65 ( ascii value of A )
• e = 17
• n=3233
• Cipher text = 2790

3. Decryption

Now let’s decrypt our ciphertext = 2790 and d = 2753 and n= 3233, now let’s apply the formula, we got the decrypted plaintext.

Values:

• ciphertext = 2790
• d=2753
• n = 3233

Performing modular exponentiation (done by computer normally), the result comes back to: plaintext = 65

NOTE :

We took simple numbers and factors just to understand the simple math logic behind encryption and decryption but in the practical approach it becomes very complex as very large prime sets are chosen

Practical RSA Example

In practical approach the key pairs are usually 2048 or 4096 chars long this makes it very hard to attacks Example : Rsa public key

-----BEGIN PUBLIC KEY-----
MIIBIjANBgkqhkiG9w0BAQEFAAOCAQ8AMIIBCgKCAQEAnyB/VaMb9jn9B3aTP5i4
jg3Q/hCi88l2POKdQl92OkJnnzGDrw+bYhfL9u7+N0PkyAzbVgOfvaRm9hTaIEt2
lywmypPTL9p36ys+0nuEKMiw124GThMzLu+kVUgFfveDQvEXcTqH2XSw0lIdtNxg
RZwVk4Z/tdYtZNX1YXsGdZAFLao0cpYeRdrv6SkdJU17a/bn6+kkvpgEl8cNr+rz
JAna/LxnVJQ4l1THfgtt/GltiJWthA7A0qVkx+/DlGPUs3/sfvfwZbT25aO1cWsp
p/aDZ+kbgWSrteFTJ2tkOVszLhBv9A/CfhwPoWbpm/isXBbkWB65S9uk9XM+OT8+
iwIDAQAB
-----END PUBLIC KEY-----

Example : Rsa private key

-----BEGIN RSA PRIVATE KEY-----
MIIEowIBAAKCAQEAnyB/VaMb9jn9B3aTP5i4jg3Q/hCi88l2POKdQl92OkJnnzGD
rw+bYhfL9u7+N0PkyAzbVgOfvaRm9hTaIEt2lywmypPTL9p36ys+0nuEKMiw124G
ThMzLu+kVUgFfveDQvEXcTqH2XSw0lIdtNxgRZwVk4Z/tdYtZNX1YXsGdZAFLao0
cpYeRdrv6SkdJU17a/bn6+kkvpgEl8cNr+rzJAna/LxnVJQ4l1THfgtt/GltiJWt
hA7A0qVkx+/DlGPUs3/sfvfwZbT25aO1cWspp/aDZ+kbgWSrteFTJ2tkOVszLhBv
9A/CfhwPoWbpm/isXBbkWB65S9uk9XM+OT8+iwIDAQABAoIBABPT0sny5vsJQrP5
XGOiPezFX/MoU4WY5riza/DnQC4GNC8r1kKr6SqR2IJOSTLNrOYYZAQVs4PHxmSH
OJ6piH9Rqwu226usxyBwZQWJCnCigRZ2ySZVUh1ZEtrlfHnTkXF35Png1yiLV7T9
MmJky0IhLrcRHTylEUbtOgQJdkaTlxv0Cq4iOHEz0RTfWJCh5MYAvlHgJUsa4+4W
jc3Q+0djU/A36PWpLTUe/HGPkORU7nQga8QbLKQ9D4GqqGv6iWypljPahOGrZZ7y
3OfYJIrM/TR3XIujqbcUL1xePoGc0yiRfCr6yO9WKf9tNukCvqbkYmixVFb/qQuK
RA/39BECgYEA0apdvch0m0hQFwdJvlAOXl8gTAGnYYM1VjBgSR7famuZwUCLuneo
Et6EQrcTZtc6APaYWlAcVx+7NYsYC7PdFAMfZXLw3/JeEvlog75R8pRwHWfZUGe1
nxSch+saMjfKG0fSvi9R+NDdm0775rhBUSBRyoQKl6/votI6/EY+TtUCgYEAwkr1
euwv+iL3LqIIFGjzdFSUw9W9Xk9hdSEJudVcwfP7oH1Oy+mVWD98Y+fisjD6azht
j0CFGueXXf0CifYgon4/tXY3kfsS8mU5oZhbGYP1gDm6HWSKM9s0qp1jOajubZCz
Czm1M2Iop++hDBllu5z7y9wcwFpGq3MuvWVtx98CgYEAio6Z8Id+d/gr5WwNkdV6
CWe4AkK9iLWbE+BYYTojz0JYk9vB+3KEAiRHJ4exLK9jR6uvN0/lyrXPlCzdsS4m
FcmSgAqboIOdI9Dq/tVRdoweI3Czrm07G2wVncUCxNkVmT23ybOf6lytdquV0P1H
PQOsybbFAUVliiaAkKMjHhkCgYB17g+wS9oXJtAIAxuKX+Wdr5UYhQzLSL1r3eDM
ZkBGDXSnBkgkpyQaC3bSITbNV8M3/2kosU3Zdca/qsm2uak3WBANcbLrLY1jiaOA
fTyWcS07Zk6cdqEYNq5x/NP0dKA76r9ySdW9WZA51s5WzLeeN/vx0im1a1ZHzMMK
/Jy02wKBgCK2QewUv3lNbbyd6gnGvEIc/6nCtgv+J3touL7YZX2QDW06Fmm0Uuq8
2j3VoKUH4J37Px3ZVMz/+fK+CdhbLFhbE43w13AD/2dolczkuf4xPsCHDKPpqf8Q
nMLFNa6PTvafpjpP7nAsiLiYWYXTcSbEDFqc2J4/L6szusT0d74h
-----END RSA PRIVATE KEY-----

Conclusion

RSA is one of the most powerful and widely used algorithms in modern cryptography. At its core, it looks like “magic” — turning a simple number into something unreadable and then restoring it perfectly — but it’s really just clever mathematics built on prime numbers and modular arithmetic.

Small examples (like n=3233) help us understand the concept, but in practice RSA relies on extremely large keys (2048 bits or more) that make it virtually impossible to break with current technology. This balance of simplicity in concept and strength in execution is why RSA has remained a cornerstone of secure communication — from protecting your online banking to securing messages in everyday internet traffic.

Thanks for reading this far guys ! Peace out ! Vishwas S Adhikari