7
$\begingroup$

Could you help me better understand how the key-pair works in Asymmetric encryption?

I'm studying cryptography at the surface level first. While reading multiple texts and talking with colleagues I'm still not sure about two things.

  1. After generating a key-pair can we pick which key will be private or public? My first assumption was that we can, but after reading about the algorithms it looks like we can't, because of mathematical reasons how the keys are generated, therefore only one of the keys can be private.

  2. Do we encrypt or decrypt a Cipher Text with a given key? Is this technically correct to say so? Or maybe is this some kind of verification process only and the algorithm is what jumbles a message?

Is it correct to say that:

Having this key pair, I can encrypt a message with my private key and then publish it. That anyone can decrypt the message with my public key means I have encrypted it with my private key, which means it must have been me who made the message, as only I have my private key. Encrypting data with the sender's private key we call an open message format, because anyone with a copy of the corresponding public key can decrypt the message.

$\endgroup$
4
  • 1
    $\begingroup$ I've collected this question in our reading list hope you don't mind. $\endgroup$
    – DannyNiu
    Aug 20 at 12:34
  • $\begingroup$ To add, there is a question from Security Stack Exchange that has helped me get the ideas. I'm pasting the link, as someone may find it useful security.stackexchange.com/questions/81760/… $\endgroup$ Aug 20 at 13:28
  • $\begingroup$ The quote at the end of the question lacks any context. It says, "this key pair", but we have no idea what key pair it's talking about. So there's no way we could tell whether or not the statement made is correct for whatever key pair it was referring to. It might or might not be. How could we know? $\endgroup$ Aug 20 at 16:26
  • $\begingroup$ In general both keys can be of a different form (like with elliptic curves, point and number), so they acanthus be swapped. You probably refer to RSA (where they can be swapped), please add this tag to your question. $\endgroup$
    – jjj
    Aug 20 at 23:47
20
$\begingroup$

No no no! You don't get to pick which key is private and which public. That false sense of freedom is due to

  1. people not understanding that public-key cryptography is conceptually different from ciphers, and
  2. the most popular public-key algorithm RSA being a bijective permutation.

With discrete logarithm for example, your private key is always a scalar integer, and your public key is always the power. Encryption and key exchange are built out of Diffie-Hellman-like formula, and digital signature out of associative and commutative properties of scalar arithmetic.

There are other public-key cryptosystems (post-quantum prodominently) where the encryption/decryption keypair is mathematically incompatible with the signing/verification key of the cryptosystem based on the same family of maths primitives.

$\endgroup$
6
  • 13
    $\begingroup$ Addition: even in RSA as practiced, there is no liberty to pick which key is public and which is private. Customarily, one of the two has a small exponent (often 65537). It must be the public key. If it was the private key, the other would be the public key, thus public, thus known to adversaries, and all security would be lost, for it would be trivial to find both keys and factor the public modulus. $\endgroup$
    – fgrieu
    Aug 20 at 9:52
  • 7
    $\begingroup$ Further addition, regarding Q2: when there are a public and a private key, and encryption is involved, we encrypt with the public key and decrypt with the private key; there is no exception. Claims to the contrary may confuse encryption and signature: we sign with the private key, and verify with the public key; there is no exception either. $\endgroup$
    – fgrieu
    Aug 20 at 10:02
  • 7
    $\begingroup$ @fgrieu The difference is that for RSA as commonly defined, you "only" break security. For many other PKE they are completely different objects and switching them would not even make sense mathematically. $\endgroup$
    – Maeher
    Aug 20 at 10:04
  • 1
    $\begingroup$ @Maeher: indeed! I was reasserting the answer to Q1 is negative, and RSA (as practiced) is no exception. $\endgroup$
    – fgrieu
    Aug 20 at 10:07
  • 1
    $\begingroup$ @ikkachu: yes you can, and most modern programs will accept the certificate, and it will be safe. But still, swapping $e$ and $d$ will not be safe, because after that swap it will remain easy to find $d$ (the unusual value of $e$) and factor $n$ given the public key. This works with the unusual $e$ up to about $n^{0.292\ldots}$ due to an attack by Boneh and Durfee. $\endgroup$
    – fgrieu
    Aug 22 at 10:23
9
$\begingroup$

After generating a key-pair can we pick which key will be private or public?

No, in general we cannot. For most asymmetric cryptosystems the private and public keys are completely different kinds of objects (e.g. one may be a number and the other a point on an elliptic curve), and there's no way to use one in place of the other.

There is, however, one notable quasi-exception: the RSA cryptosystem has public and private keys that can be represented as the same kind of object (a modulus and an exponent) and used in the same mathematical operation (modular exponentiation) to encrypt and decrypt messages. So, in theory, one could generate a "symmetric" RSA keypair (as described in this question) and then choose which half to publish and which half to keep private.

In practice, though, even RSA key generation doesn't work that way, for a couple of reasons:

  • It's more efficient to choose the public exponent to be a fixed small number with a simple form in binary. (Common choices are 3 and 65537 = 216 + 1.) This is safe to do for the public key, but would obviously be disastrously insecure for the private key (since the exponent is the only secret part of the private key — the modulus is the same for both halves of the key pair).

  • There are ways to speed up RSA private key operations (i.e. decryption or signing) by using additional mathematical tricks such as the Chinese remainder theorem, but these require extra information about how the keys were generated (such as the secret prime factors of the modulus). Storing this extra information alongside the private key is no problem, and most commonly used RSA private key formats indeed do so. But publishing it would allow anyone to break the keypair and to decrypt and/or forge messages.

The result of all this is that, in practice, it's possible to compute an RSA public key from the private key, but not vice versa. As the linked answer (which I wrote) on security.SE says, it would theoretically be possibly to generate a secure private RSA key from which the public key cannot be computed, but this would require using both a nonstandard key generation algorithm and a nonstandard private key storage format. And even if the format issues were dealt with, not all RSA implementations would work with such private keys (due to the lack of the extra information mentioned above).


Do we encrypt or decrypt a Cipher Text with a given key? Is this technically correct to say so?

Sort of, yes. But what we usually do is generate a random key for a symmetric cipher such as AES, encrypt the plaintext with that, and then encrypt the AES key using the asymmetric encryption algorithm and the intended recipient's public key. And then we send both the AES ciphertext and the asymmetrically encrypted AES key to the recipient, who can first decrypt the AES key and then the ciphertext.

The main reason for using such hybrid encryption is that symmetric ciphers like AES are designed for encrypting lots of data fast, while asymmetric systems are not:

  • Asymmetric encryption tends to be relatively slow — often dozens or hundreds or thousands of times slower than encrypting the same amount of data with a fast symmetric cipher like AES. Asymmetric decryption is often even slower (whereas AES decryption is usually just as fast as encryption).

  • All secure asymmetric encryption schemes produce ciphertext that is longer than the plaintext, due to the need to inject some randomness into the encryption process to prevent guessing attacks. Some (such as ElGamal-like schemes) will double the length of the plaintext (after padding it up to the message block size). Others, such as RSA, require padding the plaintext up to dozens of times its original length. Obviously, this is undesirable when encrypting large mounts of data. Symmetric ciphers such as AES, meanwhile, generally only add a few dozen bytes of extra data to the ciphertext regardless of its length (depending on the mode of operation).

  • More generally, asymmetric encryption schemes are simply not designed to encrypt messages longer than a few dozen bytes or so (depending on the key size and other parameters of the scheme). An AES key will fit fine, but even a single chat message won't — and a whole web page or an image or a video stream definitely won't.

    (Technically, the same is kind of true of symmetric block ciphers like AES, too: they also encrypt data in chunks of a few dozen bytes, and to encrypt long messages, they need to be used with a suitable mode of operation that applies the cipher to the data block by block. But there are plenty of fast and provably secure block cipher modes of operation that most crypto software and hardware supports out of the box, whereas for asymmetric encryption schemes there are basically none. And if you tried to design and implement one yourself, the odds are it'd be neither efficient nor secure.)


Is it correct to say that:

Having this key pair, I can encrypt a message with my private key and then publish it. That anyone can decrypt the message with my public key means I have encrypted it with my private key, which means it must have been me who made the message, as only I have my private key. Encrypting data with the sender's private key we call an open message format, because anyone with a copy of the corresponding public key can decrypt the message.

No, not really. The private key in an asymmetric encryption scheme is for decryption, while the public key is for encryption. You generally can't encrypt anything with the private key, just as you can't decrypt with the public key.

However, there are also asymmetric digital signature schemes that allow you to sign data with a private key and to verify the signature with a public key, proving that the data has in fact been signed with the private half of the same key pair.

Some digital signature schemes are indeed based on asymmetric encryption schemes. In fact, a digital signature can, in a certain general sense, be regarded as a zero-knowledge proof of the fact that the signer could decrypt a particular ciphertext (typically derived from a hash of the message being signed) with their private key using some asymmetric encryption scheme, thus proving that they had access to both the message (or at least its hash) and the private key.

In particular, the RSA cryptosystem can also be used as part of a signature scheme (such as RSA-PSS), using the same kind of public and private keys and the same mathematical operations (modular exponentiation) as for RSA encryption. This (and early popular explanations of public-key cryptography) is where the common but misleading description of (RSA) signing as "encryption with the private key" comes from. Technically it's not entirely wrong, at least if you ignore all the other parts of the scheme (hashing, padding, etc.) except for the modular exponentiation at the core of the RSA algorithm.

But if you're willing to simplify things that far, you might as well note that both RSA encryption and decryption (and signing and signature verification) are fundamentally just modular exponentiations, so you might just as well say that they're all the same thing, and that RSA signing is really just RSA decryption applied to a special ciphertext. Which would also be technically true, in a way, and probably no more (or less) misleading than describing it as "encryption with the private key".

$\endgroup$
8
$\begingroup$

In RSA encryption and decryption are similar. If you chose e randomly and calculate matching d you could then chose to swap their roles and pick either as the public key.

Usually we don't do this, we pick a small public exponent with few set bits. This makes public key operations much faster. We can not swap the roles and make the private key operations faster in this scenario because there are few options for such small exponents. So the small one must be the public key not the private.

$\endgroup$
6
$\begingroup$

The existing answers from DannyNiu and Meir Maor answer well the confusion about whether private and public keys are interchangeable. But it is also worthwhile, I think, to address this snippet from the question:

Having this key pair, I can encrypt a message with my private key and then publish it. That anyone can decrypt the message with my public key means I have encrypted it with my private key, which means it must have been me who made the message, as only I have my private key. Encrypting data with the sender's private key we call an open message format, because anyone with a copy of the corresponding public key can decrypt the message.

No, this is very wrong! The normal way that encryption is used goes like this:

  1. I publish my public key, and keep my private key secret.
  2. You decide to send me a message. You use my public key to encrypt your message; you send the encrypted message to me.
  3. I use my private key to decrypt the message, so that I can read it.

The promise that encryption makes is that after step 2, you can give the encrypted message to anybody you want. Anybody who isn't me (and therefore doesn't have my private key) will only receive apparently-random garbage; there is no way for them to learn any nontrivial property of the original, unencrypted message.

Critically, the most basic encryption promises do not provide any guarantees about provenance. If Joe hands me an encrypted message and says it's from Bob, I have no way to check whether it is actually from Bob, and even if it's from Bob, I have no way to check that the message hasn't been modified. (For example, if Joe knew that the message read "Bob would like to transfer \$XXXXX from Bob's account to Joe's account", in some encryption schemes it is possible for Joe to change the message to "Bob would like to transfer \$99999 from Bob's account to Joe's account", even though Joe can't learn what the original XXXXX was.)

There are separate algorithms which can provide guarantees of provenance, called digital signatures. In digital signatures, the normal usage goes like this:

  1. I publish my public key, and keep my private key secret.
  2. I decide I'd like to prove to you that I endorse a message. I use my private key to sign the message, and send the signature (and message) to you.
  3. You use my public key to verify that I created the signature and that the signature is about the given message.

The promise that signatures make is that after step 2, I can give my signature to anybody I want. Anybody who isn't me (and therefore doesn't have my private key) won't be able to use that to create signatures of any other messages on my behalf just from the information they learn in this signature.

Dual to the discussion above about things not promised by encryption, there are things not promised by signatures. For example, a signature might reveal nontrivial information about the message it applies to, so it doesn't promise secrecy like encryption does. So encryption and signing are complementary techniques.

...and of course, there are more complicated algorithms that make more complicated promises, including promising a mix of the secrecy you get from encryption and the integrity/provenance you get from signatures.

$\endgroup$
5
  • $\begingroup$ I don't completely understand the point you're making. The snippet you quoted from OP seems to correctly state the signature aspect of public key cryptography (maybe with the tiny optimization that one would regularly decide to only sign a hash of the message instead of the message itself; but technically/cryptologically the end result would be the same). Can you maybe specify a bit more which part of the quoted block is the incorrect one? $\endgroup$
    – AnoE
    Aug 23 at 7:41
  • $\begingroup$ @AnoE The quoted block talks about encrypting and decrypting a message, not signing and verifying a signature; this is the primary mistake. It is not just a terminology difference, either, as discussed in my answer: signatures don't promise either direction about the information they're signing, neither that the information can be recovered nor that it can't, so talking about recovering the message from the signature using the public key doesn't make sense. $\endgroup$ Aug 23 at 14:09
  • $\begingroup$ Every sentence of the quoted block makes sense in itself, and none of them are in contradiction to each other. He loses me a bit at the "open message format" (though that may be a language issue - I guess he just wants to say the ciphertext is sent in public, which is kind of obvious). And obviously none of it has any practical applicability, but as he said he's looking at the first theoretical basics. But conceptionally it seems just fine to me. Answering "No, this is very wrong!" seems a bit far-fetched... $\endgroup$
    – AnoE
    Aug 23 at 14:27
  • $\begingroup$ @AnoE "I can encrypt a message with my private key and then publish it" is incorrect in general: in many (most) encryption schemes, the private key does not have the right data inside for encryption. "anyone can decrypt the message with my public key" is incorrect for an analogous reason. "it must have been me who made the message, as only I have my private key" is incorrect because encryption does not make provenance promises. "anyone with a copy of the corresponding public key can decrypt the message" is incorrect for the same reason "anyone can decrypt the message with my public key" is. $\endgroup$ Aug 23 at 14:50
  • $\begingroup$ @AnoE In other words, contrary to your "every sentence makes sense in itself", every sentence contains an error, and some contain more. $\endgroup$ Aug 23 at 14:50

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.