Exercises

3..

1. This problem concerns encoding phrases using numbers using the encoding of Section 3.2.2. What is the longest that an arbitrary sequence of letters (no spaces) can be if it must fit in a number that is less than $10^{20}$ ?

2. Suppose Michael creates an RSA cryptosystem with a very large modulus $n$ for which the factorization of $n$ cannot be found in a reasonable amount of time. Suppose that Nikita sends messages to Michael by representing each alphabetic character as an integer between 0 and $26$ (A corresponds to $1$ , B to $2$ , etc., and a space to 0 ), then encrypts each number separately using Michael's RSA cryptosystem. Is this method secure? Explain your answer.

3. For any $n\in\mathbb{N}$ , let $\sigma(n)$ be the sum of the divisors of $n$ ; for example, $\sigma(6) = 1+2+3+6=12$ and $\sigma(10)=1+2+5+10=18$ . Suppose that $n=pqr$ with $p$ , $q$ , and $r$ distinct primes. Devise an ``efficient'' algorithm that given $n$ , $\varphi (n)$ and $\sigma(n)$ , computes the factorization of $n$ . For example, if $n=105$ , then $p=3$ , $q=5$ , and $r=7$ , so the input to the algorithm would be
   $$n = 105,\qquad \varphi (n) = 48,$$   and$$\quad \sigma(n)=192,$$
   and the output would be $3$ , $5$ , and $7$ .

4. You and Nikita wish to agree on a secret key using the Diffie-Hellman key exchange. Nikita announces that $p=3793$ and $g=7$ . Nikita secretly chooses a number $n<p$ and tells you that $g^n\equiv 454\pmod{p}$ . You choose the random number $m=1208$ . What is the secret key?

5. You see Michael and Nikita agree on a secret key using the Diffie-Hellman key exchange. Michael and Nikita choose $p=97$ and $g=5$ . Nikita chooses a random number $n$ and tells Michael that $g^n\equiv 3\pmod{97}$ , and Michael chooses a random number $m$ and tells Nikita that $g^m\equiv 7\pmod{97}$ . Brute force crack their code: What is the secret key that Nikita and Michael agree upon? What is $n$ ? What is $m$ ?

6. In this problem, you will ``crack'' an RSA cryptosystem. What is the secret decoding number $d$ for the RSA cryptosystem with public key $(n,e) = (5352381469067, 4240501142039)$ ?

7. Nikita creates an RSA cryptosystem with public key
   $$(n,e)=(1433811615146881, 329222149569169).$$
   In the following two problems, show the steps you take to factor $n$ . (Don't simply factor $n$ directly using a computer.)
   1. Somehow you discover that $d=116439879930113$ . Show how to use the probabilistic algorithm of Section 3.3.3 to use $d$ to factor $n$ .
   2. In part (a) you found that the factors $p$ and $q$ of $n$ are very close. Show how to use the Fermat factorization method of Section 3.3.2 to factor $n$ .