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.

I've seen an example of how to sign using RSA. Besides the signing itself (s = m^d mod n) it also hashes and adds an IV.

Why is that needed?

share|improve this question

3 Answers 3

up vote 12 down vote accepted

A second reason that a hash is usually present in RSA signature schemes (apart from being able to sign long messages) is to prevent existential forgery attacks. These look like this:

Assume we have the public key $n$, $e$. Choose some random garbage $s$ (smaller than $n$), and calculate $m = s^e \mod n$ (i.e. "RSA encryption"). If you used "text book RSA signature" (without a hash and any padding), you now have a message $m$ with a fitting signature $s$.

With a hash, the signature checking equation is $H(m) \equiv s^e \mod n$ instead of $m \equiv s^e \mod n$, and this does not allow to create a message $m$ fitting to an arbitrary signature $s$ (assuming the hash function is preimage-resistant). Beware however that it is remains possible to create working $(m,s)$ pairs given the capability to obtain the signatures $s_j$ of chosen messages $m_j\ne m$, using an attack devised by Desmedt and Odlyzko (see section 3 of this paper).

(The padding scheme normally present in signatures serves the same purpose, and is designed to also resist chosen-messages attacks.)

share|improve this answer
    
Thanks for the answer. –  ispiro Apr 30 '12 at 14:32

Signing a hash is cheaper than signing the whole document. RSA is relatively costly, and, as long as the hash function is not weak, there isn't any practical difference in security between signing the whole plaintext and signing its hash, because the hash uniquely identifies the plaintext.

Wikipedia says:

There are several reasons to sign such a hash (or message digest) instead of the whole document.

  • For efficiency: The signature will be much shorter and thus save time since hashing is generally much faster than signing in practice.
  • For compatibility: Messages are typically bit strings, but some signature schemes operate on other domains (such as, in the case of RSA, numbers modulo a composite number N). A hash function can be used to convert an arbitrary input into the proper format.
  • For integrity: Without the hash function, the text "to be signed" may have to be split (separated) in blocks small enough for the signature scheme to act on them directly. However, the receiver of the signed blocks is not able to recognize if all the blocks are present and in the appropriate order.
share|improve this answer
    
Thanks. So if my message is short enough – there's no need. Correct? –  ispiro Apr 27 '12 at 13:58
    
@ispiro: yes, theoretically. In practice hash is (usually?) still computed (e. g. GPG). –  Mischa Arefiev Apr 27 '12 at 14:45

Salts add an additional level of security.

All your passwords are hashed and saved in your database using some algorithm or the other. This hash is generated the way and is uniform for all your users (assuming they all have the same password). By using a salt you will basically be giving different users with the same password different hashes.

And that means that if the attacker figures out how to get your plaintext password by creating a rainbow table. He wont just magically have everyone elses password as well. He's goign to have to generate a rainbow table for every user individually.

Note: I am no expert. But I did take a class on security once and that's what I remember from it. Hopefully this answers your que

share|improve this answer
    
Thanks. But I'm referring to signing, and so it seems unlikely (correct me if I'm wrong) that someone will have a table for a rainbow attack for all 100 bit combinations. –  ispiro Apr 27 '12 at 12:02
4  
This is a nice answer to the question »Why use a salt when hashing passwords«, but it is not relevant at all to »Why use a salt when signing messages«. –  Paŭlo Ebermann Apr 27 '12 at 16:47

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.