This is an extract from The Music of the Primes: Why an Unsolved Problem in Mathematics
Matters by Marcus du Sautoy Chapter 10 “Cracking Numbers and Codes”
In
1903, Frank Nelson Cole, a professor of mathematics at Columbia University in New York, gave a rather curious talk of a meeting
of the American Mathematical Society. Without saying a word, he wrote one of the Mersenne's numbers on one blackboard,
and on the next blackboard wrote and multiplied together the two smaller numbers. In the middle he placed an equals sign,
and then sat down.
2^(67) - 1 = 193,707,721 x 761,838,257,287
The audience
rose to its feet and applauded - a rare outburst for a roomful of mathematicians at the turn of the century? In fact, Cole
had done the opposite. It had been known since 1876 that (2 raised to the power 67) - 1, a twenty-digit Mersenne number, was
not itself prime but the product of two smaller numbers. However, no one knew which ones. It had taken Cole three years of
Sunday afternoons to "crack" this number into its two prime components.
It
was not only Cole's 1903 audience who appreciated his feat. In 2000 an esoteric off-Broadway show called The Five Hysterical
Girls Theorem paid homage to his calculation by having one of the girls crack Cole's number. Prime numbers are a recurrent
theme in this play about a mathematical family's trip to the seaside. The father laments his daughter's coming of
age, not because she will be old enough to run off with her lover but because 17 is a prime number, whereas 18 can be divided
by four other numbers!
Over two thousand years ago the Greeks proved that every
number can be written as a product of prime numbers. A fast and efficient way to find which prime numbers have been used to
build up other numbers has eluded mathematicians ever since. What we are missing is a mathematical counterpart of chemical
spectroscopy, which tells chemists which elements of the Periodic Table make up a chemical compound. A discovery of a mathematical
analogue that would crack numbers into their constituent primes would earn its creator more than just academic acclaim.
In 1903, Cole's calculation was regarded as an interesting mathematical curiosity
- the standing ovation he received was in recognition of his extraordinary hard labour rather than any intrinsic importance
the problem had. Such number-cracking is no longer a Sunday afternoon pastime but lies at the heart of modern code-breaking.
Mathematicians have devised a way to wire this difficult problem of cracking numbers into the codes that protect the world's
finances on the Internet. This innocent sounding task is sufficiently tough for numbers with 100 digits that banks and e-commerce
are prepared to stake the security of their financial transactions on the impossible long time it takes - at present - to
find the prime factors. At the same time, these new mathematical codes have been used to solve a problem that dogged the world
of cryptography.
The Birth of Internet cryptography
For as long as we have been able to communicate, we have needed to deliver secret messages. To prevent important
information from falling into the wrong hands, our ancestors devised ever more intriguing ways of disguising the content of
a message. One of the first methods used to hide messages was devised by the Spartan army over two and a half thousand years
ago. The sender and recipient each had a cylinder of exactly the same dimensions, called a scytale. To encode a message, the
sender would first wrap a narrow strip of parchment around the scytale so that it spiralled down the cylinder. He would then
write his message on the parchment, along the length of the scytale. Once the parchment was unwound, the text looked meaningless.
Only when it was wrapped around an identical cylinder would the message reappear. Since then, successive generations have
concocted ever more sophisticated cryptographic methods. The ultimate mechanical encoding device was the German Enigma machine
used by the German forces in the Second World War.
Before 1977, anyone who wanted to send
a secret message faced an inherent problem. Before the message was transmitted, sender and receiver would have to meet in
advance to decide which cipher - the method of encryption - to use. The Spartan generals, for example, would have needed to
agree on the dimensions of the scytale cylinder. Even with the mass-produced Enigma machine, Berlin would still have to despatch
agents to deliver to U-boat captains and tank commanders the books detailing the machine settings for encoding each day's
messages. Of course, if an enemy got their hands on the codebook, the game was up.
Imagine
the logistics of using such a system of cryptography to do business on the Internet. Before we could send our banking details
safely, missing page Was it possible to analyse how fast that program would take to solve the problem? This was obviously
important if the program was going to be implemented. The question demanded highly theoretical analysis but was nevertheless
rooted in the real world. It was this combination that made the challenge for Rivest. He left his robots at Stanford and moved
to MIT to pursue the burgeoning subject of computational complexity. 'One day a graduate student handed me this article
and said, "You might be interested in this",' Rivest recalls. It was Diffie and Hellman's paper, and immediately
he was captivated. 'It laid out this broad vision of what cryptography was and what it might be. If only you could come
up with an idea.' The challenge of the paper brought together all of Rivest's mind. 'What you care about in cryptography
is distinguishing between the problems that are easy and the problems that are hard,' he explained. 'That was what
the computer science was all about.' If a code was going to be hard break, it had to be based on a mathematical problem
whose solution was difficult to calculate. Rivest started his attempt to build a public-key cryptography by plundering the
wealth of problems he knew computers would take a long time to solve. He also needed someone to bounce ideas off. MIT was
already beginning to break the mould of a traditional university, loosening the boundaries between departments in the hope
of encouraging interdisciplinary interactions. Rivest, a computer scientist, worked on the same floor as members of the mathematics
department. In the offices nearby were two mathameticians, Leonard Adleman and Adi Shamir. Adleman was a more gregarious character
than Rivest but still a classic academic with wild and wonderful ideas about things that seemed to have nothing much to do
with reality.
Adleman recalls coming into Rivest's office one morning: 'Ron
is sitting there with this manuscript. "Did you see this thing from Stanford about this crypto, secret code, scrambling,
blah, blah, blah..." My reaction was, "Well, that's nice, Ron, but I have something to talk about. I couldn't
care less." But Ron got very interested in this.' What Adleman cared about was the abstract world of Gauss and Euler.
Cracking Fermat's Last Theorem was what mattered to him, not some trendy subject like cryptography. Rivest found more
receptive ears down the corridor in the office of Adi Shamir, an Israeli mathematician visiting MIT. Together, Shamir and
Rivest began to search for some idea they could use to implement Diffie and Hellman's dream. Though Adleman wasn't
too interested, it was hard to ignore Rivest and Shamir's obsession with this problem. 'Every time I'd go into
their office they'd be talking about it. Most of the systems they came up with sucked, and since I was there I would join
in with their discussions to see if what they were proposing today made sense.' As they explored the range of 'hard'
mathematical problems, their embryonic crypto-systems began to use more ideas from number theory.
This was right up Adleman's street: 'Since that was my area of expertise, I could be more useful in analysing
their systems - and mostly dispensing with them.' He thought he'd met his match when Rivest and Shamir proposed a
very secure-looking system. But after a sleepless night spent working through all the number theory he knew, he could see
how to crack their latest code. 'This went on and on. We would go for a ski trip, and on the ride up that's all we
would talk about... Even as we headed to the top of the ski slopes in a gondola, that's what we would talk about...'
The breakthrough came one evening when all three had been invited to dine at a graduate's house to celebrate the first
night of Passover. Adleman doesn't drink, but he remembers Rivest knocking back the Seder wine. Adleman got home at midnight.
Soon after, the phone rang, It was Rivest. 'I've got another idea...' Adleman listened carefully. 'Ron, I
think this time you've got it. This one sounds right to me.' They had been thinking for a while about the difficult
problem of factorising numbers. There had been no clever proposals for programs, which could crack numbers into their prime
building blocks. This problem had the right flavour to it. Under the influence of the Seder wine. Rivest had seen how to program
this problem into his new code. Rivest recalls, 'It had a good feel to it at first. But we knew from experience that things
that have a good feel initially can still fall apart. So I put it aside till the morning.'
When Adleman arrived at the department in MIT late next morning Rivest greeted him with a handwritten manuscript
with the names Adlemans, Rivest and Shamir blazoned across the top. As Adleman read through it he recognised what Rivest had
told him the previous night on the telephone. ‘So I tell Ron, “Take my name off this, this is your stuff,”
and we proceed to have a fight about whether I should stay on the paper.’ Adleman agreed to think about it. At the time
he thought it probably didn’t matter wither way, as the paper would probably be the least read of all his publications.
But he did remember the early crypto-system that had kept him up all night. He had saved them from rushing into print with
an insecure code which would have left them with egg on their faces. ‘So I went back to Ron. “Make me third on
the list.” So that how it became RSA.’
Rivest decided that they had better find
out how difficult factorising really was. ‘The problem of factorising was an obscure art form at that time. There was
little literature on it. It was difficult to get good estimates on the time that the algorithms that has already been proposed
to take.’ Someone who knew more than most happened to be Martin Gardener, one of the world’s great popularisers
of mathematics. Gardener was intrigued by Rivest’s proposal and asked if it would be all right to run an article about
the idea in his regular column forScientific American.
The reaction to Gardner’s
article finally convinced Adleman that they were on to something big:
That summer
I was out at Berkeley in a bookstore. A customer and the man behind the desk are discussing something and the customer’s
saying, ‘Did you see that crypto thing in Scientific American?’ So I go, ‘Hey, I was involved in that thing.’
And the guy turns to me and says, ‘Can I get your autograph?’ How many times do we get asked for autographs? Zero.
Wow, what is this . . . maybe something’s going on here! Gardner had said in his article that the three mathematicians
would send a preprint of their paper to anyone who sent them a stamped addressed envelope. ‘When I get back to MIT there
are thousands, literally thousands, of these things from all over the world, including Bulgarian National Security blah, blah,
blah.’
People started telling the trio that they were going to be rich. Even in the 1970s, when e-commerce
was hardly dreamt of, people understood the potency of these ideas. Adleman thought the money would start to pour in within
a few months, and went straight out and got himself a little red sports car to celebrate. Bombieri was not the only mathematician
for whom the reward for mathematical success was a fast car. Adleman’s car was eventually paid off with instalments
from his regular income from MIT.
It took a little time for security agencies
and business to fully appreciate the security and the power of RSA. While Adleman was speeding round in his sports car still
thinking of Fermat, Rivest was the one whose head was tuned to the real-world implications of their proposal: We thought there
might be some business potential to the scheme. We went through the MIT patent office, and then we tried to see if there might
be some company that would be interested in marketing the product. But there was really no market in the early eighties. There
was really very little interest at this stage. The world was not well networked. People didn’t have computers on their
desks. The people who were interested were, of course, the security agencies. ‘The security agencies became very concerned
about the development of all this technology,’ say Rivest. ‘ They did their best to see that our proposal wouldn’t
go very fast.’ It seems that the same idea had been suggested behind the closed doors of the world of intelligence.
But the security agencies weren’t too sure whether to place their agents’ lives in the hands of a few mathematicians
who thought that cracking numbers was difficult. Ansgar Heuser of the BSI, the German National Security Agency, recalls how
in the 1980s they considered using RSA in the field. They asked the mathematicians whether the west was stronger than the
Russians at number theory. When the answer came back ‘No’, the idea was shelved. But in the following decade RSA
proved its worth not just for protecting the lives of spies but also in the public world of business.
The mathematics Rivest used to design this cryptographic trick is quite simple. The shuffling of the cards is done
by a mathematical calculation. When a customer places an order at a website, the computer takes the customer’s credit
card number and performs a calculation on it. The calculation will be easy to perform but will be almost impossible to undo
without the knowledge of the secret key. That is because the calculation will be done not on a conventional calculator, but
on one of Gauss’s clock calculators.
The internet company tells its customers
when they place an order on its website how many hours to use on the clock calculator. It decides how many hours to choose
by first taking two large prime numbers, p and q, of around 60 digits each. The company then multiples the primes together
to get a third number, N = p x q. The number of hours on the clock will be huge, up to 120 digits long. Every customer will
use the same clock to encode their credit card number. The security of the code means that the company can use the same clock
for months before they need to consider changing the number of hours on the clock face.
Selecting the number of hours on the website’s clock calculator is the first step in choosing a public key.
Although the number N is made public, the two primes p and q are kept secret. They are two ingredients of the key that is
used to unscramble the encrypted credit card number.
Next, every customer receives
a second number, E, called the encoding number. This number E is the same for everyone and is as public as the number N of
the hours on the clock face. To encrypt their credit card number, C, the customer raises it to power E on the website’s
public clock calculator. (Think of the number E as the number of times the magician shuffles the pack of cards to hide the
one you’ve chosen.) The result, in Gauss’s notation is, C (modulo N).
What makes
this so secure? After all, any hacker can see the encrypted credit card number as it travels through cyberspace and can look
up the company’s public key, which consists of the N-hour clock calculator and the instruction to raise the credit card
number to the power E. To crack this code all the hacker has to do is find a number which, when multiplied together E times
on the N-hour clock calculator and the instruction to raise the credit card number to the power E. To crack this code all
the hacker has to do is find a number which, when multiplied together E times on the N-hour clock calculator, gives the encrypted
credit card number. But that is very difficult. An extra twist comes from the way powers are computed on the clock calculator.
On a conventional calculator the answer grows in proportion of the number of times we multiply the credit card number together.
That doesn’t happen on the clock calculator. There, you very quickly lose sight of the starting pace because the size
of the answer bears no relationship to where you start from. The hacker is completely lost after E shuffles the pack of cards.
What if the hacker tries working through every possible hour on the clock calculator?
No chance. Cryptographers are now using clocks on which N, the total number of hours, has over a hundred digits – in
other words, there are more hours on the clock face than there are atoms in the universe. (In contrast, the encoding number
E is usually quite small.) If it is impossible to solve this problem, how on earth does the Internet company recover the customer’s
credit card number?
Rivest knew that Fermat’s little theorem guaranteed
the existence of a magic decoding number, D. When the Internet company multiplies the encrypted credit card number together
D times, the original credit card number reappears. The same idea is used by magicians in card tricks. After a certain number
of shuffles it looks as though the card order is completely random, but the magician knows that a few more shuffles will bring
the pack back to its original order. For example, the perfect shuffle – where the pack is equally divided, then interleaved
one card at a time from each half – takes eight shuffles to bring the pack into its original position. Of course, the
art of the magician is being able to perform a perfect shuffle eight times in a row. Fermat had discovered the analogue for
clocks of how many perfect shuffles it takes to return a pack of 52 cards to its original order. It was Fermat’s trick
that Rivest had exploited to decode messages in RSA.
Although the pack of cards with your
credit card number has been shuffled by the website a number of times to lose it, the Internet company knows that shuffling
it another D times will make your card appear as if by mathematical magic at the top of the pile. But you can work out what
D is only if you know the secret primes p and q. Rivest used the generalisation of Fermat’s Little Theorem discovered
by Euler which works on clock calculators built from two primes rather than just one. Euler showed that on these clocks the
pattern repeats itself after (p – 1) x (q – 1) + 1 shuffles. So the only way you can know how long it takes to
see the repeating pattern on the clock with N = p x q hours is to know both the primes p and q. Knowledge of these two primes
therefore becomes the key to unlocking the secrets of RSA. The number of shuffles required to recover the lost credit card
is known only by the Internet company, which has kept the prime numbers p and q very secret.
Although the two numbers p and q have been kept secret, their product, N = p x q, has been made very public. The
security of Rivest’s RSA code therefore relies on the difficult task of factorising N. A hacker is faced with the same
problem that occupied Professor Cole at the beginning of the last century: find the two prime building blocks for the number
N.
Throwing down the gauntlet of RSA 129
To
persuade business that the problem of factorising had a respectable heritage, the MIT three would quote what one of the big
guns. Gauss, had to say about factorising: ‘The dignity of the science itself seems to require that every possible means
be exploited for the solution of a problem so elegant and so celebrated.’ Although Gauss acknowledged the importance
of the factorisation problem, he made no headway with its solution. If Gauss had tried and failed to crack it, surely corporate
security was safe in the hands of RSA.
Despite Gauss’s ‘endorsement’ of
the RSA system, before they wired it into their new code the problem of factorising large numbers lay on the margins of mathematics.
Most mathematicians showed little interest in the nitty-gritty of cracking numbers. What if it did take the lifetime of the
universe to find the prime building blocks of large number – surely that was of no theoretical importance. But with
Rivest, Shamir and Adleman’s discovery, the problem of factorising assumed a significance way beyond what it had in
Cole’s day.
So just how difficult is it to crack a number into its prime constituents?
Cole had no access to electronic computers, so it would have taken him a good number of Sundays before he stumbled on 193,707,721
or 761,838,257,287 as one of the two building blocks of the Mersenne number 2^(67) – 1. Armed with our computers, can’t
we just check one number after another until we find one that divides the number we are trying to crack? The trouble is that
to crack a number with over a hundred digits entails checking more numbers than there are particles in the observable universe.
With so many number to check, Rivest, Shamir and Adleman felt confident enough to
issue a challenge: to crack a number with 129 digits that they had built from two primes. The number, along with an encoded
message was published in Martin Gardner’s Scientific American article that brought the code to the world’s attention.
They were not yet the millionaires they were to become, so they offered only $100 prize for unmasking the two primes used
to build the number dubbed ‘RSA 129’. In the article they estimated that it would take as many as 40 quadrillion
years to crack RSA 129. They soon realised they’d made an arithmetical slip in estimating the time it would take. Nevertheless,
given the techniques for cracking numbers into primes then available, it should still have taken thousands of years.
RSA seemed to be the code-maker’s dream come true: an unbreakable code. With so many
primes to check, confidence in the impregnability of the system seemed justified. But the Germans had thought that Enigma
was invincible since it had more combinations than there are stars in the universe – but the Bletchley mathematicians
had showed that one cannot always place one’s faith in large numbers. The gauntlet of RSA 129 was thrown down. Never
ones to shirk a challenge, mathematicians around the world began beavering away, in the years that followed, they began to
devise ever more cunning plans to find Rivest, Shamir and Adleman’s two secret primes. Instead of 40 quadrillion years,
as the MIT three had estimated, their number was eventually cracked in a paltry seventeen years. That us still long enough
for a credit card encrypted with RSA 129 to be well out of date. Nevertheless, it begs the question how much longer it will
be for a mathematician to emerge with ideas that bring seventeen years down to seventeen minutes.
New tricks on the block
The interaction between cryptography and mathematics
introduced modern mathematicians to a new culture more akin to the experimental and practical sciences. It was a culture not
experienced since the nineteenth-century German school had snatched the baton from the mathematicians of Revolutionary France.
The French had regarded their subject as a practical tool, as a means to an end, whereas Wilhelm von Humboldt believed in
the pursuit of knowledge for its own sake. Those theoreticians still steeped in the German tradition were quick to condemn
the study of methods for factorising numbers as a ‘pig in the rose garden’, in Hendrik Lenstra’s words.
In contrast to the pursuit of watertight proofs, this truffling for primes was seen as minor work of little mathematical importance.
But as RSA grew commercially more important, it became impossible to ignore the practical implications of finding an efficient
technique for unveiling the prime building blocks behind large numbers. Gradually, more mathematicians were drawn into the
challenge of cracking RSA 129. The final breakthrough came about not so much from the development of faster computers as from
unexpected theoretical advances. The new problems that sprang out of these forays into code-breaking have led to the development
of some deep and difficult mathematics.
One of the mathematicians attracted to
this emerging subject was Carl Pomerance. Pomerance is happy to split his time between the academic corridors of the University
of Georgia and the commercial environment of Bell Laboratories in Murray Hill, New Jersey. As a mathematician he has never
lost that childish love of playing with numbers and looking for new connections between them. He came to Paul Erdos’s
attention when the Hungarian read an intriguing article by Pomerance on the numerology of baseball scores. Stimulated by a
curious question raised in the article, Erdos descended on Pomerance in Georgia to begin a collaboration that would product
over twenty joint papers.
Factorising numbers had fascinated Pomerance ever since
he had been asked to factorise the number 8,051 in a high-school mathematics competition. There was a time limit of five minutes,
in the 1960s pocket calculators didn’t exist. Although Pomerance was excellent at mental arithmetic, he decided first
to look for a quick route to the solution rather than just testing one number after another. ‘I spent a couple of minutes
looking for the clever way, but grew worried that I was wasting too much time. I then belatedly started trial division, but
I had wasted to much time, and I missed the problem.’
His failure to crack
8,051 fuelled Pomerance’s lifelong quest for a fast way to factorise numbers. Eventually he learnt about the trick his
schoolteacher had had in mind. Before 1977, the smartest way to crack numbers still, amazingly, belonged to the man whose
Little Theorem was the catalyst for the invention of RSA’s prime number code. Fermat’s Factorisation Method is
a fast way factorise special choices of numbers by exploiting some simple algebra. Using Fermat’s method, Pomerance
took just seconds to crack 8,051 into 83 x 97. Fermat, who loved the idea of secret codes, would probably have been delighted
to find his work at the heart of making and breaking codes some three centuries later.
When Pomerance heard of Rivest, Shamir and Adleman’s challenge, he knew immediately that cracking the 129-digit
number was the way to exorcise the memories of his childhood failure. In the early 1980s it dawned on him that there was a
way to exploit Fermat’s Factorisation Method. By implementing the method on a variety of different clock calculators,
it could provide a powerful factorisation machine. Now it was no longer just the outcome of a high-school mathematics competition
that was at stake. This new discovery, called the quadratic sieve, had very serious implications for the emerging world of
Internet security.
Pomerance’s quadratic sieve works by using Fermat’s
Factorisation Method but continually changing the clock calculator being used to try to crack a number. The method is similar
to the Sieve of Eratosthenes, the technique invented by the Alexandrian librarian, which sifts out primes by taking the primes
in turn and then striking out all number which are multiples of that prime. Thus, by dropping numbers through different-sized
sieves, non-primes are eliminated without having to consider them individually. In Pomerance’s attack the prime sieves
are replaced by varying the number of hours on the clock calculators. The calculations performed on each separate clock calculator
provided Pomerance with more information about possible factors. The more clocks that could be used, the closer he could get
to cracking a number into its prime constituents.
The ultimate test of this idea
was to set it to work on the challenge of RSA 129. But in the 1980s this number still looked well out of reach of Pomerance’s
factorisation machine. In the early 1990s help arrived in the shape of the Internet. Two mathematicians, Arjen Lenstra and
Mark Manasse, realised that the Internet would be the perfect ally for the quadratic sieve in an attack on the RSA 129. The
beauty of Pomerance’s method was that the workload could be spread over many different computers. The Internet had been
employed to find Manasse and Lenstra realised that they could now use the Internet to co-ordinate an attack on RSA 129. Each
computer could be assigned different clocks to sieve with. Suddenly, the Internet – which was meant to be protected
by these codes – was being asked to help crack the RSA challenge.
Lenstra
and Manasse put Pomerance’s quadratic sieve on the Internet and called for volunteers. In April 1994 came the announcement
that RSA 129 had crumbled. By combining several hundred desktop computers across twenty-four countries, RSA 129 was cracked
after eight months of real time in a project led by Derek Atkins at MIT, Michael Graff at Iowa State University, Paul Leyland
of Oxford University and Arjen Lenstra. Even two fax machines had joined in the search – while they weren’t handling
messages, they were helping to look for the two prime numbers with 65 and 64 digits. The project used 524.339 different prime
clocks.
In the late 1990s Rivest, Shamir and Adleman issued a new set of challenges.
By the end of 2002 the smallest of their challenges to remain uncracked was a number with 160 digits. The trio’s finances
have improved since 1977, so you can now $10,000 for cracking an RSA challenge number. Rivest threw away the primes he used
to build these challenge numbers, so no one actually knows the answers until the numbers are cracked. RSA Security regards
$10,000 as a small price to pay to keep ahead of the current band of number-crackers. And each time a new record is set, RSA
simply advises businesses to increase the size of the primes.
Pomerance’s
quadratic sieve has been superseded by a new sieve called the number field sieve. This new sieve is responsible for the current
record, set by cracking RSA 155. This was achieved by a network of mathematicians operating under the messianic name of Kabalah.
RSA 155 was a significant psychological breakthrough. In the mid-1980s, when security agencies were still toying with the
idea of using RSA, computer security with this level of complexity had been considered sufficient. As Ansgar Heuser of the
BSI, the German security agency, admitted at a cryptography conference in Essen, had they gone ahead ‘we would be in
the middle of a disaster’. RSA Security is now recommending clocks for which N, the number of hours, has at least 230
digits. But the likes of BSI, who need long-term security to protect their agents, are currently recommending clocks with
over 600 digits.
Head in the sand
The
number field sieve makes a brief appearance in the Hollywood film Sneakers. Robert Redford sits listening to a young mathematician
lecturing about cracking very big numbers: ‘The number field sieve is the best method currently available. There exists
an intriguing possibility for a far more elegant approach… But maybe, just maybe, there is a shortcut…’
Sure enough this whizz-kid, played by Donal Logue, has discovered such a method, ‘a breakthrough of Gaussian proportions’,
and has wired it into a small box which unsurprisingly falls into the evil hands of the film’s villain, played by Ben
Kingsley. The plot is so outlandish that most viewers must imagine that this could never happen in the real world. Yet, as
the credits for the film roll, up pops ‘Mathematical Advisor: Len Adleman’, the A in RSA. As Adleman admits, this
is not a scenario that we can guarantee won’t happen. Larry Lascar, who wrote Sneakers, Awakening and War Games, came
to Adleman to make sure he got the maths right. ‘I liked Larry and his desire for verisimilitude, so I agreed. Larry
offered money, but I countered with Robert Redford – I would do the scene if my wife Lori could meet Redford.’
How prepared are businesses for such an academic breakthrough? Some more so than
others, but on the whole most have their head in the sand. If you ask business and government security agencies, their answers
are a little worrying. These are all comments I’ve recorded on the cryptograph circuit:
‘We met the government standards, that’s all we’re worried about.’ ‘If we go down then
at least a lot of other people will be going down with us.’ ‘Hopefully I will have retired anyway by the time
such a mathematical breakthrough will have happened, so it won’t be my problem.’ ‘We work on the principle
of hope – for the time being nobody expects a dramatic breakthrough.’ ‘Nobody is able to give guarantees.
We simply don’t expect it.’
When I give presentations to businesses
about Internet security I like to offer my own little RSA challenge: a bottle of champagne for the first person to uncover
two prime numbers whose product is 126,629. The difference in response to this challenge I gave in three banking seminars
in different corners of the globe revealed the interesting cultural differences in the financial world’s attitude to
security. In Venice the challenge and the mathematics behind these codes washed straight over the heads of European bankers,
and I resorted to a plant in the audience to offer the solution. In contrast to the bankers of Europe, trained in the humanities
as most of them are, the Far Eastern banking community has a far greater scientific pedigree. By the end of the presentation,
in Bali, one man rose to his feet with the two primes and claimed the champagne. They showed that they appreciated the mathematics
and its implementation in e-business much better than their European counterparts.
But
the presentation to the Americas gave me the most striking insight. Within fifteen minutes of returning to my room after the
presentation I received three phone calls with correct solutions. Two of the US bankers had logged on to the Internet, downloaded
code-cracking programs and run 126,619 through them. The third was very cagey about his method, and he strongly suspected
of having eavesdropped on the other two.
Business has put its trust in a piece
of mathematics that few have taken the time to examine for themselves. True, the immediate threat to the security of everyday
Internet business is more likely to come from sloppy management leaving vital information unencrypted on a website. Like any
cryptographic system, RSA is susceptible to human imperfection, During the Second World War the Allies benefited from a host
of textbook errors made by German operators which helped them to crack Enigma. RSA can equally be weakened by operators choosing
numbers which are too easily crackable. If you want to break codes, buying up second-hand computers is probably better investment
than enlisting for a Ph.D. in a pure mathematics department. The amount of sensitive information left on outmoded machines
is frightening. Offering a simple bribe to someone guarding secret keys could get you far more for your money than sponsoring
a team of mathematicians to crack numbers. As Bruce Schneier comments in his book Applied Cryptography, ‘It’s
a whole lot easier to find flaws in people than it is to find them in crypto-systems.’
However,
such security breaches. Though serious for the company involved, pose no threat to the whole fabric of Internet business.
This is what gives a firm like Sneakers an edge. Although the probability of a breakthrough cracking numbers is small, the
risk is still there and the result would be globally devastating. It could become the Y2K of e-business, bringing the whole
house of emails crumbling to the ground. We think that cracking numbers is inherently difficult, but we can’t prove
it. It would be a weight off the lot of executives’ minds if we could assure them that it is impossible to find a fast
programme that can factorise numbers. Obviously it is difficult to prove that such a thing does not exist.
Cracking numbers is a complex task not because the mathematics is particularly difficult, but because there is such
a huge haystack from which to pluck the two needles. There are many other problems related to this ‘haystack’
quality. For example, although every map can be coloured with for colours, how can you tell, given a particular map, whether
you can seem to be by laboriously working through all possible combinations until, with luck, you hit upon a map that requires
only three colours.
One of Landon T. Clay’s Millennium Problems, known as
P versus NP, raises a rather interesting question about such problems. In the complexity of a problem such as factorising
numbers or colouring maps arises from the very large size of the haystack one has to search through, might there always be
an efficient method to find the needle? Our hunch is that the answer to the P versus NP question is ‘no’. There
are problems which have an inherent complexity that can’t be got around even with the hacking skills of a modern-day
Gauss. If, however, the answer turns out to be ‘yes’, then as Rivest says, ‘it would be a catastrophe for
the cryptographic community’. Most cryptographic systems, RSA included, concern problems about large haystacks. A positive
answer to this Millennium Problem would mean that there really is a fast way to crack numbers – it’s just that
we haven’t found it yet!
Not too surprisingly, business is not overly concerned
with mathematicians’ obsession for building our mathematical edifice on foundations which are 100 per cent secure. Cracking
numbers has remained difficult for the last few millennia, so the business world is happy to build the Internet shopping mall
on a foundation which is 99.99 per cent secure. Most mathematicians think that there is something inherently computationally
different about cracking numbers. But no one can predict what advances the next decades may bring. After all, RSA 129 looked
secure some twenty years ago.
One of the main reasons why factorising numbers is so difficult
is the randomness of primes. Since the Riemann Hypothesis seeks to understand the source of the wild behaviour of the primes,
a proof could provide new insights. In 1900 Hilbert has stressed in his description of the Riemann Hypothesis that its solution
had the potential to unlock many other secrets about numbers. Given the central role of the Riemann Hypothesis in understanding
the primes, mathematicians began to speculate proof, if it is ever found, might yield new ways to crack numbers. This is why
businesses are now beginning to keep an eye on the abstruse world of prime number research. There is another reason why business
is particularly interested in the Riemann Hypothesis. Before they can use the RSA code, Internet companies must be first able
to find two prime numbers with sixty digits. If the Riemann Hypothesis is true, then there is a fast way to discover the primes
used to build the RSA codes on which the security of e-business currently relies.
Hunting
for big primes
Given the increasing pace of the Internet and the consequent demand
for bigger and bigger prime numbers, Euclid’s proof that the primes will never run dry suddenly takes on an unexpected
commercial significance. If the primes are such an unruly bunch how are businesses going to find these big prime numbers?
There may be an infinite number of prime numbers, but as we count higher they get thinner on the ground. If there are fewer
primes the further we count, then are there enough primes with around 60 digits for everyone in the world to have two of them
in order to make their own private key? And even if there are enough, perhaps there are only just enough, in which case there
is a high chance that two people will get the same pair.
Fortunately, Nature has
been kind to the world of e-commerce. Gauss’s Prime Number Theorem implies that the number of primes with 60 digits
is approximately 1060 divided by the logarithm of 1060. This means that there are enough primes with 60 digits for every atom
in the Earth to have its own two primes. Not only that, the chance of you winning the National Lottery is higher than the
likelihood of two different atoms being assigned the same pair of primes.
So,
given that there are enough prime numbers to go round, how can we be sure that a number is prime? As we have seen, it is difficult
enough to find the prime constituents of a non-prime number. If a candidate number is prime then isn’t it doubly difficult
to discover this fact? After all, it means showing that no smaller number divides the candidate.
It turns out that to determine whether a number is prime isn’t as tall an order as you might expect. There
is a fast test to discover whether a number is not prime, even if you can’t find any of its prime constituents. That
is why Cole knew, as had the rest of the mathematical world for some twenty-seven years before he announced his calculation,
that the number he was trying to crack wasn’t prime. This test isn’t much help in predicting the distribution
of primes, the heart of the Riemann Hypothesis. But because it tells us whether any particular number is prime, it lets us
hear individual notes in music, though it doesn’t help us appreciate the overall melody encapsulated in the Riemann
Hypothesis.
The origin of this test is Fermat’s Little Theorem, which Rivest had exploited
that night after the Passover wine when he had discovered RSA. Fermat found that if he took a number on a clock calculator
with a prime number of hours, p, and raised it to the power p, he always got the number he started with. Euler realised that
Fermat’s Little Theorem could be used to prove that a number isn’t prime. For example, on a clock with 6 hours,
multiplying 2 together 6 times lands us at 4 o’clock. If 6 were prime, we could have arrived back at 2 again. So Fermat’s
Little Theorem tells us that 6 can’t be a prime number – else it would be a counter-example to the theorem.
If we want to know whether a number p is prime, we take a clock calculator with p hours. We start testing different
times to see whether raising the hour of the power of p gets us to the time we started from. Whenever it doesn’t, we
can throw that number out, confident that it is not a prime number. Each time we find an hour that does satisfy Fermat’s
test, we won’t have proved that p is prime, but that the hour on the clock is, if you like, bearing witness to p’s
claim to be prime.
Why is testing times on the clock any better than testing whether
each number is less than p divides p? The point is that if p fails the Fermat test, it fails very badly. Over half the numbers
on the clock face will fail this test and testify to the non-primality of p. That there are so many ways to prove that this
number is not prime is therefore an important breakthrough. This method contrasts strongly with the step-by-step division
test, checking off every number to see whether it is a factor of p. if p is the product of, say, two primes, then with the
division test only those two primes can prove that p is not prime. None of the other numbers will be of any help. One has
to get an exact hit for the division test to work.
In one of his multitude of
collaborations, Erdos estimated (though did not rigorously prove) that to test whether a number less than 10150 is prime,
finding just one time on the clock which passes Fermat’s test already means that the odds of that number not being prime
as 1 in 1043. The author of The Book of Prime Number Records, Paulo Ribenboim, points out that using this test, any business
selling prime numbers could realistically peddle their wares under the banner ‘satisfaction guaranteed or your money
back’, without too much fear of going bust.
Over the centuries mathematicians
have refined Fermat’s test. In the 1980s two mathematicians, Gary Miller and Michael Rabin, finally came up with a variation
that would guarantee after just a few tests that a number is prime. But the Miller-Rabin test comes with a bit of mathematical
small print: it works for really big numbers only if you can prove the Riemann Hypothesis (To be precise, you need a slight
generalisation of the Riemann Hypothesis.) This is probably one of the most important things we know hiding behind Mount Riemann.
If you can prove the Riemann Hypothesis and its generalisation, then, as well as earning a million dollars, you will have
guaranteed that the Miller-Rabin test really is a fast and efficient method for proving whether a number is prime or not.
In August 2002, three Indian mathematicians, Manindra Agrawal, Neeraj Kayal and Nitin
Saxena, at the Indian Institute of Technology in Kanpur devised an alternative to the Miller-Rabin test. It was very slightly
slower but avoided having to assume the Riemann Hypothesis. This came as a complete surprise to the prime number community.
Within twenty-four hours of the announcement from Kanpur, 30,000 people across the world – Carl Pomerance among them
– had downloaded the paper. The test was sufficiently straightforward for Pomerance to present the details to his colleagues
in a seminar that same afternoon. He described their method as ‘wonderfully elegant’. The spirit of Ramanujan
still burns strong in India, and these three mathematicians were not afraid to challenge the received wisdom of how one should
check whether a number is prime.
