### lecture ppt - IT352 : Network Security

```PUBLIC KEY CRYPTOGRAPHY
ALGORITHM
Concept and Example
1
IT352 | Network Security |Najwa
AlGhamdi
RSA
1. It’s a block cipher algorithm.
2. Plain text and cipher text are integer
between 0 to n-1 for some n.
3. RSA algorithm involve the following
operations
1. Key Generation.
2. Encryption/Decryption
2
IT352 | Network Security |Najwa
AlGhamdi
RSA - Key Generation
• Each user generates a public/private key pair by:
1. selecting two large primes at random: p, q & p<> q
2. computing their system modulus n=p.q
3.
Calculate ø(n)=(p-1)(q-1)
‫ والقاسم‬n ‫ عدد األرقام الموجبة التي اقل من‬ø(n) is Euler Totient :
. 1 ‫المشترك بينها هو‬
4. selecting at random the encryption key e
– where 1<e<ø(n), gcd(e,ø(n))=1
5. solve following equation to find decryption key d
– e.d mod ø(n) = 1 and 0≤d≤n
6. publish their public encryption key: PU={e,n}
7. keep secret private decryption key: PR={d,n}
3
IT352 | Network Security |Najwa
AlGhamdi
–
RSA – Encryption/ Decryption
• to encrypt a message M the sender:
– obtains public key of recipient PU={e,n}
– computes: C = Me mod n, where 0≤M<n
• to decrypt the ciphertext C the owner:
– uses their private key PR={d,n}
– computes: M = Cd mod n
• Both Sender and Receiver know the value of
n, e.
4
IT352 | Network Security |Najwa
AlGhamdi
Example
• Plain Text =88;
Steps
5
Values
1. Select two prime numbers
p=17 , q = 11
2. Calculate n = pq
N = 17 ×11 = 187
3. Calculate ø(n)=(p-1)(q-1)
ø(n)= 16 × 10 =
160
4. Select e such that e is relatively
prime to ø(n) = 160
e= 7
5. Determine d such that de mod
160 = 1
d = 23 , because 27 ×7 =
161 = ( 1×160) +1
Public key
{7, 187}
Private Key
{23, 187}
IT352 | Network Security |Najwa
AlGhamdi
Example
• Plain Text =88;
sample RSA encryption/decryption is:
given message M = 88 (nb. 88<187)
encryption:
C = 887 mod 187 = 11
decryption:
M = 1123 mod 187 = 88
6
IT352 | Network Security |Najwa
AlGhamdi
1. Diffie-Hellman Key Exchange
• The purpose is to share a secrete key securely
and use it in the encryption.
• Diffie- Hellman is using discrete logarithm
•
7
IT352 | Network Security |Najwa
AlGhamdi
1. Diffie-Hellman Key Exchange:
Discrete Logarithm
• Primitive root of a
prime number p is a
number whose power
generate all integers
from 1 to p-1 .
• Example : p = 7 , then a = 3
Power
– A mod p , a^2 mod p , a
^3 mod p .. Contain all
numbers from 1 to p-1
0
3^0 mod 7 = 1
1
3^ 1 mod 7 = 3
2
3^2 mod 7 = 2
3
3^3 mod 7 = 6
4
3^4 mod 7 = 4
5
3^5 mod 7 = 5
……
8
IT352 | Network Security |Najwa
AlGhamdi
Number
2. Diffie Hellman Setup
1. all users agree on global parameters:
– large prime integer q
– a being a primitive root mod q
2. each user generates their key
– User A
• chooses a secret key (number): xA < q
xA
• compute their public key: yA = a mod q
– User B
• chooses a secret key (number): xB < q
xB
• compute their public key: yB = a mod q
9
IT352 | Network Security |Najwa
AlGhamdi
2. Diffie Hellman Setup
3. Generation of Secret Key
xA
User A : K = (yB) mod q
xB
User B : K = (yA) mod q
10
IT352 | Network Security |Najwa
AlGhamdi
2. Diffie Hellman Key Exchange
• shared session key for users A & B is KAB:
xB
KAB = yA mod q (which B can compute)
xA
= yB mod q (which A can compute)
• KAB is used as session key in private-key encryption
scheme between Alice and Bob
• if Alice and Bob subsequently communicate, they will
have the same key as before, unless they choose
new public-keys
y
A
A
B
yB
11
IT352 | Network Security |Najwa
AlGhamdi
Man in the Middle Attack
1.
2.
3.
4.
5.
6.
7.

12
Darth prepares by creating two private / public keys
Alice transmits her public key to Bob
Darth intercepts this and transmits his first public key to Bob.
Darth also calculates a shared key with Alice
Bob receives the public key and calculates the shared key (with