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
participants (2)
-
Eric Hughes -
nobody＠shell.portal.com