\documentclass[12pt,ifthen]{article} \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} \begin{document} \centerline{\textbf{HW 4 CMSC 456. Morally DUE Sep 30}} \ifshowsoln \centerline{\textbf{SOLUTIONS}} \fi {\textbf{NOTE- THE HW IS EIGHT PAGES LONG}} \begin{enumerate} \item (0 points) READ the syllabus- Content and Policy. READ my NOTES on ciphers and on English. What is your name? What is the day and time of the first midterm? \item (25 points) Alice and Bob are going to use Diffie-Hellman. Bob wants to save some time so instead of picking a RANDOM $b\in \{\frac{p}{3},\frac{2p}{3}\}$ he picks a $b$ that is a power of 2 because he thinks that for such $b$, $g^b$ will be easier to compute. (Alice still picks $a\in \{\frac{p}{3},\frac{2p}{3}\}$ at random.) \begin{enumerate} \item (10 points) Bob is right! Computing $g^b$ IS easier if $b$ is a power of 2. Explain why. \item (15 points) If Eve knows that Bob is choosing only powers of $2$, she can find the shared secret in time $(O(\log p))^c$ for some $c$. Show how. What is $c$? \end{enumerate} \bigskip \centerline{\textbf{GOTO NEXT PAGE}} \newpage \item (35 points) This is a programming problem. For this problem, you will be writing \textit{two} programs, which are described below. {\bf WARNING:} This problem is FIVE pages long. \begin{enumerate} \item (15 points) Your first program will deal with primality testing. This program will input two lines and will output two lines. \begin{enumerate} \item Begin by inputting two lines from standard input. The first line will contain a positive integer $p \ge 7$. The second line will contain a path to a text file containing a bunch of integers, one on each line. You will use the numbers in this file to generate the random numbers used for primality testing (see note below). \item For the first part of this program, you will run the primality test algorithm described in the lecture slides to determine (up to a high degree of certainty) whether $p$ is prime. For each trial, you will generate a random $a \in \{2,\ldots,p-1\}$ and will compute whether $a^p \equiv a \pmod{p}$. If all the trials pass, output ``true'' to indicate that $p$ is suspected to be prime. If one of the trials fails, output ``false'' to indicate that $p$ is known not to be prime. You must run EXACTLY $\floor{\log_2{p}}$ trials, even if some trial fails early. \item (If your program previously outputted ``false'', then output ``false'' again and skip this part.) Now, you will use the same primality test algorithm to determine (up to a high degree of certainty) if $(p-1)/2$ is prime. In other words, you will determine if $p$ is a ``safe prime''. Output ``true'' or ``false'' as before on a new line. \end{enumerate} \centerline{\textbf{GO TO NEXT PAGE FOR MORE INFO ON THIS PROBLEM}} \newpage \textbf{NOTE:} The primality testing algorithm requires you to compute powers modulo some number. When doing so, you MUST use repeated squaring. You MAY NOT use library code (i.e., no ``pow'' or ``modpow'' functions) to do this. If you do not follow these directions, you will LOSE points. \textbf{NOTE:} Because of how the autograder grades your output, you MUST generate random numbers in the following specific way. If you do not follow these directions carefully, your output may be marked as incorrect. Whenever you need to generate a random integer in the half-open interval $[b,c)$, you must (1) read the next available integer $k$ from the file specified by the input path, and then (2) compute $$a = (k\,\,\text{mod}\,\,(c-b)) + b$$ as your random number. Once you have done this, discard $k$ and move to the next number in the file. You may assume all numbers in the file are $< 2^{63}$. \centerline{\textbf{GO TO NEXT PAGE FOR MORE INFO ON THIS PROBLEM}} \newpage \item (15 points) Your second program will deal with finding large ``probable prime'' numbers. This program will input two lines and will output six lines. \begin{enumerate} \item Begin by inputting two lines from standard input. The first line will contain a positive integer $5 \le L \le 60$. The second line will contain a path to a text file containing a bunch of numbers, as with the previous program. \item First, you will do the following. Generate $(L-1)$ bits randomly, and then append a $1$-bit to the left, yielding an $L$-bit number $k$. If $k$ is determined to be a safe prime (using the same algorithm as in your first program), then output $k$ on the first line. Otherwise, repeat the process until you get a safe prime. Output on the second line how many random $k$'s you generated for this part. \item Next, you will do the following. Generate $(L-2)$ bits randomly, and then append a $1$-bit to both the left and right, yielding an $L$-bit odd number $k$. If $k$ is determined to be a safe prime, then output $k$ on the third line. Otherwise, repeat the process until you get a safe prime. Output on the fourth line how many random $k$'s you generated for this part. \centerline{\textbf{GO TO NEXT PAGE FOR MORE ON THIS PROBLEM}} \newpage \item Lastly, you will do the following. Generate $(L-3)$ bits randomly, and then append a $1$-bit to the left, yielding an $(L-2)$-bit number $m$. Then, obtain $k = 6m + 5$, which is roughly $L$ bits long. If $k$ is determined to be a safe prime, then output $k$ on the fifth line. Otherwise, repeat the process until you get a safe prime. Output on the sixth line how many random $m$'s you generated for this part. \end{enumerate} \textbf{NOTE:} To generate $L$ bits, take the next integer $k$ from the input file and compute $k \pmod{2^L}$. The bits of this integer are the bits that you want. Discard $k$ and move to the next number in the file as usual. When generating random values, keep in mind that you should only be passing through the file once per run of your program. \item (5 points) Run your second program on values $L=10,20,30,40$. You may generate your random numbers however you want for this part. Record (in the table below) the average of how many tries it takes to obtain a safe prime over $10$ trials for each method and value of $L$. Report this table along with the rest of your homework. Your code should be uploaded separately (see below). \begin{tabular}{|c|c|c|c|} \hline L & Naive Method & Odd Method & $6k$-method \cr \hline 10 & & & \cr 20 & & & \cr 30 & & & \cr 40 & & & \cr \hline \end{tabular} \\ \centerline{\textbf{GO TO NEXT PAGE FOR MORE ON THIS PROBLEM}} \newpage You are free to choose from various programming languages to complete this problem. By default, we support C, C++, Java, Python2/3, and Ruby. Ask on Piazza if you want more options. You will be submitting all code files you used to complete this problem to the Gradescope assignment called ``hw04 - problem 3''. Since you will probably want to submit multiple files, you should merge all files into a single zip file and submit that zip file to Gradescope. 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. Regardless of the language you choose, your submission must include TWO bash scripts called \texttt{run1} and \texttt{run2} (no file extensions) for running your first and second programs respectively. These scripts must begin with the shebang \texttt{\#!/usr/bin/env bash} on the very first line. These scripts will be run each time the autograder tries to run your code, so add to these files any commands that are needed to run your code. This gives you greater flexibility regarding how you want to organize your code. Additionally, if you are using a non-scripting language such as Java, also upload a bash script called \texttt{build}, also with shebang. This script will be called once upon submission to compile your code before execution. If you have any questions or confusions, or if you encounter any technical difficulties, feel free to ask for help on Piazza. \end{enumerate} \bigskip \centerline{\bf GOTO NEXT PAGE FOR NEXT PROBLEM FINALLY} \newpage \item (25 points) Find $A\in\N$ ($\N$ is the nonnegative integers) and \\ $X\subseteq \{0, 1, 2, \dots, A - 1\}$ such that \begin{align*} \{ n \in \N \st &(n\not\equiv 0 \pmod 2)\,\,\,\wedge \\ &(n\not\equiv 0 \pmod 3)\,\,\,\wedge \\ &(n\not\equiv 0 \pmod 5)\,\,\,\wedge \\ &(n\not\equiv 0 \pmod 7) \} \end{align*} $$ = \{ n \in \N \st (\exists k\in\N, i\in X)[n=Ak+i]\}.$$ (Note: IF the problem was about $2,3$ instead of $2,3,5,7$ then $A=6$ and $X=\{1,5\}$.) \begin{enumerate} \item (10 points) What is $A$? Make it as small as possible. \item (15 points) List all of the numbers in $X$ that are NOT 1 and NOT prime. Justify your answer. \end{enumerate} (Note: IF the problem was about $2,3$ instead of $2,3,5,7$ then for (a) the answer is 6 and for (b) the answer is $\es$.) \bigskip \centerline{\bf GOTO NEXT PAGE} \newpage \item (15 points) Alice and Bob are going to do Diffie-Hellman with $p=89$ and $g=30$. \begin{enumerate} \item (5 points) Alice picks $a=2$ and Bob picks $b=5$. What is the shared secret key? \item (5 points) Alice picks $a=5$ and Bob picks $b=2$. What is the shared secret key? \item (5 points) You should have gotten the same answer in parts 1 and 2 above. Is this a coincidence? Explain. \end{enumerate} \end{enumerate} \end{document}