GYANMANJARI INSTITUTE OF TECHNOLOGY

Bachelor of Engineering | Semester : 7 | Computer Engineering

Information Security
Course Code : 3170720

Prof. Mayank K. Champaneri

Computer Engineering Department
 SYLLABUS

UNIT TITLE
1 INTRODUCTION

2 STREAM CIPHERS AND BLOCK CIPHERS

3 MULTIPLE ENCRYPTION AND TRIPLE DES

4 PUBLIC KEY CRYPTOSYSTEMS WITH APPLICATIONS

5 CRYPTOGRAPHIC HASH FUNCTIONS

6 MESSAGE AUTHENTICATION CODES

7 DIGITAL SIGNATURE

8 KEY MANAGEMENT AND DISTRIBUTION

9 REMOTE USER AUTHENTICATION

 UNIT : 4

PUBLIC KEY CRYPTOSYSTEMS WITH APPLICATIONS

 Looping 4
 Topics to be covered

▪ Public Key Cryptosystems with Applications

▪ Requirements and Cryptanalysis
▪ RSA algorithm
▪ RSA computational aspects and security
▪ Diffie-Hillman Key Exchange algorithm
▪ Man-in-Middle attack
Symmetric key Encryption

Secret key shared by Secret key shared by

sender and recipient sender and recipient
K
K
Transmitted
cipher text
Y = E(K, X)
X X
Plaintext Encryption Algorithm Decryption Algorithm Plaintext
input (e.g. AES) (reverse of encryption output
algorithm)
Asymmetric key Encryption with Public Key
Bob’s ▪ The entire encrypted message
Public serves as a confidentiality.
Joy key ring
Ted
Mike Alice

PUa Alice’s public PRa Alice’s private

key key

Transmitted
X cipher text X
Y = E(PUa, X)
Plaintext Plaintext
input Encryption Algorithm Decryption Algorithm
output
(e.g. RSA)

Bob Alice
Asymmetric key Encryption with Private Key
▪ The entire encrypted message Alice’s
serves as a digital signature. Public
Joy key ring
Ted
Mike Bob

PRb Bob’s private PUb Bob’s public

key key

Transmitted
X cipher text X
Y = E(PRb, X)
Plaintext Plaintext
input Encryption Algorithm Decryption Algorithm
output
(e.g. RSA)

Bob Alice
Authentication and Confidentiality

Source A Source B

Message X Encryption Y Encryption Z Decryption Y Decryption X Message

source Algorithm Algorithm Algorithm Algorithm Dest.

PUb PRb
Key pair
PRa PUa source

Key pair
source

Z = E(PUb, E(PRa, X)) X = D(PUa, D(PRB, Z))

Applications for Public-Key Cryptosystems

▪ Encryption/decryption: The sender encrypts a message with the

recipient’s public key.
▪ Digital signature: The sender “signs” a message with its private
key. Signing is achieved by a cryptographic algorithm applied to
the message or to a small block of data that is a function of the
message.
▪ Key exchange: Two sides cooperate to exchange a session key.
Several different approaches are possible, involving the private
key(s) of one or both parties.
RSA Algorithm
▪ RSA is a block cipher in which the Plaintext and Ciphertext are
represented as integers between 0 and n-1 for some n.
▪ Large messages can be broken up into a number of blocks.
▪ Each block would then be represented by an integer.

Step-1: Generate Public key and Private key

Step-2: Encrypt message using Public key
Step-3: Decrypt message using Private key
Step-1: Generate Public key and Private key
▪ Select two large prime numbers: p and q
▪ Calculate modulus : n = p * q
▪ Calculate Euler’s totient function : φ(n) = (p-1) * (q-1)
▪ Select e such that e is relatively prime to φ(n) and 1 < e < φ(n)

Two numbers are relatively prime if they have no common factors

other than 1.

▪ Determine d such that d * e ≡ 1 (mod φ(n))

▪ Publickey : PU = { e, n }
▪ Privatekey : PR = { d, n }
Step-1: Generate Public key and Private key
▪ Select two large prime numbers: p = 3 and q = 11
▪ Calculate modulus : n = p * q, n = 33
▪ Calculate Euler’s totient function : φ(n) = (p-1) * (q-1)
φ(n) = ( 3 – 1 ) * ( 11 – 1 ) = 20
▪ Select e such that e is relatively prime to φ(n) and 1 < e < φ(n)
▪ We have several choices for e : 7, 11, 13, 17, 19 Let’s take e = 7
▪ Determine d such that d * e ≡ 1 (mod φ(n))
▪ ? * 7 ≡ 1 (mod 20), 3 * 7 ≡ 1 (mod 20) • This is equivalent to
finding d which satisfies
de = 1 + j.φ(n) where j is
▪ Public key : PU = { e, n } , PU = { 7, 33 } any integer.
▪ Private key : PR = { d, n }, PR = { 3, 33 } • We can rewrite this as
d = (1 + j. φ(n)) / e
Step-2 : Encrypt Message

▪ Encryption Using Public key: C = Me mod n

Ciphertext Input Publickey

Message

PU = { e, n } , PU = { 7, 33 }
For message M = 14
C = 147 mod 33
C = [(141 mod 33) X (142 mod 33) X (144 mod 33)] mod 33
C = (14 X 31 X 4) mod 33 = 1736 mod 33
C = 20
Step-3 : Decrypt Message

▪ Encryption Using Public key: M = Cd mod n

Plaintext Cipher Privatekey

Message Message

PR = { d, n } , PR = { 3, 33 }
For Ciphertext C = 20
M = 203 mod 33
M = [(201 mod 33) X (202 mod 33)] mod 33
M = (20 X 4) mod 33 = 80 mod 33
M = 14
 Example RSA Algorithm

Encryption Decryption

Plaintext 7 Ciphertext 3 Plaintext

14 mod 33 = 20 20 mod 33 = 14
14 20 14

PU = 7, 33 PR = 3, 33
RSA Example
▪ Find n, φ(n), e, d for p=7 and q= 19 then demonstrate encryption
and decryption for M = 6
n = p * q = 7 * 19 = 133 Finding e relatively prime to 108
φ(n) = ( p – 1 ) * ( q – 1) = 108 e = 2 => GCD( 2, 108 ) = 2 (no)
e = 3 => GCD( 3, 108 ) = 3 (no)
e = 5 => GCD( 5, 108 ) = 1 (Yes)

• Finding d such that (d * e ) mod φ(n) = 1 Public key :

• We can rewrite this as d = (1 + j . φ(n)) / e PU = { e, n } = {5, 133}
j = 0 => d = 1 / 5 = 0.2  integer ? (no) Private key :
j = 1 => d = 109 / 5 = 21.8  integer ? (no) PR = { d, n } = {65, 133}
j = 2 => d = 217 / 5 = 43.4  integer ? (no)
j = 3 => d = 325 / 5 = 65 integer ? (yes)
 RSA Example – cont…
▪ Encryption:
C = Me mod n PU = { e, n } , PU = { 5, 133 }
For message M = 6
C = 65 mod 133
C = 7776 mod 33
C = 62
▪ Decryption:
M = Cd mod n PR = { d, n } , PU = { 65, 133 }
For C = 62
M = 6265 mod 133
M = 2666 mod 33
M=6
RSA Example
▪ P and Q are two prime numbers. P=7, and Q=17. Take public key
E=5. If plain text value is 10, then what will be cipher text value
according to RSA algorithm?
▪ n = 119
▪ φ(n) = 96
▪ e=5
▪ d = 77
▪ PU = { 5, 119 }
▪ PR = {77, 119}
▪ C = 105 mod 119 => C = 40
Diffie-Hellman key Exchange
▪ The purpose of the Diffie-Hellman algorithm is to enable two
users to securely exchange a key that can be used for subsequent
encryption of message.

▪ This algorithm depends for its effectiveness on the difficulty of

computing discrete logarithms.
Primitive root
▪ Let 𝒑 be a prime number
▪ Then 𝒂 is a primitive root for 𝒑, if the powers of 𝒂 modulo 𝒑
generates all
𝑎 integers
𝑚𝑜𝑑 𝑝,from 1 to 𝒑𝑝,–…
𝑎2 𝑚𝑜𝑑 1 in
, 𝑎some
𝑝−1 permutation.
𝑚𝑜𝑑 𝑝

▪ Example: p = 7 then primitive root is 3 because powers of 3 mod 7

generates all the integers from 1 to 6
31 = 3 ≡ 3 𝑚𝑜𝑑 7
32 = 9 ≡ 2 𝑚𝑜𝑑 7
33 = 27 ≡ 6 𝑚𝑜𝑑 7
34 = 81 ≡ 4 𝑚𝑜𝑑 7
35 = 243 ≡ 5 𝑚𝑜𝑑 7
36 = 729 ≡ 1 𝑚𝑜𝑑 7
Discrete Logarithm
▪ For any integer 𝒃 and a primitive root 𝒂 of prime number 𝒑, we
can find a unique exponent 𝒊 such that
𝑏 = 𝑎𝑖 𝑚𝑜𝑑 𝑝 𝑤ℎ𝑒𝑟𝑒 0 ≤ 𝑖 ≤ (𝑝 − 1)
▪ The exponent 𝒊 is referred as the discrete logarithm of 𝒃 for the
base 𝒂, mod 𝒑. It expressed as below.
𝑏dlog 𝑎,𝑝 (𝑏)
Diffie-Hellman Key Exchange – Cont…
▪ User A and User B agree on two large prime numbers q and α.
User A and User B can use insecure channel to agree on them.
▪ User A selects a random integer 𝑋𝐴 < 𝑞 and calculates 𝑌𝐴
Diffie-Hellman Key Exchange – Cont…
Global Public Elements
𝑞 prime number
𝛼 𝛼 < 𝑞 and 𝛼 is primitive root of 𝑞

User A Key Generation

Select private 𝑋𝐴 𝑋𝐴 < 𝑞
Calculate public 𝑌𝐴 𝑌𝐴 = 𝛼 𝑋𝐴 mod 𝑞

User B Key Generation

Select private 𝑋𝐵 𝑋𝐵 < 𝑞
Calculate public 𝑌𝐵 𝑌𝐵 = 𝛼 𝑋𝐵 mod 𝑞
Diffie-Hellman Key Exchange – Cont…
User A Key Generation
Select private 𝑋𝐴 𝑋𝐴 < 𝑞
Calculate public 𝑌𝐴 𝑌𝐴 = 𝛼 𝑋𝐴 mod 𝑞
User B Key Generation
Select private 𝑋𝐵 𝑋𝐵 < 𝑞
Calculate public 𝑌𝐵 𝑌𝐵 = 𝛼 𝑋𝐵 mod 𝑞
Calculation of Secret Key by User A
𝐾 = 𝑌𝐵 𝑋𝐴 mod 𝑞

Calculation of Secret Key by User b

𝑋𝐵
𝐾 = 𝑌𝐴 mod 𝑞
Diffie-Hellman Key Exchange – Cont…
User A Key Generation
Private 𝑋𝐴 𝑋𝐴 < 𝑞 , Public 𝑌𝐴 𝑌𝐴 = 𝛼 𝑋𝐴 mod 𝑞
User B Key Generation
Private 𝑋𝐵 𝑋𝐵 < 𝑞 , Public 𝑌𝐵 𝑌𝐵 = 𝛼 𝑋𝐵 mod 𝑞
Secret Key by User A : 𝐾 = 𝑌𝐵 𝑋𝐴 mod 𝑞

Secret Key by User B : 𝐾 = 𝑌𝐴 𝑋𝐵 mod 𝑞

𝐾= 𝑌𝐵 𝑋𝐴 mod 𝑞
𝐾= 𝛼 𝑋𝐵 mod 𝑞 𝑋𝐴 mod 𝑞
𝐾= 𝛼 𝑋𝐵 𝑋𝐴 mod 𝑞
𝐾= 𝛼 𝑋𝐵 𝑋𝐴 mod 𝑞
𝐾= 𝛼 𝑋𝐴 𝑋𝐵 mod 𝑞
𝐾= 𝛼 𝑋𝐴 mod 𝑞 𝑋𝐵 mod 𝑞
𝐾= 𝑌𝐴 𝑋𝐵 mod 𝑞
Diffie-Hellman Key Exchange Example
▪ Alice and bob agrees on a prime number 𝒒 = 𝟐𝟑
▪ 𝜶 = 𝟓 as primitive root of 𝑞
▪ Alice selects a private integer 𝑿𝑨 = 𝟔
▪ Alice computes 𝑌𝐴 = 𝛼 𝑋𝐴 mod 𝑞 => 𝒀𝑨 = 𝟓𝟔 𝐦𝐨𝐝 𝟐𝟑 = 𝟖
▪ Bob selects a private integer 𝑿𝑩 = 𝟏𝟓
▪ Bob computes 𝑌𝐵 = 𝛼 𝑋𝐵 mod 𝑞 => 𝒀𝑩 = 𝟓𝟏𝟓 𝐦𝐨𝐝 𝟐𝟑 = 𝟏𝟗
▪ Alice sends 𝑌𝐴 to Bob and Bob sends 𝑌𝐵 to Alice
▪ Alice computes key 𝐾 = 𝑌𝐵 𝑋𝐴 mod 𝑞 => 𝑲 = 𝟏𝟗 𝟔 𝒎𝒐𝒅 𝟐𝟑
▪ 𝑲=𝟐
𝑋𝐵 𝟏𝟓
▪ Bob computes key 𝐾 = 𝑌𝐴 mod 𝑞=> 𝑲 = 𝟖 𝒎𝒐𝒅 𝟐𝟑
▪ 𝑲=𝟐
Diffie-Hellman Key Exchange Illustration
Man in the middle attack
▪ Suppose Alice and Bob wish to exchange keys, and Darth is the
adversary.
1. Darth prepares for the attack by generating two random private keys
XD1 and XD2 and then computes corresponding public keys YD1 and YD2.
2. Alice transmits YA to Bob.
3. Darth intercepts YA and transmits YD1 to Bob. Darth also calculates
K2=(YA)XD2 mod q.
4. Bob receives YD1 and calculates K1 = (YD1)XB mod q.
5. Bob transmits YB to Alice.
6. Darth intercepts YB and transmits YD2 to Alice. Darth calculates
K1=(YB)XD1 mod q.
7. Alice receives YD2 and calculates K2 = (YD2)XA mod q.
THANK YOU