sgo.to

Blind Signatures

Sam Goto

This is an open study of RSA Signatures from here and here.

Signatures

Alice wants to send a m = to Bob and prove that the message came from her

  • Alice constructs her public and private keys (how and why?):
    • Alice starts by picking two large prime numbers p = and q =
    • Alice then computes n = n
    • Alice selects an e = .
    • Alice finally d = d.
  • Alice has then a public key e = e, n = = n and private key d = d.
  • If Alice wants to send a public message m = m
    • Alice computes s with her private key by computing m ^ d % n = m ^ d % n = s
    • Alice sends both m = m and s = s to Bob
  • Bob verifies it by:
    • Bob computes r = s ^ e % n = s ^ e % n = r.
    • Correctness: because encryption and decryption on RSA is invertable this is guaranteed to be correct
    • Confidentiality: because only someone that possesses d could create the encryption, its provenance is guaranteed.
    • If check = m == r = m = r = check, then
      • m is guaranteed to have been signed by d.

In practice, m tends to be large, so we typically hash it before signing.

Blind Signatures

Bob wants Alice to sign a message m = m without revealing the it to Alice.

A Blind Signature works as follows (from here):

  • Bob computes a random number k = k (must be relatively prime to n = n).
  • Bob computes t = m * (k ^ e) % n = m * (k ^ e) % n = t.
  • Bob sends t to Alice and asks her to sign it
  • Alice computes the signature using her private key d = .
    • Alice calculates b = t ^ d % n = t ^ d % n = b and sends that back to Bob
  • Bob gets b and remembers that b = t ^ d % n = (m * (k ^ e) % n) ^ d % n = (m ^ d) * (k ^ e ^ d) % n
  • Bob knows that k ^ e ^ d = k because encryption and decryption cancel each other out, so it is equal to 1, so we get (m ^ d) * k % n
  • Bob computes s2 = b / k = b / k = s2.
  • The blind signature s2 = s2 is exactly the same (check2) of the unblinded signature s1 = s
  • Bob can use the traditional non-blinded verification of the signature:
    • Bob computes r2 = s2 ^ e % n = s2 ^ e % n = r2 and checks that it matches m = m.
    • m is guaranteed to have been signed by d.
    • Alice never learns m.