![Online security may have to be reviewed after a UCD team broke the world record for solving a famously hard problem used for encryption. Credit [www.geekersmagazine.com]](http://seanduke.files.wordpress.com/2013/03/online-security.jpg)
Online security may have to be reviewed after a UCD team broke the world record for solving a famously hard problem used for encryption. Credit [www.geekersmagazine.com]
Using a supercomputer provided by the Irish Centre for High-End Computing (ICHEC), the research team from UCD’s Claude Shannon Institute solved a famously difficult conundrum known as the discrete log problem.
To perform secure transactions online, mathematicians create algorithms using numbers stretching to hundreds of digits. These numbers must be large enough to prevent decryption by criminals, but small enough not to slow down transactions, which should take place instantenously.
As part of the process, the Dublin-based research team, led by Professor Gary McGuire, broke the world record last week, previously held by mathematicians in France, by solving the discrete log problem using a 1,971 bit number. The largest number previously used to solve it was a 1,425 bit number.
McGuire, from the School of Mathematical Sciences in UCD, said secure online transactions were now reliant on the discrete log problem or its variations. Most use codes based on numbers larger than the highest number ever to be decrypted but not so large as to slow down transactions.
“Online banking, buying something on Amazon or your airline tickets – any secure website that you put your credit card in [is based on it],” he said. The problem is also used to secure e-voting machines around the world.
Michael Scott, chief cryptographer with CertiVox, an online security firm, said the achievement woudl force his industry to review security levels.
“All of our security depends on variations of the discrete logarithm problem, so if the problem isn’t as hard as we thought it was, then that could be a bit of a worry,” he said.
Scott said the UCD team’s success in cracking such a “tough nut” had been noted by those interested in cryptography. “Out in the cryptographic blogosphere people are talking about it – people are impressed,” he said.
The record for the biggest number used to solve the problem was set at 127 bits by Don Coppersmith from IBM in America in 1984. It has since been broken several times, with French researchers vying with each other and a Japanese team from Fujitsu, until the Irish triumph last week. The UCD team is making plans to break its own record.
McGuire decided to tackle the problem after reading about the Japanese world record last summer. He gathered a team of post-doctoral researchers, made up of Dr Robert Granger from England, Dr Jens Zumbragel from Germany and Dr Frank Gologlu from Turkey for the record attempt, and Science Foundation Ireland provided the funding. The team applied to ICHEC to use its supercomputer and created a mathematical formula to solve the problem.
Measured in bits – the most basic units of computer calculation – their record stands at 1,971 bits. In layman’s terms the number is 594 digits long.
McGuire said their formula meant they should be able to break their own record, given time. “We can push things on quite a bit,” he said.
“Over the next month we hope to go up to 4,000 bits. That would never have been imagined a year ago.”
World records
1984, Don Coppersmith (IBM), USA, 127 bits
1992, Daniel Gordon (Google), Kevin McCurley (Georgia IT), USA, 401 bits
1998, Damien Weber, Thomas Denny, (Universitat des Saarlandes) Germany, 512 bits
2001, Antoine Joux (Ecole Normale Supérieure), Reynald Lercier (Université de Rennes), France, 521 bits
2004 Emmanuel Thomé (Institute National de Recherche en Informatique et Automatique), France, 607 bits
2005, Antoine Joux, Reynald Lercier, France, 613 bits
2012, Fujitsu, Kyushu University, National Institue for Information and Communications Technology, Japan, 934 bits
2013, Antoine Joux, Frances, 1,425 bits
2013, Gary McGuire, Faruk Gologlu, Rogert Granger, Jens Zumbragel (UCD), Ireland, 1,971 bits
First published in The Sunday Times, Irish Edition, 3rd March 2013
