9 RSA scheme II
9.1 Security
Finally, let’s explore how secure the RSA scheme really is.
Specifically, let’s consider the case where as an attacker, you already know the public key (\(n\) and \(e\)) as well as the cipher text, \(c = m^e \bmod n\). Can you recover the message \(m\)?
Exercise 1: Suppose you know that \(n = 143\) and \(e = 7\). You also know the encoded message is \(c = 41\). Can you recover the decoded message \(m\)?
Hint: The message can be recovered using the formula \(m = c^d \bmod n\).
Since you already know \(n\) and \(c\), the only thing you need to find is \(d\). Recall that \(d\) is specified by the equation \(de \equiv 1 \bmod \phi\), and \(\phi = (p - 1)(q - 1)\).
Once you have found \(d\), you can key in its value below to quickly calculate \(m\), and submit your answer.
If c = , d = , and n = , then m is:
Your answer: m =
Exercise 2: Suppose you know that \(n = 373577\) and \(e = 7\). You also know the encoded message is \(c = 226918\). Can you recover the decoded message \(m\), using the same strategy as above?
Chances are, you can’t do this on your own! However, if you’re feeling confident, you can try to guess the answer anyway:
If c = , d = , and n = , then m is:
Your answer: m =
You probably found that the key to cracking the message is figuring out the prime factors \(p\) and \(q\). Once you have those, you can calculate \(\phi\) easily, and then \(d\) using the extended Euclidean algorithm.
In the first case, this was easy enough. But in the second case, finding \(p\) and \(q\) is a lot harder, because \(n\) is a lot bigger.
But, we could get a computer to do it!
9.2 Prime factorisation
Although it is pretty slow for a human to figure out the primes \(p\) and \(q\) from their product, computers are much better at it.
Type a number into this box, and watch as the computer factorises it:
11 × 13
With this tool, you can revisit the second exercise above.
This isn’t looking very promising so far, though. If the computer can factorise \(n\) so easily, then the RSA scheme cannot be very secure at all!
In fact, the key to getting around this is to use really large numbers: ones which even computers cannot factorise in a reasonable amount of time.
Here are a few large numbers which you can try in the calculator above. Notice how the time taken to factorise them increases as the numbers get larger. You can make up your own numbers to try as well: pick a couple of prime numbers from this list, multiply them together, and see how long it takes to factorise it.
9.3 RSA in practice
Clearly, if we make \(n\) enough, there will be a point where it takes years or even longer to factorise it.
We can’t find that out for ourselves today (we don’t have that much time!), but we can make a plot of the time taken to factorise \(n\) versus the value of \(n\). Since our values of \(n\) (as well as the times) will span quite a wide range, we will take the base-10 logarithms of both values when making the plot. By extrapolating the plot, we can then figure out how large a number we would need to make RSA secure.
Start by keying in a few values of \(n\). You can use the examples above (which have been filled in for you), or choose your own. (But make sure that the examples are large enough that the time taken is not zero!)
Press the ‘factorise’ button next to each value of \(n\), and the time taken to factorise them will be displayed for you in the box next to it. Then, when you have a few data points, click the button to plot the graph:
Exercise: Using the linear regression equation (shown in the plot title), calculate how large a value of \(n\) we need to choose in order for our computer to take 1 year to factorise it.
(You don’t need to calculate the actual value of \(n\); it will be a very big number! Expressing it in terms of its logarithm is enough. To give you an idea of its size, the number of digits in \(n\) is on the order of \(\log_{10}n\).)
Although that number might be enough to stop someone cracking our messages with this computer, it is not enough to keep out someone using a more powerful computer and a more efficient method for factorising numbers.
The value of \(n\) used in practical applications of the RSA algorithm is much larger than this. It is generally recommended that \(n\) should be at least ‘2048 bits’ long; or in other words, it should be larger than \(2^{2048}\)).
This is equivalent to a decimal number with about 617 digits, meaning that \(\log_{10}n \approx 617\)!