RSA FOR BEGINNER

Hi there! we shall discuss about basics of RSA (Rivest Shamir Adelman) cryptosystem.

PRE-REQUISTES

1. Understanding of Prime and Composite Numbers
2. Euler’s Theorem (Number Theory)
3. Modular Arithmetic
4. Asymmetric-key algorithm

Introduction

RSA Cryptosystem is asymmetric-key algorithm, which means we will be using a set of keys known as public and private keys. Let’s dive into the working!

Principle

Let’s assume you want to encrypt a message M. Now you will generate a pair of public and private keys: (n and e) and (n and d) respectively.

N - Modulus, E - Public Exponent, D - Private Exponent

N is a product of primes, usually cryptanalysis of RSA depends on N of the RSA. The more difficult it is to factorize the N, the lesser is the possibility of being attacked.
NOTE: There are lot’s of cryptanalytic attacks which can be performed apart from factorizing N.

For sake of simplicity let’s take P and Q as some prime whose product is N.

N = P * Q

Encryption Formula

C ≡ M^e mod N

Decryption Formula

D ≡ C^d mod N

Encryption Process

1. Generate modulus — N using prime numbers.
2. Now generate larger random Public Exponent — e.
3. Then use the Encryption formula to encrypt the message

Encryption using python

Decryption Process

1. To decrypt the ciphertext, we need to calculate Euler’s totient phi Φ.
2. In our case Φ = (p -1) * (q-1)
3. let’s calculate the private exponent — d. By finding the modular inverse of public exponent and Euler’s totient.
4. Now we have the values needed for decryption of cipher text C.

Decryption using python

Final Note

Hope you guys understood the mechanism of RSA Cryptosystem. RSA is strong cryptosystem but when implemented wrong it’s as weak as other cryptosystem too.

Fact: Quantum Computing is a upcoming threat for RSA cryptosystem, which can factorize any number very quickly compared to the current generation computers.

Hope you all liked it : P