[Boneh-crypto-course] More about textbook RSA

[Jason Orendorff]

In segment 11-3, Boneh talks about how "textbook RSA" is insecure. He
gives an example where the attack time on some protocol using the RSA
function by itself as a cryptosystem is reduced from 2^64 to 2^40.

But I think he should have made this point in a more straightforward
way... Pull out just a few of the myriad notions of security we've
built. The RSA trapdoor function doesn't satisfy any of them.

For example, suppose you have an RSA public key (e,N) and a
"ciphertext" c = m**e % N. You have a hunch that the plaintext m is
one of two possible messages m1 and m2. How can you test your hunch
and figure out whether m is m1 or m2? Trivial, just compute m1**e % N
and m2**e % N. So having c tells us something about m. Textbook RSA
fails at semantic security.

Another example: suppose you again have the public key (e,N) and c.
This time you know nothing about the message m, but you want to
produce the encryption of 2m. Again, this is trivial, just multiply c
by 2**e % N.

Another example: It's not authenticated encryption simply by form; the
decryption function never returns _|_, and since public key is public,
messages are trivially forgeable.

Another example: suppose you have c = m**e % N, and e is a small
number, say 3; and suppose you know that the plaintext m is a
symmetric cipher key k which is 64 bits. Well c is the cube of a
64-bit number; the "% N" at the end of the formula has no effect
because m**3 isn't big enough: N is 2048 bits. So taking the cube root
of c is real easy. That is, efficient decryption doesn't require the
private key at all. It seems e-th roots are only hard to find in
general; I wonder if there are other special cases like this where
they are easy to compute.

The RSA trapdoor function by itself simply has none of the security
properties we care about, except the one thing, its sole purpose, the
"secure trapdoor permutation" property.

-j