\documentclass[11pt,twoside]{article} \usepackage{amsmath} \usepackage{amsfonts} \usepackage{epsfig} \def\handoutdate{August 3, 1998} \def\handoutname{Problem Session 1 Solutions} \def\handoutnumber{7S} \input{defs} % ======================================================================== \begin{document} \courseheader \bigskip \begin{center} {\Large{\bf Problem Session 1 Solutions}} \end{center} \bigskip \newcommand{\mmod}[1]{\,\,(mod\,\,#1)} \def\cycle{{\sc Cycle}} {\bf Problem 1.1: One-way functions can't have a small range} Prove that a one-way function cannot have a polynomial sized range. Namely show that if $f$ is a one-way function then for every polynomial $p$ there exists an infinite set $N_p$ such that $|\set{f(x)}{x\in\bits^n}|> p(n)$ for all $n\in N_p$. \bigskip {\bf Solution} \begin{center} \epsfig{file=sol-1-1.eps} \end{center} Assume that it is {\bf not} the case that \[ \left| \left\{ f(x) | x \in \{0,1\}^n \right\} \right| > p(n) \quad \text{ for infinitely many n's} \] Then $\exists$ polynomial $p()$ s.t. \[ \left| \left\{ f(x) | x \in \{0,1\}^n \right\} \right| \leq p(n) \quad \text{ for sufficiently large n} \] We design an inverting algorithm $A(1^n, y)$ which chooses a $z$ at random: $z \stackrel{R}\leftarrow \{0,1\}^n.$ We claim that $A()$ inverts with non-negligible probability: \[ \exists y_0 \text{ s.t. } \quad |f^{-1}(y_0)| = |\{x | f(x) = y_0\}| \geq \frac{1}{p(n)} \{0,1\}^n \] This $y_0$ is an element with a large pre-image. \begin{equation} \begin{split} \Pr \left[ f(z) = y | x \stackrel{R}{\leftarrow}\{0,1\}^n, y \leftarrow f(x), z\leftarrow A(1^n, y) \right] & \geq \Pr [ y = y_0 ] \cdot \Pr [f(z) = y | y = y_0 ] \\ & \geq \frac{1}{p(n)} \cdot \frac{1}{p(n)} = \frac{1}{p^2(n)} \end{split} \end{equation} This is a contradiction. We have therefore shown that for a non-negligible set of numbers, we can invert $f(x)$, which of course implies that $f(x)$ is not a one-way-function. \clearpage {\bf Problem 1.2: One-way functions can't have small cycles} Prove that one-way functions cannot have polynomially bounded cycles. Namely for any $f$ define $\cycle_{f(x)}$ to be the smallest positive integer $i$ such that $f^i(x)=x$. Prove that if $f$ is one-way then for every polynomial $p$ there exists an infinite set $X_p$ such that $\cycle_{f(x)}>p(|x|)$ for all $x\in X_p$. \bigskip {\bf Solution} Assume the above is not the case, then we know $\exists$ a polynomial $p()$ such that $\cycle_{f(x)} \leq p(|x|)$ for sufficiently large number of $x\in X_p$. We can therefore try to design an inverting algorithm. {\bf $A(1^n,y)$: } \begin {itemize} \item let $z \leftarrow y$. \item while $f(z) \neq y$, $z \leftarrow f(z)$ \item output $z$. \end{itemize} This algorithm will run until the length of the cycle, and must stop after at most $p(|y|)$ iterations. The output is $z$ such that $f(z) = y$, or alternatively, the output is $f^{-1}(y)$. This runs in polynomial time. Therefore, $A()$ succeeds in finding an inverse with probability 1, which goes against the assumption that $f()$ is a one way function, so we have a contradiction. Therefore, such a cycle cannot exist. \clearpage {\bf Problem 1.3: DES and PRFs} Let $\bar{m}$ be the bitwise complement of the string $m$. Let $\DES_K(m)$ denote the encryption of $m$ under DES using key $K$. It is not hard to see that if \[ c = \DES_K(m) \] then \[ \bar{c} = \DES_{\bar{K}}(\bar{m}) \] We know that a brute--force attack on DES requires searching a space of $2^{56}$ keys. This means that we have to perform that many DES encryptions in order to find the key, in the worst case. \begin{enumerate} \item Under {\em known plaintext attack} (i.e., you are given a single pair $(m,c)$ where $c=\DES_K(m)$) do the equations above change the number of DES encryption you perform in a brute--force attack to recover $K$? {\bf Solution} We presumably have $(c,m)$ and want $K$. While this implies that we also know $(\bar{c}, \bar{m})$ under $\bar{K}$, there is not an obvious way to use it in a brute force attack. We still need to go over all possible keys. We can halve the number of keys we try by trying $m$ and then $\bar{m}$ and comparing to $c$ and $\bar{c}$ respectively, but this doubles the number of texts we check (so not an improvement). $\rightarrow 2^{56}$. \item What is the answer to the above question in the case of {\em chosen plaintext attack} (i.e., when you are allowed to choose many $m$'s for which you get the pair $(m,c)$ with $c=\DES_K(m)$)? {\bf Solution} This time, we can use it to our advantage. We ask for $(m,c_1)$ and $(\bar{m},c_2)$, Where the $c_x$ are encryptions under $K$ of the respective messages. Now we can, with each brute-force encryption we try, check two keys at once: \begin{itemize} \item For every key that starts with $0$, encrypt $m$. \item If the result is $c_1$, the key we brute forced was correct. \item If the result is $c_2$, the key we brute forced was the complement of the right key. \end{itemize} $\rightarrow 2^{55}$ \item Suppose we think of DES as a family of pseudorandom functions, each function in the family being specified by a 56 bit key, and mapping 64 bits to 64 bits. We would like to get a new pseudorandom function family $F$ in which each function maps $64$ bits to $128$ bits. Consider the following constructions. Do you think they are good or bad? Ie.~is the specified $F$ a pseudorandom function family or not? Below, ``$\Concat$'' denotes concatenation of strings and $[y]_{56}$ means take the first 56 bits of the 64 bit string $y$. {\bf Solution} A function is pseudorandom if we cannot construct a distinguisher $D$ that can decide if it is being handed a truly random function or our function. \begin{enumerate} \item $F_K(x)=\DES_K(0^{64})\Concat \DES_K(x)$ {\bf Solution} We can construct a distinguisher fairly easily: If we query for $f(0)$, we will discover that the output is repeated. Alternatively, we can query for two distinct inputs, and simply compare the first 64 bits. If they are equal, we are using $f(x)$, otherwise, we were given a truly random function. SO this is NOT a good PRF. \item $F_K(x)=\DES_K(x)\Concat \DES_K(\bar{x})$ {\bf Solution} We ask for both $m$ and $\bar m$. If we find that the first half of one equals the second half of the other (and vice versa), we know we are looking at $f()$. \item $F_K(x)=\DES_K(x)\Concat \DES_{\bar{K}}(x)$ {\bf Solution} Since we know that $DES_K(x) = \overline{DES_{\bar{K}}(\bar x)}$, we can use it to our advantage. We again ask for $m, \bar m$. If the second half of one encryption is the same as the first half of the other, and vice-versa, then we know that we are using $f(x)$. \item $F_K(x)=\DES_{0^{56}}(x)\Concat \DES_K(x)$ {\bf Solution} This is no good, because we know how DES works, and can ourselves compute the first half of the encryption. Therefore, to distinguish, submit any $m$ desired, and check if the first half of the response corresponds to the DES encryption of $m$ with a key set to $0^{56}$. \item $F_K(x)=\DES_{K_1}(x)\Concat \DES_{K_2}(x)$ where $K_1= [\DES_K(0^{64})]_{56}$ and $K_2=[\DES_K(1^{64})]_{56}$ {\bf Solution} This appears to be a good pseudo-random scheme: This can be viewed as a two-part system. The first creates the two keys, and the second part uses the keys to encrypt the message. Since we had already assumed DES to be a good pseudo-random permutation, finding K from $K_1,K_2$ should be hard, and there should be no distinguishable relationship between the two keys. Since there isn't a poly-time distinguishable relationship between the two keys, there isn't going to be any way to tell anything about the two halves of the message (as opposed to two random strings). This can be formalized into a proof by showing that if there was a way, then there would have been a way to distinguish $K_1$ from $K_2$, which goes against the assumption that DES is a good PRF. \end{enumerate} \end{enumerate} \clearpage {\bf Problem 1.4: Square roots} \begin{enumerate} \item Let $p$ be a Blum-prime, namely $p$ is a prime such that $p = 3 \mmod{4}$. Describe a polynomial time algorithm for taking square root modulo $p$. That is, given $a$ which is a square mod $p$, find an $x$ such that $x^2=a \mmod{p}$. {\em Hint:} Show that $a^{\frac {p-1} 2 +1} = a \mmod{p}$, and then write $p$ as $p=4m+3$. {\bf Solution} Since $p$ is prime, $\exists g$ generator for ${\mathbb Z}_p^*$. Given $a \in {\mathbb Z}_p^*$, which is a square ($a \equiv x^2 \pmod p$). We know that \[ a^{\frac{p-1}{2}} \equiv (x^2)^{\frac{p-1}{2}} \equiv x^{p-1} \equiv 1 \pmod p \] \[ a^{\frac{p-1}2 + 1} \equiv a \pmod p \] Now, we know that $p$ is a Blum-prime, which means that $p \equiv 3 \bmod 4$, or otherwise stated: $p = 4m + 3$ for some integer $m$. \begin{equation*} \begin{split} a^ {\frac{p-1}2 +1} \equiv a ^{\frac{4m+2}2 + 1} & \equiv a ^{2m + 2} \equiv a \pmod p \\ & {(a ^ {m+1})}^2 \equiv a \pmod p \end{split} \end{equation*} Therefore, we have found the square root, and it is $a^{m+1}$. \bigskip \item Does 20 have a square root modulo 77? How about 23 modulo 77? {\bf Solution} A number is a QR in a field iff it is a quadratic residue in all the prime factors of the field. In this case, 7 and 11. \begin {equation*} \begin{split} 77 = 7 \cdot 11 \quad \text{:} \quad & 20 \bmod 11 = 9 \bmod 11 = 3^2 \bmod 11 \quad \Longrightarrow QR \\ & 20 \bmod 7 = 6 \bmod 7 = -1 \bmod 7 \quad \Longrightarrow QNR \\ \end{split} \end{equation*} Therefore, 20 is not a quadratic residue mod 7. \begin {equation*} \begin{split} 77 = 7 \cdot 11 \quad \text{:} \quad & 23 \bmod 11 = 1 \bmod 11 = 1^2 \bmod 11 \quad \Longrightarrow QR \\ & 23 \bmod 7 = 2 \bmod 7 = 4^2 \bmod 7 \quad \Longrightarrow QR \\ \end{split} \end{equation*} Therefore, 23 is a quadratic residue mod 7. \end{enumerate} \clearpage {\bf Problem 1.5: Relationship between number theory problems} Let $n$ be the product of two primes $n=pq$. Describe reducibilities between the following problems (e.g. if we can factor we can invert RSA.) Don't prove anything formally, just state the result. \begin{enumerate} \item computing $\phi(n)$ \item factoring $n$ \item computing $QR_n(a)$ for some $a \in Z_n^*$ \item computing square roots modulo $n$ \item computing $k$-th roots modulo $n$, where $gcd(k,\phi(n))=1$ \end{enumerate} {\bf Solution} We know that (2), (1), and (4) are equivalent: Given $(p,q)$ from the factoring algorithm we can compute $\phi(n) = (p-1)(q-1)$. We can also compute, for any $a$, $sqrt(a)$, although this can get fairly hairy (the algorithm can be found in books on the subject). Going backwards from sqrt, if we have a way to find square roots, we can factor $n$ with the fact that given two non-inverse square roots, $x \neq -y ; x^2 = y^2 \pmod n$, we know that $gcd((x+y),n)$ is a prime factor of $n$, so we can factor. In order to get those pairs, simply take a random number and square it. Then, submit it to the square-root box. Half the time, it will respond with a useful answer, which you can use to factor. Repeat until it does. Going backwards from $\phi(n)$, If you have $n$ and $\phi(n)$, then $n - \phi(n) + 1 = pq - (p-1)(q-1) + 1 = pq - pq + p + q - 1 + 1 = p + q$. Going from $p+q$ to $p,q$ such that $pq = n$ is fairly fast. We also know that if we can factor (2), then we can easily compute QR (3), and in a manner similar to computing sqrts, compute (5). It is not known whether (3) or (5) are enough to get (1), (2), or (4). \end{document}