Author(s): Bruce Schneier

ISBN: 0471128457

Publication Date: 01/01/96

Previous | Table of Contents | Next |

*An Example*

Let’s look at this protocol in action with small numbers.

If *n* = 35 (the two primes are 5 and 7), then the possible quadratic residues are:

- 1:
*x*^{2}≡ 1 (mod 35) has the solutions:*x*= 1, 6, 29, or 34. - 4:
*x*^{2}≡ 4 (mod 35) has the solutions:*x*= 2, 12, 23, or 33. - 9:
*x*^{2}≡ 9 (mod 35) has the solutions:*x*= 3, 17, 18, or 32. - 11:
*x*^{2}≡ 11 (mod 35) has the solutions:*x*= 9, 16, 19, or 26. - 14:
*x*^{2}≡ 14 (mod 35) has the solutions:*x*= 7 or 28. - 15:
*x*^{2}≡ 15 (mod 35) has the solutions:*x*= 15 or 20. - 16:
*x*^{2}≡ 16 (mod 35) has the solutions:*x*= 4, 11, 24, or 31. - 21:
*x*^{2}≡ 21 (mod 35) has the solutions:*x*= 14 or 21. - 25:
*x*^{2}≡ 25 (mod 35) has the solutions:*x*= 5 or 30. - 29:
*x*^{2}≡ 29 (mod 35) has the solutions:*x*= 8, 13, 22 or 27. - 30:
*x*^{2}≡ 30 (mod 35) has the solutions:*x*= 10 or 25.

The inverses (mod 35) and their square roots are:

v
| v^{-1}
| s = sqrt (v^{-1})
| |

1 | 1 | 1 | |

4 | 9 | 3 | |

9 | 4 | 2 | |

11 | 16 | 4 | |

16 | 11 | 9 | |

29 | 29 | 8 |

Note that 14, 15, 21, 25, and 30 do not have inverses mod 35, because they are not relatively prime to 35. This makes sense, because there should be (5 - 1) * (7 - 1)/4 quadratic residues mod 35 relatively prime to 35: That is gcd(*x,*35) = 1 (see Section 11.3).

So, Peggy gets the public key consisting of *k* = 4 values: {4,11,16,29}. The corresponding private key is {3,4,9,8}. Here’s one round of the protocol.

**(1)**Peggy chooses a random*r*= 16, computes 16^{2}mod 35 = 11, and sends it to Victor.**(2)**Victor sends Peggy a random binary string {1,1,0,1}.**(3)**Peggy computes 16 * ((3^{1}) * (4^{1}) * (9^{0}) * (8^{1})) mod 35 = 31 and sends it to Victor.**(4)**Victor verifies that 3^{12}* ((4^{1}) * (11^{1}) * (16^{0}) * (29^{1})) mod 35 = 11.

Peggy and Victor repeat the protocol *t* times, each time with a different random *r,* until Victor is satisfied.

With small values like these, there’s no real security. But when *n* is 512 bits long or more, Victor cannot learn anything about Peggy’s secret key except the fact that she knows it.

*Enhancements*

It is possible to embed identification information into the protocol. Assume that *I* is a binary string representing Peggy’s identification: her name, address, social security number, hat size, preferred brand of soft drink, and other personal information. Use a one-way hash function *H*(*x*) to compute *H*(*I,j*), where *j* is a small number concatenated onto *I.* Find a set of *j*s where *H*(*I,j*) is a quadratic residue mod *n.* These *H*(*I,j*)s become *v*_{1,} *v*_{2,...,} *v*_{k} (the *j*s need not be quadratic residues). Peggy’s public key is now *I* and the list of *j*s. She sends *I* and the list of *j*s to Victor before step (1) of the protocol (or perhaps Victor downloads them from a public bulletin board someplace), and Victor generates *v*_{1,} *v*_{2,...,} *v*_{k} from *H*(*I,j*).

Now, after Victor successfully completes the protocol with Peggy, he is assured that Trent, who knows the factorization of the modulus, has certified the association between *I* and Peggy by giving her the square roots of the *v*_{i} derived from *I.* (See Section 5.2 for background information.)

Feige, Fiat, and Shamir include the following implementation remarks [544,545]:

For nonperfect hash functions, it may be advisable to randomize

Iby concatenating it with a long random string,R.This string is chosen by the arbitrator and is revealed to Victor along withI.In typical implementations,

kshould be between 1 and 18. Larger values ofkcan reduce the time and communication complexity by reducing the number of rounds.The value

nshould be at least 512 bits long. (Of course, there has been considerable progress in factoring since then.)If each user chooses his own

nand publishes it in a public key file, they can dispense with the arbitrator. However, this RSA-like variant makes the scheme considerably less convenient.

*Fiat-Shamir Signature Scheme*

Turning this identification scheme into a signature scheme is basically a matter of turning Victor into a hash function. The primary benefit of the Fiat-Shamir digital signature scheme over RSA is speed: Fiat-Shamir requires only 1 percent to 4 percent of the modular multiplications of RSA. For this protocol, we’ll bring back Alice and Bob.

Previous | Table of Contents | Next |