ñòð. 9 |

Begin the third step of the algorithm. For ease of exposition, denote

the logarithms of the numbers p l , p 2 , p3 from S by u1, u2, u3, respec-

tively, e.g. u3 = log,, 5 mod 47. For the equations checked with a J at the

previous step, turn to the logarithms and construct a system

(3.15)

(3.16)

(3.17)

(3.18)

We can see that in the system obtained, Eqs. (3.16) and (3.17) are linearly

dependent, so it was not in vain that we have found the 4th smooth number.

To solve the system, subtract (3.15) from (3.16). We obtain

1 = u2 - u 3 . (3.19)

Add (3.19) to (3.18). We obtain

8 = 3212. (3.20)

From (3.20) we immediately find u2 (recall that the logarithms are reduced

modulo 47 - 1 = 46):

= (8/3) mod 46 = 8 . 3-1 mod 46 = 8 . 3 1 mod 46 = 18.

212

We can make a check by computing lo1' mod 47 = 3, so 212 is actually the

logarithm of 3. Now from (3.19) find u3:

Solving Discrete Logarithm Problem 41

(actually, 1017 mod 47 = 5). Finally, from (3.16) find u1:

- u2 = (2 - 18) mod 46 = -16 mod 46 = 30

=2

ti1

(lo3' mod 47 = 2).

Thus we know the logarithms of the elements of S. The most complex

part of the algorithm is left behind. Proceed to the fourth step. Select

(randomly) T = 3 and compute

3 7 . lo3 mod 47 = 3 7 . 1 3 mod 47 = 11.

The number 11 is not 5-smooth, so try the next T:

3 7 . lo4 mod 47 = 3 7 . 3 6 mod 47 = 16 = 2 . 2 . 2 . 2 .

The number 16 is 5-smooth and the fourth step is completed.

Turn to logarithms in the last equality (this is the fifth step) and obtain

the final result:

10g1037 = 410g102 - 4 = ( 4 . 3 0 - 4) mod 46 = 2 4 .

We have found the solution of Eq. (3.14) x = 24. We may check it: mod

47 = 37.

The fastest to the date is the variant of the described index calculus

algorithm called Number Field Sieve, see [Lenstra and Lenstra (1993)l.

This method is based upon subtle algebraic constructions so we do not

describe it in this book. Its time complexity is estimated as

< c1 . 2(C2+"(1)) g P ( l o g

tn. f.s. + l%P)2 (3.21)

where c1, c2 are some positive constants. It is this method which dic-

tates the conditions for choosing the length of modules in the cryptosystem

that rely on intractability of discrete logarithm problem (among the sys-

tems considered in Chap. 2 these are Diffie-Hellman, Shamir, and ElGamal

schemes). To achieve long-term security it is recommended that the length

of modulus be at least 1024 bits (as for 2005).

Remark at the conclusion that in our book, we do not consider the

methods of breaking the cryptosystems whose security is based on integer

factorisation problem (such as RSA). The fact is that this discussion would

require to introduce some extra notions and algorithms from number theory

that are of no use elsewhere in this book. However we may say that to date

the fastest methods of factorisation are characterised by the same estimate

of complexity as given by Eq. (3.21). As a consequence, to ensure long-term

Basics of Contemporary Cryptography for IT Practitioners

42

security of RSA system the modulus length must also be at least 1024 bits

(i.e. prime numbers producing a modulus must be at least 512 bits each).

Problems and Exercises

3.1 Using the baby-step giant-step algorithm, solve the following equa-

tions:

(a) 2" mod 29 = 21,

(b) 3" mod 31 = 25,

(c) 2" mod 37 = 12,

(d) 6" mod 41 = 21,

(e) 3" mod 43 = 11.

3.2 Using the index calculus algorithm, solve the following equations:

2" mod 53 = 24,

(a)

(b) 2" mod 59 = 13,

(c) 2" mod 61 = 45,

2" mod 67 = 41,

(d)

(e) 7" mod 71 = 41.

Themes for Labs

3.3 Create programs implementing the baby-step giant-step and index

calculus algorithms and solve on a computer the following equations:

(a) 2" mod 30203 = 24322,

(b) 2" mod 30323 = 21740,

(c) 2" mod 30539 = 28620,

(d) 2" mod 30803 = 16190,

(e) 5" mod 31607 = 30994

(due to lack of time, program implementation of only some steps of

the algorithms would be enough).

Chapter 4

Digital Signatures

RSA Digital Signature

4.1

Public-key cryptography has made a real revolution in contemporary com-

puter and network technologies. There emerged a possibility to solve prob-

lems that earlier had seemed insoluble but now are widely called for in

practice. One of the important elements of these new technologies is digital

signature. In many countries, including USA and Russia, digital signature

standards are adopted and the notion of digital signature is made part of

civil legislation.

Before studying cryptographic digital signatures, let us formulate the

main requirements which, ideally, should be met by any signature (including

handwritten).

(1) It must be only the entity A that could sign documents on behalf of A,

i.e. no one should be able to forge signatures.

(2) If the signed document is somehow altered or damaged, the signature

must become invalid.

(3) The author of signature should not be able to repudiate it.

(4) The signature must be verifiable by all interested parties, and more-

over, a third party (e.g. the court) should be able to decide on the

authenticity of signature in case of contention.

Of course, digital signatures should meet all these requirements but the

signer and verifier may be thousands of kilometres from each other and

communicate via an open computer network (e.g. the Internet).

In this section, we consider a digital signature scheme based on the

RSA algorithm [Rivest et al. (1978)]. Historically, it was the first method

discovered for creating digital signatures. Letâ€™s proceed to its description.

43

Basics of Contemporary Cryptography for IT Practitioners

44

Suppose Alice intends to sign documents. Then she has to choose the

RSA parameters in the same way as was described in Sec. 2.6. To do

that, Alice selects two large primes P and Q , computes N = PQ and

q5 = ( P - 1)(Q - 1). Then she selects a number d relatively prime t o 4 and

finds

c = d-' mod q5. (4.1)

At last, she publishes the numbers N and d (her public key), e.g. exposes

them at her Internet site in association with her name, and keeps secret the

number c (her private key, the other numbers P , Q, and q5 are no longer

required). Now Alice is ready to sign documents and messages.

Assume that Alice wishes to sign a message f i = m l , . . . , m,. First, she

computes a so-called hash function

h = h(m1,.. . ,mn)

which maps the message f i into a number h. It is assumed that the hash

function algorithm is publicly known. For the time being, we shall not

speak of the properties and ways of computation of hash functions, as this

question will be considered in detail in Sec. 8.5. Point out only the property

most important for us here: it is practically impossible to alter the main

text ml, . . . , m, without altering ˜ ( T T L ) So, it is enough for Alice to sign

.

only the number h, and this will act as a signature to the whole message

m.

Alice computes the number

,

mod N

s = h" (4.2)

i.e. she raises h to her secret power. The number s is nothing else but the

digital signature. Alice simply appends s to the message IRand obtains the

signed message

4. (4.3)

(m,

Now everybody who knows Alice's public key, i.e. the numbers N and

d associated with her name, can verify the authenticity of her signature.

TO do that, given the signed message (4.3), one needs to compute hash

function h(m)and the number

,

w = sd mod N (4.4)

after which to check the equality w = h(m).

Digital Signatures 45

Proposition 4.1 If the signature i s authentic, w = h(r5i).

It follows from (4.4), (4.2) and (4.1) that

Proof.

w = sd mod N = hcdmod N = h = h(m).

0

Proposition 4.2 The described digital signature satisfies all the require-

m e n t s the signature must meet.

Proof. The first requirement is met since nobody who knows only the

public parameters N and d can derive secret c which is needed to produce

a signature (we have already discussed this problem in Sec. 2.6). The

second requirement is fulfilled due to hash function: any change in the

message contents will (with overwhelming probability) also change the value

of h, which makes the previously computed signature invalid. The third

requirement is met as a consequence of the former two (the author cannot

repudiate the signature since nobody is able to alter the document and

forge the signature). Finally, everybody who knows the public parameters

N and d can verify the signature. In case of contention, the court can

reproduce all computations.

Example 4 1 Let P = 5, Q = 11. Then N = 5.11 = 55, q5 = 4.10 = 40.

.

Let d = 3. Such a choice of d is valid since gcd(40,3) = 1. Compute the

private key c = 3-1 mod 40 with the extended Euclidean algorithm (see

Sec. 2.3), c = 27.

= abbbaa, the value of

Assume that Alice wishes to sign the message ?i

i

hash function being, say, 13:

h = h(abbbaa) = 13.

Alice computes by (4.2)

s = 1327mod 55 = 7

and obtains the signed message

(abbbaa, 7 ) .

Now the one who knows Aliceâ€™s public key N = 55, d = 3 can verify the

signature. Having received the signed message, one computes hash function

h(abbbaa) = 13

Basics of Contemporary Cryptography f o r IT Practitioners

46

(if the contents of the message are not changed, the value of hash function

equals that computed by Alice) and compute by (4.4)

w = 73 mod 55 = 13.

The values of w and the hash function are equal, hence, the signature is

valid.

Notice that the same RSA scheme generated by Alice can be used for

Remark

solving two problems. First, Alice can sign messages as was shown in the present

section, by utilising her secret key c. Second, anybody can encrypt messages to

be read by Alice as was shown in Sec. 2.6, by utilising her public key d.

ElGamal Digital Signature

4.2

In the previous section, a digital signature scheme was described whose

security is based on intractability of integer factorisation problem. In this

section, we present a scheme that relies upon another hard problem, namely,

computing discrete logarithms. This scheme was suggested in [ElGamal

(1985)l and utilises the ElGamal encryption (see Sec. 2.5).

Assume as before that Alice is going to sign documents. Alice chooses

a large prime p and a number g such that different powers of g are different

numbers modulo p (see Sec. 2.2). These numbers are transmitted or stored

ñòð. 9 |