The Story of RSA

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.