-----BEGIN PGP SIGNED MESSAGE----- Cypherpunks, or maybe that's Atompunks, Earlier, Hal posted several excellent messages concerning Brands' cash, and some introductory material. I always find it useful to work through various protocols by hand (well, with Mathematica), working with real numbers to help understand the protocol and how it works. So like I did a long time ago when Hal posted a description of Chaumian cash, I will give an example of the protocols described. I intend to follow along Hal's posts and work math as it comes up (and try to keep the notation consistent!). I'll not be using numbers large enough to give actual security. For folks with Mathematica, the functions of interest are PowerMod[a,b,c] to calculate a^b mod c, and Mod[a,b] to calculate a mod b. Hal's first post was introductory material on discrete logs: * Generators
Discrete-log based cryptosystems generally work with a modulus n which is prime, along with a "generator" g < n such that the series g^0, g^1, g^2, ... , includes all values from 1 to n-1. It is pretty straightforward to find such n's and g's. It is easy to compute g^x for any x, but intractable to calculate x given just g^x.
Finding a generator g is easy if you know the factorization of n-1. You just need to calculate g^((n-1)/q) mod n for all values of q, the prime factors of n. If any of the results are 1, then g is not a generator. So say you want to see if 5 is a generator mod 2047. The prime factors of n - 1 = 2046 are { 2, 3, 11, 31 }, so you calculate: 5 ^ (2046/2) mod 2047 = 1034 5 ^ (2046/3) mod 2047 = 622 5 ^ (2046/11) mod 2047 = 1435 5 ^ (2046/31) mod 2047 = 622 None of these turned out to equal 1, so 5 is a generator mod 2047. * Diffie-Hellman key exchange
1. Alice chooses a random x and sends GX = g^x to Bob. Bob chooses a random y and sends GY = g^y to Alice.
Let's use g = 10, and pick p = 17389. 10 is indeed a generator mod 17389. Alice chooses x = 53, and calculates g^x mod p = 10^53 mod 17389 = 9059 Bob chooses y = 4321 and calculates g^y mod p = 10^4321 mod 17389 = 16077 They exchange, so Alice receives GY = 16077 and Bob receives GX = 9059
2. Alice calculates GY^x, which is g^(y*x). Bob calculates GX^y, which is g^(x*y).
Alice calculates 16077^53 mod 17389 = 11643 Bob calculates 9059^4321 mod 17389 = 11643
3. These are equal, so they use them as their shared secret value.
Alice and Bob agree to the shared secret 11643.
An observer sees only GX and GY, and without knowledge of x and y is unable to calculate g^(x*y).
* DH-based identification protocol For this example, suppose we use g = 10, p = 17389 as above. Also, Paul chooses x = 555 to be his private key, therefore 10^555 mod 17389 = 11106 is his public key.
1. Vicki chooses a random y and sends GY = g^y to Paul.
Vicki randomly chooses y = 1994, so she sends 10^1994 mod 17389 = 13848.
2. Paul calculates GYX = GY^x = g^(y*x) and sends that back to Vicki.
Paul calculates 13848^555 mod 17389 = 8324, and sends it back.
3. Vicki confirms that GYX = GX^y; both should be g^(x*y).
Vicki checks 11106^1994 mod 17389 = 8324. This matches what Paul sent back. * Schnorr identification protocol
1. Paul chooses a random w and sends GW = g^w to Vicki.
Paul chooses w = 200, and sends 10^200 mod 17389 = 14097 to Vicki.
2. Vicki chooses a random c and sends it to Paul.
Vicki chooses c = 561 and sends this to Paul.
3. Paul calculates r = cx+w and sends that to Vicki.
Paul calculates r = 561 * 555 + 200 = 311555.
4. Vicki confirms that g^r = (GX^c)*GW. Both should be g^(cx+w).
Vicki checks: 10^315555 mod 17389 = 4594 (11106^561) 14097 mod 17389 = ((11106^561 mod 17389) * 14097) mod 17389 = 4594 * Chaum discrete log interactive signature protocol Here, we'll pick m = 1040. Thus, Paul can calculate MX = 1040^555 mod 17389 = 8608
1. Paul chooses a random w and sends GW = g^w and MW = m^w to Vicki.
As above, Paul chooses w = 200, so he sends GW = 14097 and MW = m^w mod p = 1040^200 mod 17389 = 472 to Vicki.
2. Vicki chooses a random c and sends it to Paul.
She chooses 561 again.
3. Paul calculates r = cx+w and sends that to Vicki.
He calculates 311555 again.
4. Vicki confirms that g^r = (GX^c)*GW. Both should be g^(cx+w). She also confirms that m^r = (MX^c)*MW. Both should be m^(cx+w).
Vicki checks g^r as above. Now she also checks: m^r mod p = 1040^311555 mod 17389 = 13723 (MX^c)*MW = (8608^561)*472 mod 17389 = 13723 * Chaum discrete log signature protocol Well, this is similar to the above protocol except a hash function is used. I'll do something similar for Hal's other posts as time permits. Karl Barrus klbarrus@owlnet.rice.edu -----BEGIN PGP SIGNATURE----- Version: 2.6 iQCVAgUBLl5uPsSF/V8IjI8hAQE4/AP/VNauuo2nIWvF7xukbh6zNXK/pTnD7vGM 7jQeD9Hk7z9a/GXD2OTjlKUf1HAtFRkPB95X3HS/u5TzO1RdUIoxuiUok38At8vX UUBaRXaF6JJUI8xkvgOt9qCrSnZNKhjh4wZ2JxxOUY/0rB/1TBRzPe/MIIzyy0Ee bKaCRv+gJLA= =esaf -----END PGP SIGNATURE-----