Author : Brian Raiter
Page : << Previous 4 Next >>
24 + 1 equals. If we can divide the resulting number into two relatively prime values, then we have a worthy pair.
2 * 24 + 1 = 49 = 7 * 7 (no, factors must be different)
3 * 24 + 1 = 73 = 73 (we need two numbers)
4 * 24 + 1 = 97 = 97 (ditto)
5 * 24 + 1 = 121 = 11 * 11 (nope)
6 * 24 + 1 = 145 = 5 * 29 (jackpot)
We could continue searching -- nothing requires us to take the first value that works -- but this is fine for our purposes. So, we have 5 for P, our public key, and 29 for Q, our private key.
To make our cipher work, you may recall that the values we use for T must be less than R, and also relatively prime to R. We also don't want to use 1 for T, because 1 raised to any power whatsoever is going to remain 1. That leaves us with 23 values we can use for T. We'll use the following character set:
2 3 4 6 8 9 11 12 13 16 17 18 19 22 23 24 26 27 29 31 32 33 34
A B D E F G H I J K L M N O P R S T U V W Y Z
(We're missing a few letters, but this can be worked around with some creative misspellings: KS for X, KW for Q, and K or S for C. In any case, it's not important for this example.)
The message we will encrypt is "VENIO" (Latin for "I come"):
V E N I O
31 6 19 12 22
To encode it, we simply need to raise each number to the power of P modulo R.
V: 31^5 (mod 35) = 28629151 (mod 35) = 26
E: 6^5 (mod 35) = 7776 (mod 35) = 6
N: 19^5 (mod 35) = 2476099 (mod 35) = 24
I: 12^5 (mod 35) = 248832 (mod 35) = 17
O: 22^5 (mod 35) = 5153632 (mod 35) = 22
So, our encrypted message is 26, 6, 24, 17, 22 -- or "SERLO" in our personalized character set.
When the message "SERLO" arrives on the other end of our insecure phone line, we can decrypt it simply by repeating the process -- this time using Q, our private key, in place of P.
S: 26^29 (mod 35) = 10819995774...2921981566976 (mod 35) = 31
E: 6^29 (mod 35) = 36845653286788892983296 (mod 35) = 6
R: 24^29 (mod 35) = 10620036506...3621199028224 (mod 35) = 19
L: 17^29 (mod 35) = 48196857210...1825223071697 (mod 35) = 12
O: 22^29 (mod 35) = 85164331908...9721106030592 (mod 35) = 22
The result is 31, 6, 19, 12, 22 -- or "VENIO", our original message.
How to Crack RSA
Now, let's switch hats. Imagine that we've just managed to pluck the message "SERLO" off of our wiretap. By looking up the message's destination in the public-key directory, we find that our message was encrypted with a value of 35 for R and 5 for P. How do we go about decrypting it when we don't know the value for Q?
Well, we know that that:
P * Q = S * phi(R) + 1.
We can divide both sides of the equation by P, which gives us a formula for Q:
Q = (S * phi(R) + 1) / P.
S is also unknown, though, so we will have to try plugging in different numbers for S, and look for values for Q that meet all the necessary constraints.
(1 * 24 + 1) / 5 = 25 / 5 = 5 (no, same number as P)
(2 * 24 + 1) / 5 = 49 / 5 (doesn't divide evenly)
(3 * 24 + 1) / 5 = 73 / 5 (ditto)
(4 * 24 + 1) / 5 = 97 / 5 (ditto)
(5 * 24 + 1) / 5 = 121 / 5 (ditto)
(6 * 24 + 1) / 5 = 135 / 5 = 29 (this could be it!)
Each time we find a candidate for Q, we could test it out on a few messages, and see if it works. (Note that, for example, when S = 11, Q will have a value of 53, which also meets all the constraints, but does not decrypt correctly with P = 5.) If 29 hadn't worked and we needed to continue the search, it would be pretty obvious that we only needed to test every fifth number, since those are the only numbers which will give us a result that is evenly divisible by 5. So, even though this process involves a brute-force search, it is very simple and very fast.
So what's the catch? Well, in order to do any of this, we first need to know the value of phi(R). Of course, we already know that R has exactly two prime factors, so calculating phi(R) is a snap once we know what those factors are.
Famous last words.
How to Make RSA Uncrackable
Of course, in our case the factors of R can be found by consulting a times table. So it's not much of a challenge. (For that matter, since we're encrypting one character at a time, our coded messages would also be vulnerable to good old-fashioned cryptanalysis).
To make it less easy to find R's factors, we need to pick larger prime numbers for U and V to begin with. If, instead of 5 and 7, we had chosen 673 and 24971, we would have a value of 16805483 for R, and phi(R) would be 16779840. (This would also give us enough room to encrypt three bytes at a time, which pretty much ruins any hope of cryptanalysis.) Looking for a P and Q pair is no longer something you want to do with pencil and paper, of course, but it took me less than three minutes to find the usable pair 397 and 211333 -- including the time it took to write and debug a Perl script.
On the other hand, it also took me less than three seconds to run "factor" on 16805483 to obtain 673 and 24971. Armed with those numbers, it wouldn't take long to derive 211333 from 397. So even these numbers aren't close to being large enough. We need really big numbers.
Well, we can certainly find huge values for R that are difficult to factor. But how far can we go before it becomes too difficult for us to use the numbers in the first place?
Huge Exponents in Modulus Arithmetic
The problem is this: The bigger R gets, the bigger P and Q will be, and P and Q are to be used as exponents! Even the relatively tame-looking:
9^(9^9)
produces a number over 350 million decimal digits long. How are we going to be able to encrypt anything without needing terabytes of storage?
The trick is that we only need to calculate these exponential values modulo R. As always, modulus arithmetic simplifies things a great deal.
Let's revisit our example, and look at how we could decrypt the first number, 31, remembering that R = 35 and Q = 29:
31^29 (mod 35) = ?
To start with, we look at Q's binary representation. 29 in binary is 11101, which means that:
29 = 16 + 8 + 4 + 1, or
29 = 2^4 + 2^3 + 2^2 + 2^0.
We can now break the exponential calculation apart into several smaller ones:
31^29 = 31^(2^4 + 2^3 + 2^2 + 2^0)
= 31^(2^4) * 31^(2^3) *
Page : << Previous 4 Next >>