| GO

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
Carol’s public key is e, her private key is d, and the RSA modulus is n. (1) Alice and Bob agree on a random k and an m such that km ≡ e (mod n) They should choose the numbers randomly, using a coin-flip protocol to generate k and then computing m. If both k and m are greater than 3, the protocol continues. Otherwise, they choose again. (2) Alice and Bob generate a random ciphertext, C. Again, they should use a coin-flip protocol. (3) Alice, using Carol’s private key, computes M = Cd mod n She then computes X = Mk mod n and sends X to Bob. (4) Bob confirms that Xm mod n = C. If it does, he believes Alice. A similar protocol can be used to demonstrate the ability to break a discrete logarithm problem [888]. Zero-Knowledge Proof that n Is a Blum Integer There are no known truly practical zero-knowledge proofs that n =pq, where p and q are primes congruent to 3 modulo 4. However, if you allow n to be of the form prqs, where r and s are odd, then the properties which make Blum integers useful in cryptography still hold. And there exists a zero-knowledge proof that n is of that form. Assume Alice knows the factorization of the Blum integer n, where n is of the form previously discussed. Here’s how she can prove to Bob that n is of that form [660]. (1) Alice sends Bob a number u which has a Jacobi symbol -1 modulo n. (2) Alice and Bob jointly agree on random bits: b1 , b2 , ..., bk. (3) Alice and Bob jointly agree on random numbers: x1 , x2 , ..., xk. (4) For each i = 1, 2,..., k, Alice sends Bob a square root modulo n, of one of the four numbers: xi, -xi, uxi, -uxi. The square root must have the Jacobi symbol bi. The odds of Alice successfully cheating are one in 2k. ### 23.12 Blind Signatures The notion of blind signatures (see Section 5.3) was invented by David Chaum [317,323], who also invented their first implementation [318]. It uses the RSA algorithm. Bob has a public key, e, a private key, d, and a public modulus, n. Alice wants Bob to sign message m blindly. (1) Alice chooses a random value, k, between 1 and n. Then she blinds m by computing t = mke mod n (2) Bob signs t td = (mke)d mod n (3) Alice unblinds td by computing s = td/k mod n (4) And the result is s = md mod n This can easily be shown td ≡ (mke)d ≡ mdk (mod n), so td/k = mdk/k ≡ md (mod n). Chaum invented a family of more complicated blind signature algorithms in [320,324], called blind unanticipated signatures. These signatures are more complex in construction, but more flexible. ### 23.13 Oblivious Transfer In this protocol by Michael Rabin [1286], Alice has a 50 percent chance of sending Bob two primes, p, and q. Alice will not know whether the transfer is successful. (See Section 5.5.) (This protocol can be used to send Bob any message with a 50 percent success rate if p and q reveal an RSA private key.) (1) Alice sends Bob the product of the two primes: n = pq. (2) Bob chooses a random x less than n, such that x is relatively prime to n. He sends Alice: a = x2 mod n (3) Alice, knowing p and q, computes the four roots of a: x, n - x, y, and n - y. She chooses one of these roots at random and sends it to Bob. (4) If Bob receives y or n - y, he can compute the greatest common divisor of x + y and n, which is either p or q. Then, of course, n/p = q. If Bob receives x or n - x, he can’t compute anything. This protocol may have a weakness: It might be the case that Bob can compute a number a such that given the square root of a you can calculate a factor of n all the time. ### 23.14 Secure Multiparty Computation This protocol is from [1373]. Alice knows the integer i; Bob knows the integer j. Alice and Bob together wish to know whether i ≤ j or if i > j, but neither Alice nor Bob wish to reveal the integer each knows. This special case of secure multiparty computation (see Section 6.2) is sometimes known as Yao’s millionaire problem [1627]. For this example, assume that i and j range from 1 to 100. Bob has a public key and a private key. (1) Alice chooses a large random number, x, and encrypts it in Bob’s public key. c = EB(x) (2) Alice computes c - i and sends the result to Bob. (3) Bob computes the following 100 numbers: yu = DB(c - i + u), for 1 ≤ u ≤ 100 DB is the decryption algorithm with Bob’s private key. He chooses a large random prime, p. (The size of p should be somewhat smaller than x. Bob doesn’t know x, but Alice could easily tell him the size of x.) He then computes the following 100 numbers: zu = (yu mod p), for 1 ≤ u ≤ 100 He then verifies that, for all u ≠ v |zu - zv| ≥ 2 and that for all u 0 < zu < p - 1 If this is not true, Bob chooses another prime and tries again. (4) Bob sends Alice this sequence of numbers in this exact order: z1 , z2 , ..., zj, zj+1 + 1, zj+2 + 1,..., z100 + 1, p (5) Alice checks whether the ith number in the sequence is congruent to x mod p. If it is, she concludes that i ≤ j. If it is not, she concludes that i > j. (6) Alice tells Bob the conclusion.
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.