Sebery J.Cryptography.An introduction to computer security.1989
.pdf7.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
vi = pi i > N for i = 0; : : : ; ` |
|
1: |
|
|
|
|
|
|
|
|
|
|
|
Finally, Sally chooses h and x0 |
at random from ZN . The triple (N; h; x0) |
|||||
is stored in the public registry. Public keys are w and vij while their secret |
||||||
versions are w 1 and vij |
1. Clearly, the following congruences hold w 1 |
|
w |
|
||
1 mod (p 1)(q 1), and vij 1 vij 1 mod (p 1)(q 1). |
|
|
|
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
yj (xj 1hxj )vij |
1 |
(mod N) for j = 1; : : : ; : |
(7.3) |
||||||
and |
|
|
|
|
|
|
|
|
|
m w 1 |
|
|
|
|
|
|
|
||
z (x h ) |
|
(mod N) |
|
|
|
(7.4) |
|||
Finally, the signature is SGw;v(m) = (z; y1; i1; : : : ; y ; i ). |
|
||||||||
Veri cation: Victor takes (~z; y~ |
; i |
; : : : ; y~ ; i |
|
) and rst calculates |
|
||||
|
|
|
|
1 |
1 |
|
|
|
|
x~ z~wh m |
(mod N) |
|
|
|
|
(7.5) |
|||
and goes backwards |
|
|
|
|
|
|
|
||
vij |
|
x~j |
|
|
|
|
|
|
|
x~j 1 y~j |
h |
|
(mod N) for j = 1; : : : ; : |
(7.6) |
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
gk (mod p) |
(7.7) |
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)):
m1 |
k x + r y1 |
(mod p 1) |
m2 |
k x + r y2 |
(mod p 1) |
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
7.4 ElGamal Signatures |
295 |
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
x (gr mod p) mod q. For a message m 2 Zq , she computes |
|
y r 1(m + k x) (mod q) |
(7.11) |
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
public entry and computes two integers |
|
|
|
m~ y~ 1 |
(mod q) |
|
|
x~ y~ 1 |
(mod q) |
|
|
and checks whether |
|
|
|
|
? |
|
|
V ER(m;~ s~) = x~ (g (gk) mod p) mod q : |
(7.12) |
||
|
|
|
|
Consider a toy DSS scheme. Sally takes two moduli p = 2011 and q = 67
(p 1 = 67 30). To get an integer g with required properties, we rst choose a |
||
primitive element e = 1570 2 GF (p) and next compute g e(p 1)=q |
(mod p) |
|
so g = 157030 948 (mod 2011). It is easy to check that gq |
1 |
(mod p). |
Next Sally chooses her secret k = 37 < 67 and computes gk |
= 94837 857 |
|
(mod 2011). Sally's public entry is (gk; g; p; q) = (857;948; 2011;67). |
|
To sign, Sally generates a one-time random integer r = 49 < 67 and com-
putes |
|
|
|
|
|
x = 60 |
(94849 mod 2011) mod 67: |
|
|
||
For a message m = 65, she nds y = 49 1(65 + 37 |
60) |
48 (mod 67). The |
|||
signature SGk(65) = (60; 48). |
|
|
|||
Victor veri es the signature s = (60; 48) by calculating |
|||||
= 65 |
48 1 |
53 |
(mod 67) |
|
|
= 60 |
48 1 |
18 |
(mod 67): |
|
|
7.6 Undeniable Signatures |
297 |
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
s = SG (c) |
|
cd |
(mod N): |
d |
|
|
|
|
|
|
The blind signature s is sent to Henry.
Unblinding: Henry removes the random integer r by
s = SGd(m) = c |
|
r 1 |
|
md |
(mod N) |
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
s = SG (m) |
|
mk |
(mod p): |
k |
|
|
|
|
|
|
Veri cation: Victor and Sally interact going through the steps given below.
|
Challenge: Victor selects two random integers a; b 2 Zq and sends the chal- |
||||||||
|
|
|
lenge |
|
|
|
|
|
|
|
|
|
c = sa(gk)b (mod p) |
|
|
|
|
|
|
|
|
|
to Sally. |
|
|
|
|
|
|
|
Response: Sally computes k 1 (k |
k 1 |
|
1 |
(mod q)) and sends back |
||||
|
|
|
r = ck 1 ma gb (mod p) |
|
|
|
|
||
|
|
|
to Victor. |
|
|
|
|
|
|
|
Test: Victor checks whether |
|
(mod p) : |
||||||
|
|
|
? |
|
|||||
|
|
|
V ER(m;~ r~) = r~ m~ agb |
||||||
|
|
|
If the test fails, Victor runs the disavowal protocol. Otherwise, the sig- |
||||||
|
|
|
nature is accepted. |
|
|
|
|
|
|
Disavowal protocol: The protocol is executed only when veri cation fails. |
|||||||||
|
V!S: Victor selects randomly two a1; b1 |
2 Zq and sends c1 sa1 (gk)b1 |
|||||||
|
|
|
(mod p). |
|
|
|
|
|
|
|
S |
! |
V: Sally replies by sending r1 = c1k 1 . |
|
|
|
|||
|
|
|
6 ma1 gb1 |
|
|
|
|||
|
Test: Victor checks whether r1 |
|
(mod p). If that is the case, the |
||||||
|
|
|
same process is repeated. |
|
|
|
|
|
|
|
V!S: Victor selects randomly two a2; b2 |
2 Zq and sends c2 sa2 (gk)b2 |
|||||||
|
|
|
(mod p). |
|
|
|
|
|
|
|
S |
! |
V: Sally replies by sending r2 = c2k 1 . |
|
|
|
|||
|
|
|
6 ma2 gb2 |
|
|
|
|||
|
Test: Victor checks whether r2 |
|
(mod p). He concludes that sig- |
||||||
|
|
|
nature is a forgery if |
|
|
|
|
|
|
|
|
|
(r1g b1 )a2 (r2g b2 )a1 |
(mod p): |
|
|
|
||
|
|
|
Otherwise, Sally cheats by giving inconsistent responses. |
||||||
|
|
|
|
|
|
|
|
|
|
7.6 Undeniable Signatures |
299 |
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
a 6 a0 (mod q) or b 6 b0 (mod q) create di erent challenges c and c0. This |
|
statement can be proved by contradiction. Assume that c c0 |
(mod p). This |
implies that sa(gk)b sa0(gk)b0 (mod p) or sa a0 (gk)b0 b |
(mod p). If we |
represent s = g and gk = g , then |
|
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
(r1g b1 )a2 (r2g b2 )a1 |
(mod p) : |
|
||
Proof. Sally follows the algorithm and for Victor's challenges c1 |
sa1 (gk)b1 |
|||
(mod p) and c2 sa2 (gk)b2 |
(mod p) replies with |
|
||
r1 |
sa1k 1 gb1 |
(mod p) and |
|
|
r2 |
sa2k 1 gb2 |
(mod p); |
|
|
300 7 DIGITAL SIGNATURES
respectively. After simple transformations we get
sa1k 1 |
r1g b1 |
(mod p) |
sa2k 1 |
r2g b2 |
(mod p) |
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
challenge c = sa(gk)b = 349119375227 |
|
884 |
(mod 983). Sally follows the algo- |
||
|
1 |
|
|
|
|
rithm and replies with r = ck |
|
= 884182 32 (mod 983) where k 1 = 182. |
|||
Victor computes magb = 41311949227 32 |
(mod 983) which matches Sally's |
||||
response. The signature is authentic. |
|
|
|
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