<<

. 4
( 36 .)



>>

Agreement

This cryptosystem was discovered in the middle 70-s by Whitfield Diffie
and Martin Hellman [Diffie and Hellman (1976)l and caused a revolution
in cryptography and its applications. It was the first system that allowed
to protect information without using secret keys transmitted over secure
channels. To show one of application schemes of such a system, consider
a communications network with N users, where N is large. Suppose we
are to organise secret communications for each pair of users. If we use an
ordinary key distribution scheme, then each pair of users must be supplied
(y)
with its own secret key which results in the total number of keys =
N(;--l)
2
Public Key Cryptosystems 13


So if we have 100 users then 5000 keys are required, if we ever have lo4
users then as many as 5 . lo7 keys must be supplied. We can see that under
the large number of users the system of supplying secret keys becomes very
bulky and expensive.
Diffie and Hellman have solved this problem by means of public dis-
tribution and computation of keys. Proceed to description of the system
suggested.
Denote the users of a network by A, B, C,. . . . For all the users the
following common parameters are chosen: a large prime number p and an
integer g, 1 < g < p- 1, such that all numbers from the set { 1 , 2 , . . . , p - 1)
.
might be represented as powers of g modulo p (i.e. gl,g2, . . , g p - l (modp)
be different numbers; such a g is called a generator and various approaches
are known for finding generators, one of which will be presented below).
The numbers p and g are assumed to be non-secret and known to all the
users.
.
XB,XC,. . , which are kept in
The users choose large numbers X A ,
secret and called their private keys (it is usually recommended t o make the
choice randomly with the aid of random number generators). Then every
user computes a corresponding number Y and sends it to the other users
in cleartext,

YA= g X A mod p ,
YB = gxB mod p ,
Yc = g x c mod p .
The numbers YA,YB,Yc, . .are called the public keys of the users. All
,

users' information is collected in Table 2.2.
Table 2.2 User keys in Diffie-Hellman system.

User Private key Public key




Suppose user A wants to securely communicate with user B and they
both have the public information from Table 2.2. User A asks B over an
open channel to start a communication session. Then A computes

ZAB = ( Y B ) ˜ " (2.10)
modp
Basics of Contemporary Cryptography for IT Practitioners
14


(nobody else can do that since X A is kept secret). Concurrently user B
computes
ZBA = ( Y A ) ˜ ˜ . (2.11)
mod p
ZAB = ZBA.
Proposition 2.2
Proof. Indeed,

(YB)˜” = (gxB)xA modp
modp
ZAg =
mod p = Z B A .
- gXAXBmodp ( Y A ) ˜ ”
=
-

(Here the first equality follows from (2.10), the second and fourth from
0
(2.9), and the last from (2.11).)
Review the main properties of the system:
(1) users A and B have obtained the same number Z = ZAB = ZBA that
was not transmitted over the open channel;
(2) Eve cannot compute ZAg since she does not know the secret numbers
X A and Xg (strictly speaking, she might try to find secret X A from
Y A (see (2.9)), however under large p , this is practically impossible
(requires millions years)).
Now users A and B can utilise ZAB as a secret key for encryption and
decryption of their data. Similarly, each pair of users can compute a key
which will be known only to that pair.
Let™s now discuss briefly the above mentioned problem of selecting the
generator g. The general method known so far relies on factorisation ofp-1.
But, on the one hand, if p is randomly chosen then, with high probability,
p - 1 will have a large prime divisor which is very difficult to determine.
On the other hand, in the system considered, the number p - 1 have to
have a large prime divisor since otherwise the Pohlig-Hellman algorithm
([Pohlig and Hellman (1978)l; see also [Menezes et al. (1996)l) would be
able to compute the discrete logarithm fast. So, under arbitrary chosen p ,
finding g is hard. Therefore it is often recommended t o use the following
approach. The prime number p is chosen so that

p=2q+1
where q is also prime. Then g may be any number for which the following
inequalities are satisfied:
l<g<p-1 and g q m o d p # l .
Public K e y Cryptosystems 15


+
Example 2.2 Let p = 23 = 2 . 11 1 ( q = 11). Now select 9. Let™s
try g = 3. Check it: 311 mod 23 = 1, which means that this value is
irrelevant. Take g = 5. Check it: 511 mod 23 = 22 # 1, that™s OK. So we
have chosen the parameters for the Diffie-Hellman system: p = 23, g = 5.
NOW each user chooses a secret number and computes a corresponding
public number. Let X A = 7, X B = 13. Compute YA = 5™ mod 23 = 17,
YB = 513 mod 23 = 21. Let A and B decided to establish a common
secret key. For that purpose A computes ZAB = 217 mod 23 = 10 and B
computes ZBA = 1713 mod 23 = 10. They have now the common key, 10,
which has never been transmitted over communications channel.



2.3 The Elements of Number Theory

Many cryptographic algorithms are based on the results of classical theory
of numbers. We shall consider the necessary minimum from the whole
theory. The classical theorems due to Fermat, Euler and a number of other
number-theoretic results will be given without proofs since they may be
found in almost any textbook on number theory, e.g. [Rosen (1992)l. The
readers familiar with number theory may wish to proceed immediately to
Sec. 2.4.

A positive integer p is prime if it has no divisors but 1
Definition 2.2
and itself.

Example 2.3 The numbers 11, 23 are prime; the numbers 27, 33 are
composite (27 can be divided by 3 and by 9, 33 has divisors 3 and 11).

Theorem 2.1 (fundamental theorem of arithmetic) A n y positive integer
can be represented as a product of prime numbers, this representation being
unique.

Example 2.4 27 = 3 . 3 . 3 , 33 = 3 . 1 1 .

Definition 2.3 Two numbers are said to be coprime (or relatively prime)
if they have no common divisors but 1.

Example 2.5 The numbers 27 and 28 are coprime (the have no common
divisors except l ) , the numbers 27 and 33 are not (they have common
divisor 3).
Basics of Contemporary Cryptography f o r IT Practitioners
16


Definition 2.4 (Euler (totient) function) Let there be given an inte-
ger N 2. 1. Euler function ' p ( N ) is the quantity of numbers among
1,2,3,. . . , N - 1 that are coprime to N .
Example 2.6
'p(10) =? 'p(12) =?
1, $ 7 A P , 5 , P,7, b, 8, m11
1, $73, P, $ 7 677, b,9,
'p (10) = 4 'p (12) = 4

(struck out are the numbers not coprime t o the argument).
Proposition 2.3 I f p is prime then 'p ( p ) = p - 1.
Proof. In the series 1,2,3,. . . , p - 1 all numbers are coprime to p since
p is prime and, by definition, is not divisible by any other number. 0
Let p and q be distinct primes (p # q). T h e n 'p ( p q ) =
Proposition 2.4
( P - 1)( 4 - 1).
In the series 1,2,. . . ,pq - 1 the numbers not relatively prime
Proof.
to pq are p , 2 p , 3p,. . . , ( q - l)p and q,2q,3q,. . . , ( p - 1)q. The total of
-+
such numbers is ( q - 1) ( p - 1). Hence, the number of coprimes to p q is
p q - 1 - ( p - 1) - (q - 1) = pq - q - p + 1 = ( p - 1) (q - 1).
< p . Then
Theorem 2.2 (Fermat) Let p be prime and 0 < a
mod p = 1.
ap-'

Example 2.7 p = 13, a = 2;
2
212 mod 13 = (22)2 . ((2')') mod 13 = 3 . 9 mod 13 = 1,
1O1O mod 1 = 10'. ((10')')'
1 mod 11= 1.1= 1.

Theorem 2.3 (Euler) Let a and b be coprime. Then
mod b = 1.
aV@)

The Fermat theorem is a special case of the Euler theorem when b is
prime.
Example 2.8

' P ( W = 4,
54 mod 12 = (5')' mod 12 = (1')' mod 12 = 1.
(21) = 2 . 6 == 12,
212 mod 21 = 2 4 . (24)2 mod 21 = 1 6 . 4 mod 21 = 1.
Public Key Cryptosystems 17


We shall need another theorem close to Euler™s.

# q, and k is an arbitray
Theorem 2.4 I f p and q are distinct primes, p
integer then

mod (pq) = a . (2.12)

Example 2.9 Let™s take p = 5, q = 7. Then pq = 35 and the Euler
function 4 3 5 ) = 4 6 = 24. Consider the case of Ic = 2, i.e. we shall raise
numbers to the power 2 . 2 4 + 1 = 49. We obtain

g4™ mod 35 = 9 , Xi4™ mod 35 = 2 3 ,

This is not surprise because each of the numbers 9 and 23 is coprime to the
modulus 35 and by the Euler theorem 924 mod 35 = 1, 2324 mod 35 = 1.
However, Theorem 2.4 remains right even for the following numbers:

lo4™ mod 35 = 10, 2849 mod 35 = 28,

whereas the Euler theorem cannot be applied to these numbers (the num-
bers 10 and 28 are not coprime to the modulus 35 and loz4 mod 35 = 15,
2824 mod 35 = 21).

Definition 2.5 Let a and b be two positive integers. The greatest com-
mon divisor of a and b, denoted gcd(a, b), is the biggest number c which
divides both a and b:

c = gcd(a, b) .

Example 2.10 gcd(l0,15) = 5; gcd(8,28) = 4.

To find the greatest common divisor one may use the following algorithm
which is known a the Euclidean algorithm.
s


Algorithm 2.1 EUCLIDEAN ALGORITHM.

Positive integers a, b, a _> b.
INPUT:
OUTPUT: The greatest common divisor gcd(a, b).
WHILE b # 0 DO
1.
2. r t a mod b, a + b, b + r.
3. RETURN a.
Basics of Contemporary Cryptography f o r IT Practitioners
18


Example 2.11 Let™s show how the Euclidean algorithm is used to com-
pute gcd(28,8):

a:2884
b: 840
r : 40

Here each column represents one iteration of the algorithm. The process
continues until b turns to zero. Then the value of a holds the result (4).

For many cryptographic systems to be considered in the book the so-
called extended Euclidean algorithm is important to which the following
theorem is associated.

<<

. 4
( 36 .)



>>