<<

. 11
( 36 .)



>>

= ( 6 2 . 2 2 mod 67) mod 11 = 24 mod 11 = 2 .

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

<<

. 11
( 36 .)



>>