Cryptology by Discovery: An Introduction to Conjecture and Proof

1.

Finish all investigations from in-class activities.

2.

A message was encrypted with the affine cipher \(CT\equiv 5PT+1 \pmod{26}\text{.}\)

1. Solve for the DECRYPTION formula.

2. Then use the decryption formula to decrypt the ciphertext, OPOUB.

3.

Find all possible values of \(a\) and \(b\) that would solve the pairs of linear congruences below. Then determine which, if any, values of \(a\) and \(b\) would be a valid affine cipher (i.e., would be decryptable). If there are no possible values of \(a\) and \(b\) explain why not.

1. The pair of equations:

   \begin{equation*} 15 \equiv 2a+b \mod 26 \\ 18 \equiv 3a+b \mod 26 \end{equation*}

2. The pair of equations:

   \begin{equation*} 15 \equiv 2a+b \mod 26 \\ 19 \equiv 3a+b \mod 26 \end{equation*}

3. The pair of equations:

   \begin{equation*} 15 \equiv 4a+b \mod 26 \\ 18 \equiv 14a+b \mod 26 \end{equation*}

4. The pair of equations:

   \begin{equation*} 15 \equiv 4a+b \mod 26 \\ 19 \equiv 14a+b \mod 26 \end{equation*}

5. The pair of equations:

   \begin{equation*} 15 \equiv 3a+b \mod 26 \\ 2 \equiv 8a+b \mod 26 \end{equation*}

6. The pair of equations:

   \begin{equation*} 19 \equiv 3a+b \mod 26 \\ 3 \equiv 7a+b \mod 26 \end{equation*}

4.

Suppose we have a language with only 12 letters. How many affine ciphers would there be? (You should know how many multiplicative ciphers from a previous homework).

5.

For each number \(\{0,1,2,3, \cdots ,12 \}\) which has a multiplicative inverse mod 13, give the multiplicative inverse.

6.

Find all solutions to the equations below or explain why there are none.

1. \(\displaystyle 4x \equiv 5 \pmod{16}\)

2. \(\displaystyle 4x \equiv 12 \pmod{16}\)

3. \(\displaystyle 8x \equiv 4 \pmod{16}\)

4. \(\displaystyle 8x \equiv 8 \pmod{16}\)

5. \(\displaystyle 10x \equiv 6 \pmod{16}\)

6. \(\displaystyle 10x \equiv 5 \pmod{16}\)

7. \(\displaystyle 12x \equiv 4 \pmod{16}\)

8. \(\displaystyle 12x \equiv 10 \pmod{16}\)

7.

Show using the definition of modular arithmetic that 2 does not have a multiplicative inverse mod \(n\) if \(n\) is even. That is, you should show this directly from the definition and not using any theorems about multiplicative inverses.

8.

Assume that \(a\) is a valid multiplier for an affine cipher,

and \((CT_1-CT_2)\) is even. Use an integer equation and what you know about even and odd numbers to show that \((PT_1-PT_2)\) must be even. (That is, do not use the theorem that we haven't fully proved about when congruences have a solution mod \(n\text{.}\))

9.

Assume that \(a\) is a valid multiplier for an affine cipher,

and \((CT_1-CT_2)\) is odd. Use an integer equation and what you know about even and odd numbers to show that \((PT_1-PT_2)\) must be odd. (That is, do not use the theorem that we haven't fully proved about when congruences have a solution mod \(n\text{.}\))

10.

Find the solution for \(x\) in the following congruences:

Make a conjecture about the multiplicative inverse of 2 mod \(n\) for odd \(n\text{.}\) Prove it.

11.

Find the solution for \(x\) in the following congruences:

Make a conjecture about the multiplicative inverse of 3 mod \(n\) for \(n\) of this form. Also come up with a definition for what of this form means.

12.

Find the solution for \(x\) in the following congruences:

Make a conjecture about the multiplicative inverse of 3 mod \(n\) for \(n\) of this form. Also come up with a definition for what of this form means.

13.

Explain what each line of the following Sage code does.

14.

Solve for \(a,b,c,d,e\text{.}\)