7

With public key encryption you encrypt using a public key. But when creating digital signatures you sign by encrypting a hash using a private key.

I understand the principles of these two uses of public key cryptography, but I cannot reconcile in my head how or why the roles of the keys suddenly reverses. Does digital signing somehow build upon the concepts of public key encryption? or are the underlying algorithms completely different?

  • 5
    You do not encrypt anything when signing. You sign. The fact that these are the same mathematical operations in RSA does not mean they should be treated as exchangeable. Outside of RSA, they tend to be different mathematical operations, anyway. – marcelm May 7 '17 at 14:22
  • @marcelm And signing means encrypting the hashof the content with your private key. – defalt May 7 '17 at 15:14
  • 2
    @defalt : ​ No; see this question and answer. ​ ​ ​ ​ – user49075 May 7 '17 at 17:10
  • @RickyDemer The question says you encrypt the hash of the message to sign it. – defalt May 7 '17 at 17:41
  • 1
    @defalt : ​ ​ ​ Is ​ "The question" ​ the one we're commenting under or the one I linked to? ​ ​ ​ ​ ​ ​ ​ ​ – user49075 May 7 '17 at 17:43
15

I cannot reconcile in my head how or why the roles of the keys suddenly reverses.

(I'm primarily focusing on RSA signatures.)

Anyone can produce an encrypted message (by using your public key) and only you can decrypt it (by using your private key). The roles of public and private key reverse because a signature has to be something that only you can produce (by encrypting with your private key) and everyone else can confirm (by decrypting with your public key).

The basic assumption is that if you publish a ciphertext that can be decrypted to a meaningful message with your public key, you have proven that you own the private key, because otherwise you wouldn't be able to produce such a ciphertext. (Note that this plain RSA signature algorithm is insecure for numerous reasons. Most notably, in practice you should never sign a full message text, but a hash of the message.)

You can simply swap the roles of public and private key because the mathematical design of RSA allows you to encrypt a message with either key and decrypt it with the other one - resulting in the same original plaintext both ways. That's because the encryption exponent e is the multiplicative inverse of the decryption exponent d modulo φ(N) (where N is the RSA modulus and φ is Euler's totient function). That is, 1 ≡ ed ≡ de (mod φ(N)).

Also see: How does RSA signature verification work?

  • I understand the theory. I don't understand how, in one use case the public key is the encryptor, while in another it is the decryptor. – Phil_1984_ May 6 '17 at 23:57
  • 2
    @Phil_1984_ Do you not understand how that would be mathematically possible? If that's the case I'm happy to elaborate on that. – Arminius May 7 '17 at 0:00
  • 4
    @Phil_1984_ To reword Arminius's excellent answer: If you encrypt something with the public key, it can be decrypted with the private key. You can ALSO encrypt something with the private key, and decrypt it with the public key. They are mathematically designed to work in both directions. The reason for the former is to create something only the holder of the private key can view (e.g., secure messaging); the reason for the latter is to create something only the holder of the private key could have created (e.g., a signature to verify your identity). – Matthew Read May 7 '17 at 6:08
  • 3
    @Phil_1984_ RSA is "symmetrical" in that you can encrypt with either key and decrypt with the other one. For other kinds of public-key encryption, you can't encrypt with the private key. – immibis May 7 '17 at 8:02
  • 1
    Thanks for this great answer. I did not realise that RSA keys were symmetric and could be used in this way. In fact, I thought the exact opposite because private keys are much longer than public keys. – Phil_1984_ May 8 '17 at 7:31
9

I understand the principles of these two uses of public key cryptography, but I cannot reconcile in my head how or why the roles of the keys suddenly reverses.

That is the only way it makes sense. Encryption would be uselesss, if anyone could decrypt it, thus you have to need the private key for decrpytion.

Conversely, a digital signature would not make sense if anyone could create it, ergo the private is required to create it.

Does digital signing somehow build upon the concepts of public key encryption? or are the underlying algorithms completely different?

That depends on the algorithm. For RSA, encryption and signature is (mostly) the same operation with the keys reversed. With others, like ElGamal, signing and encrypting is only slightly similar techically, but you can, theoretically, reuse keys. Finally, there are schemes which are specialised to one of the operation. For example, Hash based signatures do not have any encryption counterpart.

1

The two keys are used at the opposite ends of the encryption/decryption process. You use either of the keys in the keypair to encrypt the data and the other key is required for decryption. The process requires a pair and it's prohibitively complicated to find a another key that just happens to be able to produce the same results as one you are trying to replicate.

Everyone knows the public key, therefore everyone can send a message using that key which only the private key holder can open. The public key won't decrypt the message.

Only one person has the private key, therefore everyone can be sure that a message opened by the matching public key really did come from that person. The important part here is that if the public opens it then the private key must have been used to sign it.

1

If I understand your question correctly, I'm not sure if the existing answers really address it.

It seems you may be wondering where the anti-symmetry fundamentally comes from.

If so, I'll try to explain. (No one's told me this, but I think this is where it comes from.)


First, let's remember (or learn!) what "information" is:

Information is the ability to distinguish possibilities.

In other words, when you get more information about something, that means you now have the ability to tell apart two different possibilities that otherwise looked the same to you.

You know the quote "You never learn anything by talking"? In information-theoretic terms, it means:

Communication can only benefit the receiver, not the sender.

In other words, when you send someone information, you don't gain any ability to distinguish possibilities. Only the receiver can get that benefit.

Now, consider what each of these means in a ONE-WAY communication channel (i.e. 1-way trust):

  • Signing is for protecting against unauthorized production (writing) of information.
    It is for the benefit of the receiver (reader). It's the writer's way of proving "yes, this is really me". Absent a 2-way communication channel, the writer receives no benefit from this. It's strictly for the reader's benefit.

  • Encryption is for protecting against unauthorized consumption (reading) of information.
    It is for the benefit of the receiver (reader). This is not obvious, at least until you realize I'm talking about a one-way communication channel. In a one-way channel, the sender has not authenticated the receiver—so, effectively, the sender might as well be broadcasting the information, since he doesn't trust the receiver, and the receiver can reveal the information if he desires. The only reason to encrypt would be to protect the receiver.

Notice we have an anti-symmetry between reading and writing, but we don't have a corresponding antisymmetry between reader and writer!

So that means the situation is inverted.... and that fact results in the reversal of the roles of the public and the private keys.

  • While it might be slightly OT, still +1 because that seems to be important basic theory relevant to the question - and counterintuitive too, compared to what sender/receiver roles are in commerce and psychology :) – rackandboneman May 7 '17 at 12:29
  • Oh, I found an exception, and that is if your information channel is a command channel - the sender knows - by sending - what will happen unless the receiving end is malfunctioning :) That's why securing a command channel also brings different requirements (tamper proofing has more weight than preventing eavesdropping)... – rackandboneman May 7 '17 at 12:31
  • @rackandboneman: Thanks! Can you explain what you mean by a command channel being an exception? What is it an exception to, exactly? – Mehrdad May 7 '17 at 16:49
  • Anything where the receiver will reliably act in a deterministic (or even statistic!! Think advertising vs falsified advertising...) manner to the senders information. This can be to the benefit of the sender, and the sender gains the information he sent (receiver will do xyz) by sending. Unauthorized production can be distastrous to the sender here. – rackandboneman May 7 '17 at 18:27
  • @rackandboneman: I think I see what you're saying but the sender doesn't even know who the receiver is, right? We're analyzing encryption and signing separately from each other, so the signed message is not encrypted, and the encrypted message is not signed. The sender has no way to tell who is receiving the information. How do you know how a different recipient would react? I can't see how I could claim that the net benefit is positive (even on average) without authenticating the receiver... – Mehrdad May 7 '17 at 23:18
1

In the RSA cryptosystem, encryption, decryption, signing and signature verification are all done with the same mathematical operation: modular exponentiation.

Also, mathematically, there is no difference in RSA between the private key and the public key; they're just two pairs of numbers (e, n) and (d, n), where the shared modulus n is a product of two (or sometimes more) large primes, and e and d are chosen so that xedx (mod n) for all x.

Conveniently, it turns out that choosing such numbers e and d is easy to do if you know the prime factors of n, but very hard if you don't (even if you know one of e and d already). So you can pick two random large primes, multiply them together to get n, choose suitable e and d, and then publish n and one of e or d (conventionally, we call the public one e and the other one d) while being pretty confident that nobody else can figure out which number d corresponds to your n and e.

(The math even allows you to fix one of e and d to be (almost) any number you like, and then compute the other one based on it and the prime factors of n. For example, you can always pick e = 3 or e = 65537 = 216+1 to make calculating xe mod n a little easier. Of course, if you do that, you'll want to make the constant number the public one, because if you and everyone else always used the same secret number d, it wouldn't really be much of a secret, would it?)

It then also turns out that, while it's easy for anybody to compute y = xe mod n for any x, and for you (since you also know d) to compute x = yd mod n, it's very hard for anyone who doesn't know d to figure out which (sufficiently randomly chosen) x corresponds to any given value of y. And there are at least two convenient practical applications for this property:

  1. You can let anyone "encrypt" a number x by computing y = xe mod n, so that only you can easily "decrypt" the resulting y back into x = yd mod n.

  2. You can "sign" any number y by computing the "signature" x = yd mod n and publishing it, and anybody can verify that your signature x matches the original number y = xe mod n, but nobody except you can easily come up with a signature x that would match a specific number y of their choosing.

Of course, in practice, there are some limitations to this. For example, when using RSA for encryption, it's important for the number x being encrypted to always be unpredictable; if somebody can guess a likely value for x, they can just compute xe mod n and see if it matches the actual encrypted number y.

And similarly, when using RSA for signing, it's always possible for anybody to just pick a fake "signature" x and calculate a (essentially random) number y = xe mod n that matches the signature x; thus, it's important to restrict the range of valid numbers y to only a very small subset of the full range from 1 to n−1, or to otherwise ensure that such signatures of (pseudo)random numbers are useless as practical forgeries.

The usual way in which these practical issues are solved is by padding the input numbers (x for encryption, y for signing) in ways that make them unpredictable and/or allow the correctness of the padding to be verified (in such a way that randomly chosen numbers are vanishingly unlikely to pass the check). In practice, different padding schemes are generally used for RSA encryption and for RSA signing, since the security requirements for these two distinct uses are somewhat different. Thus, while the modular exponentiation part is essentially the same for all four RSA operations (encryption, decryption, signing and signature verification), the additional (un)padding operations required to actually make the system practically secure are different.

Anyway, the point of all this is that your original question is based on a false dichotomy.

Insofar as it's meaningful to describe RSA signing as being equivalent to "encryption with the private key" (i.e. insofar as you ignore the padding and just focus on the modular exponentiation), it's also just as meaningful to say that it's equivalent to "decryption with the private key", or even "verification with the private key", since all of these are, mathematically, really just different names for modular exponentiation. Except, of course, that in practice all those operations also involve some (un)padding, which makes all of them different.

And of course, the reason why you always use the private key for signing (and for decryption) is that if you used the public key for it then, since it's public, anyone else could do it too. And that would defeat the point of using crypto in the first place.

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.