\documentclass{article}
\usepackage{a4wide}
\usepackage{amssymb}
\usepackage[utf8x]{inputenc}
\usepackage[english]{babel}
%\usepackage{graphicx}
%\usepackage{clrscode}
\usepackage{fancyhdr}
\pagestyle{fancy}
\newcounter{priklad}
\newcommand{\pr}{\newpage\noindent\stepcounter{priklad}}
\headheight 23.2pt
\fancyfoot{}
\lhead{Jiří Slabý, 98734}
\chead{\textbf{Error-correcting codes, cryptography and \\ cryptographical
protocols (IV054)}}
\rhead{Exercise 9.\arabic{priklad}}
\renewcommand{\baselinestretch}{1.17}
\renewcommand{\labelenumi}{(\alph{enumi})}
\begin{document}
\pr \indent % 1. priklad
If Bob sends same $r$, Eve can simply resend $y$, which she catched before
(in last posting). Bob gets $y=(k+ar)\,\bmod\,q$ as usual and he verifies,
that $\gamma\equiv\alpha^yv^r\,\bmod\,p$, so he can trust Eve and
communicates with her as with Alice.
\pr % 2. priklad
Since $\gamma\equiv\alpha_1^{64}\alpha_2^{35}v^{100}\equiv
\alpha_1^{6}\alpha_2^{133}v^{50}\equiv
\alpha_1^{118}\alpha_2^{45}v^{50}\pmod p$,
\[\alpha_1^{6}\alpha_2^{133}v^{50}\equiv
\alpha_1^{118}\alpha_2^{45}v^{50}\pmod p\]
and after multiplying by $\left(v^{50}\right)^{-1}$ from right
\[\alpha_1^{6}\alpha_2^{133}\equiv\alpha_1^{118}\alpha_2^{45}\pmod p\]
We know, that $\alpha_1^c=\alpha_2$ and hence
\[\alpha_1^{6+133c}=\alpha_1^{6}\alpha_1^{133c}\equiv
\alpha_1^{118}\alpha_1^{45c}=\alpha_1^{118+45c}\Rightarrow
\alpha_1^{88c}\equiv\alpha_1^{112}\Rightarrow
\alpha_1^{11c}\equiv\alpha_1^{14}\pmod p\]
it is equivalent iff $11c\,\bmod\,10008=14$ and so $\textbf{c=115}$. Check:
\[8630=195^{88\cdot115}=\alpha^{88c}\equiv\alpha^{112}=195^{112}=8630
\pmod{10009}\]
\pr \indent % 3. priklad
If we can succesfully predict the challenge bit, there are two
possibilities. If we say, that $b$ is 0, we send $y=r$ ($r$ was chosen
randomly before and sended to Bob as $r^2$), then Bob verifies $y^2=r^2$ and
he can trust us. Otherwise, if $b=1$ we choose $y$ randomly, but $a$ sended
before have to be $a=y^2v^{-1}$. Bob verifies $y^2=av$. So, if we can
predict $b$ before we send initial information, we can simply cheat.
\pr % 4. priklad
\begin{enumerate}
\item If there are big enough numbers, so that collision is hard to find,
the protocol is well-defined, but in (c) part we will see, that
attacker can gather some info, if he is not honest (and intruders
aren't). Completeness: if Alice knows the secret, then the probability for
Bob to accept the proof is very high, because there is low chance to tip
right $i'$. Soundness: if Eve doesn't know
the secret key, it is very hard (for high numbers) to compute or tip
right solution.
\item Because it's hard to solve $i\equiv j^d\pmod n$ to find out $d$
(the secret key), when $j\equiv i^e\pmod n$ is only known, it is
zero-knowledge, Bob can't gain anything about secrets of Alice.
% If he doesn't try to break it (he is honest), then somebody else, who
% sends to Alice some $i$ (to prove that she knows $d$) can be sure,
% he is talking to Alice -- again, iff good (high) numbers are chosen. In
% other words, there is high probability, that no other knows (and can't
% compute) $d$, the inverse of public key (private key).
\item The only thing, that went on my mind touching this was, that when
Jane wants to check, if she is communicating with Alice and sends
encrypted word, Bob intercepts it, sends to Alice, he sends him back
decrypted message and he may easily tell Jane, yes this is me, Alice.
\end{enumerate}
\pr \indent % 5. priklad
I used \textit{Bit commitment scheme I.} from slides: $p$, $q$ are large
primes, $n=pq$, $m\in QNR(n)$, $X=Y=Z_n^*$, $n$, $m$ are public.
\[f(b,x)=m^bx^2\,\bmod\,n\]
Let $x=0$ for stone, $x=1$ for scissors, $x=2$ for paper. One of them
chooses something from the triple and sends it encoded through the phone.
The other one tells his/her choice (in open form, not encrypted) and then,
if he/she doesn't believe, we can
send him our private keys to let him/her verify it. The side, which encrypts
can't cheat, because there are no $x_1$, $x_2$ such that
$mx_1^2=x_2^2\,\bmod\,n$.
% I used this old, well-known method: Alice and Bob have public and private
% keys, which
% are commutative. Both Alice and choose something from stone-scissors-paper
% combination. Alice encrypts it with public key and sends it to Bob.
% Bob encrypts Alice's message with his public key, adds his choice encrypted
% by his public key. Alice then decrypt first and encrypt second. Bob decrypt
% both first and second. Alice decrypt second. Both have their choice before
% encrypting without cheating. Schematic ($x$ is Alice's and $y$ Bob's
% choice): \\
% $[e_A(x),0]\stackrel{to\ Bob}{\rightarrow}[e_B(e_A(x)),e_B(y)]
% \stackrel{to\ Alice}{\rightarrow}[d_A(e_B(e_A(x))),e_A(e_B(y))]=
% [e_B(x),e_A(e_B(y))]\stackrel{2B}{\rightarrow}[d_B(e_B(x)),d_B(e_A(e_B(y)))]=
% [x,e_A(y)]\stackrel{2A}{\rightarrow}[x,d_A(e_A(y))]=[x,y]$
\end{document}