Blinded RSA signatures

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

> 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.  

Apparently the first author (the one being quoted in the forwarded
message) had never been exposed to the relevant math before.  What is
therefore significant is that this person has exactly reconstructed
the basic Chaum blind signature, except for notation.

The basic blind signature does not work well in practice, since the
product of two such signatures is also a signature.  In practice one
signs a one-way hash function of the message text and exhibits the
actual text; this destroys the ability to multiply signatures, assuming
that finding multiplicative pairs for the hash function is hard.

This scheme of algebraic blinding is quite easy to apply, once you get
the hang of it.  For example, it is behind the core of the encrypted
open books protocol, where to blind g^x you create a pair g^(x+r),h^r.
Basically all of the atomic operations that recent cryptology uses--
e.g. exponentiation in finite rings, both in the discrete log systems
and in RSA, integer multiplication in elliptic curves--are amenable to
blinding.  The El Gamal signature scheme uses a random number to
create the signature pair.

Applications to existing protocols are left as an exercise by the
reader.

Eric