3
$\begingroup$

I've been looking at an online Public Key Encryption Example (summarized below). It seems to me that choosing cyphertext = plaintext^(key) mod n would produce the same ciphertext letter for a particular plaintext letter, leading to easy frequency analysis of the output. Would there be a way to modify the example so that this isn't the case? Is there something I'm missing in the results? Thanks!

Summary of method:

  1. Pick a pair of large prime numbers at random (e.g., 3, 11 (not large in this case))
  2. Compute product: n = p × q = 3 × 11 = 33
  3. Compute the value of Euler's totient function of n: φ(n): φ(n) = (p-1) × (q-1) = 2 × 10 = 20
  4. Pick any number less than and relatively prime to φ(n) (e.g., 7)
  5. Compute the matching private or decryption key d, as the inverse of e modulus φ(n). d = inv of e mod φ(n) = inv(7) mod 20 = 3
  6. Encrypt: cyphertext = plaintext^(key) mod n
$\endgroup$
  • $\begingroup$ This is called raw or textbook RSA. It is not secure. Heed the following warning on that site: "However note that in a real RSA system, the numbers used are much larger and need to satisfy other constraints to ensure maximum security. " (seems edited today, maybe to add that in?). To ensure "any security" would probably be better :P $\endgroup$ – Maarten Bodewes Apr 6 '15 at 19:43
4
$\begingroup$

You are correct that in this case simple frequency analysis would be possible since textbook RSA encryption is deterministic.

One can get around this by using RSA with random padding.

Here are a few references:

In practice, we never use RSA for bulk encryption (encryption of large plaintexts). Instead, we encrypt symmetric keys and encrypt the data with the symmetric key. We do still use padding, however, even in these cases.

$\endgroup$
  • $\begingroup$ Great -- thanks for the links. Glad I wasn't going crazy! $\endgroup$ – Chris Gregg Apr 6 '15 at 16:13
  • $\begingroup$ Or we do something like key agreement instead of encrypt/decrypt of course. $\endgroup$ – Maarten Bodewes Apr 6 '15 at 19:39
5
$\begingroup$

The site also misrepresents RSA encryption. If you are using textbook RSA (i.e. this scheme, with no padding), you don't independently encrypt each letter. Rather, you take the entire message, treat it as a number, and encrypt that.

This doesn't work if your primes are 3 and 11, but if they're each, say, 8 bytes long, then you could encrypt a 16-byte message using textbook RSA by treating the whole message as a single number. The only time you run the encryption operation multiple times on different parts of the message is if the message is longer than the RSA modulus, in which case you need a chaining mode.

RSA has no real chaining modes (no one's bothered coming up with one), but a real block is fairly big anyway. The site broke the message into letters and encrypted each separately (which is the horrible no-good ECB mode) to make the math easier, but that's not even how textbook RSA is used.

There are all sorts of attacks on textbook RSA; frequency analysis isn't really one of them.

$\endgroup$
  • 2
    $\begingroup$ The point about not encrypting letter-by-letter is crucial. If you did that, it would just be a substitution cypher with a particularly baroque way of computing the substitution. $\endgroup$ – David Richerby Apr 6 '15 at 21:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.