Fiat-Shamir signature schemes
As described in Note 10.30, any identification scheme involving a witness-challenge response sequence can be converted to a signature scheme by replacing the random challenge of the verifier with a one-way hash function. This section describes two signature mechanisms which arise in this way. The basis for this methodology is the Fiat-Shamir identification protocol (Protocol 10.24).
Feige-Fiat-Shamir signature scheme
The Feige-Fiat-Shamir signature scheme is a modification of an earlier signature scheme of Fiat and Shamir, and requires a one-way hash function h: {0,1}* —> {0,1}^{л} for some fixed positive integer k. Here {0, l}^{fc} denotes the set of bitstrings of bitlength A:, and {0,1}* denotes the set of all bitstrings (of arbitrary bitlengths). The method provides a digital signature with appendix, and is a randomized mechanism.
11.39 Algorithm Key generation for the Feige-Fiat-Shamir signature scheme ^{[1]} ^{[2]} ^{[3]} ^{[4]} ^{[5]}
11.40 Algorithm Feige-Fiat-Shamir signature generation and verification
SUMMARY: entity A signs a binary message m of arbitrary length. Any entity В can verify this signature by using A’s public key.
- 1. Signature generation. Entity A should do the folio whig:
- (a) Select a random integer r, 1 < r < n — 1.
- (b) Compute и = r^{[6]} mod n.
- (c) Compute e = (ei, ег,... , e*,) = /r(m||u); each e* € {0,1}.
- (d) Compute s = r ■ IIj=i ^{s<}j^{} mod n.
- (e) A’s signature for m is (e, s).
- 2. Verification. To verify A’s signature (e, s) on m, В should do the following:
- (a) Obtain A’s authentic public key (wi, i/2> • • ■ , щ) and n.
- (b) Compute w = ^{A}'^{[6]} • П/=1 ^{v<}j^{J} mod 71.
- (c) Compute e' = /i(m||u’).
- (d) Accept the signature if and only if e = e'.
Proof that signature verification works.
Hence, w = и and therefore e = e'.
11.41 Example (Feige-Fiat-Slianiir signature generation with artificially small parameters) Key generation. Entity A generates primes p = 3571, q = 4523, and computes n = pq = 16151633. The following table displays the selection of Sj (ri’s private key) and integers Vj (ri’s public key) along with intermediate values sj^{1}.
j |
1 |
2 |
3 |
4 |
5 |
^{s}i |
42 |
73 |
85 |
101 |
150 |
sj^{1} mod n |
4999315 |
885021 |
6270634 |
13113207 |
11090788 |
vj = sj^{[6]} mod n |
503594 |
4879739 |
7104483 |
1409171 |
6965302 |
Signature generation. Suppose h: {0,1}* —> {0, l} is a hash function. A selects a random integer r = 23181 and computes и = r^{[6]} mod n = 4354872. To sign message m, A evaluates e = /r(m||u) = 10110 (the hash value has been contrived for this example). A forms s = г«1«з«4 mod n = (23181)(42)(85)(101) mod n = 7978909; the signature for m is (e = 10110, s = 7978909).
Signature verification. В computes s^{[6]} mod n = 2926875 and V1V3V4 mod n = (503594) (7104483)(1409171) mod n = 15668174. В then computes w = s^{[6]}viV3V4 mod » = 4354872. Since w = u, it follows that e' = /r(m||u>) = /i(ra||u) = e and, hence, В accepts the signature. □
- 11.42 Note (security of Feige-Fiat-Shamir signature scheme)
- (i) Unlike the RSA signature scheme (Algorithm 11.19), all entities may use the same modulus 71 (cf. §8.2.2(vi)). In this scenario, a trusted third party (TTP) would need to generate the primes p and q and also public and private keys for each entity.
- (ii) The security of the Feige-Fiat-Shamir scheme is based on the intractability of computing square roots modulo n (see §3.5.2). It has been proven to be secure against an adaptive chosen-message attack, provided that factoring is intractable, h is a random function, and the sfs are distmct.
- 11.43 Note (parameter selection and key storage requirements) If n is a t-bit integer, the private key constructed in Algorithm 11.39 is kt bits hi size. This may be reduced by selecting the random values Sj, 1 < j < k, as numbers of bitlength t' < t t', however, should not be chosen so small that guessing the sj is feasible. The public key is (k + 1 )t. bits in size. For example, if t = 768 and к = 128, then the private key requires 98304 bits and the public key requires 99072 bits.
- 11.44 Note (identity-based Feige-Fiat-Shamir signatures) Suppose a TTP constructs prunes p and q and modulus n; the modulus is common to all entities in the system. Algorithm 11.39 can be modified so that the scheme is identity-based. Entity A’s bitstring I, contains information which identifies A. The TTP computes Vj = /(/,i||j), 1 < j < к, where / is a one-way hash function from {0,1}* to Q„ and j is represented in binary, and computes a square root Sj of v~^{l} modulo n, 1 < j < к. A’s public key is simply the identity information I a, while A’s private key (transported securely and secretly by the TTP to A) is the fc-tuple (.si, s 2,... ,«fc). The functions h, /.and the modulus n are system-wide quantities.
This procedure has the advantage that the public key generated hi Algorithm 11.39 might be generated from a smaller quantity I a, potentially reducing the storage and transmission cost. It has the disadvantages that the private keys of entities are known to the TTP, and the modulus n is system-wide, making it a more attractive target.
11.45 Note (small prime variation of Feige-Fiat-Shamir signatures) This improvement aims to reduce the size of the public key and hicrease the efficiency of signature verification. Unlike the modification described in Note 11.44, each entity A generates its own modulus ?гд and a set of к small prunes vi,V2, ■.. ,vk € Q_{n} (each prime will require around 2 bytes to represent). Entity A selects one of the square roots Sj of v~^{L} modulo n for each j, 1 < j <
these form the private key. The public key consists of ?гд and the values vi,V2, • • • ,ufc- Verification of signatures proceeds more efficiently since computations are done with much smaller numbers.
11.46 Note (performance characteristics of Feige-Fiat-Shamir signatures) With the RSA scheme and a modulus of length t = 768, signature generation using naive techniques requires, on average, 1152 modular multiplications (more precisely, 768 squarings and 384 multiplications). Signature generation for the Feige-Fiat-Shamir scheme (Algorithm 11.40) requires, on average, к/2 modular multiplications. To sign a message with this scheme, a modulus of length t = 768 and к = 128 requires, on average, 64 modular multiplications, or less than 6% of the work required by a naive implementation of RSA. Signature verification requires only one modular multiplication for RSA if the public exponent is e = 3, and 64 modular multiplications, on average, for Feige-Fiat-Shamir. For applications where signature generation must be performed quickly and key space storage is not limited, the Feige-Fiat-Shamir scheme (or DSA-like schemes — see §11.5) may be preferable to RSA.
- [1] SUMMARY: each entity creates a public key and corresponding private key. Each entity A should do the following:
- [2] Generate random distinct secret primes p, q and form n = pq.
- [3] Select a positive integer к and distinct random integers si, s2, ■ ■ • , sfc € Z*.
- [4] Compute Vj = s~2 mod n, 1 < j < к.
- [5] ,4’s public key is the /.--tuple (v1,v2,... , t>r) and the modulus n; A’s private key isthe fc-tuple (si,s2, • • • ,«*)•
- [6] 2
- [7] 2
- [8] 2
- [9] 2
- [10] 2
- [11] 2