2
$\begingroup$

Prove that the affine cipher over Z26 has perfect secrecy if every key is used with equal probability of 1/312.

Just some guidance/help with this problem would be greatly appreciated not sure how to start the proof. Many thanks!

$\endgroup$
2
  • 2
    $\begingroup$ Well, I'd start by reviewing the definition of perfect secrecy. $\endgroup$
    – pg1989
    Oct 17, 2014 at 0:12
  • $\begingroup$ Note that such a cipher would have perfect secrecy only if the key is used only once. $\endgroup$
    – poncho
    Mar 7, 2016 at 16:41

2 Answers 2

1
$\begingroup$

This would usually I think be more suited as a comment, but you were looking for guidance instead of a complete answer as it were, and I don't have enough reputation to comment.

I'd highly recommend Claude Shannon's introduction (the literal introduction, he developed the concept) to the question you pose. Here’s the paper (PDF) and the section is Part 10 on Pg. 679. The more broad statement of your question is Theorem 6, but he does (as he always does) an incredibly good job of approaching both the motivation for the theorem as well as the proof, the latter of which he gives in relatively informal way.

$\endgroup$
1
$\begingroup$

Let's remember first what an Affine cipher is:

Let $P = C = \mathbb{Z_{26}}$ and let

$$K = \{(a,b) \in \mathbb{Z_{26} \times}\mathbb{Z_{26} : gcd(a,26) = 1 }\}$$

For $K = (a,b) \in K$, define

$$e_k(x) = (ax+b) \mod 26$$

and $d_k(y) = a^{-1} (y- b) \mod 26$ for $x,y \in \mathbb{Z_{26}}$.

Now, let's go to the solution:

There are 312 keys, due due $12 \times 26 = 312$, this is, 12 because there are twenlve coprimes with 26 mod 26, and $b$ can be any number in $\mathbb{Z_{26}}$. Now, let us pick one key and one encryption, getting one cyphertext, summing over all possibilities, we get:

$$\Pr[y] = \sum_{k \in K} \Pr[k] \Pr[d_k(y)] = 12/312\Pr[a] + ... + 12/312 \Pr[z] $$

$$ = 1/26 \cdot(\Pr[a] +...+\Pr[z]) = 1/26$$

By Bayes' Theorem, we have:

$$\Pr[x|y] = \frac{\Pr[x]\Pr[y|x ]}{\Pr[y]} = \frac{\Pr[x]1/26}{1/26} = \Pr[x] $$

Obs.: there are 12 keys that encrypt $x$ to $y$, that's why we have 12/312, note also that for each $a$, the key $(a, y-ax)$ encrypts $x$ to $y$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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