Department of Computer Science and Engineering (CSE)

(RSA Algorithm & Diffie Hellman

Algorithm)

University Institute of Engineering (UIE) 2

 Department of Computer Science and Engineering (CSE)

RSA Algorithm

• Developed in 1977 by Ron Rivest, Adi Shamir, and Len

Adleman at MIT and first published in 1978.

• Most widely accepted and implemented general-

purpose approach to public-key encryption.

• The RSA scheme is a block cipher in which the plaintext

and ciphertext are integers between 0 and n - 1 for
some n.

University Institute of Engineering (UIE)

 Department of Computer Science and Engineering (CSE)

RSA Algorithm

• RSA makes use of an expression with exponentials.

• Both sender and receiver must know the value of n.

• For some plaintext block M and ciphertext block C:

University Institute of Engineering (UIE)

 Department of Computer Science and Engineering (CSE)

RSA Algorithm

• Sender knows the value of e.

• Only receiver knows the value of d.

• Thus, this is a public-key encryption algorithm with a

public key of PU = {e, n} and a private key of PR = {d, n}

University Institute of Engineering (UIE)

 Department of Computer Science and Engineering (CSE)

RSA Algorithm

University Institute of Engineering (UIE)

 Department of Computer Science and Engineering (CSE)

RSA Algorithm

Example
1. Select two prime numbers p = 17 and q = 11

2. Calculate n = p x q = 17 × 11 = 187

3. Calculate Φ(n) = (p - 1) (q - 1) = 16 × 10 = 160

4. Select e such that e is relatively prime to Φ(n) = 160 and

less than Φ(n); we choose e = 7

University Institute of Engineering (UIE)

 Department of Computer Science and Engineering (CSE)

RSA Algorithm

5. Determine d such that de ≡ 1 (mod 160) and d < 160.

The correct value is d = 23
because 23 × 7 = 161 = (1 × 160) + 1;
d can be calculated using the extended Euclid’s
algorithm.

The resulting keys are:

Public key PU = {7, 187}
Private key PR = {23, 187}.

University Institute of Engineering (UIE)

 Department of Computer Science and Engineering (CSE)

RSA Algorithm

M = 88
C = 887 mod 187
= (884 mod 187) x (882 mod 187) x (881 mod 187)
= 11

University Institute of Engineering (UIE)

 Department of Computer Science and Engineering (CSE)

Requirements of RSA Algorithm

• It is possible to find values of e, d, n such that

Med mod n = M for all M < n.

• It is relatively easy to calculate Me mod n and Cd mod n

for all values of M < n.

• It is infeasible to determine d given e and n.

University Institute of Engineering (UIE)

 Department of Computer Science and Engineering (CSE)

Security of RSA Algorithm

• Four possible approaches to attacking the RSA algorithm

are

1. Brute force attack

• Involves trying all possible private keys.
• Defense against the brute-force approach is to use a large
key space. Thus, the larger the number of bits in d.
• key generation and encryption/decryption, are complex.
• The larger the size of the key, the slower the system will
run.

University Institute of Engineering (UIE)

 Department of Computer Science and Engineering (CSE)

Security of RSA Algorithm

2. Mathematical attacks
Effort to factoring the product of two primes.

3. Timing attacks
These depend on the running time of the decryption
algorithm.

4. Chosen ciphertext attacks

This type of attack exploits properties of the RSA
algorithm.

University Institute of Engineering (UIE)

 Department of Computer Science and Engineering (CSE)

Diffie-Hellman Algorithm

Elliptic Curve Cryptography (ECC)

• is a planar algebraic curve defined by an equation of the

form

 Y2=X3+ax+b

Where ‘a’ is the co-efficient of x and ‘b’ is the

constant of the equation 

University Institute of Engineering (UIE)

 Department of Computer Science and Engineering (CSE)

Elliptic Curve Cryptography (ECC)

University Institute of Engineering (UIE)

 Department of Computer Science and Engineering (CSE)

Diffie-Hellman Algorithm

• The Diffie-Hellman algorithm is being used to establish a

shared secret communications while exchanging data over
a public network.

• the elliptic curve is used to generate points and get the

secret key using the parameters. 

• For practical implementation of the algorithm, we will

consider only 4 variables one prime P and G (a primitive
root of P) and two private values a and b.

University Institute of Engineering (UIE)

 Department of Computer Science and Engineering (CSE)

Diffie-Hellman Algorithm

• Step by Step Explanation 

Alice Bob

Public Keys available = P, G Public Keys available = P, G

Private Key Selected = a Private Key Selected = b

Key generated = 
Key generated =  y= Gb mod P
x= Ga mod P

University Institute of Engineering (UIE)

 Department of Computer Science and Engineering (CSE)

Diffie-Hellman Algorithm

• Exchange of generated keys takes place

• Key received = y Key received = x

• Generated Secret Key =   Generated Secret Key = 

ka = yamod P kb= xbmod P

Algebraically it can be shown that  ka=kb

University Institute of Engineering (UIE)

 Department of Computer Science and Engineering (CSE)

Diffie-Hellman Algorithm

Example 

• Step 1: Alice and Bob get public numbers P = 23, G = 9

 
• Step 2: Alice selected a private key a = 4 and
Bob selected a private key b = 3

• Step 3: Alice and Bob compute public values

Alice: x =(9^4 mod 23) = (6561 mod 23) = 6
Bob: y = (9^3 mod 23) = (729 mod 23) = 16

University Institute of Engineering (UIE)

 Department of Computer Science and Engineering (CSE)

Diffie-Hellman Algorithm

• Step 4: Alice and Bob exchange public numbers

• Step 5: Alice receives public key y =16 and

Bob receives public key x = 6
 
• Step 6: Alice and Bob compute symmetric keys
Alice: ka = y^a mod p = 65536 mod 23 = 9
Bob: kb = x^b mod p = 216 mod 23 = 9

• Step 7: 9 is the shared secret.

University Institute of Engineering (UIE)

 Department of Computer Science and Engineering (CSE)

References
• [Link]
chniques_8339/
• [Link]
• [Link]
n/
• [Link]
hy#:~:text=Cryptography%20involves%20creating%20wr
itten%20or,information%20to%20be%20kept%20secret.
&text=Information%20security%20uses%20cryptography
%20on,transit%20and%20while%20being%20stored
.

University Institute of Engineering (UIE)

 Department of Computer Science and Engineering (CSE)

References

• [Link]
ion-techniques-in-network-security?qid=e388c29f-793d
-4f2b-bcaf-9d22e9ca07b5&v=&b=&from_search=1

University Institute of Engineering (UIE)

 Department of Computer Science and Engineering (CSE)

E- Books Recommended

• [Link]
• [Link]
books
• [Link]
books
• [Link]
[Link]

University Institute of Engineering (UIE)