Information Security Stack Exchange is a question and answer site for information security professionals. It only takes a minute to sign up.
Sign up to join this community
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?
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)).
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.
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.
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:
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:
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.
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 xed ≡ x (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:
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.
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.
