How Does RSA Encryption Work

A popular public-key cryptosystem for secure data transfer is RSA (Rivest-Shamir-Adleman). In addition, it is among the oldest. The surnames of Ron Rivest, Adi Shamir, and Leonard Adleman, who first publicly published the algorithm in 1977, are the origin of the abbreviation “RSA.” The English mathematician Clifford Cocks created a comparable method in secret at GCHQ (the British signals intelligence organization) in 1973. In 1997, that system was made public. 

Before We dive in to how RSA wordk, lets’ understand few math theroms and functions which re used in RSA.

Modulo:

Modulo is a function where it returns the reminder after a number A divided by another number B. (A mod B)

EG: A=16, B=5

the modulo value of  A mod B =>

16 mod 5 = 1 

Prime Numbers

A prime number is a natural number where it has only two factors, 1 and the number itself. 

Eg: 1, 2, 3,5

Coprime Number

Two numbers cna be coprime if their greatest common divisor is 1. Or we can say, two numbers are corpime if they have only number 1 as the common divisor.

Carmichael function

λ(n) of a positive integer n is the smallest positive integer m such that

holds for every integer a coprime to n. In algebraic terms, λ(n) is the exponent of the multiplicative group of integers modulo n

lets calculate the λ of number 7

lets list down the available values for a 

a => {1,2,3,4,5,7}

lets assum m = 1 and test the function for each a above.

1^1  =1 

2 ^1 =2 

3^1=3

5^1=5

7^1=7

based on the above scenario, we can notice that number 1 cannot be m as it failes to full fill the therom at the second item.

now lets take 6 as m and try the fucntion

1^6 =1 

2 ^6 =64 and the  mode 7 is 1

3^6=729 and the  mode 7 is 1

5^6=15625 and the  mode 7 is 1

7^1=117,649 and the  mode 7 is 1

therefore the λ(7) is 6

Note: If a number is aprimer number then the λ(n) will be always equal to n-1

you can try with few examples using the above manual method.

RSA key generation

select two prime numbers p and q  (in real life scenarios the p and q must be random, similar in magnitude but differ in lenght to make factoring harder)

p=7, q=19

compute n by multiplying p by q : n=pq

n=133

n is used as the modulus for both the public and private keys. Its length, usually expressed in bits, is the key length.
n is released as part of the public key.

compute λ(n)

since n=pq, we can write λ(n) as 

λ(n)=λ(p) . λ(q)

λ(n)=(p-1) . (q-1)

λ(n)=(7-1) (19-1)

λ(n)=108

identify public key e such that:

e must be a prime number

e must be less than λ(n)

e must not be a factor of λ(n)

Note:

• e having a short bit-length and small Hamming weight results in more efficient encryption – the most commonly chosen value for e is 2¹⁶ + 1 = 65537. The smallest (and fastest) possible value for e is 3, but such a small value for e has been shown to be less secure in some settings.
• e is released as part of the public key.

in our example lets select 29 as e

e=29

identify private key d such that product of e and d divide by λ(n) must result with a reminder 1.

(e . d) mode λ(n) =1

Note:

• This means: solve for d the equation de ≡ 1 (mod λ(n)); d can be computed efficiently by using the extended Euclidean algorithm, since, thanks to e and λ(n) being coprime, said equation is a form of Bézout’s identity, where d is one of the coefficients.
• d is kept secret as the private key exponent.

in our example lets select 41 as d, which fullfulls the above condition.

d=41

Now lets try to encrypt a message using RSA and decript using our above values.

message to be encrypted: 10

Encryption

(message ^ d) mod n =cipher text

(10 ^ 41) mod 133 = 117

Decryption

(Cipher ^ e) mod 133 = message

(117 ^ 29) mod 133 = 10