Cryptology by Discovery: An Introduction to Conjecture and Proof

1.

Finish all investigations from in-class activities.

2.

We can use Fermat's Little Theorem to simplify exponents in the following way. Since \(x^{16} \equiv 1 \pmod {17}\) we can simplify \(x^{20} = x^{16}x^{4} \equiv 1*x^4 = x^ 4 \pmod{17} \text{.}\) Use Fermat's Little Theorem to reduce the following congruences. Explicitly show how you are using the theorem the simplify the exponent. All of the mods are prime numbers.

1. \(\displaystyle 2^{23} \bmod 23\)

2. \(\displaystyle 2^{92} \bmod 23\)

3. \(\displaystyle 19^{500} \bmod 101\)

4. \(\displaystyle 3^{204} \bmod 101\)

5. \(\displaystyle 99^{323} \bmod 107\)

3.

Use Fermat's Little Theorem to find a multiplicative inverse of \(a \bmod p\text{.}\)

4.

Recall Euler's theorem says that \(x^{\phi(n)} \equiv 1 \pmod{n}\text{.}\) We can use Euler's Theorem to simplify exponents in the same way as you used Fermat's Little Theorem. Since \(x^{10} \equiv 1 \pmod {22}\) we can simplify \(x^{22} = x^{10}*x^{10}x^{2} \equiv 1*1*x^2 = x^ 2 \pmod{22} \text{.}\) Use Euler's Theorem to reduce the following congruences. Explicitly show how you are using the theorem the simplify the exponent. All of the mods are \(p*q\) for two distinct primes \(p\) and \(q\text{.}\)

1. \(\displaystyle 2^{27} \bmod 21\)

2. \(\displaystyle 2^{81} \bmod 55\)

3. \(\displaystyle 10^{148} \bmod 39\)

4. \(\displaystyle 3^{200} \bmod 85\)

5. \(\displaystyle 9^{106} \bmod 106\)

5.

Alice has published the modulus 22897 and exponent 7, so her encryption formula is \(CT=x^7 \pmod{22897}\text{.}\) Use a three letter base twenty-six encoding and RSA to encipher the following messages to her. Convert them to three or four letters using base 26 for your final answer.

1. LIE

2. MAD

3. SUN

6.

For an RSA encryption scheme you have chosen an encryption formula of \(E(x) = x^{113} \bmod 17741\text{.}\) Find your decryption formula. Then use it to decrypt the following messages. Last, use a base 26 conversion for the plaintext.

1. 13667

2. 4202

7.

For an RSA encryption scheme you have chosen an encryption formula of \(E(x) = x^{5093} \bmod 17617\text{.}\) Find your decryption formula. Then use it to decrypt the following messages. Assume that each block of five decimal digits represents a block of three letters. Decrypt each block separately. \(14438 \qquad 4108 \qquad 511 \qquad 3560 \qquad 16470 \qquad 1247\)

8.

For an RSA encryption scheme you have chosen an encryption formula of \(E(x) = x^{293221} \bmod 2885500349\text{.}\) Find your decryption formula. Then use it to decrypt the following messages using blocks of five letters. Decrypt each block separately.

9.

Use Induction to prove that \(1^2+2^2+3^2 + \cdots +n^2 = \frac{n(2n+1)(n+1)}{6}\) for all \(n \geq 1\text{.}\)

10.

Use induction to prove the finite geometric series formula (given below) from Calculus is true for any integer \(n \ge 0\text{.}\)

(You've probably proved this before (in Calculus) without induction, but you must use induction here.) Remember \(a\) and \(r\) are any real numbers, so they are not necessarily integers. Your induction should be with respect to \(n\text{.}\)

11.

Suppose \(n=p^2t\) for a prime \(p\) and an integer \(t \ge 1\text{.}\)

1. Prove that if \(x=pt\) then \(x^a \equiv 0 \pmod{n}\) for any integer \(a \ge 2\text{.}\)
2. Prove that if \(x=pt\) then \(x \not\equiv 0 \pmod{n}\text{.}\)
3. Explain what this tells you about which \(n\) will not have an \(a \ge 2\) such that \(x^a \equiv x \pmod{n}\) for all \(x\text{.}\)

12.

Let \(p,q\) be distinct primes. Use Theorem 5.5.8 to prove that if \(p\) is a prime and \(a=1+\phi(pq)k\) for an integer \(k\) then \(x^a \equiv x \pmod{p}\) for all \(x\text{.}\) There should be two cases for \(x\text{.}\) Case 1: \(\gcd(x,p)=1\text{.}\) Case 2: \(\gcd(x,p) \neq 1\text{.}\)

13.

Use a definition of modular arithmetic to prove that if \(p\) and \(q\) are distinct primes, \(x \equiv a \pmod{p}\) and \(x \equiv a \pmod{q}\) then \(x \equiv a \pmod{pq}\)

14.

Let \(p,q\) be distinct primes. Use the two previous problems to show that if \(p\) is a prime and \(a=1+\phi(pq)k\) for an integer \(k\) then \(x^a \equiv x \pmod{pq}\) for all \(x\text{.}\) Note, you already proved this mod \(p\text{,}\) you need to extend it to mod \(pq\text{.}\)

15.

Explain why RSA works in general. That is, explain why \(D(E(x)) \equiv x \bmod n\text{.}\) Does the order matter? Is it also true that \(E(D(x)) \equiv x \bmod n\text{?}\) Explain why or why not.

16.

Consider the following recursive algorithm for any integer \(M\text{.}\)

1. Compute \(C_3, C_4, C_5, C_6\) as powers of \(M\text{.}\) For example, \(C_2=M^3\text{.}\)
2. Find a formula for \(j\) in terms of \(k\) where \(C_k=M^j\text{.}\) (Use your above examples to identify the pattern.) Hint
   Examining powers of 2 maybe be helpful.
3. Prove your formula \(C_k=M^j\) by induction.
4. What's the connection to binary?

17.

Read the article about the secret history of public key cryptography https://www.schneier.com/essays/archives/1998/04/the_secret_story_of and write a paragraph about something interesting you learned.