eli5: why do public keys encrypt some messages the same?

Question

I heard that along with a public key, you need a initalization vector so that messages are not encryption identically in different instances. Since all a public key does is multiple prime numbers together, why are some keys the same as others? There are an infinite number of prime numbers (I think) so there should be no problem.

In: 0

Answer 1

The idea is that if you encrypt the *same* message over and over again with the same key – and users don’t change keys all that often, though it does happen – it would be possible for an adversary to notice that you’re sending the same encrypted data over and over again. Like, if after sending encrypted message A you then leave your house and go to the grocery store, they can deduce that encrypted message A is related even though they can’t actually read it.

And yes, since public keys are just a mathematical formula, applying the same formula to the same input would always produce the same output. That’s a weakness, and this is how we deal with it. The initialization vector is just a hint of randomness added to the message to prevent this. Instead of a series of encrypted messages decrypting to read:

* `I’m going to the grocery store`
* `I’m going to the grocery store`
* `I’m going to the grocery store`

It would become:

* `g74j I’m going to the grocery store`
* `894k I’m going to the grocery store`
* `0012 I’m going to the grocery store`

And so on and so forth.

This is not specific to public/private keys. Symmetrical encryption like AES absolutely has this same problem, and any half-decent encryption scheme has to deal with the fact that encryption is done in blocks – AES is 128 bits at a time, for example – and so you need to protect blocks that are part of the same bigger message from the same problem. It’s common for each block to use a constantly changing Initialization Vector that’s related to the previous block in some way, with the very first block being the where the IV is most critical to select, hence the name *Initial*ization Vector. Properly, I should not call it the IV for any other block but the first.

[Wikipedia has an example](https://en.wikipedia.org/wiki/Block_cipher_mode_of_operation) with a picture that encrypted as raw pixels, but no initialization vector used on any block. You can still make out the picture of the penguin that was encrypted, showing that encryption has failed to properly protect the hidden information.