3 August 2021

RSA-129

We are talking about a large number, although there are bigger ones. It’s a particular number with some association. This number is 129 digits long, so it more than the average calculator can handle. But it’s something that a computer could work with. In fact, computers have good reasons to work with this number. This number has a history that goes back to the late 70s, as it was created as a challenge. It starts with 11438162 and ends with 79543541, containing a total of 129 digits.  This number also has a name and sometimes called RSA 129, because it has 129 digits.

RSA-129
Figure 1: all the numbers used for RSA-129 (screenshot from the YouTube video)

The setup for RSA

RSA is the abbreviation of three names. Those are the initials of three that worked on an interesting cryptographic system back in the 70s. R is for Ron Rivest, S is for Adi Shamir and A is for Len Adleman. The three invented the particular cryptographic system that’s based on big numbers like the one shown in figure 1. This number comes from an experiment/challenge that was created, to find out more about the security of the cryptographic scheme that we proposed. The scheme was based on products of large prime numbers. This number has an interesting property. It is the product of a large prime number P and another large prime number Q. You multiply those two prime numbers together and you get this number used for RSA 129.

RSA-129
Figure 2: the creators of RSA-129 (screenshot from the YouTube video)

The secrecy behind RSA-129

The numbers P and Q were secretly chosen, as nobody is supposed to know these numbers. They were multiplied together and they uniquely determined by the product. There’s only one and p one q that when multiplied together to give this number. But the security of the cryptographic scheme that was proposed, depends on assumptions that nobody should be able to find out a P and Q from their product.

The US-patent for RSA-129
Figure 3: The US-patent for RSA-129 (screenshot from the YouTube video)

Finding large prime numbers

Finding prime numbers is not hard. You just need to find big numbers. Big random numbers aren’t so hard either. You can roll some dice or use other methods. We take some big random numbers and then you check if it is a number prime. If it’s even it’s obviously not prime. You can add one to it and say that the number is prime. There’s an easy test for Primeality which makes it easy to test if a number is prime. You can search a bit and primes are actually quite common, so it doesn’t take much time to find out the large prime number. This gives you the prime number P. You do the same thing with a different starting point to find your number Q. With leaves you with a big prime number P and a big prime number Q.

The reason for RSA

RSA was a response to an open problem posted by Whitfield Diffie and Martin Hellman. They had this idea that you could have a way of doing cryptography, called public-key cryptography, where you could tell somebody how to encrypt without telling them how to decrypt. The idea of RSA is that the core difficulty that you give an adversary is the product of factoring. You might choose two large prime numbers, multiply them together and post that as your public key. If I’m sending a message to you using your public key, as you posted this information to contractors,  you need to know yourself those two factors (P and Q) to do the decryption effectively. You keep those secret, you don’t tell anybody. You need those to decrypt the message. (Click here for more information on public keys.)

Setting a challenge

We came up with the idea and it seemed to work. It has the right kind of properties and gives the ability to host a public key. This is done in such a way that nobody can figure out how to decrypt something that was encrypted with that public key. There’s a missing piece that is not really known, that is how hard factoring the products of two large prime numbers are. Therefore a challenge was set out and but RSA 129 was the first challenge, although there were more challenges later. The belief was that this was a hard problem and wasn’t possible to solve. Thus an estimate was put. In a column from Martin Gardner, he wrote about this estimating. It would take 40 quadrillion years to factor this particular product RSA 129. Afterward $100 was offered to anybody who solves the challenge.

The difficulty of factoring

The goal was to learn about the difficulty of factoring, to see if somebody could factor it. An estimation was made determined as to how hard the factoring is, maybe it’s easier than was thought. That’s why a hundred dollar prize was offered. At the time. It was an open problem and still is an open problem as to how hard it is. It was poorly studied at the time, as there were some papers published but not like now. After RSA, factoring became an object that was studied much more. Before that, it was more of a curiosity and only a few people studied it. Therefore there was a search to find people who thought about factoring. But it seemed to be hard as there were no good algorithms.

The flexibility of RSA

It’s also the case that RSA is flexible. You can choose prime numbers of any length and build an RSA modulus. It was possible to create products of 200 to 250 digit primes. You can make it much more challenging for an adversary by choosing large primes, as larger primes will be a good foundation. The question really is, how big is the prime that has to be chosen.

The prime factors found for RSA

RSA 129 sat there for quite a while. The number was published in the late 70s and during the 80s and not much happened. Computers were getting faster. In the early 90s, the Internet started happening with the web. That number was just sitting there and seemingly ignored for a long time. But in 1994 a team of researchers came up with the factorization. They used the increasing computer speed to factor the number. The Internet was used to get a team of people together all over the planet to factor the number. They use better algorithms to factor the number. After a lot of work, they were able to produce the two prime factors, that when multiplied together, give the number for RSA-129. The creators of RSA were shocked when it happened.

Better algorithms

It is possible to predict the growth of technology. This means the with the speed of computers, you can predict the amount of the number of computers you can get together to work on a problem. What is difficult to predict is the improvements in algorithms. That was really what the key was, better algorithms.

RSA-129 is still used

Cryptography has evolved tremendously, as it was a suprise when the prime factors where found. It didn’t mean that RSA was disabled or dead, it just meant that numbers of that size shouldn’t be used. The prime numbers used for RSA-129 were too short. That was a lesson learned, as that was one of the learning goals for this challenge. People still use RSA, they just use larger prime numbers. Instead of a 129 digit number, they might use a 200 or 200 decimal digit number. Larger numbers seem to be immune from these kinds of attacks.

The check

The $100 check
Figure 4: the $100 check (screenshot from the YouTube video)

There was an offer made for $100 for the factoring, a cashier’s check was written for $100. This was given to the team composed of Derek Atkins, Michael Graff, Arjen Lenstra, and Paul Leyland. That team led many other people who were involved as well. At the time the thought was it was probably the cheapest purchase of lots of computer time. An amount of $100 was spent on that much computing time, which was quite a coup.