\documentclass[ oneside]{amsart}
\input{definitions.tex}
\setlist[enumerate,1]{itemsep=1em}


\title{Math 75, Final Cipher Challenge}
\date{Due noon on Tuesday, June 5th, 2018}
\begin{document}
\maketitle

The solution to each of the following ciphers is a codeword: this codeword is either the keyword (or key phrase) or a secret word or phrase contained in the plaintext.  Your mission is to discover these codewords.
\vspace{1em}

In a few cases, the plaintexts of earlier ciphers contain clues for the later ones.
\vspace{1em}

You have two options to turn in your final exam:
\begin{enumerate}
\item Deliver your completed solution to my office (Kemeny 339) on Tuesday,  June 5th, 2018, between 10:00 a.m.\ and noon; or
\item Email me (\verb|edgar.costa@dartmouth.edu|) your completed solution in one file by noon on Tuesday, June 5th, 2018.  (I am a bit more relaxed about this, but please do not spam me with a bunch of different documents.)
\end{enumerate}

\vspace{1em}
No late exams will be accepted.
\vspace{1em}

Show your work, and please be neat! 
No need to be laboriously detailed, but please indicate clearly your method of attack.
\vspace{1em}

If you use any computational resources, please print out and attach all code and output.  (References to code can be given, but you must also show the run and output.)  Feel free to use the SageMath notebook server:
\begin{center}
\verb|https://doob.dartmouth.edu/|
\end{center} 
\vspace{1em}
You are free to (re)use any code, algorithm, or method from classwork or homework, and you may use any programming language you like.  However, the rules for cooperation are completely different than for the homework.  You may not work with anyone else.  No communication about the exam is permitted with anyone except the instructor.  In particular, do not give away solutions and do not share code.  You may \emph{not} use code that is not yours: for example, do not use random web applets.
Exceptions to this rule will be allowed on a case-by-case basis---but contact me first!  The intent of this policy is to ensure that you are the only author of the work you turn in, not to obstruct good work.  If you consult or use any resource other than the textbooks or classwork, state this clearly.


\vspace{1em}
If you are stuck---or just anxious---about one of your solutions, please come talk to me or send me an e-mail!  I will be happy to help (at no penalty).


\vspace{1em}
Have fun and good hunting!

\newpage


\section*{Cipher 1: Substitution cipher}
\begin{verbatim}
NOCRCFSKSDATRGTSDJFHTXXCOOCCSFJSKCRRHDICVXSJCNNRFATXPCNLFJSP
TCJTNRFATXTRXCJGDKNCCSFJSXCCZTSSCOJCJTFKMFRFKDICVXSNCOLTRTDN
PTJNDJNLTVJSTRGRCONLNLTJNCCZNLTCNLTRFKQVKNFKMFDRFJSLFADJGETR
LFEKNLTPTNNTRIXFDWPTIFVKTDNOFKGRFKKHFJSOFJNTSOTFRNLCVGLFKMCR
NLFNNLTEFKKDJGNLTRTLFSOCRJNLTWRTFXXHFPCVNNLTKFWTFJSPCNLNLFNW
CRJDJGTBVFXXHXFHDJXTFATKJCKNTELFSNRCSSTJPXFIZCLDZTENNLTMDRKN
MCRFJCNLTRSFHHTNZJCODJGLCOOFHXTFSKCJNCOFHDSCVPNTSDMDKLCVXSTA
TRICWTPFIZNLTZTHOCRSDKRCPTRNMRCKNDJFJRKFERCPXTWNLTCRSTRCMKTA
TJWCSVXCEDKKWFXX
\end{verbatim}

\section*{Cipher 2: Affine cipher}

Eve intercepts the ciphertext
\begin{verbatim}
36333, 28512, 64818, 20428, 47277, 59369, 47116, 45798, 5832,
17660, 61146, 53877, 15849, 4382, 52990, 27892, 48922, 50914,
13506, 24094, 59369, 64818, 56435, 46740, 19320, 52990, 52427,
52990, 27892, 48922, 50914, 63538, 63894, 24094, 48761, 27892,
55522, 2327, 61873, 28478, 50914, 27726, 15787, 43074, 48922,
62724, 58778, 21375, 25012
\end{verbatim}
and the first part of the corresponding plaintext:
\begin{verbatim}
19561, 27769, 11296, 27753 = "Lily, li"
\end{verbatim}
Charlie, an enemy agent, was also captured.  Using enhanced interrogation techniques, Eve was able to able to extract the following information: Alice uses an affine cipher, and the plaintext alphabet consists of blocks of two letters written as ASCII bytes and then interpreted as an integer modulo $n$.  Unfortunately, Charlie suffered a medical incident before he could disclose $n$.



\section*{Cipher 3: Diffie--Hellman key exchange}

\begin{verbatim}
alice> hey bob hwru
bob> im gr8
alice> hv d secret g?
bob> ys
alice> prv it
alice> p = 1267650600228229401496703206331
alice> a = 49999
alice> compute g^a
bob> 296457517204821239980675720629
eve> LULZ, gg!
\end{verbatim}


\newpage

\section*{Cipher 4: RSA}

\begin{verbatim}
bob> xo alice, i need da secret key
bob> but eve can here us
eve> yellow!
bob> n = 4717336290102780582748894390821225413188288889113
bob> e = 2^150+1
bob> did u here abt charlie? cr8zy m8!1!
alice> that exponent has been compromised;
alice> a decryption exponent is the RSA patent number
bob> whatevs, FINE
bob> e = 65537
alice> y = 4661875409422862513191456400914162950720547233173
bob> c u l8r
eve>  Oh My!
\end{verbatim}

\section*{Cipher 5: RSA}

\begin{verbatim}
alice> hey bob hwru
bob> im gr8
bob> you ready? charlie want's to send us a message!
bob> n = 49355407517652738747237894951599690330136219174468963851
         68710088518492057924984638275768694615065921707914550359
alice> so c00l that we have the same modulus, so much more secure
alice> i dont really understand how to make my own primes :(
bob> no prob babe
alice> e = 65537 for me
bob> f = 100003 for me
charlie> hi guys, here is the wink wink nudge nudge for the you-know-what
charlie> alice: 15659657095750953485391727452558125654804182968195094456
                10680154594806215008779386260086970987024419051815666857
charlie> bob:   25787807560748679203350537953390487929765480402443820081
                42867283646315447148403107899963979076896422755472504783
charlie> i just ASCII'ed the whole thing, no blocks or anything fancy
eve> LOL
\end{verbatim}



\section*{Cipher 6: RSA}

\begin{verbatim}
n = 383633773376436494825661493028463559109071281655
    79457714343557347024260093135367748083611439063
e = 65537
y = 197587870368985566489553503279074785837735738587
    6293479689194217250273958292525224542496676604
\end{verbatim}

The plaintext is written in base 26.


\newpage
\section*{Cipher 7: Diffie--Hellman key exchange}

\begin{verbatim}
alice> Dude, look at this p!
alice> 63232914709219964600000000000000000000000000000095481701210922146547
bob> WILD! let's use it
bob> g = 2 as always!
alice> 11824133099297351280364249735666699054153772699598949884103771866349
bob> 18958445374903586524651007339890684505843652541505582097475315564406
alice> OK, I will use our common secret to send you a message
alice> I don't trust ASCII--I think it's rigged.
alice> I'm just going to write my message as an integer like
alice>    h e l l o = 07 04 11 11 14 = 704111114
alice> Here it is:
alice> 53456973083714162968699703191207469271682900420160385590785505317428
\end{verbatim}

\section*{Cipher 8: Elliptic curve discrete logarithm}

\noindent The elliptic curve $E:y^2=x^3+x$ \\
having field of definition $\mathbb{F}_p$ with $p=2^{89}-1$ \\
is used in an elliptic curve cryptosystem by Alice in Wonderland.  \\
``No wise fish would go anywhere without a porpoise.''  \\
Known is the point $P=(408358146153463289622115164, 160614043710190468600357775)$; \\
she hides a secret codeword in the \\
multiple $a$ of $P$ written in base $26$, not the \\
ordinate or anything.  This multiple is \\
observed by the trolling bellman to be 
$$aP=(553896511907353224105489574, 594394227295626927732292957).$$
The discrete logarithm problem is supposed to be \\
hard, right?  \\
``!`To grow larger and reach the key, just keep doubling!,'' advises the doorknob.

\section*{Cipher 9: Elliptic curve ElGamal}

Elliptic curve ElGamal is used with the following parameters:
\begin{itemize}
\item $p=2^{31}-1 = 2147483647$
\item $E:y^2=x^3+x+1$ over $\mathbb{F}_p$
\item $G=(493644129,2069524559)$
\end{itemize}
Bob sends the point
\[ (928984375, 811839063) \in E(\mathbb{F}_p). \]
Alice encodes her keyword as the $x$-coordinate of a point on $E$, and she sends the pair of points
\[ ((1004499824,1398370638), (270353101, 1452301961)). \]

\end{document}
