Cryptography and Network

Security
Chapter 10

Fifth Edition
by William Stallings

Lecture slides by Lawrie Brown

 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
 Diffie-Hellman Key Exchange
• a public-key distribution scheme
– cannot be used to exchange an arbitrary message
– rather it can establish a common key
– known only to the two participants
• value of key depends on the participants (and their
private and public key information)
• based on exponentiation in a finite (Galois) field
(modulo a prime or a polynomial) - easy
• security relies on the difficulty of computing discrete
logarithms (similar to factoring) – hard
Background for Primitive Roots
 For a prime integer q, the number α will be a
primitive root of q if for every positive integer
X
number X < q the computation {Y = α mod q} will
yield a different value for each value of x.
 This ensures that for any secret key XA there will
be a different public key YA.
 Example: let q=5 and α=3, then for all values of
X<5 we have different values of Y. {You can do the
above computations to get a practical proof}
 Diffie-Hellman Setup
• all users agree on global parameters:
– large prime integer or polynomial q
– α being a primitive root mod q
• each user (eg. A) generates their key
– chooses a secret key (number): xA < q
xA
– compute their public key: yA = α mod q
• each user makes public that key yA
 Diffie-Hellman Key Exchange
• shared session key for users A & B is KAB:
xA.xB
KAB = α mod q
xB
= 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
• attacker needs an x, must solve discrete log
 Diffie-Hellman Example
• users Alice & Bob who wish to swap keys:
• agree on prime q=353 and α =3
• select random secret keys:
– A chooses xA=97, B chooses xB=233
• compute respective public keys:
– yA=397 mod 353 = 40 (Alice)
– yB=3233 mod 353 = 248 (Bob)
• compute shared session key as:
– KAB= yBxA mod 353 = 24897 = 160 (Alice)
– KAB= yAxB mod 353 = 40233 = 160 (Bob)
 Key Exchange Protocols
• Users could create random private/public Diffie-
Hellman keys each time they communicate
• Users could create a known private/public
Diffie-Hellman key and publish in a directory,
then consulted and used to securely
communicate with them
• Vulnerable to Man-in-the-Middle-Attack
• Authentication of the keys is needed
 Security of Diffie-Hellman

Discrete Logarithm Attack

Man-in-the-Middle Attack

15.14
 Man-in-the-Middle Attack
1. Darth prepares by creating two private / public keys
2. Alice transmits her public key to Bob
3. Darth intercepts this and transmits his first public key to Bob.
Darth also calculates a shared key with Alice
4. Bob receives the public key and calculates the shared key (with
Darth instead of Alice)
5. Bob transmits his public key to Alice
6. Darth intercepts this and transmits his second public key to
Alice. Darth calculates a shared key with Bob
7. Alice receives the key and calculates the shared key (with Darth
instead of Bob)
 Darth can then intercept, decrypt, re-encrypt, forward all
messages between Alice & Bob
 ElGamal Cryptography
• public-key cryptosystem related to D-H
• so uses exponentiation in a finite (Galois)
• with security based difficulty of computing
discrete logarithms, as in D-H
• each user (eg. A) generates their key
– chooses a secret key (number): 1 < xA < q
xA
– compute their public key: yA = a mod q
 ElGamal Message Exchange
Public Key of Alice = YA , Private Key of Alice = XA

• Bob encrypt a message to send to A computing

– represent message M in range 0 <= M <= q-1
• longer messages must be sent as blocks
– chose random integer k with 1 <= k <= q-1
– compute one-time key K = yAk mod q
– encrypt M as a pair of integers (C1,C2) where
• C1 =α k mod q ; C2 = KM mod q
• A then recovers message by
– recovering key K as K = C1XA mod q
– computing M as M = C2 K-1 mod q
• a unique k must be used each time
– otherwise result is insecure
 ElGamal Example
• use field GF(19) q=19 and α =10
• Alice computes her key:
– A chooses xA=5 & computes yA=105 mod 19 = 3
• Bob send message m=17 as (11,5) by
– choosing random k=6
– computing K = yAk mod q = 36 mod 19 = 7
– computing C1 = α k mod q = 106 mod 19 = 11;
C2 = KM mod q = 7.17 mod 19 = 5
• Alice recovers original message by computing:
– recover K = C1xA mod q = 115 mod 19 = 7
– compute inverse K-1 = 7-1 = 11
– recover M = C2 K-1 mod q = 5.11 mod 19 = 17
 Elliptic Curve Cryptography
• majority of public-key crypto (RSA, D-H) use
either integer or polynomial arithmetic with
very large numbers/polynomials
• imposes a significant load in storing and
processing keys and messages
• an alternative is to use elliptic curves
• offers same security with smaller bit sizes
• newer, but not as well analysed
 ECC Security
• relies on elliptic curve logarithm problem
• fastest method is “Pollard rho method”
• compared to factoring, can use much smaller
key sizes than with RSA etc
• for equivalent key lengths computations are
roughly equivalent
• hence for similar security ECC offers significant
computational advantages
Comparable Key Sizes for Equivalent Security

Symmetric ECC-based RSA/DSA

scheme scheme (modulus size in
(key size in bits) (size of n in bits) bits)

56 112 512
80 160 1024
112 224 2048
128 256 3072
192 384 7680
256 512 15360
 Pseudorandom Number
Generation (PRNG) based on
Asymmetric Ciphers
 asymmetric encryption algorithm produce
apparently random output
 hence can be used to build a pseudorandom
number generator (PRNG)
 much slower than symmetric algorithms
 hence only use to generate a short
pseudorandom bit sequence (eg. key)
 Micali-Schnorr PRNG using RSA
 in ANSI X9.82 and ISO 18031
 Zi = k least significant bits of encrypted value at ith step
 Generation of Pseudo Random Numbers Using RSA

For a sufficient key length, the RSA algorithm is

considered secure and is a good candidate to form
the basis of a PRNG. Such a PRNG, known as the
Micali-Schnorr PRNG is recommended in the ANSI
standard X9.82 (Random Number Generation) and in
the ISO standard 18031 (Random Bit Generation).

The PRNG is illustrated in Stallings Figure 10.8.

This PRNG has much the same structure as the

output feedback (OFB) mode used as a PRNG but
using RSA instead of a block cipher. We can define
the PRNG as follows:
SETUP Select parameters per normal RSA key setup, with r + k =bitlength of n
SEED Select a random seed x of bitlength the same as n

GENERATE a pseudorandom sequence of length k x m using the loop:

for i from 1 to m do the following:

yi = xei-1 mod n
xi = r most significant bits of yi
zi = k least significant bits of yi

OUTPUT The output sequence is z1 || z2 || … || zm

The parameters n, r, e, and k are selected to satisfy the six conditions detailed in
the text. There is clearly a tradeoff between r and k. Because RSA is
computationally intensive, we would like to generate as many pseudorandom
bits per iteration as possible, and therefore would like a large value of k.
However, for cryptographic strength, we would like r to be as large as possible.
 Summary
• have considered:
– Diffie-Hellman key exchange
– ElGamal cryptography
– Elliptic Curve cryptography
– Pseudorandom Number Generation (PRNG) based
on Asymmetric Ciphers (RSA & ECC)