 For a prime number p, all integers from 1 to p-1 are relatively prime to p

 Zn* denotes set whose members are relatively prime to modulus n

 Zp* denotes set whose members are relatively prime to modulus p

The number of primes is infinite. Still it is difficult to find out number of primes smaller
than or equal to a given number n (consider n as large number)

Next, we discuss two theorems namely, Fermet’s theorem and Euler’s theorem that are
considered important in public key cryptography.

FUNCTIONING OF FERMET’S AND EULER’S THEOREM

Euler’s Phi Function, Φ(n)

It is also referred to as Euler’s totient function. It finds out number of integers smaller than
n and relatively prime to n i.e., Φ(n) calculates number of elements in Zn*
Φ(n) can be calculated as:
(i) If n = 1, Φ(1) = 0
(ii) If p is prime, Φ(p)= p-1
(iii)If m and n are relatively prime, Φ(m x n) = Φ(m) x Φ(n)
(iv) If p is a prime number, Φ(n) is expressed exponentially as Φ(pe) = pe - pe-1

Suppose a number ‘q’ can be factored as p1e1  p2e 2 .... pkek then (iii) and (iv) can be
combined as Φ(q) = ( p1e1  p1e1 1 )  ( p2e2  p2e2 1 )  .....( pkek  pkek 1 )

Table 1 lists some of the cases of calculating Φ(n).

Table 1 some Φ(n)

S.No. Find Solution
1. Φ(7) Φ(7) = 7-1 = 6
2. Φ(8) Φ(8) = Φ(23) = 8 - 4 = 4
3. Φ(10) Φ(10) = Φ(2) x Φ(5) = 1 x 4 = 4
4. Φ(240) 240 = 24 x 31 x 51  Φ(240) = (24 - 23) x (31 – 30) x
(51 – 50) = 64
5. Φ(49) Φ(49) = 72 - 71 = 42
6. No of element in Φ(14) = Φ(7) x Φ(2) = 6 x 1 = 6. Therefore, 6 elements
Z14* are there. These members (in Z14*) are: 1, 3, 5, 9, 11,
13

In second last example factoring Φ(49) as Φ(7) x Φ(7) is not correct as 7 is not relatively
prime to 7. Hence, rule 3 is not applicable.

Difficulty of finding Φ(n) depends upon difficulty of finding factors of n

Fermat’s little theorem

It is available in the following two versions:

 I) ap-1  1 mod p

where, a is an integer and p is a prime and p does not divides a i.e., a and p are
relatively prime to each other.

II) ap  a mod p, this version has no relatively prime constraint on a and n

Use – Fermat’s little theorem is useful in finding quickly some exponentiation and
multiplicative inverses.

Multiplicative Inverse can be evaluated as:

a-1 mod p = ap-2 mod p

Thus, use of extended Euclidean algorithm for finding an inverse is avoided.

Example 10: (a) Find exponentiation: 2402 mod 11?

(b) Find exponentiation: 312 mod 11?
Answer: (a) 210 mod 11 = 1 mod 11 [Using first version of Fermat’s theorem]
Thus, 2402 mod 11 = (210)40 * 22 mod 11 = 4 mod 11.
(b) 312 mod 11 = (311 x 3) mod 11 = (311 mod 11) x (3 mod 11)
= 3 x 3=9 [Using second version of Fermat’s theorem]
Euler’s Theorem
It is basically a generalization of Fermat’s little theorem that considers modulus as integer
instead of prime.

I) aΦ(n)  1(mod n) for two coprimes a and n.

II) Second version removes the coprime condition between a and n. It is stated as
a KxΦ(n)+1  a (mod n)

where, n = p × q, a < n and K is an integer

The second version of Euler’s theorem is used in RSA cryptosystem.

Uses [1]:-
(i) Finding of some exponentiations

Example 11: 2062 mod 77 = (20 mod 77) (20Φ(77)+1 mod 77)
= (20) (20) mod 77 = 15

(ii) Multiplicative inverses can be calculated as

a-1 mod n = aΦ(n) -1 mod n

where, a and n are coprime.

Example 12: 60-1 mod 187 = 60 Φ(187)-1 mod 187 = 60159mod 187 = 53 mod 187

FUNDAMENTALS OF DISCRETE LOGARITHM

Exponentiation and Logarithm
 Exponentiation and Logarithm are inverses of each other.
 Exponentiation is expressed as y = ax and logarithm is expressed as x = logay
 Here, a is base of exponentiation or logarithm.
 In cryptography, exponentiation is used with modular operation i.e., y = ax mod n
 Such operations utilizing large exponents are used by public key encryption system
like RSA algorithm for encryption and decryption.
 Efficient algorithms are required for computing exponentiation operations with large
exponents.
 The exhaustive search method for finding modular logarithm i.e., finding solution as
x = logay mod n by continuously solving y = ax mod n, is very inefficient.
 Hence, another approach termed as discrete logarithm is used.
 For understanding the discrete logarithm approach, multiplicative groups and their
properties need to be discussed.
 In the following subsection, some of the important concepts related to multiplicative
groups are discussed.

Finite multiplicative group

 A multiplicative finite group G = <Zn∗, ×> contains multiplicative operation.
 Set Zn∗ contains integers from 1 to n-1 that are relatively prime to n.
 The set has 1 as the identity element i.e., e = 1.
 As a special case, modulus n may be prime number and hence group becomes
G = <Zp∗, ×>

Order of the Group

Order of the group is defined as number of elements in that group and is calculated as
|G| = Φ(n).

Example 13:What is the order of group G = <Z21∗, ×>?

Answer: |G| = Φ(21) = Φ(3) × Φ(7) = 2 × 6 =12.
Corresponding 12 elements in this group are: 1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19, and 20.

Order of an Element
Order of an element is represented as ord(a) and is defined as the smallest integer i such
that
ai ≡ e (mod n)
where, e is identity element equal to 1.

Example14: Find the order of all elements in G = <Z8∗, ×>.

Answer: Order of group Φ(8) = 4

Corresponding elements: 1, 3, 5, 7.

Order of each element (by trial and error) using above definition.
 a. 11 ≡ 1 mod (8) → ord(1) = 1.
b. 32 ≡ 1 mod (8) → ord(3) = 2.
c. 52 ≡ 1 mod (8) → ord(5) = 2.
d. 72 ≡ 1 mod (8) → ord(7) = 2.

Euler’s Theorem
States that for any member of group G = <Zp∗, ×> the following holds:
aΦ(n) ≡ e (mod n) – (3)
comparing equation (3) with order of group, it can be found that the relation ai ≡ 1 (mod
n) holds when i = Φ(n). thus, it is ensured that atleast one order of element exists.

Example 15: Find order of all elements in the group G = <Z6∗, ×>

Answer: Order of group Φ(6) = Φ(2)×Φ(3) = 1×2 = 2, Corresponding elements:

1, 5.

The table (Table 2) for r = ai (mod 6) is drawn with shadded area identifying r = 1 for i =
Φ(6) = 2.

Similarly, r = 1 for other values of i for every member element of the group. Considering
smallest i for every member element, we have their orders as:

Ord(1) = 1, ord(5) = 2

Table 2 calculations for r = ai (mod n)

i=1 i=2 i=3 i=4 i=5
a = 1 r: 1 r: 1 r: 1 r: 1 r: 1
a = 5 r: 5 r: 1 r: 5 r: 1 r: 1

Primitive Roots: In the group G = <Zn∗, ×>, an element whose order is equal to Φ(n), is
called the primitive root of the group.
Example:
1. In G = <Z8∗, ×> (example 14), no primitive roots are there because none of the
element’s order is equal to Φ(8) = 4. Infact, the order of elements are all smaller than
4.
2. For group G = <Z10∗, ×> Φ(n) = 4. The results of ai ≡ r (mod 10) along with primitive
roots are shown in Table 3

Table 3 Calculations for ai ≡ r (mod 10)

i=1 i=2 i=3 i=4 i=5 i=6 i=7 i=8 i=9
a=1 r: 1 r: 1 r: 1 r: 1 r: 1 r: 1 r: 1 r: 1 r: 1
a=3 r: 3 r: 9 r: 7 r: 1 r: 3 r: 9 r: 7 r: 1 r: 3
a=7 r: 7 r: 9 r: 3 r: 1 r: 7 r: 9 r: 3 r: 1 r: 7
a=9 r: 9 r: 1 r: 9 r: 1 r: 9 r: 1 r: 9 r: 1 r: 9

= Primitive root [ ord (3) = 4 and ord (7) = 4 ]

  In general, a group G = <Zn*, ×> has primitive roots only if n is 2, 4, pt, or 2pt.

Example 16: Which of the following groups have primitive roots:

G = <Z13∗, ×> ; <Z40∗, ×> ; <Z26∗, ×> ; G = <Z98∗, ×> ?

Answer: G = <Z13∗, ×> ; <Z26∗, ×> ; and G = <Z98∗, ×> have primitive roots as in first
group n=13 is prime, in second group n=26 can be expressed as 2 × 13 and in third group
n = 98 can be expressed as 98 = 2 × 72.

Group <Z40∗, ×> has no primitive roots.

Some important points regarding primitive roots:

 A group G = <Zn*, ×> is cyclic if it has primitive roots.

 If any primitive root is present in the group G = <Zn*, ×>, then there exists Φ(Φ(n))
number of primitive roots.
 Each primitive root is termed as generator (g) and is used to generate the entire set.
 Thus, set Zn* can be generated as {g1, g2, g3, …, gf(n)}

Example 17:
Find the primitive roots in G = <Z7*, ×> and show that the entire set can be generated from
them.
Answer: Φ(Φ(n)) = Φ(Φ(7)) = Φ(6) = 2. Hence, two primitive roots 3 and 5 are possible.
These can generate the entire set as shown below (Table 4):

Table 4 Set generated by primitive roots in G = <Z7*, ×>

g=3 g=5
g1 mod7 = 3 g1 mod7 = 5
g2 mod7 = 2 g2 mod7 = 7
3
g mod7 = 6 g3 mod7 = 6
g4 mod7 = 4 g4 mod7 = 2
g5 mod7 = 5 g5 mod7 = 3
6
g mod7 = 1 g6 mod7 = 1

 If n = p then group G = <Zp*, ×> is cyclic as it always has a primitive root and is
hence considered in discrete logarithms.
 Elements in this group include all integers from 1 to p − 1.
 The elements can be created using gx where, g are primitive roots or generator and x
is an integer from 1 to Φ(n) = p − 1.

In modular arithmetic discrete logarithms are used to solve the problems of the form y =
ax (mod n) in which y is given and x is needed to be solved.

Discrete logarithms represented as Lg and considers primitive roots or generators (g) in a

group G = <Zp*, ×> as the base of logarithm i.e., logg y.
A table is maintained (similar to log tables used to calculate logarithms base 10) that
contains discrete logarithms with bases (primitive roots or generators) in rows while y lies
in the columns.

In this table, a particular value of y and g (or base a) is searched to solving the x.

Example 18: Find x for the following:

3=2x mod 5

Answer: The tabulation (Table 5) of discrete logarithm for the group G = <Z5*, ×> is done
below:

Table 5 discrete logarithm for the group G = <Z5*, ×>

Discrete logarithm y = 1 y = 2 y = 3 y=4
x= L2 y 4 1 3 2

Here, y = 3, g (or a) = 2

Considering the above table

x = L23 mod 5 = 3.

Some of the useful properties of discrete logarithms may be stated (Table 6) as:

Table 6 Some properties of discrete logarithms

Discrete logarithms properties
Lg 1 ≡ 0 (mod Φ(n))
Lg (a × b) ≡ (Lg a + Lg b) (mod Φ(n))
Lg bk ≡ k × Lg b (mod Φ(n))

Two points to be considered while solving discrete logarithm problems:

 For large p, the discrete logarithm problem cannot be solved using tabulation and
hence algorithms that make use of the basic properties of discrete logarithms are
devised.
 The discrete logarithm problem has the same complexity as the factorization
problem.
 Related with Public key Cryptosystem

Applications
Applications (use) for public key cryptosystem falls under following three categories.
 Encryption/Decryption – Use of public key encryption for providing confidentiality.
Encryption is done using receiver’s public key while decryption is done using
receiver’s private key.
 Digital Signature – Use of public key encryption for providing message and user
authentication. Usually a small sized data is derived as a function of message and
then it is encrypted using sender’s private key so as to represent signature.
 Key Exchange – Use of public key encryption for exchanging and deriving session
keys. This may involve private keys of both parties (Diffie-Hellman method).

Table 62 – lists the algorithms of public key cryptography that uses all three, two or single
of the above mentioned functionalities.

Table 2 Public-Key Cryptosystem - uses

Algorithm Uses

RSA Used for Encryption/Decryption, Digital Signature and Key Exchange

Diffie-Hellman Used for Key Exchange

DSS Used for Signature

Requirements
Public key cryptography utilizes two related keys. The public key cryptographic
algorithms must fulfill the following conditions:-
1) It is computationally easy
(i) by a party (say Veeru) to generate a key pair (KV, PV)
(ii) to generate ciphertext (C) from plaintext (P) by other party (say Jai) using public
key of first party as
C  EPV (M )
(iii)To decrypt the ciphertext to get back the plaintext as
M  DKV (C )  DKV ( EPV (M ))
2) The private and public keys can be applied in any order as
M  DKV ( EPV (M ))  DPV ( EKV (M ))
3) It is computationally infeasible for an attacker (say Gabbar) to find (i) the private key
(KV), (ii) the plaintext (M) using ciphertext (C) and public key (PV)
 The above requirement reduces itself to the need for a trap-door one-way
function.
 A one way function is one that itself is easy to calculate but finding its inverse is
infeasible.
i.e. Y = f (x) is easy, while X = f-1 (y) is infeasible.
where, X is domain of function and Y is its range.
 A function is easy to calculate means computations can be done in polynomial
time i.e., na, where n is input of n bits and a is a constant.
Here, infeasible to calculate means it requires time much larger than polynomial
time e.g. of the order of 2n.
  A trap door one way function is one for which finding inverse is feasible (may
be calculated in polynomial time) provided some additional information is
known i.e., for a trapdoor K, calculating inverse
X  f K1 ( y) is easy.
 The traditional notion of best case/worst case complexity is not followed in case
of cryptography. In cryptography infeasible to compute means it is infeasible for
all input irrespective of best or worst case input.

RSA – AN EXAMPLE PUBLIC-KEY CRYPTOSYSTEM

Diffie and Hellman’s introduction of Public key cryptography in 1976 paved the path for
development of one of the most widely accepted and general purpose public key
encryption method (in 1977) at MIT by Ron Rivest, Adi Shamir, and Len Adleman. This
method is popularly known as Rivest-Shamir-Adleman (RSA) scheme. It is a block cipher
in which the block size is taken as 1024 bits.

Description
The RSA algorithm has three components: key generation, encryption and decryption.
Each of these is described below:

Key generation
1. Select two large prime numbers p and q (p  q)
2. Calculate n = p × q
3. Calculate (n) = (p – 1) (q – 1)
4. Select an integer e (≤ (n)) such that it is relatively prime to (n) (Euler totient
function) i.e., gcd ((n), e) = 1
5. Calculate multiplicative inverse of e (name it as d) as:
d  e-1 (mod (n))
{e, n} becomes the public key while {d, n} becomes the private key

Encryption
Consider plaintext as M
Then ciphertext (C) is evaluated using public key (e, n) and exponentiation as:
C = Me mod n

Decryption
Plaintext M is gained using private key (d, n) as:
M = Cd mod n

Figure 5 shows the complexity of encryption and decryption in RSA algorithm whereas
Figure 6 shows the encryption, decryption and key generation process.
 Gabber
P:Plaintext = e C mod n
C Exponential complexity
C: Ciphertext = P e mod n
Polynomial complexity
Jai Veeru

P P

Figure 5 RSA complexity of encryption and decryption

Key generation steps by

Veeru in G = < Z(n)*, X >

Select p, q
n=p×q
Veeru Select e and d
Jai

d
e
Decryption P = C mod n
Encryption C = P mod n

(e, n)=known to public including Jai

d = selected (known) only to Veeru as secret
P= Plaintext
C= Ciphertext

Figure 6 RSA: encryption, decryption and key generation

Example 1:
Apply RSA algorithm for encrypting message m=10
Consider primes p=11, q=3.
Answer:
n = p*q = 11*3 = 33
z = (p-1)(q-1) = 10*2 = 20
Choose d=7
Compute ‘e’ such that 7*e = 1 mod 20
 e =3
Public key = (n, e) = (33, 3)
Private key = (n, d) = (33, 7).

Encryption of the message m = 10

c = me mod n = 103 mod 33 = 1000 mod 33
cipher text c = 10

Decryption
m' = cd mod n = 107 mod 33 = 10000000 mod 33 = 10 (plaintext)
Figure 7 shows another example (self explanatory) where the sender wants to send
message NO. For this purpose he maps alphabets to numbers 00 to 25.

Jai Veeru

Send “PQ” encrypted Decrypt & get transmitted “PQ”

Plaintext message = “PQ”=1516
C = 1516 343 mod 159197 d=12007 P = 78170 12007 mod 159197
(e,n)=(343, 159197)

Figure 7 Example of RSA

Proof:
C = Me mod n
Message can be obtained back as:
M = Cd mod n = (Me)d mod n = Med mod n ( ed mod (n) = 1)

 Following are to be remembered in RSA

p, q are privately chosen by a party
n is known to public
e is also known to public
d is privately calculated.
 Following requirements must be met in RSA
(i) n, e and d can be calculated such that Med mod n = M
(ii) Exponential calculations like Me mod n and Cd mod n are easy to perform.
(iii)For a given c and n, d is infeasible to calculate.
 For calculating exponentiation in modular arithmetic the following property is used:
[(a mod n) × (b mod n)] mod n = (a ×b) mod n
e.g. calculating x16 means 15 multiplications are required.
This can also be attained by using 4 multiplications by squaring the partial results.
Thus, 𝑥16 = (((𝑥 2 )2 )2 )2
Similarly x11  x1 28  ( x)( x 2 )( x8 )
x11 mod n  ( x)  ( x 2 )  ( x8 ) mod n
 [( x mod n)  ( x 2 mod n)  ( x8 mod n)]mod n
using above property
The above method is known as fast modular exponentiation algorithm
 The new key generation in RSA deals with selecting two large primes p and q.
 There is no deterministic technique that finds such primes. Instead there are
probabilistic algorithms like Miller-Rabin algorithm that identifies such prime
numbers after several trials.
 Extended Euclid’s algorithm is used to find e such that gcd((n), e) = 1, i.e. finding
e relatively prime to (n).

Security
RSA may be targeted using any of the following four methods:

1. Brute force – Under this category, attacker tries all possible combinations for private
keys. Thus, RSA must use large key space i.e. increase key size. In RSA, a complex
 key generation method is used. Also encryption/decryption depends upon key size.
Thus, upon increasing key size, the system will become slow i.e., processing with
large key will consume extra time.

2. Mathematical attacks – There are following three mathematical approaches to

counter RSA:
(i) If n factors i.e., p and q are known, then (n) = (p – 1) (q – 1) is known. This
enables calculating the private key as d = e-1 (mod (n))
(ii) Determine (n) directly without finding factors, p and q
(iii)Determine d directly without finding totient function i.e., (n)
 Among these, the attacker primarily targeted factoring the product of two
primes.
 In 1994, a group claimed the prize for breaking a challenge initiated in 1977
by RSA inventors. The public key size in this challenge was 428 bits. The
attempt shows that RSA can be broken by finding factors.
 The growing computing power of systems and improved factoring algorithms
(quadratic sieve, generalized number field sieve, special number field sieve)
indicate and force to use large key size. In India, currently RSA variants with
1024 and 2048 bits is used.

3. Timing attacks – In these attacks, attacker observes the time taken by computer to
decrypt the messages. The observations are then used to determine the private key .
 These are ciphertext only attacks.
 The attacker starts from left - bit by bit. If the particular iteration for decrypting
a single bit is slow, the bit is assumed to be 1.
 If the particular iteration for decrypting a single bit is fast, the bit is assumed to
be 0.
 Thus, variation in execution time is utilized for breaking RSA.
 The following countermeasures are utilized to dampen the effect of timing
attacks.
(i) Ensuring that all exponentiation steps take equal amount of time (constant
exponentiation time method). This method degrades the performance.
(ii) Addition of random delay for confusing the attacker. This is not much
effective as the attacker can take additional measures to compensate the
added random delays.
(iii)Blinding – This method is used by RSA data security and in this method
ciphertext is multiplied with a random number before going for
exponentiation. Blinding adds to computation and therefore has associated
performance issues.
RSA data security considers finding method as follows:
a) A secret random number (r) is generated such that 0 < r < n-1
b) Multiply ciphertext by r (Blinding) as
C = C (re) mod n where, e is public exponent
c) Decrypt ciphertext as
M = (C )d mod n
d) Calculate plaintext as
M = M r-1 mod n
Where r-1 is multiplicative inverse of r mod n

4. Chosen Ciphertext Attack (CCA)

 Let us first consider an example of CCA
Assume, Ciphertext C = Me mod n
Calculate X = (C × 2e) mod n
This X is now submitted as CCA to the receiver
The receiver decrypts as
Y = Xd mod n
= (C × 2e)d mod n
= (Me × 2e)d mod n
= (2M)ed mod n = (2M) mod n
Y = 2M mod n, hence M can easily be calculated.
Thus in CCA, attacker selects ciphertext and then submit it for decryption.
Decryption yields the desired data for cryptanalysis.
For protecting against such attacks RSA security Inc. suggests use of padding on
plaintext by using OAEP (Optimal Asymmetric Encryption Padding) method.

Figure 8 Public announcements of public keys

6.4 KEY MANAGEMENT METHODS IN PUBLIC-KEY

CRYPTOSYSTEMS
Public key cryptography is used to distribute public keys and also to distribute secret
symmetric key using public key encryption.

1. Public keys distribution approaches

Major categories into which public key distributing schemes can be grouped are
(i) Announcement of public keys to public
In this category (Figure 8) the public keys are shared between different users
using announcements or broadcasting. Pretty Good Privacy (PGP) that enhances
security in E-mail applications by using RSA, appends user’s public keys to
messages. These messages are sent to public forums, news groups and mailing
lists. The method is simple and convenient but is prone to forgery issues where a
person may act on behalf of sender and send public key to participants. The
participants start encrypted communication with this forged user. Later, actual
sender may identify the fraud and try to alert others but till then the damage may
have occurred.

(ii) Use of Public Directory- A third party maintains a public directory that keeps
public keys of all users (Figure 9). This organization keeps entries of the form
 {name, public key} for each user. For keeping entry and for updating later, each
user registers either in person or through secure authenticated communication.
The entry may be changed dynamically later or upon getting the key
compromised. For updation, authentic communication between user and public
directory is required. In case the private key of the directory gets compromised,
the attacker may impersonate any user, eavesdrop on messages and may even
modify the directory records.

PA
PB
Directory of public keys

PC

Figure 9 Public Directory for public keys

Public-key
Initiator A Responder B
authority
1. Request || Time1

2. EK auth ( PB || Re quest || Time1 )

3. EPB ( IDA || N1 )

4. Request || Time2

5. EK auth ( PA || Re quest || Time2 )

6. EPA ( N1 || N 2 )

7. EPB ( N 2 )

Figure 10 A Distribution Scenario for public keys

(iii) Use of Public-key Authority- It is similar to the Public Directory. In addition

the authority keeps its private key with itself and dismounts its public key in
public i.e., to all users. In the scenario shown in Figure 10, A is Initiator and it
wants to communicate with B who is responder. The steps required to establish
communication between A and B using Public-key authority are as:
 (a) A sends request regarding public key of B to the authority. The request
contains current time stamp.
(b) Authority’s reply contains public key of B (PB) and original request of
A. The reply is encrypted using private key (KAuth) of authority.
Encryption is done so that A is assured that the reply is given by
authority only. Time stamp ensures that this reply is not an old one.
(c) A extracts public key of B (PB) and uses it to encrypt message for B.
Message for B contains ID (IDA) and nonce (N1). Nonce identifies a
particular message from A to B.
(d) As done in (a) and (b) above by A for getting public key of B, messages
(4) and (5) are used to get public key of A from authority by B. After
this step both A and B have public keys of each other.
(e) B now replies A. Reply contains Nonce (N1) extracted in step (c) above
and a new nonce of B (N2). The message is encrypted using public key
of A.
(f) Lastly, A acknowledges B by sending back Nonce (N2). This ensures B
that it is communicating with A only. Thus, a total of 7 messages are
exchanged for sharing public keys of each other using public-key
authority. A and B can also cache the public keys. In this case first 4
steps (a - d) are not required.

(iv) Use of certificates- The previous two schemes have drawbacks. The public
directory is vulnerable to tampering while public-key authority being central to
the system must be able to handle large user requests for public keys. It may
become bottleneck as whenever a communication is required it is contacted for
user’s public key.

The concept of public certificates issued by central authority proves useful under
such conditions. A public key is extracted from certificate whenever
communication is required. The authority need not be contacted every time for
public key. This reduces load on authority. Also, as the certificate is signed by
authority it is reliable and can be trusted. The certificate contains name &
identifier of owner of public key, time of creation of certificate and public key
itself. The certificate authority is a trusted third party (usually government
organization). A user submits its public key through secure communication
medium to authority, authority in turn creates and signs corresponding
certificate. This certificate is published in a public repository or database.
Anybody can obtain this certificate and verify the contents and authority’s
signature using public key of the authority.
 Certificate
Initiator A Responder B
Authority

IDA || PA
C A  EK auth (Time1 || IDA || PA )
IDB || PB

CB  EK auth (Time2 || IDB || PB )

(1) CA

(2) CB

Figure 11 A Scenario for exchanging public key certificates

The following are the requirements of public key certificate scheme:

(1) The certificates are created, maintained and signed only by the authority.
(2) Any user can verify the contents of the certificate and signature of the
authority.
(3) After verification, a user is able to retrieve the details of the ID, name and
public key contained within the certificate.
(4) Using time stamp in certificate, it can be identified whether the certificate
is current or old.

The entire process is shown in Figure 11. The scheme has following steps:
(i) Each participating user submits the request for certificate to the authority.
The request contains identifier and public key.
(ii) The certificate authority issues a certificate as
CA  EK Auth (T ¦¦IDA ¦¦PA )
Here, T is the Timestamp of generation of certificate
KAuth is the private key of certificate issuing authority
(iii)This certificate is given to the other corresponding communicating user.
The user may verify the certificate and extract public key of user A as
DPAuth (CA )  DPAuth ( EK Auth (T ¦¦IDA ¦¦PA ))  T ¦¦IDA¦¦PA
Thus, T ensures that the certificate is current and prevents replays of old
certificates. The certificates with old timestamps are considered as
expired. PA is the desired public key of user with IDA.

 As the certificate is decrypted using public key of authority, it is

ensured that the certificate was infact generated by authority.
 X.509 is the standard for format of certificates and is used by
applications like, Secure Socket Layer (SSL), Secure Electronic
Transactions (SET) etc.

2. Utilization of public key cryptography for distributing symmetric secret keys

 Although public key cryptography provides secure mechanism but it is not preferred
exclusively or completely for communication. This is due to the fact that public key
cryptography provides slow data rates as compared to symmetric key cryptography.

Initiator A Responder B
1. PA || IDA

2. EPA ( K S )
Generates K S
Data packets protected using K S

Figure 12 A simple Session Key establishment

Initiator A Responder B
1. EPB ( N1 || IDA )

2. EPA ( N1 || N 2 )
3. EPB ( N 2 )
4. EPB [ EK A ( K S )]

Decrypt and get K S

Figure 13 Distributing Secret Keys Using Public Key Method

First, let us discuss a simple key distribution mechanism shown in Figure 12. The
communication is done between A and B using following steps.
(i) A generates public key pair, keeps private key with itself and sends ID A
(identifier A) and PA (public key of A) to B.
(ii) B generates secret key for session (KS), encrypts using A’s public key and sends
it back to A as
EPA ( KS )
(iii)A decrypts the message as
DK A ( EPA ( KS ))
and obtains secret session key (KS). Now, both A and B have shared and similar
secret keys.
(iv) A and B starts communicating using KS while discarding the public keys.

 This simple mechanism of sharing symmetric encryption key is prone to man-in-the-

middle attack.
 In this attack, the attacker (E) lies in between and intercepts the message send by A
to B. Attacker removes the B’s public key and adds its public key (PE) and sends
message containing PE ¦¦ IDA to B.
  B transmits encrypted key KS as
EPE ( KS )
This can easily be decrypted by attacker as
DKE ( EPE ( KS ))
 The attacker than reconstructs the message to A as
EPA ( KS )
Thus, to A it seems that nothing wrong has occurred but as shown above the attacker
is able to extract the symmetric key in between.

A second method that shares the symmetric encryption key and maintains confidentiality
and authentication is proposed by Needham and Schroeder (Figure 13). In this method,
both the parties share random numbers (nonce N1 and N2). The following steps are
involved in this method.
(i) A sends IDA and a nonce (N1) encrypted using B’s public key.
(ii) B extracts N1 and then reply by keeping both N1 and a new nonce (N2) into reply.
The reply is encrypted using A’s public key. The receipt of N1 at A ensures that B
has correctly received previous message and A is infact communicating with B.
(iii)A decrypts and extracts N2. This N2 is encrypted with public key of B and then send
to B. This is to confirm B that it is infact communicating with A.
(iv) A selects secret encryption key KS and encrypts it twice: using public key of B (PB)
to ensure only B can retrieve it and using its own private key (KA) as
C  EPB ( EK A ( KS ))
(v) B decrypts the ciphertext message to gain the secret key.

A hybrid approach that uses Key Distribution Centre (KDC) for distributing secret key is
also used. In this scheme, KDC shares secret master key with each of its users. KDC
evolves secret session keys and send them encrypted with master keys to the users. The
session keys are distributed frequently. Use of public key encryption/decryption for their
distribution could cause computation issues. Hence, public key encryption is limited to
update master key that is not changed so frequently. As this scheme uses KDC, it should
be backward compatible with existing KDC mechanism and involve minimal changes.

DIFFIE-HELLMAN KEY EXCHANGE ALGORITHM

 Diffie-Hellman is a popular key exchange algorithm. It enables two communicating
parties to evolve a shared secret key based upon exchanging some value over
insecure medium. The shared secret key is further used to encrypt the messages
between these two parties.
 The effectiveness of Diffie-Hellman method depends upon difficulty in computing
discrete logarithms.
 Diffie-Hellman method has some global publically known numbers considered by
both the communicating parties. These are:
(i) A prime number q
(ii) A primitive root  of q
 Whenever, two users want to exchange a key using Diffie-Hellman method, they
select their own secret numbers. Consider the two users as Jai and Veeru. Jai selects
his secret number as XJ (XJ < q) and Veeru selects his secret number as XV (XV < q).
 Both the users calculate their public numbers as
 Jai: YJ  α X J mod q
Veeru: YV  α XV mod q
 These public numbers are exchanged over insecure medium. On receiving these
public numbers each side calculates the shared common secret key as
Jai: K  (YV ) X J mod q
Veeru: K  (YJ ) XV mod q
 Thus both users (Here, Jai and Veeru) are able to evolve same key as
Jai: K  (YV ) X J mod q Veeru: K  (YJ ) XV mod q
 (α XV mod q) X J mod q  (α X J mod q) XV mod q
 α XV X J mod q  α X J XV mod q
 The entire process is shown in Figure 14.
 As both Jai and Veeru keeps XJ and XV secret, an attacker has only public numbers
i.e., q, , YJ and YB to work with.
Thus, for cracking the Diffie-Helman method, the attacker must determine the
discrete logarithms. For large primes, calculating discrete logarithms is infeasible.
 An example as shown in Figure 15:
 Diffie-Hellman method is prone to Man-in-the-middle (MitM) attack as shown in
Figure 16.

Jai Veeru
1. Generate a random number Generate a random number
XJ < q XV < q
2. Calculate YJ  α X J mod q Calculate YV  α XV mod q
3. Exchange YJ Exchange YV
4. Calculate K  (YV ) X J mod q Calculate K  (YJ ) XV mod q

Figure 14 Diffie-Hellman key exchange

Consider q = 23, α = 5

Insecure Channel
Calculations by Jai: Calculations by Veeru:
Private Key XJ=6 XV=15
Public Key YJ=56 mod 23
= 8 mod 23
23, 5, 8
YV=515 mod 23
19 19 mod 23

196 mod 23 815 mod 23

= 2 mod 23 = 2 mod 23
Secret Key=2 Secret Key=2
 Figure 15 Diffie-Hellman Example

Jai Gabbar Veeru

Generate XJ < q XG1 < q, XG2 < q XV < q
Calculate YJ  α X J mod q YG1  α XG1 mod q, YG 2  α XG 2 mod q YV  α XV mod q
Exchange YJ YG1 YG2 YV

Calculate K JG  (YG1 ) X J mod q KGJ  (YJ ) XG1 mod q KVG  (YG 2 ) XV mod q

KJG = KGJ KGV  (YV ) XG 2 mod q KVG = KGV

Figure 16 Effect of Man-in-the-middle attack

 It can be easily seen that KJG = KGJ and KGV = KVG. Hence, whatever message (M)
is sent encrypted by Jai (using KJG) is intercepted and decrypted by Gabbar (using
KGJ). Gabbar reads the message and again encrypts it (using KGV) before sending it
to Veeru. Upon receipt, Veeru decrypts the message M (using KVG).
 Thus, the middle man, Gabbar is able to read the encrypted message without letting
this fact known to Jai or Veeru.
 The Diffe-Hellman key exchange protocol is prone to MitM attacks because it lacks
user authentication. This can be overcome by using digital signatures and public-key
certificates.
 REQUIREMENTS OF AUTHENTICATION
The following are the authentication requirements imposed during communication of
message(s) between sender and receiver.
(i) The received message should be send only by the alleged sender i.e., message and the
acknowledgements from fraudulent source are never accepted.
(ii) The message has not been altered on the way i.e., insertion, deletion, transformation
and modification of message contents is not possible.
(iii)The sequencing of messages or its parts is maintained i.e., it is not possible for the
attacker to change the sequencing.
(iv) The delayed or replayed messages must not be accepted i.e., modification in timings
of message is not possible. Thus, a message cannot be accepted beyond a particular
time limit.
(v) Non repudiation of source (sender) is ensured i.e., a source may never deny sending
of message.
(vi) Non repudiation of destination (receiver) is ensured i.e., destination cannot deny
receipt of message.

AUTHENTICATION FUNCTIONALITY
Authentication of message involves two steps:
(i) Creation of a value (termed as authenticator) that is used to authenticate the message.
(ii) Verification of authenticator by receiver.

Ways of creating an authenticator:

(i) The encrypted ciphertext of the message may serve the purpose of an authenticator.
(ii) A fixed length value evaluated after applying a function that takes message and shared
secret key as input. The fixed length value is termed as message authentication code
(MAC) and may serve the purpose of an authenticator.
(iii)A fixed length value that is evaluated as a function of message only. This value is
termed as hash and may serve the purpose of an authenticator.
In the subsection, each of the above authenticators are discussed.

Use of Message Encryption for Authentication:

Both symmetric and asymmetric encryption may be used independently.

Application of Symmetric Encryption:

Symmetric encryption provides confidentiality and authentication. Figure 1 (a) shows the
usage of symmetric encryption to ensure both confidentiality and authentication.
Authentication is implicitly ensured along with confidentiality by encrypting selected
message using shared encryption key while only the receiver is able to decrypt back the
data. As no other attacker knows the shared key, the alteration to the message is also not
possible. The only issue involved in such kind of authentication is to identify the legitimacy
of the message. To elaborate this point consider communication between sender A, receiver
B, encryption function E, decryption function D and secret key K. The receiver B may
accept any input X and decrypt it as Y = DK(X). It might happen that the decrypted Y is
meaningless sequence of bits (in case X is provided by attacker). Thus, receiver needs to
identify whether this Y has some meaning or not. Upon identifying that Y has some meaning
the corresponding plaintext X is treated as legitimate and the receiver gets ensured that it
must be send by the sender A only (Figure 2).

Out of all possible bit combinations only small subset may be considered as legitimate e.g.,
out of all possible combination only few qualify as per ordinary English language. Thus,
the problem of determining that a given cipher text decrypts to intelligible plaintext is
difficult. The difficulty level get raise if the plaintext considered for encryption is in binary
format/file.
This provides ample opportunities to the attacker for disrupting or interfering decryption
process at receiver by sending forged random messages that appears as encrypted messages
from legitimate users.

Apply encryption (E) Apply decryption

on message (M) (D) using Key (K)
EK ( M )
using key (K) and gain back
Sender message (M) Receiver
A B
(a) Symmetric encryption: confidentiality and authentication

Apply encryption (E) Apply decryption

on message (M) (D) using private
EPB ( M )
using public key ( PB ) Key (KB ) and gain
Sender back message (M)
Receiver
A B
(b) Public-key encryption: confidentiality

Apply decryption (D)

Apply encryption (E) using public key ( PA )
on message (M) EK A ( M ) and gain back
using private key (KA) message (M)
Sender Receiver
A B
(c) Public-key encryption: authentication and signature

Apply Apply Apply Apply

encryption encryption EPB [ EK A ( M )] decryption (D)
decryption
(E) on (E) on (D) using using public
message (M) message private key key ( PA ) and
Sender using private (M) using gain back Receiver
(KB )
A key (K ) public key message (M) B
A
( PB )

(d) Public-key encryption: confidentiality, authentication and signature

Figure 1 Uses of message encryption

 Gabbar

dgito mbkr yproz plmn

Enemy will reach soon

Veeru
Decrypted from
Jai Message encoded using Caesar Jai’s message Decrypted from
cipher (key =3): Gabbar’s message

Meaningful
Hqhpb zloo uhdfk vrrq Meaningless
(Accept)
(Discard)

Figure 2 Symmetric encryption for providing authentication

Thus, a structure is required to be added to the transmitted message that enhances the
authentication capabilities for example, addition of check sum or Frame Check Sequence
(FCS) as error control measure to the message M and then encrypting the complete block
(Figure 3 (a)) strengthens authentication. The receiver first decrypts the message using
shared secret key and then calculates FCS from decrypted message.

If the calculated FCS matches with the FCS contained in the encrypted message, the
message (plaintext) is considered as authentic. If the attacker tries to disrupt the decryption
process by sending random message for decryption then it is unlikely that such relationship
between decrypted message M and FCS prevail and hence attacker’s messages are easily
discarded. If instead of this above mentioned scheme (termed as internal error control)
another scheme (termed as external error control) is used where the FCS is calculated by
sender for the encrypted message and is concatenated with the encrypted message (Figure
3 (b)), the attacker again has opportunity to disrupt or interfere the decryption process. This
is because the attacker can now create forged messages with valid FCS and may direct them
towards receiver.

Another example where structuring adds towards enhancing the authentication capabilities
is TCP segment encryption. The TCP segment is encapsulated in IP datagram and the part
of datagram excepting IP header is encrypted. The TCP header information includes
checksum, sequence number etc. In case the attacker tries to create and send a forged
datagram, the resulting encrypted text (containing TCP header information) will become
meaningless and therefore leading to discarding of such forged datagrams.
 * Take message M * Decrypt using key (K)
* Apply function F EK [ M || F ( M )] * Apply F to M
to M and append * Compare F(M) with the
Sender A F(M) to M one kept along with M Receiver
* Encrypt M || F(M) B
using key (K)
(a) Internal error control

* Encrypt message * Apply F to EK ( M )

M using key K EK ( M ) || F ( EK ( M )) * Compare it with the one
* Then apply function kept in the sent message
Sender A F to it and append * Decrypt EK ( M ) using Receiver
F ( EK ( M )) to M key (K) B

(b) External error control

Figure 3 Two types of Error control using FCS (Function F)

Application of Public-key Encryption:

In Public-key Encryption each sender and receiver has two key pairs (private and public
key). Thus, there are two possibilities (Figure 1 (b), Figure 1 (c)). (i) Sender uses public
key of the receiver for encryption of message M (ii) sender uses its own private key for
encryption of message M. The former ensures only confidentiality while latter ensures
authentication and signature. This is because in (i) above anybody can send encrypted
message but only the intended receiver is able to decrypt the message as only he has his
private key. In (ii) above only the sender can encrypt the message M using his private key
while others are able to verify this by decrypting using corresponding public key. Here, the
encrypted ciphertext becomes digital signature because only sender A owns his private key
( 𝐾𝐴 ) not even receiver B has any idea about this. This scheme does not provide
confidentiality as anyone who posses public key of the sender can decrypt the encrypted
message. Figure 1 (d) illustrates the public-key encryption scheme that provides both
confidentiality and authentication. Hence, first sender encrypts M using his private key
( K A ) . This becomes its signature and used for authentication and is then encrypted using
receiver’s public key to ensure confidentiality. The major drawback in this scheme as
compared to symmetric method is requirement of more calculations. Here, the public key
encryption is applied 2 times and public key decryption is applied. 2 times making count as
four whereas in symmetric method only one encryption and one decryption is required.
 * Take message M *Apply MAC function C
* Apply MAC M || CK ( M ) that utilizes key K to M
function C that * Compare C ( M ) with
K
Sender A utilizes key K to M the one kept along with Receiver
and appendC ( M ) M B
K
to M
(a) Message authentication

* Take message M * Decrypt using K 2

* Apply MAC * Apply MAC function C
function C that EK2 ( M || CK1 ( M )) that utilizes key K1 to M
Sender A utilizes key K1 to M * CompareCK ( M ) with Receiver
and append CK ( M ) 1
the one kept in the B
1
to M received message
* Encrypt M || CK ( M )
1
using key K 2

(b) Message authentication and confidentiality : authentication tied to plaintext

* Encrypt message M * Apply MAC function C

using key K 2 that utilizes key K1 to EK ( M )
* Apply MAC
EK2 ( M ) CK1 ( EK2 ( M )) * Compare it with
2

Sender A function C that CK1 ( EK2 ( M )) Receiver

utilizes key K1 to * Decrypt E ( M ) using K B
K2 2
EK2 ( M ) and
append it to EK ( M )
2

(C) Message authentication and confidentiality: authentication tied to ciphertext

Figure 4 Uses of Message Authentication Code (MAC)

Use of Message Authentication Code for Authentication:
Message Authentication Code (MAC) is basically cryptographic check sum.
 It is evaluated using shared secret key and is of fixed size.
 The evaluated MAC is appended to the message.
 Considering communication between sender A and receiver B, message M and shared
secret key as K, the MAC is evaluated as
MAC = CK(M)
Where C is the MAC function that utilizes key K
 The receiver calculates MAC using same function on M and then compares the
calculated MAC with the appended MAC. If the two matches the message is accepted
otherwise rejected.
 The receiver ensures the following upon matching the MAC:
(i) The message is not modified on the way. If attacker tries to modify the message,
the calculated MAC will not be same as that of appended MAC. The two MAC
differs because attacker is unable to evaluate and append new MAC due to lack of
secret key.
(ii) The message is send by A only as no other party know the secret key and hence
cannot create the message along with the appended MAC.
(iii)The sequence numbers corresponding to a message cannot be modified due to lack
of secret key with any other party. Hence, sequencing remains unaltered.
 In comparison to encryption algorithm, the MAC algorithm is not reversible (unlike
decryption). Also, MAC function is many-to-one e.g., considering 50-bit messages
and 10-bit MAC, possible messages are 250 while possible MACs are only 210. This
means that single MAC is generated by 250/210=240 different messages. Considering
key of 6 bit size, 26=64 different mapping from set of messages to set of MAC is
possible.
 MAC can be used to provide either authentication or authentication and
confidentiality both (Figure 4 (a) – (c)). In former, message is send in clear and hence,
only authentication is ensured (Figure 4 (a)). Latter, further has two sub cases: (i)
where authentication is tied to plaintext (Figure 4 (b)) and, (ii) where authentication
is tied to ciphertext (Figure 4 (c)). In case (i) encryption is performed after evaluating
MAC. Two separate keys shared by sender and receiver are required under these
cases. One for evaluating MAC, other for encrypting message. Out of these, case (i)
is preferred as this reduces the attacker’s chances.
 Authentication via MAC is preferred to authentication via encryption in some
scenarios. These are:-
(i) Broadcasting of a message to more number of destinations e.g. broadcasting
notifications or raising an alarm etc. Such messages are send in plaintext along
with MAC which can be verified and authenticated by destinations sharing secret
keys.
(ii) For heavily loaded systems MAC can be verified for selective messages instead
of decrypting all the incoming messages.
(iii)Computer programs may be provided with MAC instead of encrypting entire
program. The MAC verification ensures program integrity.
(iv) Messages in certain applications like Simple Network Management Protocol
(SNMP) need not be encrypted rather authenticated. Thus, a managed system
working under the control of SNMP doesn’t require commands in concealed form
rather commands are required to be authenticated for taking necessary action as
per the instructions.
 Separation of confidentiality and authentication functionalities may be helpful in
some cases where confidentiality may be provided at lower level (transport or link
layer) while authenticity may be provided at higher level (application layer). This
enhances the flexibility.
 MAC extends the message protection time. In case of encryption, once a message is
decrypted upon receipt, its protection is lost. In case of MAC protection, the MAC is
always associated with message not only in transit but otherwise also. So authenticity
is guaranteed all the time.
 MAC itself does not provide repudiation feature like digital signature as sharing of
key is involved between two parties i.e., sender and receiver. Digital signatures are
created using secret known to only one party not to others.
 * Take message M * Decrypt using key K
* Apply Hash EK ( M || H ( M )) * Apply Hash function (H)
function H and to M
Sender A append it to M * Compare calculated H(M) Receiver B
* Encrypt M || H ( M ) with the one kept along with
using key K M
(a)

* Apply Hash function * Decrypt EK ( H ( M )) using

(H) followed by encrypt key (K)
M || EK ( H ( M ))
(E) using key (K) * Compare result with that of
Sender A * Concat result with applying Hash function (H)
message M on message M Receiver B

(b)

* Apply Hash function * Decrypt EK A ( H ( M )) using

(H) followed by encrypt M || EK A ( H ( M )) public key of A ( PA )
(E) using private key * Compare result with that of
Sender A of A ( K A ) applying Hash function (H)
* Concat result with on message M Receiver B
message M
(c)

* Apply Hash function (H) * Decrypt EK ( M || EK ( H ( M )))

A
followed by encrypt (E) using key (K)
using private key of A ( K A ) * Decrypt EK A ( H ( M )) using
EK ( M EK A ( H ( M ))) public key of A ( PA )
* Concat result with
Sender A * Compare result with that of Receiver B
message M
* Encrypt M || EK ( H ( M )) applying Hash function (H)
using key (K)
A (d) on message M

* Concat a random number * Concat a random number S with

S with message M message M
* Apply Hash function (H) M || H(M || S) * Apply Hash function (H) on
on concatenated (M || S) concatenated (M||S)
Sender A Receiver B
* Concatenate the result with * Compare calculated H(M||S)
message M with that contained in received
message
(e)
* Concat a random number * Decrypt EK ( M || H ( M || S ))
S with message M using key K
* Apply Hash function (H) * Concat a random number S with
EK ( M || H ( M || S )) message M
on concatenated (M || S)
Sender A * Concatenate the result with * Apply Hash function (H) on Receiver B
message M concatenated (M||S)
* Encrypt (M||H(M||S)) * Compare calculated H(M||S)
using key K with that contained in received
(f) message

Figure 5 Uses of Hash function

Use of Hash Function for Authentication:
Hash function represents variation of MAC that doesn’t use secret key rather only variable
size message is used as input.
 Hash function is one way function and it is function of all message bits.
 It’s output is fixed and changes on changing even a single message bit. The output is
termed as message digest or hash value (code).
 A hash code is used for authentication in following ways:
(i) Message and Hash both are encrypted using shared secret key. This provides
authentication and confidentiality both (Figure 5 (a)).
 (ii) For application that do not require confidentiality. The calculated small sized hash
is encrypted using symmetric key. This also reduces the processing overhead to
encrypt/decrypt the entire message. The overall functionality of such hash use is
equivalent to MAC functionality (Figure 5 (b)).
(iii)Private Key of sender is used to encrypt the calculated hash only, leaving message
as such. This ensures authentication (also digital signatures) as only sender is able
to perform such functionality because only he has the private key (Figure 5 (c)).
(iv) When digital signatures and confidentiality is required, the digital signature is
created as in (iii) above and then both message and digital signatures are encrypted
using symmetric shared secret key (Figure 5 (d)).
(v) Sender selects a random number S concatenates it with message M and then
calculates hash. The calculated hash is appended to the message. No encryption is
done in this method. The random number is shared between sender and receiver
only. This implies no modification is possible by the attacker (Figure 5 (e)).
(vi) The message and hash calculated in (v) can be encrypted further to enhance
confidentiality (Figure 5 (f)).

Among these above mentioned hash techniques, (ii) and (iii) are popular, though they do not
involve encryption. This is due to following;
 Encryption using software is relatively slow as compared to encryption using
hardware.
 Hardware used for encryption is usually optimized for large sized data. Hence, due to
the initialization (startup) cost, small encryption is not effective on such hardware.
 Hardware cost for several systems cannot be considered as negligible.
 Algorithms for encryption (e.g. RSA algorithm) are usually patented and therefore
cost is involved for attaining licenses.

MESSAGE AUTHENTICATION CODES (MACs)

 is a fixed length authenticator.
 It is evaluated as MAC = CK (M)
Where C is MAC function, M is variable length message, K is shared secret key and
output from MAC is fixed length code.
 Any MAC function should meet the following requirements:-
(i) It is computationally infeasible to find or construct another message M such that
CK (M′) = CK (M)
(ii) The hash function should be uniformly distributed. i.e., for n bit size MAC the
probability that CK (M′) = CK (M) is 2-n.
(iii)It is not possible to apply some transformation on message M such that the hash
of M′ (transformed message) = hash of M. More specifically.
Pr = [CK (M) = CK (M′)] = 2-n
 Consider message M that is formed by concatenating 64-bit blocks (Xi) as:
M = (X1 ¦¦ X2 ¦¦…..Xm)

Define MAC as
Δ(M) = X1  X2 …. Xm
CK(M) = EK (Δ(M)) - (1)
Where, E is encryption algorithm (DES in electronic code book mode); K is secret
Key; and  is Exclusive OR (XOR) operation.

Instead of Brute force attack, attacker opted for fraud insertion and created Ym by
replacing X1 to Xm-1 by new desired values Y1 to Ym-1.
Ym = Y1  Y2 …… Ym-1  Δ(M) - (2)
Received Δm = Y1  Y2  ……. Ym {Substitute Ym from (2)}
= ΔM

Thus, hash of Δm is same as per eqn. (1) above and therefore new message (Y1 ¦¦ Y2
¦¦…..Ym-1) is inserted and still M accepted by receiver.

This should not happen and requirement (i) should be followed by MAC authenticator.

The requirement (ii) deals with protecting against brute-force attack. Consider, key
size (K) > MAC size (n).

As MAC function is many-to-one, for applying brute-force attack, attacker must try
different key values (Ki) such that

MACi = CKi (M) and MACi = MAC1

where MAC1 = CK1 (M)
In fact number of keys (set) will produce correct MAC (MAC1). Thus attacker’s task
is now reduced to find actual key from this set and hence repetitive execution of this
scheme is required.
Example 1: Key size 80 bit, MAC size = 32 bit
Ist round 280-32 = 248 possible keys
IInd round 248-32 = 216 possible keys
IIIrd round 216  last round (1 possible key)

In case K  n, the first round may produce a match. Thus, efforts required to find the
authentication key is not less than the efforts required to find the decryption key and
the key may be found in Ist round itself.

The requirement (iii) says that existence of weak spots (where algorithm proves to be
weak) in M should be avoided otherwise the attacker may easily get early success in
identifying new message (M′) such that hash of M and M′ are equal.

Example of MAC created:

 DES in Cipher Block Chaining (CBC) may be used to create/form MAC.
 Initial vector is initialized as zero.
 The data is grouped into 64-bit blocks (D1, D2, …..DN).
 Final block may be padded on right side with zeros.
 The final output, Data Authentication Code (DAC) is of 16 to 64 size (Figure
6).
 Initially At any moment i Finally
(At t = 1) (At t = i) (At t = N)

Di block (64 bits) DN block (64 bits)

D1 block (64 bits)

Outputi-1
+ OutputN-1 +

Apply DES Apply DES

Apply DES
algorithm using 56 algorithm using 56 algorithm using 56
bit key (K) bit key (K) bit key (K)

Outputi OutputN
Output1
(64 bits) (64 bits) (64 bits)
DAC =16 to 64 bits of OutputN

Figure 6 Example of MAC based upon DES

HASH FUNCTIONS: SHA-1, MD5

 As discussed in section 7.3, a hash function H produces a hash value h as

h = H (M)
where, M is variable length message
 Hash value itself is not secret rather it needs to be protected by applying another
function.
 The main purpose of hash function is to generate a fingerprint of data.
 The following are requirements for a hash function (H):
(i) Input is data block of any size.
(ii) Output is of fixed size.
(iii) Software and hardware implementations of H are practical.
(iv) Given input x, it is easy to calculate h as H(x) but reverse calculations are
computationally infeasible i.e., given h it is not possible to computationally find
x in some time. This requirement is also referred to as one way property.
(v) Weak collision resistance: Given x, it is computationally insensible to find y (≠
x) such that H(y) = H(x).
(vi) Strong collision resistance: No pair (x, y) can be found computationally such that
H(x) = H(y).
 th
(iv) property ensures that if secret key is used during hash evaluation then it remains
safe as reverse calculations are not possible.
 (v)th property ensures that an alternate message that generates some hash value is not
possible.
 (vi)th property ensures resistance against birthday attacks.
In birthday attacks, attacker generates 2m/2 variations of message and compares them with
actual set and then tries to find pair of messages that produces the same hash code.

(i) Initial
Result = 0
Block I
(ii) Rotate Result (Hash
Value) left by 1 bit
Block II
.
.
.
Block N (iii) XOR rotated Result
with current block and
store it back into Result

Result
Repeat steps (ii) & (iii) till all
th
i Result bit = N blocks have been XORed
XORing of ith bit of
all blocks

(a) Hash function using XOR (b) Hash function using XOR with
rotation

Figure 7 Two simple Hash function (one using XOR other using XOR with rotation)

Below two simple hash functions are presented to enhance the understandability [3].
(1) Hash function (Figure 7(a)) that performs bit-by-bit XoRing of every block to
produce single bit of hash code (Ci) as:
Ci = bi1  bi2 …. bim
where
m = number blocks (each block is of n-bit size)
bij = ith bit of jth block
 The above function is effective for data integrity check. It provides parity for each
bit and is known as longitudinal redundancy check.
 The function is less effective where data is predictably formatted e.g. in normal
text files, the MSB in each octet is always zero. For 128 bit hash code effectiveness
should be 2-128 but in the normal text file case it is 2-112 as 16 bit positions evaluates
to zero hash code.
 Thus a method to randomize the input is required.
(2) Hash function that shifts one bit in circular fashion on hash code after each block is
processed (Figure 7(b))
  It has two steps
(i) n – bit hash code is initialized to zero.
(ii) For each n – bit block of data:
Rotate the hash code left then XoR it with block bits and store it back into hash
code.
 This hash function is still of not much use even when encrypted hash code is used
along with the message because it is easy to prepare alternate message which still
evaluates same hash code.
 Another technique that encrypts message and hash code is as:

message M : sequence of 64 bit blocks X2, X2….Xn

hash code C = XN+1 = X1  X2 ….. Xn - (1)
and append it to message
Encrypt message and hash code using CBC mode
Encrypted message Y1, Y2……Yn+1

According to CBC definition

X1 = IV  DK (Y1)
Xi = Yi-1  DK (Yi)
XN+1 = YN  DK (YN+1)
Substituting Xi’s into (1) above - results in hash code as:
XN+1 = [IV  DK (Y1)]  [Y1  DK (Y2)] …. [YN-1  DK (YN)]
This XoRing can be done irrespective of order of ciphertext block. Thus, hash
code doesn’t change upon permuting ciphertext blocks giving chances to attacker.

(I) Initially for (i = 1) CV0=IV

(II) Apply the following process repetitively L times
CVi-1 (n bits) Yi-1 (input block of b bits)

Compression function f

CV: Chaining Variable

CVi (n bits)
(III) Finally (i = L)
CVi = CVL = n bit hash code

Figure 8 General Structure (Secure Hash Code)

Overall structure of a typical secure Hash function:

 The structure shown in Figure 8 was proposed by Merkle.
 This structure is used by most hash functions including SHA (discussed in next
section) and whirlpool.
 The input message is divided into L fixed sized blocks each of b bits.
 The last block is padded so that its size becomes b bits.
 The last block also contains length of message. The length is included to make
attacker’s task difficult.
 The hash function (H) repeatedly uses a compression function .  takes two inputs:
one b-bit block (Yi-1) and other n bit chaining variable CVi-1 (previous step output).
The initial value of CVo is IV. The final output (CVL) is the hash code (H(M)). The
intermediate CVi (output of ) is calculated as
CVi =  (CVi-1, Yi-1) 1 i  L
 The function  is termed as compression function because the block size (b) is often
greater than hash code size (n).
 The presented general structure for secure hash code has an important property stated
as:

If  is collision resistant then so is hash function H. This means that-

(i) H can operate upon message of any size.
(ii) The secure hash function designing is reduced to collision resistant 
designing.
(iii)Designing  is comparatively easy as it operates upon fixed sized inputs.
 Crypt analysis of hash function is directed to  and hence try to produce collisions for
.
  itself consists of series of processing rounds.
 For any Hash function, collision does exist (as b  n) but these are computationally
infeasible to identify.

SECURE HASH ALGORITHM (SHA)

 The basic structure provided in the previous section has proved fundamentally sound
and hence most of the hash function design follows the refinement of this
structure/compression function.
 Two approaches of hash algorithm are widespread: one that considers use of modular
arithmetic and logic binary operations as the compression function (e.g., secure hash
algorithm (SHA)). Other that considers use of symmetric block cipher as the
compression function (e.g., whirlpool).
 MAC approaches are also divided into two: one based upon SHA as the main part
other that uses symmetric block cipher in cipher block chaining mode.
 Secure hash algorithm (SHA) was developed by National Institute of Standards and
Technology (NIST).
 It is published as Federal Information Processing Standard (FIPS 180) in 1993 and
subsequent revisions as (FIPS 180-1) in 1995 and (FIPS 180-2) in 2002.
 FIPS 180 is the initial secure hash standard, FIPS 180-1 describes SHA-1 while FIPS
180-2 defines three versions namely, SHA-256, SHA-384 and SHA-512.
 SHA-I that produced 160 bit hash code is currently phased out.
 SHA-1, SHA-256, SHA-384 and SHA-512 uses modular arithmetic and logical binary
operations as compression function.
 SHA-512 algorithmic logic and steps are presented next.
 Following are the parameters of SHA-512 algorithm.
Input: message having maximum length as 2128 bits i.e., M<2128
Output: 512 bit fixed
Block size: 1024 bits
Word size: 64 bits
No of steps: 80
 The overall structure of SHA-512 is shown in Figure 9
 The processing involves 5 steps
 Step 1: A padding consisting of single 1-bit followed by variable number of
0-bits (as per the requirement) is added at the end (last block). The padding is
always done even if the message fits completely in block or not. Padding is
done such that the length becomes congruent to 896 mod 1024 i.e. length ≡
896 (mod 1024).
 Step 2: The original message length (size) is treated as unsigned integer of 128
bit and is added in the last block such that the total length of message now
becomes multiple of 1024 i.e., length message (M1,M2,…MN) = N*1024 bits.
 Step 3: For holding hash code or value 512 bit buffer is used. It is considered
as combination of eight 64-bit registers and these are named as a, b, c, d, e, f,
g and h (Figure 10).

For initializing these registers square roots of first eight prime numbers is
calculated and the first 64 bits corresponding to fractional part of each root is
assigned to these registers in big endian format (where MSB corresponds to
leftmost byte position). Thus initial values (in hexadecimal) of these registers
during first block processing are [3]:

a = 6A09E667F3BCC908
b = BB67AE8584CAA73B
c = 3C6EF372FE94F82B
d = A54FF53A5F1D36F1
e = 510E527FADE682D1
f = 9B05688C2B3E6C1F
g = 1F83D9ABFB41BD6B
h = 5BE0CDI9137E2179

 Step 4: processing (Figure 10) of each 1024-bit block of message is done in

80 rounds (Shown by F in Figure 9). Each round considers the buffer
(abcdefgh) and updates its value. Initial value of this buffer is initialized as per
step 3 above.
 For ith block of message the buffer has intermediate hash value Hi-1
 Each round t considers following inputs:
(i) A 64-bit value Wt derived from current block of message (Mi).
(ii) An additive constant Kt (0 ≤ t ≤ 79). Each Kt for a round is
evaluated from first 64 bits of fractional part of cube root of
first tth prime number. These Kt are used to remove regularities
in the input data.
(iii) Buffer values from previous round.

 The output of last round (80th round) is added with Hi-1 to produce final
Hi from this processing. Each of the eight registers (a, b, c, d, e, f, g
and h) are added independently using modulo 264 addition.
 Step 5: After processing all blocks, the output Message Digest (MD) (of 512
bits) from Nth block processing represents the hash code or value
 Hiding the round complexities, entire algorithm may be summed as:
HO = IV
Hi = SUM64 (Hi-1, abcdefghi)
MD = HN

where,
IV is the initial value of buffer (abcdefgh)
abcdefghi represents out of last round processing for ith message block
SUM64 represents addition in modulo 264 for each word.
MD represents final message digest or hash value

 Message converted into N-blocks (each of 1024 bits).

 While doing so, if entire message fits in exactly N blocks then an extra block is added.
 Last block contains message data (if any), message length and is padded using single 1 followed by 0's (binary values).

Mi
Mi (1024 bits)
Word by
H i - 1 (512 bits) word addition
F
mod 264 H i (512 bits)
i th message block processing

For Ist block processing H0 = IV(512 bits)

Total block processed = N
Hash code = H N

Figure 9 Message Digest Generation (SHA-512)

 For Ist round Wt = W0
(a,b,c,d,e,f,g,h) = Hi-1 From previous
round
Kt = K0
t th round
3 inputs
Total = 79 rounds
(i) (a, b, c, d, e, f, g, h) - each of 64 bits
from previous round
(ii) Wt - word each Wt is derived
from message block M i
(iii) K t - additive constant to remove
regularities in the input data
Output goes to next round as input
(a, b, c, d, e, f, g, h)
th
After 79 round

th
Output of 79 round is added to Hi - 1 to yield Hi

Final output of single block processing = Hi

Figure 10 Single Block (1024 bit) Processing (SHA-512) corresponding to ith block

PROTOCOLS FOR AUTHENTICATION

Digital signatures provide authenticity to message and to its originator. Considering two
party communication, authentication is either mutual or one-way. Therefore, discussion in
this section pertains to two categories: (1) Mutual authentication and (2) One-way
authentication.

I. Authentication of each other (mutual authentication):

Mutual authentication protocols assume that the two communicating parties possess
secret key or private/public key pairs. In mutual authentication, the two
communicating parties prove each other identity and are able to evolve session key
for securing the communication. The authenticated key exchange should be
performed such that the (i) confidentiality requirement is met i.e., information
exchange must use encryption technique and (ii) message replays doesn’t affect the
ongoing process. The replays may lead to key compromise, other party impersonation
and key exchange disruption. Table 1 lists the various replay attacks.

S.No. Type Comments

1. Simple replay attack A copy of the original message is replayed later by
the attacker.
2. Logged repetitions A timestamped message may be used for replays
within valid time limits.
3. Repetition that cannot be This can happen when the original message is
detected suppressed while the replayed message is
communicated.
 4. Backward replay without Under symmetric encryption, the encrypted
modification message is replayed back to the sender such that
he is unable to differentiate between the actually
send and the replayed messages.
Table 1 Replay Attacks
There 3 possibilities against replay attacks:

(i) Sequence numbers are used in each message.

(ii) Timestamps are used in each message.
(iii) First party gives a challenge (nonce) and expects it back from other in response.

 First approach requires tracking of sequence numbers for each participant and due
to this overhead, sequence numbers are seldom used in authentication and key
exchange.
 Second approach based on timestamp is useful in connectionless applications. It
cannot be used for connection oriented applications due to following reasons:
(i) Another protocol that requires synchronization among various processor
clocks is required. This protocol should be fault tolerant and secure.
(ii) If one of the party’s clock faults, there are chances of attack.
(iii)Precise synchronization is difficult due to variable and unpredictable network
delays.

The acceptable window of time in this approach should be large enough to

accommodate the network delays. On the other hand, it should be small enough
so that chances of attacks are less.
 The third approach that of challenge/response requires overhead of handshake
before transmission and is hence not suitable for connectionless applications.
Connectionless applications are basically faster applications that usually avoid
overhead of handshakes.

Symmetric encryption based mutual authentication approaches:

 The symmetric encryption methods are used to provide mutual authentication to the
two users.
 They usually involve a trusted third party termed as key distribution centre (KDC)
who is responsible for key distribution.
 It is assumed that each participating user or communicating party shares a master
secret key with KDC (Figure 2).
 The secure communication between any two users or parties is done by encrypting the
data packets using shared symmetric key that has short lifetime. It is termed as session
key (Figure 2).
 The session key is usually generated by KDC. It is encrypted by master key (shared
between KDC and communicating party) and is distributed to both the communicating
parties.
 In this section, three such schemes namely, Needham and Schroeder [4], Denning [5-
6] and KEHN [7] are discussed. This discussion also serves as initial platform for a
well known KDC based authentication protocol known as Kerberos.
 KDC

Master key Master key

(KA) (KB)
Session key
A B
(KAB or KS)

Figure 2 A two level hierarchy of symmetric keys.

Note: In this unit KA (or KB) refers to shared key between A (or B) and KDC whereas in public key encryption
methods in other units KA (or KB) refers to private key of A (or B).

))
D
A
¦¦ I
(K
S
B
K
¦¦ E

KDC
1
¦¦ N
¦¦ N
1
B
D

B
¦¦ ID
¦¦ I
(K
S

A
ID
A
K
)E
(2

(1)

A B
(3) E K b (K S ¦¦ ID A )

(4)EKS (N2 )

(5)KS ( f (N2 ))

Figure 3 Needham and Schroeder method

Needham and Schroeder method:

The steps (1 – 5) in Needham and Schroeder method (Figure 3) are as follows:
 A requests KDC for a new session key between A & B (indicated via their
identifiers IDA & IDB). A nonce is kept in request to prevent reply of request and
to indicate that this is fresh request.
 A decrypts the response given by KDC using shared master key (KA). From the
response, A is able to get session key (KS) generated by KDC and is also able to
verify nonce N1 (which means this is response against its own request). A is unable
to decrypt the part of response encrypted using KB. It hence forwards this part to
B.
 B decrypts the message sent by A (using master key KB) and is able to extract the
session key (KS). Thus, now both A & B possess some secret key (KS). Presence
of IDA, ensures that the message/request is originated by A.
 B selects a new nonce and encrypts it using recently acquired session key (KS).
[Step 4]. A decrypts the message and is able to get nonce. A applies function f to
this nonce and encrypts it using KS and send it to B. [Step 5]. Step 4 and 5 assures
A and B mutually that they now possess session key and are now ready for secure
communication using this session key.
 Needham and Schroeder protected key generation and sharing has an issue. If an
adversary is able to compromise an old session key between A and B then he
impersonates A and can replay message 3 to B. B as usual, extracts the session
key and puts a new nonce encrypted using this old session key. Adversary decrypts
message 4 and sends message 5 to B. B verifies the message and enters into
communication with adversary using this old session key.

Denning’s improvement:
 Denning [5][6] suggested incorporating timestamp in steps 2 and 3 using
distributed clock mechanism to overcome the weakness of Needham and
Schroeder protocol. The entire communication is shown in Figure 4:

))
¦¦ T
D
A
¦¦ I
(K
S

KDC
B
K
¦¦ E
¦¦ T

B
¦¦ ID
D
B
¦¦ I

A
D
(K
S

(1)I
A
K
E
(2)

A B
(3)EKB (KS ¦¦ IDA ¦¦ T)

(4)EKS (N1 )

(5) K S f ( N1 )
Figure 4 Denning’s improvement

 Time stamps in this protocol ensures:

(i) Fresh message exchange
(ii) As the time stamps are communicated using encryption, the adversary who is
in possession of old session key is not able to forge the time stamp and hence
the replay of message 3 will be treated as useless due to wrong time stamp.
 The Denning protocol may face problem if the distributed clocks become
unsynchronized.
 To overcome this problem, the communicating parties may regularly check their
clock with that of KDC or the hand shaking messages may involve nonce along
with time stamps.

An improvement to both of the above protocols is given by KEHN [7] is shown in

Figure 5.
 b
b )¦
¦N
et ¦ T
ck S ¦
Ti A ¦¦ K
(ID
KDC

(2)
B
K
E

ID B
) ¦¦
¦¦ T
b

¦¦ N b
S
¦¦ K

¦¦ E K
a
¦¦ N

B
(ID
B
(ID

A
¦¦ N
A

A B
K
E

a
¦¦ T b
(3)

(1) ID A ¦¦ N a

)
(4)Ticket ¦¦ EK S (N b )

Figure 5 KEHN’s improvement

 A initiates the communication and sends message containing selected nonce Na to

B. This nonce is returned to A via KDC which ensures that communication is
fresh.
 B appends timestamp to A’s message and forwards it in encrypted form to KDC
indicating that a session key between A and B is required.
 KDC creates a ticket (encrypted IDA, session key (KS) and timestamp (Tb)) and
adds other information for A (IDB, Na, KS and Tb).
 Upon receipt of message 3, A extracts session key (KS), confirms that this is fresh
and creates message 4 containing ticket and encrypted nonce of B (Nb).
 Message 4 provides securely the session key to B via associated ticket. It also
ensures B that A is in possession of session key.
 An important aspect of this protocol is that the unexpired ticket may still be used
again by A to derive a new session key directly without involving KDC.
 The expiry of ticket is checked by B (for TB) using its own clock and hence no
synchronization of clocks is required.

Public encryption key based mutual authentication approaches:

 A compact public key based protocol that uses timestamps is shown in Figure 6.
 The protocol uses central Authentication Server (AS) for distributing public key
certificates not for key distribution.
 As the session key is chosen by A, AS has no idea about it and this ensures that
no other party except A and B has key.
 This protocol requires synchronization of clocks.
 )
te B ¦¦ T
u
tif B ¦¦ P
B
ID
ica
AS (
AS

r
Pr

e
E
C
A T ) ¦¦
ate A ¦¦

B
ID
fic Pu
¦
Ce DA ¦

A
D
)I
S (I

(1
rti
A
Pr
)E

A B
(2

(3) Certificate A ¦¦ Certificate B ¦¦ EPuB (E PrA (KS ¦¦ T ))

Pu = Public key
Pr = Private key

Figure 6 Public key encryption protocol that uses timestamps

 Another protocol (shown in Figure 8.7) proposed by Woo and Lam [8], does away
with clock synchronization issues and uses only nonces.
(5)
E Pr KDC Cer

KDC
( ID A fica
B B)
Pu

(4)

¦¦ P te A
t
ID A
rtif B ¦¦

i
u A)
e
Ce DC (ID

B
t

¦¦ I
ID
ica

DB

¦¦ E P
A ¦¦
K

¦¦ E P
Pr

ID
E

uB
(2)

( E Pr KD
(1)

KD u
C
(N a

C
(N a
)

(3)E ( N ¦¦ ID )
¦¦ K S

A Pu a BA
B
(6)EPu A ( EPrKDC ( N a ¦¦ K S ¦¦ IDB ) ¦¦ Nb ))
¦¦ ID
B
))

(7)EKS ( Nb )

Figure 7 Woo and Lam protocol for Sharing Session Keys

 Steps involved are briefly explained as:
(1) Request of A to KDC.
(2) KDC gives B’s public certificate to A, A extracts public key of B.
(3) A sends nonce Na encrypted using B’s public key.
 (4) B encrypts this nonce using KDC’s public key and forwards A’s request to
KDC.
(5) KDC provides A’s certificate to B along with encrypted session key bound to
Na. The encryption with PuB ensures that only B is able to extract the encrypted
session key.
(6) The encrypted session key bound with Na is forwarded by B to A. B also puts
its nonce (Nb) and encrypts the entire message.
(7) A retrieves session key and acknowledge B by encrypting Nb with this session
key.
 The authors later found a flaw in this protocol and suggested use of IDA by KDC
in step 5 i.e., session is bound not only to nonce, NA but also to user IDA.
 Thus, pair {IDA, Na} uniquely identifies request of A for session key.

II. Authentication of only one side i.e., one way authentication:

 In some cases authentication is required in only one direction i.e., receiver requires
guarantee that the message is from the particular sender.
 One such system of that requires one way authentication is E-mail system which
has following issues:
(i) Sender and receiver are not necessarily online at the same time.
(ii) The header of e-mail is not encrypted because the e-mail is forwarded by
intermediate systems in store and forward manner (using SMTP) after reading
and understanding the information contained in header.
(iii)The message contained in e-mail can be encrypted for ensuring confidentiality
and privacy.
 Both symmetric and asymmetric encryption is used for enhancing security in e-
mail system.

Use of symmetric encryption for one way authentication

Assumptions:
(1) Presence of key distribution centre (KDC) who shares symmetric secret key with
each participant.
(2) Session key is generated by KDC and is supplied to communicating participants.
 In this method, KDC encrypts the session key along with ID of the
communicating party.
 Upon decryption, each party gets the session key and is able to verify the other
participant using ID.
))A
D
¦¦ I
S
(K

KDC
b
K
¦¦ E

1
¦¦ N
1
¦¦ N

M : Contents of E-mail
B
D

B
¦¦ ID
¦¦I
S
(K

A
a
K

ID
)E
(2

(1)

A B
(3) EKb (KS ¦¦ IDA ) ¦¦ EK S ( M )
Figure 8 Use of symmetric encryption
  This method does not protect against replays and use of timestamp may
improve the situation.

Use of public key encryption for one way authentication:

Using public key encryption, either confidentiality or authentication or both may be
provided as shown in Table 2. It is assumed that A is sender while B is receiver and B
knows A’s public key.

S.No. Property attained Method

1. Confidentiality EPuB ( KS )¦¦EKS (M )

2. Authentication M ¦¦EPrA ( H (M ))

3. Authentication and (i) EPuB (M ¦¦EPrA ( H (M ))

confidentiality (ii) M ¦¦EPrA ( H (M ))¦¦EPrAS (T ¦¦IDA¦¦PuA )

Digital Certificate
Table 2 Use of public key encryption

 In (2), another user (adversary) may capture the message, calculate new hash and
encrypt message using his private key and deliver it to receiver. This should not
be permitted. Hence message M should be encrypted (also in 3 (ii)).
 For encrypting message, one time session key may be used. This key is itself
encrypted using B’s public key before transmitting.
 M || signature (r, s) M' || signature (r', s')
Sender A Receiver B
Output H s’ r’ Pu G Pu A  y

r = (gk mod p) mod q w = (s’)-1 mod q

-1
s = [k (H(M) + xr)] mod q u1 = [H(M’)w] mod q
Signature = (r, s) u2 = (r’) w mod q
u1 u2
v=[ (g y ) mod p] mod q
Compare v = r’
H k Pu G PrA  x
Output true/false
Signature calculation
Signature verification

Global
Global Public
Public KeyKey Components
Components ( P u G ) :: Prime Prime numbers
numbers pp
and
and q;
q; aa primitive
primitive number
number hh and and generator
generator gg based
based upon
upon itit
Sender’s
Sender’s Private
Private Key:
Key: xx random
random or or pseudorandom
pseudorandom integer
integer
with
with 00 << xx << qq
x
M
M == message
message H(M)
H(M) == hash
hash of
of MM
Sender’s
Sender’s Public
Public Key:
Key: yy == ggx mod
mod pp
M’,
M’, r’,
r’, s’
s’ == received
received versoins
versoins of
of M,
M, r,r, ss
Sender’s
Sender’s Per-Message
Per-Message Secret
Secret Number
Number
kk == random
random or
or pseudorandom
pseudorandom integer
integer with
with 00 << kk << qq

Figure 9 DSS approach for digital signing

THE DIGITAL SIGNATURE STANDARD (DSS)

 Digital Signature Standard (DSS) is published by National Institute of Standards and
Technology (NIST) as Federal Information Processing Standard (FIPS 186).
 DSS involves hash calculation using Secure Hash Algorithm (SHA) while digital
signature using Digital Signature Algorithm (DSA).
 Though several improvements have been made to DSS, the original DSS algorithm is
discussed here.
 In comparison to RSA: DSS is used only for signing whereas RSA can also be used
for encryption or key exchange. For some prime number p, DSS out performs RSA
signatures.
 In RSA method, a hash of message is evaluated and is encrypted using private key of
sender. The encrypted message is send along with the message. Receiver is able to
decrypt the hash using public key and comparison of the decrypted hash with
calculated hash verifies the message authenticity and integrity.
 In DSS method, the hash is still calculated and is provided as input to the signature
function. The other inputs to the signature function are: (i) random number k generated
for this particular signature, (ii) sender’s private key ( PrA ) and (iii) set of global
parameters termed as PuG . The output of signature function consists of two values
termed as s and r. At receiver side, signature is verified by verification function. The
 hash of received message is calculated and is provided as input to verification
function. The other inputs to verification function are: (i) Signature (s and r), (ii)
sender’s public key ( Pu A ) and (iii) PuG . If output produced by verification function
is equal to r, the signature of sender is verified. As only the sender is in possession of
private key it is guaranteed that only he has put this signature.
 The digital signature algorithm (Figure 9) has three major components:
(1) Key Generation
The signing party (say A) generates key pairs and announces the public key along
with other global parameters ( PuG )
(i) The global parameters are selected as:
 Prime number p is selected such that its length lies between 512 to
1024 bits and is expressed in increments of 64 bits.
 Prime number q that divides (p-1) and is of 160 bit length.
 A primitive element in Zp is selected as h (1 < h < (p-1))
Then g is evaluated as:
g = h(p-1)/q mod p
(ii) Private key x is selected such 0 < x < q.
Public key is evaluated as:
y = gx mod p
(iii)A random per message secret number k is selected such that 0<k<q.
(2) Signing
Signature consists of calculating r and s, generated as:
r = (gK mod p) mod q
s = [k-1 (H(M) + x r)] mod q

(3) Verifying
(i) r and s are checked by receiver i.e. 0 < r < q and 0 < s < q.
(ii) Digest/hash of message is calculated (Assuming receiver knows the hashing
algorithm used by sender).
(iii)Receiver calculates V as
1 1
V  [( g h ( M ) s y rs ) mod p]mod q
(iv) If r is congruent to V, the sign is verified, else rejected.