m' = m k p ( N B ) + l mod NB =m,

0

Proposition 2.8 (properties of RSA protocol)

(1) The protocol encrypts and decrypts data correctly;

(2) A n adversary who overhears all transmitted messages and knows all

public information cannot recover the plaintext message i f P and Q are

large.

Public Key Cryptosystems 29

Proof. The first property follows from Proposition 2.7. To prove the

second property notice that the adversary knows only public parameters N

and d. In order to find c she must know the value q5 = ( P - l)(Q - 1) for

which, in turn, P and Q must be known. Generally speaking, P and Q can

be found by factoring N but it is a hard problem (Fact 2). Note, however,

that the choice of large random primes P and Q can be done in acceptable

0

time (Fact 1).

The one-way function y = xd mod N employed in RSA has a so-.called

“trapdoor” which allows for easy computation of the inverse function x =

$ mod N if the factorisation of N is known. (Indeed, it is easy to compute

j

q5 = ( P - 1)(Q - 1) and then c = d-™ mod q5.) If P and Q are unknown

then to compute the inverse function is practically impossible because to

find P and Q given N is very hard (Fact 2), i.e. the knowledge of P and Q

is a “trapdoor”. The trapdoor functions are employed in other branches of

cryptography, as well.

Notice that it is important for the RSA system that each user chooses

his own pair of primes P and Q, i.e. that all moduli N A , N g , N c , . . . b e

different (otherwise one user would be able to read encrypted messages

destined to another user). But it is not required for the second public

parameter d. The parameter d can be the same for all users. It is often

recommended to choose d = 3 (for correspondingly chosen P and Q), see

e.g. [Menezes et al. (1996)l. In this case encryption is maximally fast (it

requires only 2 modular multiplications).

Example 2.17 Suppose Alice wants to send Bob the message m = 15.

Let Bob™s parameters be

PB = 3, 11, N B = 33, d B = 3

QB =

(3 is coprime to ( ˜ ( 3 3= 20). Find cg using the extended Euclidean algo-

)

rithm: C B = 7 (check it: 3 . 7 mod 20 = 1). Encrypt m using Eq. (2.31):

mod 33 = 152.15 mod 33 = 27.15 mod 33 = 9 .

e=

Alice sends the number 9 to Bob over an open channel. Only Bob knows

cg = 7 so he decrypts by (2.32):

2

m = g7 mod 33 = (g2) .9™ . 9 mod 33 = 152 .15 ™ 9 mod 33 = 15.

˜

We can see that Bob has deciphered the message.

Basics of Contemporary Cryptography for IT Practitioners

30

The considered system is unbreakable if P and Q are large but has the

following imperfection: A sends a message to B by utilising B™s public

information (the numbers NB and d B ) . Adversary E cannot read the mes-

sages destined for B but she is able to send a message to B on behalf of

A, i.e. E can impersonate A. Surely, we need more complex protocols to

avoid this. It is interesting that one of the possible solutions may be based

entirely on the RSA scheme, as the following.

A wants to send B message m. First A computes the number e =

mCAmod N A . E cannot do that since C A is secret. Then A computes the

number f = e d B mod N B and sends f to B. B receives f and computes

sequentially u = f“” mod NB and w = udA mod NA.

As a result, B obtains the message w = m. As in the conventional

RSA system, E cannot recover the message but, in contrast to RSA, she

also cannot send a message on behalf of A (because she does not know the

secret C A ) .

Here we meet a new situation. B knows that the message was originated

by A as if it were signed by A. A virtually signs the message by encrypting it

with the use of her secret parameter C A . This is an example of the so-called

digital signature. The digital signature is one of the widely used inventions

of modern cryptography. It will be systematically studied in Chap. 4.

Problems and Exercises

+ 8, 3 - 8, 3 . 8 ,

2.1 Reduce the results of expressions 5, 16, 27, -4, -13, 3

3.8.5

(a) modulo 10,

(b) modulo 11.

2.2 Compute using fast modular exponentiation algorithms 28 mod 10,

37 mod 10, 7™™ mod 100, 757 mod 100.

2.3 Factor numbers 108, 77, 65, 30, 159.

2.4 Determine what pairs of numbers (25,12), (25,15), (13,39), (40,27)

are relatively prime.

2.5 Find values of Euler function ( ˜ ( 1 4 )(,˜ ( 2 0 ) .

2.6 Compute using the properties of Euler function ( ˜ ( 5 3 ) ,

(p(21), ( ˜ ( 1 5 9 ) .

2.7 Compute the quantities 313 mod 13, 524 mod 11, 317 mod 5 using the

Fermat theorem.

2.8 Compute the quantities 3™ mod 20, 214 mod 21, 21°7 mod 159 using

the Euler theorem.

Public Key Cryptosystems 31

2.9 Find using the Euclidean algorithm gcd(21,12), gcd(30,12),

gcd(24,40), gcd(33,16).

2.10 Using the extended Euclidean algorithm, find 2 and y in equations

+ 12y = gcd(21,12),

212

(a)

+ 12y = gcd(30,12),

(b) 302

+ 40y = gcd(24,40),

(c) 242

+ 163 = gcd(33,16).

(d) 332

2.11 Compute 3-l mod 7, 5-™ mod 8, 3-1 mod 53, 10-1 mod 53.

2.12 Write out all primes less than 100. Which of them are of the form

+

p = 2q 1, where q is also prime?

2.13 Find all relevant values for the parameter g in the Diffie-Hellman

system with p = 11.

2.14 Compute secret keys YA,YB and a corresponding common key ZAg

in the Diffie-Hellman system with parameters

X A = 5 , X B = 7;

(a) p = 23, g = 5 ,

X A = 5 , X B = 7;

= 19, g = 2,

(b) p

X A = 3, Xg = 4;

= 23, g = 7,

p

(c)

= 17, g = 3, X A = 10, Xg = 5;

(d) p

= 19, g = 10, X A = 4, X g = 8.

(e) p

2.15 For Shamir™s cipher with specified parameters p , C A , CB find missing

parameters and describe the process of transmitting message m from

A to B

(a) 19, C A = 5, CB = 7, m = 4;

p =

= 23, C A = 15, CB = 7, m = 6;

(b) p

= 19, CA = 11, cg = 5, m = 10;

(c) p

(d) = 23, CA = 9, cg = 3, m = 17;

p

= 17, C A = 3, CB = 13, m = 9.

(e) p

2.16 For EIGamal™s cipher with specified parameters p , g, cg, k find miss-

ing parameters and describe the process of transmitting message m

to user B

(a) p = 19, g = 2, C B = 5 , k = 7, m = 5 ;

(b) p = 23, g = 5, cg = 8, k = 10, m = 10;

(c) p = 19, g = 2, cg = 11, k = 4, m = 10;

(d) p = 23, g = 7, cg = 3, k = 15, m = 5;

(e) p = 17, g = 3, CB = 10, k = 5, m = 10.

2.17 For the RSA system with specified parameters PA, QA, dA find miss-

ing parameters and describe the process of transmitting message m

Basics of Contemporary Cryptography for I T Practitioners

32

to user A

(a) PA = 5, Q A = 11, d A = 3, m = 12;

(b) PA = 5, Q A = 13, d A = 5, m = 20;

(C) PA = 7, Q A = 11, d A = 7, m = 17;

(d) PA = 7, QA = 13, d A = 5, m = 30;

(e) PA = 3, QA = 11, d A = 3, m = 15.

2.18 The encrypted message e = 100 is sent to the RSA user with param-

eters N = 187, d = 3. Decrypt the message by breaking the RSA

system of the user.

Themes for Labs

2.19 Write and debug the set of program functions implementing the ba-

sic algorithms used in the cryptosystems studied: modular exponen-

tiation (azmod m), greatest common divisor (gcd(a, b ) ) , inversion

(x-' mod m).

2.20 Write a program implementing the Diffie-Hellman key agreement.

The following parameter values are recommended: p = 30803, g = 2.

Secret keys are to be randomly generated.

2.21 Write a program implementing the Shamir cipher. The number p =

30803 may be taken as a prime modulus. The other parameters are

to be randomly generated.

2.22 Write a program implementing the ElGamal cipher. The following

parameter values are recommended: p = 30803, g = 2. Private keys

and the other parameters are to be randomly generated.

2.23 Write a program implementing the RSA cipher for transmitting mes-

sages to users A or B. The following parameter values are recom-

mended: PA = 131, Q A = 227, PB = 113, Q B = 281, d A = d B = 3.

Chapter 3

Solving Discrete Logarithm Problem

Problem Setting

3.1

In order to construct a reliable cryptosystem one should take into account

the methods of disclosure the adversary can employ. This allows one to

choose cryptosystem parameters (e.g. the length of numbers) so that the

adversary™s methods become infeasible. In the present section, we shall

consider two such methods to give the reader some insight into this LLmys-

terious” field.

We have seen that many of the public-key ciphers are based on the

one-way function

y = a x modp (3.1)

and we know that given a and x the value of y can be computed with not

more than 2logz operations (Proposition 2.1). But finding x given a and

y, i.e. computing the discrete logarithm, is assumed to be a much more

complex problem.

As it was shown in the justification of Shamir cipher (see (2.23)), by

Fermat™s theorem, when exponentiating modulo a prime p exponents are

reduced modulo p - 1. Therefore it suffices to deal with only the exponents

x satisfying the inequality 0 _< x _< p - 1.

Denote by t, the number of multiplications needed for computation of y

in (3.1) given a and x and, for brevity, we shall call ty time of computation.

Time of exponentiation with the algorithms of Sec. 2.1 is not more than

2 log x and x < p. Hence

I210gp (34

ty

for any exponent x.

33

Basics of Contemporary Cryptography for IT Practitioners

34

Now proceed to the problem of finding 2 in (3.1) given u and y. First

estimate the complexity of the exhaustive search. In the exhaustive search,

we begin with u1 and check whether u1 = y. If it is not the case, check

whether u2 = y, u3 = y, and so on until ui = y is found (then z = i). On

average, it will require to multiply by u and check for equality ( p - 1)/2

times. So the time of exhaustive search

With the “baby-step giant-step” algorithm described below the time of

finding z is noticeably smaller:

and with the index calculus algorithm also described below this time is even

substantially smaller:

where c1, c2 are some positive constants.

To make the comparison more illustrative, express the time of compu-

tation through the bitlength of the numbers in (3.1). Denote the bitlength

of p by n. When making computations modulo p we have n x logp. There-

fore the order of complexity (time of computation) for the above mentioned

algorithms will be the following:

where M loosely denotes “proportional”.