We see that v = T , hence, the signature is valid.

Basics of Contemporary Cryptography f o r IT Practitioners

52

Let us now discuss the differences of the Russian standard with respect

to the American. These are only the following.

(1) The length of q is 256 bits.

(2) As a hash function, Russian GOST R34.11-94 is used.

(3) In signature generation at Step 4, the parameter s is computed by the

+

formula s = (kh XC.)mod q.

(4) In signature verification at Step 8, u and u are computed by the

2

1

formulas u1= s . h- mod q, 2 ˜ 2 --T. h-l mod q.

1

=

Taking into account these differences one can easily rewrite the whole

scheme in “Russian” style. The proof of correctness is quite similar.

Problems and Exercises

Assume in all tasks that h(m)= m for all m.

4 1 Generate RSA signature on m given the following parameters:

.

P = 5, Q = 11, c = 27, m = 7;

(a)

P = 5, Q = 13, c = 29, m = 10;

(b)

P = 7, Q = 11, c = 43, m = 5;

(c)

P = 7, Q = 13, c = 29, m = 15;

(d)

P = 3, Q = 11, c = 7, m = 24.

(e)

4.2 For the specified public keys of RSA user, verify the authenticity of

signed messages

N = 55, d = 3: (7,28), (22,15), (16,36);

(a)

N = 65, d = 5: (6,42), (10,30), (6,41);

(b)

N

(c) = 77, d = 7: (13,41), (11,28), (5,26);

N = 91, d = 5: (15,71), (11,46), (16,74);

(d)

N = 33, d = 3: (10,14), (24,18), (17,8).

(e)

4.3 The users of some network apply the ElGamal signature with com-

mon parameters p = 23, g = 5. For the specified private key, find

corresponding public key and generate a signature for message m.

z = 11, k = 3, m = h = 15;

(a)

2 = 10, k = 15, m = h = 5;

(b)

z = 3, k = 13, m = h = 8;

(c)

z = 18, k = 7, m = h = 5;

(d)

z = 9, k = 19, m = h = 15.

(e)

Digital Signatures 53

4.4 For the specified public key (y) of the ElGamal system with common

parameters p = 23, g = 5, verify the authenticity of signed messages

(a) y = 2 2 : (15;20,3), (15;10,5), (15;19,3);

(b) y = 9: (5; 19,17), (7; 17,8), (6; 17,8);

(c) y = 10: (3; 17,12), (2; 17,12), (8;2 1 , l l ) ;

(d) y = 6: (5; 17, l), (5; 11,3), (5; 17,lO);

(e) y = l l : (15;7,1), (10;15,3), (15;7,16).

4.5 A community of DSA users have the common parameters q = 11,

p = 67, a = 25. Compute the public key (y) and generate a signature

for message m given the following secret parameters:

= 3, h = m = 10, k = 1;

(a) 2

x=8, h = m = l , k=3;

(b)

z = 5 , h = m = 5 , k=9;

(c)

x=2, h=m=6,k=7;

(d)

1 ˜ = 9 , h = m = 7k=5.

,

(e)

4.6 For the specified public keys of DSA users with common parameters

q = 11, p = 67, a = 25, verify the authenticity of signed messages

y = 14: (10;4,5), (10;7,4), (10;3,8);

(a)

y=24: (1;3,1), (1;9,1), (1;4,5);

(b)

(7; 7,4), (7; 9, a), (5; 9 , s ) ;

y = 40:

(c)

y = 22: (6; 9,5), (8; 8,3), (7; 4,7);

(d)

y = 64: (10;7,8), (7;7,3), (8;7,5).

(e)

Themes for Labs

4.7 Work out programs for generation and verification of RSA signa-

tures. The user parameters should be chosen on one™s own. To test

the signature verification program, the signed message (500,46514)

constructed under the public parameters N = 52891, d = 3 may be

used (assume that h(m) = m). This message should be declared au-

thentic. Any change in components of the signed message, with high

probability, should make the signature invalid.

4.8 Work out programs for generation and verification of ElGamal sig-

natures. The recommended values of common parameters are p =

31259, g = 2. The other parameters should be chosen on one™s

own. To test the signature verification program, the signed mes-

sage (500; 27665,26022) constructed under the public key y = 16196

54 Basics of Contemporary Cryptography for IT Practitioners

may be used (assume that h(m)= m). This message should be de-

clared authentic. Any change in components of the signed message,

with high probability, should make the signature invalid.

4.9 Work out programs for generation and verification of DSA signatures.

The recommended values of common parameters are q = 787, p =

31481, a = 1928. The other parameters should be chosen on one™s

own. To test the signature verification program, the signed message

(500; 655,441) constructed under the public key y = 12785 may be

used (assume that h(m) = m). This message should be declared

authentic. Any change in components of the signed message, with

high probability, should make the signature invalid.

Chapter 5

Cryptographic Protocols

The cryptographic methods considered in the previous chapters are often

used as tools for solving many other important problems. Not long ago some

of those problems seemed completely insoluble. For example, it seemed im-

possible to securely commit commercial transactions between remote par-

ticipants connected through open communications media, to make secure

money transfers over public channels, to conduct elections without personal

attendance and so on. Now all these problems can be solved by applying

cryptographic techniques. The methods involved are usually described in

a form of so-called cryptographic protocols. Several such protocols will be

presented in this chapter.

Notice that cryptographic algorithms not only offer new facilities to the

user (e.g. she can use a home computer and does not need to go to the bank

to make payments) but are able to provide a considerably higher level of

security compared to traditional mechanisms. For example, a traditional

paper bank note can be fabricated, and the acts of fabricating money occur

quite frequently, but by contrast, a digital bank note created with the use

of cryptographic methods is practically impossible to fabricate.

Quite often important problems are formulated in a form of amusing

game in order to make a solution “pure”, not overladen with technical

details. One of such problems, itmental poker”, is considered in the next

section.

Mental Poker

51

.

Consider a problem of playing a fair card game when the players are far

from each other and can communicate only via some public channel, e.g. ex-

change messages via electronic mail. We consider an extremely simplified

55

Basics of Contemporary Cryptography f o r IT Practitioners

56

version of the problem where there are only two players and three cards.

Nevertheless, all basic ideas will be demonstrated with obvious generalisa-

tions to other cases.

The problem is stated as follows. There are two players, Alice and Bob,

and three cards, a , ,f3, y. It is required to deal cards so that each player

gets one card and one card remains in the deck. Moreover, at the end of

the game the following conditions must be fulfilled:

(1) each player gets any of three cards with equal probabilities;

(2) each player knows only his/her card but not the card of the opponent

and/or the deck;

(3) in case of contention, a third party is able to judge who has cheated;

(4) anyone who overhears transmitted messages is unable to determine

which cards are dealt to.

Let's describe the protocol that allows to arrange such distribution of

cards. A preliminary stage is needed for selecting the parameters of proto-

col. The participants publicly choose a large prime p . Then Alice randomly

selects a number C A coprime to p - 1 and finds with the extended Gaussian

algorithm the number d A such that

Independently and similarly, Bob finds a pair such that

C B , dg

c ˜ mod ( ˜ - 1)= 1.

dp (5.2)

These numbers are kept secret by each player. Then Alice randomly

p,

selects three different numbers 8, 9 in the interval from 1 to p - 1, sends

them to Bob in clear and tells that & corresponds to a, j to p, to y

?

(e.g. 3756 denotes the ace).

After that we go to the second stage - the distribution of cards which

is described by the following steps.

Step 1 Alice computes the numbers

and sends u1, to Bob having shuffled them beforehand.

212, u 3

57

Cryptographic Protocols

Step 2 Bob receives the three numbers, selects randomly one of them, say,

up1 and sends it back to Alice. It will be the card dealt to her in the

game. Upon the receipt of up1Alice can compute

ii=udAm o d p = p d Am o d p = p l (5.3)

2

i.e. she learns that her hand is ,6 (she could learn this without com-

putation since she knows the correspondence between all u and the

i

cards).

Step 3 Bob continues. He computes for the two numbers left

v1 = uEB mod p (5.4)

= uzB mod p .

213 (5.5)

With probability 1/2 he rearranges v1 and 213 and sends them to Alice.

Step 4 Alice selects randomly one of the numbers received, say, v1, com-

putes the number

w1 = vfA modp (5.6)

and sends w1 to Bob. Bob computes

z = w p mod p (5.7)

and learns his card (his hand is &). Indeed,

wp- = & C A C B d A d B = & mod p .

= d a d s = uCedBda

- 1

v1

The card corresponding to remains in the deck.

212

Proposition 5 1 The described protocol satisfies all requirements t o fair

.

distribution of cards.

Proof. We give only the idea of proof. Alice shuffles the numbers u1, up,

u3 prior to sending them to Bob. Then Bob selects one of these numbers

without any knowledge of what corresponds to what. If he selects a number

randomly, Alice gets any card with probability 1/3. Similarly, if Alice

selects one of the two remaining cards randomly (with equal probabilities)

then Bob gets the card which can be any card with probability 1/3. It is

plain that under these conditions, the card in the deck can also be any card