\documentclass[11pt,twoside]{article}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{epsfig}

\def\handoutdate{August 5, 1998}
\def\handoutname{Problem Session 3 Solutions}
\def\handoutnumber{9S}
\input{defs}


% ========================================================================

\begin{document}


\courseheader

\bigskip
\begin{center}
{\Large{\bf Problem Session 3 Solutions}}
\end{center}

{\bf Problem 3.1: Probabilistic Encryption.}

Assume that you have a message $m$ that you want to encrypt 
in a probabilistic way. For each of the following methods, tell 
us if you think it is a good or a bad method. 

\begin{enumerate}

\item Fix $p$ a large prime and let $g$ be a generator. 
For each bit $b_i$ in $m$, choose at random $x_i \in Z_{p-1}$ such that
$lsb(x_i)=b_i$ ($lsb(x)=$ least significant bit of $x$.)
The ciphertext is the concatenation of the $y_i=g^{x_i} \bmod p$. 
What about if you use $x$ such that $msb(x_i)=b_i$?

{\bf Solution}
If we use $lsb(x_i)$, $g^{x_i}$ is QR if the $lsb()$ was zero, and NQR
otherwise. We can check QR mod p, so this is a bad choice.  However,
we also know that the msb is a good choice, the $msb(x_i)$ is hard
core predicate for the discrete log. That is, if we can find the
$msb(x)$ given $g^x$, then we can solve the discrete log problem.

\bigskip

\item Choose an RSA public key $n,e$ such that $|n|>2|m|$. Pad $m$ with random
bits to get it to the same length of $n$. Let $m'$ be the padded plaintext. 
Encrypt $c=m^e \bmod n$. 

{\bf Solution}
This one is harder to decide.  If it was definitely secure, then we
would know that at least half of the RSA bits are all secure. However,
this is as of the writing of this solution unknown. So, it is an okay
method if you trust the above unproven fact.

\bigskip

\item Choose an RSA public key $n,e$. Assume that $|m|$ is smaller than 
$\log \log n$ (you can always break the message in blocks of that size.)
Pad $m$ with random
bits to get it to the same length of $n$. Let $m'$ be the padded plaintext. 
Encrypt $c=m^e \bmod n$. 

{\bf Solution}
This is similar to the above, only this time we're only assuming that
$\log \log n$ bits of RSA are secure. This has been shown to be true
{\bf IF} RSA is indeed a one-way fuction.

\bigskip

\item Choose two large primes $p,q = 3 \bmod 4$. Let $n=pq$. 
For each bit $b_i$ in $m$, choose at random $x_i \in Z_n^*$ and 
set $y_i=x_i^2 \bmod n$ if $b_i=0$ or $y_i=-x_i^2 \bmod n$ if $b_i=1$. 
The ciphertext is the concatenation of the $y_i$'s.

{\bf Solution}
This technique relies on the fact that finding if a number is a QR mod
n is hard. Since we believe this to be the case, then it is
secure. The fact that $n \equiv 3 \bmod 4$ is necessary to distinguish
which bit we want, but doesn't help the adversary any.

\end{enumerate}

\clearpage

{\bf Problem 3.2: Possible Forgeries.}

For both RSA and ElGamal say if the scheme is 
\begin{enumerate}
\item universally forgeable

{\bf Solution} 

RSA is universally forgeable under a {\it chosen message} attack. The
adversary can request two message $m_1, m_2$ such that their product
in the field equals the message he wants to forge a signature of.
Since $\sigma(m_1) = (m_1)^d , \sigma(m_2) = (m_2)^d \pmod n$, we now have
$\sigma(M' = m_1m_2) = (m_1m_2)^d = (m_1)^d (m_2)^d = \sigma(m_1) \sigma
(m_2) \pmod n$.

ElGamal is not universally foregeable under the three standard
attacks. However, an attack that involves predicting the pseudo-random
number generator being used, or an attack that involves figuring out
$k$, lets us totally break the system (that is: universal forgery is
possible) by seeing one signature. If we have $m = xr + ks
\pmod{p-1}$, and we know $m,r,s,p$, having a good guess for $k$ gives
us $x$.

\bigskip

\item selectively forgeable

{\bf Solution}

As above, RSA is selectively forgeable under a {\it chosen message}
attack. It is also theoretically possible to forge the signature of
the message $m = 1$, since under RSA, the signature of that is also
$1$ (that being a {\it Key-Only} attack).

ElGamal appears to not be selectively forgeable either, although see
above for a possible attack.

\bigskip

\item existentially forgeable

{\bf Solution}

RSA is existentially forgeable under a {\it known signature} attack
(multiply two signatures and the two respective messages).

ElGamal is also existentially forgeable under a {\it known
signature} attack:

Suppose we are given $(r,s)$ such that $r = g^k \bmod p$ and $s$ is
computed such that $M = (xr + ks) \bmod{(p-1})$. $x$ is our private
key, and $y = g^x \bmod p$ is the public key (along with $p, g$). $k$
is selected randomly for each signature. Now, to forge, select $0 \leq
h, i, j \leq (p-2)$ such that $gcd(hr - js, p-1) = 1$. Now, compute:
\begin{eqnarray*}
r' & = & r^hg^iy^j \bmod p \\
s' & = & sr'(hr-js)^{-1} \bmod{(p-1)} \\
M' & = & r'(hM + is)(hr - js)^{-1} \bmod{(p-1)}
\end{eqnarray*}

The verification for the above should work that:
\[ y^{r'}{(r')}^{s'} \equiv g^{M'} \pmod p \]


\end{enumerate}
and if it is under which kind of attack. 

\clearpage
{\bf Problem 3.3: About ElGamal.}

Suppose Bob is using the ElGamal signature scheme. Bob signs two
messages $m_1$ and $m_2$ with signatures $(r,s_1)$ and $(r,s_2)$
(the same value of $r$ occurs in both signatures.)
Suppose also that $gcd(s_1-s_2,p-1)=1$. 
\begin{enumerate}
\item Show how $k$ can be computed efficiently given this information

{\bf Solution}

From the above info, we can play around with things until we get $k$:

\begin{eqnarray*}
g^{m_1 - m_2} &  \equiv & r^{s_1 - s_2} \pmod p \\
		 & \equiv & g^{k(s_1 - s_2)} \pmod p \\
m_1 - m_2 & \equiv & k(s_1 -s_2) \pmod {p-1} \\
k & = & (m_1 - m_2)(s_1 - s_2)^{-1} \pmod {p-1}
\end{eqnarray*}

\item Show how the signature scheme can subsequently be broken

{\bf Solution}

Once we have $k$, we have $x = (m_1 - kr_1)(s_1)^{-1}
\bmod{(p-1)}$. When we have $x$, we have the private key, so we can
forge as much as we like.

\end{enumerate}

\clearpage
%\medskip
{\bf Problem 3.4: Suggested signature scheme}

Consider the following discrete log based signature scheme. Let $p$ be a
large prime and $g$ a generator.
The private key is $x < p$. The public key is $y=g^x \bmod p$.

To sign a message $M$, calculate the hash $h=H(M)$. If $gcd(h,p-1)$ is
different than 1 then append $h$ to $M$ and hash again. Repeat this
until $gcd(h,p-1)=1$. Then solve for $z$ in
\[ zh=x \bmod (p-1) \]
The signature of the message is $s=g^z \bmod p$. To verify the signature,
a user checks that $s^h=y \bmod p$ and that $h$ was obtained from $M$
using the method outlined above.

\begin{enumerate}

\item Show that valid signatures are always accepted

{\bf Solution}

$\sigma(M) = g^z \bmod p$,  where $zh \equiv x \bmod {(p-1)}$.

For a valid signature, we need to check that $(\sigma(M))^h \equiv y
\pmod p$.  And we know that $zh \equiv x \pmod {\phi(p)}$, so:
$(\sigma(M))^h \equiv g^{zh} \equiv g^x \equiv y \pmod p$, and we
therefore accept.

\item Is the scheme secure?

{\bf Solution}

Unfortunately, this scheme is not secure. While it's true that $z
\equiv xh^{-1} \pmod {p-1}$ is difficult to compute, $g^z \equiv
g^{xh^{-1}} \equiv y^{h^{-1}}$ is easy.

So, to get the signature for any message $M$, repeat the process to
get $h$ until $gcd(h, p-1) = 1$. Then, compute $h^{-1} \bmod (p-1)$,
and the signature is just $y^{h^{-1}} \bmod p$.
\end{enumerate}

\end{document}