Click Here! |

Brief Full Advanced Search Search Tips
|  |  | To access the contents, click the chapter and section titles. Applied Cryptography, Second Edition: Protocols, Algorthms, and Source Code in C (cloth) (Publisher: John Wiley & Sons, Inc.) Author(s): Bruce Schneier ISBN: 0471128457 Publication Date: 01/01/96 Search this book:
Previous | Table of Contents | Next
Unfortunately, a pair of dishonest parties can cheat. Alice and Carol, working together, can easily find out what secret Bob is getting: If they know the FBI of Cb and Bob’s encryption algorithm, they can find b such that Cb has the right FBI. And Bob and Carol, working together, can easily get all the secrets from Alice. If you assume honest parties,there’s an easier protocol [389]. (1) Alice encrypts all of the secrets with RSA and sends them to Bob: Ci = Sie mod n (2) Bob chooses his secret Cb, picks a random r, and sends C', to Alice. C' = Cbre mod n (3) Alice sends Bob P'. P' = C'd mod n (4) Bob calculates Sb. Sb = P'r-1 mod n If the parties may be dishonest, Bob can prove in zero-knowledge that he knows some r such that C'=Cbre mod n and keep b secret until Alice gives him P' in step (3) [246]. ### 23.10 Fair and Failsafe Cryptosystems Fair Diffie-Hellman Fair cryptosystems are a way to do key escrowing in software (see Section 4.14). This example is from Silvio Micali [1084,1085]. It is patented [1086,1087]. In the basic Diffie-Hellman scheme, a group of users share a prime, p, and a generator, g. Alice’s private key is s, and her public key is t =gs mod p. Here’s how to make Diffie-Hellman fair (this example uses five trustees). (1) Alice chooses five integers, s1 , s2, s3, s4, and s5, each less than p - 1. Alice’s private key is s = (s1 + s2 + s3 + s4 + s5) mod p - 1 and her public key is t = gs mod p Alice also computes ti = gsi mod p, for i = 1 to 5 Alice’s public shares are ti, and her private shares are si. (2) Alice sends a private piece and corresponding public piece to each trustee. For example, she sends s1 and t1 to trustee 1. She sends t to the KDC. (3) Each trustee verifies that ti = gsi mod p If it does, the trustee signs ti and sends it to the KDC. The trustee stores si in a secure place. (4) After receiving all five public pieces, the KDC verifies that t = (t1 * t2 * t3 * t4 * t5) mod p If it does, the KDC approves the public key. At this point, the KDC knows that the trustees each have a valid piece, and that they can reconstruct the private key if required. However, neither the KDC nor any four of the trustees working together can reconstruct Alice’s private key. Micali’s papers [1084,1085] also contain a procedure for making RSA fair and for combining a threshold scheme with the fair cryptosystem, so that m out of n trustees can reconstruct the private key. Failsafe Diffie-Hellman Like the previous protocol, a group of users share a prime, p, and a generator, g. Alice’s private key is s, and her public key is t =gs mod p. (1) The KDC chooses a random number, B, between 0 and p - 2, and commits to B using a bit-commitment protocol (see Section 4.9). (2) Alice chooses a random number, A, between 0 and p - 2. She sends gA mod p to the KDC. (3) The user “shares” A with each trustee using a verifiable secret-sharing scheme (see Section 3.7). (4) The KDC reveals B to Alice. (5) Alice verifies the commitment from step (1). Then she sets her public key as t = (gA)gB mod p She sets her private key as s = (A + B) mod (p - 1) The trustees can reconstruct A. Since the KDC knows B, this is enough to reconstruct s. And Alice cannot make use of any subliminal channels to send unauthorized information. This protocol, discussed in [946,833] is being patented. ### 23.11 Zero-Knowledge Proofs of Knowledge Zero-Knowledge Proof of a Discrete Logarithm Peggy wants to prove to Victor that she knows an x that satisfies Ax ≡ B (mod p) where p is a prime, and x is a random number relatively prime to p - 1. The numbers A, B, and p are public, and x is secret. Here’s how Peggy can prove she knows x without revealing it (see Section 5.1) [338,337]. (1) Peggy generates t random numbers, r1 , r2 , ..., rt, where all ri are less than p - 1.1 (2) Peggy computes hi = Ari mod p, for all values of i, and sends them to Victor. (3) Peggy and Victor engage in a coin-flipping protocol to generate t bits: b1, b2 , ..., bt. (4) For all t bits, Peggy does one of the following: a) If bi = 0, she sends Victor ri b) If bi = 1, she sends Victor si = (ri - rj) mod (p - 1), where j is the lowest value for which bj = 1 (5) For all t bits, Victor confirms one of the following: a) If bi = 0, that Ari ≡ hi (mod p) b) If bi = 1, that Asi ≡ hihj-1 (mod p) (6) Peggy sends Victor Z, where Z = (x - rj) mod (p - 1) (7) Victor confirms that AZ ≡ Bhj-1 (mod p) Peggy’s probability of successfully cheating is 2-t. Zero-Knowledge Proof of the Ability to Break RSA Alice knows Carol’s private key. Maybe she has broken RSA; maybe she has broken into Carol’s house and stolen the key. Alice wants to convince Bob that she knows Carol’s key. However, she doesn’t want to tell Bob the key or even decrypt one of Carol’s messages for Bob. Here’s a zero-knowledge protocol by which Alice convinces Bob that she knows Carol’s private key [888].
Previous | Table of Contents | Next
[an error occurred while processing this directive]

| Products | Contact Us | About Us | Privacy | Ad Info | Home Use of this site is subject to certain Terms & Conditions, Copyright © 1996-1999 EarthWeb Inc. All rights reserved. Reproduction whole or in part in any form or medium without express written permision of EarthWeb is prohibited.