Number Theory: In Context and Interactive

1.

Do all the encryptions and/or encodings in Sections 11.1 and 11.2 ‘by hand’.

2.

Encrypt your name using an affine method ($ax+b$) with key $(5,6,29)$ (don't worry about letters), and decrypt BXHBI.

3.

Create your own $ax+b$ (mod $n$) system of encryption and bring an encrypted message to class (or a friend also interested in number theory).

4.

Use the Diffie-Hellman method of encryption to encrypt a short (three to five character) message with a $26<p<50$ ‘by hand’ (i.e. without Sage but with a calculator). Be prepared to explain your choice of $e$ and $p\text{,}$ and calculate that $ef\equiv 1$ (mod $p-1$) by hand.

5.

Draw a diagram and show that if Eve has control of both communications in Diffie-Hellman key exchange (Algorithm 11.4.2), she can intercept and decrypt all messages.

6.

Do this two-parter:

• Suppose you discovered that the message 4363094, where $p=7387543\text{,}$ actually represented the (numerical) message 2718. What steps might you take to try to discover $e\text{?}$

• Suppose that you discovered in the previous part by hard work that $e=35\text{.}$ Now quickly decrypt the message 6618138.

7.

Pick two primes between 1000 and 2000 and create an RSA public key $(n,e)$ for them. What is the decryption key $f\text{?}$ Show your work.

8.

Suppose that $n=9211$ and $e=539\text{.}$

• Encrypt a (short) message.

• Find the decryption key $f$ for this situation, and decrypt your message.

• Use $f$ to sign your name!

9.

Come up with your own RSA public-key system by choosing $p$ and $q$ and $e$ as appropriate, but with $n>10000\text{;}$ then encrypt a short numerical message and hand in only the public key $(n,e)$ and the encrypted message. (Your instructor's job will be to crack it!)

10.

Construct a secret and share it in the way described in Algorithm 11.7.1.

11.

Learn about a symmetric key cryptosystem in common use. Do you own any devices which use it?

12.

Learn about the El-Gamal public key encryption method. How is it implemented? What mathematics used there is similar to what is used in this chapter? What is different?

13.

Learn about the Advanced Encryption Standard. How is the mathematics used there different from what is used in this chapter?

14.

Examine the code for encode and decode throughout, or have your instructor explain it. If you were trying to encode real human communication, what improvements would you like to make to these? Could you implement them, and how?

15.

In Example 11.7.2, explain mathematically the necessity of the Sage comment # First line: turn modular integers back into integers just before the invocation of the Chinese Remainder Theorem with CRT.