Chapter -3

Public key cryptography

Objectives
 To distinguish between two cryptosystems:
symmetric-key and asymmetric-key
 To introduce trapdoor one-way functions and their
use in asymmetric-key cryptosystems
 To discuss the RSA cryptosystem

 To discuss the ElGamal cryptosystem

To discuss cryptographic hash functions

Introduction
In the symmetric key system:
 Key is shared by both sender and receiver
 if the key is disclosed communications are
compromised
In public key cryptography:
 uses two keys – a public key and a private key
 uses clever application of number theory concepts to
function
 complements rather than replaces private key
cryptography
Continued
 a public-key, which may be known by anybody, and can be
used to encrypt messages, and verify signatures
 a private-key, known only to the recipient, used to decrypt
messages, and sign (create) signatures
 Those who encrypt messages or verify signatures cannot
decrypt messages or create signatures
Continued
 Unlike in symmetric-key cryptography, plaintext and
ciphertext are treated as integers in asymmetric-key
cryptography
 The main idea behind asymmetric-key cryptography is the
concept of the trapdoor one-way function
 computationally infeasible to find decryption key
knowing only algorithm & encryption key
 computationally easy to en/decrypt messages when
the relevant (en/decrypt) key is known
Encryption(f)/Decryption(g)
C = f (Kpublic , P) P = g(Kprivate , C)
 Continued
Example 1
When n is large, n = p × q is a one-way function. Given p
and q , it is always easy to calculate n ; given n, it is very
difficult to compute p and q. This is the factorization
problem.
Example 2
When n is large, the function y = kx mod n is a trapdoor
one-way function. Given x, k, and n, it is easy to calculate
y. Given y, k, and n, it is very difficult to calculate x. This
is the discrete logarithm problem.
Continued
o Public-Key Applications
 Can classify uses into 3 categories :
encryption/decryption (provide secrecy)
digital signatures (provide authentication)
key exchange
o Like private key schemes brute force exhaustive search
attack is always theoretically possible
o but keys used are too large ( grater than 512 bits)
o security relies on a large enough difference in difficulty
between easy (en/decrypt) and hard (cryptanalyse)
problems
RSA cryptosystem
ϗ Stands for Rivest, Shamir & Adleman .
ϗ Proposed arround 1977
ϗ best known & widely used public-key scheme
ϗ based on exponentiation in a finite (Galois) field
over integers modulo a prime. i.e. encryption and
decryption uses exponential modulus
ϗ uses large integers (eg. 1024 bits)
ϗ security due to cost of factoring large numbers
Continued
Encryption, decryption, and key generation in RSA
RSA key setup
ϗ each user generates a public/private key pair by:
selecting two large primes at random p, q
ϗ computing their system modulus n=p.q
 note ø(n)=(p-1)(q-1)
ϗ selecting at random the encryption key e where
1<e<ø(N), gcd(e,ø(N))=1
ϗ solve following equation to find decryption key d
e.d=1 mod ø(n) and 0≤d≤n
ϗ publish their public encryption key: {e,n}
ϗ keep secret private decryption key: {d,p,q}
Encryption using RSA
ϗ To encrypt a message M the sender:
• obtains public key of recipient {e,n}
• computes:C=Me mod n, where 0≤M<n
ϗ To decrypt the ciphertext C the owner:
• uses their private key {d,p,q}
• computes: M=Cd mod n

 Note that the message M must be smaller than the

modulus n
(block if needed)
RSA Example
1. Select primes: p=17 & q=11
2. Compute n = pq =17×11=187
3. Compute ø(n)=(p–1)(q-1)=16×10=160
4. Select e :gcd(e,160)=1; choose e=7
5. Determine d:de=1 mod 160 and d < 160Value
Then d=23 since 23×7=161= 10×160+1
6. Publish public key {7,187}
7. Keep secret private key {23,17,11}
Continued
Encryption and decryption
ϗ given message M = 88 (nb. 88<187)
ϗ Encryption
C = 887 mod 187 = 11
ϗ Decryption
M = 1123 mod 187 = 88
 RSA signature generation and verification
RSA may be used directly as a digital signature scheme
ϗ Choose large primes p and q
ϗ Choose e such that gcd(e, (p-1)(q-1))=1, 1<e<p-1)(q-
1)
ϗ Choose d such that ed=1 mod(p-1)(q-1), 1<d<p-1)(q-
1)
ϗ Then RSA scheme with public key (n, e), (d,p,q)}
ϗ to sign a message M, compute: S = Md(mod pq)
 RSA can be used both for encryption and digital
ϗ to verify a signature, compute: M = Se(mod pq)
signatures, simply by reversing the order in which the
exponents are used: the secret exponent (d) to create the
signature, the public exponent (e) for anyone to verify the
signature. Everything else is identical
RSA signature and verification Example
• Try to communicate with your friend by exchanging
with your signature.
• Use primes p and q with p=5, q=7, n = 35 to send the
message "the first letter of your name over the alphabet
Z26.
• let e = 5; d = 5 b/c ed=1 mod 24 => d = 5.
 Public key: (35,5) Private key: d=5
 Now my name starts at J, which is 9 in Z26.
 Thus signature s=9d=95 mod 35=4
 Your friend has to verify the signature as follows
 message m = s5 mod 35 = 45mod 35= 9
RSA security
• brute force key search (infeasible given size of numbers)
• The security of the RSA cryptosystem is based on the
widely believed difficulty of factoring large numbers
• The RSA challenge, sponsored by RSA Security, offers
cash prizes for the factorization of given large numbers
• In April 2002, prizes ranged from $10,000 (576 bits) to
$200,000
(2048 bits)
• In 1999, a 512-bit number was factored in 4 months using
the following computers:
• 160 175-400 MHz SGI and Sun
• 8 250 MHz SGI Origin
• 120 300-450 MHz Pentium II
• 4 500 MHz Digital/Compaq
• Estimated resources needed to factor a number within one
Elgamal cryptosystem
ϗ Published in 1985 by ElGamal.
ϗ Its security is based on the intractability of the DL
problem.
ϗ Discrete Logarithm Problem - even harder than
factorize.
ϗ Uses randomization, each message has p-1
possible different encryptions.
Elgamal key generation
ϗ Generate a large random prime p such that DLP is
infeasible in Zp and a generator g of the
multiplicative group Zp of the integers modulo p
ϗ Select a random integer x, 1 < x < p-1, and
compute gx
mod p
 Public key is (p, g , y)
 Private key is x
Encryption and Decryption
ϗ If B wants to send secret message m to A then
 B obtains A’s public key (p , g , y)
 B generates random integer k.
 B sends a=gk (mod p) and b = myk (mod p) to A.
 Ciphertext C = (a, b).
ϗ Decryption:
 To decrypt, compute a-x as (a)p-1-x = a-x mod p
 M= a-xb mod p
Elgamal Example:
ϗ Alice choses her public key (17, 6, 7):
 Prime p = 17 , Generator g = 6, Private key part x
= 5,
Public key part gx mod p = 65 mod 17
= 64+1 mod 17
= 64 (6) mod 17
=4(6) mod 17
=7
Bob encrypts his message m = 13:
ϗ He chooses a random k = 10
ϗ He calculates a= gk mod p = 610 mod 17 = 68+2
=(62)4 62 mod 17=24 2 mod 17= 15
ϗ He encrypts b= Myk mod p = (13 ( 710) mod 17
= 13 (72)472 =13 (154) 15=13(16)15 mod 17
 Elgamal Example:
Bob sends a= 15 and b = 9 to Alice.
ϗ Alice receives a = 15 and b = 9 from Bob.
ϗ Her public key is (p, g, gxmodp) = (17,6, 7)
ϗ Her private key is x = 5
Alice now decrypts the message using her private
key:
ϗ Decryption factor
ϗ (a-x) mod p = 15-5 mod 17 = 1511 mod 17 = 9
= 1511 mod 17 =158+2+1mod 17 =(152)4 152 15 mod
17
=44 4(15) mod 17 = 1(4)(15)mod 17 =9
Decryption: b( 9) mod p = (9 * 9) mod 17 = 13
Alice has now decrypted the message and
 ElGamal Signature Algorithm
 Parameters for the key:
ϗ Choose p - large prime number
ϗ Choose g primitive root of p
ϗ Choose x - randomly chosen in the range {2, . . . , p - 2}
ϗ Compute y= gx( mod p)
ϗ Declare: (p, g, y ) is your public
ϗ x is kept secret key
 ElGamal Signature Algorithm
Signature algorithm
 We want to sign message m.
1. Select random k such that gcd(k, p-1 ) = 1.
2. Compute r = gk (mod p).
3. Compute s = k-1 (m - xr)( mod (p-1)).
4. The signature is the pair (r, s) and the signed message is (m, (r, s)).

Verification algorithm
ElGamal Signature Example
 ElGamal Signature Algorithm
 to sign a message M=5
ϗ choose random k=9
ϗ confirm gcd(10,9)=1
ϗ compute: r = gk mod p
= 29 mod 11
=6
ϗ solve: m=sk+xr (mod(p-1)), that is,
5 = 8*6+9*S mod 10; but 9-1 = 9 mod 10; hence S = (5-
8*6)*9-1 =3 mod 10
ϗ signature pair is (r=6, S=3)= (6,3)
ϗ The signed message is (5,(6,3))
 The Diffie-Hellman Algorithm(DH)
ϗ Discovered by Whitfield Diffie and Martin Hellman
ϗ Security of transmission is critical for many network and
Internet applications
DH
ϗ Allows two users to exchange a secret key
ϗ Requires no prior secrets
ϗ Applicable over an untrusted network
ϗ Based on the difficulty of computing discrete logarithms of
large numbers.
ϗ No known successful attack strategies*
ϗ Requires two large numbers, one prime (P), and g, a
primitive root of P
ϗ Requires users to share information in a way that others
can’t decipher the flow of information
 Continued
ϗ P and g are both publicly available numbers
ϗ P is at least 512 bits
ϗ Users pick private values a and b
ϗ Compute public values
ϗ x = ga mod p
ϗ y = gb mod p
ϗ Public values x and y are exchanged
ϗ Compute shared, private key
ϗ Ka= ya mod p
ϗ kb = xb mod p
ϗ Algebraically it can be shown that ka = kb
ϗ Users now have a symmetric secret key to encrypt
 Example
Alice and Bob get public numbers
 P = 23, g = 9
Alice and Bob compute public values
 X = 94 mod 23 = 6561 mod 23 = 6
 Y = 93 mod 23 = 729 mod 23 = 16
 Alice and Bob exchange public numbers
Alice and Bob compute symmetric keys
 ka= ya mod p = 164 mod 23 = 9
 kb = xb mod p = 63 mod 23 = 9
 Alice and Bob now can talk securely!
 DH application
ϗ Diffie-Hellman is currently used in many protocols,
namely:
Secure Sockets Layer (SSL)/Transport Layer Security
(TLS)
Secure Shell (SSH)
Internet Protocol Security (IPSec)
Public Key Infrastructure (PKI)
Message authentication and hash function
ϗ Message authentication is concerned with:
protecting the integrity of a message
validating identity of originator
non-repudiation of origin (dispute resolution)
ϗ Three alternative functions used:
message encryption
message authentication code (MAC)
hash function
 Message Authentication Code (MAC)
ϗ Generated by an algorithm that creates a small fixed-sized block
depending on both message and some key
like encryption though need not be reversible
ϗ Appended to message as a signature
ϗ Receiver performs same computation on message and checks it
matches the MAC
ϗ Provides assurance that message is unaltered and comes from
sender
MAC properties
A MAC is a cryptographic checksum
MAC = CK(M)
condenses a variable-length message M
using a secret key K
to a fixed-sized authenticator
Is a many-to-one function
potentially many messages have same MAC
But finding these needs to be very difficult
 Hash Functions
 condenses arbitrary message to fixed size
 usually assume that the hash function is public and not
keyed
MAC which is keyed
 hash used to detect changes to message
 can use in various ways with message
 most often to create a digital signature
Hash Function Properties
a Hash Function produces a fingerprint of some
file/message/data
h = H(M)
condenses a variable-length message M
to a fixed-sized fingerprint
assumed to be public
Requirements for Hash Functions
1. can be applied to any sized message M
2. produces fixed-length output h
3. is easy to compute h=H(M) for any message M
4. given h is infeasible to find x s.t. H(x)=h
 one-way property
5. given x is infeasible to find y s.t. H(y)=H(x)
 weak collision resistance
6. is infeasible to find any x,y s.t. H(y)=H(x)
 strong collision resistance
Hash Algorithms
see similarities in the evolution of hash functions &
block ciphers
increasing power of brute-force attacks
leading to evolution in algorithms
from DES to AES in block ciphers
from MD4 & MD5 to SHA-1 & RIPEMD-160 in hash
algorithms
likewise tend to use common iterative structure as do
block ciphers
MD5
designed by Ronald Rivest (the R in RSA)
latest in a series of MD2, MD4
produces a 128-bit hash value
until recently was the most widely used hash algorithm
in recent times have both brute-force & cryptanalytic
concerns
specified as Internet standard RFC1321
MD5 Overview
How MD5 works?
1. pad message so its length is 448 mod 512
2. append a 64-bit length value to message
3. initialise 4-word (128-bit) MD buffer (A,B,C,D)
4. process message in 16-word (512-bit) blocks:
 using 4 rounds of 16 bit operations on message block
& buffer
 add output to buffer input to form new buffer value

5. output hash value is the final buffer value

How MD5 works? (con’t…)
Step 1: append padding bits
 The message is padded so that its length in bits is congruent to
448
 mod 512 (length ≡ 448 mod 512)
 Padding is always added (1 to 512 bits)
 The padding pattern is 100…0
Step 2: append length
 A 64-bit length in bits of the original message is appended
 If the original length is greater than 2 64, the length is modulo 264
 The expanded message is L×512 bits: Y0, Y1, …, YL-1
 A total of L×16 32-bit words: M[0...N-1], N = L×16
Step 3: initialize MD buffer
 A 128-bit buffer is used to hold intermediate and final results of the
hash function
How MD5 works? (con’t…)
 The buffer is represented as 4 32-bit registers (A, B, C, D)
initialized to the following integers (hexadecimal values):
A = 67452301
B = EFCDAB89
C = 98BADCFE
D = 10325476
 The values are stored in little-ending order, i.e., the least
significant byte of a word in the low-address byte position:
word A = 01 23 45 67
word B = 89 AB CD EF
word C = FE DC BA 98
word D = 76 54 32 10
 How MD5 works? (con’t…)
Step 4: process message in 512-bit (16-word) blocks
 A compression function HMD5 consists of 4 “rounds” of
processing
Input – 512-bit block Yq and 128-bit buffer value CVq
represented by ABCD
Output – 128-bit chaining variable CVq+1
 For each round operation
Input –Yq and ABCD
Output – updated ABCD
Each round makes use of 1/4 of a 64-element table T[1…64] –
T[i] is the integer part of 232 × abs[sin(i)], where i is in radian
 The output of the last round is added to the input of the first round
(CVq) to produce CVq+1
Step 5: output
MD5 Compression Function
each round has 16 steps of the form:
a = b+((a+g(b,c,d)+X[k]+T[i])<<<s)
a,b,c,d refer to the 4 words of the buffer, but used in
varying permutations
note this updates 1 word only of the buffer
after 16 steps each word is updated 4 times
where g(b,c,d) is a different nonlinear function in each
round (F,G,H,I)
T[i] is a constant value derived from sin
MD5 Compression Function….
Primitive functions F,G,H,I:
 Input – 3 32-bit words
 Output – a 32-bit word
 Each function performs a set of bitwise logical
operations
MD5 Compression Function
 Permutations on the 32-bit words X[0..15] vary from round
to round:
round 1: i
round 2: ρ2(i) = (1 + 5i) mod 16
round 3: ρ3(i) = (5 + 3i) mod 16
round 4: ρ4(i) = 7i mod 16
 Four different circular left shift amounts are used each
round and
different from round to round:
round 1: 7, 12, 17, 22
round 2: 5, 9, 14, 20
round 3: 4, 11, 16, 23
round 4: 6, 10, 15, 21
 Difficult to generate collisions (two blocks produce the
same output)
MD5 Compression Function
Strength of MD5
MD5 hash is dependent on all message bits
Rivest claims security is good as can be
known attacks are:
Berson 92 attacked any 1 round using differential
cryptanalysis (but can’t extend)
Boer & Bosselaers 93 found a pseudo collision (again
unable to extend)
Dobbertin 96 created collisions on MD compression
function (but initial constants prevent exploit)
conclusion is that MD5 looks vulnerable soon
Secure Hash Algorithm (SHA-1)
SHA was designed by NIST & NSA in 1993,
revised 1995 as SHA-1
US standard for use with DSA signature scheme
standard is FIPS 180-1 1995, also Internet
RFC3174
nb. the algorithm is SHA, the standard is SHS
produces 160-bit hash values
now the generally preferred hash algorithm
It has following versions-
SHA-0
 SHA-1
SHA-2
 How SHA-1 works? (con’t…)
1. pad message so its length is 448 mod 512
2. append a 64-bit length value to message
3. initialise 5-word (160-bit) buffer (A,B,C,D,E) to
4. process message in 16-word (512-bit) chunks:
 expand 16 words into 80 words by mixing & shifting
 use 4 rounds of 20 bit operations on message block &
buffer
 add output to input to form new buffer value

5. output hash value is the final buffer value

 How SHA-1 works? (con’t…)
Step 1: append padding bits
 The message is padded so that its length is congruent to 448
mod 512(length ≡ 448 mod 512)
 Padding is always added (1 to 512 bits)
 The padding pattern is 100…0
Step 2: append length
 A 64-bit length in bits of the original message is appended
Step 3: initialize MD buffer
 A 160-bit buffer is used to hold intermediate and final results
of the hash function
 How SHA-1 works? (con’t…)
 The buffer is represented as 5 32-bit registers (A, B, C, D, E)
initialized to the following integers (hexadecimal values):
A = 67452301
B = EFCDAB89
C = 98BADCFE
D = 10325476
E = C3D2E1F0
 The values are stored in big-ending order, i.e., the most
significant
byte of a word in the low-address byte position:
word A = 67 45 23 01
word B = EF CD AB 89
word C = 98 BA DC FE
word D = 10 32 54 76
word E = C3 D2 E1 F0
 How SHA-1 works? (con’t…)
Step 4: process message in 512-bit (16-word) blocks
 A compression function with 4 rounds of processing
of 20 steps each
 For each round operation
Input – 512-bit block Yq, 160-bit buffer value CVq
represented by ABCDE
Output – 160-bit chaining variable CVq+1 (updated
ABCDE)
Makes use of additive constant Kt where 0 ≤ t ≤ 79
 The output of the last round is added to the input of
the first round (CVq) to produce CVq+1
Step 5: output
 The output from the L-th stage is the 160-bit message
How SHA-1 works? (con’t…)
SHA-1 Compression Function
each round has 20 steps which replaces the 5 buffer
words thus:
(A,B,C,D,E) <-(E+f(t,B,C,D)+(A<<5)+Wt+Kt),A,
(B<<30),C,D)
a,b,c,d refer to the 4 words of the buffer
t is the step number
f(t,B,C,D) is nonlinear function for round
W
t is derived from the message block
K is a constant value derived from sin
t
 SHA-1 Compression Function…
Primitive functions f(t,B,C,D):
 Input – 3 32-bit words
 Output – a 32-bit word
 Each function performs a set of bitwise logical
operations
SHA-1 Compression Function….
Derivation of the 32-bit word Wt from the 512-bit
input block
 The first 16 values of W t are taken directly from the 16
words of the current block
 The remaining values are defined as follows:
Wt = S1(Wt-16 ⊕ Wt-14 ⊕ Wt-8 ⊕ Wt-3)
 Difficult to generate collisions
SHA-1 Compression Function…
SHA-1 verses MD5
brute force attack is harder (160 vs 128 bits for MD5)
not vulnerable to any known attacks (compared to
MD4/5)
a little slower than MD5 (80 vs 64 steps)
both designed as simple and compact
optimised for big endian CPU's (vs MD5 which is
optimised for little endian CPU’s)
Revised Secure Hash Standard
NIST issued revision FIPS 180-2 in 2002
adds 3 additional versions of SHA
SHA-256, SHA-384, SHA-512
designed for compatibility with increased security
provided by the AES cipher
structure & detail is similar to SHA-1
hence analysis should be similar
but security levels are rather higher
 SHA-512
Step 1: Append padding bits
Step 2: Append length
Step 3: Initialize hash buffer
Step 4: Process the message in 1024-bit (128-word)
blocks, which forms the heart of the algorithm
Step 5: Output the final state value as the resulting
hash

60 Dr. Monther Aldwairi 11/8/2009

SHA-512 Overview
SHA-512 Compression Function
heart of the algorithm
processing message in 1024-bit blocks
consists of 80 rounds
updating a 512-bit buffer
using a 64-bit value Wt derived from the current
message block
and a round constant based on cube root of first 80 prime
numbers
63 11/8/2009
SHA-512 Round Function
 Function Elements
Ch(e,f,g) = (e AND f) XOR (NOT e AND g)
Maj(a,b,c) = (a AND b) XOR (a AND c) XOR (b
AND c)
∑(a) = ROTR(a,28) XOR ROTR(a,34) XOR
ROTR(a,39)
∑(e) = ROTR(e,14) XOR ROTR(e,18) XOR
ROTR(e,41)
+ = addition modulo 2^64
Kt = a 64-bit additive constant
Wt = a 64-bit word derived from the current 512-bit input
block.
65 11/8/2009
SHA-512 Round Function
 ! !!!
ou !
k y
h a n
T