Talk:Public-key cryptography

External links modified (January 2018)

Hello fellow Wikipedians,

I have just modified one external link on Public-key cryptography. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

• Added archive https://archive.is/20121208212741/http://wiki.crypto.rub.de/Buch/movies.php to http://wiki.crypto.rub.de/Buch/movies.php

When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.

This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 5 June 2024).

• If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
• If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—InternetArchiveBot (Report bug) 11:15, 20 January 2018 (UTC)

Trim and tidy

Have just done a tidy-up of the intro. The rest of the article is in dire need of the same. - Snori (talk) 19:14, 26 December 2018 (UTC)

Have now done a fairly brutal edit of the body. I would suggest that the most important element to any further changes are: Keeping/building a good structure of sections; Tight wording; Good citations to back the text. - Snori (talk) 20:35, 26 December 2018 (UTC)

I believe the introduction needs another clarification. imo it confuses the objective (mathematical) fact that asymmetric cryptography allows for two unrelated keys to encrypt and decrypt any string / message with the convention that one of those keys is considered public and the other private for most uses. Your comments welcome.--BBird (talk) 13:47, 7 August 2019 (UTC)

You’re absolutely right about the confusion of the two objective facts in the lead, but the problems with this article go further than that. I came to it hoping to find an explanation about how it is that one key (namely, the private key) can decrypt something that was encrypted using another key (namely, the public one), but there is nothing in the entire article that explains this.

The principle seems to imply that the two keys are related, but... how, exactly? In fact, the first bullet of the Description section does (somewhat) confirm a relation by stating that the private key must “match” the public one that was used for the encryption. Again: how exactly do they match? 74.58.147.69 (talk) 20:17, 27 August 2019 (UTC)

Reverted vandalism

I have just reverted a spate of changes by @2402:3a80:19f8:c3dc::2 which had seemingly randomly copy-pasted chunks of text of the article into different sections. As far as I can tell there were no meaningful contributions made with any of these edits – just nuisance text. I think I got them all. Phidica (talk) 02:17, 9 December 2022 (UTC)

@Phidica It looks like you got it all. I wasn't sure what was going on with this contribution. Thanks for evaluating it. ~Kvng (talk) 15:24, 12 December 2022 (UTC)

Diffie Hellman Diagram

Is the Diffie Hellman Diagram accurate? Im under the impression that the shared secret is obtained by a shared public secret combined with the two private keys. The diagram seems to indicate that the private key of Alice with the public key of Bob is equal to the private key of Bob mixed with the public key of Alice. Epachamo (talk) 23:48, 9 February 2024 (UTC)

Yes, it is accurate. Alice and Bob's private keys are $a$ and $b$, and their public keys are $g^{a}$ and $g^{b}$. Alice computes the shared secret by combining her private key $a$ with Bob's public key $g^{b}$ via $(g^{b})^{a}=g^{ba}=g^{ab}$; Bob computes the shared secret by combining his private key $b$ with Alice's public key $g^{a}$ via $(g^{a})^{b}=g^{ab}$.

The whole point is that Alice and Bob need only exchange public information over a channel that an adversary may be eavesdropping on, and can still establish a shared secret. If each party had to also learn the other party's private key in advance over some secret channel they'd previously established, it wouldn't have been a revolutionary idea in 1976. Taylor Riastradh Campbell (talk) 11:47, 10 February 2024 (UTC)

Can a pair of keys do anything other than encryption?

I would be grateful if someone explained to me the complete purpose of public and private keys if there is any type of public-private cryptosystem that does not serve, in its core, for encryption.

From my understanding, this is a simple matter: public keys serve to encrypt data and private keys serve to decrypt data. Thus, the only thing public-private cryptosystems can do is encrypt and decrypt data.

If I understood these systems correctly, the purpose of public-private cryptosystems is in fact not limited to data confidentiality, but any other application (digital cash, password-authenticated key agreement, time-stamping services, etc.) uses encryption because that is the base of pubic-private cryptosystems.

The state of the article at my last edit was quite easier for non-experts, it would be good to have a similar first paragraph in the lead. Have I misunderstand something?

PS: after the first @Taylor Riastradh Campbell's revert of my edit, I investigated the topic before ediiting the lead; after that, I was sure that public-private cryptosystems were limited to encryption, so I was bold to get a faster feedback, I see nothing wrong on doing this.

Emunah00 (talk) 01:41, 18 June 2024 (UTC)

An encryption scheme is loosely a system to turn plaintext messages into ciphertexts in a way that can be reversed, with a security goal to conceal any patterns in the plaintext from an adversary. (The formalization is ciphertext indistinguishability.) In the public-key setting, anyone with a public key can turn plaintexts into ciphertexts, but only those who know the related private key can decrypt the ciphertexts to recover the plaintexts. Reversibility, and the security goal of concealing patterns in messages, are defining characteristics of encryption.

The first public-key cryptosystem ever published, Diffie-Hellman key exchange, is a way for Alice and Bob to agree on a secret key by exchanging only public information that can be eavesdropped. This is public-key key agreement. Neither one can pick the secret key in advance—they just get a random key out of the procedure, which nobody else knows. So on its own this is not encryption. You can build a public-key encryption scheme on top of public-key key agreement, by combining it with a secret-key (authenticated) cipher (e.g., IES), but that is extra structure which is not itself part of public-key key agreement.

Public-key signature doesn't involve concealing patterns in messages at all. It is loosely a system where anyone with a public key can use it to verify signed messages, but only those who know the related private key can make signatures that will pass verification. (The formalization is unforgeability.) Although there are some signature schemes that encode part of the message in the signature, you can't in general recover a message from a signature—there's no reversibility.

Some signature schemes have a subroutine that resembles a very limited form of encryption, mainly those based on the RSA trapdoor function. But you can't simply take a secure RSA-based encryption scheme like RSAES-OAEP or RSA-KEM-with-a-DEM as a subroutine and make a secure signature scheme out of that, or vice versa. And there's no generic way to turn a public-key encryption scheme into a public-key signature scheme, or vice versa. There are many public-key signature schemes—most of them, really!—that don't involve the RSA trapdoor function, or any structure that really resembles a public-key encryption scheme as a subroutine. Examples:

• Schnorr signature
• Lamport signature and Merkle signature (based on one-way hash functions only)
• Rabin signature (loosely related to RSA, sometimes misrepresented in textbooks as a completely broken public-key encryption scheme)
• BLS digital signature
• Falcon (signature scheme)

Other examples of public-key cryptosystems that don't involve encryption:

• Public-key key encapsulation provides a way for someone to simultaneously create and send a random secret key to a recipient using the recipient's public key, but like in public-key key agreement, the sender can't choose what the random secret key will be. Modern public-key encryption schemes are built out of public-key key encapsulation, not the other way around.
• Dual_EC_DRBG is a public-key pseudorandom number generator: anyone can use the public key to expand a secret seed into an arbitrarily long roughly-uniform string of bits (like a normal pseudorandom number generator), but only those who know the private key (like the NSA) can use one output to guess the next output without knowing the seed. (The NSA doesn't get to learn the seed, though, only the next output—it's still not encryption!)
• A verifiable random function is a system where only those who know a private key can compute a pseudorandom function of given inputs, but anyone who knows the related public key can verify that the outputs are correct. This is more related to signature than to encryption.

None of the examples you gave necessarily involve encryption:

• Digital cash is almost always based on signature, sometimes blind signature as in Ecash, sometimes ordinary signature as in Bitcoin.
• Password-authenticated key exchange takes passwords as inputs, and returns a random shared key (sometimes together with an indication that the passwords matched), but the parties generally can't choose what the random shared key will be—otherwise, if they chose it in advance, why would they bother with the human-memorable password?
• Trusted timestamping services are all about signatures, not encryption. One party is trusted to operate a clock and keep a private signing key secret; anyone can submit a message and get a signed timestamped version of it that everyone else, having the public key of the timestamping service distributed, can verify.

Taylor Riastradh Campbell (talk) 02:43, 18 June 2024 (UTC)

Thank you for your detailed response, I'm sorry for introducing those errors in the lead (if you provided just one very clear example like Diffie-Hellman key exchange in your first or second revert I would have understood).

I have a minor question: according to its article, public-key key encapsulation does involve encryption, if I understood it correctly, doesn't it?

Do you think it's possible to summarize both public-key cryptosystems that don't envolve encryption taking a common property of all of them, yet keeping it understandable by non-expert readers?

Emunah00 (talk) 03:39, 18 June 2024 (UTC)

[A]ccording to its article, public-key key encapsulation does involve encryption, if I understood it correctly, doesn't it?

Public-key key encapsulation takes a public key and produces two outputs at once:

• a random secret key
• an encapsulation of that secret key, from which the secret key can be recovered only with knowledge of the private key corresponding to the public key

But you have no control over what the random secret key will be, other than by running it repeatedly and filtering for ones you like—you can't pick the secret key in advance and find a working encapsulation for it.

This can be used as a subroutine in a public-key encryption scheme to send a message, by using the random secret key with an authenticated cipher on the message and transmitting the message's ciphertext alongside the encapsulated secret key:

To Encrypt(pubkey, message):

1. (secretkey, encapsulation) := Encapsulate(pubkey)
2. ciphertext := AuthenticatedEncrypt(secretkey, message)
3. return (ciphertext, encapsulation)

To Decrypt(privkey, (ciphertext, encapsulation)):

1. secretkey := Decapsulate(privkey, encapsulation)
2. message := AuthenticatedDecrypt(secretkey, ciphertext)
3. return message, or fail if authentication failed

Given a public-key encryption scheme, you can also build a public-key key encapsulation scheme. But it is practically always easier to design a secure public-key key encapsulation scheme than it is to design a secure public-key encryption scheme, so essentially all new designs—e.g., the NIST PQCRYPTO submissions—start with key encapsulation and derive encryption from that.

Only archaic legacy designs like RSAES-PKCS1-v1_5 and RSAES-OAEP do it the other way around—and even then, they build a very limited public-key encryption scheme out of the RSA trapdoor function that only handles short messages, and then use the limited encryption scheme to transmit a short random secret key, and then use that in a public-key key encapsulation mechanism like I sketched above to encrypt arbitrary-length messages. Taylor Riastradh Campbell (talk) 11:35, 19 June 2024 (UTC)

Do you think it's possible to summarize both public-key cryptosystems that don't envolve encryption taking a common property of all of them, yet keeping it understandable by non-expert readers?

Well, I tried that for the lead, but rather than expound on it in paragraphs of abstract prose defining a property, I tried to illustrate it with two practical examples.

The common property is that the cryptosystem involves pairs of keys that are mathematically related, so the public key has one power and the private key has a related power which—as a security goal—can't be derived from the public key or from any use of the cryptosystem interacting with whoever has the private key.

The most prominent examples are probably encryption (public key: power to send secret messages; private key: power to receive secret messages that were sent using the public key) and signature (public key: power to verify messages; private key: power to sign messages that will pass verification by the public key), with some other less-common examples like VRFs (public key: power to verify a random function was evaluated; private key: power to evaluate the random function that is verified by the public key).

In practice, signature and key agreement are probably the most widely used—just about every web page you load leads to signature and key agreement behind the scenes; public-key encryption, VRFs, PAKEs, and others see much less use in the real world. But public-key key agreement is a little more abstract than public-key encryption, so it's harder to illustrate with an example. Taylor Riastradh Campbell (talk) 13:21, 19 June 2024 (UTC)

WP:TLDR If I understand your question correctly, I think a simpler view of the system would answer it.

Firstly, the system operates on the creation of a related pair of keys. Which one is the public key and which is the private is purely a matter of choice (often enforced by cryptographic systems but it doesn't have to be).

Secondly, although one would normally encrypt a message with one key and decrypt it with other, this is also purely a matter of convention. There is nothing preventing the originator of the message decrypting the plain text message with either key and the recipient encrypting it with the partner key to recover the plain text. The intermediate encrypted message is just as encrypted as doing it the other way around. It is only necessary to know in which direction the encrypter processed the message.

As you noted: anything can be encrypted as long as it is represented as a stream of binary numbers. A well know public key encryption system, in reality isn't quite. PGP is in fact a symmetric cypher system (in that the same key is used to encrypt and decrypt the actual message). What makes it appear to be a public key system is the public key part of the system is only used to encrypt the symmetric key (individually generated for each message). This makes it substantially more efficient than a naked public key system because public key systems with keys that are large enough to be considered secure are much more computationally expensive than symmetric systems. PGP thus only has to public key encrypt a symmetric key which can be much smaller for the same security and thus the computation is kept to a minimum. 2A00:23C8:9883:A001:6012:33CA:E0B6:6163 (talk) 14:59, 18 June 2024 (UTC)

Which one is the public key and which is the private is purely a matter of choice (often enforced by cryptographic systems but it doesn't have to be).

This is a misconception that makes no sense in most cases, and leads to security-destroying blunders in cases where it looks like it might make sense.

• This misconception makes no sense in most cryptosystems, because public keys and private keys are different kinds of things.

  For example, in the public-key signature scheme Ed25519, the public key is the encoding of a point $(x,y)$ on an elliptic curve, satisfying $$-x^{2}+y^{2}\equiv 1-(121665/121666)x^{2}y^{2}{\pmod {2^{255}-19}},$$ and the private key is (or can be hashed to derive) an integer $$s\in [0,2^{252}+27742317777372353535851937790883648493)$$ together with a 256-bit string. Even if you were to misinterpret the private scalar $s$ as the $y$-coordinate of a public point (and ignore the extra 256-bit string in the private key), only about half of the possibilities satisfy the equation; the rest can't be valid public keys.

• In the cryptosystems where it kinda sorta looks plausible if you squint, which is really limited to RSA-based cryptosystems, this misconception leads to security-destroying blunders.

  If you look at an RSA public key as Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/en.wikipedia.org/v1/":): {\displaystyle (n, e)} and an RSA private key as $(n,d)$ with $$ed\equiv 1{\pmod {\lambda (n)}},$$ and if you look only at the pure RSA trapdoor function $x\mapsto x^{e}{\bmod {n}}$ itself (which is not a public-key encryption scheme or a public-key signature scheme), the inverse $y\mapsto y^{d}{\bmod {n}}$ is the same function so the roles of $e$ and $d$ look similar.

  But the similarity ends there. Almost all encryption and signature schemes based on RSA in the real world use $e=65537$ for efficiency (RSA supports some of the cheapest public-key operations, second only to Rabin signature), and derive $d:=e^{-1}{\bmod {\lambda }}(n)$, and have a host of other details on top of the trapdoor function—sometimes called padding schemes—to make a secure encryption scheme, or a host of different details to make a secure signature scheme. If you try to interchange the public key and the private key in these cases, security is immediately lost because there's no more secrets in the private key—everyone knows it's $(n,65537)$!

  More generally, in secure RSA-based cryptosystems like RSA-FDH signature or RSA-KEM key encapsulation or RSAES-OAEP encryption, it is safe to use public exponent $e$ as low as 3. But to resist Wiener's attack and variants like Boneh–Durfee, one must use private exponent $d\gg n^{0.292}$ (and it is conjectured that $d\gg n^{0.5}$ may be needed). That is, although the public exponent $e$ and the private exponent $d$ are syntactically the same kind of thing (exponents in $\mathbb {Z} /\lambda (n)\mathbb {Z}$), they have completely different security requirements. So it is not ‘purely a matter of choice’ which one is the public key and which one is the private key.

Taylor Riastradh Campbell (talk) 13:02, 19 June 2024 (UTC)

WP:TLDR. You are making this more complicated than this needs to be. You can generate the pair of keys how you like. But there is no requirement that one is specifically the public key and other is the private. Though, obviously in any cryptographic system, you have to settle on one or the other. Whichever key that you use to encrypt (and you can use either), you have to use the other to decrypt (and vice versa). 2A00:23C8:9883:A001:783C:2503:45B1:2CB0 (talk) 13:26, 19 June 2024 (UTC)

You can generate the pair of keys how you like. But there is no requirement that one is specifically the public key and other is the private.

This is not true, and it suggests that you're only familiar with the idealized textbook treatment of a single family of cryptosystems, that is, those based on the RSA trapdoor function. While this pop-science oversimplification of cryptography is common in classroom settings, it's wrong and, if applied in practice, can destroy security of what might have otherwise been a secure cryptosystem.

Would you like to explain how to use an Ed25519 public key to create a signature, or cite the literature that explains how to do this? Taylor Riastradh Campbell (talk) 14:11, 19 June 2024 (UTC)

References