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² ≡ 1 (mod 35) has the solutions: x = 1, 6, 29, or 34.

4: x² ≡ 4 (mod 35) has the solutions: x = 2, 12, 23, or 33.

9: x² ≡ 9 (mod 35) has the solutions: x = 3, 17, 18, or 32.

11: x² ≡ 11 (mod 35) has the solutions: x = 9, 16, 19, or 26.

14: x² ≡ 14 (mod 35) has the solutions: x = 7 or 28.

15: x² ≡ 15 (mod 35) has the solutions: x = 15 or 20.

16: x² ≡ 16 (mod 35) has the solutions: x = 4, 11, 24, or 31.

21: x² ≡ 21 (mod 35) has the solutions: x = 14 or 21.

25: x² ≡ 25 (mod 35) has the solutions: x = 5 or 30.

29: x² ≡ 29 (mod 35) has the solutions: x = 8, 13, 22 or 27.

30: x² ≡ 30 (mod 35) has the solutions: x = 10 or 25.

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

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² 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¹) * (4¹) * (9⁰) * (8¹)) mod 35 = 31 and sends it to Victor.

(4)  Victor verifies that 3¹² * ((4¹) * (11¹) * (16⁰) * (29¹)) 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 js where H(I,j) is a quadratic residue mod n. These H(I,j)s become v_1, v_2,..., v_k (the js need not be quadratic residues). Peggy’s public key is now I and the list of js. She sends I and the list of js 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 I by concatenating it with a long random string, R. This string is chosen by the arbitrator and is revealed to Victor along with I.

In typical implementations, k should be between 1 and 18. Larger values of k can reduce the time and communication complexity by reducing the number of rounds.

The value n should be at least 512 bits long. (Of course, there has been considerable progress in factoring since then.)

If each user chooses his own n and 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.