3

PUBLIC KEY CRYPTOGRAPHY

MATHEMATICS OF ASYMMETRIC KEY CRYPTOGRAPHY: Primes – Primality
Testing – Factorization – Euler‘s totient function, Fermat‘s and Euler‘s Theorem -
Chinese Remainder Theorem – Exponentiation and logarithm - ASYMMETRIC KEY
CIPHERS: RSA cryptosystem – Key distribution – Key management – Diffie Hellman
key exchange - ElGamal cryptosystem – Elliptic curve arithmetic-Elliptic curve
cryptography.
3.1 Mathematics of Asymmetric Key Cryptography
3.1.1 Number Theory
 Number Theory plays an important role in encryption algorithm. It is a vast and
fascinating field of mathematics, sometimes called "higher arithmetic," consisting of
the study of the properties of whole numbers.

 Primes and Prime Factorization are especially important in number theory, as are a
number of functions including the Totient function.

 Cryptography is the practice of hiding information, converting some secret

information to not readable texts.

 Cryptography is the study of methods to send and receive the secret messages. In
general, we have a sender who is trying to send a message to receiver. There is also an
adversary, who wants to steal the message. We are successful if sender is able to
communicate a message to the receiver without adversary learning what the message
was.

 Applications of number theory in cryptography are very important in constructions of

public key cryptosystems.

 The most popular public key cryptosystems are based on the problem of factorization
of large integers and discrete logarithm problem in finite groups, in particular in the
multiplicative group of finite fields and the group of points on elliptic curve over
finite field.

3.2 Important concepts in Number Theory

3.2.1 Prime Numbers
 A positive integer p is said to be a prime if it has only two factors namely 1 and p
itself.
For Example: 2, 3, 5, 7, 11, 13, 17 are prime numbers. 4,6,8,9,10 are not.
 Prime numbers are central to number theory
 List of prime number less than 200 is:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103
107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199
3.2.2 Relatively Prime Numbers
  Two integers are relatively prime (or coprime) if there is no integer greater than
one that divides them both (that is, their greatest common divisor is one).
For example, 12 and 13 are relatively prime, but 12 and 14 are not.
3.2.3 Divisors
 A positive integer a is said to divide an integer b if there exist an integer c such
that b  a.c and written as a | b.
For Example, 2 |10 as 10 = 2.5 but 3 do not divide 10 as there does not exist any
integer c such that 10 = 3. C
3.2.4 Greatest Common Divisor
 Let a and b be two positive integers then an integer d is called greatest common
divisor of a and b if d | a and d | b i.e. d is common divisor of a and b. And if any
integer c is such that c | a and c | b then c | d, i.e. any other common divisor of a
and b will divide d it is denoted by d  (a, b)
 Conversely can determine the greatest common divisor by comparing their prime
factorizations and using least powers
For Example, 300=21x31x52 18=21x32 hence GCD (18, 300) = 21x31x50=6

Using Euclid's algorithm

 A much more efficient method is the Euclidean algorithm, which uses the division
algorithm in combination with the observation that the gcd of two numbers also
divides their difference.
gcd(a,0) =a
gcd (a, b) =gcd (b, a mod b)
 For example,
Program 1: Write C++ program to find GCD of two numbers using Euclidean algorithm
#include <iostream>
using namespace std;
// Recursive function to return gcd of a and b
int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a % b);

// Driver program to test above function

int main ()
{
 int a = 98, b = 56;
cout<<"GCD of "<<a<<" and "<<b<<" is "<<gcd(a, b);
return 0;
}

Output:

GCD of 98 and 56 is 14

3.3 Primality Testing

 A primality test is an algorithm for determining whether an input number is prime.
Among other fields of mathematics, it is used for cryptography. Unlike integer
factorization, primality tests do not generally give prime factors, only stating whether
the input number is prime or not.
The Fermat Test
 By Fermat’s Theorem, if n is prime, then for any a we have

an−1 = 1(mod n). This suggests the Fermat test for a prime: pick a random a
∈{1,...,n−1} a ∈ {1,...,n−1} and see if an−1=1 (mod n). If not, then n must be
composite.

However, we may still get equality even when n is not prime.

For example, take n = 561 = 3 × 11 × 17. By the Chinese Remainder Theorem

Z561=Z3×Z11×Z17
thus, each a ∈ Z* 561 corresponds to some

(x, y, z) ∈ Z∗3×Z∗11×Z∗17

By Fermat’s Theorem, x2 = 1, y10 = 1 and z16 =1. Since 2, 10, and 16 all divide 560, this
means (x, y, z)560= (1, 1, 1) in other words, a560 = 1 for any a ∈ Z∗561.

Thus, no matter what “a” we pick, 561 always passes the Fermat test despite being composite
so long as aa is coprime to n. Such numbers are called Carmichael numbers, and it turns out
there are infinitely many of them.

If a is not coprime to n then the Fermat test fails, but in this case, we may as well forgo tests
and recover a factor of n simply by computing gcd (a, n).

3.4 Factorization
  Prime Factorization (or integer factorization) is a commonly used mathematical
problem often used to secure public-key encryption systems. A common practice is to
use very large semi-primes (that is, the result of the multiplication of
two prime numbers) as the number securing the encryption.
3.4.1Fundamental Theorem of Arithmetic
 Any positive integer greater than one can be written uniquely in the following prime
factorization form where P1, P2…., Pk are primes and e1, e2…ek are positive integers.

Applications of factorization
 Greatest Common Divisor
 The GCD of two numbers, gcd (a, b). This value can also be found if we know
the factorization of a and b.

 Least Common Multiplier

 The least common multiplication, lcm (a, b), is the smallest integer that is
multiple of both a and b. using factorization, can also find lcm (a, b).

 It can be proved that gcd (a, b) and lcm (a, b) are related to each other as
shown below.

3.4.2 Factorization Methods

 Although there are several algorithms that can factor a number, none are capable of
factoring a very large number in a reasonable amount of time.
Trial Division Method
 It is the simplest and least efficient algorithm.
 The essential idea behind trial division tests to see if an integer n, the integer to be
factored, can be divided by each number in turn that is less than n. For example, for
the integer n = 12, the only numbers that divide it are 1, 2, 3, 4, 6, 12. Selecting only
the largest powers of primes in this list gives that 12 = 3 × 4 = 3 × 22.
  The algorithm 3.4.2 shows the pseudocode for this method. The algorithm has two
loops, outer and inner. The outer loop finds unique factors and the inner loop finds
duplicates of a factor.
 For example, 24=23*3. The outer loop finds the factors 2 and 3. The inner loop finds
that 2 is a multiple factor.
Algorithm 3.4.2 Pseudocode for trial-division factorization

 Example 1: Use the trial division algorithm to find the factors of 1233.

Solution
We run a program based on the algorithm and get the following result.
1233=32 * 137
3.4.3 Fermat Method
 The Fermat’s Factorization method is based on the representation of an odd integer as
the difference of two squares. For an integer n, we want a and b such as:
n = a2 - b2 = (a + b) (a - b)

where (a + b) and (a - b) are the factors of the number n

 Example:
Input: n = 6557
Output: [79,83]
Explanation:
For the above value, the first try for a is ceil value of square root of 6557,
which is 81.
Then,
 b2 = 812 - 6557 = 4, as it is a perfect square.
So, b = 2
So, the factors of 6557 are:
(a - b) = 81 - 2 = 79 &
(a + b) = 81 + 2 = 83.
3.4.4 Pollard p – 1 Method
 This method finds a prime factor p of a number based on the condition that p-1 has no
factor larger than a predefined value B, which is called bound.

 Algorithm 3.4.4 shows the pseudocode for pollard p - 1 factorization method.

Algorithm 3.4.4 Pseudocode for Pollard p – 1 factorization

Example
Use the Pollard p − 1 method to find a factor of 57247159 with the bound B = 8.
Solution
We run a program based on the algorithm and find that p = 421. As a matter of fact
57247159 = 421 × 135979. Note that 421 is a prime and p − 1 has no factor greater
than 8
421 − 1 = 22 × 3 × 5 × 7
3.4.5 Pollard's rho algorithm
 Pollard's rho algorithm is an algorithm for integer factorization. It was invented by
John Pollard in 1975. It uses only a small amount of space, and its expected running
 time is proportional to the square root of the size of the smallest prime factor of the
composite number being factorized.
 Given a positive integer n, and that it is composite, find a divisor of it.
 Example:
Input: n = 12;
Output: 2 [OR 3 OR 4]

Input: n = 187;
Output: 11 [OR 17]

Concepts used in Pollard’s Rho Algorithm

1. Two numbers x and y are said to be congruent modulo n (x = y modulo n) if

 their absolute difference is an integer multiple of n, OR,
 each of them leaves the same remainder when divided by n.
2. The Greatest Common Divisor is the largest number which divides evenly into each
of the original numbers.
3. Birthday Paradox: The probability of two persons having same birthday is
unexpectedly high even for small set of people.
4. Floyd’s cycle-finding algorithm: If tortoise and hare start at same point and move in a
cycle such that speed of hare is twice the speed of tortoise, then they must meet at
some point.

3.5 Fermat’s and Euler’s Theorem

 Two theorems that play important roles in public-key cryptography are Fermat's
theorem and Euler's theorem.
Fermat’s Theorem (Fermat’s Little Theorem)
 If p is prime and a is a positive integer not divisible by p, then
ap-1 ≡ 1 (mod p)
where p is prime and gcd (a, p) = 1
Example 1:
If a = 2 and p = 7, then 26 = 64, and 64 − 1 = 63 = 7 × 9 is thus a multiple of 7.
Example 2:
If a =7 and p = 19 solve using Fermat’s theorem
 a18 ≡ 1 mod P
a2 = 72 = 49 ≡ 11 mod 19
74 = 121 mod 19 = 7
78 = 74 * 74
= 7 * 7 = 49 mod 19 = 11
716 = 78 * 78
= 11 * 11 = 121 mod 19 = 7
718 = 716 * 72
= 7 * 11
= 77 mod 19
=1
Euler ‘s Totient Function

 Euler's totient function is a multiplicative function, meaning that if two numbers m

and n are relatively prime, then φ(mn) = φ(m)φ(n).
 This function gives the order of the multiplicative group of integers modulo n (the
group of units of the ring ℤ/nℤ).
 It is also used for defining the RSA encryption system.
 The Euler's totient function, or phi (φ) function is a very important number theoretic
function having a deep relationship to prime numbers and the so-called order of
integers.
 The totient φ(n) of a positive integer n greater than 1 is defined to be the number of
positive integers less than n that are coprime to n. φ(1) is defined to be 1.
 The following table shows the function values for the first several natural numbers:
Table 3.5 Some values of Euler’s Totient Function φ(n)
  Table 3.5 lists the first 15 values of φ(n). the value φ(1) is without meaning but is
defined to have the value 1.
 For the prime number p,
φ(p) = p-1
 Now, two prime numbers p and q with p ≠ q. Then we can show that, for n=pq.
φ(n) = φ(pq)= φ(p)* φ(q) = (p-1) * (q-1)
 For example, φ(10) = φ(5) * φ(2) = (5-1) * (2-1) = 4 * 1 = 4
φ(15) = φ(5) * φ(3) = (5-1) * (3-1) = 4 * 2 = 8
Euler’s Theorem
 Euler's theorem states that, “if p and q are relatively prime, then”, where φ
is Euler's totient function for integers. That is, is the number of non-negative numbers
that are less than q and relatively prime to q.
a(n) ≡ 1 (mod n)
 for any a, n where gcd (a, n) = 1
Example 1:
a=3, n= 10 prove Euler’s theorem
Solution
φ(n) = φ(10) => φ(p * q)
= φ(2) * φ(5 ) // 2 and 5 are relative prime numbers for 10
= (2-1) * (5-1) =4
= 34 mod 10
= 81 mod 10 = 1
Example 2:
a=2; n=11 prove Euler’s theorem
Solution
ø(11) = 10;
hence 210 = 1024 = 1 mod 11

3.6 Chinese Remainder Theorem (CRT)

 The Chinese Remainder Theorem is an ancient, which is developed in 3rd centuries
by Chinese mathematician Sun-tzu.
 The CRT is a result about congruences in number theory and its generalization in
abstract algebra.
  It enables one to solve simultaneous equation with respect to different moduli in
considerable generality.
Theorem
 Chinese Remainder Theorem: If m1, m2, .., mk are pairwise relatively prime
positive integers, and if a1, a2, .., ak are any integers, then the simultaneous
congruences
x ≡ a1 (mod m1),
x ≡ a2 (mod m2),
.
.
.
x ≡ ak (mod mk)
have a solution, and the solution is unique modulo m, where m = m1, m2⋅⋅⋅mk. That is
a unique solution x with 0 ≤ x ≤ m.
Algorithm
 Let m = m1, m2, ..., mk
 Let Mk = m / mk for all K = 1, 2, 3, … k
 For all K = 1, 2, 3, … k find integers 1 / K such Mk, Yk ≡ (1 mod mk)
Since gcd (Mk, mk) = 1
 Euclid’s extended algorithm can be used to find yk
 The integer x ≡ (a1 M1 y1 + a2 M2 y2 + ... + akMkYk) (mod M) is a unique solution.
Example 1:
x ≡ 1 (mod 4)
x ≡ 2 (mod 5)
x ≡ 4 (mod 7)
solve the value for x using Chinese Remainder Theoren.
Solution
m1 = 4 a1 = 1
m2 = 5 a2 = 2
m3 = 7 a3 = 4
Step 1:
m = m1 * m2 * m3
=4*5*7
m = 140
Step 2:
M1 = m/ m1 => 140/4 = 35
M2 = m/m2 => 140/5 = 28
M3 = m/m3 => 140/7 = 20
Step 3:
MkYk ≡ 1 (mod mk)
Put k=1
M1y1 ≡ 1(mod m1)
35y1 ≡ 1 (mod 4)
Put k = 2
M2y2 ≡ 1(mod m2)
28y2 ≡ 1 (mod 5)
Put k = 3
M3y3 ≡ 1(mod m3)
20y3 ≡ 1 (mod 7)

35y1 ≡ 1 (mod 4)
28y2 ≡ 1 (mod 5)
20y3 ≡ 1 (mod 7)
To find y1
35y1 ≡ 1 (mod 4)
gcd (Mk, mk)
gcd (35, 4)
gcd (4, 35 mod 4)
gcd (4, 3)
gcd (3, 4 mod 3)
gcd (3, 1) when n = 1
y1 = 3 gcd (m, n) = n
Similarly,
Find y2 and y3
Here, y2 = 2
y3 = 6
Step 4:
x = (a1 M1 y1 + a2 M2 y2 + a3M3Y3) (mod m)
 = ((1 * 35 * 3) + (2 * 28 * 2) + (4 * 20 * 6)) mod 140
= (105 + 112 + 480) mod 140
= 697 mod 140
x = 137

Example 2:
x ≡ 3 (mod 4)
x ≡ 2 (mod 3)
x ≡ 4 (mod 5)
solve the value for x using Chinese Remainder Theoren.
Solution
m1 = 4 a1 = 3
m2 = 3 a2 = 2
m3 = 5 a3 = 4
Step 1:
m = m1 * m2 * m3
=4*3*5
m = 60
Step 2:
M1 = m/ m1 => 60/4 = 15
M2 = m/m2 => 60/3 = 20
M3 = m/m3 => 60/5 = 12
Step 3:
MkYk ≡ 1 (mod mk)
Put k=1
M1y1 ≡ 1(mod m1)
15y1 ≡ 1 (mod 4)
Put k = 2
M2y2 ≡ 1(mod m2)
20y2 ≡ 1 (mod 3)
Put k = 3
M3y3 ≡ 1(mod m3)
12y3 ≡ 1 (mod 5)
 15y1 ≡ 1 (mod 4)
20y2 ≡ 1 (mod 3)
12y3 ≡ 1 (mod 5)
Find y1 =3
y2 =2
y3 = 3
Step 4:
x = (a1 M1 y1 + a2 M2 y2 + a3M3Y3) (mod m)
= ((3 * 15 * 3) + (2 * 20 * 2) + (4 * 12 * 3)) mod 60
= (135 + 80 + 144) mod 60
= 359 mod 60
x = 59

3.7 Exponentiation and Logarithm

3.7.1 Modular Exponentiation

 Modular exponentiation is a type of exponentiation performed over a modulus.

 It is useful in computer science, especially in the field of cryptography. The

operation of modular exponentiation calculates the remainder when an
integer b (the base) raised to the eth power (the exponent), be, is divided by
a positive integer m (the modulus).

 In symbols, given base b, exponent e, and modulus m, the modular

exponentiation c is: c = be mod m.

 From the definition of c, it follows that 0 ≤ c < m. For example, given b = 5, e =

3 and m = 13, the solution c = 8 is the remainder of dividing 53 = 125 by 13.

 Modular exponentiation can be performed with a negative exponent e by finding

the modular multiplicative inverse d of b modulo m using the extended Euclidean
algorithm.

 That is: c = be mod m = d−e mod m, where e < 0 and b ⋅ d ≡ 1 (mod m).

 Modular exponentiation similar to the one described above is considered easy to

compute, even when the integers involved are enormous.
  On the other hand, computing the modular discrete logarithm – that is, the task of
finding the exponent e when given b, c, and m – is believed to be difficult.

 This one-way function behaviour makes modular exponentiation a candidate for

use in cryptographic algorithms.

3.7.2 Discreate Logarithms

 In the mathematics of the real numbers, the logarithm logb a is a number x such
that bx = a, for given numbers a and b. Analogously, in any group G, powers bk can be
defined for all integers k, and the discrete logarithm logb a is an integer k such
that bk = a.

 In number theory, the more commonly used term is index: we can write x =
indr a (mod m) (read the index of a to the base r modulo m) for rx ≡ a (mod m) if r is
a primitive root of m and gcd(a, m) = 1.

 Discrete logarithms are quickly computable in a few special cases. However, no

efficient method is known for computing them in general.

 Several important algorithms in public-key cryptography base their security on the

assumption that the discrete logarithm problem over carefully chosen groups has no
efficient solution.

 Let G be any group. Denote its group operation by multiplication and its identity
element by 1. Let b be any element of G. For any positive integer k, the
expression bk denotes the product of b with itself k times:

 Similarly, let b-k denote the product of b−1 with itself k times. For k = 0, the kth power
is the identity: b0 = 1.

 Let a also be an element of G. An integer k that solves the equation bk = a is termed

a discrete logarithm (or simply logarithm, in this context) of a to the base b. One
writes k = logb a.

3.8 Asymmetric Key Ciphers

 Asymmetric cryptography, also known as public key cryptography, uses public and
private keys to encrypt and decrypt data.
  The keys are simply large numbers that have been paired together but are not identical
(asymmetric). One key in the pair can be shared with everyone; it is called the public
key.

3.8.1 Public Key Cryptography

 Symmetric cryptography was well suited for organizations such as governments,

military, and big financial corporations were involved in the classified
communication.

 With the spread of more unsecure computer networks in last few decades, a genuine
need was felt to use cryptography at larger scale.

 The symmetric key was found to be non-practical due to challenges it faced for key
management. This gave rise to the public key cryptosystems.

 The process of encryption and decryption is depicted in the following illustration −

Figure 3.1 Public Key Cryptosystem

The most important properties of public key encryption scheme are:

 Different keys are used for encryption and decryption. This is a property which
set this scheme different than symmetric encryption scheme.

 Each receiver possesses a unique decryption key, generally referred to as his

private key.
  Receiver needs to publish an encryption key, referred to as his public key.

 Some assurance of the authenticity of a public key is needed in this scheme to

avoid spoofing by adversary as the receiver. Generally, this type of cryptosystem
involves trusted third party which certifies that a particular public key belongs to
a specific person or entity only.

 Encryption algorithm is complex enough to prohibit attacker from deducing the

plaintext from the ciphertext and the encryption (public) key.

 Though private and public keys are related mathematically, it is not be feasible to
calculate the private key from the public key. In fact, intelligent part of any
public-key cryptosystem is in designing a relationship between two keys.

3.9 RSA Cryptosystem

 This cryptosystem is one the initial system. It remains most employed cryptosystem
even today. The system was invented by three scholars Ron Rivest, Adi
Shamir, and Len Adleman and hence, it is termed as RSA cryptosystem.

 We will see two aspects of the RSA cryptosystem, firstly generation of key pair and
secondly encryption-decryption algorithms.

Generation of RSA Key Pair

 Each person or a party who desires to participate in communication using encryption

needs to generate a pair of keys, namely public key and private key. The process
followed in the generation of keys is described below −

 Generate the RSA modulus (n)

 Select two large primes, p and q.

 Calculate n=p*q. For strong unbreakable encryption, let n be a large

number, typically a minimum of 512 bits.

 note ø(n) = (p-1) (q-1)

 Find Derived Number (e)

 Number e must be greater than 1 and less than (p − 1) (q − 1).

  There must be no common factor for e and (p − 1) (q − 1) except for 1.
In other words, two numbers e and (p – 1) (q – 1) are co-prime.

 Form the public key

 The pair of numbers (n, e) form the RSA public key and is made
public.

 Interestingly, though n is part of the public key, difficulty in factorizing

a large prime number ensures that attacker cannot find in finite time the
two primes (p & q) used to obtain n. This is strength of RSA.

 Generate the private key

 Private Key d is calculated from p, q, and e. For given n and e, there is

unique number d.

 Number d is the inverse of e modulo (p - 1) (q – 1). This means that d is

the number less than (p - 1) (q - 1) such that when multiplied by e, it is
equal to 1 modulo (p - 1) (q - 1).

 Calculate d, d ≡ e-1(mod ø(n))

 This relationship is written mathematically as follows –

 ed = 1 mod (p − 1) (q − 1)
 Public key PU = {e, n}
 Private key PR = {d, n}
 Figure 3.2 The RSA Algorithm

Encryption and Decryption

 To encrypt a message M the sender:

 Computes: C=Me mod N, where 0≤M<N
 To decrypt the ciphertext C the receiver
 Computes: M=Cd mod N
Example
 Select primes: p=17 & q=11
 Compute n = p × q =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×16+1
 Publish public key PU = {7, 187}
 Keep secret private key PR = {23, 187}
Encryption
 Given message (Plaintext) M = 88
887 mod 187 = [(884 mod 187) x 882 mod 187) x 881 mod 187)] mod 187
881 mod 187 = 88
882 mod 187 = 7744 mod 187 = 77
884 mod 187 = 59,969,536 mod 187 = 132
887 mod 187 = (88 x 77 x 132) mod 187
= 8,94432 mod 187
= 11

So, Ciphertext C = 11
Decryption
 M = 1123 mod 187
1123 mod 187 = [(111 mod 187) x (112 mod 187) x (114 mod 187) x
(118 mod 187) x (118 mod 187)] mod 187
111 mod 187 = 11
112 mod 187 = 121
114 mod 187 = 14641 mod 187 = 55
118 mod 187 = 2,14, 358, 881 mod 187 = 33
118 mod 187 = 2,14, 358, 881 mod 187 = 33
1123 mod 187 = (11 x 121 x 55 x 33 x 33) mod 187
= 79, 720, 245 mod 187
= 88
So, Plaintext M =88
RSA Analysis

 The security of RSA depends on the strengths of two separate functions. The RSA
cryptosystem is most popular public-key cryptosystem strength of which is based on
the practical difficulty of factoring the very large numbers.

 Encryption Function − It is considered as a one-way function of converting

plaintext into ciphertext and it can be reversed only with the knowledge of
private key d.

 Key Generation − The difficulty of determining a private key from an RSA

public key is equivalent to factoring the modulus n. An attacker thus cannot
use knowledge of an RSA public key to determine an RSA private key unless
 he can factor n. It is also a one-way function, going from p & q values to
modulus n is easy but reverse is not possible.

 If either of these two functions are proved non one-way, then RSA will be broken. In
fact, if a technique for factoring efficiently is developed then RSA will no longer be
safe.

 The strength of RSA encryption drastically goes down against attacks if the number p
and q are not large primes and/ or chosen public key e is a small number.

3.10 Key Management

 Key management refers to management of cryptographic keys in a cryptosystem.
Figure 3.4 illustrates the lifecycle of key management.

Fig. 3.4 Lifecycle of Key Management

 This includes dealing with the generation, exchange, storage, use, crypto-shredding
(destruction) and replacement of keys. Successful key management is critical to the
security of a cryptosystem.

 In cryptography it is a very tedious task to distribute the public and private key
between sender and receiver.

 If key is known to the third party (forger/eavesdropper) then the whole security
mechanism becomes worthless. So, there comes the need to secure the exchange of
keys.
  There are 2 aspects for Key Management:

 Distribution of public keys.

 Use of public-key encryption to distribute secret.

3.10.1 Distribution of Public Keys

 Several techniques have been proposed for the distribution of public keys which can
mostly be grouped into the categories shown.
 Public announcement
 Publicly available directory
 Public-key authority
 Public-key certificates
Public Announcement
 The point of public-key encryption is that the public key is public, hence any
participant can send his or her public key to any other participant, or broadcast the
key to the community at large. eg. append PGP keys to email messages or post to
news groups or email list.
 Figure 3.5 illustrates the public key distribution

Figure 3.5 Uncontrolled Public Key Distribution

 Its major weakness is forgery, anyone could pretend to be user A and send a public
key to another participant or broadcast such a public key. Until the forgery is
discovered they can masquerade as the claimed user.
Publicly Available Directory
 The user obtains greater security by registering keys with a public directory.
  The directory must be trusted with properties:
 The authority maintains a directory with a {name, public key} entry for each
participant.
 Each participant registers a public key with the directory authority.
 A participant may replace the existing key with a new one at any time because
the corresponding private key has been compromised in some way.
 Participants could also access the directory electronically. For this purpose,
secure, authenticated communication from the authority to the participant is
mandatory.
 Figure 3.6 illustrates the public key publication

Figure 3.6 Public Key Publication

 This scheme is clearly more secure than individual public announcements but still has
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.
 Another way to achieve the same end is for the adversary to tamper with the records
kept by the authority.
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.
  It requires users to know the public key for the directory, and that they interact with
directory in real-time to obtain any desired public key securely.
 Totally seven messages are required.
 Figure 3.7 illustrates the public key distribution Scenario
1. A sends a timestamped message to the public-key authority containing a request for the
current public key of B.
2. The authority responds with a message that is encrypted using the authority's private
key, PRauth Thus, A is able to decrypt the message using the authority's public key.
Therefore, A is assured that the message originated with the authority. The message
includes the following:
 B's public key, PUb which A can use to encrypt messages destined for B.
 The original request, to enable A to match this response with the corresponding
earlier request and to verify that the original request was not altered before
reception by the authority.
 The original timestamp, so A can determine that this is not an old message from
the authority containing a key other than B's current public key.

Figure 3.7 Public key distribution Scenario

3. A stores B's public key and also uses it to encrypt a message to B containing an
identifier of A (IDA) and a nonce (N1), which is used to identify this transaction
uniquely.
4. B retrieves A's public key from the authority in the same manner as A retrieved B's
public key.
5. At this point, public keys have been securely delivered to A and B, and they may begin
their protected exchange. However, two additional steps are desirable:
6. 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 (3), the
presence of N1 in message (6) assures A that the correspondent is B.
7. A returns N2, encrypted using B's public key, to assure B that its correspondent is A.
Public-Key Certificates
 A user must appeal to the authority for a public key for every other user that it wishes
to contact and it is vulnerable to tampering too.
 Public key certificates can be used to exchange keys without contacting a public-key
authority.
 Figure 3.8 illustrates the public key Certificate exchanges
 A certificate binds an identity to public key, with all contents signed by a trusted
Public- Key or Certificate Authority (CA).
 This can be verified by anyone who knows the public-key authorities public-key.
 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. We can
place the following requirements on this scheme:
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.
 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.

Figure 3.8 Public Key Certificates

3.10.2 Symmetric Key Distribution using Public Key Cryptography
 Once public keys have been distributed or have become accessible, secure
communication that thwarts eavesdropping, tampering, or both, is possible.
 The Public-key encryption provides for the distribution of secret keys to be used for
conventional encryption.
Simple Secret Key Distribution
 A generates a public/private key pair {PUa, PRa} and transmits a message to B
consisting of PUa and an identifier of A, IDA.
 B generates a secret key, Ks, and transmits it to A, encrypted with A's public key.
 A computes D(PRa, E(PUa, Ks)) to recover the secret key. Because only A can
decrypt the message, only A and B will know the identity of Ks.
 A discards PUa and PRa and B discards PUa.

Figure 3.9 Simple Secret Key Distribution

  Figure 3.9 illustrates the simple secret key distribution
 Here third party can intercept messages and then either relay the intercepted message
or substitute another message Such an attack is known as a man-in-the-middle
attack. Figure 3.10 shows the mam-in-the-middle attack.

Figure 3.10 Man-in-the-Middle Attack

Secret Key Distribution with Confidentiality and Authentication

 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.
 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.
 Figure 3.11 illustrates the secret key distribution

Figure 3.11 Secret Key Distribution

  A returns N2 encrypted using B's public key, to assure B that its correspondent is A.
 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.
 B computes D(PUa, D(PRb, M)) to recover the secret key.

A Hybrid Scheme
 Another way to use public-key encryption to distribute secret keys is a hybrid
approach.
 This scheme retains the use of a Key Distribution Center (KDC) that shares a secret
master key with each user and distributes secret session keys encrypted with the
master key.
 A public key scheme is used to distribute the master keys.
 The addition of a public-key layer provides a secure, efficient means of distributing
master keys.
3.11 Diffie-Hellman Key Exchange Algorithm
 The Diffie–Hellman key exchange or Key Agreement is a method of securely
exchanging cryptographic keys over a public channel.

 It was developed by Whitfield Diffie and Martin Hellman in 1976.

 This protocol allows two users to exchange a secret key over an untrusted
network without any prior secrets. Security of transmission is critical for many
network and Internet applications.

 A number of commercial products employ this exchange technique.

 The purpose of the algorithm is to enable two users to securely exchange a key
that can be used for subsequent encryption of messages. So, two persons can
talk in untrusted network.
 The D-H, Based on the difficulty of computing discrete logarithms of large
numbers.
 Suppose A and B wish to exchange a secret key, the following steps are
needed.
 o There are two publicly known numbers: one is prime number q and an integer
α that is primitive root of q.
o Suppose the user A and B wish to exchange a key.
o User A selects a random integer XA < q and
 computes YA = αxA mod q.
o Similarly, user B selects a random integer XB < q and
 computes YB = αxB mod q.
 Then user A computes the key as K= (YB)xA mod q
 User B computes K= (YA)xB mod q
 Then two calculations produce identical results.

Figure 3.12 The D-H Algorithm

Example 1:
• Choose global public elements
q=23, α = 9
• User A select value XA is 4
• Calculate public YA
 YA= αxA mod q
= 94 mod 23
= 6561 mod 23
YA = 6
• User B select value XB is 3
• Calculate public YB
YB = αxB mod q
= 93 mod 23
= 729 mod 23
YB = 16
 Now, exchange their public keys
 Figure 3.13 shows the exchange of keys

Figure 3.13 Diffie- Hellmam Key Exchange

After exchange their public keys, each can compute the common key.
 A compute K = (YB)xA mod q
= 164 mod 23
= 65536 mod 23
K=9
 B compute K = (YA)xB mod q
 = 63 mod 23
= 216 mod 23
K=9
Now A and B can talk securely
Example 2:
 users Alice & Bob who wish to swap keys:
 agree on prime q=353 and a=3
 select random secret keys:
 A chooses XA=97, B chooses XB=233
 compute respective public keys:
 YA=397 mod 353 = 40 (Alice)
 YB=3233 mod 353 = 248 (Bob)
 compute shared session key as:
 KAB= YBxA mod 353 = 24897 = 160 (Alice)
 KAB= YAxB mod 353 = 40233 = 160 (Bob)
Advantages
 The sender and receiver don’t need any prior knowledge of each other.
 Once the keys are exchanged, the communication of data can be done through an
insecure channel.
 The sharing of the secret key is safe.
Disadvantages
 The algorithm cannot be sued for any asymmetric key exchange.
 Similarly, it cannot be used for signing digital signatures.
 Since it doesn’t authenticate any party in the transmission, the Diffie Hellman key
exchange is susceptible to a man-in-the-middle attack.
Man-in-the-Middle Attack

Figure 3.14 Man-in-the-Middle Attack

1. Darth prepares by creating two private / public keys
 2. Alice transmits her public key to Bob
3. Darth intercepts this and transmits his first public key to Bob. Darth also calculates a
shared key with Alice
4. Bob receives the public key and calculates the shared key (with Darth instead of
Alice)
5. Bob transmits his public key to Alice
6. Darth intercepts this and transmits his second public key to Alice. Darth calculates a
shared key with Bob
7. Alice receives the key and calculates the shared key (with Darth instead of Bob)
Now, Darth can then intercept, decrypt, re-encrypt, forward all messages between
Alice & Bob
Applications
 Diffie-Hellman is currently used in many protocols, namely:
• Secure Sockets Layer (SSL)/Transport Layer Security (TLS)
• Secure Shell (SSH)
• Internet Protocol Security (IPSec)
• Public Key Infrastructure (PKI)

3.12 ElGamal cryptosystem

 In cryptography, ElGamal encryption is an public-key cryptosystem. It uses
asymmetric key encryption for communicating between two parties and encrypting the
message, which is based on the Diffie–Hellman key exchange algorithm.
 It is developed by Elgamal in 1984.
 The Elgamal algorithm consists of three components.
 Key Generation
 Encryption Algorithm
 Decryption Algorithm
Key Generation
 Like D-H algorithm, generate of global elements are a prime number q and α
 User A generate private/public key pair as follows:
 Generate a random integer XA, 1 < XA < q-1
 Compute their public key YA = α XA mod q
 A’s private key is XA; and public key {q, α, YA}
Encryption
 User B that has access to A’s public key can encrypt a message as follows
 Represent message M in range 0 ≤ M ≤ q-1
 Longer messages are sent as a sequence of blocks, with each block being an
integer less than q.
 Choose random integer k with 1 ≤ k ≤ q-1
 Compute one-time key K = (YA)k mod q
 Encrypt M as a pair of integers (C1, C2) where
 C1 = α k mod q; C2 = KM mod q
Decryption
 User A recovers the plaintext.
 Recover the key by computing K as K = (C1)XA mod q
 computing M as M = (C2 K-1) mod q
Example
 Alice generates a public/private key pair; Bob encrypts using Alice’s public key and
Alice decrypts using her private key
 Global elements q = 19, α = 10
Alice Generates a key pair as follows:
 Alice chooses XA=5
 Computes YA = α XA mod q => YA =105 mod 19
= 10000 mod 19
YA = 3
 Alice private key is 5; public key {q, α, YA}= {19, 10, 3}
Suppose Bob wants to send the message with the value M = 17, then
Encryption
 Bob choose K = 6
o k = (YA)k mod q => 36 mod 19
= 729 mod 19
k=7
 Calculate C1
o C1 = α k mod q = > 106 mod 19
= 1000000 mod 19
C1 = 11
  Calculate C2
o C2 = KM mod q => 7 * 17 mod 19
= 119 mod 19
C2 = 5
 Bob sends the ciphertext (11, 5)
Decryption
 Alice Calculates recover K = (C1)xA mod q = 115 mod 19 = 7
 Compute inverse K-1 = 7-1 = 11
 Finally, M = (C2 K-1) mod q = 5 *11 mod 19
= 55 mod 19
M= 17

3.13 Elliptic Curve Arithmetic

 Most of the products and standards that use public-key cryptography for
encryption and digital signatures use RSA.
 The key length for secure RSA use has increased over recent years, and this has
put a heavier processing load on applications using RSA. This burden has
ramifications, especially for electronic commerce sites that conduct large numbers
of secure transactions.
 The principal attraction of ECC, compared to RSA, is that it appears to offer equal
security for a far smaller key size, thereby reducing processing overhead.
3.13.1 Why the name Elliptic Curve?
 The mathematical properties of certain cubic equations that are today known as
elliptic curves were seen to be generalizations of those of conics.
 However, the advent of calculus helped highlight marked differences between
conics and elliptic curves. While conic sections can be parameterized by rational
functions, elliptic curves cannot be parameterized by rational functions.
 The simplest functions that can parameterize elliptic curves are elliptic functions
encountered in calculus as the inverses of so-called elliptic integrals.
 The Elliptic integrals are called so, as a typical example is the integral for the arc
length of an ellipse. Thus, the name elliptic curve.
3.13.2 Abelian Groups
  An abelian group G, sometimes denoted by {G, •}, is a set of elements with a binary
operation, denoted by •, that associates to each ordered pair (a, b) of elements in G an
element (a • b) in G, such that the following axioms are obeyed:
 Closure: If a and b belong to G, then a • b is also in G.
 Associative: a • (b • c) = (a • b) • c for all a, b, c in G.
 Identity element: There is an element e in G such that a • e = e • a = a for all a
in G.
 Inverse element: For each a in G there is an element a' in G such that a • a' =
a' • a = e.
 Commutative: a • b = b • a for all a, b in G.
 A number of public-key ciphers are based on the use of an abelian group. For
example, Diffie-Hellman key exchange involves multiplying pairs of nonzero integers
modulo a prime number q.
 The Keys are generated by exponentiation over the group, with exponentiation
defined as repeated multiplication. For example, ak mod q

mod q.
 To attack Diffie-Hellman, the attacker must determine k given a and ak;
 For elliptic curve cryptography, an operation over elliptic curves, called addition, is
used. Multiplication is defined by repeated addition. For example,

where the addition is performed over an elliptic curve. The Cryptanalysis involves
determining k given a and (a x k).
3.13.3 Elliptic Curves over Real Numbers
 Elliptic curves are not ellipses. They are so named because they are described by
cubic equations, similar to those used for calculating the circumference of an ellipse.
 In general, cubic equations for elliptic curves take the form
y2 + axy + by = x3 + cx2 + dx + e
where a, b, c, d, and e are real numbers and x and y take on values in the real
numbers. For our purpose, it is sufficient to limit ourselves to equations of the form
y2 = x3 + ax+ b
  Such equations are said to be cubic, or of degree 3, because the highest exponent they
contain is a 3. Also included in the definition of an elliptic curve is a single element
denoted O and called the point at infinity or the zero point, which we discuss
subsequently. To plot such a curve, we need to compute

 For given values of a and b, the plot consists of positive and negative values of y for
each value of x. Thus, each curve is symmetric about y = 0. Figures 3.15 shows two
examples of elliptic curves.

Figure 3.15 Examples of Elliptic Curve

3.14 Elliptic curve cryptography (ECC)

 Diffie-Hellman and RSA cryptographic methods are based on the creation of keys by
using very large prime numbers. Hence, key creation requires a lot computational
power.

 Elliptic curve cryptography (ECC) is a public key encryption technique based on

an elliptic curve theory that can be used to create faster, smaller, and more
efficient cryptographic keys.
  ECC generates keys through the properties of the elliptic curve equation instead
of the traditional method of generation as the product of very large prime
numbers.

 The technology can be used in conjunction with most public key encryption methods,
such as RSA and Diffie-Hellman.

 The ECC can achieve the same level of security with a 164-bit key that other systems
require a 1,024-bit key. Because ECC helps to establish equivalent security with lower
computing power and battery resource usage, it is becoming widely used for mobile
applications. The use of elliptic curves in cryptography was suggested independently
by Neal Koblitz and Victor S. Miller in 1985 and elliptic curve cryptography
algorithms entered wide use around 2004.

3.14.1 How Does ECC work?

 An elliptic curve is the set of points that satisfy a specific mathematical equation. The
equation for an elliptic curve looks like this y2=x3+ax+b and is being represented
graphically like the image below.

Figure 3.16 Elliptic Curve

 Multiplying a point on the curve by a number will produce another point on the curve,
but it is very difficult to find what number was used, even if you know the original
point and the result.
 The Equations based on elliptic curves have a characteristic that is very valuable for
cryptography purposes: they are relatively easy to perform, and extremely difficult to
reverse.

 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, we need to find a "hard problem"
corresponding to factoring the product of two primes or taking the discrete logarithm.

 Consider the equation Q = kP where Q, P Ep (a, b) and k < p. It is relatively easy to

calculate Q given k and P, but it is relatively hard to determine k given Q and P. This
is called the discrete logarithm problem for elliptic curves.

 Consider the group E23 (9, 17). This is the group defined by the equation y2 mod 23 =
(x3 + 9x + 17) mod 23. What is the discrete logarithm k of Q = (4, 5) to the base P =
(16.5)? The brute-force method is to compute multiples of P until Q is found. Thus,

P = (16, 5); 2P = (20, 20); 3P = (14, 14); 4P = (19, 20); 5P = (13, 10); 6P = (7, 3); 7P
= (8, 7); 8P (12, 17); 9P = (4, 5).

Because 9P = (4, 5) = Q, the discrete logarithm Q = (4, 5) to the base P = (16, 5) is k

= 9. In a real application, k would be so large as to make the brute-force approach
infeasible.