# PKCS1 and blind RSA signatures

Wikipedia's article on RSA blind signatures says that you need to raise the message $m$ to the secret exponent $d$ modulo the public modulus $N$.

Implicit within that, it seems to me, is that m needs to be less than $N$. Problem with that is that that's not a restriction imposed upon signatures.

So for blind signatures to work as Wikipedia describes them you need to set $m$ to the hash or to the output of EMSA-PKCS1-v1_5-ENCODE or EMSA-PSS-ENCODE instead of setting $m$ to the plaintext. And then you do the modular exponentiation after you've blinded $m$.

IE.: you kinda have to side-step RSASSA-PSS-SIGN or RSASSA-PKCS1-V1_5-SIGN for blind signatures to work correctly.

Is that correct?

-
I'd certainly choose a deterministic padding for blind signatures. In the simplest case, full domain hash. –  CodesInChaos Sep 18 '13 at 7:05

No, that is not correct. You appear to have a misconception about how RSA signatures work.

Here is how an RSA signature is generated:

• You take your message $M$

• You apply a padding function to create a value $m = pad(M)$

• You then use the RSA private key to compute $m^d \bmod N$

Now, this last step isn't always done in the straight-forward manner. With blinded RSA signatures, it's done using a random value $r$ to defeat some side channel attacks; however that isn't that important for how RSA signatures work in general. In particular, the value that a blinded RSA computes is precisely the same as a nonblinded version; it just uses a different algorithm to get that value. In addition, that's the only part that's different for "blinded RSA signatures"; in all other respects, they are computed precisely like any other RSA signature.

You appear to be expecting that you can skip step 2, and step the value $m$ to the message $M$. However, that can be dangerous; one of the issues with using RSA without padding is that the RSA operation (either public or private) preserves multiplication, that is:

$RSA(a) \times RSA(b) = RSA( a \times b )$

(where both multiplications is done modulo $N$).

What this means is that if someone gets a series of messages $m_1, m_2, ..., m_n$ with their unpadded signatures $RSA(m_1), RSA(m_2), .., RSA(m_n)$, they may be able to find a message $m_{evil} = m_1^{e_1} m_2^{e_2} ... m_n^{e_n}$ (for some set of exponents $e_1, e_2, ..., e_n$; note that some exponents may be negative). The attacker typically can do this if some of the $m_1, m_2, ..., m_n$ values are smooth (consists of only small factors); if there are enough smooth values, the attacker may be able to find a subset that they can recombine to form $m_{evil}$. If that attacker can do that, that means that he can immediately deduce the signature $RSA( m_{evil}) = RSA(m_1)^{e_1} RSA(m_2)^{e_2} ... RSA(m_n)^{e_n}$

Signature padding methods are designed to prevent this; the value $pad(M)$ are large values, and hence are extremely unlikely to be smooth.

Hence, it is considered a Good Idea to always have a padding method when generating RSA signatures.

-
I'm not proposing unpadded rsa. I'm proposing doing EMSA-PKCS1-v1_5-ENCODE but not the full blown RSASSA-PKCS1-V1_5-SIGN –  neubert Sep 17 '13 at 23:28
@neubert: Huh? The EMSA-PKCS1-V1_5-ENCODE is just the padding operation. Are you saying that you'll be doing the padding, but not the RSA part? If not, what are you saying? –  poncho Sep 18 '13 at 1:41
You do EMSA-PKCS1-V1_5-ENCODE, blind and then do modular exponentiation. RSASSA-PKCS1-V1_5-SIGN is EMSA-PKCS1-V1_5-ENCODE and modular exponentiation. Blinding has to be done in the middle of those two, it seems to me, hence my saying you have to side-step RSASSA-PKCS1-V1_5-SIGN. –  neubert Sep 18 '13 at 3:38
Also, it seems to me that it necessarily needs to be broken up anyway. If you were going to sign the message wouldn't be a blind signature. It'd be a regular signature. So you pad the message, don't do RSA, blind it, and then send it off to the signer for them to sign it. But since they're signing a blinded message they wouldn't know what the original message was. Of course since you're sending a padded hash it seems to me that they wouldn't know what the orig message was anyway. Unless I'm totally misunderstanding blind signing. –  neubert Sep 18 '13 at 3:41
@neubert When you actually use blind signatures (e.g. to implement Chaumian E-Cash) then the padding is done by a different entity than the private key operation. One important consequence is that the padder wants to forge signatures, so it doesn't seem like a good idea to use a probabilistic padding scheme. –  CodesInChaos Sep 18 '13 at 9:46