\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 6 CMSC 456. Morally DUE Oct 14}} {\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) Alice wants to speed up and simplify RSA. She tells Bob ``lets ALWAYS use $e=2^{2^4}+1$''. Let $e=2^{2^4}+1$ for the rest of this problem. \begin{enumerate} \item (5 points) Write $e-2,e-1$, and $e$ in both decimal and binary. \item (5 points) If Bob computes $m^e$ using repeated squaring then how many operations will it take? If Bob computes $m^{e-1}$ using repeated squaring then how many operations will it take? If Bob computes $m^{e-2}$ using repeated squaring then how many operations will it take? Express answers as ACTUAL NUMBERS like 81 or $\pi$. So I don't want things like {\it The $e$th Fibonacci Number}. ({\it Warning:} The answer is NOT $\pi$, or the $e$th Fib number, or even the $\pi$th Fib number.) \item (5 points) If you did part 1 right, then using $e-1$ is the best (though not by much), then $e$, then $e-2$ (and $e-2$ is much worse than $e$). So why not use $e-1$ for RSA? \item (5 points) Give two PROS to using this value of $e$. \item (5 points) Give two CONS to using this value of $e$. \item (0 points but look into and think about) Do people really use this value of $e$? Is using this value of $e$ a good idea? \end{enumerate} \centerline{\bf GOTO NEXT PAGE} \newpage \newpage \item (25 points) \begin{enumerate} \item (10 points) Compute the following: $$30^{123,456,789,111,213,141} \pmod {1001}.$$ \item (15 points) Give an algorithm that does the following: Given primes $p,q$ and $1\le a\le pq-1$ such that $a$ is rel prime to $pq$, and $n$ (which could be VERY LARGE!) return $$a^n \pmod {pq}.$$ We assume that any operation with numbers less than $pq$ takes 1 step, but any operation with a number BIGGER than $pq$, of length $L$, takes $L$ steps. Give an upper bound on the number of operations in terms of $n,p,q$. The answer should be of the form $O(f(n,p,q))$. \end{enumerate} \bigskip \centerline{\bf GOTO NEXT PAGE FOR NEXT PROBLEM } \newpage \item (25 points) Alice and Bob are going to do RSA with $p=31$, $q=37$, $N=pq=1147$, $R=(p-1)(q-1)=30*36=1080$, $e=77$ (one can check that 77 is rel prime to 1080), and $d=533$ (one can check that $ed\equiv 1 \pmod R$). Recall that $(N,e)$ are public, but only Alice knows $d$. They operate in Base 10. So messages are in $\{0001,\ldots, 1146\}$ and are only 4-digits long (we pad with 0's). They want to avoid the NY,NY problem. They will now send only 3-digit messages and add a random digit on the RIGHT of the message. If Bob wants to send $107$ he generates a random digit $r$ and sends $107r$. \begin{enumerate} \item (10 points) Bob wants to send 107. The random $r$ he picks is 8. What does Bob send? Show how Alice decodes it. \item (10 points) Bob wants to send 107 again. The random $r$ he picks is 5. What does Bob send? Show how Alice decodes it. \item (5 points) Bob has another idea: Hey Alice, let's add a random digit to the LEFT instead of to the RIGHT. This is a terrible idea. Why? \end{enumerate} \bigskip \centerline{\bf GOTO NEXT PAGE} \newpage \item (25 points) Zelda does RSA with Alice1 and Alice2. With Alice1 she uses $N_1=91$ and $e=2$. With Alice2 she uses $N_2=187$ and $e=2$. Hence this is just the right setting for a low-$e$ attack. (Note that $e=2$ cannot actually be used in RSA since $e$ is not coprime to $\phi(N_1)$ and $\phi(N_2)$, but we use it here to make the problem easier.) Eve sees Zelda send Alice1 43. Eve sees Zelda send Alice2 185. Eve knows that Zelda send the SAME message to both Alice1 and Alice2. Use the low-$e$ attack to find the message. Show all of your steps. (ADVICE: write a program or use the web to find inverses of $x$ mod $y$. You can use that and not have to show work. Everything else you do.) \end{enumerate} \end{document}