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 11, 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 more than one byte at a time, which seriously reduces the vulnerability to 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 much longer 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 number in the first place?