\documentclass[11pt]{article}
\include{macros}
\title{Homework 3: Public-Key Cryptography\\
\sc \Large DUE Wednesday, October 10}
\begin{document}
\maketitle
\noindent{\em Cite sources of help, work with other students,
and come see me during office hours (WF at 2pm).  Feel free
to make unrestricted use of PARI in problems 1--7.}

\begin{enumerate}

\item (3 points) You and Nikita wish to agree on a secret key using
the Diffie-Hellman protocol.  Nikita announces that $p=3793$ and
$g=7$.  Nikita secretely chooses a number~$n<p$ and tells you
that $g^n\con 454\pmod{p}$.  You choose the random number 
$m=1208$.  Tell me what the secret key is!

\item (4 points) This problem concerns encoding phrases using numbers.
\begin{enumerate}
\item Find the number that corresponds to 
\verb*|VE RI TAS|, where we view this string as a number in 
base~$27$ using the encoding of Section~2 of Lecture~9.  
(Note that the left-most ``digit'', \verb*|V|, is the
least significant digit, and \verb*| | denotes a blank space.)
\item What is the longest sequence of letters (and space) that
can be stored using a number that is less than $10^{20}$?
\end{enumerate}

\item (4 points) You see Michael and
Nikita agree on a secret key using the Diffie-Hellman key exchange
protocol.  Michael and Nikita choose $p=97$ and $g=5$.  Nikita chooses
a random number~$n$ and tells Michael that $g^n\con 3\pmod{97}$, and
Michael chooses a random number~$m$ and tells Nikita that $g^m\con
7\pmod{97}$.  Crack their code: What is the secret key that Nikita and
Michael agree upon?  What is~$n$?  What is~$m$?

\item (2 points)
Using the RSA public key is $(n,e) = (441484567519, 238402465195)$,
encrypt the year that you will graduate from Harvard. 

\item (6 points) In this problem, you will ``crack'' an RSA cryptosystem.
\begin{enumerate}
\item What is the secret decoding number~$d$ for the RSA 
cryptosystem with public key $(n,e) = (5352381469067, 4240501142039)$?
\item The number $3539014000459$ encrypts an important question using 
the RSA cryptosystem from part (a).  What is the question?  (After decoding,
you'll get a number.  To find the corresponding word, see Section~2 of
Lecture~9.)
\end{enumerate}

\newpage
\item (4 points) 
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$ (\verb*|A| corresponds 
to $1$, \verb*|B| to~$2$, etc., and a space \verb*| | to~$0$), 
then encrypts each number {\em separately} 
using Michael's RSA cryptosystem.  Is this method secure? 
Explain your answer.

\item (6 points)
Nikita creates an RSA cryptosystem with public key
$$(n,e)=(1433811615146881, 329222149569169).$$ 
In the following two problems, show the steps you take. 
Don't simply factor~$n$ directly using the {\tt factor} 
function in PARI.
\begin{enumerate}
\item 
Somehow you discover that $d=116439879930113$.  Show how to use the
probabilistic algorithm of Lecture~10 to use~$d$ to factor~$n$.
\item 
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 Lecture~10 to factor~$n$.
\end{enumerate}

\end{enumerate}


\end{document}