\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 8 CMSC 456. Morally DUE Nov 4}} {\textbf{NOTE- THE HW IS THREE 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 FINAL? \item (30 points) Recall the following key exchange protocol: \begin{enumerate} \item Alice generates rand prime $p$ of length $L$, rand $S\times S$ matrix $A$ over $\Z_p$. You can assume $A$ is invertible. \item Alice sends $(p,A,SOTE)$. All public. \item Alice generates rand row $\vec y \in \Z_p^S$. Sends $\vec y A$. \item Bob generate rand column $\vec x \in \Z_p^S$, Sends $A\vec x$. \item Alice computes $\vec y(A\vec x)=\vec y A\vec x$. \item Bob computes $(\vec y A)\vec x=\vec y A \vec x$. \item Alice and Bob have shared secret $\vec y A \vec x$ \end{enumerate} Eve only sees $(p,A,SOTE,\vec y A,A\vec x)$. Give an attack that Eve can use to recover $\vec y A \vec x$. \vspace{5mm} \centerline{\textbf{GOTO NEXT PAGE}} \newpage \newpage \item (40 points) Alice and Bob never did like working in mod $p$ or any mod. So they decide to do the following version of Diffie-Hellman. \begin{enumerate} \item[i.] Security parameters are $S,T$. \item[ii.] Alice picks a random $g\in \{2,\ldots, S\}$ and broadcasts $g$. % this line added by npg \item[iii.] Alice picks a random $a\in \{2,\ldots, T\}$ and broadcasts $g^a$. \item[iv.] Bob picks a random $b\in \{2,\ldots, T\}$ and broadcasts $g^b$. \item[v.] Alice computes $(g^b)^a = g^{ab}$. \item[vi.] Bob computes $(g^a)^b = g^{ab}$. \item[vii.] The shared secret key is $g^{ab}$. \end{enumerate} We assume that $+,-,\times,\div$ take 1 step each (this is not realistic if $S,T$ are large but this is % an exam a homework problem, not the NSA). {\bf And NOW for the questions:} \begin{enumerate} \item (10 points) Show that computing $g^a$ can be done in $O(\log_2(T))$ steps. \item (20 points) Give an algorithm that will, given a $g\in \{2,\ldots,S\}$ and number $x\in \{1,\ldots,Z\}$ (1) if $x=g^y$ for some $y\in \N$ then output $y$, (2) if $x\ne g^y$ for any $y\in \N$ then output OH, NO SUCH $y$. The algorithm has to be in time $(\log\log Z)^{O(1)}$. ($S$ may play a role in the base of the log but we ignore this.) You can't just say {\it take the logarithm base $g$}, you have to do it using only the basic operations $+,-,\times,\div$. \item (5 points) Eve only sees $(g,g^a,g^b)$. Show how she can efficiently find $g^{ab}$ using Part (b). What is the runtime? \item (5 points) From the above we see that doing Diffie Hellman over the naturals is insecure. Give one more reason why using it is a bad idea. \end{enumerate} \bigskip \centerline{\bf GOTO NEXT PAGE FOR NEXT PROBLEM } \newpage \item (30 points) Alice and Bob are bridge partners. And they cheat! Here is their scheme: \begin{itemize} \item If the first card is placed horizontally then the person placing it has 0 or 1 Ace. \item If the first card is placed vertically then the person placing it has 2 or 3 or 4 Aces. \end{itemize} In this problem we will both (1) help Alice and Bob and (2) help the bridge community. \begin{enumerate} \item (15 points) Alice and Bob will be playing 20 games and are worried that their cheating may be discovered. Show how they can use a 1-time pad to make their cheating harder to discover. \item (15 points) Change something about how Bridge is played so that Alice and Bob cannot use their method to cheat. \end{enumerate} \end{enumerate} \end{document}