Shy osprey case. 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 Directions in Cryptography" with revolutionary encryption ideas using the public key. And then, in August 1977 , three scientists Ronald Rajvest , Adi Shamir and Leonard Adleman published an article in the journal Scientific American , where they described in detail their algorithm using calculations in the ring of integers. As many know, the idea of the algorithm is the existence of a conditionally one-way function — ordinary multiplication on a set of primes of great 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 prime numbers), finding p and q (or factoring the number n) for large n seems to be a resource-intensive task.
In the same issue, the famous 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) - the 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 to decrypt the message a reward of $ 100, which he put into the bank at 2% per annum. According to analysts, it would take 20,000 years of continuous work to decompose such a huge number into factors with the existing factorization algorithms and the power of those computers (Ron Rivest assumed 40 quadrillion years for a number of 125 characters). But the situation has changed ...
Then, in 1994, the young cryptographer of the American army, Arjen Lenstra, developed an improvement of the Quadratic Sieve agitourt , which allows finding the simple factors of up to 130 digits in a reasonable time. The asymptotics of the algorithm was O (e sqrt (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)) , which is longer for large n. Lenstra himself did not have the necessary computing power, and then he offered to volunteers to 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 the solution of the problem, providing 1600 computers: in addition to the most common computers, 3 supercomputers took part and, according to Russian-speaking 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, a meteorological supercomputer dedicated to Lenstre himself entered the business, which, after 220 days of continuous operation, factorized 129 a significant number n.
The answer was:
The lengths of the numbers p and q were 64 and 65 characters, respectively. The phrase , coded by Martin Gardner, was: " The Magic Words are Squeamish Ossifrage ", which translates " Magic words are Shy Osprey " or, according to Russian Wikipedia, " Magic words are a squeamish lamb ". After that, the recommended key length was increased to 140 characters until, after 4 years, the control number of 140 digits was decomposed. In 1998, Bill Gates stated that he provided unlimited funding and computational resources for his company to decompose a number of 200 characters. At the moment, this goal has already been achieved in 2005, the task of RSA-200 . Of the $ 100, it’s not hard to calculate, the interest for 17 years was about $ 140, which was transferred to the free software fund :-)
The whole story was an excellent PR move for the authors of the algorithm and the founders of the company, which patented RSA, and received $ 900 million in profits as a result.
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 corrections in the comments!
In 1976, Whitfield Diffie and Martin Hellman published their article "New Directions in Cryptography" with revolutionary encryption ideas using the public key. And then, in August 1977 , three scientists Ronald Rajvest , Adi Shamir and Leonard Adleman published an article in the journal Scientific American , where they described in detail their algorithm using calculations in the ring of integers. As many know, the idea of the algorithm is the existence of a conditionally one-way function — ordinary multiplication on a set of primes of great 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 prime numbers), finding p and q (or factoring the number n) for large n seems to be a resource-intensive task.
In the same issue, the famous 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) - the 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 to decrypt the message a reward of $ 100, which he put into the bank at 2% per annum. According to analysts, it would take 20,000 years of continuous work to decompose such a huge number into factors with the existing factorization algorithms and the power of those computers (Ron Rivest assumed 40 quadrillion years for a number of 125 characters). But the situation has changed ...
Then, in 1994, the young cryptographer of the American army, Arjen Lenstra, developed an improvement of the Quadratic Sieve agitourt , which allows finding the simple factors of up to 130 digits in a reasonable time. The asymptotics of the algorithm was O (e sqrt (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 was:
RSA-129 = 3490529510847650949147849619903898133417764638493387843990820577
× 32769132993266709549961988190834461413177642967992942539798288533
The lengths of the numbers p and q were 64 and 65 characters, respectively. The phrase , coded by Martin Gardner, was: " The Magic Words are Squeamish Ossifrage ", which translates " Magic words are Shy Osprey " or, according to Russian Wikipedia, " Magic words are a squeamish lamb ". After that, the recommended key length was increased to 140 characters until, after 4 years, the control number of 140 digits was decomposed. In 1998, Bill Gates stated that he provided unlimited funding and computational resources for his company to decompose a number of 200 characters. At the moment, this goal has already been achieved in 2005, the task of RSA-200 . Of the $ 100, it’s not hard to calculate, the interest for 17 years was about $ 140, which was transferred to the free software fund :-)
The whole story was an excellent PR move for the authors of the algorithm and the founders of the company, which patented RSA, and received $ 900 million in profits as a result.
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 corrections in the comments!
Source: https://habr.com/ru/post/74971/
All Articles