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$

1 Answer 1

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$
2
  • $\begingroup$ $\frac1{25}\sum_{n=1}^{25}n =\frac1{25} \times \frac{25 \times 26}{ 2}=13$ $\endgroup$
    – Henry
    Commented May 15, 2018 at 0:38
  • $\begingroup$ @Henry: right you are. I had an off by $\frac 12$ error. $\endgroup$ Commented May 15, 2018 at 0:40

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .