CHAPTER three

Fundaments of
Cryptography

1
 Cryptography
• Cryptography is the process of hiding or coding
information so that only the person a message
was intended for can read it.

• The art of cryptography has been used to code

messages for thousands of years and continues
to be used in bank cards, computer passwords,
and ecommerce.

2
 Cryptography…

• Steganography is good examples of ancient

cryptography.
• The word steganography, with origin in Greek,
means “covered writing,” in contrast with
cryptography, which means “secret writing.”
• Cryptography means concealing the contents of
a message by enciphering;
• steganography means concealing the message
itself by covering it with something else. 3
 Services Provided by Cryptography
• Confidentiality
– provides privacy for messages and stored data by hiding
• Message Integrity
– provides assurance to all parties that a message remains
unchanged
• Non-repudiation
– Prevent ability to deny that an activity on the network
occurred
• Authentication
– identifies the origin of a message
– verifies the identity of person using a computer system
• Secure Channels
– Encryption can be used to create secure channels over
private or public networks 4
 Cryptography
• Cryptography has five components:
- Plaintext: This is what you want to encrypt.
- Ciphertext: The encrypted output.
- Enciphering or encryption: The process by which
plaintext is converted into ciphertext.
- Encryption algorithm: The sequence of data processing
steps that go into transforming plaintext into ciphertext.
- Secret Key: is used to set some or all of the various
parameters used by the encryption algorithm.
- Deciphering or decryption: Recovering plaintext
from ciphertext.
- Decryption algorithm: The sequence of data processing
steps that go into transforming ciphertext back into
plaintext. 5
 Keys
• A key can be thought of as 010100111
simply a collection of bits 0
• The more bits, the stronger 101111011
the key 101100101
• Keys are tied to specific
encryption algorithms
• Lengths vary depending on
the encryption algorithm
– e.g. 128 bits is long for
some algorithms, but
short for others

6
 Cryptography
• Encryption Overview
– Plain text is converted to cipher text by use of
an algorithm and key.
• Algorithm is publicly known
• Key is held private
– Three Main Categories
• Secret Key
– single key is used to encrypt and decrypt information
• Public/Private Key
– two keys are used: one for encryption (public key) and
one for decryption (private key)
• One-way Function
– information is encrypted to produce a “digest” of the
original information that can be used later to prove its 7
authenticity
 Encryption
• Encryption is the process
of taking some data and a
key and feeding it into a
function and getting
encrypted data out
Encryption
• Encrypted data is, in Function
principle, unreadable
unless decrypted

8
 Decryption
• Decryption is the
process of taking
encrypted data and a
key and feeding it into
a function and getting
out the original data
– Encryption and
decryption functions are Decryption
linked Function

9
 Encryption Techniques
Symmetric Encryption
• Encryption and decryption
algorithms that use the same
key are called symmetric
– In this case everyone wanting Encrypt
to read encrypted data must
share the same key
• Sender and receive have the
same secret key that will
encrypt and decrypt plain
text.
• Strength of encryption Decrypt
technique depends on key
length
10
 Encryption Techniques…

• Secret Key (Symmetric)

– Known symmetrical algorithms
• Data Encryption Standard (DES)
– 56 bit key
• Triple DES, DESX, GDES, RDES
– 168 bit key
• RC2, RC4, RC5
– variable length up to 2048 bits
• IDEA - basis of PGP
– 128 bit key
• Blowfish
– variable length up to 448 bits

11
 Encryption Techniques…
Asymmetric Encryption
• Encryption and decryption
algorithms that use a key
pair are called asymmetric
– Keys are mathematically
linked
• Most common algorithm is
the RSA (Rivest Shamir
Adelman) algorithm with
key lengths from 512 to
1024 bits.

12
 ENCRYPTION DECRYPTION

Message 1 Encrypted Message 1

Central to the growth of e-commerce and e- 9a46894335be49f0b9cab28d755aaa9cd98571b
governance is the issue of trust in electronic 275bbb0adb405e6931e856ca3e5e569edd13528
environment. 5482

Encrypted Message 1 Message 1

9a46894335be49f0b9cab28d755aaa9cd985 Central to the growth of e-commerce and e-
71b275bbb0adb405e6931e856ca3e5e569e governance is the issue of trust in electronic
dd135285482 environment.

Same Key
Message 2 SYMMETRIC
The Internet knows no geographical boundaries. Encrypted Message 2
It has redefined time and space. Advances in a520eecb61a770f947ca856cd675463f1c95a9a2b
computer and telecommunication technologies 8d4e6a71f80830c87f5715f5f59334978dd7e97da
have led to the explosive growth of the Internet. 0707b48a1138d77ced56feba2b467c398683c7db
This in turn is affecting the methods of eb86b854f120606a7ae1ed934f5703672adab0d7
communication, work, study, education, be66dccde1a763c736cb9001d0731d541106f50b
interaction, leisure, health, governance, trade b7e54240c40ba780b7a553bea570b99c9ab3df13
and commerce. d75f8ccfdddeaaf3a749fd1411
Encrypted Message 2 Message 2
a520eecb61a770f947ca856cd675463f1c95a The Internet knows no geographical boundaries. It has
9a2b8d4e6a71f80830c87f5715f5f59334978 redefined time and space. Advances in computer and
dd7e97da0707b48a1138d77ced56feba2b46 telecommunication technologies have led to the
7c398683c7dbeb86b854f120606a7ae1ed93 explosive growth of the Internet. This in turn is
Different Keys
4f5703672adab0d7be66dccde1a763c736cb affecting the methods of communication, work, study,
9001d0731d541106f50bb7e54240c40ba780 education, interaction, leisure, health, governance,
[Keys of a pair – Public and Private]
b7a553bea570b99c9ab3df13d75f8ccfdddea trade and commerce.
af3a749fd1411 ASYMMETRIC
[PKI]
 Encryption Techniques…
• One-Way Function
– non-reversible “quick” encryption
– produces a fixed length value called a
hash or message digest
– used to authenticate contents of a
message
– Common message digest functions
• MD4 and MD5
– produces 128 bit hashes
• SHA
– produces 160 bit hashes

14
 Building Blocks of Encryption
Techniques
• Two building blocks of all classical encryption
techniques are
substitution and transposition.

• Substitution means replacing an element of the

plaintext with an element of ciphertext.
– each element in the plaintext (bit, letter, group of bits or
letters) is mapped into another element

• Transposition means rearranging the order of

appearance of the elements of the plaintext.

• Transposition is also referred to as permutation. 15

 Cryptography...
Description
• A sender S wants to transmit message M to a
receiver R.
• To protect the message M, the sender first
encrypts it into an intelligible message M’.
• After receipt of M’, R decrypts the message to
obtain M.
• M is called the plaintext
 What we want to encrypt

• M’

is called the ciphertext
The encrypted output
16
 Cryptography...
• Mathematical Notation
 Given
P=Plaintext

C=Ciphertext

 C = E (P) Encryption
K

 P = D (C) Decryption
K

17
 Cryptanalytic Attacks
• Types of attacks
- An attacker having only the ciphertext and his goal
is to find the corresponding plaintext.
- An attacker having a ciphertext and the
corresponding plaintext and his goal is to find the
key.

• A good cryptosystem protects against all types

of attacks.

• Attackers use both Mathematics and Statistics.

18
 Cryptanalytic Attack…
• Intruders
• Eavesdropping (listening/spying the message)
 An intruder may try to read the message
 If it is well encrypted, the intruder will not know the
content
 However, just the fact the intruder knows that there is
communication may be a threat (Traffic analysis)

• Modification
 Modifying a plaintext is easy, but modifying encrypted
messages is more difficult

• Insertion of messages
 Inserting new message into a ciphertext is difficult
19
 Cryptography example:
Caesar cipher
• This is the earliest known example of a
substitution cipher.
• Each character of a message is replaced by a
character three position down in the alphabet.

• Shift of letters:
Plain: ABCDEFGHIJKLMNOPQRSTUVWXYZ
Cipher: DEFGHIJKLMNOPQRSTUVWXYZABC

Example
plaintext: are you ready

20
 Cryptography example:
Caesar cipher
Example: Encipher the message
THIS MESSAGE IS TOP SECRET
• using the ordinary alphabet and a Caesar cipher with a shift
of 3.
• When each letter is converted to a number, and we group
into blocks of length 5, we get

19 7 8 18 12 4 18 18 0 6 4 8 18 19 14 15 18 4 2 17 4 19

• Here, we group the items in blocks for readability. After

applying the enciphering transformation, each number
becomes
22 10 11 21 15 7 21 21 3 9 7 11 21 22 17 18 21 7 5 20 7 22
• and the ciphertext message is sent as
WKLVP HVVDI HLVWR SVHFU HW 21
 Cryptography example:
Caesar cipher
• If we represent each letter of the alphabet by an integer
that corresponds to its position in the alphabet, the
formula for replacing each character ’P’ of the plaintext
with a character ’C’ of the ciphertext can be expressed as
C = E( 3, P) = (P + 3) mod 26
• A more general version of this cipher that allows for any
degree of shift would be expressed by
C = E( k, P) = (P + k) mod 26
• The formula for decryption would be
P = D( k, C ) = (C - k) mod 26
• In these formulas, ’k’ would be the secret key.
• The symbols ’E’ and ’D’ represent encryption and 22
decryption.
 Playfair cipher
• The Playfair cipher was the first practical
digraph substitution cipher.

• It was invented by Charles Wheatstone in

1854

• In playfair cipher we encrypt a pair of

alphabets(digraphs) instead of a single
alphabet. 23
 How the Playfair Cipher Works

 Constructing the 5×5

Key Square
• Choose a keyword
(e.g., “security").
• Fill the 5×5 grid with the
letters of the keyword
(without repetition).
• Fill the remaining spaces
with the rest of the
alphabet (excluding "J",
which is combined with
"I").
24
 Playfair Encryption Process
 There are mainly three criterias for encrypting
letters within the same pair.
• Break the plaintext into letter pairs (digraphs).
 If two successive letters in a digraph are identical,
an X is inserted between them and If there is an odd
number of letters, a Z is added to the last letter.
• If the two letters in the pair are in the same row of
the key square, we replace them with the letter to
their right.
• If both letters in the pair are found in the same
column of the key square, we will replace each
letter with the letter below it.
• If the letters are in different rows and columns, we
form a rectangle with them and change each letter
with the letter in the opposite corner. 25
 Ciphering with Transposition

• In transposition ciphering:

– You write your plaintext message along the

rows of a matrix of some size.

– You generate ciphertext by reading along the

columns.

– The order in which you read the columns is

determined by the encryption key.
26
 Ciphering with Transposition…

Key: 4 1 3 6 2 5

Plaintext: m e e t m e
a t s q u a
r e g u a r
d e n f o r
g o o d d i
n n e r o k

Ciphertext:

The cipher can be made more secure by performing

multiple 27
rounds of such permutations.
 Block vs Stream Ciphers

• Block ciphers process messages into

blocks, each of which is then en/decrypted

• Stream ciphers process messages a bit or

byte at a time when en/decrypting

• many current ciphers are block ciphers

28
 Substitution-Permutation Ciphers

• In his 1949 paper, Shannon

introduced the idea of substitution-
permutation (S-P) networks, which
now form the basis of modern block
ciphers.

• an S-P network is the modern form of

a substitution-transposition product
cipher.
29
Substitution-Permutation Ciphers…
• Substitution Operation

– a binary word is replaced by some other binary word

– the whole substitution function forms the key

– will call them S-Boxes

• Permutation Operation

– a binary word has its bits reordered (permuted)

– the re-ordering forms the key

– will call these P-Boxes

30
 Data Encryption Standard (DES)

• most widely used block cipher in world

• adopted in 1977 by NBS (now NIST)

– NBS - National Bureau of Standards

– NIST - National Institute of Standards and Technology

• encrypts 64-bit data using 56-bit key

• has widespread use

31
 Symmetric DES…

• The basic process in enciphering a 64-bit data

block using the DES consists of:

– an initial permutation (IP)

– 16 rounds of a complex key dependent

calculation of f

– a final permutation, being the inverse of IP

32
 Symmetric DES...
• DES Utilizes block cipher.
- During the encryption process, the plaintext is divided into
fixed length blocks of 64 bits.

• The key is 56 bits wide.

• DES algorithm involves carrying out combinations of

substitutions and permutations between the text to be
encrypted and the key,
• while making sure the operations can be performed in
both directions (for decryption).

• The combination of substitutions and permutations is

called a product cipher.

33
Symmetric DES...

34
 Symmetric DES...
• DES Encryption starts with an initial permutation (IP) of
the 64 input bits.

• These bits are then divided into two 32-bit halves

called L and R.

• The encryption then proceeds through 16 rounds, each

using the L and R parts, and a roundkey.

• The R and roundkeys are processed in the so called f-

function, and exclusive-or of the output of the f-
function with the existing L part to create the new R
part.

• The new L part is simply a copy of the incoming R part.

35
 Symmetric DES...
• In the final round, the L and R parts are swapped
once more before the final permutation (FP)
producing the output block.

• Decryption is identical to encryption, except that

the subkeys are used in the opposite order.

• That is, roundkey 16 is used in round 1, roundkey

15 is used in round 2, etc., ending with roundkey 1
being used in round 16.
36
 Symmetric DES...
• The f-function mixes the bits of the R portion using
the roundkey for the current round.

• First the 32-bit R value is expanded to 48 bits using

a permutation E. That value is then exclusive-or'ed
with the roundkey.

• The 48 bits are then divided into eight 6-bit

chunks, each of which is fed into an S-Box that
mixes the bits and produces a 4-bit output.

• Those 4-bit outputs are combined into a 32-bit

value, and permuted once again to produce the f-
function output.

37
 Symmetric DES...
One Round of Processing in DES
• The algorithmic implementation of DES is known
as DEA for Data Encryption Algorithm.

• The 32-bit right half of the 64-bit input data

block is expanded by into a 48-bit block.

• This is referred to as the expansion permutation

step, or the E-step.

38
 Symmetric DES...
One Round of Processing in DEA
• The E-step involves the following:
– First divide the 32-bit block into eight 4-bit words
– attach an additional bit on the left to each 4-bit
word that is the last bit of the previous 4-bit word
– attach an additional bit to the right of each 4-bit
word that is the beginning bit of the next 4-bit
word.
• The 56-bit key is divided into two halves,
– each half shifted separately, and the combined
56-bit key permuted/contracted to yield a 48-bit
round key.
39
 Symmetric DES...
One Round of Processing in DEA
• The 48 bits of the expanded output produced by the
E-step are XORed with the round key.
– This is referred to as key mixing.

• The output produced by the previous step is broken

into eight six-bit words.
• Each six-bit word goes through a substitution step.
– its replacement is a 4-bit word.

• The substitution is carried out with an S-box.

• So after all the substitutions, we again end up with
a 32-bit word.
40
 Symmetric DES...
One Round of Processing in DEA

NOTE
• The goal of the substitution step implemented by the S-
box is to introduce diffusion in the generation of the
output from the input.
– Diffusion means that each plaintext bit must affect as many
ciphertext bits as possible.
• The strategy used for creating the different round keys
from the main key is meant to introduce confusion into
the encryption process.
– Confusion in this context means that the relationship
between the encryption key and the ciphertext must be as
complex as possible.

• Diffusion and confusion are the two cornerstones of block

41
cipher design.
 Symmetric DES...
• DES algorithm

42
 Symmetric DES
The S-Box for the Substitution Step in Each
Round
• The 48-bit input word is divided into eight 6-bit
words and each 6-bit word fed into a separate S-
box.

• Each S-box produces a 4-bit output. Therefore, the

8 S-boxes together generate a 32-bit output.

• The overall substitution step takes the 48-bit input

back to a 32-bit output.

43
 Symmetric DES
The S-Box for the Substitution Step in Each Round

44
 Symmetric DES
The S-Box for the Substitution Step in Each Round
The S-Box

45
 The S-Box for the Substitution Step in Each Round

• If S1 is the function defined in this table and B is a

block of 6 bits, then S1(B) is determined as follows:

• The first and last bits of B represented in the

decimal range 0 to 3 (or binary 00 to 11). Let that
number be i.

• The middle 4 bits of B represented in the decimal

range 0 to 15 (binary 0000 to 1111). Let that
number be j.

46
 The S-Box for the Substitution Step in Each Round(cont’d…)

• Look up in the table the number in the i-th row and j-

th column.
• It is a number in the range 0 to 15 and is uniquely
represented by a 4 bit block. That block is the output
S1(B) of S1 for the input B.
• For example, for input block B = 011011 the first bit
is "0" and the last bit "1" giving 01 as the row. This is
row 1. The middle four bits are "1101".
• This is the binary equivalent of decimal 13, so the
column is column number 13.
• In row 1, column 13 appears 5. This determines the
output; 5 is binary 0101, so that the output is 0101.
Hence S1(011011) = 0101.
47
 Symmetric DES
The P-Box Permutation in Feistel Function
• The last step in the Feistel function is labeled
“Permutation with P-Box”.
• This permutation table simply means that the first
output bit will be the 16th bit of the
input, the second output bit
the 7th bit of the input, and
so on.
• For all of the 32 bits of the
output that are obtained from the 32 bits of the input.
• NOTE
– bit indexing starts with 1 and not with 0. 48
 Symmetric DES

Initial Permutation (IP) Final Permutation (FP)

IP IP-1
58 50 42 34 26 18 10 2 40 8 48 16 56 24 64 32
60 52 44 36 28 20 12 4 39 7 47 15 55 23 63 31
62 54 46 38 30 22 14 6 38 6 46 14 54 22 62 30
64 56 48 40 32 24 16 8 37 5 45 13 53 21 61 29
57 49 41 33 25 17 9 1 36 4 44 12 52 20 60 28
59 51 43 35 27 19 11 3 35 3 43 11 51 19 59 27
61 53 45 37 29 21 13 5 34 2 42 10 50 18 58 26
63 55 47 39 31 23 15 7 33 1 41 9 49 17 57 25
49
First Bit of the output is taken from the 58th bit of the input, etc...”
 Symmetric DES...
Round Key Generation

• To generate the roundkeys, start with the 56-bit

keys

• These are permuted and divided into two halves

called C and D.

• For each round, C and D are each shifted left

circularly one or two bits.

• The 48-bit roundkey is then selected from the

current C and D bits.

50
 Symmetric DES...
Single round of DES Algorithm

51
 Triple-DES with Three-Keys…

• With triple length key of three 56-bit keys K1, K2 & K3,
encryption is:

- Encrypt with K1

- Decrypt with K2

- Encrypt with K3

• Decryption is the reverse process:

- Decrypt with K3

- Encrypt with K2

- Decrypt with K1 52
Triple DES…

53
 Public Key Cryptography
• RSA
• RSA is from Rivesh, Shamir and Aldermen
• In RSA, the private and public keys are
constructed from very large prime numbers
(consists of hundred of decimal digits) One of
the keys can be made public.
• Breaking RSA is equivalent to finding the prime
factors: this is know to be computationally
infeasible. (NP-hard)
• It is only the person who has produced the keys
from the prime number can easily decrypt the
messages. 54
 Asymmetric RSA

• The RSA algorithm

- Used for both public key encryption and digital signatures.

- Security is based on the difficulty of factoring large

integers.

• Major Activities

- Key Generation

- Encryption

- Decryption
55
 Asymmetric RSA
Key Generation Algorithm
1. Generate two large random primes, p and q
2. Compute n = pq and (φ) phi = (p-1)(q-1)
3. Choose an integer e, 1 < e < φ, such that gcd(e, phi) =
1
4. Compute the secret exponent d, 1 < d < φ, such that
d = e-1 mod φ , i.e. φ divides (ed-1)
5. The public key is (e, n) and the private key is (d, n).
 Keep all the values d, p, q and φ secret
 n is known as the modulus
 e is known as the public exponent or encryption exponent
 d is known as the secret exponent or decryption
exponent.
56
 Asymmetric RSA
Encryption and Decryption
Encryption
• Sender A does the following
- Obtains the recipient B's public key (n, e)
- Represents the plaintext message as a positive integer
m
- Computes the ciphertext c = me mod n
- Sends the ciphertext c to B
Decryption
• Recipient B does the following
- Uses his private key (n, d) to compute m = cd mod n
- Extracts the plaintext from the message representative
m
57
 Asymmetric RSA
Key Generation example
1. Select primes p=11, q=3.
2. n = pq = 11*3 = 33
phi = (p-1)(q-1) = 10*2 = 20

3. Choose e=3
Check gcd(e, p-1) = gcd(3, 10) = 1 (i.e. 3 and 10 are
relatively prime - have no common factors except 1) and
check gcd(e, q-1) = gcd(3, 2) = 1,
therefore gcd(e, phi) = gcd(e, (p-1)(q-1)) = gcd(3, 20) = 1

4. Compute d (1<d<phi) such that d = e -1

mod phi = 3-1 mod 20
i.e. find a value for d such that phi divides ed-1 (20 divides
3d-1)
Simple testing (d = 2, 3 ...) gives d = 7
Check: ed-1 = 3*7 - 1 = 20, which is divisible by phi (20).

5. Public key = (e, n) = (3, 33)

Private key = (d, n) = (7, 33) 58
 Asymmetric RSA
Encryption and Decryption example
• Given
Public key = (e, n) = (3, 33)
Private key = (d, n) = (7, 33)

Encryption
• Now say we want to encrypt the message m= 7
- c = me mod n = 73 mod 33 = 343 mod 33 = 13
- Hence the ciphertext c = 13

Decryption
• To check decryption we compute
- m = cd mod n = 137 mod 33 = 7
59
Encryption and decryption of the word technology using the generated key

60
Encryption and decryption of the word technology using the generated key…

61
RSA Algorithm Summary

62
The DHA for generating a shared secret session
key

• The first public key scheme was invented by Diffie and

Hellman.

• Though it could not be used to send messages, it could

establish secret keys for use in secret key cryptosystems.

• An eavesdropper “tapping the line” would be unable to

determine what the generated key was.

63
 Diffie-Hellman Key Exchange
Algorithm
• 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)

64
 The DHA for generating a shared secret
session key
• The pair of numbers (q, α) is public.
• This pair of numbers may be used for several
runs of the protocol.
• These two numbers may even stay the same for
a large number of users for a long period of time.
• Subsequently, A and B use the algorithm
described below to calculate their public keys
that are then made available by each party to the
other:
– We will denote A’s and B’s private keys by XA
and XB.
– And their public keys by YA and YB.
– In other words, X stands for private and Y for
public. 65
 The DHA for generating a shared secret
session key
• A selects a random number XA from the set {1, 2, .
. . , q − 2} to serve as his/her private key.
• A then calculates a public-key integer YA that is
guaranteed to exist:
YA = αXA mod q
• A makes the public key YA available to B.
• Similarly, B selects a random number XB from the
set
{1, 2, . . . , q − 2} to serve as his/her private key.
• B then calculates an integer YB that serves his/her
public key:
YB = αXB mod q
• B makes the public-key YB available to A.
66
The DHA for generating a shared secret session
key
• A now calculates the secret key K from his/her
private key XA and B’s public key YB :

K = (YB)XA mod q

• B carries out a similar calculation for locally

generating the shared secret key K from his/her
private key XB and A’s public key YA :

K = (YA)XB mod q

67
 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 68
 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 public keys:
– yA=397 mod 353 = 40 (Alice)
– yB=3233 mod 353 = 248 (Bob)
• compute shared session key as:
xA 97
KAB= yB mod 353 = 248 mod 353= 160
(Alice)
xB 233
KAB= y A mod 353 = 40 mod 353= 160
(Bob) 69
 Digital Signature

• Digital signatures allow the world to

verify I created a piece of data
–e.g. email, code

• They are created by encrypting a hash of

the data with my private key
• The resulting encrypted data is the
signature
• This hash can then only be decrypted by
my public key

70
 Why Digital Signatures?

•To provide Authenticity, Integrity and

Non-repudiation to electronic
documents

•To use the Internet as the safe and

secure medium for any data exchange
between two users

71
 Digital Signature using pubic key cryptography
(RSA)
• RSA may be used directly as a digital signature
scheme
–given an RSA scheme {(e,n), (d,n)}
• To sign a message, compute:
–s = md(mod n)
• To verify a signature, compute:
–m = se(mod n)=me.d(mod n)
• Thus know the message was signed by the
owner of the public-key.
• More commonly use a hash function to create
a separate Message Digest (MD) which is then
signed.
72
 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 h
-
the length of h must be at least 128 bits.
-
given M, it must be easy to calculate H(M) = h
-
given h, it must be difficult to calculate M = H-
1
(h)
-
given M, it must be difficult to find M’ such that
H(M) = H(M’)
• Examples:
●
MD4/MD5: hash of 128 bits;
●
SHA : hash of 160,256 bits.

73
 Digital Signatures – Authentication
using hash function
• Abe calculates the hash of the
message: a 128 bit value based
Abe
on the content of the message
• Abe encrypts the hash using his
private key: the encrypted hash
message Hash A message
is the digital signature.
signature
• Abe sends the signed message Digital Signature
Digital Signature
to Kebe.
• Kebe calculates the hash of the
message
• Decrypts A with Abe’s public Keb
key. e
Abe’s keys
• If hashes equal: Hash B
message
1. hash A is from =?

Abe’s private key; Hash A Digital Signature

• 2. message wasn’t public private 74

modified;
 Digital Certificates

• Abe’s digital signature is useful to Kebe if:

1.Abe’s private key is not compromised – keep these

safe!!!

2.Kebe has Abe’s public key

• How can Kebe be sure that Abe’s public key is really

Abe’s public key and not someone else’s?

– A third party establishes the correspondence between

public key and owner’s identity.

– Both Kebe and Abe trust this third party

The “third party” is called a Certification Authority (CA).

CA 75
 Certificate Authorities for authenticating your
public key

• A certificate issued by a certificate authority (CA)

authenticates your public key.

– A certificate is your public key signed by the CA’s private

key.

• A certificate assigned to a user consists of:

– The user’s public key,
– the identifier of the key owner,
– a time stamp (in the form of a period of validity), etc.,
• The whole block encrypted with the CA’s private key.

• Encryption of the block with the CA’s private key is referred

to as the CA having signed the certificate. 76
 Certificate Authorities for authenticating your public
key…
• We may therefore express a certificate issued to party A
by
CA = E (PRCA, [T, IDA, PUA])
–where PRCA is the private key of the Certificate
Authority,
–T the expiration date/time for the A’s public key PUA
that is being validated by the CA, and
–IDA the party A’s identifier.

• Subsequently, when party A presents his/her certificate

to party B, B can verify the legitimacy of the certificate
by decrypting it with the CA’s public key.
• Successful decryption authenticates both:
–the certificate supplied by A and
–A’s public key. 77
 Certificate Authorities for authenticating your
public key…
• Having established the certificate’s legitimacy,
–having authenticated A, and
–having acquired A’s public key,
• B responds back to A with his own certificate.
• A processes B’s certificate in the same manner as B
processed A’s certificate.
• This exchange results in A and B acquiring authenticated
public keys for each other.
• NOTE
–Each of the two parties A and B acquires the other
party’s public key not directly but through the other
party’s certificate.
–For greater security, B can ask CA to verify that the
certificate received from A is currently valid, that is, it
has not been revoked.
78
Parties A and B want to establish a secure and authenticated
communication link

• Party A initiates a request for the link

79
Using Authenticated Public Keys to Exchange a Secret
Session Key
• Having acquired the public keys, the two parties A and B
then proceed to exchange a secret session key.

Party Party
A B

80
 Using Authenticated Public Keys to Exchange a
Secret Session Key…
• A uses B’s public key PUB to encrypt a message that
contains A’s identifier IDA and N1 as a transaction
identifier.
• A sends this encrypted message to B.
• This message can be ex-pressed as
E (PUB, [N1, IDA])
• B responds back with a message encrypted using
A’s public key PUA, the message containing A’s N1
and new N2 from B to A.
• The structure of this message can be expressed as
E (PUA, [N1, N2])
81
 Using Authenticated Public Keys to
Exchange a Secret Session Key…

• Since only B could have decrypted the first message

from A to B, the presence of N1 in this response from B
further assures A that the responding party is actually B
– since only B could have decrypted the original
message containing N1.

• A now selects a secret session key KS and sends B the

following message
M = E (PUB, E (PRA, KS))
• NOTE
• A encrypts the secret key KS with his/her own private key
PRA before further encrypting it with B’s public key PUB.
• Encryption with A’s private key makes it possible for B to
authenticate the sender of the secret key. 82
 Using Authenticated Public Keys to Exchange a Secret
Session Key…

• Further encryption with B’s public key

means that only B will be able to read it.

• B decrypts the message first with its own

private key PRB and then recovers the secret
key by applying another round of decryption
using A public key PUA.

83
84
 Public key infrastructure
• Public Key Infrastructure (PKI) is a framework
that manages digital keys and certificates used for
secure communication and authentication over
networks

• Provide the set of hardware, software, people,

policies, and procedures to:

– create, store, manage, distrbute and revoke

digital certificate

85
 Key Components of PKI
• End entity: A generic term used to denote end
users, devices (e.g., servers).
• Certificate Authority (CA):The CA is a trusted
organization that issues digital certificates.
• It verifies the identity of entities requesting a
certificate and signs their digital certificates to
validate their public keys.
• Registration Authority (RA):The RA acts as a
mediator between users and the CA.
• It receives certificate requests, verifies the
applicant’s identity, and forwards the request to
the CA for the issuance of a certificate.
86
 Key Components of PKI…
• Digital Certificates: A digital certificate contains the
public key and other information about the entity, such as
its name, domain, and expiration date.
• It is digitally signed by the CA to prove its authenticity.
• Repository: A database or directory that stores public
keys and certificates for easy access.
• It allows users and systems to retrieve a certificate to verify
a public key.
• Certificate Revocation List (CRL):A list maintained by
the CA that includes certificates that have been revoked
before their expiration date.
• This helps prevent using invalid or compromised
certificates.
87
Delegation of authority

88
The X.509 Certificate format standard
• X.509 is one of the PKI standards.
– It is this standard that specifies the
format of digital certificates.
• The X.509 standard is based on a strict
hierarchical organization of the CAs in
which the trust can only flow downwards.
• The CAs at the top of the hierarchy are
known as root CAs.
• The CAs below the root are generally
referred to as intermediate-level CAs.
89
 X.509 Certificate Format

• Version Number: describes

the version of the X.509
standard to which the
certificate corresponds.
• Serial Number: This is the
serial number assigned to a
certificate by the CA.
• Signature Algorithm ID: This
is the name of the digital
signature algorithm used to sign
the certificate. (MD5,SHA)
• Issuer Name: This is the name
of the Certificate Authority that
issued this certificate.
• Validity Period: This field
states the time period during
which the certificate is valid.
• Subject Name: This field
identifies the individual/organization
to which the certificate was issued.

90
 X.509 Certificate Format
• Subject Public Key: This field
presents the public key that is
meant to be authenticated by this
certificate.
– This field also names the
algorithm used for public-key
generation.
• Issuer Unique Identifier:
(optional)With the help of this
identifier, two or more different CA’s
can operate as logically a single CA.
– The Issuer Name field will be
distinct for each such CA but they
will share the same value for the
Issuer Unique Identifier.
• Subject Unique Identifier:
(optional) With the help of this
identifier, two or more different
certificate holders can act as a
single logical entity. 91
 X.509 Certificate Format
• Each holder will have a different
value for the Subject Name field but
they will share the same value for the
Subject Unique Identifier field.
• Extensions: (optional) This field
allows a CA to add additional private
information to a certificate.
• Signature: This field contains the
signature of the CA that issued the
certificate.
– This signature is obtained by first
computing a message digest from
the rest of the fields with a hashing
algorithm like SHA-1,
– Then CA will encrypt MD using
private key Signature

92