RSA blind signatures in practice

Question

Hi I have a problem with moving my blind signature implementation from educational (textbook RSA) to more practical (padded RSA) side.

David Chaums paper gives a following figure:

$r$ - blinding factor

$e$, $d$ - public & private exponent

$Blinded\ message = Message \cdot r^{e}$

$Signature\ of\ a\ Blinded\ message = Blinded\ message^{d} = (Message \cdot r^{e})^{d} = Message^{d} \cdot r^{ed} = Message^{d} \cdot r\ (\bmod\ N)$

now to unblind a blinded message we should remove the blinding factor:

$Unblinded\ signature = Signature\ of\ a\ Blinded\ message \cdot r^{-1} = Message^{d} \cdot r\ \cdot r^{-1} = Message^{d}\ (\bmod\ N)$

It is clear that real-world RSA implementation shouldn't use plain textbook for encryption or signature purposes as it is vulnerable to a range of attacks. To overcome these attacks a textbook must be armoured with "padding", prior encryption or signature operation.

Now, as far as I understood (in simple English): a "padding" process "changes" the plain text prior encryption to make it more durable to known attacks.

Mathematically speaking, the whole process would look like:

$Signature\ of\ a\ Blinded\ message = pad(Message \cdot r^{e})^{d} (\bmod N)$

In other words "padding" destroys blind signature, because there is no such "$unpad$" function that would satisfy the following equation:

$unpad(pad(Message \cdot r^{e})^{d})\ (\bmod N) = (Message \cdot r^{e})^{d}$

So this means blind signatures can not be used with padding.

Question Am I correct that using blind signatures in practice, one should never use a public/private key pair for both encryption and blind signature purposes together, and to actually use a blind signature that person is obligated operate on a plain textbook making the whole process vulnerable to a range of attacks?

---

EDIT

As far as I understood the whole process, there are two sides A - Applicant, B - Bank. For example Applicant creates a token that represents 10\$ with serial number AH43S, then Applicant blinds the token with random R so that the Bank is not able to discover token's serial number. Then applicant sends blinded token to Bank, and asks it to sign with 10\$ key. Now Bank needs to pad a blinded version of token, to prevent any attacks on it's key, and after the blinded token is padded there is no way to unblind it...

The padding is applied on the bank side(side that signs the message), am I correct? And if so, it would break blinding factor presented by the side that asked to sign a token...

Answer 1

The answer is correct, you don't need to unpad the message. When/if you verify the signature, simply check that $(\text{signature})^e == \text{pad}(\text{message})$

Regarding the padding scheme, you can just use a full domain hash.

Here's how you implement a full domain hash: $$ \mathrm{cycles} = \frac{\text{(RSA key length)}}{\text{(SHA digest length)} \times 8} + 1$$ (e.g., RSA key length = 1024bits and SHA digest length = 20bytes) $$ \mathrm{FDH}(M) = \mathrm{SHA1}(M || 0) \mathbin\Vert \mathrm{SHA1}(M || 1) \mathbin\Vert \ldots \mathbin\Vert \mathrm{SHA1}(M || \mathrm{cycles}-1)$$

where $||$ denotes concatenation

Answer 2

I'm not really familiar with blind signature schemes, so please take the following with a grain of salt, but what you describe looks like a really funny way to apply padding. Normally, one would pad the message (using a suitable padding scheme like RSA-PSS) before the first RSA operation, i.e.

• $\text{padded message = pad(message)}$
• $\text{blinded message = padded message} \cdot r^e \pmod N$
• $\text{blinded signature = blinded message}^d = \text{padded message}^d \cdot r \pmod N$
• $\text{signature = blinded signature} \cdot r^{-1} = \text{padded message}^d \pmod N$