A computer processor. Photo AP
A group of scientists, including several mathematicians in Amsterdam, has set a new record in digital code-cracking.
The group of mathematical scientists succeeded in factoring a 232-digit number into two prime quotients, each 116 digits long. The feat constitutes a new world record, shattering the last one set five years ago when a number 200 digits long was factored into primes.
The international group of scientists, which includes mathematicians working for the Centre for Mathematics and Computer Science (CWI) in Amsterdam, has presented a paper describing its feat to the online periodical Cryptology for publication.
Prime numbers are numbers only divisible by one and themselves. They play a crucial role in protecting digital information. Secure connections commonly used in electronic banking depend on them. So called RSA-cryptography, named after its inventors, (Ron Rivest, Adi Shamir and Leonard Adleman) works with large numbers that are the product of two primes.
How prime numbers are used in codes
The number 15 is a good example of a figure that can easily be factored into two primes: 3 and 5. The larger a number gets however, the more difficult it is to determine whether this number can be factored into primes and, if so, which primes it factors into. So far, no one has discovered a quick mathematical solution to this so-called ‘factorisation problem’.
The difficulty in finding out the prime quotients is the foundation of RSA-cryptography. In RSA, the product of two large prime numbers is used as a public security key to encode information, but anybody looking to break the code needs to know its secret prime quotients to do so. These can only be discovered by factoring the number into primes and that is only possible through the use of brute computational force.
To determine the reliability of digital security protocols, mathematicians are constantly trying to factor larger numbers into their constituent primes using ever larger supercomputers. Their approach basically consists of multiplying two large primes until they have been able to confirm the number under scrutiny is the product of two prime factors. A normal personal computer would need 1,700 years to reconstitute the 232-digit number into primes.
By pooling the processing capacity of hundreds of fast computers, the mathematicians were able to unveil the secrets of RSA-768 (a 232-digit decimal equals 768 digital bits) in two and a half years.
Old RSA-codes no longer safe
The 768-bit key that has now been hacked is currently used only for encrypting information that need only remain secret for a few weeks. Even so, cracking it is no cakewalk. Anybody intent on deciphering it would require computing capacity equal to that the scientists had at their disposal.
Sensitive information which needs to remain secret for longer periods of time, credit card information for instance, is coded using 1,024 bit keys (309-decimal digits). These have not been cracked yet and are considered to be safe –for the time being. “Cracking these codes requires a thousand times more computational power,” said Herman te Riele, a scientist working for the CWI involved in the cracking of the RSA-768 code. “Ten years ago, we cracked a 512-bit code. Five years back, we did a 663-bit one. You need approximately a thousand times more computational power for each 256 additional bits. We hope to crack a 1024-bit code in the next ten years. 768-bit codes should not really be used any more. Ten years from now, 1.280-bit codes should have become the standard.”
No comments:
Post a Comment