An excellent description of blinding and digital
cash, forwarded from sci.crypt:
In article <24924cINNg4c@network.ucsd.edu>,
loki@sdphu3.ucsd.edu (Lance M Cottrell) writes:
-----BEGIN PGP SIGNED MESSAGE-----
Some time ago I read an article in Scientific American
about using RSA and smart cards to achieve untraceable
and unforgable electronic cash. The system hinged on being
able to "blind" a message which would be signed
by the bank, and then the blinding would be removed
without disturbing the signature. The signed message
would then decrypt to the original message, but the signer
would not know what she had signed. The article made no
mention of how to do this "blinding".
This morning I came up with a method which I would like
comments upon. First the notation
^ : exponentiation
n : the bank's modulus (p*q in usual notation)
e : the exponent used to encrypt the message sent
to the bank
d : the exponent used to decrypt the bank's encryption.
t : the text that you want signed.
x : some random number with a multiplicative inverse mod n.
y : the inverse of x mod n.
c : the cipher text corresponding to t
a : the blinded plain text
b : the encrypted blinded text.
Now the procedure.
blind the plain text by
a = ((x^d) * t) mod n
the bank encrypts a by
b = (a^e) mod n
= ((((x^d)^e)mod n) * ((t^e)mod n)) mod n
the blind is removed by multiplying through by y
since ((x^d)^e)mod n = (x^(d*e))mod n = x
c = y * b
= (y * x * ((t^e) mod n))mod n
= (t^e) mod n
The question is, can one find x and y such that
(x*y) mod n = 1, and can the bank recover t when only given a.
Also, please tell me if there is some fundamental error in
my handeling of math mod n.
Many thanks for any comments. If anyone knows the method the
original authors used, please post that as well.
Fine description of Chaum's blind signature protocol. Your
math looks good.
It is easy to find y, given x and n, such that (x*y) mod n = 1,
(provided gcd(x,n)=1, as it is for most x ).
See Knuth Vol II section 4.5.2, or look up the extended
Euclid's algorithm in some good algorithms text.
The bank can not tell which t was signed via some a, since
for any t and a with t in the multiplicative group mod n,
there is some x such that a=x^d * t (mod n).
Thus (1)the procedure is tractable, (2)blind forgeries are
only possible if RSA is weak, and (3)the "blind" is
unconditionally secure.
Bryan Olson
olson@umbc.edu