<<

. 5
( 36 .)



>>


Theorem 2.5 Let a and b be positive integers. T h e n the integer (not
necessarily positive) numbers x and y exist such that

+ by = gcd(a, b) . (2.13)
ax

The extended Euclidean algorithm serves for finding gcd(a, b) and x, y
satisfying (2.13). Introduce three vectors U = ( u ˜ , u z , u ˜ =, w ˜ , w z , w ˜ ) ,
V) (
and T = ( t l ,t 2 , t 3 ) . The algorithm is written as follows.


Algorithm 2.2 EXTENDED EUCLIDEAN ALGORITHM.

Positive integers a, b, a 2 b.
INPUT:
OUTPUT: gcd(a, b), x and y satisfying (2.13).
v
u +- (b, 0 , l ) .
1. +- ( a , 1,O),
WHILE Z J # 0 DO
2. ˜
3. q +- u1 div vl;
4. T + ( ˜ mod v1, ˜2 - qv2,˜3 - ˜ 3 )
1 ;
U +- V , V + T.
5.
RETURN U = (gcd(a,b),x,y).
6.

Vector U contains the result.
Operation div in the algorithm is integer division

.
a div b = \a/b]

The proof of correctness of Algorithm 2.2 may be found in [Aho et al.
(1976); Knuth (1981)l.
Public Key Cryptosystems 19


Example 2.12 Let a = 28, b = 19. Find and y satisfying (2.13).
2

U 28 1 0
vu 1
19 0
TVU 9 1 -lq=l
T V U 1- 2 3 q = 2
T V 0 19-28qz9
Let us comment the presented schema. First, vector U is filled with numbers
(28,1,0) and vector V with (19,0,1) (these are the first two rows in the
schema). Vector T is computed (3rd row). After that the 2nd row becomes
vector U, 3rd row becomes vector V , and again vector T is computed
the
(4th row). The process continues until the first element of V turns to 0.
Then the next to last row holds the result. In our case gcd(28,19) = 1,
+
IC = -2, y = 3. Check up the result: 28. (-2) 1 9 . 3 = 1.
Consider one important application of extended Euclidean algorithm.
In many cryptographic schemes, it is required to find for specified numbers
c, m a number d < m such that
cd mod m = 1 . (2.14)

Notice that such d exists if and only if c and m are coprime.
Definition 2.6 A number d satisfying (2.14) is called the inverse of c
modulo m and often denoted c-l mod m.
The above notation for the inverse is quite natural since we can now
rewrite (2.14) as
cc-l mod m = 1.

Multiplication by c-l corresponds to division by c when operating modulo
m. By analogy, arbitrary negative powers modulo m can be introduced:
- (mod m) .
c = (c")-' = (c-I)"

Example 2.13 3 . 4 mod 11 = 1, therefore 4 is the inverse of 3 modulo
11. We can write 3-l mod 11 = 4. The number 5-2 mod 11 can be found
in two ways:
5-2 mod 11 = (5' mod ll)-' mod 11 = 3-1 mod 11 = 4 ,

5+2 mod 11 = (5-1 mod 11)2mod 11 = g2 mod 11 = 4 .
Basics of Contemporary Cryptography for IT Practitioners
20


-
In the second variant, we used the equality 5-l mod 11 = 9. Indeed, 5
9 mod 11 = 45 mod 11 = 1.

Let us show how one computes the inverse by use of extended Euclidean
algorithm. The equality (2.14) means that for some integer k

cd - km = 1. (2.15)

Taking into account that c and m are relatively prime rewrite (2.15) as

+ cd = gcd(m, c) , (2.16)
m(-k)

which agrees with (2.13) up to the names of variables. Therefore t o compute
c-l mod m, i.e. to find d, one can use the extended Euclidean algorithm
for solving Eq. (2.16). Notice that the value of k is not interesting for us,
so it makes sense not to compute the second element of vectors U , V, T.
Besides, if the value of d occurs negative, we must add to it the modulus
m because, by definition, a mod m belongs to the set {0,1,. . . , m - 1).

Example 2.14 Compute 7-l mod 11. We use the same form of presen-
tation as in Example 2.12.

11 0
71
4-1q=l
3 2q=1
1-3q=l
0 1lq=3.

We obtain d = -3 and since it is negative we add the modulus: -3+11 = 8,
i.e. 7-1 mod 11 = 8. Check the result: 7 . 8 mod 11 = 56 mod 11 = 1.

One of the main operations in public-key cryptography is modular expo-
nentiation. The idea of efficient algorithmic construction for exponentiation
has already been shown in Eqs. (2.5) and (2.6). It is possible to implement
this algorithm without storing in memory the series of numbers (2.5). Now
we give the description of the algorithm in a form suitable for its imme-
diate computer implementation. The name of the algorithm reflects the
fact that the bits of exponent are examined from right to left, i.e. from the
least-significant bit to the most-significant.
21
Public Key Cryptosystems


Algorithm 2.3 MODULAR EXPONENTIATION (FROM RIGHT T O LEFT).

Integer numbers a, z = (ztzt--1.. . z o ) ˜ , p.
INPUT:
OUTPUT: The number y = a" mod p .
1. yt1,sta.
FOR i = 0,1,. . . ,t DO
2.
IF zi= 1 THEN y t y . s modp;
3.
s t s . s modp.
4.
5. RETURNy.

To show how the algorithm works, trace the powers after each iteration.
Let z = 74 = (1001010)2 as in Example 2.1.

5 6
4
i:O12 3
z2:o 1 0 1 0 0 1
1 .2 .lo .lo .lo
y: a74
a2
s: 4
. .6
1 a64 .128
.
2 a32


There are situations where the following algorithm is more effective. It
differs from the previous algorithm in that the bits of exponent are ex-
amined from left to right, i.e. from the most-significant bit to the least-
significant.


MODULAR
Algorithm 2.4 EXPONENTIATION (FROM LEFT T O RIGHT).

Integer numbers a, z= (ztzt-1. . . zo)2, p.
INPUT:
OUTPUT: The number y = a" mod p.
1. y +- 1.
FOR i = t ,t - 1,.. . , 0 DO
2.
3. Y t Y * Y mod p ;
IF z = 1 THEN y t y . a modp.
i
4.
RETURN y.
5.

To assure oneself that Algorithm 2.4 computes exactly the same value
a Algorithm 2.3, trace again the powers after each iteration for x = 73.
s

i:654 3 2 1 0
1 0
1 0
zi:10 0
y: a a2 a4 a9 a18 a37 a74
Basics of Contemporary Cryptography for IT Practitioners
22


In fact, the number-theoretic results provided in this section will be
enough for the description of basic cryptographic algorithms and methods
in the rest of the book.



2.4 Shamir Cipher

This cipher attributed to Adi Shamir (see [Menezes et al. (1996)I) was one
of the first public-key systems that allowed two parties to securely exchange
messages over an open channel provided these parties had neither secure
channels nor secret keys and, perhaps, had never seen each other. (Recall
that Diffie-Hellman key-agreement scheme allows for creating only a secret
key but for secure message transmission a cipher is needed where this key
can be used.)
Proceed to description of the system. Let there be two users A and B
connected by an open communications line. User A wants to send a message
m to user B so that nobody but B could be able to learn its contents. A
randomly chooses a large prime number p and sends it to B. Then A selects
two numbers CA and dA such that


(2.17)


A keeps these numbers secret, they will not be transmitted. B , similarly,
selects two numbers CB and dB such that


cBdB mod ( p - 1) = 1, (2.18)


and also keeps them secret.
After that A transmits her message m using the three-step protocol
described below. If m < p (mis viewed as a number) then m is transmitted
at once. If m 2 p then the message is represented as a sequence of blocks
ml, m2,. . . ,mt, where all mi < p , and these blocks are transmitted by
turn. For secure transmission of each mi, it is better to randomly select
new pairs (CA, d A ) and (CB,
dB), otherwise the security of the system decays.
In present time such a cipher is commonly used as a transport for secret
keys whose values are less than p . So we shall focus on the case m < p .
The protocol is as follows.
Public K e y Cvyptosystems 23


Step 1 A computes

mod p
= mCA (2.19)
x1

and sends x 1 to B.
Step 2 B , upon the receipt of computes
z1,

22 = xyE mod p (2.20)
A.
and sends x2 back to
Step 3 A computes

= xgA mod p (2.21)
x3

and sends it to B.
Step 4 B, upon the receipt of computes
23,

x p mod p. (2.22)
=
24

<<

. 5
( 36 .)



>>