Please Login to access more options.

Problem 43 (Affine Encryption Key Introduction)

If we let $m=31$, then we can use the function $f(x)=5x+12\pmod m$ to encrypt the message "save them" by (1) swapping the letters to the numbers (19,1,22,5,0,20,8,5,13) and then (2) applying $f(x)$ to each letter to obtain the encrypted numbers (14, 17, 29, 6, 12, 19, 21, 6, 15).

  1. Find $c,d\in \mathbb{Z}_{31}$ so that the inverse of $f$ is $f^{-1}(x)=cx+d$ where $c,d\in \mathbb{Z}_{31}$.
  2. If instead we let $m=27$, then find the inverses of $f(x)=2x+17\pmod{27}$ or explain why it cannot be done.
  3. Give an example of nonzero $a,b\in \mathbb{Z}_{27}$ so that $f(x)=ax+b\pmod{27}$ is not invertible.

Solution

Let $m=31$ and let $f$ be the function that maps from $\mathbb{Z}_{m}$ to $\mathbb{Z}_{m}$ defined by $f(x)=5x+12 \pmod m$ that we will use to encrypt the message "savethem" (after swapping to numbers in $\mathbb{Z}_{m}$). In numbers, our message becomes (19, 1, 22, 5, 0, 20, 8, 5, 13). After applying our encryption function to each entry we get the message (14, 17, 29, 6, 12, 19, 21, 6, 15). We want to know if we can find a function $f^{-1}:\mathbb{Z}_{m}\rightarrow \mathbb{Z}_{m}$ that is the inverse of $f$ and, hence, will decrypt our encoded message.

1. We will start by finding $c,d \in \mathbb{Z}_{31}$ such that $f^{-1}(x)=cx+d \pmod {31}$. We know that $f^{-1}(f(x))=f(f^{-1}(x))=x$. We compute $$\begin{array}{rl} x=f^{-1}(f(x))=f(f^{-1}(x)) &=5(cx+d)+12 \pmod {31}\\ &=5cx+5d+12 \pmod {31}\\ &=(5cx\mod 31 +5d\mod 31 +12\mod 31)\mod 31\\ &=(((5c\mod 31)(x\mod 31)\mod 31 + 5d\mod 31 +12)\mod 31. \end{array}$$

We can easily solve for $d$ by setting $(5d\mod 31 +12)\mod {31}=0$. This means $5d\mod 31 = -12\mod 31 = 19\mod 31 = 50\mod 31$ and hence $d=10$. Now we must solve for $c$. We now compute $$\begin{array}{rl} x&=(((5c\mod 31)(x\mod 31)\mod 31 + 5d\mod 31 +12)\mod 31\\ &=(((5c\mod 31)(x\mod 31)\mod 31 + 0)\mod 31\\ &=(((5c\mod 31)(x\mod 31)\mod 31)\mod 31\\ &=(((5c\mod 31)x)\mod 31)\mod 31\\ &=((5c\mod 31)x)\mod 31. \end{array}$$

Clearly the equality above will be true when $5c\mod 31=1$ In other words $c$ is the multiplicative modular inverse of 5 in $\mathbb{Z}_{31}$. Hence, $c=25$. Therefore, $f^{-1}(x)=25x+10$. Though the result looks pretty, it's always a good idea to check if it really is the inverse of $f$. Let $a\in \mathbb{Z}_{31}$. We will show that $f^{-1}(f(a))=a=f(f^{-1}(a))$. Let us quickly compute $$\begin{array}{rl} f^{-1}(f(a)) &=25(5a+12)+10 \pmod {31}\\ &=(25*5a+25*12+10)\mod 31\\ &=(25*5a\pmod {31}+25*12\pmod {31}+10)\mod 31\\ &=((-6)5a\pmod {31}+(-6)*12\pmod {31}+10)\mod 31\\ &=((-6)5a\pmod {31}-10+10)\mod 31\\ &=((-6)5a\pmod {31}+0)\mod 31\\ &=((-6)5a\pmod {31})\mod 31\\ &=-30a\mod 31\\ &=1a\mod 31\\ &= a\\ &=a\mod 31\\ &=(a+0)\mod 31\\ &=(a+31)\mod 31\\ &=(1a+19+12)\mod 31\\ &=((-30a\mod 31)+(50\mod 31)+12)\mod 31\\ &=(((-30a+50)\mod 31)+12)\mod 31\\ &=(5(-6a+10)\pmod {31}+12)\mod 31\\ &=(5(25a+10)\pmod {31}+12)\mod 31\\ &=(5(25a+10)+12)\pmod {31}\\ &=f(f^{-1}(a)). \square \end{array}$$

2. Now let $m=27$ and $f:\mathbb{Z}_{27}\rightarrow \mathbb{Z}_{27}$ be defined by $f(x)=2x+17\pmod {27}$. We will show that $f^{-1}(x)=14x+5\pmod {27}$ is the inverse of $f$. Let $b\in \mathbb{Z}_{27}$. First we compute

$$\begin{array}{rl} f^{-1}(f(b)) &=14(2b+17)+5 \pmod {27}\\ &=(28b+14*17+5)\mod 27\\ &=((28\mod 27*b)\mod 27+(14*17)\mod 27+5)\mod 27\\ &=(1b\mod 27+(14*(-10))\mod 27+5)\mod 27\\ &=(b+(-140)\mod 27+5)\mod 27\\ &=(b-5+5)\mod 27\\ &=b\mod 27\\ &= b. \end{array}$$

Now we must show $f(f^{-1}(b))=b$. Let us compute

$$\begin{array}{rl} f(f^{-1}(b)) &=2(14b+5)+17 \pmod {27}\\ &=(28b+10+17)\mod 27\\ &=(28b+27)\mod 27\\ &=(28b\mod 27+27\mod 27)\mod 27\\ &=(1b\mod 27)\mod 27\\ &= b. \end{array}$$

Because $f^{-1}(f(b))=f(f^{-1}(b))=b$ we know that $f^{-1}$ is the inverse of $f$ in $\mathbb{Z}_{27}.\square$

3. Based upon the method above, finding a new function $g:\mathbb{Z}_{27}\rightarrow \mathbb{Z}_{27}$ defined by $g(x)=ax+b$ for some $a,b\in \mathbb{Z}_{27}$ that is not decryptable simply relies on the fact that for it to not be invertible, $a$ must not have a multiplicative modular inverse in $\mathbb{Z}_{27}$. Therefore, pick $a=9$ and $b=13$. Then $g(x)=9x+13$ is not invertible and hence not decryptable.

Tags
  • When you are ready to submit this written work for grading, add the phrase [[!Submit]] to your page. This will tell me that you have completed the page (it's past rough draft form, and you believe it is in final draft form). Don't type [[!Submit]] on a rough draft.
  • If I put [[!NeedsWork]] on your page, then your job is to review what I've written, address any comments made, and then delete all the comments I made. When you have finished reviewing your work, leave [[!NeedsWork]] on your page and type [[!Submit]]. (Both tags will show up). This tells me you have addressed the comments.
  • I'll mark your work with [[!Complete]] after you have made appropriate revisions.