Cryptology by Discovery: An Introduction to Conjecture and Proof

1.

Find all solutions to the following discrete log problems or determine that there are no solutions. Note: all solutions does not necessarily mean checking all values 0 to \(n\) for mod \(n\text{.}\) Instead find the pattern for all values of \(x\) that are solutions.

1. \(\displaystyle 3^x \equiv 4 \pmod 5\)

2. \(\displaystyle 3^x \equiv 4 \pmod 6\)

3. \(\displaystyle 3^x \equiv 4 \pmod 7\)

4. \(\displaystyle 3^x \equiv 4 \pmod 8\)

5. \(\displaystyle 3^x \equiv 4 \pmod 9\)

6. \(\displaystyle 3^x \equiv 4 \pmod {10}\)

7. \(\displaystyle 3^x \equiv 1 \pmod 5\)

8. \(\displaystyle 3^x \equiv 1 \pmod 6\)

9. \(\displaystyle 3^x \equiv 1 \pmod 7\)

10. \(\displaystyle 3^x \equiv 1 \pmod 8\)

11. \(\displaystyle 3^x \equiv 1 \pmod 9\)

12. \(\displaystyle 3^x \equiv 1 \pmod {10}\)

2.

As you may have noticed above, not all mods are created equal when it comes to the discrete log problem. Compute the items below and determine which are good mods to use to exchange a secret key. (I.e., when do we get most different values mod \(n\) before repeating?)

1. Compute \(6^x\) mod 13 for \(x=1,2,3,4, \ldots 13\text{.}\)

2. Compute \(6^x\) mod 14 for \(x=1,2,3,4, \ldots 14\text{.}\)

3. Compute \(6^x\) mod 15 for \(x=1,2,3,4, \ldots 15\text{.}\)

4. Compute \(6^x\) mod 16 for \(x=1,2,3,4, \ldots 16\text{.}\)

5. Compute \(6^x\) mod 17 for \(x=1,2,3,4, \ldots 17\text{.}\)

3.

Not all bases are created equal either.

1. Compute \(6^x\) mod 19 for \(x=1,2,3,4, \ldots 19\text{.}\) What bad thing happens here?

2. Find all good bases for mod 19. That is, compute \(a^x \mod{ 19}\) for all \(a\) mod 19 and list the best ones.

3. Is 2 a good base mod 131 in our previous definition?

4. Solve \(2^x \equiv 128 \pmod{131}\) for \(x\text{.}\) This should be easy, why?

5. Solve \(6^x \equiv 17 \pmod{131}\) for \(x\text{.}\) This should not be as easy.

1.

Pick any number, \(x\text{,}\) between 2 and 17.

1. Compute \(y=x^5 \pmod{19}\text{.}\) Now compute \(z=y^{11} \pmod{19}\text{.}\) What's interesting about \(z\text{?}\) Why?
2. Compute \(y=x^7 \pmod{19}\text{.}\) Find a \(b\) such that \(z=y^{b} \pmod{19}\) gives you the same interesting result as before for all \(x\text{.}\) That is, try all \(b\) in \(1,2,\cdots 19\) until you find one that works.
3. Compute \(y=x^3 \pmod{19}\text{.}\) Can you find a \(b\) such that \(z=y^{b} \pmod{19}\) gives you the same interesting result as before? That is, try all \(b\) in \(1,2,\cdots 19\) until you find one that works.

2.

Explain what the code below does. How does it relate to the earlier questions?

3.

Run Sage Computation 5.11.2 but change it to \(n=3\text{.}\) What is the pattern for the values of \(a\text{?}\)

4.

Run Sage Computation 5.11.2 for \(n=5\text{.}\) What is the pattern for the values of \(a\text{?}\)

5.

Run Sage Computation 5.11.2 for \(n=7,11,13\text{.}\) What is the pattern for the values of \(a\text{?}\)

6.

Make a prediction for what will happen for \(n=17\) and use Sage Computation 5.11.2 to check your conjecture. What is the pattern for the values of \(a\text{?}\)

7.

Use your above conjecture for mod 17 to explain Exercise 5.3.16. That is, explain why

1. \(\displaystyle (x^5)^{13} \equiv x \pmod {17}\)
2. \((x^7)^b\equiv x \pmod {17}\) had a solution for \(b\text{.}\)
3. \((x^4)^b\equiv x \pmod {17}\) has no solution for \(b\text{.}\)

8.

Run Sage Computation 5.11.2 for \(n=6\text{.}\) What is the pattern for the values of \(a\text{?}\)

9.

Repeat the above for \(n=9,10,11,\cdots,30\text{.}\) Make a conjecture about when we can find such an \(a>1\) and test your conjecture with a few more mods.

1.

Compute \(C(n,k) \bmod{n}\) as below.

1. Compute \(C(2,k) \bmod{2}\) for \(k=0,1,2\text{.}\)
2. Compute \(C(3,k) \bmod{3}\) for \(k=0,1,2, 3\text{.}\)
3. Compute \(C(4,k) \bmod{4}\) for \(k=0,1,2, 3,4\text{.}\)
4. Compute \(C(5,k) \bmod{5}\) for \(k=0,1,2,\ldots 5\text{.}\)
5. Compute \(C(6,k) \bmod{6}\) for \(k=0,1,2, \ldots 6\text{.}\)
6. Compute \(C(7,k) \bmod{7}\) for \(k=0,1,2,\ldots 7\text{.}\)
7. Compute \(C(8,k) \bmod{8}\) for \(k=0,1,2, \ldots 8\text{.}\)
8. Compute \(C(9,k) \bmod{9}\) for \(k=0,1,2,\ldots 9\text{.}\)
9. Some values of \(n\) are nicer than others. Make a conjecture.

2.

Compute \((x+y)^n \bmod{n}\) as below. Hint: there's a relationship between the calculations above and the calculations below that we discussed once already. It will really help you...

1. Compute \((x+y)^2 \bmod{2}\text{.}\)
2. Compute \((x+y)^3 \bmod{3}\text{.}\)
3. Compute \((x+y)^4 \bmod{4}\text{.}\)
4. Compute \((x+y)^5 \bmod{5}\text{.}\)
5. Compute \((x+y)^6 \bmod{6}\text{.}\)
6. Compute \((x+y)^7 \bmod{7}\text{.}\)
7. Compute \((x+y)^8 \bmod{8}\text{.}\)
8. Compute \((x+y)^9 \bmod{9}\text{.}\)
9. Make a conjecture. It should be connected to your previous conjecture.

1.

Find all numbers \(x\) which satisfy \(x\equiv 1 \pmod{3}\) and \(x\equiv 1 \pmod{5}\text{.}\)

2.

Find all numbers \(x\) which satisfy \(x\equiv 1 \pmod{3}\) and \(x\equiv 1 \pmod{7}\text{.}\) Again, this really means find the pattern for all such numbers \(x\text{.}\)

3.

Find all numbers \(x\) which satisfy \(x\equiv 1 \pmod{5}\) and \(x\equiv 1 \pmod{7}\text{.}\)

4.

Find all numbers \(x\) which satisfy \(x\equiv 1 \pmod{4}\) and \(x\equiv 1 \pmod{6}\text{.}\)

5.

Find all numbers \(x\) which satisfy \(x\equiv 1 \pmod{6}\) and \(x\equiv 1 \pmod{9}\text{.}\)

6.

Make a conjecture. Pick several more values for \(m\) and \(n\) and see if your conjecture accurately predicts when \(x\equiv 1 \pmod{m}\) and \(x\equiv 1 \pmod{n}\text{.}\) If necessary, revise your conjecture.

7.

Prove your conjecture.

1.

Create your own RSA encryption formula.

1. Pick two large primes, \(p\) and \(q\text{.}\) (Say \(p\) and \(q\) bigger than 26. )
2. Compute \(n=p*q\) and \(\phi(n)=(p-1)*(q-1)\text{.}\)
3. Pick \(e\) such that \(\gcd(e, \phi(n))=1\text{.}\)
4. Compute \(d\) such that \(de \equiv 1 \pmod{ \phi(n)}\text{.}\) That is, compute the multiplicative inverse of \(e\) mod \(\phi(n)\text{.}\)
5. What do you publish for the encryption formula \(E(x)=x^e \pmod{ n}\text{?}\)
6. What's your secret decryption formula?

2.

Let's try it out.

1. The message “RK MH JL” was encrypted with RSA using blocks of two letters. The modulus is 713 and the decryption exponent is 19. So the decryption formula is \(D(y)=y^{19} \pmod{ 713}\text{.}\)
2. Use base 26 to convert the blocks of two letters to the numerical equivalent.
3. Use the decryption exponent to decrypt the message by raising each block to the \(d\) and reducing mod \(713\text{.}\) Then convert the numbers back to blocks of two letters using base 26 to get the message.
4. Find the secret \(p\) and \(q\) used to create this RSA. That is, factor 713.
5. Use \(p\) and \(q\) to compute \(\phi(713)\text{.}\)
6. Find the encryption formula, \(E(x)=x^e \pmod{ n}\text{.}\)

3.

Encrypting a message. The public encryption formula is \(x^{61} \pmod{26989}\text{.}\)

1. Convert the message “HI” to decimal by converting from Base 26 to decimal.
2. Encrypt your message using the above formula and convert it to base 26. You should have a 3 letter ciphertext.
3. Break it! Find the decryption exponent and check to make sure you get the message back.

1.

Bob wants to send a signed and encrypted message to Alice. The message is \(M=252 \text{.}\) Compute his signature \(\sigma\) for this message.

2.

Encrypt the message and its signature and find the pair \((M',\sigma')\text{,}\) that Bob should send to Alice.

3.

Alice sends the encrypted message-signature pair of \((M',\sigma')= (159, 42)\) to Bob. Compute the message and check to see if Bob should accept this as a valid message from Alice.

4.

Bob sends the encrypted message-signature pair to Alice of \((M',\sigma')= (425, 616)\text{.}\) Compute the message and check to see if Alice should accept this as a valid message from Bob.