\documentclass[12pt]{amsart}

\input{../../TeX/macros}

\usepackage{fullpage}

\begin{document}

\title[Math 75 Homework \#6]{Math 75: Mathematical Cryptography \\ Homework \#6}
\date{Due Wednesday, 11 May 2016}

\maketitle

\section*{Problems}

\begin{problab}{1}
Alice publishes her RSA public key: modulus $n=2038667$ and exponent $e=103$.
\begin{enumalph}
\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{enumalph}
\end{problab}

\begin{problab}{2}
Alice uses the RSA public key modulus $n=pq=172205490419$.  Through espionage, Eve discovers that $(p-1)(q-1)=172204660344$.  Determine $p,q$.
\end{problab}

\begin{problab}{3}
Bob uses RSA to receive a single ciphertext $b$ corresponding to the message $a$.  Suppose that Eve can trick Bob into decrypting a single chosen ciphertext $c$ which is not equal to $b$.  Show how Eve can recover $a$.
\end{problab}

\begin{problab}{4}
Suppose that Alice and Bob have the same RSA modulus $n$ and suppose that their encryption exponents $e$ and $f$ are relatively prime.  Charles wants to send the message $a$ to Alice and Bob, so he encrypts to get $b=a^e \pmod{n}$ and $c=a^f \pmod{n}$.  Show how Eve can find $a$ if she intercepts $b$ and $c$.
\end{problab}

\begin{problab}{5}
A \emph{Carmichael number} is an integer $n>1$ that is \emph{not} prime with the property that for all $a \in \Z$, $a^n \equiv a \pmod{n}$.  Prove that $561,1105,1729$ are Carmichael numbers.  \emph{[Hint: Look at the proof of $a^{ed} \equiv a \pmod{n}$, $n=pq$, in RSA.  You may factor these numbers!]}
\end{problab}

\end{document}