Asymmetry between public key and private key: digital signatures use the private key for “encryption”?

Question

I have a misunderstanding concerning public key cryptography...would be very helpful if you answer the questions...

1. Digital signatures: You use your private key for "encryption" and they use your public for "decryption". I thought that you can only decrypt with a private key and encrypt with a public key.. and that's why it is called asymmetric cryptography and this is where all the maths comes in with trapdoor functions and so on.... That's obviously wrong so please explain what I got wrong.

2. So obviously what I thought in 1) is wrong... so I have read a bit further. Now I have the impression that private and public key are symmetric in a sense that you can choose one for encryption and then the other one is for decryption but you could also do it the other way round. Then the term "private" and "public" would only refer to which key you publish and which key you keep in secret. What I dont understand here is: Where is the math with trapdoor function used here if it is in a sense completely symmetric?

3. Is it possible to easily derive the public key from a private key? I have heard that in theory NO but in practice YES...

So I'm a bit confused at the moment, maybe you can help me out here.

Answer 1

You use your private key for "encryption".

That's a common misconception, which has roots in history. The point is that for RSA calculations the signature generation operation uses the same mathematical operation - modular exponentiation - with the private key as the encryption operation with the public key. So in older versions of PKCS#1 - itself called "RSA encryption - this is called "encryption with the private key":

The data D shall be encrypted with the signer's RSA private key as described in Section 7 to give an octet string ED, the encrypted data. The block type shall be 01. (See Section 8.1.)

This is also reflected in RSA encryption originally being used as object identifier within X509 certificates, such as those within your browser.

This over-simplification was fixed in PKCS#1 v2 and higher, where the modular exponentiation got a different name: RSASP1 (RSA signature primitive 1) instead of RSAEP (RSA encryption primitive). A primitive here is simply an underlying function within the algorithm, by the way.

Other signature standards such as the Digital Signature Algorithm (DSA) use a specific operation to perform signature generation. This specific operation cannot directly be used for encryption. So there isn't a direct encryption counterpart for DSA. The Integrated Encryption Scheme (IES) can be used but it depends on Diffie-Hellman (DH) rather than DSA. The same goes for the more modern Elliptic Curve implementations (ECDSA, ECIES and ECDH respectively).

Now I have the impression that private and public key are symmetric in a sense that you can choose one for encryption and then the other one is for decryption but you could also do it the other way round.

Yes, and that's precisely what you should not be thinking, Poncho has given a good answer here.

But note that if an implementation expects a public key that the operation with a private key may fail. Furthermore, as explained in the last part of the answer, the operation may not be secured for keeping the private key, well, private. And finally it may not use CRT speedup / security either as a public key generally doesn't contain CRT parameters - there is no need and they are not present during key pair generation for the public key.

What I dont understand here is: Where is the math with trapdoor function used here if it is in a sense completely symmetric?

This is an RSA specific question. It's during the modular exponentiation. The trick is to keep the right exponent (and possibly the parts used during key generation for calculations that use the efficient Chinese Remainder Theorem (CRT) secret.

But please remind that padding is required for a computation using RSA. Just the trapdoor isn't enough; there are certain requirements to make the trapdoor secure.

Is it possible to easily derive the public key from a private key? I have heard that in theory NO but in practice YES...

I'm not sure about the theory, but if the public key has a large public exponent (e.g. almost the same size as the modulus) then the public key may have as much security as the private key when it comes to the algorithm itself. But there are many reasons why RSA decryption with the public key would still not be secure; e.g. side channel analysis may be performed that the implementation is not protected against (no reason to secure the public key after all). Large public exponents are not common at all and many implementations would even fail if they were to be used.

So you could just test all public exponents, combine them with the modulus and test if an RSA operation is successful. However, in practice the public exponent is simply set at the value 65537 (the fourth prime of Fermat). Besides that, the public exponent is often included in the private key structure as well. So you should not expect to keep the public key secret, period.

Answer 2

I'm trying to give an answer on a very basic level.

1. Digital signatures: You use your private key for "encryption" and they use your public for "decryption". ...

This is only true for one specific digital signature (RSA signature), and simply not true in general. This is like saying "Every animal lives in the water" - also not true in general. Even for RSA, we have to take a step back:

This symmetry is only true if we consider the basic textbook-RSA. However, this is not secure for either encryption or signatures. The textbook variant is basically just the generation of the keys and to show how the trapdoor works. For actual encryption and signatures you need to use a so called "padding scheme" - and there are different padding schemes (e.g. RSA-OAEP for encryption, RSA-PSS for signatures). Exchanging those is either not possible or has no guarantee for security any more.

.2 ... Now I have the impression that private and public key are symmetric in a sense that you can choose one for encryption and then the other one is for decryption but you could also do it the other way round. ...

Again, this is just for the RSA systems, not in general. And the short answer is: Don't do it, even if you are not aware of the reason.

With a bit more detail: The algorithm for key generation is just that - it does not include the actual reasons for every decision. The algorithms are written in a way that they work - if you follow the instructions precisely. The algorithms should be usable without extensive knowledge of cryptography, but the exact reasons why something was chosen with certain properties usually does require that knowledge.

Here is an example: If you choose $d$ small, then calculate $e$ instead and publish $(N,e)$ as public key as usual, then the system is still working correctly and the steps are basically the same as the regular key generation. However, it is not secure at all, because there is an efficient attack against small values for $d$ (see Wiener's attack). This is just one example how you can screw up really badly, if you don't know exactly what you're doing.

... Where is the math with trapdoor function used here if it is in a sense completely symmetric?

The trapdoor is hidden in knowing both $e$ and $d$ at the same time. With that, you can also find the factorization of $N$, but the explanation is quite advanced. Basically it is like a two piece puzzle, and you need both pieces to make sense of it. And since one of the pieces is known to everyone, you have to keep the other hidden.

3. Is it possible to easily derive the public key from a private key? I have heard that in theory NO but in practice YES...

We have the basic assumption that public keys are public: Everyone knows them, no exceptions. But let's assume the public key isn't known. In textbook RSA, if you only know $N,d$ and know nothing about $e$ (and $e$ is as large as $N$), then you can't find $e$. In other systems, e.g. ElGamal encryption, the private key is an exponent, and if you know that and the parameters of the modular group, then calculating the public key is easy.

You referred to a difference in theory and practice here, which is easy to explain: Usually the "private key" in practical systems is not just the very minimum information required. More often it either has the public key in there as well, or you can easily derive the public key from it. For example in RSA, you would call $(N,e)$ the public key, and keep $(N,e,d,p,q)$ as private key. Sure, there is some redundant information, but even with $N,e,d$ with up to $2048$ bit and $p,q$ with $1024$ bit, we're only at $1024$ Byte in size.

Answer 3

Is it possible to easily derive the public key from a private key? I have heard that in theory NO but in practice YES...

Both in theory and in practice, it depends on the particular cryptosystem. Some systems have this property; others don't. It's neither a requirement, nor a weakness.

However, in theoretical discussions it is common to assume that the system has this property, because it often makes things easier and any cryptosystem can be trivially modified to one that does (i.e., set the private key to be the random tape of the key generation algorithm).