[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

*To*: [email protected]*Subject*: bank protocol run through*From*: Karl L. Barrus <[email protected]>*Date*: Wed, 2 Dec 92 21:49:20 -0600

I find it useful to work through a protocol by hand a few times to really see what's going on. Here is an example of the digital bank protocol. It is meant for people who are curious to see if it works, as educational material for new subscribers, or general interest. I'm choosing relatively small numbers to use: in a real implementation, they would be much much larger. OK, let's start! ---------------------------------------- On the bank's side, it chooses the primes p = 2038074743 and q = 2038074947 and so the public key n = pq = 4153749073821763621 also phin = Euler totient function of n = (p-1)(q-1) = 4153749069745613932 The bank decides to make people use the exponent 5 (it's just easier to tell if GCD[5, phin] is 1) 1) Alice chooses a random x, r. She hashes x to yield fx x = 3141526535 r = 5772156649 fx = 2718281828 Here, I just picked the value of the hash function from the mathematical air, so to speak. Alice computes B = r^5 fx mod n = (5772156649^5 2718281828) mod 4153749073821763621 = 592088213321408342 -> B = PowerMod[r^5 fx, 1, n] in Mathematica Alice sends B to the bank. 2) The bank takes fifth root of B. Or, it raises B to the power that is the inverse of 5 mod n. To find the inverse of 5 mod n, compute inv1 = 5^(-1) mod phin = 5^(-1) mod 4153749069745613932 = 1661499627898245573 The bank can do this since it knows the factorization of n. -> inv1 = PowerMod[5, -1, phin] in Mathematica So, to take the fifth root: D = B^inv1 mod n = (592088213321408342 ^ 1661499627898245573) mod 4153749073821763621 = 1189395596986402260 -> D = PowerMod[B, inv, n] in Mathematica Just as a check: D^5 mod n = = (1189395596986402260 ^ 5) mod 4153749073821763621 = 592088213321408342 = B So we're OK. -> Mod[D^5, n] in Mathematica Bank sends Alice D. 3) Alice extracts C by dividing D by r. Or, she solves the following equation for C: D = C r mod n, or 1189395596986402260 = C 5772156649 mod 4153749073821763621 This can be solved by multiplying D by the inverse of r mod n, and taking the result mod n. You don't need to know the factors of n. As a technical note, there will be only one solution since GCD[D,n] = 1, which is usually true since n only has two factors p and q. The bank is in trouble if GCD[D, n] != 1 since that means n can be factored by the information in D. inv2 = r^(-1) mod n = 5772156649 ^ (-1) mod 4153749073821763621 = 3900656075651054436 -> inv2 = PowerMod[r, -1, n] in Mathematica So, C = (D inv2) mod n = (1189395596986402260 3900656075651054436) mod 4153749073821763621 = 3844350519262422248 -> C = Mod[D inv2, n] in Mathematica Just as a check: C r mod n = = (3844350519262422248 5772156649) mod 4153749073821763621 = 1189395596986402260 = D So we're OK. -> Mod[C r, n] in Mathematica So now Alice has x = 3141526535 and C = 3844350519262422248 4) Alice pays Bob by giving him (x, C) 5) Bob verifies that C = fx ^ (1/5) mod n. Or, he verifies that fx = C^5 mod n C^5 mod n = = 3844350519262422248 ^ 5 mod 4153749073821763621 = 2718281828 which does indeed equal f(3141526535) = 2718281828 where f is our hashing function. So Alice isn't cheating by sending a bogus (x, C) But Bob must also send (x, C) to the bank to verify Alice isn't trying to spend the money more than once! ---------------------------------------- So there it is, with numbers and Mathematica statements for those who have access to Mathematica. Hopefully, the numbers are large enough to convince people it didn't work out by chance. Now, the code to perform the math must be written, as well as the scripts to support the bank. Has anyone used the RSAREF routines, or should we stick to what's supplied with PGP? I haven't thought that far ahead. Like I said earlier, I'll pick up work on this in a few weeks. --- /-----------------------------------\ | Karl L. Barrus | | [email protected] (NeXTMail) | | [email protected] | \-----------------------------------/

- Prev by Date:
**uh oh, o-o** - Next by Date:
**Re: Suggest splitting things up** - Prev by thread:
**uh oh, o-o** - Next by thread:
**enjoy enjoy** - Index(es):