. 9
( 36 .)


to the exponents 1, 2, 4, and 7.
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


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.

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

(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

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-
(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,
(b) 2" mod 59 = 13,
(c) 2" mod 61 = 45,
2" mod 67 = 41,
(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

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

(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.

Basics of Contemporary Cryptography for IT Practitioners

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
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
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)
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

w = sd mod N = hcdmod N = h = h(m).
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
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

(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
Notice that the same RSA scheme generated by Alice can be used for
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

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
( 36 .)