School of Informatics and Robotics

Information Security
Instructor
Sobia Iqbal
 Table of Contents

Lecture Topics Covered Page #

Lecture No 1 3

Lecture No 2 17

Lecture No 3 27

Lecture No 4 41

Lecture No 5 50

Lecture No 6 60

Lecture No 7 69

Lecture No 8 84

Lecture No 10 91

Lecture No 11 96

Lecture No 12 112

Lecture No 13 120

Lecture No14 125

Lecture No 15 137
 Lecture 8: Asymmetric Key Ciphers

OUTCOMES: Asymmetric Key Ciphers: Principles of Public Key Cryptosystems, Algorithms (RSA,
Diffie- Hellman, ECC), Key Distribution

DIFFIE-HELLMAN 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.
 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 toBob.
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).
 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.

ELLIPTIC CURVE CRYPTOGRAPHY (ECC)

Elliptic curve cryptography (ECC) is an approach to public-key cryptography based 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,y) ᴄ GF(p) * GF(p) which satisfy the 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.
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 }

ECC Encryption/Decryption As with key exchange system, an 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
 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.
 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.
4. Participants could also access the directory electronically. For this purpose, 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 theauthority.

PUBLIC-KEY 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:
 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 thetransaction)
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-KEY 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
 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 ID A 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.
SECRET KEY DISTRIBUTION WITH CONFIDENTIALITY AND AUTHENTICATION
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.