-1
$\begingroup$

I have this lecture slide. I am hoping someone can take me through line by line of how it works, because I cannot understand the a to the power of -1 part.

So far I have

Key(3,5).
EncLetter((3,5), 7) = 3 * 7 + 5 mod 26 = 0
DecLetter((3,5),0) = ???? * (0-5) mod 26 = ???

I need to calculate an inverse or something, but I have no idea.

From the comments it appears that I am very wrong. If someone could please provide a step by step instruction with how to calculate this I would be eternally grateful.

Slide

$\endgroup$
  • $\begingroup$ It's the multiplicative inverse. It's right there in the slide, $a^{-1}$ is the number such that $a^{-1}a \equiv 1 \bmod{26}$. $\endgroup$ – Morgan Rodgers Jul 31 '19 at 0:23
  • $\begingroup$ Mind giving me a line with numbers, sorry I am just awful at maths. $\endgroup$ – plagiarism Jul 31 '19 at 0:24
  • $\begingroup$ $3^{-1} = 9$, since $3\cdot 9 = 27 \equiv 1 \bmod{26}$. $\endgroup$ – Morgan Rodgers Jul 31 '19 at 0:26
  • $\begingroup$ Why is 3 to the power of -1 = 9? How do I plug this into the decrypt line to end up with 7 (the number I encrypted at beginning)? $\endgroup$ – plagiarism Jul 31 '19 at 0:27
  • 2
    $\begingroup$ $3^{-1} = 9$ because $3 \cdot 9 \equiv 1 \bmod{26}$. That's how it is defined. You plug the 9 in where $a^{-1}$ goes (where you have the ????), since $a=3$. You should look up some details about modular arithmetic, otherwise you won't have much chance of learning anything about cryptography. $\endgroup$ – Morgan Rodgers Jul 31 '19 at 0:28
0
$\begingroup$

So your encryption function for a letter $m$ is $3m + 5 \pmod{26}$, and indeed $E(7) = 26 \equiv 0$.

To go back we have to subtract $5$ first and we get $-5 \equiv 21 \pmod{26}$ and then we have to "divide by $3$", which just means, by definition really, to multiply by the inverse of $3$ modulo $26$ and this inverse of $3$ is $9$ as $$3 \times 9 = 27 \equiv 1 \pmod{26}$$

And $21 \times 9 = 189 \equiv 7 \pmod{26}$ as $189 = 7\times 26+7$, or alternatively $-5 \times 9 = -45 \equiv -45 + 52 = 7 \pmod{26}$.

In any case, we get back the $7$, as we should.

So decryption in a formula:

$$D(c) = 9(c-5) \pmod{26}$$

or using that $-45 \equiv 7$, as we saw,

$$D(c) = 9c + 7 \pmod{26}$$

and note that it is of the same form as the encryption formula.

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