0
$\begingroup$

In the book Cryptography: Theory and Practice by Douglas R. Stinson, there is a section on the shift cipher where he makes the following claim:

On average, a plaintext will be computed using this [exhaustive key search] method after trying $26/2 = 13$ decryption rules.

But this isn't clear to me.

Using the definitions below, fix an agreed upon key $k_0 \in \mathcal{K}$. Since there are $26$ decryption keys, the probability of choosing the correct key $k_0$ to successfully decrypt a ciphertext is $\frac{1}{26}$. Then if $X$ is the random variable denoting the number of keys used until successfully decrypting the ciphertext, then $X \sim \operatorname{Geometric} \Big(\frac{1}{26}\Big)$, which suggests that the average number of attempts until successfully decrypting a cipher text is $26$. Thoughts?

Definitions

Here are some definitions.

I. A cryptosystem is a five-tuple $(\mathcal{P},\mathcal{C},\mathcal{K},\mathcal{E},\mathcal{D})$ where the following conditions are satisfied:

  1. $\mathcal{P}$ is a finite set of possible plaintexts
  2. $\mathcal{C}$ is a finite set of possible ciphertexts
  3. $\mathcal{C}$, the keyspace, is a finite set of possible keys
  4. For each $K \in \mathcal{K}$, there is an encryption rule $e_K \in \mathcal{E}$ and a corresponding decryption rule $d_K \in \mathcal{D}$. Each $e_K \, : \, \mathcal{P} \rightarrow \mathcal{C}$ and $d_K \, : \, \mathcal{C} \rightarrow \mathcal{P}$ are functions such that $d_K(e_K(x)) = x$ for every plaintext element $x \in \mathcal{P}$.

II. Shift Cipher.

Let $\mathcal{P} = \mathcal{C} = \mathcal{K} = \mathbb{Z}_{26}$. For $0\leq K \leq 25$ and $x,y \in \mathbb{Z}_{26}$, define $$e_K(x) = (x+K)\operatorname{mod}26$$ $$d_k(y) = (y-K)\operatorname{mod}26$$

$\endgroup$
2
$\begingroup$

The chance of successful decryption rises with each failure because you are presumably smart enough not to try a shift that has failed. That means the distribution is not geometric. In fact there are only $25$ encryption rules because we presumably exclude the $0$ shift. You would only try $12.5$ on average before finding the right one

$\endgroup$
  • $\begingroup$ $\frac1{25}\sum_{n=1}^{25}n =\frac1{25} \times \frac{25 \times 26}{ 2}=13$ $\endgroup$ – Henry May 15 '18 at 0:38
  • $\begingroup$ @Henry: right you are. I had an off by $\frac 12$ error. $\endgroup$ – Ross Millikan May 15 '18 at 0:40

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.