Talk:Public-key cryptography

From Wikipedia, the free encyclopedia

This article is part of WikiProject Cryptography, an attempt to build a comprehensive and detailed guide to cryptography on Wikipedia. If you would like to participate, you can choose to edit the article attached to this page, or visit the project page, where you can join the project and see a list of open tasks.

It is intended that this article be included in WikiReader Cryptography, a WikiReader on the topic of cryptography. Help and comments for improving this article would be especially welcome. A tool for coordinating the editing and review of these articles is the daily article box.

To-do list for Public-key cryptography:	edit · history · watch · refresh
Images

Contents 1 Emminent Issues 2 Combine with Asymmeteric Key Article? 3 Felten's comments 4 Errors 5 Diffie-Hellman key exchange 6 on separate article for hybrid cryptosystems 7 Suggestion regarding vulnerability 8 PGP Question 9 Article Tone / Grammar 10 Use of Private Key to Encrypt Messages 11 Rounding out Weaknesses Section 12 Unclear part in Weaknesses section 13 Public-key diagrams 14 Reading my sent emails? 15 Brute Force 16 Terminology (Key Making Function) 17 Math ? 18 Broken external link 19 Stupid Demands for Citations 20 Reissuing public keys 21 Legality (UK) 22 Problem with padlock exchange analogies in "A postal analogy" section

[edit] 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.

[edit] 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)

[edit] 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)

[edit] 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)

[edit] 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)

[edit] 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)

[edit] 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)

[edit] 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)

[edit] 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)

[edit] 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)

[edit] 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)

[edit] 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)

[edit] 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)

[edit] 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)

[edit] 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)

[edit] 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)

[edit] 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)

[edit] 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)

[edit] 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)

[edit] 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)

[edit] 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^[1].

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^[2] - 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)

[edit] 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)