21CS2212
COMPUTER NETWORKS AND SECURITY
© 2020-21 KL University – The contents of this presentation are an intellectual and copyrighted property of KL
University. ALL RIGHTS RESERVED
1
RSA
© 2020-21 KL University – The contents of this presentation are an intellectual and copyrighted property of KL
University. ALL RIGHTS RESERVED 2
RSA
• RSA algorithm is a public key encryption technique and is considered
as the most secure way of encryption.
• It was invented by Rivest, Shamir and Adleman in year 1978 and
hence name RSA algorithm.
- The RSA algorithm holds the following features −
- RSA algorithm is a popular exponentiation in a finite field over
integers including prime numbers.
- The integers used by this method are sufficiently large and
difficult to crack it.
- There are two sets of keys in this algorithm: private key and
public key.
3
RSA
You will have to go through the following stepsto work on RSA algorithm −
Step 1: Generate the RSA modulus
The initial procedure begins with selection of two prime numbers
namely p and q, and then calculating their product n, asshown −
n=p*q Here, let n be the specified large number.
Step 2: Calculate ᵩ(n) using Euler’sTotient function
Step 3: Derived Number (e)
Consider number e asa derived number which should be greater than
1 and lessthan (p-1) and (q-1). The primary condition will be that there
should be no common factor of (p-1) and (q-1) except 1
4
RSA
Step 4: compute d
Private Key d is calculated from the numbers p, q and e. The
mathematical relationship between the numbers is as follows−
d * e = 1 mod ᵩ(n)
The above formula isthe basic formula for Extended Euclidean Algorithm,
which takesp and q asthe input parameters.
step 5: Encryption Formula
Consider a sender who sendsthe plain text message M to someone
whose public key is(n,e). To encrypt the plain text message in the given
scenario, use the following syntax −
C= Me mod n
5
RSA
Step 6: Decryption Formula
The decryption process is very straightforward and includes
analytics for calculation in a systematic approach. Considering
receiver C has the private key d, the result modulus will be calculated
as −
M = Cd mod n
6
Euler’s Totient function
It is defined as the number of positive integers less than n and
relatively prime to n.
Ex: ᵩ(37)
Since 37 is prime and all of the positive integers from 1 to 36 are
respectively prime to 37.
So ᵩ(37) = 36 , so ᵩ(n) = n-1
Ex: ᵩ(35)
since 35 is not prime list all the positive integers less than 35 that
are relatively prime to it as
1,2,3,4,6,8,9,11,12,13,16,17,18,19,22,23,24,26,27,29,31,32,33,34
which are 24 numbers.
So ᵩ(35) = 24
7
RSA Example
Assume two prime numbers p=17 and q=11 in RSA algorithm. Convert
the plain text M=88 to cipher text by explaining the step by step
process of Encryption and also Decryption.
Sol: Given two prime numbers p=17 and q=11
step 1: calculating n
n=p*q = 17 * 11 = 187
step 2: calculating ᵩ(n) using Euler’s Totient function
since p≠q, ᵩ(n) = ᵩ(p*q) = ᵩ(p)*ᵩ(q) = (p-1)(q-1)
ᵩ(n) = (17-1)(11-1) = 16*10 = 160
8
RSA Example
step 3: Deriving e
Assuming e as 7 which is greater than 1 and less than (p-1) and (q-1)
and there should be no common factor of (p-1) and (q-1) except 1
step 4: computing d by using
d * e = 1 mod ᵩ(n)
d * 7 = 1 mod160
(d * 7) mod 160 = 1
Assuming d as 23 , since (23 * 7) mod 160 = 1
161 mod 160 = 1
so, we know values as p=17, q=11, n=187, ᵩ(n)=160,
e=7, d=23
9
RSA Example
step 5: Encryption Formula, C = Me mod n
Given M = 88 which satisfies the condition M<n (88<187)
C = Me mod n = 887 mod 187 = 11
step 6: Decryption Formula,
M = Cd mod n = 1123 mod 187 = 88
10