0
$\begingroup$

Given two letters of the plaintext 'ZP' corresponding to the ciphertext 'AE' respectively, I have found the key to be (a,b)=(10,10) (modulo 26).

Therefore the decryption map $D(x)=a^{-1}(x-a)\bmod26$ I obtain here is $D(x)=10^{-1}(x-10) \bmod26$. However, $10^{-1}\bmod26$ does not exist so how am I able to find this? Have I got the key wrong? I know $(23,23)$ also works but i dont know how to find that key with my working.

This is my working:

$25a+b\equiv0 \pmod{26}$, $15a+b\equiv4 \pmod{26}$

where $(a,b)$ are the two elements of the key, and $Z,A,P,E$ correspond to the numbers $25,0,15,4$ using the standard translation of the alphabet to numbers, starting with $A=0$.

Then using simultaneous equations I get:

$10a\equiv-4\pmod{26}$ which can be written as $10a\equiv22\pmod{26}$ as $-4\equiv22\pmod{26}$.

Then dividing by $2$ you get $5a\equiv11\pmod{13}$ so $a\equiv11\cdot5^{-1}\pmod{13}$ then by using the extended euclidean algorithm you can calculate the inverse of $5\bmod 26$ which is $-5\pmod{13}$ or $8\pmod{13}$.

Therefore $a\equiv11\cdot 8 \pmod{13}$, $a\equiv88\pmod{13}$ and so you get $a\equiv10\pmod{13}$.

Therefore $a=10$ and by plugging $a=10$ into $25a+b\equiv0\pmod{26}$,

I get $250+b\equiv0\pmod{26}$ and so $b\equiv-250\pmod{26}$ which then gives $b=10$ and so $(a,b)=(10,10)$.

$\endgroup$
  • $\begingroup$ I am familiar with the Chinese Remainder theorem but not with using the prime factorization to solve. @Moo $\endgroup$ – DavinaGoodman Jan 29 '17 at 11:18
1
$\begingroup$

We indeed know that

  1. $25a + b \equiv 0 \bmod 26$

from 'Z' mapping to 'A' and

  1. $15 a + b \equiv 4 \bmod 26$

from 'P' mapping to 'E' under $E(x) = ax + b \bmod 26$.

subtracting 2 from 1, we get $$10a \equiv -4 \equiv 22 \bmod 26$$

Subtracting 15 times (1) from 25 times (1) the $a$'s cancel and we get

$$10b \equiv 100 \equiv 22 \bmod 26$$ as well.

So we just have to solve $10x \equiv 22 \bmod 26$, and check the answer.

If I'm lazy I open my terminal and in python one can type:

for a in xrange(26): if 10*a % 26 == 22: print a (with proper formatting of course)

and we get 10 and 23 as answers. So we have 4 options to check against the original equations, and both $(23,23)$ and $(10,10)$ work, it turns out. with the former we have a proper decryption function, as $23^{-1} \bmod 26 \equiv 17$. The other option has no decryption function, as $\gcd(10, 26) \neq 1$ .So $(23, 23)$ is actually correct and $D(x) = 17(x-23) \bmod 26$.

For a more mathematical solution to $10x \equiv 22 \bmod 26$, we can follow the algorithm described in these notes (theorem 2.7).

We compute $d = \gcd(10,26) = 2$ and we write (extended Euclidean)

$$2 \cdot 26 -5 \cdot 10 = 2$$

Multiplying this with $11 = \frac{22}{2}$ we get

$$2 \cdot 26 \cdot 11 -5 \cdot 10 \cdot 11= 22$$ which shows (look at it modulo 26) that

$ x =-55= -5 \cdot 11$ is a particular solution to our original equation. Then we add multiples of 13 ($\frac{26}{2}$) for all other solutions, so we get $-55 \equiv -3 \equiv 23 \bmod 26$ is the one and $-3 + 13 = 10$ is the other one, confirming the python script answer.

$\endgroup$

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.