1

I understand the encryption process uses a generated symmetric key to encrypt a message, and then encrypts the symmetric key with the receiver's public key before it is sent across the wire. This creates a situation that only the owner of the correlating private key can decrypt the symmetric key, and therefore decrypt the encrypted message.

I would like to understand the exact order of things for message signing. Mostly, something that looks like this, but for signatures.

I understand it may vary by protocol, and if so, describing the exact way a particular protocol would still be a good answer if you can also list at least a few pros/cons of doing it that way, verses any other protocol's strategy.

Within that, my main confusion point is:

  • If asymmetric encryption operations are more taxing on the CPU, and I am planning on sending many many messages, wouldn't there be a better (more efficient) way using some sort of symmetric key to encrypt the message digests that can be reused for many messages? Then using asymmetric encryption to exchange the symmetric key? Could that still prove a message was sent by a sender, while taking advantages of the efficiencies of symmetric encryption?
7

In message signing, there is no encryption. Otherwise we would call it encryption.

A signature algorithm is, nominally, the combination of three sub-algorithms:

  • Key pair generation: that algorithm produces a brand new public/private key pair, using some strong random source, and using as parameter a "security level" to achieve (i.e. the size of the key that is to be generated).

  • Signature generation: inputs are the message to be signed m and the private key. The output is the signature value s.

  • Signature verification: inputs are the message m, the signature s, and the public key. Output is a boolean value: "true" if the signature matches the message and the public key, "false" otherwise.

The signature generation and verification algorithms are supposed to be able to process messages of arbitrary length, possibly gigabytes. And they do. Existing signature algorithms are already very efficient at handling huge inputs. So there is no problem which would require some additional construction, contrary to asymmetric encryption where something else is needed to cope with the severe limitations of these algorithms.

Most texts that talk about hybrid encryption say that we need to do that because asymmetric encryption is slow, but that's wrong. The real reason why hybrid encryption is used is because known asymmetric encryption algorithms cannot simply process messages of arbitrary length, and we have no real idea about how we could alter them in order to do so securely. Basically, the "chaining modes" for block ciphers do not have equivalents for asymmetric encryption that would be obviously safe. However, signature algorithms never had a limitation on input length to begin with, so that is a non-issue.

It so happens, internally, that most signature algorithms are efficient at handling large inputs because their first step is to process the complete message through a cryptographic hash function, and then work only over the hash value. This is a design element of most signature algorithms and should be of no concern to outsiders who just use the algorithm. It does explain, though, why some people discussing about "RSA signatures" suddenly begin to talk about hash functions such as SHA-1: this is because the signature algorithm includes, as one of its building elements, a hash function. Note that some algorithms do not work exactly that way; it would be wrong to claim that all signature algorithms begin by simple hashing.


Ultimately this is a matter of terminology. In the case of asymmetric encryption, e.g. RSA, it is traditional to talk about "the encryption algorithm" as using only a short input; and any extra symmetric encryption layer is considered to be, indeed, some extra, outside layer. However, in the case of digital signatures, the same tradition holds that the initial hashing step is part of what we call the "signature algorithm".

There are some good reasons for this terminology choice; in particular, we want the hash function to be part of what we call the "signature algorithm" because using a signature algorithm like RSA or ECDSA without a hashing step (using a "short input" directly with no hashing) may induce severe weaknesses. However, at its core, it still is a terminology issue.

  • Is it really because they cannot process message of arbitrary length? crypto.stackexchange.com/a/8571/16369 – Gudradain Oct 22 '15 at 20:30
  • Yes it is. The notion about "too many CPU cycles" is just the traditional way to explain things, but, as many traditional things, it is wrong. It can be traced back to the first PGP implementation, at a time where the security of chaining modes was not well understood, which explains the weirdness of what PGP does. In the head of Zimmerman, it was a problem of CPU, but since then we learned a lot and now know better; you can always add more CPU, but making a secure RSA-based chaining is a lot harder. – Tom Leek Oct 23 '15 at 13:08
2

Image Source

enter image description here

The data is first hashed so that a unique representation of that data is generated, and the digital signature of that hash is computationally cheap. Generally the signing of the hash only applies to the key exchange to ensure that everything was received and sent correctly by both parties.

Generally each individual message is verified using an HMAC algorithm. This is on the order of symmetric encryption/decryption speeds so that the CPU doesn't get overworked.

  • 2
    Your diagram explains the signature as being "encryption with the private key". For this offence against logic and pedagogy, I shall be forced to extract your spleen with a blunt spoon. – Tom Leek Oct 22 '15 at 18:40
  • Blast... I didn't notice this sigh, found a better image. – RoraΖ Oct 22 '15 at 18:44
  • @TomLeek For RSA, isn't that basically what a signature is? A hash of the message, encrypted with the sender's private key? – Ajedi32 Oct 23 '15 at 13:20
  • 2
    No, it is not "encrypted with the private key". This is a flawed analogy that does not work for algorithms other than RSA, and, when looked at closely, does not work for RSA either. It is an old way of explaining signatures that, in practice, spreads more confusion than enlightenment. – Tom Leek Oct 23 '15 at 17:06
1

If you want non repudiation and identification security properties valid also in legal cause the sender have to sign the digest with the private key that has to be valid at the sign time by Certification Authority.

If these properties are not necessary, a symmetric key, with adequate length for robustness, can be used to encrypt the digest and, if the key exchange phase is been done in privacy, it is enough to provide only integrity of the message because there's any possibility to proof that the message comes from a specific peer.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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