<http://www.physorg.com/printnews.php?newsid=98962171> This news is brought to you by PhysOrg.com A mighty number falls Mathematicians and number buffs have their records. And today, an international team has broken a long-standing one in an impressive feat of calculation. On March 6, computer clusters from three institutions - the EPFL, the University of Bonn and NTT in Japan -- reached the end of eleven months of strenuous calculation, churning out the prime factors of a well-known, hard-to-factor number that is a whopping 307 digits long. "This is the largest 'special' hard-to-factor number factored to date," explains EPFL cryptology professor Arjen Lenstra. (The number is 'special' because it has a special mathematical form -- it is close to a power of two.) The news of this feat will grab the attention of information security experts and may eventually lead to changes in encryption techniques. Although it is relatively easy to identify huge prime numbers, factoring, or breaking a number down into its prime components, is extremely difficult. RSA encryption, named for the three individuals who devised the technique (Ronald Rivest, Adi Shamir and Leonard Adleman), takes advantage of this. Using the RSA method, information is encrypted using a large composite number, usually 1024 bits in size, created by multiplying together two 150-or-so digit prime numbers. Only someone who knows those two numbers, the "keys", can read the message. Because there is a vast supply of large prime numbers, it's easy to come up with unique keys. Information encrypted this way is secure, because no one has ever been able to factor these huge numbers. At least not yet. The most recent factoring record is RSA200, a 200-digit 'non-special' number whose two prime factors were identified in 2005 after 18 months of calculations that took over a half century of computer time. The international team factored the current 307-digit behemoth using the "special number field sieve," a method devised in the late 1980s by Lenstra (then at Bellcore), his brother Hendrik, then a professor at UC Berkeley, English mathematician John Pollard and Mark Manasse from DEC. The 11-month job took a century of computer time. A feat like this would have been unthinkable back in 1990 when Lenstra started applying number theory and distributed computing to the task of breaking factoring records. Increased computer power and refined computational techniques have raised the bar, and will continue to do so. "We have more powerful computers, we have come up with better ways to map the algorithm onto the architecture, and we take better advantage of cache behavior," Lenstra explains. Is the writing on the wall for 1024-bit encryption" "The answer to that question is an unqualified yes," says Lenstra. For the moment the standard is still secure, because it is much more difficult to factor a number made up of two huge prime numbers, such as an RSA number, than it is to factor a number like this one that has a special mathematical form. But the clock is definitely ticking. "Last time, it took nine years for us to generalize from a special to a non-special hard-to factor number (155 digits). I won't make predictions, but let's just say it might be a good idea to stay tuned." Source: Ecole Polytechnique Fidirale de Lausanne -- ----------------- R. A. Hettinga <mailto: rah@ibuc.com> The Internet Bearer Underwriting Corporation <http://www.ibuc.com/> 44 Farquhar Street, Boston, MA 02131 USA "... however it may deserve respect for its usefulness and antiquity, [predicting the end of the world] has not been found agreeable to experience." -- Edward Gibbon, 'Decline and Fall of the Roman Empire'
11 months in 2007? How long will that take 18 months from now if we assume pure microprocessor advance a la Moore's law? Is there also a slow but steady stream of algorithmic imrpovements to factoring? Where the f's Cordian these days? Also, I didn't know any real encryption work was done at Bellcore, though I consider it possible this guy was doing this work in his "spare time". I remember back in the day they broke a 'Smartcard' by environmentally stressing it and getting the sick chip to throw up essential bits... -TD
From: "R.A. Hettinga" <rah@shipwright.com> To: Philodox Clips List <clips@philodox.com>, cypherpunks@jfet.org Subject: A mighty number falls Date: Sat, 16 Jun 2007 10:25:58 -0400
<http://www.physorg.com/printnews.php?newsid=98962171>
This news is brought to you by PhysOrg.com
A mighty number falls
Mathematicians and number buffs have their records. And today, an international team has broken a long-standing one in an impressive feat of calculation.
On March 6, computer clusters from three institutions - the EPFL, the University of Bonn and NTT in Japan -- reached the end of eleven months of strenuous calculation, churning out the prime factors of a well-known, hard-to-factor number that is a whopping 307 digits long.
"This is the largest 'special' hard-to-factor number factored to date," explains EPFL cryptology professor Arjen Lenstra. (The number is 'special' because it has a special mathematical form -- it is close to a power of two.) The news of this feat will grab the attention of information security experts and may eventually lead to changes in encryption techniques.
Although it is relatively easy to identify huge prime numbers, factoring, or breaking a number down into its prime components, is extremely difficult. RSA encryption, named for the three individuals who devised the technique (Ronald Rivest, Adi Shamir and Leonard Adleman), takes advantage of this. Using the RSA method, information is encrypted using a large composite number, usually 1024 bits in size, created by multiplying together two 150-or-so digit prime numbers. Only someone who knows those two numbers, the "keys", can read the message. Because there is a vast supply of large prime numbers, it's easy to come up with unique keys. Information encrypted this way is secure, because no one has ever been able to factor these huge numbers. At least not yet.
The most recent factoring record is RSA200, a 200-digit 'non-special' number whose two prime factors were identified in 2005 after 18 months of calculations that took over a half century of computer time.
The international team factored the current 307-digit behemoth using the "special number field sieve," a method devised in the late 1980s by Lenstra (then at Bellcore), his brother Hendrik, then a professor at UC Berkeley, English mathematician John Pollard and Mark Manasse from DEC. The 11-month job took a century of computer time.
A feat like this would have been unthinkable back in 1990 when Lenstra started applying number theory and distributed computing to the task of breaking factoring records. Increased computer power and refined computational techniques have raised the bar, and will continue to do so. "We have more powerful computers, we have come up with better ways to map the algorithm onto the architecture, and we take better advantage of cache behavior," Lenstra explains.
Is the writing on the wall for 1024-bit encryption" "The answer to that question is an unqualified yes," says Lenstra. For the moment the standard is still secure, because it is much more difficult to factor a number made up of two huge prime numbers, such as an RSA number, than it is to factor a number like this one that has a special mathematical form. But the clock is definitely ticking. "Last time, it took nine years for us to generalize from a special to a non-special hard-to factor number (155 digits). I won't make predictions, but let's just say it might be a good idea to stay tuned."
Source: Ecole Polytechnique Fidirale de Lausanne
-- ----------------- R. A. Hettinga <mailto: rah@ibuc.com> The Internet Bearer Underwriting Corporation <http://www.ibuc.com/> 44 Farquhar Street, Boston, MA 02131 USA "... however it may deserve respect for its usefulness and antiquity, [predicting the end of the world] has not been found agreeable to experience." -- Edward Gibbon, 'Decline and Fall of the Roman Empire'
_________________________________________________________________ Picture this share your photos and you could win big! http://www.GETREALPhotoContest.com?ocid=TXT_TAGHM&loc=us
On Sun, Jun 17, 2007 at 05:03:27AM -0400, Tyler Durden wrote:
11 months in 2007? How long will that take 18 months from now if we assume pure microprocessor advance a la Moore's law? Is there also a slow but
Moore's law is about integration density; I'm not sure brute-force L1 code/data also doubles in 12-18 month range. With multicores, it now probably does. It would be interesting to see how systems requiring very large precomputed lookup tables (GBytes and TBytes) for cryptoattack do here. -- Eugen* Leitl <a href="http://leitl.org">leitl</a> http://leitl.org ______________________________________________________________ ICBM: 48.07100, 11.36820 http://www.ativel.com http://postbiota.org 8B29F6BE: 099D 78BA 2FD3 B014 B08A 7779 75B0 2443 8B29 F6BE
participants (3)
-
Eugen Leitl -
R.A. Hettinga -
Tyler Durden