[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
bank protocol run through
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] |
\-----------------------------------/