A matter of shy osprey. RSA Algorithm
I think this story will be interesting to many, including people not related to mathematics.
In 1976, Whitfield Diffie and Martin Hellman published their article, New Trends in Cryptography, with revolutionary ideas for public-key encryption. And then, three scientists Ronald Ryvest , Adi Shamir and Leonard Adleman in August 1977 published an article in the journal Scientific American , where they described in detail their algorithm using calculations in the ring of integers. As many people know, the idea of the algorithm is the existence of a conditionally one-sided function - ordinary multiplication by a set of prime numbers of large length
(f: P x P -> P * P ), which is computationally difficult to reverse. In other words, knowing n = p * q (where p and q are primes), finding p and q (or factoring the number n) for large n seems to be a demanding task.
In the same issue, a well-known mathematician and scientist Martin Gardner, by agreement of the authors of the algorithm, published a mathematical problem called RSA-129. In it, he wrote a pair of numbers (n, e) - a public key, where the length of the number n was 129 decimal places, and e was equal to 1007, and the encrypted message itself. He promised the decryptor of the message a reward of $ 100, which he put into the bank at 2% per annum. According to analysts, decomposing such a huge number into factors with the existing factorization algorithms and the power of those computers would require 20,000 years of continuous operation (Ron Rivest assumed 40 quadrillennes for a number of 125 characters). But the situation changed ...
Then, in 1994, the young cryptographer of the American army Arjen Lenstra developed an improvement of the Quadratic Sieve algorithm , which allows finding reasonable factors of up to 130 digits in a reasonable time. The asymptotic behavior of the algorithm was O (esqrt (log n * log log n) ), where e is the base of the natural logarithm. By the way, the asymptotics of the trivial factorization algorithmO (sqrt (n)) that, longer for large n. Lenstra himself did not possess the necessary computing power, and then he suggested that volunteers allocate part of their processor time via the Internet for the benefit of mathematics. It was one of the first in the history of large projects using distributed computing. 600 people joined in solving the problem, providing 1,600 computers: in addition to the most ordinary computers, 3 supercomputers took part and, according to the Russian-language Wikipedia, 2 fax machines :-). As a result, a final matrix of size 20,000 by 20,000 was formed, filled with ones and zeros. Further, the meteorological supercomputer, allocated to Lenstre himself, entered the business, who, after 220 days of continuous operation, factorized 129 a significant number n.
The answer turned out to be:
The lengths of the numbers p and q turned out to be 64 and 65 characters, respectively. The phrase encrypted by Martin Gardner was: " The Magic Words are Squeamish Ossifrage ", which translates as " Magic words are Shy Osprey ", or, according to the Russian Wikipedia, " Magic words are squeamish lamb ." After that, the recommended key length was increased to 140 characters until after 4 years the check number of 140 digits was laid out. In 1998, Bill Gates announced that he provided unlimited funding and computing resources to his company to decompose a number of 200 characters. At the moment, this goal has already been achieved in 2005, the RSA-200 task. Of the $ 100, it’s not difficult to calculate, the interest for 17 years turned out to be approximately $ 140, which were transferred to the free software fund :-)
This whole story was an excellent PR move for the authors of the algorithm and the founders of the company that patented RSA, and received in The result is a $ 900 million profit.
That's what it means to make money wisely;)
Source: Professor Saliy Vyacheslav Nikolaevich, SSU.
I apologize in advance for inaccuracies.
Thank you all for the corrections in the comments!
In 1976, Whitfield Diffie and Martin Hellman published their article, New Trends in Cryptography, with revolutionary ideas for public-key encryption. And then, three scientists Ronald Ryvest , Adi Shamir and Leonard Adleman in August 1977 published an article in the journal Scientific American , where they described in detail their algorithm using calculations in the ring of integers. As many people know, the idea of the algorithm is the existence of a conditionally one-sided function - ordinary multiplication by a set of prime numbers of large length
(f: P x P -> P * P ), which is computationally difficult to reverse. In other words, knowing n = p * q (where p and q are primes), finding p and q (or factoring the number n) for large n seems to be a demanding task.
In the same issue, a well-known mathematician and scientist Martin Gardner, by agreement of the authors of the algorithm, published a mathematical problem called RSA-129. In it, he wrote a pair of numbers (n, e) - a public key, where the length of the number n was 129 decimal places, and e was equal to 1007, and the encrypted message itself. He promised the decryptor of the message a reward of $ 100, which he put into the bank at 2% per annum. According to analysts, decomposing such a huge number into factors with the existing factorization algorithms and the power of those computers would require 20,000 years of continuous operation (Ron Rivest assumed 40 quadrillennes for a number of 125 characters). But the situation changed ...
Then, in 1994, the young cryptographer of the American army Arjen Lenstra developed an improvement of the Quadratic Sieve algorithm , which allows finding reasonable factors of up to 130 digits in a reasonable time. The asymptotic behavior of the algorithm was O (esqrt (log n * log log n) ), where e is the base of the natural logarithm. By the way, the asymptotics of the trivial factorization algorithm
The answer turned out to be:
RSA-129 = 3490529510847650949147849619903898133417764638493387843990820577
× 32769132993266709549961988190834461413177642967992942539798288533
The lengths of the numbers p and q turned out to be 64 and 65 characters, respectively. The phrase encrypted by Martin Gardner was: " The Magic Words are Squeamish Ossifrage ", which translates as " Magic words are Shy Osprey ", or, according to the Russian Wikipedia, " Magic words are squeamish lamb ." After that, the recommended key length was increased to 140 characters until after 4 years the check number of 140 digits was laid out. In 1998, Bill Gates announced that he provided unlimited funding and computing resources to his company to decompose a number of 200 characters. At the moment, this goal has already been achieved in 2005, the RSA-200 task. Of the $ 100, it’s not difficult to calculate, the interest for 17 years turned out to be approximately $ 140, which were transferred to the free software fund :-)
This whole story was an excellent PR move for the authors of the algorithm and the founders of the company that patented RSA, and received in The result is a $ 900 million profit.
That's what it means to make money wisely;)
Source: Professor Saliy Vyacheslav Nikolaevich, SSU.
I apologize in advance for inaccuracies.
Thank you all for the corrections in the comments!