\documentclass[12pt]{article}
\usepackage{graphics}
\usepackage{epsfig}
\usepackage{comment}
\usepackage{amsmath}
\usepackage{amssymb}  % for \nmid
\newcommand{\bits}[1]{\{0,1\}^{{#1}}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}

\renewcommand{\Pr}{{\rm Pr}}
\newcommand{\prob}{{\rm prob}}
\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{\abit }{\hat{a}}
\newcommand{\bbit }{\hat{b}}

\newcommand{\nth}{n^{th}}

\begin{document}

  \centerline{\bf CMSC-MATH-ENEE 456 Timed Final, Fall 2021}


  \begin{enumerate}

    \addtolength{\itemsep}{-2mm}  % reduced space between lines

    \item This is an open-book, open-slides, open-web exam.

    \item  There are 4 problems which add up to 50 points.

    \item In order to be eligible for as much partial credit as possible,
          show all of your work for each problem, \textbf{write legibly},
          and \textbf{clearly indicate} your answers.  Credit
          \textbf{cannot} be given for illegible answers.

    \item Please write out the following statement:
          ``\textit{I pledge on my honor that I
          will not give or receive any unauthorized assistance on this
          examination\/}.''  

\bigskip
\bigskip

          \bigskip \bigskip
\item
Fill in the following:

\[
\begin{array}{rl}
{\rm NAME: } & \cr
{\rm SIGNATURE: } & \cr
{\rm UID: } & \cr
\end{array}
\]
\end{enumerate}

%You may use the following table of numbers in $\{0,1,\ldots,36\}$ that are rel prime to 36,
%and their inverses.
%
%\[
%\begin{array}{ccccccccccccc}
%\hbox{NUMBER:}     & 1 & 5 & 7  & 11 & 13 & 17 & 19 & 23 & 25 & 29 & 31 & 35 \cr
%\hbox{INV MOD 36:} & 1 & 29& 31 & 23 & 25 & 17 & 19 & 11 & 11 &  5 &  7 & 35\cr
%\end{array}
%\]

\newpage


\begin{enumerate} 

\item
(4 points) 
To set up RSA, 
Zelda sends Alice $(77,31)$, so $N=77$ and $e=31$. 
Find the value of $d$.
Show work, though you can use a calculator or Wolfram Alpha.

\vfill

\centerline{\bf GOTO NEXT PAGE} 

\newpage


\item
(24 points- 4 points each)
For each of the following questions give a short answer (no more than five sentences).
Your answer has to really be about the cipher in question. For example, you CANNOT SAY

{\it The matrix cipher is not used because Alice and Bob have to meet}

since that is true of MANY ciphers. 

\begin{enumerate}

\item 
Why is the Matrix Cipher not used in the real world?




\vfill

\centerline{\bf GOTO NEXT PAGE}

\newpage


\item
There are three reasons people often use RSA with $e=2^{16}+1$.
One is that $e$ is prime, so no need to test if its rel prime to $d$.
Another is that $e$ is large.
What is the third reason?


\vfill

\centerline{\bf GOTO NEXT PAGE}

\newpage


\item
Why do people use a safe prime when doing Diffie-Helman?

\vfill

\centerline{\bf GOTO NEXT PAGE}

\newpage


\item
Why do people use a pair of safe primes when doing RSA?


\vfill

\centerline{\bf GOTO NEXT PAGE}

\newpage


\item
Why would someone use LWE-PUBLIC rather than RSA?


\vfill

\centerline{\bf GOTO NEXT PAGE}

\newpage


\item
When doing Diffie-Helman, Alice and Bob use a prime $p$ and a generator $g$.
Why do they use a generator? 


\end{enumerate} 


\vfill

\centerline{\bf GOTO NEXT PAGE} 

\newpage 

\item
(12 points) Zelda is doing $(2,2)$ secret sharing with $A_1$ and $A_2$ over $\Z_7$. 

Zelda gives $A_1$ the number 2.

Zelda gives $A_2$ the number 1. 

What is the secret? Show your work.


\vfill

\centerline{\bf GOTO NEXT PAGE} 

\newpage 




\item
(10 points) 
Alice and Bob are going to do LWE-PRIVATE with parameters:

$\vec k = (12,203,44,47)$. (RECALL- this is private)

$p=2009$. (RECALL- this is public) 

$\gamma=10$. (RECALL- this is public. This is smaller than recommended, but that's not an issue for this problem.)

Find TEN values of $x$ such that if Bob receives $(1,2,3,4;x)$ then Bob KNOWS
that Eve tampered with the message. 


\end{enumerate}

\end{document}