CLO 2

Lecture#06
Public Key Cryptography and
RSA
Course: Cryptography & Network Security (CE-408)
Course Teacher: Ms. Rukaiya

Contact Info:

Room No: BS-02, CED / AS-09, ORIC

Email: [email protected]

1
 Secret/ Symmetric Key Encryption
Problems

• If key is disclosed, communications are

compromised

• Key must be exchanged before transmission

with recipient, so to exchange need a secure
method

• Also, does not protect sender from receiver

forging a message and claiming that it’s sent
by the sender

2
 Public-Key Cryptography
• Public-key encryption involves usage of two keys

 Public-key
 It is known to anybody
 It can be used to encrypt messages and verify signatures

 Private-key
 It is known to the recipient
 It can be used to decrypt messages and create digital
signature

3
 Conventional And Public Key Encryption
Conventional Encryption Public-Key Encryption
Needed to Work: Needed to Work:

1. The same algorithm with the 1. One algorithm is used for encryption
same key is used for encryption and a related algorithm for
and decryption. decryption with a pair of keys, one
for encryption and one for
2. The sender and receiver must decryption.
share the algorithm and the key.
2. The sender and receiver must each
Needed for Security: have one of the matched pair of keys
(not the same one).
1. The key must be kept secret.
Needed for Security:
2. It must be impossible or at least
impractical to decipher a 1. One of the two keys must be kept
message if the key is kept secret. secret.

3. Knowledge of the algorithm plus 2. It must be impossible or at least

samples of ciphertext must be impractical to decipher a message if
insufficient to determine the key. one of the keys is kept secret.

3. Knowledge of the algorithm plus one

of the keys plus samples of ciphertext
must be insufficient to determine the
other key. 4
Comparison of Secret and Public Key
Encryption

Distinct
Secret Key Public Key
Features
No. of keys Single key Pair of keys
Types of Keys Key is secret One is public,
one is private
Size of keys 50 – 250 bits 500 – 2500 bits
Relative Faster Slower
Speeds

5
 Terminologies Related to Asymmetric
Encryption
Table 9.1 Terminology Related to Asymmetric Encryption

Asymmetric Keys
Two related keys, a public key and a private key that are used to perform complementary
operations, such as encryption and decryption or signature generation and signature verification.

Public Key Certificate

A digital document issued and digitally signed by the private key of a Certification
Authority that binds the name of a subscriber to a public key. The certificate indicates that the
subscriber identified in the certificate has sole control and access to the corresponding private
key.

Public Key (Asymmetric) Cryptographic Algorithm

A cryptographic algorithm that uses two related keys, a public key and a private key. The
two keys have the property that deriving the private key from the public key is computationally
infeasible.

Public Key Infrastructure (PKI)

A set of policies, processes, server platforms, software and workstations used for the
purpose of administering certificates and public-private key pairs, including the ability to issue,
maintain, and revoke public key certificates.

6
 Misconceptions Concerning 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

7
 Principles of Public-Key Cryptosystems
• The concept of public-key cryptography evolved from an attempt
to attack two of the most difficult problems associated with
symmetric encryption:
Key
distribution
• How to have secure communications in general without
having to trust a KDC with your key

Digital
signatures
• How to verify that a message comes intact from the
claimed sender

• Whitfield Diffie and Martin Hellman from Stanford University

achieved a breakthrough in 1976 by coming up with a method
that addressed both problems and was radically different from
all previous approaches to cryptography
8
 Public-Key Cryptosystems
• A public-key encryption scheme has six
ingredients:

Encryption Decryption
Plaintext Public key Private key Ciphertext
algorithm algorithm

The Accepts
readable the
The
message Performs ciphertext
Used for Used for scrambl
or data various and the
encryptio encrypti ed
that is transform matching
n or on or message
fed into ations on key and
decryptio decrypti produce
the the produces
n on d as
algorith plaintext the
output
m as original
input plaintext

9
 Encryption with Public Key

Bobs's
public key
ring
Joy
Ted
Mike Alice

PUa Alice's public PRa Alice 's private

key key

Transmitted X=
X ciphertext D[PRa, Y]

Y = E[PUa, X]
Plaintext Plaintext
Encryption algorithm Decryption algorithm
input output
(e.g., RSA)

Bob (a) Encryption with public key Alice

10
Plaintext Plaintext
Encryption algorithm Decryption algorithm
input output
(e.g., RSA)
Encryption with Private Key
Bob (a) Encryption with public key Alice

Alice's
public key
ring
Joy
Ted
Mike Bob

PRb Bob's private PUb Bob's public

key key

X=
X Transmitted D[PUb, Y]
ciphertext

Y = E[PRb, X]

Plaintext Plaintext
Encryption algorithm Decryption algorithm
input output
(e.g., RSA)

Bob (b) Encryption with private key Alice

11
 Public-key Cryptosystem: Confidentiality

^
X
Cryptanalyst
^
PRb

Source A Destination B

Message X Encryption Decryption

Destination
Source Algorithm Y = E[PUb, X] Algorithm
X=
D[PRb, Y]

PUb PRb

Key Pair
Source

Figure 9.2 Public-Key Cryptosystem: Secrecy

12
Public-key Cryptosystem: Authentication

13
Public-key Cryptosystem: Authentication
and Secrecy

14
Applications for Public-Key Cryptosystems

Algorithm Encryption/Decryption Digital Signature Key Exchange

RSA Yes Yes Yes
Elliptic Curve Yes Yes Yes
Diffie-Hellman No No Yes
DSS No Yes No

15
 Applications for Public-Key Cryptosystems
• Public-key cryptosystems can be classified into
three categories:

• The sender encrypts a message

Encryption/decryption with the recipient’s public key

• The sender “signs” a message

Digital signature with its private key

• Two sides cooperate to

Key exchange exchange a session key

• Some algorithms are suitable for all three

applications, whereas others can be used only
for one or two
16
 Public-Key Requirements
• Conditions that these algorithms must fulfill:
 It is computationally easy for a party B to generate a
pair (public-key PUb, private key PRb)
 It is computationally easy for a sender A, knowing the
public key and the message to be encrypted, to generate
the corresponding ciphertext
 It is computationally easy for the receiver B to decrypt
the resulting ciphertext using the private key to recover
the original message
 It is computationally infeasible for an adversary,
knowing the public key, to determine the private key
 It is computationally infeasible for an adversary,
knowing the public key and a ciphertext, to recover the
original message
 The two keys can be applied in either order
17
 Public-Key Requirements
• Need a trap-door one-way function
 A one-way function is one that maps a domain into a range such that
every function value has a unique inverse, with the condition that the
calculation of the function is easy, whereas the calculation of the inverse
is infeasible
 Y = f(X) easy
 X = f–1(Y) infeasible

• A trap-door one-way function is a family of invertible functions fk,

such that
 Y = fk(X) easy, if k and X are known
 X = fk–1(Y) easy, if k and Y are known
 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

18
 Public-Key Cryptanalysis
• A public-key encryption scheme is vulnerable to a brute-force
attack
 Countermeasure: use large keys
 Key size must be small enough for practical encryption and
decryption
 Key sizes that have been proposed result in encryption/decryption speeds
that are too slow for general-purpose use
 Public-key encryption is currently confined to key management
and signature applications

 Another form of attack is to find some way to compute the private key
given the public key
 To date it has not been mathematically proven that this form of
attack is infeasible for a particular public-key algorithm

 Finally, there is a probable-message attack

 This attack can be thwarted by appending some random bits to simple
messages

19
 Rivest-Shamir-Adleman (RSA)
Algorithm
• Developed in 1977 at MIT by Ron Rivest, Adi
Shamir & Len Adleman

• Most widely used general-purpose approach to

public-key encryption

• It is a cipher in which the plaintext and

ciphertext are integers between 0 and n – 1 for
some n
 A typical size for n is 1024 bits, or 309 decimal digits

20
 RSA Algorithm
• RSA makes use of an expression with exponentials
• Plaintext is encrypted in blocks with each block having a
binary value less than some number n
• Encryption and decryption are of the following form, for
some plaintext block M and ciphertext block C
C = Me mod n
M = Cd mod n = (Me)d mod n = Med mod n
• Both sender and receiver must know the value of n
• The sender knows the value of e, and only the receiver
knows the value of d
• This is a public-key encryption algorithm with a public key
of PU={e,n} and a private key of PR={d,n}

21
 Algorithm Requirements
• For this algorithm to be satisfactory for public-
key encryption, the following requirements
must be met:
1. It is possible to find values of e, d, n
such that Med mod n = M for all M < n
2. It is relatively easy to calculate Me mod n
and Cd mod n for all values of M < n
3. It is infeasible to determine d given e
and n

22
 Key Generation by Alice

Select p, q p and q both prime, p ≠ q

Calculate n = p ´ q

Calculate f(n) = (p – 1)(q – 1)

Select integer e gcd(f(n), e) = 1; 1 < e < f(n)

Calculate d d º e-1 (mod f(n))

Public key PU = {e, n}

Private key PR = {d, n}

Encryption by Bob with Alice's Public Key

Plaintext: M<n

Ciphertext: C = Me mod n

Decryption by Alice with Alice's Private Key

Ciphertext: C

Plaintext: M = Cd mod n

Figure 9.5 The RSA Algorithm 23

RSA-Key Generation
• RSA obtains its security from the difficulty of factoring large
numbers

Key Generation
1. First choose two prime numbers p and q (large) and find
the product n, where n= p x q

2. Compute Euler totient function

ø(n) = (p-1)(q-1)

3. Next chose ‘e’ relatively prime to ø(n)

e < n , gcd(e, ø(n) =1) Encryption key

4. Finally compute ‘d’ such that e.d=1 mod ø(n), where

0 < d< n Decryption key
Obviously ‘d’ can be recovered only if p and q are known/
recovered from modulus n
(e,n) -> public key
(d,n) -> private key 24
RSA-Key Generation

• PUBLIC KEY INFRASTRUCTURE (PKI)

 It provides assurance of public key.

 It provides the identification of public keys and their

distribution. An anatomy of PKI comprises of the following
components

• Public Key Certificate, commonly referred to as ‘digital

certificate.
• Private Key tokens.
• Certification Authority.
• Registration Authority.
• Certificate Management System

25
DIGITAL CERTIFICATE
• It can be considered as the ID card issued to the person. People use
ID cards such as a driver's license, passport to prove their identity.

• These are not only issued to people, but they can be issued to
computers, software packages or anything else that need to prove the
identity in the electronic world.

• These are based on the ITU standard X.509 which defines a standard
certificate format for public key certificates and certification validation.
Hence digital certificates are sometimes also referred to as X.509
certificates.

• Public key pertaining to the user client is stored in digital certificates

by CA along with other relevant information such as client information,
expiration date, usage, issuer etc.

• CA digitally signs this entire information and includes digital signature

in the certificate.

• Anyone who needs the assurance about the public key and
associated information of client, he carries out the signature validation
process using CA’s public key. Successful validation assures that the
public key given in the certificate belongs to the person whose details
are given in the certificate. 26
RSA-Key Generation

27
 Example of RSA Algorithm
• p = 3, q =11. n=p* q = 3* 11 = 33
• Calculate ø(n) = (p-1) (q-1) = (3-1) (11-1) = 2 * 10 = 20
There are 20 relative numbers to 33, what are they??
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20,
21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32
d=7 (7 and 20 have no common factor but 1)
7 e = 1 mod 20
Find ‘e’ using Extended Euclidean algorithm, as e is
multiplicative inverse of d
e =3 Decryption

Encryption M=Cd mod n

=267 mod 33
C=Me mod n = 8031810176 mod 33
C=53 mod 33 M = 5 mod 33
C = 125 mod 33 = 26 mod 33
28
 Example
• p = 7, q =11, e =13 , M= 5 n=p* q = 7* 11 = 77
• Calculate ø(n) = (p-1) (q-1) = (7-1) (11-1) = 6 * 10 = 60
Encryption
C=Me mod n
C=513mod 77
C = 1220703125 mod 77 = 26 mod 77
e * d = 1 mod ø(n)
Find ‘d’ using Extended Euclidean algorithm
q a b r 𝒕𝟏 𝒕𝟐 t
4 60 13 8 0 1 -4
1 13 8 5 1 -4 5 Decryption
1 8 5 3 -4 5 -9
M=Cd mod n
1 5 3 2 5 -9 14
=2637 mod 77
1 3 2 1 -9 14 -23 M = 5 mod 77
2 2 1 0 14 -23 60
1 0 -23 60 29
 Example
• Using Fast Algorithm
M =2637 mod 77
Binary representation of 37 is 100101
261 mod 77 = 26
262 = 26 x 26 mod 77 = 676 mod 77 = 60
264 = 262 x 262 mod 77 = 60 x 60 mod 77 =3600 mod 77 =58
268 = 264 x 264 mod 77 = 58 x 58 mod 77 =3364 mod 77 =53
2616 = 268 x 268 mod 77 = 53 x 53 mod 77 =2809 mod 77 =37
2632 = 2616 x 2616 mod 77 = 37 x 37 mod 77 =1369 mod 77 =60
= 26 x 58 x 60 mod 77
= 90480 mod 77
M = 5 mod 77 30
 Example of RSA Algorithm

Encryption Decryption

ciphertext
plaintext plaintext
7 11 23
88 88 mod 187 = 11 11 mod 187 = 88 88

PU = 7, 187 PR = 23, 187

Figure 9.6 Example of RSA Algorithm

31
 Sender
3
Plaintext P

Decimal string

4
Blocks of numbers
P1, P2,

5
Ciphertext C
2
Public key C1 = P1e mod n
e, n C2 = P2e mod n

RSA Processing of n = pq
Multiple Blocks
11
Transmit
6 7
Private key Recovered
d, n decimal text
P1 = C1d mod n
d= mod f(n)
e–1 P2 = C2d mod n 5
f(n) = (p – 1)(q – 1) 1
1 n = pq 1 1

e, p, q
p

Random number Ran

Receiver
generator

(a) General approach

32
 Sender Sender
3 3
Plaintext P How_are_you?

Decimal string 33 14 22 62 00 17 04 62 24 14 20 66

4 4
Blocks of numbers P1 = 3314 P2 = 2262 P3 = 0017
P1, P2, P4 = 0462 P5 = 2414 P6 = 2066

5 5
Ciphertext C C1 = 3314 11 mod 11023 = 10260
2 2 C2 = 2262 11 mod 11023 = 9489
Public key C1 = P1e mod n e = 11 C3 = 17 11 mod 11023 = 1782
e, n C2 = P2e mod n n = 11023
RSA Processing of
C4 = 462 11 mod 11023 = 727
C5 = 2414 11 mod 11023 = 10032
C6 = 2066 11 mod 11023 = 2253

Multiple Blocks
n = pq
Transmit
11023 = 73 151
Transmit
6 7 6 7
Private key Recovered d = 5891
P1 = 10260 5891 mod 11023 = 3314
d, n decimal text n = 11023
P2 = 9489 5891 mod 11023 = 2262
P1 = C1d mod n P3 = 1782 5891 mod 11023 = 0017
d= mod f(n)
e–1 P2 = C2d mod n 5891 = 11–1 mod 10800 P4 = 7275891 mod 11023 = 0462
f(n) = (p – 1)(q – 1) 10800 = (73 – 1)(151 – 1) P5 = 10032 5891 mod 11023 = 2414
1 n = pq 1 11023 = 73 51 P6 = 2253 5891 mod 11023 = 2066
e = 11
e, p, q
p = 73, q = 151

Random number Random number

Receiver Receiver
generator generator

(a) General approach (b) Example

33
 Efficient Operation Using the Public
Key
• To speed up the operation of the RSA algorithm
using the public key, a specific choice of e is
usually made
• The most common choice is 65537 (2 16 + 1)
 Two other popular choices are e=3 and e=17
 Each of these choices has only two 1 bits, so the
number of multiplications required to perform
exponentiation is minimized
 With a very small public key, such as e = 3, RSA
becomes vulnerable to a simple attack

34
 Efficient Operation Using the Public
Key
• Decryption uses exponentiation to power d
 A small value of d is vulnerable to a brute-force
attack and to other forms of cryptanalysis

• Can use the Chinese Remainder Theorem (CRT)

to speed up computation
 The quantities d mod (p – 1) and d mod (q – 1) can be
precalculated
 End result is that the calculation is approximately
four times as fast as evaluating M = Cd mod n
directly

35
 Key Generation

• Before the application • Because the value of n =

of the public-key pq will be known to any
cryptosystem each potential adversary,
participant must primes must be chosen
generate a pair of keys: from a sufficiently large
 Determine two prime set
numbers p and q  The method used for
 Select either e or d and finding large primes must
calculate the other be reasonably efficient

36
The Security of RSA

Brute force
•Involves Mathematical
Chosen ciphertext trying all attacks
attacks possible •There are several
•This type of private keys approaches, all
attack exploits equivalent in effort
properties of the to factoring the
RSA algorithm product of two
primes
Five
possible
approaches
to
Hardware fault- attacking
based attack RSA are:
Timing attacks
•This involves
inducing hardware •These depend on
faults in the the running time
processor that is of the decryption
generating digital algorithm
signatures
37
 Factoring Problem
• We can identify three approaches to attacking
RSA mathematically:
 Factor n into its two prime factors. This enables
calculation of ø(n) = (p – 1) x (q – 1), which in turn
enables determination of d = e-1 (mod ø(n))

 Determine ø(n) directly without first determining p

and q. Again this enables determination of d = e-1
(mod ø(n))

 Determine d directly without first determining ø(n)

38
 Timing Attack
• Paul Kocher, a cryptographic consultant,
demonstrated that a snooper can determine a
private key by keeping track of how long a
computer takes to decipher messages
• Are applicable not just to RSA but to other
public-key cryptography systems
• Are alarming for two reasons:
 It comes from a completely unexpected
direction
 It is a ciphertext-only attack

39
 Countermeasures

Constant Random delay Blinding

exponentiation •Better performance •Multiply the ciphertext
time could be achieved by by a random number
adding a random delay before performing
•Ensure that all to the exponentiation exponentiation; this
exponentiations take the algorithm to confuse the process prevents the
same amount of time timing attack attacker from knowing
before returning a what ciphertext bits are
result; this is a simple being processed inside
fix but does degrade the computer and
performance therefore prevents the
bit-by-bit analysis
essential to the timing
attack

40
 Fault-Based Attack
• An attack on a processor that is generating RSA
digital signatures
 Induces faults in the signature computation by
reducing the power to the processor
 The faults cause the software to produce invalid
signatures which can then be analyzed by the
attacker to recover the private key

• The attack algorithm involves inducing single-bit

errors and observing the results
• While worthy of consideration, this attack does
not appear to be a serious threat to RSA
 It requires that the attacker have physical access to the
target machine and is able to directly control the input
power to the processor
41
 Chosen Ciphertext
Attack(CCA)
• The adversary chooses a number of ciphertexts and is then given
the corresponding plaintexts, decrypted with the target’s private
key
 Thus the adversary could select a plaintext, encrypt it with the target’s
public key, and then be able to get the plaintext back by having it
decrypted with the private key
 The adversary exploits properties of RSA and selects blocks of data that,
when processed using the target’s private key, yield information needed
for cryptanalysis

 To counter such attacks, RSA Security

Inc. recommends modifying the plaintext
using a procedure known as optimal
asymmetric encryption padding (OAEP)

42
 P

seed M

H(P)

padding

DB

MGF

maskedDB

MGF

maskedseed

EM

P = encoding parameters DB = data block

M = message to be encoded MGF = mask generating function
H = hash function EM = encoded message

Figure 9.9 Encryption Using Optimal Asymmetric Encryption Padding (OAEP)

43
 Summary

• Present an overview of the basic principles of public-

key cryptosystems
• Explain the two distinct uses of public-key
cryptosystems
• List and explain the requirements for a public-key
cryptosystem
• Present an overview of the RSA algorithm
• Understand the timing attack
• Summarize the relevant issues related to the
complexity of algorithms
44