\documentclass[11pt]{article}
\usepackage{jeffe,handout,multicol,tikz,kgm}

\newcommand{\kgmcomment}[1]{}
\renewcommand{\gcd}{\mathrm{gcd}}
\newcommand{\ord}{\mathrm{ord}}
\newcommand{\priv}{\mathrm{priv}}
\newcommand{\pub}{\mathrm{pub}}

\begin{document}
\headers{Math373}{Homework 11}{Due Fri, Apr. 11, 2014}


%\makeatletter
%\def\@oddfoot{\hfill \tikz \node[draw] {over} ; }
%\makeatother

%\newcommand{\seq}[1]{\left\langle #1\right\rangle}

\newcommand{\compicon}%
{%
	\begin{tikzpicture}[scale=0.15]%
		\draw[double] (0,0) rectangle (1,1) ;
		\begin{scope}[yshift=-5pt]
			\draw (-0.5, -0.5) rectangle (1.5, 0) ;
		\end{scope}
	\end{tikzpicture}
}


\makeatletter
\def\@oddfoot{}
\makeatother

\newcommand{\F}{\mathbb{F}}
\newcommand{\K}{\mathcal{K}}
\newcommand{\M}{\mathcal{M}}
\newcommand{\C}{\mathcal{C}}

\noindent
\textbf{Directions:} Solve the following problems.  All written work must be your own.  See the course syllabus for detailed rules.

\begin{enumerate}

\newcommand{\dr}[3]%
{%
	$x^{#1} \equiv #2 \pmod{#3}$%
}

\item {} [JJJ 3.6] Alice publishes her RSA public key $(N,e) = (2038667, 103)$.
\begin{enumerate}
	\item Bob wants to send Alice the message $m=892383$.  What ciphertext does Bob send to Alice?
	\item Alice knows that her modulus factors into a product of two primes, one of which is $p=1301$.  Find a decryption exponent $d$ for Alice.
	\item Alice receives the ciphertext $c=317730$ from Bob.  Decrypt the message.
\end{enumerate}

\item {} [JJJ 3.7] Bob's RSA public key has modulus $N=12191$ and exponent $e=37$.  Alice sends Bob the ciphertext $c=587$.  Unfortunately, Bob has chosen too small a modulus.  Help Eve by factoring $N$ and decrypting Alice's message.  \emph{Hint:} $N$ has a factor that is less than $100$.

\item {} [JJJ 3.8] For each of the given values $N=pq$ and $N'=(p-1)(q-1)$, use the method in the proof that \textbf{FactorN} is at least as easy as \textbf{ComputeN'} to find $p$ and $q$.
\begin{enumerate}
	\item $N = 352717$ and $N' = 351520$
	\item $N = 28424293$ and $N' = 28411488$
	\item $N = 111702827046011$ and $N' = 111702805302024$.
\end{enumerate}

\item {} Consider the following two problems.
\begin{paragraph}{FactorN} Given an integer $N$ that is the product of distinct, unknown primes $p$ and $q$, output $p$ and $q$.
\end{paragraph}
\begin{paragraph}{Reduce} Given an integer $a$ and an integer $N$ that is the product of distinct, unknown primes $p$ and $q$ with $p<q$, output $b\in \Z_p$ and $c\in \Z_q$ such that $a\equiv b\pmod{p}$ and $a\equiv c\pmod{q}$.
\end{paragraph}
\begin{enumerate}
	\item Prove that $\textbf{Reduce} \le \textbf{FactorN}$.
	\item Prove that $\textbf{FactorN} \le \textbf{Reduce}$.
	\item Illustrate part (b) by factoring $N = 446846784807308867$.  Given $a=723728945230$ and $N$, your black box for \textbf{Reduce} reports that $a\equiv 299450419 \pmod{p}$ and $a\equiv 316955067 \pmod{q}$.
\end{enumerate}
\end{enumerate}
\end{document}
