0
$\begingroup$

I am doing probabilistic decryption, I was given that A and E had the highest frequency count in the plain text. H and X have the highest frequency in the encrypted text. So in solving for a and b I got a=4 and b=7, but that a won't work because there is no inverse of 4 in mod 26 (which I need for the decryption parameters) What can I do from here?

$\endgroup$
4
  • $\begingroup$ Try assuming the highest frequency letter is A and the next is E. That gives other equations, I think. $\endgroup$ Commented Dec 1, 2017 at 5:28
  • $\begingroup$ I tried that, still end up with the same result. $\endgroup$
    – undergrad
    Commented Dec 1, 2017 at 20:05
  • $\begingroup$ Give the data maybe? $\endgroup$ Commented Dec 1, 2017 at 20:09
  • $\begingroup$ You've messed up your linear algebra somewhere. Assuming that A → X and E → H, as suggested by @Henno, should give you a=9. $\endgroup$ Commented Dec 2, 2017 at 8:12

1 Answer 1

0
$\begingroup$

Maybe you should read up on solving congruences modulo composite moduli like $26$. There are some examples here, or slightly easier here etc.

Note that A,E,H,X correspond to the integers $0,4,7,23$ respectively. Suppose that $c(x) = ax + b$ where $x$ is the plain letter and $c(x)$ the corresponding encryption, $a,b \in \mathbb{Z}_{26}$.

If we assume $A \to X, E \to H$, we get the equations (for $a,b$, using $x=0,4$):

$$ \begin{align} c(0) =& 23 \equiv a\cdot 0 + b \bmod{26}\\ c(4) =& 7 \equiv a \cdot 4 + b \end{align} $$

which gives $b = 23$ and $4a + 23 \equiv 7 \bmod{26}$, or $4a \equiv -16 \equiv 10 \bmod{26}$.

This last equation has two solutions as $\gcd(4,26) = 2 | 10$, and we find they are $a=9$ and $a=22$. Only $a=9$ has an inverse modulo $26$ namely $3$ ($3\cdot 9 = 27 = 26 + 1$). You can then find the decryption formula and try other letters to check whether the assumption $A \to X, E \to H$ was correct.

If however you'd assume $A \to H, E \to X$ we'd have gotten the equations:

$$ \begin{align} c(0) =& 7 \equiv a\cdot 0 + b \bmod{26}\\ c(4) =& 23 \equiv a \cdot 4 + b \end{align} $$

which gives $b=7$, and $4a \equiv 16 \bmod{26}$ and this last equation has two solutions again: $a=4$ and $a=17$, of which only $a=17$ is a potential candidate as it has an inverse in $\mathbb{Z}_{26}$ of $23$. So again compute the decryption formula for this case to check this hypothesis on other letters as well.

Note that if there is at least $1$ solution to $4a = x$ modulo $26$ it has $2$ that differ by $13$, corresponding to the theory I referred to. So you either have $0$ or $2$ solutions to such linear equations in one variable. This is why you're better off working over prime fields (add a space as an extra character and some more to work module $29$ or $31$ or some such idea).

$\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.