Topics to Cover

1) Principles of Public-Key Cryptosystems

2) Rivest-Shamir-Adleman (RSA)
3) Diffie Hellman Key Exchange
PRINCIPLES OF PUBLIC-KEY
CRYPTOSYSTEMS
 Asymmetric Keys:-
• a public key that anyone can use and a private key
that only one person has.
• They work together to do opposite tasks, like
locking (encrypting) and unlocking (decrypting)
Terminologies messages, or creating (signing) and checking
(verifying) signatures.
Associated with
Asymmetric Public Key Certificate:-
• A digital certificate, issued and signed by a
Encryption Certification Authority, links a subscriber's name to
a public key.
• The certificate confirms that the subscriber has
exclusive control over the corresponding private
key.
 Public Key (Asymmetric) Cryptographic
Algorithm:-
Terminologies • A cryptographic algorithm uses two keys: a
Associated public key that anyone can see and a
private key that only you keep secret.
with • It's very hard to figure out the private key
Asymmetric just by knowing the public key.
Encryption
Public Key Infrastructure (PKI):-
(Contd..)
• A system for managing certificates and
keys.
• Can create, update, and cancel certificates.
Misconceptions of Public-Key Encryption

• Public-key encryption is more secure from cryptanalysis than

symmetric encryption

• Public-key encryption is a general-purpose technique that has made

symmetric encryption obsolete

• There is a feeling that key distribution is trivial when using public-key

encryption, compared to the cumbersome handshaking involved with
key distribution centers for symmetric encryption
Evolution and Principles of Public-Key
Cryptosystems (PKC)

Public-key cryptography was created to solve 2 major challenges with

symmetric encryption:-
• Key Distribution
• Digital Signatures

In 1976, Whitfield Diffie and Martin Hellman from Stanford

University made a big discovery, which addressed both the problems,
and was different from cryptographic methods in past.
 • Private key
• Public Key
6 • Plaintext
Ingredients • Encryption Algorithm
• Ciphertext
of PKC • Decryption Algorithm
PKC (Encryption with Public Key)
PKC (Encryption with Private Key)
Conventional
and Public
Key
Encryption
Security • Confidentiality
• Authentication
Goals
• Integrity
provided • Accountability
by PKC
PKC for Confidentiality
 • Y = E(PUb, X)
• X = D(PRb,Y)
• An attacker can capture Y and has the public key
PKC for (PUb), but not the private key (PRb) or X.
Confidentiality • The attacker wants to find X and/or the private
(Contd..) key (PRb).
• The attacker has knowledge of E() and D().
• If the attacker cares about only one message,
he/she tries to guess X by generating a PT
estimate X̂ .
• If the enemy wants to read future messages too,
he/she will also try to guess the private key
(PRb) by generating an estimate (PRb)̂.
PKC for Authentication
 • Y = E(PRa, X)
• X = D(PUa, Y)

PKC for • Only A could have created the message since

Authentication it was encrypted with A’s private key.
(Contd..) • The encrypted message acts as a digital
signature.
• The message can't be changed without A’s
private key.
• This confirms both who sent it (source) and
that it hasn’t been altered (data integrity).
PKC for Confidentiality and
Authentication
 • Z = E(PUb, E(PRa,X))
• X = D(PUa, D(PRb,Z))

PKC for • ‘A’ encrypts a message with the sender’s private

Confidentiality key for a digital signature (Result = Y).
and • ‘A’ encrypts Y using receiver’s public key
(PUb). (Result = X)
Authentication • Only the intended receiver can decrypt the final
(Contd..) message with their private key.
• This method ensures that the message remains
confidential.
• However, the complete process requires the
complex public-key process to be done four
times instead of just two.
  The sender uses their private key, the
receiver’s public key, or both to encrypt or
sign messages, depending on the application.
Applications
 Public-key cryptosystems can be classified
for PKC into three categories:
• Encryption/Decryption
• Digital Signature
• Key Exchange

 Some algorithms work for all three

applications.

 Others can only be used for one or two

applications.
Applications
for PKC
(Contd..)
 • B (PUb, PRb):- Computationally easy
• C = E(PUb, M):- Computationally easy
Requirements • M = D(PRb, C) = D[PRb, E(PUb, M)]:-
Computationally easy
for PKC • Deriving PRb from PUb should be
computationally infeasible for an attacker.
• Recovering M from C and PUb should be
computationally infeasible for an attacker.
• M = D[PUb, E(PRb, M)] = D[PRb, E(PUb, M)]
  Trap Door One-Way Function
• Y = f(X):- Computationally feasible
• X = f-1(Y):- Computationally infeasible
Requirements • Y = fk(X) easy, if k and X are known
for PKC • X = fk–1(Y) easy, if k and Y are known
(Contd..) • X = fk–1(Y) infeasible, if Y known but k not
known

 A practical public-key scheme depends on

a suitable trap-door one-way function
 • Public-key encryption can be attacked using
brute-force, so using large keys is important for
security.
• However, bigger keys can slow down the
Cryptanalysis encryption and decryption process.
on PKC • Because of this, public-key encryption is
mainly used for key management and
signatures, rather than regular data encryption.
• It’s possible to calculate the private key from
the public key, but it's not yet been proven
Mathematically that this can't be done for any
public-key system.
• This means that all algorithms, even popular
ones like RSA, could potentially be vulnerable
because new ways to solve problems can be
discovered over time.
Rivest-Shamir-Adleman (RSA)
 RSA (Overview)
• Developed in 1977 at MIT, Cambridge (USA) by Ron Rivest, Adi Shamir &
Len Adleman.
• It was one of the first public-key cryptosystems.
• RSA is one of the most adopted algorithms in practical applications.
• RSA is versatile and can be applied to a wide range of applications, from
securing emails to enabling secure connections for websites (via SSL/TLS).
• RSA is also used for applications like digital signatures, VPNs, Blockchain,
Cryptocurrencies, etc.
 RSA (Overview)
• The PT and CT falls in the range [0,n-1], where n has a typical size of atleast
1024 bits.
• RSA makes use of modular exponentiation.
• PT is divided into blocks.
• Number of bits in each block ≤ (log2(n)+1).
 RSA (Key Generation)
• Select large primes ‘p’ and ‘q’, such that p≠q.
• n = p*q
• Φ(n) = (p-1)*(q-1)
• Select ‘e’, such that 1<e<Φ(n) and GCD(e, Φ(n))=1
• d = MI(e) mod Φ(n)
• Public Key = (e, n)
• Private Key = d
 RSA (Encryption and Decryption)

• Encryption:- C = Pe (mod n)
• Decryption:- P = Cd (mod n)
• P,C ∈ Zn

• Inputs to Encryption:- (P, e, n)

• Inputs to Decryption:- (C, d, n)
 Requirements for RSA algorithm
• Large ‘p’ and ‘q’ (at least 512 bits each).
• p≠q
• Significant difference between ‘p’ and ‘q’.
• It is possible to find values of ‘e’, ‘d’, and ‘n’ such that (M e)d 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’.
• e*d mod Φ(n) = 1
 d
Proof for C mod n = M
• Cd mod n = (Me)d mod n
• e*d ≡ 1 mod Φ(n)
• e*d = k*Φ(n) + 1
• MΦ(n) mod n = 1
• Mk*Φ(n) mod n = 1
• Mk*Φ(n) + 1 mod n = M
• Me*d mod n = M
• Cd mod n = M
 Computational Aspects of RSA
Encryption and Decryption
• Both encryption and decryption in RSA involve raising an integer to an integer
power, mod n
• Can make use of a property of modular arithmetic: [(a mod n) * (b mod n)] mod
n = (a * b) mod n
• Exponentiations Efficiency is also an important aspect to consider.
• CT or DT can be calculated using Fast modular exponentiation.
 Efficient RSA Public Key Operation

• To make the RSA algorithm faster, a specific number for ‘e’ is chosen.
• The most common choice for ‘e’ is 65537 (i.e. 216+1).
• Other popular choices for e are 3 and 17.
• These choices have only two 1 bits, which reduces the number of
multiplications needed.
• RSA can be weak with a small public key (e = 3).
 Efficient RSA Public Key generation
(e=3)
Assume that there are 3 different recipients who use e=3, but unique values of n
(i.e. n1, n2, n3)

In that case, the sender would send 3 different CTs to the 3 different recipients:-
• C1 = M3 mod n1
• C2 = M3 mod n2
• C3 = M3 mod n3

If n1, n2, n3, are pairwise relatively prime, then the attacker can calculate M 3 using
 Efficient RSA Private Key Operation

• Small value of ‘d’ will make RSA vulnerable to BFA and other
cryptanalysis methods.
• We can speed up the calculation M=C d mod n using CRT.
• Vp = Cd mod p; Vq = Cd mod q
• Let Xp = q*MI(q) mod p; Xq = p*MI(p) mod q
• According to CRT, M = (Vp*Xp + Vq*Xq) mod n
 Efficient RSA Private Key Operation
(Contd..)
• if d>p, Vp = Cd mod p = Cd mod (p-1) mod p
• if d>q, Vq = Cd mod q = Cd mod (q-1) mod q

• if d=p, Vp = Cd mod p = C
• if d=q, Vq = Cd mod q = C

• If d>p, and d>q, then the CRT method is 4 times the speed of
d
calculating (M = C mod n) directly.
 Computational Aspects for Key
Generation
Finding large prime numbers efficiently is important.

There’s no perfect way to find very large primes, so a different method is used:
• Randomly pick an odd number and check if it’s prime.
• If it’s not prime, keep picking new numbers until a prime is found.

Primality can be tested using various tests (Common one is Miller Rabin
algorithm)
 Computational Aspects for Key
Generation
Steps to find a prime number:-
• Randomly choose an odd number ‘n’.
• Randomly choose another number ‘a’ (a<n).
• As long as ‘n’ fails the test, start over from Step 1.
• If ‘n’ passes enough number of tests, accept ‘n’ as a prime, else go to step 2.

Approximate number of trials required to identify a prime near a number N =

ln(N)/2.
 Numerical 1
• A Plaintext = 123 is encrypted using RSA with key generation primes 61 and
59, and public exponent = 17. Calculate the private key, and CT.

Solution:-
• p = 61, q = 59, M = 123
• n = p*q = 3599
• Φ(n) = (p-1)*(q-1) = 3480
• e = 17
• d = MI(e) mod Φ(n) = MI(17) mod 3480
 Numerical 1 (Contd..)
q a b r v1 v2 v
204 3480 17 12 0 1 -204
1 17 12 5 1 -204 205
2 12 5 2 -204 205 -614
2 5 2 1 205 -614 1433
2 2 1 0 -614 1433 -3480
1 0 1433

• Private Key = d = 1433

 Numerical 1 (Contd..)
• C = Me mod n = 12317 mod 3599

12317 mod 3599:-

• 1232 mod 3599 = 733
• 1234 mod 3599 = 1038
• 12316 mod 3599 = 550
• 12317 mod 3599 = (12316 mod 3599 * 123) mod 3599 = (550*123) mod 3599
= 2868

CT = C = 2868
 Numerical 2
• In reference to the previous numerical, calculate the PT when CT=2868.

Solution:-
• M = Cd mod n = 28681433 mod 3599
• 1433 = 1024 + 256 + 128 + 16 + 8 + 1

28681433 mod 3599:-

• 28682 mod 3599 = 1709
• 28684 mod 3599 = 1892
• 28688 mod 3599 = 2258
 Numerical 2 (Contd..)
16
• 2868 mod 3599 = 2380
32
• 2868 mod 3599 = 3173
64
• 2868 mod 3599 = 1526
128
• 2868 mod 3599 = 123
256
• 2868 mod 3599 = 733
512
• 2868 mod 3599 = 1038
1024
• 2868 mod 3599 = 1343
 Numerical 2 (Contd..)
• 28681433 mod 3599 = (1343 * 733 * 123 * 2380 * 2258 * 2868) mod 3599
• 28681433 mod 3599 = [(1343 * 733 * 123) mod 3599 * (2380 * 2258 * 2868)
mod 3599 ] mod 3599
• 28681433 mod 3599 = (2380 * 428) mod 3599 = 123

PT = M = 123
 Numerical 3
• A PT (consists of 5 characters) is encrypted by using its corresponding ASCII
equivalents, and each character is encrypted separately. The key generation
primes are 11 and 19, and the public exponent is 47. The CT has a sequence
(41, 141, 76, 76, 29). Calculate the private key and PT.

Solution:-
• p = 11, q = 19, e = 47
• n = p*q = 209
• Φ(n) = (p-1)*(q-1) = 180
• d = MI(e) mod Φ(n) = MI(47) mod 180
 Numerical 3 (Contd..)
q a b r v1 v2 v
3 180 47 39 0 1 -3
1 47 39 8 1 -3 4
4 39 8 7 -3 4 -19
1 8 7 1 4 -19 23
7 7 1 0 -19 23 -180
1 0 23 -180

• Private Key = d = 23 = 16 + 4 + 2 + 1
 Numerical 3 (Contd..)
M1 = C1d mod n = 4123 mod 209:-
• 412 mod 209 = 9
4
• 41 mod 209 = 81
16
• 41 mod 209 = 36
• 4123 mod 209 = (4116 mod 209 * 414 mod 209 * 412 mod 209 * 41)
mod 209
23
• 41 mod 209 = (36 * 81 * 9 *41) mod 209 = 72
• M1 = ‘H’
 Numerical 3 (Contd..)
M2 = C2d mod n = 14123 mod 209:-
• 1412 mod 209 = 26
4
• 141 mod 209 = 49
16
• 141 mod 209 = 163
• 14123 mod 209 = (14116 mod 209 * 1414 mod 209 * 1412 mod 209 *
141) mod 209
23
• 141 mod 209 = (163 * 49 * 26 * 141) mod 209 = 69
• M2 = ‘E’
 Numerical 3 (Contd..)
M3 = C3d mod n = 7623 mod 209:-
• 762 mod 209 = 133
• 764 mod 209 = 133
• 7616 mod 209 = 133
• 7623 mod 209 = (7616 mod 209 * 764 mod 209 * 762 mod 209 * 76) mod
209
• 7623 mod 209 = (133 * 133 * 133 * 76) mod 209 = 76
• M3 = ‘L’

M = C d mod n = 7623 mod 209 = 76 = ‘L’

 Numerical 3 (Contd..)
M5 = C5d mod n = 2923 mod 209:-
2
• 29 mod 209 = 5
• 294 mod 209 = 25
• 2916 mod 209 = 4
23 16 4 2
• 29 mod 209 = (29 mod 209 * 29 mod 209 * 29 mod 209 * 29) mod
209
• 2923 mod 209 = (4 * 25 * 5 * 29) mod 209 = 79
• M5 = ‘O’

PT = ‘HELLO’
Diffie-Hellmann Key Exchange
(DHKE)
 History and Evolution of DHKE

• In 1970, Clifford Williamson secretly proposed the idea of Public Key

Exchange.
• In 1976, Whitfield Diffie and Martin Hellman publicly introduced the
algorithm in a paper titled 'New Directions in Cryptography’.
• This was a groundbreaking moment in cryptography, providing a method
for secure key exchange over an insecure channel.
• The algorithm gained traction in both academic and practical applications,
influencing many cryptographic protocols and systems, in 1980s.
• The method began to be standardized, with implementations appearing in
various protocols, including SSL/TLS for secure internet communications,
in 1990s.
DHKE
 • Used to establish secret key between only 2
communicating entities, at a time.
• The secret key depends on the participants'
private and public keys.
• Uses exponentiation in a finite field (modulo a
prime or polynomial):- Easy to calculate
DHKE • Security relies on the difficulty of solving
discrete logarithms.
(Contd..) • Discrete Logarithm for calculating private key
of Alice:- XA = dlogα,q(YA)
• Discrete Logarithm for calculating private key
of Bob:- XB = dlogα,q(YB)
Proof of same
secret key
generation by
Alice and Bob
 Numerical 1
• Alice and Bob agree upon the DHKE global parameters (59 and 6), where 6
is the primitive root of 59. The private key of Alice is 4 and that of Bob is 8.
Calculate the public keys generated by the 2 communicating entities, and the
secret key established by both the entities (show secret key calculations for
both the entities).

Solution:-
• q = 59, α = 6, XA = 4, XB = 8
XA
• YA = α mod q = 64 mod 59 = 57
XB
• YB = α 8
mod q = 6 mod 59 = 4
 Numerical 1 (Contd..)
K = (Y )XA mod q = 44 mod 59 = 20
A B

K = (Y )XB mod q = 578 mod 59

B A

• 574 mod 59 = 16
• 578 mod 59 = 20
• KB = 20
 Numerical 2
• Alice and Bob agree upon the DHKE global parameters (1009 and 22), where
22 is the primitive root of 1009. The private key of Alice is 25 and that of
Bob is 75. Calculate the public keys generated by the 2 communicating
entities, and the secret key established by both the entities.
Solution:-
q = 1009, α = 22, XA = 25, XB = 75

Y = αXA mod q = 2225 mod 1009

A
 Numerical 2 (Contd..)
• 25 = 16 + 8 + 1
4
• 22 mod 1009 = 168
• 228 mod 1009 = 981
• 2216 mod 1009 = 784
• 2225 mod 1009 = (784 * 981 * 22) mod 1009 =367
• YA = 367

Y = αXB mod q = 2275 mod 1009

B

• 75 = 64 + 8 + 2 + 1
 Numerical 2 (Contd..)
• 222 mod 1009 = 484
• 224 mod 1009 = 168
• 228 mod 1009 = 981
• 2216 mod 1009 = 784
• 2232 mod 1009 = 175
• 2264 mod 1009 = 355
• 2275 mod 1009 = (355 * 981 * 484 * 22) mod 1009 =
• 2275 mod 1009 = [(355 * 981) mod 1009 * (484 * 22) mod 1009] mod 1009
• 2275 mod 1009 = (150 * 558) mod 1009 = 962 = YB
 Numerical 2 (Contd..)
X
 KA = (YB) A mod q = 96225 mod 1009
• 25 = 16 + 8 + 1
• 9622 mod 1009 = 191
• 9624 mod 1009 = 157
• 9628 mod 1009 = 433
• 96216 mod 1009 = 824
• 96225 mod 1009 = (824 * 433 * 962) mod 1009 = 356
• KA = 356
 • Assume that a group of users (for example on LAN) agree
upon the global public parameters (‘α’ and ‘q’)
• Assume that a group of users (for example on LAN) each
creates a long-lasting private key (Xi).
• Each user calculates a public number (Y i) from their private.
• All public keys are stored in a trusted central location.
Use case of • Any user (j) can access another user’s (i) public value and
compute a secret key.
DHKE for • This key can be used to send encrypted messages between
users.
a group of • Only users ‘i’ and ‘j’ can figure out the key, so no one else
can read the messages.
users • User ‘i’ knows that only user ‘j’ could have sent the message,
confirming their identity. (Authentication, and Eventually
Resistance to Replay attack).
MITM on
DHKE
 • Alice and Bob think they have a secret key together.
• But Bob has a secret key (K1) with Darth, and Alice has a
secret key (K2) with Darth.
• This setup allows Darth to intercept and manipulate
messages between Alice and Bob.
MITM on
DHKE • Alice sends a PT to Bob, encrypted with K2: E(K2, PT).
(Contd..) • Darth intercepts this message and decrypts it to get PT.
• Darth can send the original message PT to Bob, encrypted
with K1: E(K1, PT)
• Or Darth can even send a modified message to Bob, also
encrypted with K1: E(K1, PTm)
• Hence, there is severe threat to Authentication +
Confidentiality.