Standing Up For Academic Freedoms
Standing Up For Academic Freedoms
The people who changed the world …
Introduction
In August 1977, The Stranglers were in the charts with “Something Better Change” and something really was changing, and it something that would change the world forever. This was the month that Martin Gardner, in his Scientific American column, posted a challenge of a method that has stood the test of time: RSA.
It related to the work of R(ivest), A(dleman) and S(hamir) and was a puzzle on their discovery of a method which allowed two keys to be created, where one could encrypt, and the other to decrypt. Their work had been based on a proposal from Whitfield Diffie and Martin Hellman on trapdoor functions that could be used to create the key pair.
In order to explain the RSA concept, Martin’s provided a background the Diffie-Hellman method for which he outlined:
Then in 1975 a new kind of cipher was proposed that radically altered the situation by supplying a new definition of “unbreakable.” a definition that comes from the branch of computer science known as complexity theory. These new ciphers are not absolutely unbreakable in the sense of the one-time pad. but in practice they are unbreakable in a much stronger sense than any cipher previously designed for widespread use. In principle these new ciphers can be broken, but only by computer programs that run for millions of years!
Overall the Diffie-Hellman method has had a good run, but it has struggled in recent years to keep up with the processing power for computers, and the millions of years of running is not quite the case in the modern area, and where the original ciphers could now easily be broken with the simplest of computers within minutes.
With the RSA method, Martin Gardner outlined:
Their work supported by grants from the NSF and the Office of Naval Research. appears in On Digital Signatures and Public-Key Cryptosystems (Technical Memo 82. April. 1977) issued by the Laboratory for Computer Science Massachusetts Institute of Technology 545 Technology Square. Cambridge Mass. 02139.
The memorandum is free to anyone who writes Rivest at the above address enclosing a self-addressed. 9-by-12-inch clasp.
On receipt the requesters eventually (it took over four months in many cases) received a precious piece of history:
It seems unbelievable these days, but the original methods were based on two 63-digital prime numbers that would be multiplied to create a 126-digit value:
Contrast this with the difficulty of finding the two prime factors of a 125- or 126-digit number obtained by multiplying two 63-digit primes. If the best algorithm known and the fastest of today’s computers were used, Rivest estimates that the running time required would be about 40 quadrillion years’
A 256-bit number, at its maximum, generates 78-digits [here]:
115,792,089,237,316,195,423,570,985,008,687,907,853,269,984,665, 640,564,039,457,584,007,913,129,639,936
The 40 quadrillion years has not quite happened, and where 512-bit keys are easily broken in Cloud. If you are interested, here is a 512-bit integer value and which has 148 digits, such as [example]:
13,407,807,929,942,597,099,574,024,998,205,846,127,479,365,820,5 92,393,377,723,561,443,721,764,030,073,546,976,801,874,298,166,9 03,427,690,031,858,186,486,050,853,753,882,811,946,569,946,433,6 49,006,084,096
The search for prime numbers, too, has been progressive since 1977, and by 2014, the world discovered a 17,425,170-digit prime number. The finding of prime numbers make the finding of them in the RSA method must easier.
So the RSA method has been under attack for years, from both discovering prime numbers and also in factorizing. Along with this computing power has increased massively. If think that 40 years that have passed, and take a quick assumption that computing power doubles every year then we get:
1977 4 Quadrillion Years (4,000,000,000,000,000)
1978 2 Quadrillion Year
1979 1 Quadrillion Year
...
2015 3,637 years
2016 1,818 years
2017 909 years
2018 454 years
and if we get an NVIDIA card with 4,000 processors, we take it to less than a year, and we get of few of them today into a cluster, and we crack it within one day! The FREAK vulnerability was actually caused by the limiting of RSA keys, due to US Export controls, to 512-bits [view].
The factorising of prime numbers too has generated methods which can quickly find the prime number factors [here].
The Tension of Crypto and Academic Freedom
Once Martin had published the article, the requests for the article came rushing in, especially as the paper had not yet appeared in the Communication of the ACM. Initially there were 4,000 requests for the paper (which rose to 7,000), and it took until December 1977 for them to be posted.
Why did it take so long to get the paper published and also to send them out?
Well the RSA method caused significant problems within the US defence agencies. This was highlighted in a letter sent from J.A.Meyer to the IEEE Information Theory Group on a viewpoint that cryptography could be violating the 1954 Munitions Control Act, the Arms Export Control Act, and the International Traffic in Arms Regulations (ITAR), and could thus be viewed equivalent to nuclear weapons. In even went on to say that:
Atomic weapons and cryptography are also covered by special secrecy laws
The main focus of the letter was that any work related to cryptography would have to be cleared by the NSA before publication. In fact, the letter itself had been written by Joseph A Meyer, an employee of the NSA.
Joseph had already been embroiled in controversy with a proposal to fit a tracking device to the 20 million US citizens who had been associated with crime. The tag would then be used to monitor the location of the “subscriber”, and to detect when they broke a curfew or committed a crime. In this modern era of GPS tracking of everyone’s phones, Joseph’s dream has actually become a reality, but now everyone is monitored.
The RSA team thus had a major dilemma, as many of the requests for the paper come from outside the US. Martin Hellman, who was a co-author of the Diffie-Hellman method, had already had problems with ITAR, and even decided to present a paper himself in 1977 at Cornell University rather than the practice of letting his PhD students present the work.
His thinking was that the court case would be lengthy, and that it would damage his PhD student’s studies (Ralph Merkle and Steve Pohlig), and so he stood up for academic freedoms. Initially the students wanted to present their work, but their families did not think it a good idea. Eventually though, Ralph and Steve stood beside Hellman on the stage to present the paper, but did not utter a word.
With this stance the cryptographers held ground, and hoped that a stated exemption on published work within ITAR would see them through. The worry, though, did delay the paper being published, and for the posting of the article. In reply to Meyer’s letter, the IEEE stood its ground on their publications being free of export licence controls, with the burden of permissions placed on the authors:
and then additional response from the IEEE say them put in place safeguards for the publishing of material which did not have the correct level of permission:
The scope of the impact of RSA was perhaps not quite known at the time with Len Adleman stating:
I thought this would be the least important paper my name would ever appear on
In fact, Adleman has said that he did not want his name on the paper, as he had done little work on it, but he did insist that his name went last. Often papers, too, have an alphabet order, and if so the method could have been known as the ARS method … not the kind of thing that you would want to say to audiences on a regular basis.
As another contribution, Ron Rivest came up with the concept of Bob and Alice, and for Bruce Schneier to then introduce the concept of Eve (the intruder), Trend (the trusted agent) and Mallory (the active attacker).
Conclusions
Doesn’t 1977 feel like 2018? The problems that the RSA team faced in 1977 are all coming back, as Governments rain-in against the evils of cryptography.
And for the forty Quadrillion years, well it’s now a day or less. The initial foundations of cryptography are still strong, but the require quite a bit of maintenance.
Finally … how many PhD supervisors would stand up for the rights of academic freedoms, in order that their students did not go to prison?
And how many academic would insist that their name would go last on a high-impact paper?
If you are interested, here is an RSA problem generator: