Sebery J.Cryptography.An introduction to computer security.1989

7.3 RSA Signatures 291

The RSA signature scheme may be subject to variety of attacks that exploit the commutativity of exponentiation [129, 352] if the RSA signature scheme is meant to be used many times. Assume that Oscar knows two original documents (m1; s1 ) and (m2; s2) signed by Sally. He can sign a new document m = m1m2 as its valid signature is s = s1s2. Even the knowledge of a single document (m; s) signed by Sally, can be used to sign message m0 = m 1 as its valid signature is s0 = s 1.

Multiple use of the RSA scheme tends to weaken it. The way out is to make subsequent signatures dependent on the previously generated. Cramer and Damgard [113] proposed an RSA scheme for multiple use, which is secure against chosen message attacks under the assumption that the factoring is dif-cult. An additional component is needed to keep track of previous signatures. This component is an algorithm T R that builds up a full `-ary tree of depth d by random selection of its nodes xi. The root of the tree is an integer x0. Every time Sally wants to sign a new message, she invokes T R. The algorithm creates a new leaf x and returns its full path (x1; i1; : : : ; x ; i ) where the integer ij tells that the node xj is the ijth child of xj 1. T R can be used to sign up to ` messages.

Multiple RSA signatures

Initialization: The scheme is set up as previously; the modulus is N = p q where p; q are two strong primes. The scheme uses also set of distinct primes

L = fq; p0; : : : ; p` 1g:

All primes are co-prime to (p 1)(q 1). Let be the smallest integer such that

w = q > N

and i be the smallest integer such that

292 7 DIGITAL SIGNATURES

Signing: The signature generation can be done up to ` times. For the ith signature, Sally calls T R(i) which returns (x1; i1; : : : ; x ; i ). Next, she computes

At last, if x~0 x0 (mod N) the signature is authentic.

Consider Equations (7.3) and (7.4). To get rid of commutativity, the message appears as an exponent and a sequence of random elements xj is used. Each element plays a double role as a multiplier and exponent.

Victor reverses Sally's computations using public w and vij . If the signature is authentic, he must always end up with x0 in the last step of his computations. Victor can also update his copy of the tree from T R. Note that any two valid signature never traverse through the same path in the tree.

7.4 ElGamal Signatures

The scheme is based on the discrete logarithm problem [164].

ElGamal signatures

Initialization: Sally chooses a nite eld GF (p) where p is a long enough prime so the corresponding instance of discrete logarithm is intractable. She se-

lects a primitive element g 2 Z and a random integer k 2 Z . Sally then

p p

computes the public key

and communicates gk, g and p to the public registry. The element k is kept secret.

294 7 DIGITAL SIGNATURES

The elements (gk; g; p) stored in the public registry are xed for the life time of the scheme. The scheme can be used to sign many signatures. The signer, however, has to select a new secret integer r 2 Zp every time she signs. What happens if Sally signs two messages using the same r ? Let us consider the repercussions. Suppose Sally has signed two messages: m1 with (x; y1) and m2 with (x; y2 ). The two signatures produce (Congruence (7.9)):

The integer r which was supposed to be secret can now be computed from m1 m2 r(y1 y2) (mod p 1)

(Section 2.1.4). If the congruence does not have the unique solution, it can be found by testing possible candidates and calling the veri cation algorithm. After nding r, it is easy to compute the secret

k = (m1 ry1)x 1 (mod p 1):

Consider a simple example of the ElGamal signature scheme. First Sally sets up the scheme. She selects a modulus p = 359, a random secret k = 215 and a primitive element g = 152. She computes gk = 152215 293 (mod 359). The triple (gk; g; p) = (293; 152; 359) is Sally's public registry entry. To sign a message m = 312, Sally selects a \one-time" random integer r = 175, nds x = gr = 152175 58 (mod 359), and computes y from the following congruence:

m k x + r y (mod p 1) 312 215 58 + 175 y (mod 358)

It is easy to check that y = 86. The signature on m = 312 is s = (58; 86). Knowing Sally's public elements, Victor veri es the signature by computingrst gm 74 (mod 359) and next (gk)x xy 74 (mod 359). So Victor assumes that the signature is authentic.

A modi cation of the ElGamal signature was proposed as Digital Signature Standard (DSS) in 1991 [187]. DSS is also known as Digital Signature Algorithm or DSA.

Digital Signature Standard

Initialization: A large enough prime p is selected as one of the moduli used in the system. The modulus p is recommended to be of length at least 512 bits. The second modulus q is a 160-bit prime factor of p 1. An integer g is a qth root of 1 modulo p, that is, gq 1 (mod p) and g 6 1 (mod p) for < q. Sally selects her secret k < q and computes the public key gk (mod p). The sequence (gk; g; p; q) is deposited in the public registry.

Signing: Sally generates a one-time random integer r < q and the corresponding

The signature on the message m is s = SGk(m) = (x; y).

Veri cation: Victor takes the signature s~ = (~x; y~), the message m~ and Sally's

Consider a toy DSS scheme. Sally takes two moduli p = 2011 and q = 67

To sign, Sally generates a one-time random integer r = 49 < 67 and com-

Blinding: Henry looks up the public registry for Sally's N and e, chooses a

random integer r 2 Z , takes his message m 2 Z , and computes the

N N

blinded message

c m re (mod N):

Signing: Sally simply signs the blinded message c as

The blind signature s is sent to Henry.

Unblinding: Henry removes the random integer r by

and gets Sally's signature.

Veri cation: Victor takes Sally's public information (N; e), the message m~ , and the signature s~ and checks whether

V ERe(m;~ s~) = s~e ? m~ (mod N) :

In applications where messages are long, Harry asks Sally to sign blindly the digest of a message generated from a collision-resistant hash function instead of the message.

7.6 Undeniable Signatures

Chaum and van Antwerpen [89] introduced undeniable signatures. Their main feature is that Victor cannot verify a signature without Sally's cooperation. The cooperation takes form of a challenge-response interaction. Victor sends a challenge to Sally. Sally answers with her response. Victor takes Sally's response and veri es the signature. If the signature is authentic the process ends.

What happens if the veri cation fails? There are two possibilities: rst, the signature is indeed a fraud, or second Sally cheats by giving an \incorrect" response. To eliminate the second case, undeniable signatures have to have a disavowal protocol that is run only after veri cation failures.

Chaum-van Antwerpen signatures

298 7 DIGITAL SIGNATURES

Initialization: The security of the scheme is based on intractability of discrete logarithm. Sally selects a large prime modulus p such that p 1 = 2q where q is prime. She also takes an element g which generates the cyclic group G of order q. Next she chooses at random her secret k (0 < k < q) and computes the public key gk (mod p). The triple (gk; g; p) is Sally's entry stored in the public registry.

Signing: For a message m 2 G, Sally computes

Veri cation: Victor and Sally interact going through the steps given below.

After signing the message, Sally may have second thoughts and try to modify either the message or the signature. The next theorem characterises her chances of success.

Theorem 27. If s 6 mk (mod p), then Sally can provide a valid response with the probability q 1.

Proof. We start from an observation that any two pairs (a; b), (a0; b0) where

g (a a0) g (b0 b) (mod p)

and

(a a0) (b0 b) (mod q):

So the above congruence is satis ed if a a0 (mod q) and b b0 (mod q). This is the requested contradiction.

For the challenge c sa(gr)b (mod p), Sally has to reply with her response r magb (mod p). Because s 6 mk (mod p) she cannot use c to produce the response according to the algorithm. As Sally does not know (a; b) and for any possible choice of (a; b) the response is di erent, her best strategy would be to select a random x = 0; : : : ; q 1 and try to send r gx (mod p) with the probability of success q 1. tu

Consider the case when Sally follows the algorithm but the signature is a forgery, that is s 6 mk (mod p).

Theorem 28. Let Sally follow the disavowal algorithm, then the following congruence is satis ed

300 7 DIGITAL SIGNATURES

respectively. After simple transformations we get

Now if we rise the sides of the rst congruence to the power a2 and the second congruence to the power a1, we obtain the requested result. tu

Clearly, when Sally cheats by giving an invalid response she may succeed with the probability q 1. So with the probability (1 q 1), she fails and Victor will run the disavowal protocol.

Theorem 29. Let Sally give responses inconsistent with the algorithm, then Victor will detect the lack of consistency with the probability (1 q 1) by running the disavowal protocol.

Proof. It is enough to note that rst inconsistent response forces Sally to guess the unknown pair of (a2; b2) in the second response. By Theorem 27 the result follows. tu

Consider an example. Sally initializes the scheme choosing the modulus p = 983 with q = 491. The primitive element of GF (983) is e = 7. This element gives a requested g = e(p 1)=q = 72 = 49. Finally, Sally randomly selects k = 375 < 491, calculates the public key gk = 49375 100 (mod 983), and puts the triple (gk; g; p) = (100; 49; 983) into the public registry. To sign,

Sally takes her message m = 413 and computes s = SGk(m) = 413375 349 (mod 983). The pair (m; s) is published. To verify signature, Victor picks up two random numbers a = 119 and b = 227 smaller than 491 and prepares his

7.7 Fail-Stop Signatures

The concept was introduced by P tzmann and Waidner in [403]. Fail-stop signatures allow us to protect the signatures against an opponent with unlimited computational power. The trick is that the signature is produced by a signer