Applied Cryptography, Second Edition: Protocols, Algorthms, and Source Code in C (cloth)
(Publisher: John Wiley & Sons, Inc.)
Author(s): Bruce Schneier
Publication Date: 01/01/96
23.6 Computing with Encrypted Data
The Discrete Logarithm Problem
There is a large prime, p, and a generator, g. Alice has a particular value for x, and wants to know e, such that
- ge ≡ x (mod p)
This is a hard problem, and Alice lacks the computational power to compute the result. Bob has the power to solve the problemhe represents the government, or a large computing organization, or whatever. Heres how Bob can do it without Alice revealing x [547,4]:
- (1) Alice chooses a random number, r, less than p.
- (2) Alice computes
- x' = xgr mod p
- (3) Alice asks Bob to solve
- ge' ≡ x' (mod p)
- (5) Bob computes e' and sends it to Alice.
- (6) Alice recovers e by computing
- e = (e' - r) mod (p - 1)
Similar protocols for the quadratic residuosity problem and for the primitive root problem are in [3,4]. (See also Section 4.8.)
23.7 Fair Coin Flips
The following protocols allow Alice and Bob to flip a fair coin over a data network (see Section 4.9) . This is an example of flipping a coin into a well (see Section 4.10). At first, only Bob knows the result of the coin toss and tells it to Alice. Later, Alice may check to make sure that Bob told her the correct outcome of the toss.
Coin Flipping Using Square Roots
- (1) Alice chooses two large primes, p and q, and sends their product, n to Bob.
- (2) Bob chooses a random positive integer, r, such that r is less than n/2. Bob computes
- z = r2 mod n
and sends z to Alice.
- (3) Alice computes the four square roots of z (mod n). She can do this because she knows the factorization of n. Lets call them +x, -x, +y, and -y. Call x' the smaller of these two numbers:
- x mod n
- -x mod n
Similarly, call y' the smaller of these two numbers:
- y mod n
- -y mod n
Note that r is equal either to x' or y'.
- (4) Alice guesses whether r = x' or r = y', and sends her guess to Bob.
- (5) If Alices guess is correct, the result of the coin flip is heads. If Alices guess is incorrect, the result of the coin flip is tails. Bob announces the result of the coin flip.
- (6) Alice sends p and q to Bob.
- (7) Bob computes x' and y' and sends them to Alice.
- (8) Alice calculates r.
Alice has no way of knowing r, so her guess is real. She only tells Bob one bit of her guess in step (4) to prevent Bob from getting both x' and y'. If Bob has both of those numbers, he can change r after step (4).
Coin Flipping Using Exponentiation Modulo p
Exponentiation modulo a prime number, p, is used as a one-way function in this protocol :
- (1) Alice chooses a prime number, p, in such a way that the factorization of p - 1 is known and contains at least one large prime.
- (2) Bob selects two primitive elements, h and t, in GF(p). He sends them to Alice.
- (3) Alice checks that h and t are primitive and then chooses a random integer x, relatively prime to p - 1. She then computes one of the two values:
- y = hx mod p, or y = tx mod p
She sends y to Bob.
- (4) Bob guesses whether Alice calculated y as afunction of h or t, and sends his guess to Alice.
- (5) If Bobs guess is correct, the result of the coin flip is heads. If Bobs guess is incorrect, the result of the coin flip is tails. Alice announces the result of the coin flip.
- (6) Alice reveals x to Bob. Bob computes hx mod p and tx mod p, to confirm that Alice has played fairly and to verify the result of the toss. He also checks that x and p - 1 are relatively prime.
For Alice to cheat, she has to know two integers, x and x', such that h<