Why does a key have to be at least as long as a message (cryptography)?

Question

I am studying cryptography and find it hard to understand. What happens if the key is one bit or 100 bits shorter than the message?

Answer 1

In general, this condition is not needed. But it is needed if you demand perfect secrecy.

Definition: A cryptosystem has perfect secrecy if for any message $x$ and any encipherment $y$, $P[x~|~y]=P[x]$

But the following are equivalent:

• For any message $x$ and any encipherment $y$, $P[x~|~y]=P[x]$
• For any message $x$ and any encipherment $y$, $P[y~|~x]=P[y]$
• For any encipherment $y$ and ay messages $x_1$, $x_2$, $P[y~|~x_1]=P[y~|~x_2]$

Practically, these equivalent definitions of perfect secrecy state that a ciphertext gives no information about the plaintext. Also, it implies that $$|\mathcal{M}|\leq|\mathcal{C}|\leq |\mathcal{K}|$$

where $\mathcal{M}$ is the set of plaintexts, $\mathcal{K}$ the set of the keys of the cryptosystem and $\mathcal{C}$ the set of all ciphertexts which can be produced from a message $m\in\mathcal{M}$

If we assume that $|\mathcal{K}|<|\mathcal{C}|$, then there will be some $y\in\mathcal{C}$ such that no $k\in\mathcal{K}$ gives $\text{enc}_k(x)=y$, for any $x\in\mathcal{M}$. Therefore, the third equivalent definition of perfect secrecy fails. So we need, $|\mathcal{M}|\leq|\mathcal{C}|\leq |\mathcal{K}|$

In my opinion, the best way to understand this is to play with OTP.

Answer 2

A "random" key that is $k$ bits in length has $k$ bits of entropy. Once that key is used to encode a string those $k$ bits are essentially mixed with the bits of the message to increase its entropy with the caveat that a string can never contain more bits of entropy than its length.

So if you have a message of length $m$ and a key of length $k$ then the entropy of the encoded message is at least $\min(m,k)$. This means that if your message is 10 bits shorter than your key you might as well have a key that's 10 bits shorter since it is, from an information theoretic standpoint, doing nothing for you.

Answer 3

Informally, if a key is shorter than the message, that means the key has to be reused somewhere (for an OTP). When it's reused, attackers can exploit the repeated patterns to decipher the message quicker.