Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
    
    
I'd certainly choose a deterministic padding for blind signatures. In the simplest case, full domain hash. –  CodesInChaos Sep 18 '13 at 7:05
add comment

1 Answer

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.

share|improve this answer
    
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
show 2 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.