15

I have recently learned of a way for person B to verify that a document sent from person A is indeed from person A.

  1. Person A gives Person B his public RSA key. This must be done reliably.
  2. Person A uses SHA1 to hash the document in a 160-bit hash.
  3. Person A uses his private RSA key to sign the 160-bit SHA1 hash of the document.
  4. Person A sends both the RSA-signed SHA1 hash and the document to person B.
  5. Person B verifies the hash with Person A's public RSA key.
  6. Person B generates a SHA1 to compare the document Person A sent him.
  7. If the two SHA1 hashes match, then the document is indeed from Person A.

This process seems reliable, but also cumbersome to me. Why can't Person A just encrypt the document directly with his RSA private key and send that to Person B. Why encrypt a hash of the document instead and send it alongside with the document?

Jeff Ferland
  • 38,090
  • 9
  • 93
  • 171
David Faux
  • 253
  • 2
  • 5
  • 5
    The RSA encryption routines are very slow. – Loren Pechtel Oct 18 '12 at 17:46
  • 1
    Your description is a signature. You never mention encrypting the document. Do you want to know about why signatures use hashes, or why we use symmetric encryption for the actual document? – CodesInChaos Oct 18 '12 at 18:50
  • 2
    "Encrypt with RSA private key" is an undefined operation. You cannot encrypt with a private key, only with a public key. – Stephen Touset Oct 18 '12 at 19:13
  • Thanks! Wait, where does symmetric encryption come into play? Also, why is "Encrypt with RSA private key" undefined? Doesn't the public key decrypt? – David Faux Oct 19 '12 at 02:06
  • 1
    @StephenTouset - actually that's how digital signatures work. The two keys (private and public) can both be used to encrypt, and the other one will decrypt it. So to sign something, you hash it and encrypt the hash with your private key. Anyone else can compute the same hash from the original, then decrypt your signature with your public key, and compare. – Scott Whitlock Oct 19 '12 at 10:55

6 Answers6

23

There is more than one reason:

1) Actually the RSA algorithm is slower. For instance:

By comparison, DES (see Section 3.2) and other block ciphers are much faster than the RSA algorithm. DES is generally at least 100 times as fast in software and between 1,000 and 10,000 times as fast in hardware, depending on the implementation. Implementations of the RSA algorithm will probably narrow the gap a bit in coming years, due to high demand, but block ciphers will get faster as well.

Then if you look here you can see that they list DES as taking 54.7 cycles per byte and SHA-1 taking 11.4 cycles per byte.

Therefore computing the SHA-1 hash of the document and signing that is a performance optimization vs. encrypting the entire document with your private key.

2) By splitting the document from the signature you have a more flexible system. You can transmit them separately or store them in different places. It might be a case where everyone already has a copy of the document, and you just want person A to verify to person B that they have the same document (or a hash of it).

3) Thinking about it, if someone encrypts the document with a fake private key, and you decrypt it with the real public key, your algorithm can't actually tell you the result (signed or not). Unless your program can interpret the meaning of the resulting document (perhaps you know it's supposed to be XML, etc.) then you can't reliably say it was 'signed'. You either got the right message, or the wrong message. Presumably a human could tell, but not a machine. Using the hash method it assumes I already have the plain text and I just want to verify that person A signed it.

Say I have a program that launches nuclear weapons. It gets a command file that's encrypted using your method, so I decrypt with the public key and send the result to my command processor. You're then relying on the command processor to know if it's a valid command. That's scary. What if the protocol of the command is just the latitude and longitude of where to target the missile, encoded into binary? You could easily just launch at the wrong target.

Using a hash, you get a command and a signed hash over a plain text channel. You hash the command, check the signature, and if they don't match then you don't bother sending anything to the command processor. If they match, you send the commands on.

If you want to hide the contents of the command, then you take the commands and the signature, zip them together and encrypt the whole thing with the public key of the receiving station before you send them.

Scott Whitlock
  • 416
  • 3
  • 6
3

Sometimes you don't particularly mind letting the whole world read a message (or would rather they did) yet want to provide a mechanism to prove that you wrote the message. Signing does just this.

RSA is slow, but most encryption software using RSA actually encrypts documents with a symmetric cipher like AES, and encrypts the key used (sometimes called a "session" key) with RSA, so the slowdown from encrypting the entire document is not that great.

peejaybee
  • 131
  • 2
1

This would take every byte of the document and turn it into 40 bytes. The documents would be massive files now compared to what they were before. It would take up lots of resources to encrypte, send and decrypt data. I believe encrypting the entire document to send then the other person decryptes it, is much more cumborsome than the way you described.

DFord
  • 119
  • 4
  • 4
    While RSA encryption increases the data size a bit due to padding, it's by far not a factor of 40, more like an increase of 25%. – CodesInChaos Oct 18 '12 at 18:48
1

One word - non-repudiation - it's not really that encrypting the document matters or not, nor does the time taken to encrypt it vs hash it matter much - it's a critical issue with things like large electronic purchase orders, electronic contracts, etc -

When only non-repudiation is required, then there is no need to provide the signer with >>>>DIRECT<<<<< access to/control over the private key - in cases where physical possession of the key >CONTAINER< is required along with a pin, this is often a satisfactory means of producing reliable electronic signatures, e.g. http://en.wikipedia.org/wiki/Common_Access_Card

Mark Mullin
  • 381
  • 2
  • 9
  • Digital signatures are not sufficient for non-repudiation see [How to achieve non-repudiation?](http://security.stackexchange.com/questions/1786/how-to-achieve-non-repudiation) – this.josh Oct 19 '12 at 05:35
  • I beg to differ - the function of a digital signature is non-repudiation, and it is (so far) considered impossible to consider that a digital signature DID NOT REQUIRE POSSESSION OF THE KEY - hence the constraints I gave above and some of the specific considerations with respect to access to the separated public and private key components for signing, and why signing keys are often separated from encryption keys - as far as issues,I think this http://e-archivo.uc3m.es/bitstream/10016/11882/1/Tesis_Jorge_Lopez_Hernandez_Ardieta.pdf is better than your example – Mark Mullin Oct 19 '12 at 14:12
  • @MarkMullin If you read the link this.josh gave, it points out for non-repudiation needs to link the person, not the key. All you know from the digital signature alone is that someone with access of a given private key signed the message. Not that the owner of the private key is Alice. – ewanm89 Oct 19 '12 at 16:22
  • I did read the posting - it was a bit fuzzy, which is why I offered something with a bit more thought behind those exact issues - there's a lot more to digital signatures than this - for example, refer to NIST standards for Federal Financial Management Service (FMS) which specifically dictates mechanisms for non-repudiation of signing purchase orders and other federal obligations – Mark Mullin Oct 19 '12 at 19:46
1

One reason is that this would require to "encrypt" the whole document for every recipient, which could lead to very large file-sizes.

Also when you're encrypting (and not signing like you described) you encrypt the entire document with a symmetric cipher and only encrypt the resulting key with the public-keys of the recipients. Symmetric encryption is much faster and you have much more flexibility over your recipients etc.

Fabian Zeindl
  • 380
  • 2
  • 9
-2

The main reason for this is one of the significant properties of a cryptographic hash function i.e. it is infeasible to find two different messages with the same hash.

If the person encrypts the entire document with RSA and sends his private key along with it, then the main disadvantage is that if the Adversary gets to know the private key, he would also know the message and can modify it.

Now consider these properties of Hash Functions:

  1. It is infeasible to generate a message that has a given hash.
  2. It is infeasible to modify a message without changing the hash.

So, if Alice is using Hash Function, then even if Adversary gets to know the private key by some means of compromization, he would not be able to generate the message because of the hashing. And nor can he modify the message. So, RSA ensures a win-win condition for communication between Alice and Bob.

  • I'm not sure I follow. If someone gets your private key, they can sign any hash they want as if they're you. –  Oct 18 '12 at 18:05
  • 1
    I cringed at "sends his private key". That's not at all the algorithm that's been described. –  Oct 18 '12 at 18:11
  • 5
    -1 - this is wrong. The sender's private RSA key is not released / sent with the document, so your scenario doesn't play out. And your description doesn't prevent a MiM attack. Even if the adversary got the private key, they could modify the message, rehash the altered message, and then encrypt the new hashed. Then they send the altered message + new hash intead. (Props @Tacroy for the adversary edit) –  Oct 18 '12 at 18:17