Talk:Public-key cryptography/Archive 1

Archive 1

Archive 2

Combine with Asymmeteric Key Article?

This should probably be combined with Asymmetric key algorithm or vice-versa. Rasmus Faber 15:39, 8 Dec 2003 (UTC)

---

Rasmus, I think I disagree. Not because there is any content issue here, but because public discussion of the subject has become perverted by -- well, let's blame them, it's probably their fault anyway -- the journalists. As with the hijacking of the word hacker, public key has come to mean asymmetric key. In fact, some asymmetric key algorithms are not public key, and vice versa.

Perhaps the best option is to have an entry 'public key' pointing to the 'asymmetric key' article. At least then the Wikipedia would not be contributing to the distortion of content in this area.

ww

Hmm. I think, I can see how an asymmetric key algorithm might not be a public key system, though I cannot think of any examples -- but how can a public key algorithm not be an asymmetric algorithm? Rasmus Faber 19:19, 21 Jan 2004 (UTC)

In prowling around, I've just noticed that I didn't reply. Sorry about that. There are several examples of non public key asymmetric algorithms. Since they're not all that useful, they've fallen out of my head. Rabin may have developed one, or I may just be slandering that estimable man, due to my deteriorating gray matter. See Applied Crypto by Schneier. If memory serves, he notes a few. The problem is being able to derive the other key from the public key. Ought not to be able to do that in an actual public key system.

As for your other thought, well if we are not to allow that the versa got me, I would have to suggest that a non-asymmetric key public key system would be an insecure one in which a symmetric key gets published.

And with that I guess I'd better duck. Quack, quack, quack....

ww

The actual situation, if you'll permit me to be a little pedantic, is that asymmetric key algorithms are tools used in public key cryptography. Merging these two articles would be like merging block cipher and symmetric key cryptography. Public key cryptography includes more than just asymmetric key algorithms - it includes key agreement algorithms and digital signature algorithms, not to mention the actual protocols in which these algorithms are used. I disagree with the merge -- leave them separate. Decrypt3 21:27, Jul 10, 2004 (UTC)

De3, There is a comment to this effect at Talk:WikiProject Cryptography. ww 14:42, 13 Jul 2004 (UTC)

Felten's comments

Ed Felten conducted a "Wikipedia quality check", examining a handful of articles; he said

The technical entries, on virtual memory and public-key cryptography, were certainly accurate, which is a real achievement. Both are backed by detailed technical information that probably would not be available at all in a conventional encyclopedia. My only criticism of these entries is that they could do more to make the concepts accessible to non-experts. But that's a quibble; these entries are certainly up to the standard of typical encyclopedia writing about technical topics. [1] (emph mine)

— Matt 01:38, 6 Sep 2004 (UTC)

Matt, Do we consult the physician's lounge folk about the dislocated shoulders occasioned by patting ourselves on the back? On the whole, I agree with Prof F's comments. We are serving the Average Reader a bit less well than we might. But we're doing good work, nonetheless. I'm glad to hear someone of prominence agrees. ww 20:35, 8 Sep 2004 (UTC)

Errors

Should RSA be in the highly regarded section? I thought that significant flaws existed compared to ElGammal User:Watsonladd

I believe there are weaknesses if you directly apply RSA, but apparently (under certain assumptions) RSA with a certain type of padding (OAEP) has been proved secure. — Matt 13:31, 26 Nov 2004 (UTC)

I'm not an RSA type of guy, but I just went to a talk by Neal Koblitz (with Menezes in attendance) based on this paper where they were mentioning OAEP and how it was "proven secure" and then later was discovered to have problems. Anyway, the talk was interesting. I haven't read the paper. CryptoDerk 23:49, Nov 26, 2004 (UTC)

[offtopic, sorry] I came across the paper last week, and it was definitely one of the best crypto papers I ever read. Where was the talk, btw? Arvindn 04:27, 27 Nov 2004 (UTC)

At the University of Waterloo. The talk was fairly interesting, although Koblitz mostly read directly from his slides. Koblitz is adjunct faculty and Menezes is faculty at UW. Miller and Merkle also gave talks, but that was on the next day, and Merkle wasn't even talking about crypto :(. CryptoDerk 06:06, Nov 27, 2004 (UTC)

Diffie-Hellman key exchange

There isn't any word about Diffie-Hellman key exchange algorithm in the history section, I think it is the first public asymmetric-key cryptography algorithm. Gbiten 02:55, 24 Dec 2004 (UTC)

I guess I'm inclined to agree on this. Perhaps a pointer to a D-H article would be appropriate? ww 19:27, 19 Jan 2005 (UTC)

Why is DH cited as an example of public key? Isn't it a symmetrical key algorithm?

Based on the article I agree that DH is in the end symmetrical, but it does have asymetrical parts also.

Diffie-Hellman key exchange is exactly that, a key exchange protocol - there are no public or private keys used in the protocol, it is used to generate a new symmetric key. Broadly speaking, key exchange protocols are public key cryptography, since many key exchange protocols use public keys to protect against man-in-the middle attacks, but the diffie-hellman protocol itself does not do this, in fact it has no authentication mechanism whatsoever. Birkett 15:23, 21 November 2006 (UTC)

on separate article for hybrid cryptosystems

Parakan, in a recent edit summary suggested such an article may be needed. Given the way things have developed regarding cryptography topics here, he's probably right. I think we need one, and pointers to it from, eg, cryptosystem and perhaps cryptographic engineering. ww 19:27, 19 Jan 2005 (UTC)

Suggestion regarding vulnerability

I am very much outside my area of expertise here, but is it not true that public key cryptography (in general) would be in serious trouble if an efficient algorithm were found to solve the Diffie-Hellman problem? The article on this (as yet unsolved) problem is new and, I think, very good; perhaps someone with more knowledge of the subject could briefly discuss this vulnerability here and link to Diffie-Hellman problem. Regards Bryan 14:42, 29 November 2005 (UTC)

I don't think the Diffie-Hellman problem has any general implications for public key cryptography. If DH were solved, other algorithms could be used in its place. The article already states that there are no algorithms that have been proven to be secure. Ray Spalding 21:21, 29 November 2005 (UTC)

PGP Question

I am writing my Security+ test tomorrow and need a clarification about one issue in regards to PGP. My question is "What does PGP uses to encrypt data....Asymetric or Symetric algorithms? —Preceding unsigned comment added by 24.83.1.79 (talk • contribs) 07:17, 30 November 2005.

Both, also known as "hybrid encryption". See PGP#How_PGP_works. Best of luck with the test. — Matt Crypto 08:48, 30 November 2005 (UTC)

Article Tone / Grammar

The tone of this section seems a bit paranoid:

(from Practical considerations → Weaknesses)

The function of this server is to present itself as Alice (validated by the certificate obtained by coercion), log all messages and forward them to the "real" Alice web server. Practical Secure Sockets Layer/TLS man-in-the-middle attack at least for a mighty government! Very few people seem to take coercion of Certificate Authorities/Issuers into account. Note that a government might also have the power to coerce PGP key holders to do something equivalent as described with SSL/TLS.

I can see that this could be a practical concern to have, but I can't remember the last time I saw an exclamation mark in an encyclopedia...

Yuck. Please feel free to dive in and fix it! — Matt Crypto 08:41, 27 January 2006 (UTC)

I removed it. I didn't see a way to make is pretty and still get the point across. I'm not sure the point actually needs to be made. I might clean it up a little more later, but for right now, it just didn't seem right in there.--Mdwyer 18:52, 24 March 2006 (UTC)

Have just noticed this exchange. I agree with Matt (unfortunate phrasing) and disagree with Mdwyer (point may not need to be made).

All responsible crypto is driven by paranoia, and designers who are insufficiently paranoid will find their systems' errors and vulnerabilties being passed around by the l33t amongat us (first the competent and then the script kiddies). Irresponsible crypto, by Bozo Crypto Inc perhaps, just gets there more quickly (see snake oil. The point does need to be made, but it really should be written well, lest readers be left confused or worse take from one of our articles that there are solutions which just work and that the problem is merely to choose one.

Schneier is famous for having given up on his prior work and come down hard on the 'security is a process not an end point' side of things. He's right in that, especially in commercial contexts (rpoducts and practical problems), but the technical side of algorithms and protocols and such is still fascinating to many and necessary for crypto system designers in an ever-changing threat environment from the Opposition. When combined with a generous portion of paranoia, designers can sometimes come up with reasonable security (ie, crypto) systems using this research. Most of it is not very accessible to the Average Reader, but our accounts should not mislead as to the underlying context, by concentrating on the merely technical. ww 15:22, 14 May 2006 (UTC)

Use of Private Key to Encrypt Messages

There is something that has been bothering me in many descriptions of public key encryption. I see that it is possible to use a private key to encrypt a message and the public key to decrypt same. This seems very insecure since anyone intercepting the message can then use a person's public key to decrypt it? What am I missing?

Thanks Simon PS. As you can tell I am a cryptosystems newbie :-(

As you correctly perceive, one does not use this technique to insure secrecy. The point is that only the person with the private key can create a message that will decrypt properly. So this technique is used to create digital signatures. One creates a cryptographic hash of the message and encrypts it with ones private key. The encrypted data is sent with the message as a signature. Anyone can use the public key to decrypt the sig and get the hash which they can then check for themselves against the message.--agr 15:33, 7 May 2006 (UTC)

It should be noted that not all schemes can be used in this way. In the case of RSA, decrypting is basically the same as encrypting with the private key, and this technique works. In most other schemes, such as ElGamal, it is not possible to encrypt with a private key, because the encryption and decryption operations are very different. Birkett 14:18, 16 December 2006 (UTC)

Signing has in common with decryption the fact that a private key is used; signature verification has in common with encryption the fact that a public key is used. Therefore, mentioning encryption, not decryption, when describing signing is prone to confusion. I have encountered someone trying to explain public-key encryption based on the Wikipedia diagram for digital signing because it contained the words "encryption" and "decryption". Thomas 11:25, 31 January 2007 (UTC)

I agree with Birkett that It is a particularity of RSA that the same algorithm can be used for encryption, decryption, creating digital signatures and verifying them. In general a digital signature algorithm is not automatically of any use for encryption. Anecdotal evidence: due to import/export control restrictions, Sun did not use to provide the RSA algorithm with the SunJCE crypto provider that could be used from Java programs. Because RSA can be used for encryption, digital signing with RSA was not available, either. On the contrary, at the same time DSA was available, which is consistent with the idea that DSA can be used for signatures, but not for encryption. In conclusion, it's best not to mention encryption/decryption in the context of digital signature creation/verification, but keep each pair of terms within their proper contexts. Thomas 11:25, 31 January 2007 (UTC)

In reference to using private key encryption for authentication and non-repudiation in the Application section, is there a difference between authentication and non-repudiation in this case or not? --Etienne 03:56, 30 July 2006 (UTC)

I'd say they're different. For example, Bernstein's notion of "public-key authenticators" provide authentication but explicitly don't provide non-repudiation [2]. Phr (talk) 04:36, 30 July 2006 (UTC)

Non-repudiation is rather different than authentication, though often confused. The language is not as precise as the theroy and engineering is. Authentication is not a 'state of being'. It's an attitude, or a reason for an attitude, on the part of some observer, who could (wearing another hat) be the recipient. So, if I get a message which the asymmetric key crypto says could only have been produced with a private key matching some public key I have, I've got no authentication of the message at all. Is the public key I have actually yours? Unless I got it directly from your hand (and knew you personally besides) I've no idea. Only some kind of secondary authentication of that key in its belonging to you aspect, can help. PKIs try to do this, with more or less seccess, as do other key distribution schemes. The Web of Trust used by PGP in its original release is a very differetn approach.

But even if the public key I have has been fully authenticated (lots of slips twixt cup and lip there), how can I tell if you haven't lost a copy of your key. Or been mugged and had it stolen. Or whatever. I don't have any such recourse. I must rely on faith, in some sense, that you haven't been careless or taken by some underhanded scheme.

Non-repudiation has to do with your ability to claim something like this (stolen key, copied key, etc) sometime later on. So, if you sign a contract with me (proper authentication that I, and the court if it comes to that) believe, and later find out you can make a better deal with someone else, you might claim that your signature was faked and repudiate it. If you waited a while, a court might not let you do it, being a kind of prima facie fraud. But less obviously, crypto non-repudiation involves some kind of protocol, carried out usually with a trusted third party, which will preclude such a later claim of the dog ate my signature.

Two quite different issues, and addressable cryptographically in very different ways.

Hope this helps, sketchy as it is. ww 20:52, 30 July 2006 (UTC)

Rounding out Weaknesses Section

The discussion of interception/falsification weaknesses for public key approaches (the last paragraph in the weakness section) would be greatly helped by mentioning that these vulnerabilities can be avoided by using a secure connection such as SSL.

By grouping interception/falsification vulnerabilities together with weaknesses that are truly unknown and not preventable (due to the nature of algorithms) it makes these problems sound equally unavoidable when in fact modern implementations of public key cryptography require approaches that prevent most forms of interception and falsification (for example SSL makes man-in-the-middle attacks impossible based on what I know about it).

Also, mentioning that gaining control of the users system and by extension their private key is another potential security risk which, while obvious, rounds out the list of weaknesses. Since currently I'm learning about cryptography I'd rather leave this to more qualified editiors to consider and potentially implement. Antonrojo 14:52, 14 May 2006 (UTC)

Antonrojo, It is certainly true that protocols such as SSL (or in the standardized form, TLS) make elementary attacks against underlying algorithms more difficult, but it cannot be said with accuracy that they eliminate such vulnerabilities. The Opposition must merely be more cunning in many cases. To take a trivial example, the MD3 message digest algorithm was discovered to be insecure during testing and was never released for public use, unlike MD4 (also found to be insecure, but after release (similarly the original version of SHA), and MD5, which has no been shown to be vulnerable to a not very effective attack in some very recent Chinese research). However, had MD3 been used in the SSL protocol, it's insecurity may have provided an entry point for an attacker.

And, note carefully, that there have been three versions of the SSL protocol. Only the latest, v 3, includes exchange of cryptographic identity certificates from _both_ parties. Until then, there had been more or less trusting assumptions as to the identity of the other party, in one or the other direction. This alone makes claims made by assorted entities (from your bank to some e-tailer to ...) that their site is "secure and can be trusted" more than somewhat dubious, and, fundamentally, an exercise in PR as security. There is little evidence of someone actually knowing much about cryptography in the real world here, and much hint of someone who has read an introductory book or article and made too many assumptions about the completeness of their knowledge in approving such claims. As they will have legal effect in some jurisdictions, some of this over assumption may be laid to the legal counsel involved. Cleverness of scheme, and apparent solidity of security, is insufficient for security, though impressive to the less than fully cynical inexperienced. Experience tends to recommend cynicism and suspicion of security or quality claims, explicit or implicit.

Actual cryptographic security is hard to manage, and theoretically provable security is harder than that. Crypto systems are composed of algorithms (which can have deficient implmentations, sometimes most subtly so), protocols (the same), and user procedures (humans being involved, almost anything is possible). Whatever the security of an individual system element (and implementation), its use incombination with other elements may result in what's often called a 'compositional weakness'. An example is the one-time pad, which has a proof of security from no less than Claude Shannon himself. It's almost never used in practice (snake oil crypto purveyors' claims notwithstanding) since ensuring that the ancillary requirements are actually met is so very hard in the real world. The WP article discussed this, the last time I looked.

WP articles in the crypto corner are repeatedly adjusted, and 'improved', by editors wishing to remove from them traces of this real world caution and cynicism. Doesn't read as clean and clear as accounts of such a crisp mathematical subject ought to read, perhaps. Or by those editors who object to the NPOV of such cynicism. The difficulty is that the mathematical quality of the subject, attractive to a sort of Platonic cast of mind I suppose, does not always control in the real world of actual work, and an actual Opposition. And in the case of alleged NPOV cynicism, htere seems to be having a sort of political correctness on behalf of algorithm classes' reputations or something indistinctly similar. An inappropritate concern, and not a violation of WP's NPOV rule, despite some strongly held views. The result in either case is an article which disserves our Gentle (and not crypto sophisticated) Reader by implying directly (or allowing the inference) that there are no (or easily treated, if extant) difficulties in using the described algorithm class or protocol or ... Not a good outcome in my view. ww 14:12, 18 May 2006 (UTC)

Pointing specifically at the government as the corrupter of CA signing authorities is both biased and short sighted. Any number of entities might blackmail or convince a CA to sign bogus certificates (kidnap CEO's kids, bank holding loan on CA or who has potential large legal suit for losses due to CA error, etc). Further this overlooks social engineering of applications (as happened to Microsoft), internal attackers at the CA (for profit, revenge, etc) and CA servers simply succumbing to intrusions. —Preceding unsigned comment added by 70.230.251.78 (talk • contribs)

Unclear part in Weaknesses section

In the last paragraph of the Weaknesses, the last two sentences about government coercion are very unclear. Right now it's written as follows:

This attack is especially interesting when the attacker is the government as they potentially have the power to persuade a Certificate Authority to sign a bogus public key. Then the government can plug off the cable at Bob's ISP and insert their bogus web server. The function of this server is to present itself as Alice (validated by the certificate obtained by coercion), log all messages and forward them to the "real" Alice web server.

I started rewriting it as,

This attack is especially interesting when the attacker is the government as they potentially have the power to persuade a Certificate Authority to sign a bogus public key. In this case for instance, if Bob's ISP was sending a message to Alice, they could intercept the message by posing as Alice (validated by the certificate obtained by coercion), log all mesages and then forward them to the "real" Alice web server.

but I think this is wrong. I'm really having trouble understanding what the original text meant. --Etienne 05:10, 30 July 2006 (UTC)

That section is pretty badly written. Anyone who can get a bogus certificate that the client trusts can mount an MITM attack in the obvious way. The paragraph just says the government is in an unusually good position to get such certificates, because it can issue compulsory legal orders to any CA in its jurisdiction. Phr (talk) 11:12, 30 July 2006 (UTC)

Public-key diagrams

I made some diagrams for this article. I put the first draft version of the diagrams into the article. I hope you like them. I have some ideas about how to extend them but not sure that is necessary. For instance adding the Alice and Bob users in the encrypt and sign images just like I have in the shared secret image.

I made the images in .svg format which usually works fine. But this time Wikimedia rendered them wrong. I tried several ways to fix it but failed. So I put .png versions into the article instead. The .svg versions of the images are available here: User:Davidgothberg/Test_area. If any one can fix them so they render correctly I would appreciate it.

--David Göthberg 09:45, 7 August 2006 (UTC)

Nice diagrams! One minor issue: "secret key" has slight connotations of symmetric cryptography, so we more normally say "private key", and we'd designate it A_VK instead of A_SK. Would that be hard to fix?

Phr (talk) 09:39, 7 August 2006 (UTC)

Oh, thanks! Ah yes, I should have read the article and looked around more first. I just made those diagrams based on my old slides from the 90's when I taught crypto. So I am not entirely up to date on modern naming. And sure, I expect to do several changes/improvements on the images based on comments on this talk page. --David Göthberg 10:00, 7 August 2006 (UTC)

Ok, I updated the images. I changed "secret key" to "private key", A_SK to A_VK and I did put in a little more Alice and Bob to make it clearer who does what when. --David Göthberg 12:40, 7 August 2006 (UTC)

I think the Alice and Bob labels actually make it more confusing, but I'm sleepy. I'll look again when I'm more alert. Phr (talk) 13:42, 7 August 2006 (UTC)

Yeah, I sort of agree. The added Alice and Bob labels made the images "harder on the eyes" since the images then contains to many items. So I am not sure if we should have those labels in there or not. But my hope is that they make it clearer for beginners (after some studying of the images). That is, it perhaps makes it a bit harder to see the basic functionality of the keys, but it better explains who does what with which key. Another option is to remove the (A_SK) and (A_VK) since they are not necessary for this article. I just put them in there to make people used to the notation since such notation is used in many other related articles. (And those images might be reused in those other articles too.) --David Göthberg 23:56, 7 August 2006 (UTC)

I've looked again, I still think the Alice/Bob labels are confusing and I advise getting rid of them except when they're needed to distinguish between roles. Phr (talk) 01:09, 8 August 2006 (UTC)

Just before your comment I updated the images again. I removed the (A_SK) and (A_VK) to make the images less cluttered. And I added "Big random number" to the first image to make it self-explanatory and not dependant on the image caption. Regarding the Alice/Bob labels I am unsure myself. To me they seem both good and bad. Depends on what one wants to explain. Let's leave them in there for a while and see what other Wikipedians think about it. I will ask the people in the crypto chat I hang out in too, they often have some good comments/ideas. --David Göthberg 01:39, 8 August 2006 (UTC)

Like the idea of these diagrams a lot, one slight error: key generation in RSA needs *two* big random numbers to form the public and private keys.WolfKeeper 01:48, 8 August 2006 (UTC)

Ehm, actually as far as I understood it RSA key generation uses MANY random numbers when it tries to find primes for the keys. (But I am not a maths guy so don't quote me on that.) However, the libs I have seen take a PRNG as input to their RSA key generator, and we seed that PRNG with one single random number. Other public key algorithms I have seen (some DH variants) actually uses one single random number as the private key itself and only does a calculation to generate the public key. But in the RSA case, if you think of the PRNG + key generator together as one "key making function" all you need to feed it is a big random seed.

It's really the same thing as when we use one single shared secret to create many keys. For instance one encryption key and one MAC key for each message sent. For that we usually use the shared secret as a seed to a cryptographically secure pseudo random number generator (CSPRNG).

And an interesting side note: If you feed the "key making function" the same "random number" the next time you get the same key pair again. Normally we delete the random number since we do not want to risk it getting exposed. But one could use a long passphrase as that seed and thus be able to bring along ones "key pair" in ones head just as a passphrase. And a software could recreate your key pair whenever you need it from your passphrase. This would be nice for some usage cases. --David Göthberg 03:45, 8 August 2006 (UTC)

I'm ok with "key making function" and one random number as the diagram already has. It's not RSA-specific, and RSA keymaking info can go into the RSA article if needed. The suggestion of generating RSA keys from passphrases has been in the GnuPG bug database for over 3 years [3] but nobody has done anything about it ;-) Phr (talk) 05:47, 8 August 2006 (UTC)

I'm under the impression that Hushmail can generate a private key reproducably from the users passphrase. On a side note, I have been trying to clean up the category Cryptography on Commons, which has gottenrather big. Could you recat the diagrams to "Category;Cryptography diagrams" next time you edit them?--agr 02:55, 9 August 2006 (UTC)

Phr: Hehe, funny to hear about the GPG case. Agr: Nice to hear that Hushmail already has that function. And regarding the categorising, I am way ahead of you! I already did recategorise those crypto diagrams and all my old ones and many others too into the "Category:Cryptography diagrams" on commons 22 hours before you wrote your comment. Although there are a bunch more diagrams in the Category:Cryptography on commons that needs recategorising. And there are many crypto images here on en.wikipeida.org that needs moving to commons too. But I didn't have have more time at the moment. (I have a swarm of qute dance girls waiting for me down at our city festival each evening so I have a little less time for Wikipedia than usual right now. :)) By the way, that diagram category is nice. Suddenly it doesn't matter so much if one miss to put a note in the diagram description about any other similar versions since one can now easily get an overview of all the diagrams in that category. --David Göthberg 12:13, 9 August 2006 (UTC)

Bug in signing diagram

The literature usually describes the private key operation as sign/decrypt and the public key operation as verify/encrypt. Yet the diagram/image that shows the signature scheme shows the private key operation as sign/ENCRYPT and the public key operation as verify/DECRYPT. I think this is confusing at best. But is it wrong or dangerous for any specific public key scheme? 163.181.251.9 (talk) 22:11, 24 September 2009 (UTC)

Intuitively, you can "decrypt" the message you wish to sign to obtain a signature. Another user can encrypt your "signature" and if it equals the original message, the signature is valid. This is what's meant to be captured by the picture. However, taking into account modern definitions of security, this does not work in general.

Regardless, as you suggest, the encrypt and decrypt labels should be switched. I would go further and remove them all together. I'll put a note on David Göthberg's page. Let's see if he's willing to edit the diagrams. Skippydo (talk) 20:14, 25 September 2009 (UTC)

It's an SVG. If the diagrams need to be changed in that way, just download it, open it in a text editor, swap or remove the text, and re-upload it as a new version of the file.
Cheers, Amalthea 21:17, 25 September 2009 (UTC)

Decrypting and signing are not the same operations, neither for ElGamal nor for elliptic curve cryptosystems. Some public key cryptosystem only allow either signatures or just encryption. And even in the case of RSA signing and decrypting are significantly different operations. Hence the "encrypt/decrypt"-labels should not be switched, they should be removed. 85.3.238.229 (talk) 21:21, 25 September 2009 (UTC)

Reading my sent emails?

I tried following the diagrams and the article but I can't understand why I'm able to read sent emails I've encrypted in Outlook Express since I shouldn't be able to according to the diagrams and this statement "a message encrypted with a recipient's public key cannot be decrypted by anyone except the recipient possessing the corresponding private key. This is used to ensure confidentiality." I am not in possession of the recipients private key, only their public one, so how come I am able to read the emails I sent to them in my sent items folder? As far as I know digital signing and encryption used in Outlook Express is public key cryptography.121.209.117.2 21:43, 28 September 2007 (UTC)

That must be due to that your email program does some additional trick. Either it also saves a cleartext copy of your sent emails or it encrypts the emails to one extra recipient, namely yourself. That is, it usually is possible to add several recipients for an encrypted text, and all of those recipients can open and read the text. And many email programs by default add yourself as one of those "recipients" in the encryption header, but of course without actually sending a copy to your email address since you already have a copy on disk.

It works like this: The text itself is usually encrypted using a randomly chosen symmetric key since that is faster and stronger. That is, a big random symmetric key is created extra for that one message. Say a 128 bit AES key. Then that random symmetric key is encrypted using the public key of the recipient and the resulting block of encrypted key is added in the encryption header of the message. Since those blocks of encrypted keys are fairly small there is no problem to add more such small blocks in the encryption header of the message, thus adding more recipients. The recipients then simply find the key block with their name on it and decrypts that block using their private key thus getting the symmetric key that can decrypt the actual message text. All this is of course done automatically by the email encryption software.

--David Göthberg (talk) 09:40, 6 February 2008 (UTC)

Brute Force

This article seems to claim that private key encryption cannot be made safe against a brute force attack. However a private key encrytion placed over another private key cannot ever be cracked by someone without at least one of the keys. Why has this been overlooked? Symmetric Chaos 13:18, 20 September 2006 (UTC)

Not quite. The situation is actually more complex than you state. Consider a symmetric key cypher (eg the Caesar Cypher with offset 3) which is "placed over" (I am assuming you mean superencryption here) a Caesar Cypher with offset 4. The result is a single Caesar Cypher with offset 7 which is just as vulnerable to frequency analysis as any other.

Superencryption can in fact increase analytic difficulty, perhaps to the point of practical infeasibility, but not to unbreakability. The one time pad still has the only proof of security amongst usable cyphers for reasons grounded in information theory.

That's why your understanding has been 'overlooked'. ww 16:44, 20 September 2006 (UTC)

Ah, he, I did not understand what Symmetric Chaos was asking before I read the response from ww. Yes, superencryption if used right makes it much harder to crack messages. But it doesn't make it impossible in the strict sense of the word, just much harder. Simple superencryption really is more or less the same as using for instance a block cipher with twice as many rounds internally. Good superencryption of course uses two "sufficiently independent" keys. Say two keys derived like this: key1 = hash( salt1 + user_key ), key2 = hash( salt2 + user_key). And it preferably uses two very different encryption algorithms on top of each other, for instance a block cipher on top of a stream cipher. For instance Twofish on top of RC4. But still, there is no proof that that is not crackable. We can just assume (to a high degree of certainty) that superencryption is much harder to crack than running just one of those ciphers alone.

--David Göthberg 18:10, 20 September 2006 (UTC)

That's simply incorrect. If I can bruteforce the keyspace I can as well bruteforce the combined space of two keys. Arvindn 05:20, 3 January 2007 (UTC)

Terminology (Key Making Function)

I have never seen the term "Key Making Function" used in any cryptography paper - the standard term is Key Generation function. If no-one objects, I will change the diagram to reflect this. Birkett 15:17, 21 November 2006 (UTC)

Oh, right you are. When I made that image I just used the first term that came to mind without checking what term is the most used. But I now did the Google test and it confirms that you are right. So, I made a new version of the image and uploaded it. --David Göthberg 01:27, 19 May 2007 (UTC)

Broken external link

The external link for note 4 ("The NSA has also claimed to have invented public-key cryptography, in the 1960s; however, there is currently (as of 2004) little supporting public evidence for this claim") is broken. I suspect it was attempting to link to something called "NSA Memorandum 160" -- could someone with actual knowledge of this subject confirm that? (The text of that memo is available online; this may be exactly what was being linked to.) Jd4v15 19:30, 1 February 2007 (UTC)

Stupid Demands for Citations

Reading this article is annoying because of the dorky demands for citations every 6 words. Stop making demands for citations for simple statements. It detracts from the readability. --61.9.138.145 23:53, 12 March 2007

The worst offender is the Security section and it seems well-deserved. "There is nothing especially more secure about asymmetric key algorithms than symmetric key algorithms" is a claim that clearly needs justification, especially since multiple users with the same symmetric key increase vulnerability. If one person's key is cracked or lost, the entire network's security is gone. With an asymmetric key encryption, if one person's private key is cracked or lost, that user and that user only has lost their security.

I can make the same argument the other way around. Consider a network system using asymmetric crypto for securing communications for users within a subnetwork. If the private key is broken, the entire network security is compromised. — Loadmaster 18:02, 31 July 2007 (UTC)

The network's private key in an asymmetric key system is a single point of vulnerability. Multiple users with the same symmetric key ensures multiple points of vulnerability. Either way, if you lose control of your server's key, you're screwed. With a symmetric key system, if you lose control of a user's key, you're also screwed. Gahread 07:56, 3 August 2007 (UTC)

There is also a need to securely exchange the symmetric key between two parties. The usual method is to use a hybrid encryption, where the symmetric key is sent via an asymmetric key encryption! I'm not enough of a crypto expert to delete that paragraph outright, but it sure looks fishy to me.

Gahread 09:16, 31 July 2007 (UTC)

I find these statement unclear: does it means that symmetric key algorithms (when the key is properly protected) are better (i.e. harder to break) than asymmetric ones? I thought it was otherwise, but this sentence suggest this idea. Rjgodoy 16:34, 31 July 2007 (UTC)

It's supposed to mean that, mathematically speaking, neither is inherently more secure than the other. Both suffer from the same weaknesses about protection of secret/private keys. The primary drawbacks to PK crypto are its slowness and requiring bigger ciphertext block sizes. — Loadmaster 18:02, 31 July 2007 (UTC)

So even if we might use a symmetric system to transmit data because of the greater speed, why do we use PK over symmetric to establish a connection with most common secure web connections? Gahread 07:56, 3 August 2007 (UTC)

PK is used to establish a shared symmetric key for an SSL session. Symmetric crypto can't be used to do this because the parties have to have a way of encrypting the key exchange beforehand (to foil man-in-the-middle attacks). This is only possible with PK crypto, where each party already has its own private key. Once the symmetric key is agreed upon by both sides (actually, each side contributes half of the key), symmetric crypto can then be used for the rest of the session. — Loadmaster 23:00, 3 August 2007 (UTC)

Indeed there exists key agreement algorithms with assymetric keys for perfect forward secrecy, i.e. disclosure of long-term secret keying material that is used to derive an agreed ephemeral key does not compromise the secrecy of agreed keys from earlier runs. Rjgodoy 04:33, 4 August 2007 (UTC)

Reissuing public keys

The following text seems dubious:

When a private key higher in the hierarchy is compromised or accidentally disclosed, all of the keypairs beneath it in the hierarchy must be assumed to be compromised and must be re-issued.

It appears that when a private key high in the hierarchy (which probably means a key of a certificate authority) is disclosed then this key must be revoked and certificates signed with that key must be reissued. But I can't see any need for revoking keys signed with that key. This text seems to be some kind of false advertising for the company offering transient key crypto. 85.2.94.204 (talk) 22:28, 11 December 2007 (UTC)

This comment neglects a fundamental issue of security in this context. When was the higher level key compromised? Since one can't know this, one must evaluate all endorsements made using that key as suspect. they must be abandoned in any system which makes claim to a concern for security. If there is a company offering such a product (just what the product could be is at best obscure), there is no endorsement here in any case.

Not a problem. Retain. or make clearer. ww (talk) 22:50, 11 December 2007 (UTC)

Ok, I'll try to give an example. Let's assume user Alice chooses an key pair and gets a certificate on that key pair from a certificate authority CA. At some point it becomes known that the secret key of the CA has leaked. As you say, it may not be possible to know when the secret key has leaked. Of course, the key of the CA needs to be revoked. This also means that the certificates issued with the leaked key can no longer be trusted. However, Alice did only submit her public key to the CA and not her private key. Hence, the private key itself is not compromised. Thus all she needs is a new certificate, but not a new key pair. However, the text cited above seems to imply that Alice would have to choose new keys. 85.1.100.113 (talk) 07:46, 12 December 2007 (UTC)

Once again if a CA leaks their then there is not true that all keys that were signed with the CA key are compromised. Only the key that is leaked needs to revoked and changed. This means that the certificates signed with the key are now invalid and need to be replaced, but not the keys that were signed with it. I've removed the corresponding misleading paragraph.85.2.20.87 (talk) 09:38, 20 September 2008 (UTC)

Your point is strictly correct but has no practical impact. The only reason I use a PKI is to have some confidence that the public key I have, purporting to be yours, is yours. If I don't know you (or you are a Web site on a server on some other continent I've never visited and don't speak the language anyway), I've no reason to believe that this public key is yours or not, and I rely on a PKI for that evaluation. So if that PKI hierarchy is compromised, I can no longer trust any of the certificates it endorses, including any CAs lower in the hierarchy. One of which may have signed your certificate. And if I can't trust those certificates, your still uncompromised private key won't mean squat to me. You'll have to generate a new key pair, get a new certificate for the public key in that key pair from some uncompromised CA hierarchy, and send me the new certificate. I will of course reserve the right to consider that CA to lacking credibility and so we may still not be able to communicate securely.

One escape from the PKI tangle of dubiousness is to adopt the Web of Trust model used exclusively by the early versions of PGP (still usable, mostly), but it has troubles too. There're just different ones, but since it was decentralized, Zimmerman found it far more acceptable for his design purposes. With it, I must make a correct evaluation of the reliability of the signers of your certificate (many of which I don't know personally and so my evaluations will be a little shaky), and so on, in order to be secure. in some respects, better, in others worse (especially in that there is no prospect of commercial profit by running a centralized certificate service).

So, do you think that must be rewritten to make more clear the underlying point? ww (talk) 22:57, 10 October 2008 (UTC)

Most of what you write here is ok and makes perfect sense. However, you keep repeating that a leak of a CA key means that not only the CA key must be replaced but also the uncompromised keys of the users. To clarify, this let's assume that user Alice uses a 2048 bit RSA key and that the CA uses only a 1024 bit key. (This assumption is of course a little contrieved but I hope it helps to have a more concrete situation here). Now assume further that 1024 bit factoring result is published. This of course means that the CA key must be assumed compromised. And, as you write, another user can no longer verify that Alice's key really belongs to Alice. However, all that Alice has to do is to get another certificate on her old 2048 bit key from a CA with an uncompromised key (e.g. 2048 bit RSA). Alice doesn't have to change her key.

I think, all this does have practical impacts. First, Alice's digital signature before the CA key leak can still be verified, once she has a new certificate on her old key, respectively encrypted messages to Alice remain confidential. Alice can get several certificates for her key, and use it as long a her key is uncompromised an the receiver trusts at least one of the certificates. Expanding on this further leads into the PGP model that you already describe.

As for changing the text in the article: The offending statement is already removed from the text. Giving detailed explanations of PKI models would be nice. It may even enough stuff for a new article. 85.2.20.229 (talk) 09:32, 12 October 2008 (UTC)

<--

You state the case exactly, but do not draw the practical conclusion. A compromised CA means that all certificates depending on that CA (or any CA lower in the heirarchy) must get a new certificate from some other CA. This is the entire problem CAs are supposed to assist with and solve. When they fail, users are thrown back to the Wild west condition of being unable to be sure any key belongs to anyone in particular, thus stopping protected communications abruptly and permanently until new certificates are obtained and published. The problem is not with the user's encryption/decryption which as you point out may be perfectly sensible and secure in practice, but with the system on which communication relies, namely an uncorrupted CA in a PKI system. Both are required for successful secure communication and either alone is insufficient.

I'll look into the article again to see whether something can be done to make clear the point to our Average Reader. ww (talk) 00:23, 13 October 2008 (UTC)

I think you are wrong again in one point. First, (it is probably just a typo) there are no certificates on other certificates. Rather CAs issue digital signatures confirming that some key belongs to a given identity. Then it is not necessary to reissue certificates lower in the hierarchy. Assume that we have a certificate chain. CA1 signs that the public key PK2 belongs to CA2. CA2 signs that PK3 belongs to CA3. Now if CA1 leaks his/her key then this of course means that the certificate linking PK2 to CA2 is no longer valid and of course this means that any certificate chain containing this certificate can no longer be validated. However, unlike what you write it is sufficient to replace just the certificates issued by CA1. I.e., in the example here all we need is a certificate that assure that PK2 belongs to the certificate authority CA2. The other certificate that assures that PK3 belongs to CA3 is still valid and does not have to be reissued. The point is that one has to clearly distinguish the case where a key has been compromised and the case where it is merely not possible to verify that a key belongs to a claimed identity. 85.2.113.185 (talk) 11:37, 18 October 2008 (UTC)

In your example above, compromise of the CA1 key means that no certificate relying upon its security may be trusted. Including those lower such as CA2 (singed by CA1) and so on. Replacing CA1's key does nothing with regard to some user attempting to rely on CA2 or lower certificates. They must be reissued since there has been a security breach in a context on which they depend. As for users, they now hold certificates from CAx which depended on CA1 (when was it actually compromised??), and no one can now rely on them. Time for new certificates, and, for sanitation's sake, new user keys as well. Someone potentially playing certificate games might actually be Malory, and the only to defeat his evil schmes is to move to new keys asin the new certificates.

As I have agreed, this is not strictly necessary in theory, but as amatter of safe practice is quite sensible. Are we closer to mutual understanding? ww (talk) 03:02, 19 October 2008 (UTC)

Nope, you are still drawing the wrong conclusion. If a CA leaks their key there is absolutely no need for any other party to change their keys an there is no benefit for it either. Let's assume Alice has been talking to Bob using Bob's public key verified by a certificate chain involving CA1 as above. Now when CA1 leaks it's key then Alice may no longer trust that the public key she was using is Bob's key. So what she needs is a new certificate chain that she can trust. If she can get such a chain then she can regain the trust that she is and always was talking to Bob. As long as Bob keeps his key safe there is no need for him to change it. That means the holder of the public key (and not the holder of the private key) has to take actions. I.e., each party has to reevaluate whether the public keys they use really belong to right party. Leaking CA keys means that the link between public keys and identities may be compromised, but not the keys themselves. And hence this link must be fixed and not the keys. 85.2.21.96 (talk) 06:45, 19 October 2008 (UTC)

We're repeating the same thing over an over again. With one exception. If I no longer trust a CA )and so its subsidiary CA servers) then it is clearly so that new certificates are required.

So far, so agreed. I make a further practical point, not one forced by the theory. Given that bindings in the certificates are defunct or must be assumed to be, then to avoid any possibility of games with the key pair, it behooves all concerned to generate a new key pair prior to seeking new certificates from some other, more trustworthy, CA. Are we tracking yet?

On another point, the text we've been reverting back and forth is illustrative and more informative than the text you have substituted, at least to the Average Reader. sharp distinctions are useful in the end, but for informational purposes, it's useful to approach the most precise formulation gently. A pedagological point really. ww (talk) 23:57, 19 October 2008 (UTC)

Well, you haven't made a point yet, because your repeated claim that uncompromised users and CAs must revoke their keys has not been backed up by a single concrete argument. As for pratical implications: if I had an application where a CA key leak would have major implications, I'd proactively get multiple certificates on my keys, so that in the case of a leak I could without interruption replace the untrusted certificates with other ones. Replacing my keys in a situation where authenticated distribution of the new keys may be rather uncertain would not be one of my considerations.

As for the encryption/signature change. A digitial signature is not the same as just encryption with the private key. Most public key encryptions (e.g. ElGamal encryption, ECC, McEliece, ...) can not be used in this way to sign messages. And even for RSA encryption and signing are completely different once one considers message padding. Hence the text I removed was simply wrong. Pedagogically it is a bad idea to describe a concept incorrectly and quite often leads to confusion. Specifically, I've seen dozens of help requests from people trying to implement digital signatures by just calling encryption/decryption functions of some crypto library and not understanding why this does not work. 85.2.108.104 (talk) 05:11, 20 October 2008 (UTC)

<--

Failure to authenticate a piece of information does not invalidate that piece of information. Certificates exists precisely to avoid man in the middle attacks. They are independent of the security of the actual scheme, where public keys are assumed to be communicated through an authenticated channel. There is absolutely no reason to discard a key when a certifying authority of this key is compromised. I cannot see any theoretical or practical reason why one would wish to discard the key in this case. Skippydo (talk) 06:18, 20 October 2008 (UTC)

The passage over which we are wrangling does not, last time I read it, claim to be anything other than illustrative of the principle, not an elucidation of any particular scheme. If someone thinks it is, I think it's been misread. But if so, clearly some changes to make clear the illustrative nature is indicated. As for not corresponding to any single (or all -- a single example couldn't after all do so) signature scheme, well, illustrative examples don't generally do so. As an point in aid of Reader understanding, I think plunging that Reader into the labyrinthine details of an actual signature scheme would be a disservice. And avoiding an illustrative example (a cartoon, if you will) disserves that Reader by leaving them with (ans survives now) foggy writing and no increased (even simplified) conceptual clarity. I cannot see that there's a disagreement over theory here and have said so multiple times above. The crossed wires we're having are on presentation and writing issues, not technical ones.

As for precautionary re-generation of keys, this is normal prophylaxis to do so, even in the absence of a system breakdown of any kind. After such a breakdown, the precautionary re keying should, to a careful user, just be made sooner. NOT a theoretically forced point, folks. Just reasonable hygiene. ww (talk) 21:26, 20 October 2008 (UTC)

As for precautionary re-generation of keys, this is normal prophylaxis to do so... NOT a theoretically forced point, folks. Just reasonable hygiene.

You seem to state that it's normal and reasonable to unnecessarily regenerate keys. I don't believe you will find literature which supports you. Do you have a reference? Skippydo (talk) 23:35, 20 October 2008 (UTC)

Not off the top of my head no. I'll dig into the stuff I have available to see if I can find one WP will find acceptable. ww (talk) 01:13, 21 October 2008 (UTC)

Ok, here is a reference: Report of the Nist Workshop on Digital Signature Certificate Management, Dec 10-11, 1992. On page 16: Elaine [Baker] finished by showing the ASN.1 specs for the Certificate Revocation List and for the Attribute Certificate. There was considerable discussion over what would be revoked in the case of a CA compromise. If we stop using the compromised CA key, do we also need to stop using a user's key in any certificate signed with that (now) compromised key? It was pointed out that we must differentiate between the idea that we are revoking certificates and not revoking keys. That is, it is not in general necessary to reissue a user's public/private key pair due to CA compromise. After an appropriate investigation, you may reissue certificates signed in error, or hot list certificats as necessary, but the keying material may still be valid. Hope, this finally settle the discussion. 85.0.101.155 (talk) 07:02, 21 October 2008 (UTC)

Legality (UK)

The UK has a law (Regulation of Investigatory Powers Act or RIPA) that requires you to either provide clear-text versions of encrypted data, or to provide a decryption key upon receipt of a "Section 49" notice. Recipients are also bound from telling anyone apart from their lawyer that they have been issued the notice. This power, whilst originally passed in 2000 was activated in 2007.

Is it not possible for someone to decrypt data that has been encrypted with other people's public keys. To do so would require access to the other person's private key. It is therefore a problem to use public-key cryptography if you are not keeping a clear-text version of everything you encrypt.

For example: say you use a friend's public key to encrypt a message to him - say your bank details to repay you some money you lent him. There is no surrounding text on the message to make it clear what the message was about. 5 years go past. He has changed his keys in this time, or has moved away, or has died, or lost his private key for some reason. Should you ever be asked to tell the police what the message in my Outbox was about, or to provide a cleartext version, you would be unable to comply as you could never have decoded it. That gives you an automatic 2 year jail sentence.

This has not yet come to court, although it has started to be used by the police - and not against al-Qaeda or child porn creators, either.

Well, that just goes to show how stupid that law is. If I have a block of random data on my disk, for instance as the result from a test run of my home built CSPRNG they could send me to jail for "refusing to decrypt that file to something readable". See how stupid the law is?

Another perhaps slightly more common situation is that I have switched to a stronger key pair and after some years might not any more have a copy of my old no more used key pair. Thus I can not comply either.

Another common situation is when we use encrypted memory swap files. Such swap file encryption is usually done with a symmetric key that is randomly chosen at boot time and kept in RAM during the session and lost when the computer is turned off. Since there is no need to read the old swap file on next run. So there is no way to comply if the police wants to read your swap file.

But hey, governments love broad silly laws that no one can comply with so they can send any one they dislike into jail...

That the law comes with a built in "gag order" so you are not allowed to tell people when they harass you is just typical. Who thought there was freedom of speech? From what I know from some countries that has similar laws there is a way around that gag order: Refuse to comply, they send you to jail and then it becomes public that you refused, then give them the key after a day in jail and you are released. Unfortunately most countries have an intermediate step where you first are fined a hefty sum.

Fortunately I live in a country where we actually have the full "right to remain silent" even in court. And no, that is not the US, there you do not have the right to remain silent in court.

--David Göthberg (talk) 10:00, 6 February 2008 (UTC)

Problem with padlock exchange analogies in "A postal analogy" section

The analogy given: "In an asymmetric key system, Bob and Alice have separate padlocks. First, Alice asks Bob to send his open padlock to her through regular mail, keeping his key to himself. When Alice receives it she uses it to lock a box containing her message, and sends the locked box to Bob. Bob can then unlock the box with his key and read the message from Alice. To reply, Bob must similarly get Alice's open padlock to lock the box before sending it back to her."

is flawed in that it is subject to a man-in-the-middle attack. If a malicious third-party were to intercept Bob's open padlock in transit, and then sends their own open padlock to Alice, Alice will send her secret message back with the attacker's padlock, which the attacker can easily remove. Once the attacker has finished with the message, he can simply replace Bob's padlock on the message, and send it to Bob, who believes it has come from Alice untampered.

The second analogy with two different padlocks is also flawed:

"In another kind of asymmetric key system, Bob and Alice have separate padlocks. First, Alice puts the secret message in a box, and locks the box using a padlock to which only she has a key. She then sends the box to Bob through regular mail. When Bob receives the box, he adds his own padlock to the box, and sends it back to Alice. When Alice receives the box with the two padlocks, she removes her padlock and sends it back to Bob. When Bob receives the box with only his padlock on it, Bob can then unlock the box with his key and read the message from Alice."

The problem again lies in a third-party with their own padlocks. When Alice sends the message with her padlock to Bob, the attacker intercepts and places his own padlock on the box, and sends it back to Alice, who dutifully removes her padlock, and sends it off to the attacker, who can now unlock and read the message and possibly change it maliciously. Now, similarly, the attacker can send the box off to Bob with his padlock on it, and Bob, believing it to have come from Alice, places his padlock on it, and sends it off again. The attacker removes his padlock and sends it to Bob, who removes his padlock and reads the tampered message.

In both cases, the main problem is the fact that there is no verification of identity. Bob and Alice have no idea what the other's padlocks should look like, and even if they do, have no way to verify that it is in fact the senders.

I think these weaknesses should be detailed in the Weaknesses section, as there is no clear (from what I can see) expression of the weaknesses of the actual analogy. Sorry for the lengthiness, but I felt the analogies needed to be picked apart in detail.

Matwilko (talk) 17:08, 9 March 2008 (UTC)

Another issue I see with the example is - when it says "First, Alice asks Bob to send his open padlock to her through regular mail, keeping his key to himself. When Alice receives it she uses it to lock a box containing her message". How is that possible, when Alice does not have the key, but only has the padlock Bob sent her. She cannot lock a box with only the padlock. I don't think the postal analogy holds true for asymmetric keys because its difficult to find a real life equivalent to the mathematical concept underlying this technology. —Preceding unsigned comment added by 17.227.143.125 (talk) 20:35, 28 July 2009 (UTC)

Clarification on insuring authentication and confidentiality needed?

In the security section, the following statement I think could use more elaboration: "To achieve authentication, non-repudiation, and confidentiality, the sender would first encrypt the message using his private key, then a second encryption is performed using the recipient's public key."

Namely, does it really matter which encryption is done first and which is done second? If if does, it would probably be good to add a sentence explaining why. If it doesn't, to add a sentence saying the actual ordering of the two encryptions is unimportant. —Preceding unsigned comment added by 70.17.114.124 (talk) 20:19, 22 June 2008 (UTC)

Key combination

This article contains a diagram showing the possibility of two parties each combining their own private key with the public key of the other party to yield a new shared secret. I assume that this is done without exchanging any messages (which would make it easy). I see that this is possible with some public key schemes (notably ElGamal), but I have no idea how (and honestly doubt that) it could be done with RSA for example. Could someone please give more information about this (in short: Citation needed)? —Preceding unsigned comment added by 141.3.32.141 (talk) 08:36, 10 July 2008 (UTC)

You are looking for Diffie-Hellman key exchange. I should mention, it is not recommended to use your key for both secret sharing and encryption. The security model is different in this situation. Doing so may leak too much information or give an advisory too much power, making the scheme insecure Skippydo (talk) 13:27, 10 July 2008 (UTC)

I am well aware of the fact that DH key exchange and ElGamal are closely related. But how can you use a Diffie-Hellman using your own private RSA key and the public RSA key of another user to obtain a shared secret without sending any additional message? Please feel free to use my User talk page (German wikipedia). —Preceding unsigned comment added by 141.3.32.141 (talk) 16:10, 14 July 2008 (UTC)

Christian Henrich (141.3.32.141): The four images in the article shows the four main operations that can be done with public-key cryptography. But no public-key cryptography algorithm can do all of the operations as far as I know. For instance RSA can do encryption and signing, but not key combination to get a shared secret. (Well, RSA can do it if you allow sending one message during key negotiation, and that is often how we use RSA. And that message can be added to the beginning of the actual encrypted text message you are sending, so usually doesn't cost any extra messages to send.) While for instance Diffie-Hellman can only do the key combination to get a shared secret and can not do encryption and signing. (But the DH derived shared secret is usually used for encryption, and for MACing which is kind of signing.)

And you can not use your RSA keys to do a Diffie-Hellman operation. You need different algorithms and different keys for different kinds of operations. And that is why for instance "one" PGP key usually contains several different keys together.

--David Göthberg (talk) 14:03, 19 July 2008 (UTC)

DG, I changed the caption to one of the images to note that exposing one's secret key is insecure and you reverted. You would seem to think I've missed something, but what it is remains unclear. More explanation please? If I'm right, we're misleading the unwary reader by concelaing crypto twistiness. ww (talk) 21:36, 19 July 2008 (UTC)

I agree that there we lose our notion of provable security when we use our asymmetric keys for anything except their intended purpose. If you wish to encrypt and share a secret using the same key, you need to account for that in your security model. By hashing the shared secret, we at least obtain a DDH oracle. It's not immediately clear to me that this can be used to mount some attack against some asymmetric scheme. Skippydo (talk) 23:08, 19 July 2008 (UTC)

Ww and Skippydo: I am not sure what you guys mean, but it seems to me that you have misunderstood what a shared secret is. A shared secret is never published. It is never shown to any one. It is a secret that is known to two communicating parties (Alice and Bob) and to no one else. That is, it is "shared" as in both Alice and Bob knows it, but it is not "shared" as in "published to the world". The shared secret is not sent on the wire so it is not exposed. (The shared secret is usually fed as the seed to a cryptographically secure pseudorandom number generator (CSPRNG) which is then used to produce all the symmetric keys and MAC keys we need to encrypt and MAC messages to be sent between the two parties. For instance TLS/SSL works this way.)

A shared secret can be a pre agreed key such as a password or passphrase, or it can be created using public-key cryptography. One way is to use Diffie-Hellman and similar methods, and that's exactly what those methods are intended to be used for. And that is what the fourth picture is showing.

Alice is not exposing her secret key to Bob, since Bob calculates the secret by using his secret key and Alice's public key. Bob can do that calculation at any time, without ever talking to Alice, so Alice is not exposing anything to him. And the same is true in the other direction, Bob is not exposing anything to Alice.

I think you guys need to read the shared secret article.

--David Göthberg (talk) 01:39, 20 July 2008 (UTC)

DG, The secret sharing idea (Shamir etc) seems skew to this concern. If Alice and Bob wish to establish secure communications, they will clearly have to have some shared secret in common they can use as a key or to generate a key. Diffie-Hellman exchange was invented for just this situation. But what was described in the image whose caption I changed was not that. It was the conjoining of a private key to some other material which was exchanged. That's insecure, should some method of identifying the two parts be found, for any eavesdropper (insecure channels remember) will then know a secret key. Had the image shown a secure hashing of the combination or of the secret key before being combined with other material, i suppose I wouldn't have seen the need to change the caption. I might not have agreed the image is realistic, but .... So I'm not sure we've gotten anywhere regarding the concern I raised here. ww (talk) 02:18, 20 July 2008 (UTC)

I am not sure if you do or not do understand this, but to make everything clear here goes:

The image does not show secret sharing. Secret sharing is not the same thing as shared secret, they are two very different concepts but unfortunately with similar names. The image shows that public-key cryptography can be used to establish a shared secret between two parties.

Also, the image does not show "concatenation" of the public and secret keys. It shows "combination" of the keys which means performing some mathematical operations.

For instance, we can use Diffie-Hellman with pre-published public keys. Take a look at the Diffie-Hellman article then read this: That is, Alice publishes her "g^a mod p" and Bob publishes his "g^b mod p". That is, Alice publishes "8" as her public key and Bob publishes "19" as his public key. (How Alice knows that "19" really is the public key of Bob is another matter, for that we need some kind of PKI system.)

Then Alice can calculate "g^ab mod p" by doing the Diffie-Hellman operations on her secret DH key and Bobs public DH key. "g^ab mod p" then is the shared secret. Bob too can combine his secret key and Alice's public key to calculate "g^ab mod p". Thus then both of them know the same "shared secret", a secret that no one else knows.

And note, this is exactly what Diffie-Hellman was designed for, to create shared secrets. It's not a special case or special use, it is the intended normal use. And as you can see, it doesn't involve encrypting or signing so it is a third kind of public-key operation.

The shared secret (and a session IV) can then for instance be fed as the seed to a CSPRNG to produce all the symmetric keys needed to encrypt messages between Alice and Bob.

There are other ways to establish a shared secret by using public-key cryptography. (But the image mostly shows the basic public-key operation that DH and similar methods use.) We can for instance do it with RSA keys:

Alice chooses a large random number to be the shared secret. She then encrypts it with the public key of Bob and then signs it with her own public key. Then she sends the result to Bob. Bob checks the signature and sees it is from Alice, and then decrypts the shared secret by using his secret key. Then both Alice and Bob knows the same shared secret, and no one else can know it, and Bob is sure that the shared secret came from Alice. (This of course assumes that Alice and Bob is sure that they know the right public keys for each other. For that we need some kind of PKI system.) It might look like it costs one message to establish the shared secret, but the "shared secret message" from Alice to Bob can be concatenated with the first encrypted message from Alice to Bob so it doesn't really cost any extra messages on the wire, just a slightly larger first message.

I don't know how I can explain this better to you guys. Those images were checked by a whole bunch of crypto experts I know. They all said it was good that I show the fourth image. Since the fourth image shows the operation that most people are not aware of in public-key cryptography, since most texts only talk about the encrypt and sign kinds of public-key cryptography. And I have tried the images on non-cryptographers and they did understand that "combine" did not mean "concatenate" but that it involved some more complex operations.

The problem is not the image, but that the article text doesn't explain this third kind of public-key operation.

--David Göthberg (talk) 13:13, 20 July 2008 (UTC)

I'm not quite sure what the fourth image is meant to represent. It seems to me as though it is simply Diffie-Hellman key exchange. If it is meant to be something more, let me know.

The caveat do not use the public/private key pair for anything except the key change is justified, since using the keys for any scheme with a notion of provable security destroys the security proof.

Let me give you a concrete example. Let us work in an elliptic curve equipped with a pairing. We assume that Alice and Bob each posses their own private public key pair and have obtained an authentic copy of each others public keys. Consider that Alice also uses that key pair for signing messages using BLS. We have a security proof for the BLS scheme which tells us that we may solve CDH using a BLS forger. A forger is able to query an oracle for signed messages of it's choosing and must output a signature for a message not queried. If we use the key pair to create a shared secret this gives the forger more power.

Let me give an outline of the security proof and show how it changes when the forger is given more power. I believe it is reasonable to assume that the forger can access message/ciphertext pairs encrypted under the shared secret. We being with an instance of the CDH problem and we design an instance of the signature scheme based on the CDH instance. We run a forger which has access to signatures of it's choosing so we need to respond to signature queries. Eventually, the forger will output a signature which we will use to construct a solution to the CDH problem. If we add in the forgers ability to obtain message/ciphertext pairs encrypted under the shared secret, then in our security reduction, we need to provide a forger with not only signatures of it's choosing but message/ciphertext pairs encrypted under a shared secret (of it's choosing?).

No such reduction exists that I'm aware of. This does not mean that BLS is insecure. However, it is no longer provably secure. Skippydo (talk) 18:06, 20 July 2008 (UTC)

Skippydo: I am not a cryptanalyst and not a mathematician. I am a software engineer specialized in computer communications and in computer security. I know how to use cryptographic building blocks to build secure systems, but I don't know that much about the inner workings of the cryptographic building blocks. Your discussion about BLS and CDH is over my head.

The four images are meant to show the four basic operations that can be done with the various public-key algorithms that currently are known. That is to create key pairs, and then use the key pairs to encrypt messages, or sign messages, or create shared secrets. And yes, Diffie-Hellman is one algorithm that does what the fourth image shows (to create shared secrets). As far as I have read and heard there are also other public-key algorithms that can do that, most of them similar to or based on Diffie-Hellman in some way. But that is not my area of expertise so I don't want to spend time looking around for them.

Skippydo: Are you saying that we should not show the fourth basic public-key operation? That we should not cover "Diffie-Hellman key exchange" and the other similar algorithms? As I see it that operation is a public-key operation, and it is not covered by the other images, thus it needs its own image.

I think that any deeper explanations of those basic four public-key operations and any caveats and so on should be in the article text, not in the image captions. Otherwise the image captions will be ridiculously large.

The caveat that Ww added to the fourth image was: "This is not recommended, as this exposes your private key in an insecure way. Other techniques should be used when generating such a shared secret." So are you guys saying that Diffie-Hellman should not be used to establish a shared secret? What should Diffie-Hellman then be used for? Do you mean that Diffie-Hellman is considered insecure or even broken? (Yes, I know that DH without some kind of PKI system can be broken with man-in-the-middle, but that is just as true for RSA. With PKI and similar you can make sure that the public DH key of the other user is not from the man in the middle.)

Another thing you guys seem to mention is that the same key pair should not be used for different kinds of operations. That is, a key pair should only be used for say signing. And I agree with that, that is a well known caveat in cryptography. Unfortunately the article doesn't currently mention that. (I think that should be added to the article text, not to the image captions.)

Another thing we need to add to the article text is that most/all public-key algorithms can only do some of the three basic operations. Thus different algorithms (and thus different key pairs) are needed for the different operations.

--David Göthberg (talk) 20:31, 20 July 2008 (UTC)

<-- DG, I now understand the point you had in mind when you reverted. I agree with your comments above. What I disagree with is that the fourth image suggests what you think it does. I took it to mean concatenation of secret key with other material as that's what the image shows. Other processing, as you suggest would clearly be sensible, which is the import of the comment I added. I was trying for brevity and a note of caution. If we revise the image to suggest additional processing, I'd have no problem. With the image as it was, there is sufficient imprecision that it can lead to confusion. It certainly misled me, and I'm a little less credulous re crypto than the Average Reader can be expected to be. ww (talk) 02:43, 22 July 2008 (UTC)

I've modified the caption image to clarify that the public/private keys are part of a larger key distribution scheme and not keys from another scheme (as was my misinterpretation). For a reference, please see Cryptography Theory and Practice by Stinson. I see no need to mention that keys should not be used in other schemes as well in the caption. However, I certainly believe the article itself should contain such a disclaimer. Thank you both for being so patient. I hope you find the changes satisfactory. Skippydo (talk) 03:53, 22 July 2008 (UTC)

Skippydo: Yes, I like your addition to the caption, it makes it much clearer. I seem to remember there are other algorithms than Diffie-Hellman that can combine keys like that, but public-key cryptography is not my area of expertise. If there are more methods like that then the caption should perhaps be: "In for instance the Diffie-Hellman key agreement scheme," (My suggested addition is underlined.)

Ww: Take a look at the image again. It doesn't show "concatenation of secret key with other material" as in "any other material", instead it clearly shows that two keys are fed into the yellow "Combine keys" box. And that box doesn't say "concatenate", it says "combine" and is a yellow box like the other processing boxes in the other images. What goes on inside the yellow box isn't important the first time a lay person looks at the image. The important idea that the image is meant to show is that there is some kind of way that two keys can be combined to produce a shared secret. More details about such key combination should then be in the article text. But of course, if you have a better label than "combine keys" to put in the yellow box, then by all means suggest it.

The same goes for the other boxes. For instance the second image (the encrypt image) doesn't show that when encrypting with for instance RSA the data first have to be "RSA padded" before encrypted. (I think RSA padding works something like this: Pad to a fixed length, then mix/avalanche and then treat it so it doesn't get some certain bad values that would give the secret key away.) Instead the encrypt image simply shows the basic idea/concept that the public key can encrypt and then the secret key can decrypt. So the yellow processing boxes contains all the operations needed, not just one single operation.

Remember, this is the introduction article about "public-key cryptography". The first images should show the basic concepts, not all the intricate details. That is for the article text and for other articles and other images to show.

--David Göthberg (talk) 05:56, 22 July 2008 (UTC)

Computational cost

I have a problem with understanding this section so it appears to me that there's an error in writing. It says:

...in such [hybrid] cryptosystem, a shared secret key ("session key") is generated by one party and this much briefer session key is then encrypted by each recipient's public key. Each recipient uses the corresponding private key to decrypt the session key. Once all parties have obtained the session key they can use a much faster symmetric algorithm to encrypt and decrypt messages.

Now it appears to me that all an attacker may need is a public key from a recipient (which is public, therefore available) to gain the session key and break any security. Another thing which I can't understand is whether the session key is encrypted by all recipents' public keys combined or using a corresponding public key for each recipent (it only says "encrypted by each recipient's public key).

I hope you understand what I mean. --Darko Maksimović (talk) 13:16, 24 July 2008 (UTC)

I explain how it works with several recipients in section #Reading my sent emails? above.

And remember, anything that is encrypted with a public key, can only be decrypted with the corresponding private key. That is, the public key can not decrypt what it itself did encrypt.

And sorry about the confusing article text, it needs a major rework and some images that explain hybrid encryption. That is, we need to properly explain how public-keys and symmetric keys are used together for efficiency and security.

--David Göthberg (talk) 21:33, 24 July 2008 (UTC)

Category rename suggestion

The related Category:Asymmetric-key cryptosystems has been nominated for deletion, merging, or renaming. You are encouraged to join the discussion on the Categories for Discussion page.

The renaming of the category was not suggested by me and I disagree with the suggestion. I just report it here so more editors can join in the discussion. (Follow the "discussion" link in the box above if you want to discuss it.)

--David Göthberg (talk) 15:40, 2 August 2008 (UTC)

And the result of the discussion was to not rename the category.

--David Göthberg (talk) 06:01, 10 October 2008 (UTC)

Category:Cryptography vs. Category:Public-key cryptography

Category:Public-key cryptography is itself a category within Category:Cryptography. — Robert Greer (talk) 15:34, 6 March 2009 (UTC)

Math ?

I'm reading this article and the diagrams are nice and all, but they lack any description of how this works mathematically. How is it possible to encrypt with one key and decrypt with the other? A math section would add to this article.

The math is specific to each algorithm/system. Check out the links in the "Examples" section (RSA, Diffie-Hellman, Elliptic curve cryptography etc.) for an assload of math. Arvindn 05:16, 3 January 2007 (UTC)

I concur - without reducing to practice, the article devolves into hand waving. You can write an algorithm from any of the diagrams on: http://en.wikipedia.org/wiki/Block_cipher_modes_of_operation This article should achieve at least that depth. —Preceding unsigned comment added by 69.254.42.143 (talk) 02:25, 19 January 2010 (UTC)

Unclear text

I'm having a problem with the following:

"The first invention [4] of asymmetric key algorithms was by James H. Ellis, Clifford Cocks, and Malcolm Williamson at GCHQ in the UK in the early 1970s; these inventions were what later became known as Diffie-Hellman key exchange, and a special case of RSA."

The first time I read this, it appeared to say that D & H's work was based on the GCHQ material. Following sentences clarify it, but what I'm looking for is a way of rewording the sentence so that it's referring to the the type of the inventions, rather than the specific work. How about, "...1970s; these inventions were {the same as, similar to} what later became known as..."? Since I'm not familiar enough with either work, I don't feel comfortable just plopping it in without checking with others.

GuiderBob (talk) 20:21, 27 May 2009 (UTC)

I'm not exactly familiar with their work either. But it's safe to say that they were developed independently. I took a stab at rewriting the paragraph in question. Also, I moved it to the end so that it has a better context. Please tell me what you think. Skippydo (talk) 02:09, 28 May 2009 (UTC)

Emminent Issues

Introduction needs to be rewritten for accessibility by nonspecialist readers, and to change from a description of behavior - "a form of cryptography in which" - to at least include a description of context - "a form of cryptography that". A nonexperienced person should be able to walk in and glean a concise and precise idea of what public-key cryptography is, what it is used for, to what end, in what media, and in what context as available; notwithstanding details, of course - that's what the body of the article is for.

Just added simplified explanation. Sure it needs checking. I hope it replaces that citation and latin and WTF terms full of crap which scared even my mom when she read it. Not that she read it, but You know what I mean. —Preceding unsigned comment added by 84.16.123.194 (talk) 13:41, 12 June 2009 (UTC)

Merge of Sections Needed

I performed a total revamp of the summary, and I separated what was a very detailed working description from the summary into a section called "How it works". This section needs to be merged with the section "Description", preferably retaining the name "How it Works". The description is already covered by the summary (I hope). Stephen Charles Thompson (talk) 22:03, 21 November 2009 (UTC)

"Asynchronous" cryptography

"Asynchronous encryption" is not an accepted term for public-key cryptography, and does not appear in any literature. Perhaps it is a corruption of "Asymmetric cryptography," which is an accepted term, but the word "asynchronous" refers to a different concept entirely. Hashbrowncipher (talk) 22:31, 23 February 2010 (UTC)

Clarify

I've been making a few minor changes, but need clarification on this passage:

In contrast, symmetric-key algorithms, variations of which have been used for some thousands of years, use a single secret key shared by sender and receiver (which must also be kept private, thus accounting for the ambiguity of the common terminology) for both encryption and decryption [emphasis mine]

What common terminology is ambiguous? What "must also be kept private", just the key or something else, too? I'm going to take a stab at fixing this up, but please let me know or help out if I botch anything. Thanks! /ninly_(talk) 21:29, 6 July 2010 (UTC)

Misleading "How it works" section

The "How it works" section states that "each user has a pair of cryptographic keys—a public encryption key and a private decryption key". This makes it sound like public keys are only uses for encryption, and private keys are only used for decryption, which not the case for signatures. For years, I was confused on this point. The article needs to make it more clear that information encrypted with one key (which may either be the public key or the private key, depending on what you're trying to accomplish) may only be decrypted with the other key. —Preceding unsigned comment added by AndrewGarber (talk • contribs) 04:18, 8 May 2011 (UTC)

No. This is wrong. Public keys are either used to encrypt messages or to verify digital signatures, they are never used to encrypt messages. Claiming that signing is the same as encrypting with the public key is incorrect and confusing, because the two processes are clearly distinct for any existing public key cryptosytem. 83.78.156.243 (talk) 05:05, 8 May 2011 (UTC)

I believe the confusion comes from the fact that certain mathematical primitives give rise to both signature and encryption schemes. This isn't always the case. Where it is the case, drawing artificial parallels between the algorithms within these schemes isn't particularly useful. Skippydo (talk) 05:17, 8 May 2011 (UTC)

"Public keys are either used to encrypt messages or to verify digital signatures, they are never used to encrypt messages." <-- did you mean decrypt here?

In the case of digital signatures, the private key is used to encrypt the hash (which I would argue is a message), and the public key is used to decrypt it. 69.165.135.233 (talk) 20:46, 8 May 2011 (UTC)

I too didn't understand the comment by 83.78.156.243. I think the private key is used to decrypt an encrypted message in public key crypto.

DonL (talk) 16:50, 28 July 2011 (UTC)

The comment by 83.78.156.243 is wrong, and does not make sense. A message that's been "signed", is a message that has been encrypted with the sender's PRIVATE key. That is, the "signature" IS the encrypted message. To verify the "signature" is to decrypt that encrypted message with the sender's PUBLIC key.

Basically, I concur with AndrewGarber's comment/suggestion. 173.78.162.217 (talk) 22:22, 14 October 2011 (UTC)

Public/Private Key systems

Can someone explain why these systems are not completely compromised by simply reversing what ever process the 'public' key does to the message;thereby recreating the original plain text. The fact that the 'private' key cannot be determined from the 'public' key would seem to be completely irrelevant, since whatever the program does with the public key to encrypt the message could certainly be undone, using the 'public' key, by a program specifically written to do so. This has always seemed obvious to me and so must occur to others. An explanation of why this isn't (or is) a problem would seem beneficial to me. Danm60 (talk) 17:39, 11 September 2010 (UTC)

Both the introduction to the article and the Weaknesses section addresses just this sort of an issue. It's possible to 'undo' it, but it's also computationally expensive. So expensive that in most circumstances, it's not even worth trying. Through some really, really complex mathematics, you get a function that is easy to perform in one direction, but incredibly hard to perform in the other direction. Gahread (talk) 14:37, 22 September 2010 (UTC)

The same point occurred to me as to Danm60. I think I understand Gahread's reply (in principle!), but I don't think the explanation is at all clear in the existing article. The intro to the article says that 'it is extremely difficult for anyone to figure out the private key based on their knowledge of the public key', but this is not Danm60's (or my) concern. Intuitively, if the encrypted message is made using some algorithmic operation on the 'public' key, then it seems plausible that if one knows the message, the algorithm, and the public key, one can reverse the process and decrypt the message without first finding the 'private' key. I understand from Gahread's reply that this is in practice very difficult because of the nature of the algorithm, but I think the article itself could be clearer about this.109.149.27.90 (talk) 14:00, 6 September 2011 (UTC)

Example?

Given that all of this is difficult by intention, is it at all possible to give worked examples? Maybe by using a quite trivial pair of keys and a trivial trapdoor program? Old_Wombat (talk) 10:12, 5 March 2011 (UTC)

Myths: Leonardo Da Vinci invented public key cryptography

If it is correct that,

"... Leonardo da Vinci who had invented one of the first rudimentary forms of public key encryption centuries ago ...",

D. Brown (2003), "The Da Vinci Code", Doubleday pp. 199. ISBN 0-385-50420-9.

then, this article must cite da Vinci! —Preceding unsigned comment added by 187.56.21.46 (talk) 11:53, 10 March 2011 (UTC)

Just saw the same claim in the novel, and looked it up online, and unsurprisingly, it appears not to be true:

http://boards.straightdope.com/sdmb/showthread.php?t=272184

Let's just look at the whole sentence:

"Sophie's university instructors, while presenting computer encryption methods for securing data, praised modern cryptologists like Zimmermann and Schneier but failed to mention that it was Leonardo who had invented one of the first rudimentary forms of public key encryption centuries ago."

Doh, Schneier and Zimmermann did not invent public key cryptography. Diffie, Hellman, Merkle and Cocks come to my mind. Brown's book is fiction. Hence there is no reason to expect a lot of research and no reason to expect correct statements. 81.62.140.83 (talk) 07:23, 27 September 2011 (UTC)

Electronwill (talk) 06:07, 27 September 2011 (UTC)

Actual Algorithms doesn't have any.

There is a section titled Actual Algorithms - Two Linked Keys, but when going to that section there's yet another description of encryption by means of analogies, and certain nothing resembling an Actual Algorithm. Silas Maxfield (talk) 09:26, 2 February 2012 (UTC)

Inappropriate External Link

Surely given all that is said in this article., the link to

 http://gpg4win.org/documentation.html

is inappropriate. Far more suitable external links readily come to mind.

Please consider an edit to remove that link. G. Robert Shiplett 15:13, 15 June 2011 (UTC)

I understand your point, but gpg4win is an free libre open source(although not waived copyright like CC0 or WTFPL, but I think copyleft) implementation of the Public-key cryptography system. It is relevant in one way or another, but yeah I don't think it belongs in External links. Maybe it belongs in references! Logictheo (talk) 16:14, 20 March 2012 (UTC)