UNIT -3

Principles of public key crypto systems - RSA algorithm - security of RSA - key management – Diffle-
Hellman key exchange algorithm - introductory idea of Elliptic curve cryptography – Elgamel encryption
- Message Authentication and Hash Function: Authentication requirements - authentication functions -
message authentication code - hash functions - birthday attacks – security of hash functions and MACS.

PUBLIC KEY CRYPTOGRAPHY

The development of public-key cryptography is the greatest and perhaps the only
true revolution in the entire history of cryptography. It is asymmetric, involving the
use of two separate keys, in contrast to symmetric encryption, which uses only one
key. Public key schemes are neither more nor less secure than private key (security
depends on the key size for both). Public-key cryptography complements rather than
replaces symmetric cryptography. Both also have issues with key distribution,
requiring the use of some suitable protocol. The concept of public-key cryptography
evolved from an attempt to attack two of the most difficult problems associated with
symmetric
encryption: 1.) key distribution – how to have secure communications in general
without having to trust a KDC with your key 2.) digital signatures – how to verify a
message comes intact from the claimed sender Public-key/two-key/asymmetric
cryptography involves the use of two keys:

35
  a public-key, which may be known by anybody, and can be used to encrypt
messages, and verify signatures
 a private-key, known only to the recipient, used to decrypt messages, and
sign
(create) signatures.
 is asymmetric because those who encrypt messages or verify signatures
cannot decrypt messages or create signatures

Public-Key algorithms rely on one key for encryption and a different but related
key for decryption. These algorithms have the following important characteristics:
 it is computationally infeasible to find decryption key knowing only algorithm
& encryption key
 it is computationally easy to en/decrypt messages when the relevant
(en/decrypt) key is known
 either of the two related keys can be used for encryption, with the other used for
decryption (for some algorithms like RSA)
The following figure illustrates public-key encryption process and shows that a public-
key encryption scheme has six ingredients: plaintext, encryption algorithm, public &
private keys, ciphertext & decryption algorithm.

The essential steps involved in a public-key encryption scheme are given below: 1.)
Each user generates a pair of keys to be used for encryption and decryption.
2.) Each user places one of the two keys in a public register and the other key is kept
private.
3.) If B wants to send a confidential message to A, B encrypts the message using A’s
public key.
4.) When A receives the message, she decrypts it using her private key. Nobody else
can decrypt the message because that can only be done using A’s private key
(Deducing a private key should be infeasible).
5.) If a user wishes to change his keys –generate another pair of keys and publish the
public one: no interaction with other users is needed.
Notations used in Public-key cryptography:
 The public key of user A will be denoted KUA.
 The private key of user A will be denoted KRA.
 Encryption method will be a function E.
 Decryption method will be a function D.
 If B wishes to send a plain message X to A, then he sends the cryptotext

36
 Y=E(KUA,X)
 The intended receiver A will decrypt the message: D(KRA,Y)=X
The first attack on Public-key Cryptography is the attack on Authenticity. An attacker
may impersonate user B: he sends a message E(KUA,X) and claims in the message to be B
–A has no guarantee this is so. To overcome this, B will encrypt the message using his
private key: Y=E(KRB,X). Receiver decrypts using B’s public key KRB. This shows the
authenticity of the sender because (supposedly) he is the only one who knows the private
key. The entire encrypted message serves as a digital signature. This scheme is depicted
in the following figure:

But, a drawback still exists. Anybody can decrypt the message using B’s public key. So,
secrecy or confidentiality is being compromised. One can provide both authentication and
confidentiality using the public-key scheme twice:

B encrypts X with his private key: Y=E(KRB,X) B encrypts Y with A’s public key:
Z=E(KUA,Y)
A will decrypt Z (and she is the only one capable of doing it): Y=D(KRA,Z)
A can now get the plaintext and ensure that it comes from B (he is the only one who
knows his private key): decrypt Y using B’s public key: X=E(KUB,Y).

37
 Applications for public-key cryptosystems:
1.) Encryption/decryption: sender encrypts the message with the receiver’s public
key.
2.) Digital signature: sender “signs” the message (or a representative part of the
message) using his private key
3.) Key exchange: two sides cooperate to exchange a secret key for later use in a
secret- key cryptosystem.

The main requirements of Public-key cryptography are:

1. Computationally easy for a party B to generate a pair (public key KUb, private key
KRb).
2. Easy for sender A to generate ciphertext:
3. Easy for the receiver B to decrypt ciphertect using private key:
4. Computationally infeasible to determine private key (KRb) knowing public key
(KUb)
5. Computationally infeasible to recover message M, knowing KUb and ciphertext C
6. Either of the two keys can be used for encryption, with the other used for
decryption:
M= DKRb[EKUb(M)]=DKUb[EKRb(M)]
Easy is defined to mean a problem that can be solved in polynomial time as a function of
input length. A problem is infeasible if the effort to solve it grows faster than polynomial
time as a function of input size. Public-key cryptosystems usually rely on difficult math
functions rather than S-P networks as classical cryptosystems. One-way function is one,
easy to calculate in one direction, infeasible to calculate in the other direction (i.e., the
inverse is infeasible to compute). Trap-door function is a difficult function that becomes
easy if some extra information is known. Our aim to find a trap-door one-way function,
which is easy to calculate in one direction and infeasible to calculate in the other direction
unless certain additional information is known.
Security of Public-key schemes:
 Like private key schemes brute force exhaustive search attack is always
theoretically possible. But keys used are too large (>512bits).
 Security relies on a large enough difference in difficulty between easy
(en/decrypt) and hard (cryptanalyse) problems. More generally the hard problem is
known, its just made too hard to do in practise.
 Requires the use of very large numbers, hence is slow compared to private
key schemes

RSA A LGORITHM
RSA is the best known, and by far the most widely used general public key
encryption algorithm, and was first published by Rivest, Shamir & Adleman of MIT
in 1978 [RIVE78]. Since that time RSA has reigned supreme as the most widely
accepted and implemented general-purpose approach to public-key encryption.
The RSA scheme is a block cipher in which the plaintext and the ciphertext are
integers between 0 and n- 1 for some fixed n and typical size for n is 1024 bits (or
309 decimal digits). It is based on exponentiation in a finite (Galois) field over
integers modulo a prime, using large integers (eg. 1024 bits). Its security is due to
the cost of factoring
38
 large numbers. RSA involves a public-key and a private-key where the public key is
known to all and is used to encrypt data or message. The data or message which has
been encrypted using a public key can only be decryted by using its corresponding
private-key. Each user generates a key pair
public and private key using the following steps:
 each user selects two large primes at random - p, q
 compute their system modulus n=p.q
 calculate ø(n), where ø(n)=(p-1)(q-1)
 selecting at random the encryption key e, where 1<e<ø(n),andgcd(e,ø(n))=1
 solve following equation to find decryption key d: e.d=1 mod ø(n) and0≤d≤n
 publish their public encryption key: KU={e,n}
 keep secret private decryption key: KR={d,n}

Both the sender and receiver must know the values of n and e, and only the receiver
knows the value of d. Encryption and Decryption are done using the following
equations. To encrypt a message M the sender:
– obtains public key of recipient KU={e,n}
– computes: C=Me mod n, where 0≤M<n To decrypt the ciphertext C the owner:
– uses their private key KR={d,n}
– computes: M=Cd mod n = (Me) d mod n = Med mod n
For this algorithm to be satisfactory, the following requirements are to be met.
a) Its possible to find values of e, d, n such that Med = M mod n for all M<n
b) It is relatively easy to calculate Me and C for all values of M < n.
c) It is impossible to determine d given e and n

The way RSA works is based on Number theory: Fermat’s little theorem: if p
is prime and a is positive integer not divisible by p, then ap-1 ≡ 1 mod p. Corollary:
For any positive integer a and prime p, ap ≡ a mod p.

Fermat’s theorem, as useful as will turn out to be does not provide us with
integers d,e we are looking for –Euler’s theorem (a refinement of Fermat’s) does.
Euler’s function associates to any positive integer n, a number φ(n): the number of
positive integers smaller than n and relatively prime to n. For example, φ(37) = 36
i.e. φ(p) = p-1 for any prime p. For any two primes p,q, φ(pq)=(p-1)(q-1). Euler’s
theorem: for any relatively prime integers a,n we have aφ(n)≡1 mod n. Corollary:
For any integers a,n we have aφ(n)+1≡a mod n Corollary: Let p,q be two odd primes
and n=pq. Then: φ(n)=(p-1)(q-
1) For any integer m with 0<m<n, m(p-1)(q-1)+1 ≡ m mod n For any integers k,m
with 0<m<n, mk(p-1)(q-1)+1 ≡ m mod n Euler’s theorem provides us the numbers d,
e such that Med=M mod n. We have to choose d,e such that ed=kφ(n)+1, or
equivalently, d≡e- 1mod φ(n)

An example of RSA can be given as, Select primes: p=17 & q=11 Compute n = pq
=17×11=187
Compute ø(n)=(p–1)(q-1)=16×10=160 Select e : gcd(e,160)=1; choose e=7
Determine d: de=1 mod 160 and d < 160 Value is d=23 since 23×7=161= 10×160+1

39
 Publish public key KU={7,187}
Keep secret private key KR={23,187} Now, given message M = 88 (nb. 88<187)
encryption: C = 887 mod 187 = 11
decryption: M = 1123 mod 187 = 88
Another example of RSA is given as,
Let p = 11, q = 13, e = 11, m = 7
n = pq i.e. n= 11*13 = 143
ø(n)= (p-1)(q-1) i.e. (11-1)(13-1) = 120
e.d=1 mod ø(n) i.e. 11d mod 120 = 1 i.e. (11*11) mod 120=1; so d = 11 public key
:{11,143} and private key: {11,143}
C=Me mod n, so ciphertext = 711mod143 = 727833 mod 143; i.e. C = 106
M=Cd mod n, plaintext = 10611 mod 143 = 1008 mod 143; i.e. M = 7

For RSA key generation,

– determine two primes at random - p, q

– select either e or d and compute the other

– means must be sufficiently large

– typically guess and use probabilistic test

Security of RSA
There are three main approaches of attacking RSA algorithm.
Brute force key search (infeasible given size of numbers) As explained before,
involves trying all possible private keys. Best defence is using large keys.
Mathematical attacks (based on difficulty of computing ø(N), by factoring modulus
N) There are several approaches, all equivalent in effect to factoring the product of
two primes. Some of them are given as:
– factor N=p.q, hence find ø(N) and then d
– determine ø(N) directly and find d
– find d directly

The possible defense would be using large keys and also choosing large numbers for p
and q, which should differ only by a few bits and are also on the order of magnitude
1075 to 10100. And gcd (p-1, q-1) should be small.

40
 D IFFIE -H ELLMAN KEY EXCHANGE
Diffie-Hellman key exchange (D-H) is a cryptographic protocol that allows two
parties that have no prior knowledge of each other to jointly establish a shared secret
key over an insecure communications channel. This key can then be used to encrypt
subsequent communications using a symmetric key cipher. The D-H algorithm
depends for its effectiveness on the difficulty of computing discrete logarithms.
First, a primitive root of a prime number p, can be defined as one whose powers
generate all the integers from 1 to p-1. If a is a primitive root of the prime number p,
then the numbers, a mod p, a2 mod p,..., ap-1 mod p, are distinct and consist of the
integers from 1 through p 1 in some permutation. For any integer b and a primitive
root a of prime number p, we can find a unique exponent

i such that .The exponent i is referred to as the

discrete logarithm of b for the base a, mod p. We express this value as dloga,p (b). The
algorithm is summarized below:

For this scheme, there are two publicly known numbers: a prime number q and an
integer α that is a primitive root of q. Suppose the users A and B wish to exchange a
key. User A selects a random integer XA < q and computes YA = αXA mod q.
Similarly,
user B independently selects a random integer XA < q and computes YB = αXB mod q.

41
 Each side keeps the X value private and makes the Y value available publicly to the
other side. User A computes the key as K = (YB)XA mod q and user B computes the
key
as K = (YA)XB mod q. These two calculations produce identical results. Discrete Log
Problem The (discrete) exponentiation problem is as follows: Given a base a, an
exponent b
and a modulus p, calculate c such that ab ≡ c (mod p) and 0 ≤ c < p. It turns out that this
problem is fairly easy and can be calculated "quickly" using fast-exponentiation. The
discrete log problem is the inverse problem: Given a base a, a result c (0 ≤ c < p) and a
modulus p,
calculate the exponent b such that ab ≡ c (mod p). It turns out
that no one has
found a quick way to solve this problem With DLP, if P had 300 digits, Xa and Xb have
more than 100 digits, it would take longer than the life of the universe to crack the
method.
Examples for D-H key distribution scheme: 1) Let p = 37 and g = 13.

Let Alice pick a = 10. Alice calculates 1310 (mod 37) which is 4 and sends that to Bob.
Let Bob pick b = 7. Bob calculates 137 (mod 37) which is 32 and sends that to Alice.
(Note: 6 and 7 are secret to Alice and Bob, respectively, but both 4 and 32 are known
by all.)
10 (mod 37) which is 30, the secret key.
7 (mod 37) which is 30, the same secret key.

2) Let p = 47 and g = 5. Let Alice pick a = 18. Alice calculates 518 (mod 47) which is 2
and sends that to Bob. Let Bob pick b = 22. Bob calculates 522 (mod 47) which is 28 and
sends that to Alice.
18 (mod 47) which is 24, the secret key.
22 (mod 47) which is 24, the same secret key

Man-in-the-Middle Attack on D-H protocol

Suppose Alice and Bob wish to exchange keys, and Darth is the adversary. The attack
proceeds as follows:
1. Darth prepares for the attack by generating two random private keys XD1 and XD2
and then computing the corresponding public keys YD1 and YD2.
2. Alice transmits YA to Bob.
3. Darth intercepts YA and transmits YD1 to Bob. Darth also calculates K2 = (YA)XD2mod
q.
4. Bob receives YD1 and calculates K1 = (YD1)XE mod q.
5. Bob transmits XA to Alice.
6. Darth intercepts XA and transmits YD2 to Alice. Darth calculates K1 = (YB)XD1 mod q.
7. Alice receives YD2 and calculates K2 = (YD2)XA modq.
At this point, Bob and Alice think that they share a secret key, but instead Bob and
Darth share secret key K1 and Alice and Darth share secret key K2. All future
communication between Bob and Alice is compromised in the following way:
1. Alice sends an encrypted message M: E(K2, M).

42
 2. Darth intercepts the encrypted message and decrypts it, to recover M. 3. Darth sends
Bob E(K1, M) or E(K1, M'), where M' is any message. In the first case, Darth simply
wants to eavesdrop on the communication without altering it. In the second case, Darth
wants to modify the message going to Bob. The key exchange protocol is vulnerable to
such an attack because it does not authenticate the participants. This vulnerability can
be overcome with the use of digital signatures and public-key certificates.

E C C (ECC)
EllipticLLIPTIC
curve cryptography (ECC) is an approach to public-key cryptography based
URVE RYPTOGRAPHY
on the algebraic structure of elliptic curves over finite fields. The use of elliptic curves
in cryptography was suggested independently by Neal Koblitz and Victor S. Miller in
1985. The principal attraction of ECC compared to RSA is that it appears to offer equal
security for a far smaller bit size, thereby reducing the processing overhead.
Elliptic Curve over GF(p)
Let GF(p) be a finite field, p > 3, and let a, b
4a3 + 27b2 ≡ 0 (mod p). An elliptic curve,

E(a,b)(GF(p)), is defined as the set of points (x,

equation
y2 ≡ x3 + ax + b (mod p), together with a special point, O, called the point at infinity.
Let P and Q be two points on E(a,b)(GF(p)) and O is the point at infinity.
• P+O = O+P = P

• If P = (x1,y1) then -P = (x1 ,-y1) and P + (-P) = O.

• If P = (x1,y1) and Q = (x2,y2), and P and Q are not O.

then P +Q = (x3 ,y3) where

x3 = ƛ 2 - x1 - x2
y3 = ƛ (x1 - x3) - y1 and 86
ƛ = (y2-y1)/(x2-x1) if P ≠ Q
ƛ = (3x12+a)/ 2y1 if P = Q

An elliptic curve may be defined over any finite field GF(q). For GF(2m), the curve has a
different form:- y2 + xy = x3 + ax2 + b, where b !=0.

Cryptography with Elliptic Curves

The addition operation in ECC is the counterpart of modular multiplication in RSA, and
multiple addition is the counterpart of modular exponentiation. To form a cryptographic
system using elliptic curves, some kind of hard problem such as discrete logarithm or
factorization of prime numbers is needed. Considering the equation, Q=kP, where Q,P
are points in an elliptic curve, it is “easy” to compute Q given k,P , but “hard” to find k
given Q,P. This is known as the elliptic curve logarithm problem. k could be so large as to
make brute- force fail.

43
 ECC Key Exchange
Pick a prime number p= 2180 and elliptic curve parameters a and b for the equation
y2 ≡ x3 + ax + b (mod p) which defines the elliptic group of points Ep(a,b). Select
generator point G=(x1,y1) in Ep(a,b) such that the smallest value for which nG=O be a
very large prime number. Ep(a,b) and G are parameters of the cryptosystem known to
all participants. The following steps take place:
• A & B select private keys nA<n, nB<n

• compute public keys: PA=nA×G, PB=nB×G

• Compute shared key: K=nA×PB, K=nB×PA {same since K=nA×nB×G }

an
ECC Encryption/Decryption As with key exchange system,
encryption/decryption system requires a point G and and elliptic group Ep(a,b) as
parameters. First thing to be done is to encode the plaintext message m to be sent as
an x-y point Pm. Each user chooses private key nA<n and computes public key
PA=nA×G. To encrypt and send a message to Pm to B, A chooses a random positive
integer k and produces the ciphertext Cm consisting of the pair of points Cm={kG,
Pm+kPb}. here, A uses B’s public key. To
decrypt the ciphertext, B multiplies the first point in the pair by B’s secret key and
subtracts the result from the second point Pm+kPb – nB(kG) = Pm+k(nBG) –
nB(kG) = Pm A has masked the message Pm by adding kPb to it. Nobody but A
knows the value of k, so even though Pb is a public key, nobody can remove the mask
kPb. For an attacker to recover the message, he has to compute k given G and kG,
which is assumed hard.
Security of ECC To protect a 128 bit AES key it would take a RSA Key Size of 3072
bits whereas an ECC Key Size of 256 bits.

Hence for similar security ECC offers significant computational advantages.

Applications of ECC:
 Wireless communication devices
 Smart cards
 Web servers that need to handle many encryption sessions
 Any application where security is needed but lacks the power,
storage and computational power that is necessary for our current

44
 cryptosystems

KEY MANAGEMENT
One of the major roles of public-key encryption has been to address the problem of
key distribution. Two distinct aspects to use of public key encryption are present.
The distribution of public keys.
Use of public-key encryption to distribute secret keys.

Distribution of Public Keys The most general schemes for distribution of public
keys are given below
PUBLIC ANNOUNCEMENT OF PUBLIC KEYS
Here any participant can send his or her public key to any other participant or
broadcast the key to the community at large. For example, many PGP users have
adopted the practice of appending their public key to messages that they send to
public forums.

Though this approach seems convenient, it has a major drawback. Anyone can forge
such a public announcement. Some user could pretend to be user A and send a public
key to another participant or broadcast such a public key. Until the time when A
discovers about the forgery and alerts other participants, the forger is able to read all
encrypted messages intended for A and can use the forged keys for authentication.

PUBLICLY AVAILABLE DIRECTORY

A greater degree of security can be achieved by maintaining a publicly available
dynamic directory of public keys. Maintenance and distribution of the public directory
would have to be the responsibility of some trusted entity or organization. It includes
the following elements:
1. The authority maintains a directory with a {name, public key} entry for each
participant.
2. Each participant registers a public key with the directory authority. Registration
would have to be in person or by some form of secure authenticated communication.

45
 3. A participant may replace the existing key with a new one at any time, either
because of the desire to replace a public key that has already been used for a
large amount of data, or because the corresponding private key has been
compromised in some way.
Participants could also access the directory electronically. For this purpose,
4.
secure, authenticated communication from the authority to the participant is
mandatory. This scheme has still got some vulnerabilities. If an adversary
succeeds in obtaining or computing the private key of the directory authority,
the adversary could authoritatively pass out counterfeit public keys and
subsequently impersonate any participant and eavesdrop on messages sent to
any participant. Or else, the adversary may tamper with the records kept by
the authority.

PUBLIC-K EY AUTHORITY
Stronger security for public-key distribution can be achieved by providing tighter
control over the distribution of public keys from the directory. This scenario assumes
the existence of a public authority (whoever that may be) that maintains a dynamic
directory of public keys of all users. The public authority has its own (private key, public
key) that it is using to communicate to users. Each participant reliably knows a public
key for the authority, with only the authority knowing the corresponding private key.
For example, consider that Alice and Bob wish to
communicate with each other and the following steps take place and are also shown in
the figure below:

46
 1.) Alice sends a timestamped message to the central authority with a request for
Bob’s public key (the time stamp is to mark the moment of the request)
2.) The authority sends back a message encrypted with its private key (for
authentication) –message contains Bob’s public key and the original message of Alice
– this way Alice knows this is not a reply to an old request;
3.) Alice starts the communication to Bob by sending him an encrypted message
containing her identity IDA and a nonce N1 (to identify uniquely this transaction)
4.) Bob requests Alice’s public key in the same way (step 1)
5.) Bob acquires Alice’s public key in the same way as Alice did. (Step-2)
6.) Bob replies to Alice by sending an encrypted message with N1 plus a new
generated nonce N2 (to identify uniquely the transaction)
7.) Alice replies once more encrypting Bob’s nonce N2 to assure bob that its
correspondent is Alice
Thus, a total of seven messages are required. However, the initial four messages need
be used only infrequently because both A and B can save the other's public key for
future use, a technique known as caching. Periodically, a user should request fresh
copies of the public keys of its correspondents to ensure currency.
PUBLIC-K EY CERTIFICATES
The above technique looks attractive, but still has some drawbacks. For any communication
between any two users, the central authority must be consulted by both users to get the
newest public keys i.e. the central authority must be online 24 hours/day. If the central
authority goes offline, all secure communications get to a halt. This clearly leads to an
undesirable bottleneck. A further improvement is to use certificates, which can be used to
exchange keys without contacting a public-key authority, in a way that is as reliable as if the
keys were obtained directly from a public-key authority. A certificate binds an identity to
public key, with all contents signed by a trusted Public-Key or Certificate Authority (CA). A
user can present his or her public key to the authority in a secure manner, and obtain a
certificate. The user can then publish the certificate. Anyone needed this user's public key
can obtain the certificate and verify that it is valid by way of the attached trusted signature.
A participant can also convey its key information to another by transmitting its certificate.
Other participants can verify that the certificate was created by the authority. This
certificate issuing scheme does have the following

47
 requirements:
1. Any participant can read a certificate to determine the name and public key of the
certificate's owner.
2. Any participant can verify that the certificate originated from the certificate authority
and is not counterfeit.
3. Only the certificate authority can create and update certificates.
4. Any participant can verify the currency of the certificate.

Application must be in person or by some form of secure authenticated

communication. For participant A, the authority provides a certificate of the form
CA = E(PRauth, [T||IDA||PUa]) where PRauth is the private key used by the authority
and T is a timestamp. A may then pass this certificate on to any other participant,
who reads and verifies the certificate as follows: D(PUauth, CA) = D(PUauth, E(PRauth,
[T||IDA||PUa]))
= (T||IDA||PUa) The recipient uses the authority's public key, PUauth to decrypt the
certificate. Because the certificate is readable only using the authority's public key,
this verifies that the certificate came from the certificate authority. The elements IDA
and PUa provide the recipient with the name and public key of the certificate's holder.
The timestamp T validates the currency of the certificate. The timestamp counters the
following scenario. A's private key is learned by an adversary. A generates a new
private/public key pair and applies to the certificate authority for a new certificate.
Meanwhile, the adversary replays the old certificate to B. If B then encrypts messages
using the compromised old public key, the adversary can read those messages. In this
context, the compromise of a private key is comparable to the loss of a credit card.
The owner cancels the credit card number but is at risk until all possible
communicants are aware that the old credit card is obsolete. Thus, the timestamp
serves as something like an expiration date. If a certificate is sufficiently old, it is
assumed to be expired.
One scheme has become universally accepted for formatting public-key certificates:
the
X.509 standard. X.509 certificates are used in most network security applications,
including IP security, secure sockets layer (SSL), secure electronic transactions (SET),
and S/MIME.

SECRETKEYD ISTRIBUTION WITH CONFIDENTIALITY AND AUTHENTICATION

48
It is assumed that A and B have exchanged public keys by one of the schemes described
earlier. Then the following steps occur:

1. A uses B's public key to encrypt a message to B containing an identifier of A (IDA)

and a nonce (N1), which is used to identify this transaction uniquely.
2. B sends a message to A encrypted with PUa and containing A's nonce (N1) as well as a
new nonce generated by B (N2) Because only B could have decrypted message (1), the
presence of N1 in message (2) assures A that the correspondent is B.
3. A returns N2 encrypted using B's public key, to assure B that its correspondent is
A.
4. A selects a secret key Ks and sends M = E(PUb, E(PRa, Ks)) to B. Encryption of this
message with B's public key ensures that only B can read it; encryption with A's
private key ensures that only A could have sent it.
5. B computes D(PUa, D(PRb, M)) to recover the secret key.
The result is that this scheme ensures both confidentiality and authentication in the
exchange of a secret key.

50
M ESSAGE A UTHENTICATION
Message authentication is a procedure to verify that received messages come
from the alleged source and have not been altered. Message authentication may also
verify sequencing and timeliness. It is intended against the attacks like content
modification, sequence modification, timing modification and repudiation. For
repudiation, concept of digital signatures is used to counter it. There are three classes
by which different types of functions that may be used to produce an authenticator.
They are:

Message encryption–the ciphertext serves as authenticator

Message authentication code (MAC)–a public function of the message and a
secret key producing a fixed-length value to serve as authenticator. This does not
provide a digital signature because A and B share the same key.
Hash function–a public function mapping an arbitrary length message into a
fixed- length hash value to serve as authenticator. This does not provide a digital
signature because there is no key.
MESSAGE ENCRYPTION:
Message encryption by itself can provide a measure of authentication. The analysis
differs for conventional and public-key encryption schemes. The message must have
come from the sender itself, because the ciphertext can be decrypted using his (secret
or public) key. Also, none of the bits in the message have been altered because an
opponent does not know how to manipulate the bits of the ciphertext to induce
meaningful changes to the plaintext. Often one needs alternative authentication
schemes than just encrypting the message.
Sometimes one needs to avoid encryption of full messages due to legal
requirements.
Encryption and authentication may be separated in the system architecture.

The different ways in which message encryption can provide authentication,

confidentiality in both symmetric and asymmetric encryption techniques is explained
with the table below:

51
M ESSAGE AUTHENTICATION CODE
An alternative authentication technique involves the use of a secret key to generate a
small fixed-size block of data, known as cryptographic checksum or MAC,
which is appended to the message. This technique assumes that both the

52
communicating parties say A and B share a common secret key K. When A has a message
to send to B, it calculates MAC as a function C of key and message given as: MAC=Ck(M)
The message and the MAC are transmitted to the intended recipient, who upon receiving
performs the same calculation on the received message, using the same secret key to
generate a new MAC. The received MAC is compared to the calculated MAC and only if
they match, then: 1. The receiver is assured that the message has not been altered: Any
alternations been done the MAC’s do not match. 2. The receiver is assured that the
message is from the alleged sender: No one except the sender has the secret key and
could prepare a message with a proper MAC. 3. If the message includes a sequence
number, then receiver is assured of proper sequence as an attacker cannot successfully
alter the sequence number. Basic uses of Message Authentication Code (MAC) are
shown in the figure:

There are three different situations where use of a MAC is desirable:

a message is broadcast to several destinations in a network (such as a military
If
control center), then it is cheaper and more reliable to have just one node responsible
to evaluate the authenticity –message will be sent in plain with an attached
authenticator.
If one side has a heavy load, it cannot afford to decrypt all messages –it will just
check the authenticity of some randomly selected messages.
Authentication of computer programs in plaintext is very attractive service as they
need not be decrypted every time wasting of processor resources. Integrity of the
program can always be checked by MAC.
MESSAGE AUTHENTICATION CODE BASED ON DES

53
The Data Authentication Algorithm, based on DES, has been one of the most widely
used MACs for a number of years. The algorithm is both a FIPS publication (FIPS PUB
113) and an ANSI standard (X9.17). But, security weaknesses in this algorithm have
been discovered and it is being replaced by newer and stronger algorithms. The
algorithm can be defined as using the cipher block chaining (CBC) mode of operation
of DES shown below with an initialization vector of zero.

The data (e.g., message, record, file, or program) to be authenticated are grouped into

contiguous 64-bit blocks: D1, D2,..., DN. If necessary, the final block is padded on the
right with zeroes to form a full 64-bit block. Using the DES encryption algorithm, E,
and a secret key, K, a data authentication code (DAC) is calculated as follows:

The DAC consists of either the entire block ON or the leftmost M bits of the block, with
16
≤ M ≤ 64 Use of MAC needs a shared secret key between the communicating
parties and also MAC does not provide digital signature. The following table
summarizes the confidentiality and authentication implications of the approaches
shown above.
HASH FUNCTION
A variation on the message authentication code is the one-way hash function.
As with the message authentication code, the hash function accepts a variable-size
message M as input and produces a fixed-size hash code H(M), sometimes called a
message digest, as output. The hash code is a function of all bits of the message and
provides an error- detection capability: A change to any bit or bits in the message
results in a change to the hash code. A variety of ways in which a hash code can be
used to provide message authentication is shown below and explained stepwise in the
table.

54
n is required.
In casesGrowing
where confidentiality
interest for techniques
is not required,
that avoid
methods
encryption
b and cishave
due ato reasons lik
e, Encryption
advantage oversoftware is encrypt
those that quite slow and may
the entire be covered
message in thatby
lesspatents. Also encryption
computation
hardware costs are not negligible and the algorithms are subject to U.S export control. A
fixed-length hash value h is generated by a function H that takes as input a message
of arbitrary length: h=H(M).
sends M and H(M)
authenticates the message by computing H(M) and checking the match

A
B
Requirements for a hash function: The purpose of a hash function is to produce a
“fingerprint” of a file, message, or other block of data. To be used for message

55
authentication, the hash function H must have the following properties
can be applied to a message of any size produces fixed-length output
Computationally easy to compute H(M) for any given M
H Computationally infeasible to find M such that H(M)=h, for a given h, referred to as
the
one-way property
Computationally infeasible to find M’ such that H(M’)=H(M), for a given M, referred
to as weak collision resistance.
Computationally infeasible to find M,M’ with H(M)=H(M’) (to resist to birthday
attacks), referred to as strong collision resistance.

Examples of simple hash functions are:

 Bit-by-bit XOR of plaintext blocks: h= D1⊕D2⊕…⊕DN
 Rotated XOR –before each addition the hash value is rotated to the left with 1
bit
 Cipher block chaining technique without a secret key.

56