Further Remarks

If one were to implement an actual RSA cryptosystem, there are many additional tricks and ideas to keep in mind. For example, one can add some extra random letters to each block of text, so that a given string will encrypt differently each time it is encrypted. This makes it more difficult for an attacker who knows the encrypted and plaintext versions of one message to gain information about subsequent encrypted messages. In any particular implementation, there might be attacks that would be devastating in practice, but which wouldn't require factoring the RSA modulus.

RSA is in common use, e.g., it is used in OpenSSH protocol version 1 (see http://www.openssh.com/).

We will consider the ElGamal cryptosystem in Sections 6.4.2. It has a similar flavor to RSA, but is more flexible in some ways.

Probably the best general purpose attack on RSA is the number field sieve, which is a general algorithm for factoring integers of the form $pq$ . A description of the sieve is beyond the scope of this book.

SAGE Example 3.3   Here is a simple example of using a variant of the number field sieve in SAGE to factor an RSA key with about 192 bits:

sage: n = next_prime(randrange(2^96))*next_prime(randrange(2^97))
sage: v = qsieve(n)              # takes a long time (less than a minute)
sage.: v                         # random output
([9198565782803667323524291559, 103444690435104030848257111301], '')