\documentclass[12pt,ifthen]{article}
\usepackage{comment}
\usepackage{url}

\newif{\ifshowsoln}
\showsolntrue
\newcommand{\und}{\_\_\_\_\_\_\_\_\_}
\newcommand{\Z}{\mathbb{Z}}
\usepackage{amsmath}
\usepackage{amssymb}  % for \nmid
\newcommand{\lf}{\left\lfloor}
\newcommand{\rf}{\right\rfloor}
\newcommand{\lc}{\left\lceil}
\newcommand{\rc}{\right\rceil}
\newcommand{\Ceil}[1]{\left\lceil {#1}\right\rceil}
\newcommand{\ceil}[1]{\left\lceil {#1}\right\rceil}
\newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\st}{\mathrel{:}}
\newcommand{\es}{\emptyset}
\newcommand{\bits}[1]{\{0,1\}^{{#1}}}


\begin{document}

\centerline{\textbf{HW 7 CMSC 456. Morally DUE Oct 21}}

{\textbf{NOTE- THE HW IS FOUR PAGES LONG}}


\begin{enumerate}


\item
(0 points)
READ the syllabus- Content and Policy.
What is your name?
What is the day and time of the midterm?



\item
(25 points)
This is a programming assignment.
You will write code that uses the low-$e$ attack to crack a message $m$ encrypted with RSA.
\begin{enumerate}
\item Begin by inputting multiple lines from standard input.
On the first line, the value $e$ will be given, and on the second line, the value $L$ will be given.
(Note that $e$ might be larger than $L$.)
The first two lines will be followed by $2L$ more lines.
The next $L$ lines will consist of the values $N_1,N_2,\ldots,N_L$ (one value on each line).
You can assume that $N_i$ is relatively prime to $N_j$ for each $i \ne j$.
The last $L$ lines will consist of the values $x_1,x_2,\ldots,x_L$ (one value on each line), where each $x_i \equiv m^e \pmod{N_i}$.

\item You will print two lines to standard output.
First, you will use the Chinese Remainder Theorem and the input provided to calculate $m^e \pmod{N_1 \cdots N_L}$; call this value $x$.
(Recall that $0 \le x < N_1 \cdots N_L$.)
Print this value on the first line.

After that, you will check to see if $x$ has an positive integer $e$-th root.
If it does, then print the root on the second line; this should be the value $m$.
(This may exist even when $e > L$.)
If this root does not exist, then print ``failed'' on the second line.
(This will happen only when $e > L$.)

\end{enumerate}

\textbf{NOTE:}
The integer values given via input will be of arbitrary length, so make sure the language you are using supports arbitrary-length integers.
Wtih that said, be careful about how you are checking for / finding roots, as built-in functions may give you unsatisfactory results.
For a simple algorithm that computes integer roots without loss of precision, see 
\url{https://stackoverflow.com/a/15979957}.
\vspace{5mm}

\centerline{\textbf{GO TO NEXT PAGE FOR MORE INFO ON THIS PROBLEM}}
\newpage

You may use C, C++, Java, Python2/3, and Ruby for this problem.
You will be submitting a zip file containing all code files you used to complete this problem to the Gradescope assignment called

\centerline{``hw07 - problem 2''.}
Upon submission, your code will be automatically run on a Linux machine and tested against various test cases to ensure correctness.
You are allowed to submit your code as many times as you want.
As with previous programming assignnments, upload a bash script called \texttt{run} and (if necessary) another bash script called \texttt{build}.
These files must begin with the shebang \texttt{\#!/usr/bin/env bash} on the very first line.
If you have any questions or confusions, or if you encounter any technical difficulties, feel free to ask for help on Piazza.

\vspace{5mm}
\centerline{\textbf{GOTO NEXT PAGE}}
\newpage

\newpage

\item
(25 points) 
\begin{enumerate}
\item
(6 points)
Write Rabin's Encryption algorithm (the original version, not the one
modified).
\item
(6 points)
What is the big advantage of Rabin's Encryption?
\item
(6 points)
What is the big disadvantage of Rabin's Encryption?
\item
(7 points)
Give a scenario where that disadvantage is not a problem.
(We assume that Eve ONLY has access to seeing what Bob sends.
She CANNOT trick Bob into sending anything.)
\end{enumerate}






\bigskip

\centerline{\bf GOTO NEXT PAGE FOR NEXT PROBLEM }

\newpage

\item
(25 points)
(You can assume there is an algorithm that will, given $A,B$ rel prime,
can find $A^{-1} \pmod B$.)

Write a program in pseudocode to do the following
(this is the $L=3$ case of CRT).

Given $N_1,N_2,N_3$ rel prime and $x_1,x_2,x_3$, show that there
exists $x$ such that

\[
\begin{array}{rl}
x\equiv x_1 \pmod {N_1}\cr
x\equiv x_2 \pmod {N_2}\cr
x\equiv x_3 \pmod {N_3}\cr
\end{array}
\]






\bigskip

\centerline{\bf GOTO NEXT PAGE}

\newpage

\item
(25 points)
(We do this problem in BASE 10. Replace $\oplus$ with addition of digits mod 10.)
Alice and Bob are doing the Blum-Goldwasser cryptosystem with
$p=1019$, $q=1051$ (remember, this is in base 10, so $p,q$ are of length 4), 
$r=5432$, and $m=8761$.
What does Bob send? Show all of your work.


\end{enumerate}

\end{document}