The Bell scientist suggested that the person receiving the message simply add noise to the line. When the message arrives, message and noise are intermingled and eavesdroppers will hear only garbage. The recipient, knowing precisely how the noise was added, can subtract it from the transmission and wind up with the original, unscrambled message.
For modern cryptography, Project C43 was useless. For one thing, it was an analog model, and by the late '60s the world was going digital. But Ellis found it exciting nevertheless: The sender of a message didn't have to worry about an enemy listening in, even if the foe knew how the system worked.
What made this possible was that, in contrast to conventional cryptography, the recipient is a collaborator in the encryption. That raised a tantalizing question for Ellis: Could a secure, digitally encrypted message be sent without keys being exchanged in advance?
This heretical idea popped into his head one night after he had gone to bed. Sitting in the dark in his Cheltenham bedroom, he decided it could, and he came up with an existence proof for the question. His name for it would embody the contradiction: nonsecret encryption. It worked by taking the digitized, nonsecret exchange between two parties - call them Alice and Bob - and submitting it to a series of three mathematical alterations.
Let's say, for instance, that Bob wants to send a message to Alice. The problem is Eve, an unwelcome snoop who is familiar with the way this particular scrambling system works, down to the mathematical formulas themselves - since these rules are, in this scenario, public knowledge.
Alice gets the ball rolling by generating a large number chosen at random. This, in effect, is a secret key that only she holds. Now comes a crucial act suggested to Ellis by Project C Alice, who is the intended recipient, actually initiates the scrambling process by executing a mathematical operation to transform the key to a new number. She sends the new number to Bob. The new number is analogous to what we know as a public key.
Since an important property of the mathematical operation Alice uses is that it cannot be calculated in reverse, even by an outside observer who has this second, nonsecret number, and also knows what function produced it, cannot do an inverse calculation to retrieve the first, secret number.
This is something that will remain known only to the recipient, Alice. Now that Bob has this nonsecret number, he uses a second operation to scramble the private message he has for Alice, which he then sends. With a third mathematical function, Alice uses her original, secret key to essentially strip the encryption from the message. She can now read the plain text, and Eve can do nothing but gnash her teeth as she watches a very public exchange of what, to her, will remain gibberish.
The nonsecret key acts like the line noise in Project C Since such keys wouldn't have to be protected, it would be possible to have secure communications without all the prior arrangements necessary in conventional crypto, opening the way for protected communications on a vast scale.
Ellis hadn't been assigned to unleash a revolution in cryptography, but the possibility that he had done so had to be dealt with. The very basis of the idea - its "nonsecret" element - seemed so heretical that, to some at the GCHQ, disproving his thesis would be striking a blow for the natural order of things. Just before Christmas, he delivered his judgment: "Unfortunately, I can't see anything wrong with this.
However, the mathematician noted, Ellis had presented only a proof that such a system could exist. The unknown remained: Was there really a way of generating a nonsecret key from the original private key?
To make it work, you needed to be certain that the Eves of the world could not reverse the first mathematical process and get their hands on the key. Ellis had conjectured a set of lookup tables that would perform the various scrambling and descrambling calculations but had not developed the specific functions.
Until they were formulated, nonsecret encryption would be nothing more than a theoretical curiosity. Ellis did not hide this state of affairs when he formally wrote up his idea in a January internal paper called "The Possibility of Secure Non-Secret Digital Encryption.
The remaining step in the creation of a secure, nonsecret key was not trivial. Even as he set about the search for the nonreversible functions that would make his scheme work, Ellis, an engineer by training, was concerned that his mathematics skills were not up to the task.
And despite the possible importance of a nonsecret system, the GCHQ did not assign much brainpower to aid him in the quest.
At times over the next few years, some Communications-Electronics Security Group cryptographers would read Ellis's paper and work for a while on potential solutions, and in a new chief scientist took an interest and assigned some people to the problem.
But while those looking for the mystery functions developed ideas about what the characteristics of such things might be, they had no luck in actually finding one that worked. In , Cocks was a recent arrival in the electronics-security group. He had come to intelligence work from Kings College, Cambridge, where he earned an undergraduate degree in math, and Oxford, where he did graduate work in number theory before deciding to move on.
Although Cocks didn't know much about the GCHQ and really hadn't thought about cryptography as a focus of his work, he knew the agency needed mathematicians. Also, a childhood friend, Malcolm Williamson, was already there. In September of that year, at age 22, Cocks went to work in Cheltenham.
When people arrived at the GCHQ, they were assigned a mentor "to teach you the ropes and tell you what you needed to know," Cocks recalled in a recent lecture. His was Nick Patterson, another Cambridge alumnus. That allowed him to consider the problem without preconceptions.
Since he had done his research the previous year in number theory - working with large primes and multiplication - it made sense to him to use that knowledge.
After work he walked back to the modest house he rented in Cheltenham with Williamson, ate dinner, and sat down to think. Because of the secrecy imposed by the GCHQ, he had certain limitations: He could not bring anything home from his office, and if he pondered a work-related problem "in digs," he was not permitted to write anything down. The only medium he had was his brain. His idea was more than fine - it was elegant. Cocks is pointing to a basic mathematical truth: The product of two large prime numbers is extremely difficult to factor - that is, to reverse to obtain the original primes.
He figured that the secret key in his implementation would be two huge primes, generated by a message recipient. The primes would be multiplied, and the product would be the nonsecret key, the number given openly to a sender who could, if need be, also get the number from a public directory. Cocks then figured out a simple mathematical formula that would allow the sender to encrypt a message in such a way that it could be decrypted only by someone who knows the original primes.
After mapping it out in his head, he went to sleep. Cocks, in one evening, had achieved a breakthrough that several years later would be repeated - in the form of the revolutionary RSA algorithm - after months of intensive trial and error by MIT researchers Ron Rivest, Adi Shamir, and Len Adleman. Malcolm Williamson worried that such a "simple" scheme was vulnerable to attack.
Word got around the electronics-security group that someone had found a way to implement James Ellis's idea. Cocks mentioned to his friend Malcolm Williamson that he had an internal paper coming out. This was a one-up move; it was unusual for a recruit to circulate a paper so soon.
Cocks's announcement got Williamson's attention; he listened closely as Cocks explained the problem and his solution. Williamson had known Cocks since they were both 12 - they had attended the same grammar school in Manchester, and they had both gone to Cambridge.
Williamson had done graduate work at Liverpool University, then one day saw an ad, posted by the GCHQ, calling for mathematicians. Without knowing much about the agency, he had applied - and soon found himself working on cryptographic problems.
Williamson had not heard of the Ellis problem before, but it struck him as rather unreasonable. How could you do cryptography when you passed the key in the open? So he set about to shoot down the concept, but he couldn't. But in the process, Williamson began considering ways that two collaborating parties could pass numbers back and forth to build a shared key that would be secure even if an eavesdropper was monitoring every bit of the exchange.
It was very late when he got it - 8 or 12 hours after he sat down to think. His scheme involved a complex set of exchanges in which each party picks a random number, performs a calculation on it by a difficult-to-reverse formula, and arrives at a shared key.
It's indicative of the project's relative unimportance at the GCHQ that Williamson didn't write up his work for a couple of months. Not long after he did, and after some conversations with Ellis, he came up with an idea that streamlined his concept.
It was precisely the same formulation for what would later be known as the Diffie-Hellman algorithm. As far as Williamson is concerned, though, it was pretty much a consequence of his first paper, so obvious that he felt in no hurry to circulate it.
But just as the agency had been suspicious of the initial idea, it moved ultracautiously with Cocks's and Williamson's schemes. Ironically, one factor weighing against accepting the solutions was their sheer straightforwardness. So we're pretty comfortable that people are not going to be able to break those things, because even if you hack away at it, you're not going to suddenly find a little magic screw there that, if you unscrew it, everything falls to pieces.
But in all this stuff with public key, there absolutely may be a magic screw. Some graduate-student mathematician could really cause a disaster. So concerned was the GCHQ with this possibility that it not only looked at the schemes internally - finding no inherent flaws - but also took the unusual step in of going to a renowned outsider, Professor R.
Churchhouse of the University of Wales, presenting him with the mathematical foundation of Cocks's idea, and asking whether it was secure. Churchhouse concluded that as long as no one figured out a fast way of factoring huge primes - something that no mathematician had ever come close to - the scheme was sound. The agency ultimately determined that between the two methods, Williamson's was preferable because its functions were easier to work with than the huge numbers Cocks's scheme required.
Even so, the system was judged to be impractical. We looked at the circumstances under which you would find it useful to have a machine that took that long to produce keys and immediately thought the applications were too limited to make it worth floating. So the GCHQ's thinking had advanced from judging nonsecret encryption to be impossible to finding it overly cumbersome.
Many people in the agency also remained concerned that such a radically new kind of cryptography might have weaknesses too subtle to detect, weaknesses that an enemy might use to crack the system.
Cocks's breakthrough was repeated, years later, after months of intensive effort at MIT. Even Williamson believed that the whole venture was too risky. When he finally wrote up a revised version of his key scheme, he cited these reservations as the reason for the two-year delay. The trouble is that I have no proof that the method The largest number yet factored is digits long.
It took computers, most of them fast workstations, more than seven months. Note something odd. It is easy to multiply primes together.
But there is no easy way to take the product and reduce it back to its original primes. In crypto jargon, this is a "trapdoor"—a function that lets you go one way easily, but not the other. Such one-way functions, of which this is perhaps the simplest example, are at the bottom of all public-key encryption.
They make asymmetric ciphers possible. To use RSA encryption, Alice first secretly chooses two prime numbers, p and q , each more than a hundred digits long. This is easier than it may sound: there are an infinite supply of prime numbers. Last year a Canadian college student found the biggest known prime: 2 It has 4,, digits; typed without commas in standard point type, the number would be more than ten miles long. Fortunately Alice doesn't need one nearly that big.
She runs a program that randomly selects two prime numbers for her and then she multiplies them by each other, producing p x q , a still bigger number that is, naturally, not prime.
This is Alice's "public key. As the name suggests, public keys are not secret; indeed, the Alices of this world often post them on the Internet or attach them to the bottom of their e-mail. When Bob wants to send Alice a secret message, he first converts the text of the message into a number.
Perhaps, as before, he transforms "attack" into "5 5 15 Note here that Bob does not use his key to send Alice a message, as in regular encryption. Instead, he uses Alice's key. Having found Alice's public key, he plugs it into a special algorithm invented by Rivest, Shamir, and Adleman to encrypt the message. At this point the three mathematicians' cleverness becomes evident. Bob knows the product p x q, because Alice has displayed it on her Web site.
But he almost certainly does not know p and q themselves, because they are its only factors, and factoring large numbers is effectively impossible. Yet the algorithm is constructed in such a way that to decipher the message the recipient must know both p and q individually. Because only Alice knows p and q, Bob can send secret messages to Alice without ever having to swap keys. Anyone else who wants to read the message will somehow have to factor p x q. How hard is that? Even if a team of demented government agents spent a trillion dollars on custom computers that do nothing but try random numbers, the Sun would likely go nova before they succeeded.
In the real world, public-key encryption is practically never used to encrypt actual messages. The reason is that it requires so much computation—even on computers, public-key is very slow. According to a widely cited estimate by Schneier, public-key crypto is about a thousand times slower than conventional cryptography. As a result, public-key cryptography is more often used as a solution to the key-management problem, rather than as direct cryptography.
People employ public-key to distribute regular, symmetric keys, which are then used to encrypt and decrypt actual messages. In other words, Alice and Bob send each other their public keys. Alice generates a symmetric key that she will only use for a short time usually, in the trade, called a session key , encrypts it with Bob's public key, and sends it to Bob, who decrypts it with his private key. Now that Alice and Bob both have the session key, they can exchange messages. When Alice wants to begin a new round of messages, she creates another session key.
Systems that use both symmetric and public-key cryptography are called hybrid, and almost every available public-key system, such as PGP, is a hybrid. Solving the key problem, one should note, didn't make encryption easy for novices—it made encryption easier for experts. In a Carnegie Mellon doctoral student named Alma Whitten asked twelve experienced computer users to send and receive five encrypted e-mail messages apiece with PGP.
One couldn't manage it at all; three accidentally sent unencrypted messages; seven created them with the wrong key; two had so much difficulty with the other tasks that they never bothered to send out the public, encrypting half of their keys; two who received properly encrypted messages tried to decrypt their decryption key, rather than the messages. Whitten called her report, cowritten with J. Indeed, as mentioned in the profile, Johnny not only can't encrypt, he doesn't encrypt.
Fascinating as a mathematical exercise, public-key encryption has yet to make much difference in people's lives. Skip to content Site Navigation The Atlantic.
Popular Latest. The Atlantic Crossword.
0コメント