PKCS1 and blind RSA signatures

Question

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?

Answer 1

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.