\documentclass[12pt,389,ifthen]{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}} \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 456 Final, Fall 2020} \begin{enumerate} \addtolength{\itemsep}{-2mm} % reduced space between lines \item This is an open-book, open-slides, open-web exam. If you have a question please go to class Zoom site or post to private piazza. \item You may use calculators or programs you find online or programs you wrote for the class on any of the problems. \item There are 5 problems which add up to 100 points. The exam is 120 minutes. \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 After the last page there is paper for scratch work. \item Please SIGN the following statement, which you can do by typing if this is being done online in (say) LaTeX. ``\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} \newpage \begin{enumerate} \item (20 points) (This problem has 5 parts, 2 on this page and 2 on the next page and 1 on the next page after that. Do this problem in the space provided after each question.) Give SHORT answers to all of these questions. \begin{enumerate} \item What is an advantage of using the public-key LWE rather than RSA? \bigskip \bigskip \bigskip \bigskip \bigskip \bigskip \bigskip \bigskip \bigskip \bigskip \bigskip \bigskip \bigskip \bigskip \bigskip \bigskip \item What is an advantage of using RSA rather than public-key LWE? \vfill\eject \item What is an advantage of using the randomized-shift cipher rather than the shift cipher? \bigskip \bigskip \bigskip \bigskip \bigskip \bigskip \bigskip \bigskip \bigskip \bigskip \bigskip \bigskip \bigskip \bigskip \bigskip \bigskip \bigskip \bigskip \bigskip \bigskip \bigskip \bigskip \bigskip \item The Eric-$3$ cipher is as follows: Let $S$ be the set of all $3$-blocks of letters ($aaa$, $aab$, $\ldots$, $zzz$). Take a random perm of $S$ (e.g., $pqz$, $ppq$, $uvb$ might be the first three). Use this for your key and for you mapping (e.g., in the above $aaa$ maps to $pqz$). And NOW for the question: What is an advantage of using the Eric-3 cipher rather than the $3\times 3$ matrix cipher? \bigskip \bigskip \bigskip \bigskip \bigskip \bigskip \bigskip \bigskip \bigskip \bigskip \bigskip \bigskip \bigskip \bigskip \bigskip \bigskip \item What is an advantage of using the $3\times 3$ matrix cipher rather than the Eric-3 cipher? \bigskip \bigskip \bigskip \bigskip \bigskip \bigskip \bigskip \bigskip \bigskip \bigskip \bigskip \bigskip \bigskip \bigskip \bigskip \bigskip \end{enumerate} \vfill\eject \item (20 points) (Do this problem on this page and, if needed, the next page.) Alice and Bob have an idea! They will do Diffie Helman using $\N$ (the naturals) instead of mod $p$. They do not need to pick a prime. They will pick $g,a,b$ such that $g,a,b\in \{2,\ldots,L\}$ where $L$ is a security parameter. (We assume that calculations with $g,a,b\in \{2,\ldots,L\}$ do not take much time and that space is abundant and hence not an issue.) They call their protocol DHON (Diffie-Helman-Over-N). \begin{enumerate} \item Give READABLE psuedo code for DHON. It should look like ALICE does BLAH BLAH BOB does BLAH BLAH BLAH BLAH BLAH and their shared secret is BLAH BLAH \item If $g=3$, $a=2$, and $b=5$ then what is the shared secret key? Express in base 2. \item Why is DHON worse than DH? (Recall that we are assuming calculation is fast and space is abundant so neither speed nor space are an issue.) \end{enumerate} \newpage \hbox{\ } \newpage \hbox{\ } \item (20 points) (Do this problem on this page and, if needed, the next page.) READ THIS NOW!: In this problem you will likely use a calculator or an online program OR the program you wrote for class. However, you should {\bf show work} as follows: If I ask you what (say) $R$ is, you can't just write down $R=6769$, you need to write down how you got $R$, for example (THIS IS NOT TRUE) $R=\ceil{p^2\lg q} = \ceil{101 * \lg(103)} = 676$. You an use English if you need to, like (THIS IS NOT TRUE) for example ``$R$ is the inverse of $p$ mod $q$ so $R$ is the inverse of 101 mod 103 which is BLAH''. \smallskip AND NOW FOR THE PROBLEM: \smallskip Alice and Bob are going to do RSA. Alice is using $p=101$, $q=103$, and $e=11$. In this problem we use the notation for RSA from the slides. \begin{enumerate} \item What is $N$? (REMEMBER- show work, though you can use a calculator or a program on the web.) \item What is $R$? (REMEMBER- show work, though you can use a calculator or a program on the web.) \item What is $d$? (REMEMBER- show work, though you can use a calculator or a program on the web.) \item Bob wants to send plaintext 40. What does he send? (REMEMBER- show work, though you can use a calculator or a program on the web.) \item (This problem is NOT connected to part (d).) Lets say Alice sees that Bob sent her ciphertext 7534. What is the plaintext? (REMEMBER- show work, though you can use a calculator or a program on the web.) \end{enumerate} \newpage \hbox{\ } \newpage \hbox{\ } \item (20 points) (Do this problem on this page and, if needed, the next page.) A Zan-Prime is a prime $p$ such that $p-1=6q$ where $q$ is prime. ASSUME we have a fast program that will, given a number, determine if it is prime. (You do not need to do trial division or anything to optimize this program.) You also have a random number generator. \begin{enumerate} \item Write pseudo code for a program that will, on input $L$, output a random $L$-bit Zan-Prime. (The left most bit has to be 1. The result must be exactly $L$ bits, so $2^{L-1} \leq p < 2^L$. \item Write pseudo code for a program that will, given a Zan-Prime $p$ and a number $g\in \{1,\ldots,p-1\}$, determine if $g$ is a generator in $O(\log p)$ time. (HINT: Use that $p$ is a Zan-prime.) \end{enumerate} \newpage \hbox{\ } \vfill\eject \item (20 points) (Do this problem on the next page and, if needed, the page after that.) For this problem we assume that $m$ is a perfect square so $\sqrt{m}$ is a natural. Let $sq$ be $\sqrt{m}$. Zelda has a secret $s$. She wants to share it with $A_1,\ldots,A_m$. We assume If $A_1,\ldots,A_{sq}$ (or any superset) get together they can learn the secret. If $A_2,\ldots,A_{sq+1}$ (or any superset) get together they can learn the secret. $\vdots$ If $A_{m-sq+1},\ldots,A_m$ (or any superset) get together they can learn the secret. If $A_{m-sq+2},\ldots,A_m,A_1$ (or any superset) get together they can learn the secret. If $A_{m-sq+3},\ldots,A_m,A_1,A_2$ (or any superset) get together they can learn the secret. $\vdots$ If $A_m,A_1,\ldots,A_{sq-1}$ (or any superset) get together they can learn the secret. (So any consecutive segment of $sq$ people, including wrap-around.) NO OTHER set of people who get together can learn the secret. (For Example, $A_1,A_3,A_5,A_7$ cannot learn the secret.) \begin{enumerate} \item EXPLAIN a secret sharing scheme Zelda can use. Specify: (1) What Zelda gives to each person, and (2) What each group does to obtain the secret. \item Let $|s|$ be the length of the secret. ROUGHLY how many bits does each $A_i$ get? Your answer should be of the form $O(f(|s|,m))$. (NOTE THAT the answer is a function of $|s|$ and $m$ NOT just $|s|$.) \end{enumerate} \end{enumerate} \newpage \hbox{\ } \newpage \hbox{\ } \newpage \hbox{\ } {\bf EXTRA PAGE IF YOU NEED IT} \end{document}