Signature schemes based on the strong RSA assumption

更新时间：2023-05-29 09:58:01 阅读量：实用文档文档下载

说明：文章内容仅供预览，部分内容可能不全。下载后的文档，内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的，是否完整无缺。

signature推荐度：
相关推荐

We describe and analyze a new digital signature scheme. The new scheme is quite efficient, does not require the the signer to maintain any state, and can be proven secure against adaptive chosen message attack under a reasonable intractability assumption,

Signature Schemes Based on the Strong RSA AssumptionInstitute for Theoretical Computer Science, ETH Zurich, 8092 Zurich, Switzerlandcramer@inf.ethz.ch

Ronald Cramer Victor Shoup

IBM Zurich Research Laboratory, Saumerstr. 4, 8803 Ruschlikon, Switzerlandsho@

December 6, 1998We describe and analyze a new digital signature scheme. The new scheme is quite e cient, does not require the the signer to maintain any state, and can be proven secure against adaptive chosen message attack under a reasonable intractability assumption, the so-called Strong RSA Assumption. Moreover, a hash function can be incorporated into the scheme in such a way that it is also secure in the random oracle model under the standard RSA Assumption.

Abstract

1 IntroductionWe describe new, e cient digital signature schemes whose security is based on the Strong RSA Assumption. By security, we mean security against an adaptive chosen message attack, as de ned in 9]. To prove that our new schemes are secure, we need to make the Strong RSA Assumption (SRA), recently introduced by 2]. We also need a collision-resistant hash function.1 Our new schemes are interesting in that they are state-free, unlike other provably secure schemes 9, 7, 6]. Of course, we achieve this at the expense using of a potentially stronger assumption than is made in 9, 7, 6].We could get by using a target collision-resistant hash function by adapting the ideas from 4].1

We stress that in discussing proofs of security, we are not making use of the\random oracle" model of computation 3], but rather, we are working in the\real world" of computation. Indeed, the standard\hash and invert" RSA signature is provably secure in the random oracle model under the standard RSA Assumption. We also make the further observation that another hash function can be incorporated into our new schemes in such a way that they are also secure in the random oracle model under the standard RSA Assumption. In this sense, our schemes can be made to be at least as secure as a standard RSA signature. The SRA is the assumption that the following problem is hard to solve. Given a randomly chosen RSA modulus n and a random z 2 Zn, nd r> 1 and y 2 Zn such that yr= z . Note that this di ers from the ordinary RSA Assumption (RA), in that for RA, the exponent r is chosen independently of z, whereas for SRA, r may be chosen in a way that depends on z . The SRA is a potentially stronger assumption than the RA, but at the present time, the only known method for breaking either RA or SRA is to solve the integer factorization problem. Independently, Gennaro, Halevi, and Rabin 8] have also recently discovered e cient, state-free signature schemes based on the SRA. Our schemes are actually quite di erent from theirs, and we think that all of these di erent schemes are of interest from both a theoretical and practical perspective, because they are the only truly practical and state-free schemes available that admit a pr

oof of security under a natural intractability assumption. Moreover, our scheme is potentially more e cient for the following reason. The paper 8] contains several signature schemes, but the only fully proved scheme requires a\trapdoor" or\chameleon" collision-resistant hash function with the following very special property: its output is a prime number. Implementing such a hash function is both awkward and potentially computationally expensive. Indeed, depending on the security parameters and implementation details, evaluating this hash function can dominate the running time of the signing algorithm. Our scheme sidesteps this problem altogether. While the signing algorithm still has to generate a prime number, it has a great deal of exibility in how this is done, yielding a much more e cient algorithm. Basically, our signing algorithm just needs to generate any prime number of appropriate length (e.g., 161-bits) subject only to the requirement that the probability of generating the same prime twice is small. Our new schemes can be seen as variations of the scheme of Cramer and Damgard 6], which itself can be seen as an adaptation of the identi cation 2

scheme of Guillou and Quisquater 10]. In x2, we present and analyze our basic scheme. In x3, we present and analyze a variation based on trapdoor hashing. In x4, we sketch an algorithm for fast prime generation, as required by the signing algorithm, and discuss how the intractability assumption can be weakened by using hash functions.

2 The Basic SchemeIn this section we describe the basic scheme, and give a proof of its security. The scheme is parameterized by two security parameters, k and l, where l+ 1< k. Reasonable choices might be k= 512 and l= 160. The scheme makes use of a collision-resistant hash function H whose output can be interpreted as a positive integer less than 2l . A reasonable choice for H might be SHA-1. For a positive integer n, we let QRn denote the subgroup of Zn of squares (i.e., the quadratic residues modulo n).

Key Generation Two random k-bit primes p and q are chosen, whereAlso chosen are: random h; x 2 QRn; a random (l+ 1)-bit prime e0 . The public key is (n; h; x; e0 ): The private key is (p; q): chosen. The equation

p= 2p0+ 1 and q= 2q0+ 1, with both p0 and q0 prime. Let n= pq.

Signature Generation To sign a message m (an arbitrary bit string), a random (l+ 1) bit prime e= e0 is chosen, and a random y0 2 QRn is 6is solved for y, where x0 satis es the equation (y0 )e= x0 hH (m):0

ye= xhH (x )0

Note that y can be calculated using the factorization of n in the private key. The signature is (e; y; y0 ): 3

Signature Veri cation To verify a putative signature (e; y; y0 ) on a mes0 0

sage m, it is rst checked that e is an odd (l+ 1)-bit number di erent from e0 . Second, x0= (y0 )e h?H (m) is computed. Third, it is checked that x= yeh?H (x ) .

We remark that the signature veri cation algorithm does not need to verify that e is prime. To

speed both veri cation and signing, the public key might contain h?1 instead of h. In generating a signature, the only full-length exponentiation that needs to be performed is in the computation of y. The cost of this can be signi cantly reduced, as follows. First, we can arrange that x= ha for a random number a mod p0 q0, where a is stored in the secret key. This is acceptable, because h is with overwhelming probability a generator of QRn, and thus the distribution of the public key does not change signi cantly. Now, if d is the inverse of e mod p0 q0, then y= hb, where b= da+ dH (x0 ) mod p0 q0 . So the computation of y involves exponentiation with the xed base h to the power b. Using pre-computation techniques 13], we can substantially reduce the number of modular multiplications using a table of pre-computed numbers. Of course, in all of the above, one utilizes the Chinese Remainder Theorem as well to speed the exponentiations. We also note that the primes generated by the signer do not have to be random primes. The only requirement is that the probability of generating the same prime twice is negligible. Using these implementation ideas, together with a fast prime generator like the one described in x4, it would appear that the cost of signing is almost the same as that of basic RSA. Veri cation, however, will still be slower, involving basically two 160-bit exponentiations. Now we proceed to prove the security of the above scheme.

Implementation Notes

Proof of Security

Theorem 1 The above signature scheme is secure against adaptive chosen message attack, assuming the SRA and assuming that H is collisionresistant.

To prove this theorem, let us consider a forging algorithm that makes t signing queries and then produces a forgery. For 1 i t, let mi be the ith message signed, let (ei; yi; yi0 ) be the i signature, and let x0i be de ned as x0i= (yi0 )e h?H (mi ) . Let (e; y; y0 ) be the forgery on message m (so m 6= mi for all 1 i t). Also, let x0= (y0 )e h?H (m) . We distinguish between three types of forgeries: Type I For some 1 j t, e= ej and x0= x0j . Type II For some 1 j t, e= ej and x0 6= x0j . Type III For all 1 i t, e 6= ei. Assuming that the probability of generating two equal ei values is negligible, a forgery has a unique type. If there is a forger that succeeds with non-negligible probability, then there exists either Type I forger, a Type II forger, or a Type III forger, one of which succeeds with non-negligible probability. We show that any of these forgers can be turned into an algorithm breaking the SRA. In fact, a forger of Types I or II can be used to break the RA, and the proof of this is quite similar to proofs in 6]. We only need the SRA in case the forger is Type III.0 0

Type I ForgerSuppose we have a Type I forger that succeeds with non-negligible probability. We want to show how to use this forger to break the RA. That is, we are given n, a random z 2 Zn, and a random (l+ 1)-bit prime r, and we

want to compute z 1=r . We describe a simulator that interacts with the forger. We choose random (l+ 1)-bit primes e1;:::; et, and we create a public key as follows. We set Q h= z 2 i ei: We next choose w 2 Zn at random and set

x= w20

Q eii

Finally, we set e0= r. Now, to sign message mi, the simulator chooses yi0 2 QRn at random, and computes x0i= (yi0 )e h?H (mi ) . Next, the simulator solves the equation yie= xhH (xi ) for yi, which is can easily do, since it knows the ei th roots of x and h.0

It is easy to see that the simulator perfectly simulates the forger's view. Now suppose the forger creates a Type I forgery (e; y; y0 ) on a message m. So for some 1 j t, e= ej and x0= x0j . This yields two equations (y0 )e= x0 hH (m); 0 (yj )e= x0 hH (mj ):0 0

Since we are assuming H is collision-resistant, we may assume that H (m) 6= H (mj ). Thus, dividing these two equations, we can calculate v 2 Zn and an integer a 6 0 (mod e0 ) such that

ve= ha= z 2a i ei: Q Moreover, since gcd(2a i ei; e0 )= 1 and e0= r, we can easily compute an rth root of z. This is done via a standard procedure, which we will need to use several times, and we recall it for completeness. If we have vr= z b, where gcd(r; b)= 1, then we compute b0 such that bb0= 1+ rk. It follows that (vb z?k )r= z .0 0

As in the Type I case, we are given n, z 2 Zn and r, and we want to nd an rth root of z . We may assume that the value j in the de nition of a Type II forgery is xed. If not, we can guess it. Again, we describe a simulator. We create a public key as follows. For 1 i t, with i 6= j, we choose ei to be a random (l+ 1)-bit prime. We set ej= r. We also select e0 to be a random (l+ 1)-bit prime. We set

Type II Forger

h=z

i=j ei:6

We choose w 2 Zn at random, and set

yj= w 2We choose u 2 Zn at random, and set We compute

i=j ei:6

x0j= e2e:0 0

x= yjej h?H (xj ):6

Next, we describe how to sign message mi . First, suppose i 6= j . We choose yi0 2 QRn at random, and compute as x0i= (yi0 )e h?H (mi ) . Then, since we know the ei th roots of x and h, we can easily compute the corresponding value yi . Second, suppose i= j . Since we know the e0 th roots of h and x0j, we 0 can compute the correct value yj . The correct value of yj has already been determined. That completes the description of the simulator. It is easy to see that the simulator perfectly simulates the forger's view. Now suppose the forger creates a Type II forgery (e; y; y0 ) on a message m, where e= ej and x0 6= x0j . Then we have0

ye= xhH (x ); yje= xhH (xj ):0 0

Then by an argument similar to that in the Type I case, we can divide these two equations, and calculate an rth root of z . Given a Type III forger, we show how to break the SRA. That is, given n and z 2 Zn, compute r> 1 and an rth root of z . The simulator runs as follows. We choose random (l+ 1)-bit primes 0; e1;:::; et . We set e Q h= z 2e i ei: Now we

choose a random a 2 f1;:::; n2 g, and set x= ha . Now, by construction, QRn is a cyclic group of order p0 q0 . We can assume that h generates QRn, since this happens with overwhelming probability. Now let a= bp0 q0+ c, where 0 c< p0 q0 . Because a was chosen at random from a suitably large interval, the distribution of c is statistically indistinguishable the uniform distribution on f0;:::; p0 q0? 1g. Moreover, the conditional distribution of b given c is statistically indistinguishable from the uniform distribution on f0;:::; bn2=p0 q0 cg. That is, c and b are essentially independent. Because the distribution of c is essentially uniform, x is essentially distributed like a random element of QRn . Since we know all the relevant roots of x and h, we can easily sign all messages.0

Type III Forger

Now suppose the forger creates a Type III forgery, (e; y; y0 ). Then we have ye= xhH (x )= z m; where Y m= 2e0 ei (a+ H (x0 )):0

Let d= gcd(e; m). Now, using the same procedure as was used in the Type I and Type II cases, we can compute an (e= gcd(e; m))-th root of z, which is nontrivial provided e6 j m. So it su ces to show that e6 jQ with non-negligible m probability. Let r be a prime dividing e. Now, r6 j 2e0 i ei by construction. So it su ces to show that r6 j (a+ H (x0 )) with non-negligible probability. Let a= bp0 q0+ c as above. Now, r may depend on c, but we observed above that c and b are essentially independent. And since by construction r6 j p0 q0, it follows that r j (a+ H (x0)) with probability very close to 1=r, as we are evaluating a linear polynomial in b at a random point. Thus, with non-negligible probability, r6 j (a+ H (x0 )).

3 Trapdoor Hash SchemeConsider the basic signature scheme presented above, and consider a signature (e; y; y0 ) on a message m. Let x0= (y0 )e h?H (m) . Then we have ye= xhH (x ) . One can view the value H (x0 ) as a kind of\trapdoor hash," also called a\chameleon hash" (see 12] for detailed discussion, references, and further applications). One can also base a trapdoor hash on the Discrete Logarithm Assumption in a standard way, as follows. Let g1; g2 be two random generators for a group G of order s, where s is an (l+ 1)-bit prime. To hash t H a message m, we compute the hash value= H (g1 g2 (m) ), where H is an ordinary, collision-resistant hash function, and t is chosen at random mod s. In addition to the hash value, we also output the side information t. The trapdoor in this scheme is the g1 logarithm of g2 . A simulator that knows the trapdoor can construct a hash value without knowing m, and then later, given m, can construct and the appropriate side information t. We now describe a signature scheme based on this.0 0

Key Generation Two random k-bit primes p and q are chosen, wherep= 2p0+ 1 and q= 2q0+ 1, with both p0 and q0 prime. Let n= pq.Also chosen are: 8

random h; x 2 QRn; a group G of order s, where s is an (l+ 1)-bit prime, and two ra

ndom generators g1; g2 of G. The public key is (n; h; x; g1; g2 ); along with an appropriate description of G (including s). The private key is (p; q):

Signature Generation To sign a message m (an arbitrary bit string), a random (l+ 1) bit prime e is chosen, and a random t 2 Zs is chosen.The equation is solved for y. The signature is

ye= xhH (gt g(e; y; t):

1 2

H (m) )

Signature Veri cation To verify a putative signature (e; y; t) on a mes1 2 ( )

sage m, it is rst checked that e is an odd (l+ 1)-bit number. Second, it is checked that Hm x= ye h?H (gt g ):

Theorem 2 The above signature scheme is secure against adaptive chosenmessage attack, assuming the SRA, assuming that H is collision-resistant, and assuming the Discrete Logarithm Assumption for the group G.

The proof of this theorem is very similar to the proof of Theorem 1. We leave the details to the reader. In a variation on this scheme, we give the signing algorithm the trapdoor to the hash. The advantage of doing this can be appreciated if one makes a distinction between the\o line" and\on line" cost of signing. If the signer has the trap door, then in fact the\on line" cost is essentially a single multiplication mod s|all of the other work in creating the signature can be done before the message m is actually received.

4 Remarks on Prime GenerationIn our signature scheme, the signer must generate a random (l+ 1) bit prime with each signature. As we remarked already, these primes need not be chosen from the uniform distribution (l+ 1)-bit primes. The only requirement is that the probability of generating two equal primes should be negligible. Thus, we have quite a bit of exibility in how we generate these primes. This is perhaps important, because if one is not careful, the cost of prime generation can easily be the dominant cost of signing. This is especially so if one wants a completely rigorous algorithm with a su ciently small error probability. For example, suppose one uses the Miller-Rabin test 16] to test for primality. Suppose l= 160. Further, suppose we want an error rate of 2?96, which will allow us to make 232 signatures with an overall error rate of 2?64 . Now suppose we choose random 161-bit numbers until we have found a number that passes a number of trial divisions and a single Miller-Rabin test Along the way, we will make a small handful of Miller-Rabin tests that reject some composite numbers that pass the trial division test. Then we will need to perform about 47 additional Miller-Rabin tests to achieve the desired error rate. Working with a 1024-bit RSA modulus, empirical tests suggest that the cost of all these Miller-Rabin tests is much more than the cost of all the other steps in the signing algorithm. Moreover, the best results we know of 11] on the error rate of the Miller-Rabin test do not improve this situation much. Here we sketch a very e cient algorithm for generating primes as required by the signing algorithm. Again, assume l=

160. So we need to generate a 161-bit prime. To do this, we rst generate a random prime P in the range (252; 253 ). Because P is small enough, the primality of P can be quickly veri ed using one of a number of procedures described in Bleichenbacher's thesis 5, Chapter 3], which are correct for primes up to 1016> 253 . For example, one of Bleichenbacher's results, as reported in 14], states that the Miller-Rabin test for the bases 2; 3; 5; 7; 11; 13 and 23 is a correct primality test for numbers in this range. Next, we repeatedly choose integers R in the interval ((2160? 1)=8P; (2161? 1)=8P ) until e= 8RP+ 1 is prime. Lemma 2 in 14] provides an extremely e cient probabilistic algorithm for generating a certi cate of primality for numbers of this form, requiring essentially just a single exponentiation on average to certify a prime; our choice of parameters 10

A Fast Prime Generation Algorithm

ensures that 4P

e1=3, as required by that lemma.

Lemma 1 With this procedure, the expected number of trials until P isprime is at most 64. Assuming the Generalized Riemann Hypothesis, the following holds. For any xed P, the number of trials until 8RP+ 1 is prime is at most 128. The probability that two independent runs of this procedure output the same prime is at most 2?141 .

To prove this we use some explicit estimates from 1]. First, by Theorem 8.8.1 in 1], we have the number of primes P in the given range is more than 246 . The rst claim in the lemma follows trivially. For the second and third claims, we use Theorem 8.8.18 in 1], which gives a very sharp estimate on the number of primes in an arithmetic progression, assuming the Generalized Riemann Hypothesis. Using a simple calculation, this theorem implies that for any xed P, there are at least 298 primes of the form 8RP+ 1 in the range (2160; 2161 ). The second claim in the lemma is now follows easily. Now for the third claim. Let ei= 8Pi Ri+ 1 for i= 1; 2 be two primes generated by independent executions of the algorithm. We have Pr e1= e2] Pr e1= e2 jP1= P2] Pr P1= P2]+ Pr e1= e2 jP1 6= P2] (1) By the previous observations, the rst term in (1) is bounded by 2?98 2?46= 2?144 . Now x P1 6= P2 . The second term in (1) is bounded by the probability that the following two events occur: P1 j R2 and R1= (R2=P1 )P2 . By a simple calculation, the rst event occurs with probability at most 2?44 and the second with probability at most 2?98 . As these events are independent, we get a bound of 2?142 for the second term in (1). This implies the lemma. We do not claim that this is the best way to generate 161-bit primes, or even particularly original, but it seems like a reasonable one, and it is certainly much more e cient than the cost of iterating the Miller-Rabin test. In 15] a similar approach to generating certi ed primes is presented, but their analysis is insu cient for our purposes, as it is only asymptotic|we need explicit bounds, and thus have to appeal to the Generalize

d Riemann Hypothesis. Moreover, their approach would anyway give a higher collision probability. Since the technique suggested here provides a certi cate of primality that is small and easily veri ed, one could augment the signature scheme by adding this certi cate to the signature and having the veri er check it. 11

This can only improve security, allowing us to weaken the SRA so that the adversary's exponent has to be a certi ed prime of the proper form, and not just an arbitrary integer. We can weaken the intractability assumption even further. Suppose that in the above algorithm for generating a prime, we require that the random numbers P and R are outputs of a cryptographic hash function. The signing algorithm can feed random bits into such a hash function, and if the hash function is nearly uniform, the same properties that are proved above will still hold. The hash function inputs that yield P and R (respectively) are included as part of the signature, and the veri er checks that these values are correct. By doing this, we greatly constrain the adversary's attack strategy, allowing us to weaken the SRA so that the adversary's exponent is a certi ed prime of this very special form. This intuitively seems like a much harder problem, and indeed, this intuition is somewhat justi ed by the fact that is is straightforward to prove in the random oracle model that the resulting signature scheme is secure under a standard RSA assumption.

Using a Hash Function

References1] E. Bach and J. Shallit. Algorithmic Number Theory, volume 1. MIT Press, 1996. 2] N. Baric and B. P tzmann. Collision-free accumulators and fail-stop signature schemes without trees. In Advances in Cryptology{Eurocrypt '97, pages 480{494, 1997. 3] M. Bellare and P. Rogaway. Random oracles are practical: a paradigm for designing e cient protocols. In First ACM Conference on Computer and Communications Security, pages 62{73, 1993. 4] M. Bellare and P. Rogaway. Collision-resistant hashing: towards making UOWHFs practical. In Advances in Cryptology{Crypto '97, 1997. 5] D. Bleichenbacher. E ciency and security of cryptosystems based on number theory. PhD thesis, Swiss Federal Institute of Technology Zurich, 1996. 12

6] R. Cramer and I. Damgard. New generation of secure and practical RSA-based signatures. In Advances in Cryptology{Crypto '96, pages 173{185, 1996. 7] C. Dwork and M. Naor. An e cient existentially unforegeable signature scheme and its applications. In Advances in Cryptology{Crypto '94, pages 218{238, 1994. 8] R. Gennaro, S. Halevi, and T. Rabin. Secure signatures, without trees or random oracles. Preprint, 1998. 9] S. Goldwasser, S. Micali, and R. Rivest. A digital signature scheme secure against adaptive chosen-message attacks. SIAM J. Comput., 17:281{308, 1988. 10] L. Guillou and J. Quisquater. A practical zero-knowledge protocol tted to security microprocesors minimizing both transmission and memory. In Advances in Cryptology{Eurocrypt '88, Springer LNCS 330, pag

es 123{128, 1988. 11] S. H. Kim and C. Pomerance. The probability that a random probable prime is composite. Math. Comp., 53(188):721{741, 1989. 12] H. Krawczyk and T. Rabin. Chameleon hashing and signatures. Preprint, Theory of Cryptography Library, March 1998. 13] C. H. Lim and P. J. Lee. More exible exponentiation with precomputation. In Advances in Cryptology{Crypto '94, pages 95{107, 1994. 14] U. Maurer. Fast generation of prime numbers and secure public-key cryptographic parameters. J. Cryptology, 8:123{155, 1995. 15] J. Pintz, W. L. Steiger, and E. Szemeredi. In nite sets of primes with fast primality tests and quick generatio of large primes. Math. Comp., 53(187):399{406, 1989. 16] M. O. Rabin. Probabilistic algorithms for testing primality. J. of Number Theory, 12:128{138, 1980.

本文来源：https://www.bwwdw.com/article/xbp4.html

相关文章：

1 醋酸解离常数的测定12-05

2015年银行从业资格考试真题及答案下载06-11

结核病报告与转诊培训试题01-08

制冷原理及设备课程课程设计 - 图文11-18

上一篇：ICU心理护理量表的汉化及信效度评价下一篇：生地会考复习资料：初中生物图集(附题目)1