\documentstyle[11pt,twoside]{article}

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


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

\begin{document}


\courseheader

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

\bigskip
{\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$?

\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$. 

\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$. 

\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.


\end{enumerate}

\bigskip
{\bf Problem 3.2: Possible Forgeries.}

For both RSA and ElGamal say if the scheme is 
\begin{enumerate}
\item universally forgeable
\item selectively forgeable
\item existentially forgeable
\end{enumerate}
and if it is under which kind of attack. 

\bigskip
{\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
\item Show how the signature scheme can subsequently be broken
\end{enumerate}

\bigskip
%\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

\item Is the scheme secure?
\end{enumerate}

\end{document}