Chapter 4: Number Theory and Cryptography

Find each of these values.

a)\(\left( {{\rm{ - 133 }}{\bf{mod}}{\rm{ 23}} + {\bf{2}}61{\rm{ }}{\bf{mod}}{\rm{ 23}}} \right){\rm{ }}{\bf{mod}}{\rm{ 23}}\)

b)\(\left( {45{\bf{7}}{\rm{ }}{\bf{mod}}{\rm{ 23}} \cdot 182{\rm{ }}{\bf{mod}}\;23} \right){\rm{ }}{\bf{mod}}{\rm{ 23}}\)

Show that a positive integer is divisible by 3 if and only if the sum of its decimal digits is divisible by 3.

Explain why you cannot directly adapt the proof that there

are infinitely many primes (Theorem 3 in Section 4.3) to show that are

infinitely many primes in the arithmetic progression 4 k + 1, k = 1,2 ,

Use Euclidean algorithm to find

1. \(\gcd \left( {1,\,5} \right)\)
2. \(\gcd \left( {100,\,101} \right)\)
3. \(\gcd \left( {123,\,277} \right)\)
4. \(\gcd \left( {1529,\,14039} \right)\)
5. \(\gcd \left( {1529,\,14038} \right)\)
6. \(\gcd \left( {11111,\,111111} \right)\)

For each of these initial seven digits of an ISSN, determine the check digit (which may be the letter $\mathbf{X}$).

a) 1570-868

b) 1553-734

c) 1089-708

d) 1383-811

In Exercises $31-32$suppose that Alice and Bob have these public keys and corresponding private keys:

First express your answers without carrying out the calculations. Then, using a computational aid, if available, perform the calculation to get the numerical answers.role="math" localid="1668617920431" $\left(n_{Alice},e_{Aïce}\right)=(2867,7)=(61\cdot 47,7),d_{Ailice}=1183and\left({\mathrm{n}}_{Bob},e_{Bob}\right)=(3127,21)=(59\cdot 53,21),d_{Bob}=1149$

Alice wants to send to Bob the message “BUY NOW” so that he knows that she sent it and so that only Bob can read it. What should she send to Bob, assuming she signs the message and then encrypts it using Bob’s public key?

32. Show that a positive integer is divisible by 11 if and only if the difference of the sum of its decimal digits in even- numbered positions and the sum of its decimal digits in odd-numbered positions is divisible by 11.

Which integers are divisible by 5 but leave a remainderof 1 when divided by 3?

Show that if the smallest prime factor pof the positive

Integer nis larger than $\sqrt[\mathbf{3}]{\mathbf{n}}$, then$\raisebox{1ex}{$\mathbf{n}$}\!\left/ \!\raisebox{-1ex}{$\mathbf{p}$}\right.$is prime or equal to 1.

We describe a basic key exchange protocol using private key cryptography upon which more sophisticated protocols for key exchange are based. Encryption within the protocol is done using a private key cryptosystem (such as AES) that is considered secure. The protocol involves three parties, Alice and Bob, who wish to exchange a key, and a trusted third party Cathy. Assume that Alice has a secret key $k_{Alice}$that only she and Cathy know, and Bob has a secret key $k_{Bob}$which only he and Cathy know. The protocol has three steps:

1. Alice sends the trusted third party Cathy the message “request a shared key with Bob” encrypted using Alice’s key $k_{Alice}$.
2. Cathy sends back to Alice a key $k_{Alice,Bob}$, which she generates, encrypted using the key $k_{Alice,Bob}$, followed by this same key $k_{Alice}$, encrypted using Bob’s key, $k_{Bob}$.
3. Alice sends to Bob the key $k_{Alice,Bob}$encrypted using $k_{Bob}$, known only to Bob and to Cathy.

Explain why this protocol allows Alice and Bob to share the secret key $k_{Alice,Bob}$, known only to them and to Cathy.