Please Login to access more options.

Problem 9(Simple Shift Repetition)

Let's now devise a way to not only encrypt a message, but also keep track of who has seen the message? There are several ways to do this. Let's look at an example that involves repeated application of the same encrpytion key. For this example, let's use the encryption key $\phi_4:S\to S$ (the simple shift permutation that shifts right 4).

A group of military commanders decide to send messages using a message chain. The message passes sequentially from one person to the next, where at each stage they apply the encryption key to the ciphertext before sending it on. If I want to send the plain text message $attackatdawn$, then I'd send the message $exxegoexhear$ to the person after me in the chain. This person would decipher the text using $\phi_4^{-1}$ (shift left 4), and then apply $\phi_4$ to the cipher text $exxegoexhear$ and then send the ciphertext $ibbiksibliev$ to the person after them in the chain. This would repeat until the message made it to every commander.

  1. You receive the cipher text $skkzgzkomnz$. What is the plain text message? How many people have seen this message?
  2. How many commanders can we include in this encryption scheme and still tell who sent the message?
  3. If we use $\phi_5$ instead of $\phi_4$, how many commanders can we include in this encryption scheme and still tell who sent the message?
  4. Is there an encryption key $\phi_n$ so that $\phi_n^2=\phi_0$. In other words, is there an encryption key $\phi_n$ that will only allow up to two commands to be in the chain?

Solution

  1. In order to decypher the message $skkzgzkomnz$, we need to apply the $\phi_{-4}$ shift until we find a message that makes sense. Upon doing so, we find that $\phi_{-4}^{8}$ gets us to the message $meetateight$. This means that 8 other people have seen the message (including the commander who sent it).
  2. To figure out how many commanders we can include in the encryption chain, we simply need to apply $\phi_{4}$ to the original message $meetateight$ as many times as possible until we get back to the original message. We find then that $\phi_{4}^{13}$ will return $meetateight$ and so we have returned to the original. So we can send the message only to 12 other commanders before we get back to the original message. Notice that applying the it a 13th time gets back to the original and the encrytption would be pretty pointless at that point. Applying it any more than 13 times will make it impossible to determine how many commanders have seen the message previously.
  3. We now use $\phi_{5}$. Applying this to the message $meetateight$ we find that if we apply $\phi_{5}^{26}$ we get back to the original message. So we can have 25 other commanders see the message before we loop back around.
  4. If we really want a tight circle of trust, we can narrow down the number of commanders that can view the message. We want to find $n$ such that $\phi_{n}^{2}=\phi_{0}$. Let $s\in S$ where $S$ is a set of letters in the alphabet. Also, let $\phi_{n}^{2}=\phi_{0}$. We know that $\phi_{n}(s)=p=s+n$ where $p\in S$. Then we have $s+2n=s+n+n=\phi_{n}^{2}(s)=s+26$ (because we know that a shift of 26 is the same output as a shift of 0). By taking the first and last terms in the expression, namely $s+2n=s+26$, we can solve for $n$ by first subtracting an $s$ from either side. Doing so leads us to the expression $2n=26$. After dividing both sides by 2 wee see that $$n=13.$$ Therefore, a shift of $\phi_{13}^{2}$ will get us back to the original message and we can include only one other commander (again, other than ourselves) in our circle of trust.
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.