RSA encryption is a method of encryption which allows you to publicly announce how the encryption works by telling all a number, but only you can decipher easily because you know more details about the number. This is about a method to find out the details.
Once I wondered why the fraction 1/3 repeats every single digit as 0,33.. , or why the digits in the inverse of 7 repeat not but after the 6th digit. Some years later it occurred to me that this leads to a method of breaking RSA encryption. So, as this kind of encryption is pretty popular because it is considered safe, I day-dreamed I might become rich by blackmailing people and secret government agencies by threatening to break their keys, or if they knew how to break the keys themselves, to threaten to reveal that method.
Of course, this kind of activity might get me into jail quickly, so I figured out a method of doing this 'legally': I would set up a website which would offer to "just do some math", since doing math isn't illegal yet; It would just break up some big number into two smaller numbers, the smaller numbers being prime numbers with the product of them being the big number. I would require a minimum fee, but accept higher payments too, and promise not to break this number again unless someone paid me four times that money. I guess you can this see how this works like blackmail, but really isn't because strangers are approaching me, and it isn't me who is the stranger approaching people. To protect a secret worth $10 million, strangers would offer $2.5 million to keep it secret ! And they'd tell me too what they wanted to keep secret !
Observations on 1/3, 1/7, 1/13 ..
Maybe like me, you are now interested in a little math. All you need is a pocket calculator (There's probably a calculator program on your computer). It turns out that the repetition in 1/3 = 0.333.. is just one digit long because 9 can be divided evenly by 3, and that both 1/7=0.142857142857... and 1/13=0.076923076923.. have repetitions of length
6 because 7 and 13 are factors of 999999(
6 times the digit 9) (so there is no rest dividing 999999 by 7 and 13, it gives 999999/7/13 = 10989).
See
recurring decimal.
As proof, consider that the inverse of e.g. 999999 is 0.000001000001... ( I think you have no doubts that that is a proof if a
handwaving lunatic mathematics professor had been saying it in the last 5 seconds of his lecture.)
Now I guessed this would probably be also true if you had a product of two prime numbers. For example, take 11*17, that then because 999999999999999(15 times the digit 9) was divisible by 17 that the inverse of 11*17=1/187 had digits repeating in blocks of length 15 as well. I think one could turn this into a party trick, like one of those tricks were you think of one number, add, multiply and divide, and then the magician tells you either the result or what number you were thinking of. (Again, I have no proof for it, but I guess it is somehow related to subgroups).
How to apply this to RSA encryption ?
It seems to break RSA, you start with a big number, the product, and you only need to find the factors of the product of two large primes, for an example with smaller numbers, break up 187 as the product of two primes, as 11*17, and you'd have broken the key 187. Now my ingenious scheme was this: I would find one of the primes as a a factor of a number of the form 9999999.. (
n times the digit 9). I would find out how many digits
n by calculating the digits of the inverse of the product (e.g. the fraction 1/189) as far as needed, till I detected the length where the pattern repeated. So I'd have a really huge 999999.. number, which would have as a factor one of the factors of the key. By calculating the
greatest common divisor of the 99999.. number and the key, I'd find one factor of the key
Now, having written 3000 lines of badly tested
C code, is where the bugs in my plan to
rule the world occurred to me:
To find a matching pattern of length n in the sequence of digits in 1/x, I would probably have to calculate about as many digits of the inverse as there are primes between 1 and the bigger of the two primes in the product. Means my method was only a little smarter than trying out every single prime simply by dividing the product by it and seeing whether there was no rest. Also, even more shocking, once I had found the length n of the repeated 9999... number, then in order to find the prime I was looking for, I'd have to find the
greatest common divisor of the really huge 99999... number and the product. This might be hard, since the most obvious way to do that would have required more computer memory than any normal computer had, not to speak of my crappy one, even just to store the results of the first step of the
algorithm.
Congratulations ! By reading this, you, like me, almost did join the secret club of people who will be invited by the NSA to a never-ending holiday on some Hawaian island.
Some remarks, for people who actually would consider trying out or improving the above algorithm.
Finding one more digit of the inverse is really a very quick calculation, and I think this might actually be useful somehow. In fact, it has been pointed out to me that
Shor's algorithm also works by finding the period of a repetition. The final step of Shor's algorithm needs to find a gcd too, but not with that big 9999.. number as the algorithm I try here. So it seems my above way might be a dumb (but easy to explain !) way of doing something similar to Shor's. Who knows maybe if you mix Shor's and what I tried, you can find a faster algorithm ..
You might want to use others bases but the usual 10 digit number system, e.g. hexadecimal.
I guessed right that "this would probably be also true if you had a product of two prime numbers", but all this doesn't work because both have to be factors of the 9999.. number.