MODULE - 2

Pseudorandom number Generators: Linear Congruential Generators,

Blum Blum Shub Generator
Public key cryptography and RSA: Principles of public key
cryptosystems-Public key cryptosystems, Applications for public
key cryptosystems, Requirements for public key cryptography,
Public key Cryptanalysis, The RSA algorithm: Description of the
Algorithm, Computational aspects, The Security of RSA
Diffie-Hellman key exchange: The Algorithm, Key exchange
Protocols, Man-in-the-middle Attack, Elliptic Curve Cryptography:
Analog of Diffie-Hellman key Exchange, Elliptic Curve
Encryption/Decryption, Security of Elliptic Curve Cryptography
Pseudorandom Numbers
 Cryptographic applications typically make use of algorithmic
techniques for random number generation
 These algorithms are deterministic and therefore produce
sequences of numbers that are not statistically random
 If the algorithm is good, the resulting sequences will pass
many tests of randomness and are referred to as pseudorandom
numbers
 Source of Context-
true specific
randomness Seed Seed values

Conversion Deterministic Deterministic

to binary algorithm algorithm

Random Pseudorandom Pseudorandom

bit stream bit stream value

(a) TRNG (b) PRNG (c) PRF

TRNG = true random number generator

PRNG = pseudorandom number generator
PRF = pseudorandom function

Figure 8.1 Random and Pseudorandom Number Generators

Pseudorandom number Generators: Linear
Congruential Generators
 An algorithm first proposed by Lehmer that is parameterized with four numbers:
m the modulus m>0
a the multiplier 0 < a< m
c the increment 0≤ c < m
X0 the starting value, or seed 0 ≤ X0 < m

 The sequence of random numbers {Xn} is obtained via the following iterative
equation:
Xn+1 = (aXn + c) mod m
 If m , a , c , and X0 are integers, then this technique will produce a sequence of
integers with each integer in the range 0 ≤ Xn < m
 The selection of values for a , c , and m is critical in developing a good random
number generator
Blum Blum Shub (BBS) Generator
 Has perhaps the strongest public proof of its cryptographic strength of
any purpose-built algorithm
 Referred to as a cryptographically secure pseudorandom bit generator
(CSPRBG)
A CSPRBG is defined as one that passes the next-bit-test if there is
not a polynomial-time algorithm that, on input of the first k bits of an
output sequence, can predict the (k + 1)st bit with probability
significantly greater than 1/2
 The security of BBS is based on the difficulty of factoring n
 Initialize
with seed s

Generate
x2 mod n

Select least
significant bit

[0, 1]

Figure 8.3 Blum Blum Shub Block Diagram

 Table 8.1 Example Operation of BBS Generator

i Xi Bi i Xi Bi
0 20749 11 137922 0
1 143135 1 12 123175 1
2 177671 1 13 8630 0
3 97048 0 14 114386 0
4 89992 0 15 14863 1
5 174051 1 16 133015 1
6 80649 1 17 106065 1
7 45663 1 18 45870 0
8 69442 0 19 137171 1
9 186894 0 20 48060 0
10 177046 0
 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.
Principles of Public-Key Cryptosystems
Public-Key Cryptosystems
 A public-key encryption scheme has six ingredients:

Encryption Decryption
Plaintext Public key Private key Ciphertext
algorithm algorithm

The Accepts the

readable ciphertext
Performs The
message Used for Used for and the
various scrambled
or data encryption encryption matching
transforma- message
that is fed or or produced key and
tions on the
into the decryption decryption as output produces the
plaintext
algorithm original
as input plaintext
Public-Key Cryptosystems

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

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

Public-Key Cryptosystems
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

Figure 9.1 Public-Key Cryptography

CONVENTIONAL AND PUBLIC-KEY ENCRYPTION
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

Public-Key Cryptosystem: Authentication
Public-Key Cryptosystem: Authentication and
Secrecy
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
 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
 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
 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
 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
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
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
 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}
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
RSA Algorithm
 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

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 (216 + 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
Efficient Operation Using the Private 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
Key Generation
The Security of RSA
Diffie-Hellman Key Exchange
 First published public-key algorithm
 A number of commercial products employ this key exchange
technique
 Purpose is to enable two users to securely exchange a key that can
then be used for subsequent symmetric encryption of messages
 The algorithm itself is limited to the exchange of secret values
 Its effectiveness depends on the difficulty of computing discrete
logarithms
The Algorithm

Alice Bob
Alice and Bob share a Alice and Bob share a
prime q and a, such that prime q and a, such that
a < q and a is a primitive a < q and a is a primitive
root of q root of q

Alice generates a private Bob generates a private

key XA such that XA < q key XB such that XB < q

Alice calculates a public Bob calculates a public

key YA = aXA mod q YA YB key YB = aXB mod q

Alice receives Bob’s Bob receives Alice’s

public key YB in plaintext public key YA in plaintext

Alice calculates shared Bob calculates shared

secret key K = (YB)XA mod q secret key K = (YA)XB mod q
Key Exchange Protocols
 Simple Diffie–Hellman Protocol:
 User A generates a private value 𝑋𝐴 ,computes public value 𝑌𝐴 ,and
sends it to User B.
 User B does the same with private value 𝑋𝐵 and public value 𝑌𝐵 .
 Both can then compute the same shared secret key.
 Public parameters 𝑞 and 𝑎 must be known beforehand (or chosen
by A in the first message).
Man-in-the-middle Attack

Alice Darth Bob

Private key XA
public key
YA = aXA mod q

YA

Private keys XD1, XD2

public keys
YD1 = aXD1 mod q
YD2 = aXD2 mod q
YD2 YD1

Secret key Secret key Private key XB

K2 = (YD2)XA mod q K2 = (YA)XD2 mod q public key
YB = aXB mod q

YB

Secret key Secret key

K1 = (YB)XD1 mod q K1 = (YD1)XB mod q

Alice and Darth Bob and Darth

share K2 share K1
Man-in-the-middle Attack
 Man-in-the-Middle Attack on Diffie–Hellman
 Setup: Alice Bob want a shared key; Darth (attacker) intercepts.
 Attack Steps:
 Darth generates two private keys (𝑋𝐷1 , 𝑋𝐷2 )and corresponding public keys.
 Replaces Alice’s public value with 𝑌𝐷1 (to Bob) and Bob’s public value with 𝑌𝐷2 (to
Alice).
 Result: Alice shares K2 with Darth, Bob shares K1 with Darth.
 Impact:
 All future encrypted messages pass through Darth.
 Darth can read (decrypt with one key) and modify/forward (encrypt with the other
key).
 Reason: Protocol lacks authentication.
 Solution: Use digital signatures and public-key certificates to verify participants.
Elliptic Curve Cryptography

 Addition operation in ECC is the counterpart of modular

multiplication in RSA
 Multiple addition is the counterpart of modular exponentiation
Analog of Diffie–Hellman Key Exchange
 Elliptic Curve Key Exchange (ECC-DH
 Choose large integer 𝑞(prime 𝑝or 2𝑚 )and elliptic curve parameters 𝑎 𝑏 .
 Define elliptic group 𝐸𝑞 𝑎 𝑏 .
 Select base point 𝐺with large order 𝑛.
 Public parameters: 𝑞 𝑎 𝑏 𝐺 𝑛 .
 Key Exchange:
 A picks private key 𝑛𝐴 ,computes public key 𝑃𝐴 = 𝑛𝐴 𝐺.
 B picks private key 𝑛𝐵 ,computes public key 𝑃𝐵 = 𝑛𝐵 𝐺.
 Shared secret:
 𝑘 = 𝑛𝐴 𝑃𝐵 = 𝑛𝐵 𝑃𝐴 = 𝑛𝐴 𝑛𝐵 𝐺.
 Example:
 𝑝 = 211, 𝐸𝑝 0 −4 , 𝐺 = 2 2 , 240𝐺 = 𝑂.
 A: 𝑛𝐴 = 121 ⇒ 𝑃𝐴 = 115 48 .
 B: 𝑛𝐵 = 203 ⇒ 𝑃𝐵 = 130 203 .
 Shared key: 161 69 .
 Use x-coordinate (161) as session key for symmetric encryption.
Elliptic Curve Encryption/Decryption
Global Public Elements

Eq(a, b) elliptic curve with parameters a, b, and q, where q is a prime

or an integer of the form 2m

G point on elliptic curve whose order is large value n

User A Key Generation

Select private nA nA < n

Calculate public PA P A = nA ´ G

User B Key Generation

Select private nB nB < n

Calculate public PB P B = nB ´ G

Calculation of Secret Key by User A

K = nA ´ PB

Calculation of Secret Key by User B

K = nB ´ PA
Encryption and Decryption:
Security of Elliptic Curve Cryptography
 Depends on the difficulty of the elliptic curve logarithm problem
 Fastest known technique is “Pollard rho method”
 Compared to factoring, can use much smaller key sizes than with
RSA
 For equivalent key lengths computations are roughly equivalent
 Hence, for similar security ECC offers significant computational
advantages
Comparable Key Sizes in Terms of Computational
Effort for Cryptanalysis (NIST SP-800-57)
Symmetric key Diffie-Hellman, RSA ECC
algorithms Digital Signature (size of n in bits) (modulus size in
Algorithm bits)
80 L = 1024 1024 160–223
N = 160
112 L = 2048 2048 224–255
N = 224
128 L = 3072 3072 256–383
N = 256
192 L = 7680 7680 384–511
N = 384
256 L = 15,360 15,360 512+
N = 512

Note: L = size of public key, N = size of private key