70
$\begingroup$

I became interested in crypto lately and read about symmetric and public key crypto algorithms. I understand how crucial the discoveries of the 1970s like RSA, DES and DH were in advancing the technology.

I just don't understand how public key cryptography as an idea just came less than 50 years ago while it was a highly desired solution throughout history and kingdoms/countries/intelligence services would pay handsomely to whoever discover this simple yet revolutionary idea.

Things like integer factorization and elliptic curves were studied since the 19th century, how come nobody thought of using such known mathematical problems to create strong crypto systems, especially in WW1 and WW2 where confidentiality and integrity of data could decide the fate of a whole nation, instead of relying on centuries-old futile crypto techniques?

I am sure that this wasn't a lack of human resources, every European country had lots of geniuses, so why wasn't public key cryptography discovered until so late?

$\endgroup$
  • 4
    $\begingroup$ Some useful inks there explaining the (covert) discovery of Public key cryptography. $\endgroup$ – fgrieu May 25 '18 at 9:35
  • 6
    $\begingroup$ If I recall correctly, in "The Cuckoo's Egg" it is claimed that an unnamed British employee in the security system discovered RSA shortly after WWII but was not allowed to publish it. Without digital computers this is not practically interesting. $\endgroup$ – Ross Millikan May 28 '18 at 4:33
  • $\begingroup$ Isn't public key cryptography crudely analogous to sending out padlocks and strongboxes to generals in the field, with the king having the only key? Not secure if the enemy gains physical access, but it would keep prying eyes away from sensitive material. The basic concept seems at least somewhat useful beyond mathematical implementations. $\endgroup$ – jdk1.0 May 29 '18 at 19:54
104
$\begingroup$

If you read about Merkle's experience with bringing the subject to the mainstream, you might be surprised. His professor rejected his initial proposal and show little interest in any further developments:

...We were required to submit two project proposals, one of which we would complete for the course. I submitted a proposal for what would eventually become known as Public Key Cryptography -- which Hoffman rejected. I dropped the course, but kept working on the idea.

He showed it to a different faculty member and was encouraged to publish it. His proposal to the Communications of the ACM was rejected:

... I showed an early draft to Bob Fabry, then on the faculty at Berkeley, who immediately recognized it as both novel and valuable and said "Publish it, win fame and fortune!" I then submitted it to Susan Graham, then an Editor at the Communications of the ACM in August of 1975. As I was to learn, Fabry's response was rare.

Graham sent my submitted paper out for review and received the following response from an "experienced cryptography expert" whose identity is unknown to this day:

"I am sorry to have to inform you that the paper is not in the main stream of present cryptography thinking and I would not recommend that it be published in the Communications of the ACM."

"Experience shows that it is extremely dangerous to transmit key information in the clear."

With this blanket rejection of public key cryptography by an "expert", she rejected my article. She "was particularly bothered by the fact that there are no references to the literature. Has anyone else ever investigated this approach. If they consider it and reject it, why?"

Novel concepts that aren't "mainstream" can be difficult to accept:

I had failed to provide any references to the prior work on public key cryptography, and the reasons previous workers in the field had rejected it as impossible. I should have looked up "public key cryptography" on Google before submitting my paper. My defense is feeble: there was no Google, the term "public key cryptography" did not yet exist, and there were no previous workers in the field. There were no words for what I had done, and looking up a concept to show that no one had previously thought of it is difficult. This is not a unique problem: it illustrates a problem faced by anyone trying to explain a new idea to an "expert" who expects a properly referenced article anytime anyone tries to explain something to them. The more a new idea is unrelated to any prior idea or concept the more it must appear as a squawling bastard, naked and alone, appearing de novo and lacking any respectable pedigree or family to vouch for its acceptability.

... CACM eventually published the paper, though only after almost three years of delay, and only after others (who were better able to persuade their editors to publish in a timely fashion).

Conclusion

While the utility of public-key cryptography is obvious to us, this was not always the case. Encryption that is secure when you know the key almost sounds like something that can't exist because it would be too good to be true. So you can certainly forgive people for not pursuing the idea seriously.

$\endgroup$
  • 34
    $\begingroup$ Yes, we sometimes forget how weird the idea of 'here's a key that we can make public' would sound before PKC... $\endgroup$ – poncho May 25 '18 at 14:52
  • 9
    $\begingroup$ That early version of Merkle's CS244 proposal is a must read, if only for the visionary and clear statement of his goals, and his Method 1. I did not knew it, and it makes perfect sense as a proof of concept that the goals are not pipedream. I won't be the first to throw a stone at the professor who rejected Method 2, and ultimately the project, though; notably, Method 1 required too much communication for the times, and in the absence of something credible, it can at least understand the rejection. $\endgroup$ – fgrieu May 25 '18 at 15:29
  • 32
    $\begingroup$ I think there's a lesson here about terminology and impression management: The very word "key" was used consistently in the art to refer to secret part. If he had just called them "key" and "[not key]" instead of "private key" and "public key" respectively, I think the result would've been much better. A really hard lesson I've learned is that you should never ever trust another human to actually carefully grok your idea when they can instead skim and your words provide opportunities to slip into half-misunderstandings.... $\endgroup$ – mtraceur May 25 '18 at 18:56
  • 12
    $\begingroup$ @poncho, PKC's been around for decades, and we still get people over on Security.SE asking what the best way to protect the public key is. $\endgroup$ – Mark May 25 '18 at 23:34
  • 4
    $\begingroup$ I'm not sure how exactly the timing works but the fact that he got rejected (at least by the reviewer) might have been influenced by the earlier or contemporaneous discovery and classification of the idea in the UK and US. $\endgroup$ – DRF May 26 '18 at 7:11
33
$\begingroup$

I guess the discovery of public key crypto was not earlier due to three combined factors:

  • before (digital) computers, public key cryptography was impossible difficult to implement, and things that can't be implemented are rarely discovered, much less get any traction;
  • before the 1970's, serious crypto was a military thing, and entrenched habits change slowly in this environment;
  • before the 1970's, access to computers by civilians academics and mathematicians was rather restricted by economic reasons.
$\endgroup$
  • 17
    $\begingroup$ Additionally there wasn't a serious need for the military to have PK-crypto, given that they do have trusted couriers (eg officers) and the means to guarantee the physical security of the transport. $\endgroup$ – SEJPM May 25 '18 at 10:29
  • 2
    $\begingroup$ Thanks! I pretty much agree with all the points, but I have 2 points here: 1. cryptography itself was desired and implemented since antiquity, there were implemented crypto systems even before their math were discovered. That's understandable because secrecy was a very old problem. 2. crypto looked like it was a primitive CS branch compared to other branches (computer arithmetic (e.g. there were floating point units invented before ww2), computer architecture (there were even decimal based computers in the 1940s), many important algorithms were dated back to the 1950s). $\endgroup$ – pls no May 25 '18 at 11:08
  • 1
    $\begingroup$ "before (digital) computers, public key cryptography was impossible to implement" -- Was it? I suspect that it was within the realm of possibility using state-of-the-art mechanical calculators from the 1930s (perhaps modified to handle larger numbers). They couldn't have handled very large numbers, but then neither could an attacker. The product of two primes in the trillions might have been impossible for an attacker with 1930s tech to factor but small enough for 1930s calculators to work with via exponentiation by squaring. The lack of need that @SEJPM mentions is more telling. $\endgroup$ – John Coleman May 25 '18 at 22:57
  • 5
    $\begingroup$ The concept of "keys" for communication may have relied upon confidentiality, but the value of being able to publicize the means of authenticating something without publicizing the means of forging it should be apparent even to an agency with trusted couriers. $\endgroup$ – supercat May 26 '18 at 18:00
  • 2
    $\begingroup$ @James_pic Given the famous anecdote about the factorization of 2^67 - 1, I find it implausible that there were no exploitable mathematical asymmetries prior to electronic computers. It would take someone who knows more than I do about the capabilities of 1930's computational tools to answer the question definitively. $\endgroup$ – John Coleman May 29 '18 at 13:30
12
$\begingroup$

I find the introduction to Hellman's 1979 Scientific American article titled "The Mathematics of Public-Key Cryptography" to be illuminating.

According to the very authoritative Hellman, public key cryptography became really interesting when demand for cryptography arose outside of governments and the military.

Particularly, asymmetric cryptography answered a demand of multiple, private/commercial subjects to securely transmit information to peers over large public, insecure telecommunication networks in a cost-effective manner.

Hellman also saw the uses of asymmetric cryptography for protection against spoofing, tampering and repudiation which would have benefited this sort of users.

Until quite recently the principal us­ers of cryptosystems were the military and diplomatic services of the world.

The drawbacks of the conventional sys­tems are particularly troubling, how­ ever, to the new commercial users of cryptography. To begin with, before any information can be enciphered and transmitted over an insecure channel the receiver and the sender must agree on a key.

Since the security of the system de­pends exclusively on the secrecy of the key, the key must be transmitted by means of a secure channel such as a trusted courier, a system that is slow and costly. The distribution of keys is a par­ticular problem in those instances when the individuals seeking privacy have had no prior communication or when pri­vacy must be maintained over a large network, two situations that are often encountered in commercial dealings. Indeed, the cost and inconvenience of relying on couriers to distribute the amount of key information that is need­ed for any broad application of cryptog­raphy are virtually prohibitive.

The requirement of key distribution is not the only drawback of the conven­tional cryptosystems currently in serv­ice. They also fail to meet fully the re­quirements of message authentication. Since a single key is shared between the sender and the receiver, there is nothing to prevent the receiver from sending himself messages that appear to come from the sender. Consider the diffi­culties such forgeries could cause in electronic mail or electronic banking systems. Conventional cryptosystems, then, cannot offer the same insurance against disputes over what message (if any) was sent that the exchange of signed documents can.

The public-key systems, however, provide answers to both the problem of distributing keys and the problem of authentication.

$\endgroup$
10
$\begingroup$

It was discovered earlier, contrary to widespread belief. GCHQ already developed the public-key cryptography scheme in 1973 by Clifford Cocks [1], based on James H. Ellis already preconceived theory of non-secret encryption in his paper in 1968 [2]; research had already taken place into this beforehand within the agency.

$\endgroup$
  • 12
    $\begingroup$ 1968 is exactly 50 years ago now. I understand the question to be about the preceding two millennia since the development of the Caesar cipher. $\endgroup$ – Squeamish Ossifrage May 26 '18 at 23:05
  • 5
    $\begingroup$ @SqueamishOssifrage, yet the accepted answer is all about how it was delayed in the publishing of a paper. $\endgroup$ – Prof. Falken May 28 '18 at 6:38
  • 1
    $\begingroup$ For more bibliography, see that question. $\endgroup$ – fgrieu May 28 '18 at 17:34
2
$\begingroup$

Temporarily setting aside public key crypto specifically, I want to expand on a tangent from @fgrieu's answer.

Frankly, before digital computers the need and use for what we now consider strong encryption was minimal. Asymmetric encryption is particularly vulnerable but not alone in this regard.

Functionally, breaking crypto is about effective keyspace. To put that in to practice there are three steps:

  1. Determine the method used. One of the desired properties of an encryption scheme is signature reduction. It goes without saying that you want to avoid cryptographic weaknesses that leave artifacts in the cipher, but going further than that you also want to avoid leaving leaving indication of what cipher was used in the first place.

    A perfect cipher would be indistinguishable from random noise for anyone not in possession of the full decryption settings, or to put it another way, the only way to validate a cipher's integrity is to decrypt it. If you can't tell which of 10 ciphers I used then I've multiplied the work you need to do to break it by 10.

  2. Identify the weakest points. No cipher should be assumed perfect, at best we can say there are no known attacks. Trying to find attacks on the cipher itself is an important part of cryptanalysis, both from the desire to break the cipher and for proving its strength.

    Equally, people's application cryptography can't be assumed perfect. People tend to be dumb about these things. The more human involvement there is in the process, the more chance they'll mess something up and make your life easier by weakening things.

  3. Compute through whatever keyspace is left. Unless you get really lucky, chances are you've still got more than 1 permutation left to try. So you'll need to try decryption with each permutation left in your keyspace. Maybe you'll find an working set of inputs after 1%, maybe it'll be at 99%.

So here's the thing. You don't need an especially large keyspace when the computers are people with paper, that's why combination locks (kinda) work.

From the actual key perspective, a 3 digit combination has a keyspace of 1000 combinations. From my experience with a particular type of 3 wheel combination lock I figure about 20-30 minutes on average to get the code purely by exhaustive search. Finding a good weakness or mechanical speed up will reduce the effort needed by at least an order of magnitude and often far more.

Even as recently as WW2, Enigma was sufficient. Actually, properly used Enigma is still hard to crack. Ciphers that require fast computers to use effectively aren't practical without said computers. Ciphers based on mechanical implementations that are hard to optimise mathematically or computationally, those are the ones we wanted for a long time.

So, why are asymmetric ciphers particularly vulnerable? Well it depends on what your goal in choosing it is.

In one case, asymmetric encryption is good for adding an authenticating factor to the message. With symmetric encryption possessing the key means you can forge the messages as well as intercept them. If you're using an asymmetric scheme you can only impersonate or receive the key you have. Yeah, this does work but you can achieve the same thing in other ways without the drawbacks of using 1:1 messaging schemes when broadcasting information.

In the other case, the public part of public key refers to using the ability to publish the key to enable a more secure exchange of another (usually symmetric) key. Exactly how and what is exchanged in the process varies. The issue is that most of the benefit requires real time communication and extra work and using separate mechanisms for the sending and receiving portion.

A modern analogy for using PKI for the first purpose is PGP and its family, where asymmetric encryption and PKI is used both for authentication and securing messages. You can maybe follow why it's less effective by considering a mailing list where everyone is sending PGP encrypted messages.

The second purpose, is what most people think of when talking about Public Key encryption... it's what makes HTTPS and SSH work. Imagine if, every time you wanted to make a phone call, you had to read out a 10 digit number, write one down, punch the new one in to the phone, and then hope you can both understand each other.

The biggest problem with PKI specifically, going back to the three stages I talked about above, is that to effectively perform stage 3 you ideally need to have done stage 2, and to do stage 2 effectively you need to have done stage 1. PKI, by nature and design, publishes not only part of the cipher settings but what cipher you're actually using. With computers in the picture you can compensate for exposing that information by just making the key space many many orders of magnitude larger. Still, if you can, it's always preferable to reduce how much you information you reveal to an adversary.

So, given the issues, and the fact that it only really becomes useful with the advent of trust infrastructure, electronic computation, fast high quality telecommunication and key exchange algorithms... it's actually not surprising that it didn't become notable earlier, evidenced by the difficulties mentioned in the answer from @ella-rose.

$\endgroup$
  • 3
    $\begingroup$ What made public-key cryptography revolutionary from an authentication standpoint was not so much it the existence of means by which some people could authenticate themselves without the authentication instructions facilitating forgery, but rather the development of a system for producing such means without reliance upon personal skill. If someone who claims to be a famous violinist is given a violin and asked to play it, and they perform just like the violinist they claim to be, odds are they are who they claim. But many people have no such skill that would uniquely identify them. $\endgroup$ – supercat May 27 '18 at 18:16
  • 2
    $\begingroup$ @supercat I might be able to persuade some people that I can play very avantgarde contemporary music on the violin and have transcended all of classics ... $\endgroup$ – Hagen von Eitzen May 27 '18 at 20:27
  • $\begingroup$ @supercat true, PKC does facilitate many such systems, but I'd say that it is fundementally a lock for which there can be a key that is capable of either locking or unlocking but not both. The value is that it can be applied to problems in a fairly generic way. $\endgroup$ – Kaithar May 30 '18 at 15:53
  • 1
    $\begingroup$ @Kaithar: Perhaps "personal skill" wasn't the right term. Even in antiquity, there was a recognized need to prove that something which claims to be a message, order, proclamation, etc. from someone was, in fact, issued by that person. A sufficiently ornate signet ring might prove that a message was issued with someone with either sufficient skill to produce such a ring or, more likely, of sufficient means to have such a ring produced, but my key point is the production of a means of authentication something would be difficult and/or expensive even for the person legitimately using it. $\endgroup$ – supercat May 30 '18 at 16:37
  • $\begingroup$ @supercat as noted in another answer, asymmetric really needs electronics so it wouldn't be helpful in antiquity. On the other hand, authentication via a stamp or seal is alive an well today over in Japan where they can use personal seals in place of signatures on most documents.. handmade seals are extremely hard to forge due to the scratches on the surface. $\endgroup$ – Kaithar Jun 4 '18 at 17:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.