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?
-
$\begingroup$ Try assuming the highest frequency letter is A and the next is E. That gives other equations, I think. $\endgroup$– Henno BrandsmaCommented Dec 1, 2017 at 5:28
-
$\begingroup$ I tried that, still end up with the same result. $\endgroup$– undergradCommented Dec 1, 2017 at 20:05
-
$\begingroup$ Give the data maybe? $\endgroup$– Henno BrandsmaCommented 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$– Ilmari KaronenCommented Dec 2, 2017 at 8:12
1 Answer
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).