\documentclass{article}
\usepackage{slovak}
\usepackage{mya4wide}
\pagestyle{empty}
\def\nsd{{\rm nsd}}
\def\mod{{\rm mod~}}
\def\pmod#1{~({\rm mod~}#1)}
\def\then{\Rightarrow}

\newlength{\myboxwidth}
\newlength{\mypagewidth}
\mypagewidth=0.32\textwidth 
\myboxwidth=0.32\textwidth \advance\myboxwidth -13pt
\def\Urob#1{{\noindent\framebox{\parbox{\myboxwidth}{\vbox{#1}}}}}

\begin{document}

\begin{minipage}{\mypagewidth}\vbox to 28cm{
\Urob{
\centerline{\large RSA}
{\bf Init:} \\
1. zvol�me prvo��sla $p\not=q$ \\
2. zvol�me $e$ aby $\nsd(e,\phi(n))=1$ \\
3. dor�tame $d$ aby $ed\equiv 1\pmod{\phi(n)}$ \\
public: $(n,e)$, private: $d$ \\
{\bf �ifrovanie:} \\
$E(m)=m^e \bmod n$ \\
{\bf De�ifrovanie:} \\
$D(c)=c^d \bmod n$ \\
{\bf Bezpe�nos�:} \\
- vieme faktorizova� $\to$ rozbijeme RSA \\
- vieme $\phi(n)$ $\to$ vieme faktorizova� \\
- vieme $d$ $\to$ polo��me $m=ed-1$, potom $m$ je n�sobok $\phi(i)$, k�m plat� 
  $\forall a\in Z^*; a^m \equiv 1$ ho del�me 2, potom s pp 1/2 je 
  $\nsd(n,a^{m/2}-1)$ faktor. \\
- zdie�an� $n$ $\to$ vieme rozbi� svoje $n$, a teda aj $n$ niekoho in�ho \\
- $|p-q|$ je mal� $\to$ vysk��ame a je \\
- $p-1$ m� len mal� prvo�. faktory $\to$ zvol�me $K$ ako vhodn� n�sobok
  mal�ch prvo�., bude $(p-1)|K$, preto pre n�h. $a$ je $a^K\equiv 1\pmod p$,
  pravdep. $a^K\not\equiv 1\pmod q$, preto $\nsd(n,a^K-1)$ je faktor. \\
- mal� priestor spr�v $\to$ vysk��ame $\forall$ \\
- mal� $e$ $\to$ sta�� odchyti� spr�vu poslan� $e$ �u�om \\
- mal� $d$ $\to$ d� sa nejako \\
- takmer CCA: ak niekto podp��e $\forall$ �o mu po�leme, vieme si 
  dekryptova� $E(m)$: d�me podp�sa� $r\cdot E(m)$, on nevie �o podpisuje \\
- bezpe�nos� posledn�ho bitu: keby sme ho vedeli, vieme rozbi� RSA
}

\Urob{
\centerline{\large ElGamalov syst�m}
{\bf Init:} \\
1. zvol�me verejn� prvo��slo $p$ a gener�tor $g$ grupy $(Z_p\setminus \{0\},\cdot)$ \\
2. ka�d� u�ivate� zvol� $x\in_R\{1,\ldots,p-2\}$, spo��ta $y=g^x \bmod p$ \\
public: $(p,g,y)$, private: $x$ \\
{\bf �ifrovanie:} \\
1. zvol� sa $k\in_R \{1,\ldots,p-2\}$ \\
2. $E(m)=( g^k , my^k )$ \\
{\bf De�ifrovanie:} \\
$D(c_1,c_2):$ spo��tame $a=c_1^{~x}(=g^{kx})$, potom $m=c_2a^{-1}$ \\
{\bf Bezpe�nos�:} \\
- ekviv. s Diffie-Hellmannov�m probl�mom: z $g^a$, $g^b$ ur�i� $g^{ab}$ \\
- najviac tak �a�k� ako DLOG \\
- nesmie sa prezradi� $k$, $y^k$ \\
- nerecyklova� $k$ \\
- m��u sa sharova� $p,g$
}

\vfill

\copyright Mi�oF. 2003
}\end{minipage}
\begin{minipage}{\mypagewidth}\vbox to 28cm{
\Urob{
\centerline{\large Pohlig-Hellmannov alg.}
m�me $p-1=q_1^{e_1}\ldots q_k^{e_k}$, chceme r�ta� $x=DLOG_g y$ $\pmod p$ \\
por�tame $x \bmod q_k^{e_k}$, z toho a ��nskej zv. vety vieme $x$ \\
h�adajme $x \bmod q^e$ v tvare $\sum_{i=0}^{e-1} a_iq^i$ \\
plat�: $y^{(p-1)/q}\equiv x^{a_0(p-1)/q} \pmod p$, z toho brute-force dor�tame $a_0$,
uprav�me $y'=yx^{-a_0}$ a pokra�ujeme odznova ur�i� $a_1$, at�. \\
Vypl�va z toho, �e pre $p=2^st$ vieme posledn�ch $s$ bitov $DLOG$u
}

\Urob{
\centerline{\large Rabinov syst�m}
{\bf Init:} \\
1. zvol�me prvo��sla $p,q\equiv 3\pmod 4$ \\
public: $n=pq$, private: $(p,q)$ \\
{\bf �ifrovanie:} \\
$E(m)=m^2 \bmod n$ \\
{\bf De�ifrovanie:} \\
n�jdeme odmocniny $\mod p$ a $\mod q$, z ��nskej zv. vety m�me 4 odmocniny, nejako ur��me, ktor�
je dobr� \\
(odmocnina z $c$ je $c^{(p+1)/4}$ $\pmod p$) \\
{\bf Bezpe�nos�:} \\
- ekviv. s faktoriz�ciou \\
- CCA �tok: zvol�me si $m$, d�me si de�ifrova� $m^2$, s pp=1/2 dostaneme dve odmocniny, z kt. sa d�
spo��ta� faktor \\
- d� sa prida� vhodn� padding
}

\Urob{
\centerline{\large Goldwasser-Micali}
{\bf Init:} \\
1. zvol�me prvo��sla $p,q\equiv 3\pmod 4$ \\
2. zvol�me $y\in QNR_n$ \\
public: $(n=pq,y)$, private: $(p,q)$ \\
{\bf �ifrovanie:} \\
rozbijeme spr�vu na bity, pre $m_i\in\{0,1\}$ zvol�me $x\in_R Z_n^*$, potom $E(m_i)=x^2y^{m_i}$ \\
{\bf De�ifrovanie:} \\
- test �i $c\in QR_n$: pozri, �i $c^{(p-1)/2}\equiv 1$
{\bf Bezpe�nos�:} \\
- najviac tak �a�k� ako faktoriz�cia
}

\Urob{
\centerline{\large BBS gener�tor}
{\bf Init:} \\
1. zvol�me prvo��sla $p,q\equiv 3\pmod 4$, nech $n=pq$ \\
2. zvol�me $x\in_R Z_n^*$, nech $x_0=x^2 \bmod n$ \\
3. zostroj�me $\{x_i\}_{i\geq 0}$: $x_{i+1}=x_i^2 \bmod n$ \\
4. zostroj�me $\{b_i\}_{i\geq 0}$: $b_i=x_i \bmod 2$ \\
{\bf �ifrovanie:} \\
rozbijeme spr�vu na bity, pre $m_i\in\{0,1\}$ je $E(m_i)=m_i\oplus b_i$, navy�e po�leme $x_{|m|}$ \\
{\bf De�ifrovanie:} \\
vieme $p,q$ $\to$ vieme odmoc�ova� $x_i$, pr�ve 1 zo 4 odmocn�n bude $QR_n$
}

\Urob{
\centerline{\large Chaum-van Heijst-Pfitzmann hash}
nech $p=2q+1$ s� prvo�., $g,c$ gener�tory v $(Z_p\setminus \{0\},\cdot)$ \\
$h:(Z_q\times Z_q)\to (Z_p \setminus \{0\})$ \\
$h(x_1,x_2)=g^{x_1}c^{x_2} \bmod p$\\
- ak vieme n�js� kol�ziu, vieme $DLOG_g c$
}

\vfill}\end{minipage}
\begin{minipage}{\mypagewidth}\vbox to 28cm{
\Urob{
\centerline{\large Pred�enie hash fcie}
nech $h:\{0,1\}^m\to\{0,1\}^t$, $m\geq t+2$ \\
nasek�me spr�vu $x$ na �seky $x_i$ d�ky $m-t-1$,
posledn� dopln�me paddingom (tvaru 10..0), r�tame:\\
$h_1=h(0^{t+1}\|x_1)$ \\
$h_2=h(h_1\|1\|x_2)$ \\
\dots \\
$h^*(x)=h_n=h(h_{n-1}\|1\|x_n)$ \\
ak $h$ je odoln� vo�i kol�zi�m, aj $h^*$ je
}

\Urob{
\centerline{\large MAC}
message authentication code \\
cie�: zabezpe�i� integritu spr�vy \\
po�leme $(m,h_K(m))$ ($h$ je hash, $K$ k���) \\
vhodn� $h_K$: $h_K(m)=h(K\|pad\|m\|K)$, kde $pad$ je dohodnut� padding, aby to bolo dos� dlh�
}

\Urob{
\centerline{\large RSA podpis. sch�ma}
podpisujeme $D$, overujeme $E$\\
podpisuje sa hash spr�vy, aby sme zabr�nili random message forgery (z dvoch podp�san�ch podp�san�
s��in)
}

\Urob{
\centerline{\large ElGamal podpis. sch�ma}
{\bf Init} ako pri �ifrovan� \\
{\bf Podpisovanie:} \\
1. zvol� sa $k\in_R \{1,\ldots,p-2\}$ \\
2. vypo��tame $r=g^k \bmod p$, dor�tame $s$ tak, aby $H(m)=(xr+ks) \bmod p-1$ \\
podpis: $(r,s)$ \\
{\bf Overovanie:} \\
1. pozrieme, �i $1\leq r<p$ \\
2. over�me, �i $y^rr^s \equiv g^{H(m)} \pmod p$ \\
{\bf Bezpe�nos�:} \\
- ak by sme neoverili 1., vieme z 1 podpisu vyrobi� podpis �ub. spr�vy -- dor�tame vhodn� $r$ \\
- viacn�sobn� $k$ vedie k prezradeniu $k$ a n�sledne s�kr. k���a \\
- podpisuje sa hash kv�li forgery
}

\Urob{
\centerline{\large DSA podpis. sch�ma}
{\bf Init:}\\
1. $p,q$ prvo�., $q|p-1$ \\
2. zvol� sa $h\in_R \{2,\ldots,p-2\}$, dor�ta $g=h^{(p-1)/q}$, mus� $g>1$, potom r�d $g$ je $q$ \\
3. pou��vate� zvol� $x\in_R Z_q^*$, dor�ta $y=g^x \bmod p$ \\
private: $x$, public: $(y,p,q,g)$ \\
{\bf Podpisovanie:} \\
1. zvol� sa $k\in_R \{1,\ldots,q-1\}$ \\
2. vypo�. $r=(g^k \bmod p) \bmod q$ \\
3. $s=k^{-1}(H(m)+xr) \bmod q$ \\
4. ak $rs=0$, odznova \\
podpis: $(r,s)$ \\
{\bf Overovanie:} \\
Spo��tame: $w=s^{-1} \bmod q$ \\
$u_1=H(m)w \bmod q$, $u_2=rw \bmod q$ \\
over�me, �i $(g^{u_1}y^{u_2} \bmod p) \bmod q = r$
}

\Urob{
\centerline{\large Slep� podpisy}
podpisuj�ci nevie �o podpisuje, d� sa tak napr. modifikova� RSA
}

\vfill}\end{minipage}

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

\begin{minipage}{\mypagewidth}\vbox to 28cm{
\Urob{
\centerline{\large Diffie-Hellmann protokol}
�loha: dohodn�� session key \\
vopred zn�me: $p$, gener�tor $g$ \\
$A$ si zvol� $\alpha$, $B$ zvol� $\beta$ \\
$A\to B$: $g^\alpha$ \\
$B\to A$: $g^\beta$ \\
k��� je $g^{\alpha\beta}$ \\
{\bf �toky:}\\
Eva: mus� vedie� rie�i� DH probl�m \\
Oscar: uspeje (podvedie oboch)
}

\Urob{
\centerline{\large Station-to-station protokol}
modifik�cia DH, m�me od TA vydan� certifik�ty na podpisy $A$, $B$ \\
$A\to B$: $g^\alpha$ \\
$B\to A$: $g^\beta, E_k(sign_B(g^\alpha,g^\beta)), C(B)$ \\
$A\to B$: $E_k(sign_A(g^\alpha,g^\beta)), C(A)$ \\
($k=g^{\alpha\beta}$) \\
{\bf �toky:}\\
Eva: mus� vedie� rie�i� DH probl�m \\
Oscar: nem� ako zasiahnu�
}

\Urob{
\centerline{\large Interlock protokol}
�loha: s�a�i� v DH situ�ciu Oscarovi \\
$A\to B$: $g^\alpha$ \\
$B\to A$: $g^\beta$ \\
$A$ zvol� $m_A$, $B$ zvol� $m_B$ \\
$A$ spo��ta $E_k(m_A)$, $B$ spo��ta $E_k(m_B)$ \\
$A\to B$: polovica bitov $E_k(m_A)$ \\
$B\to A$: polovica bitov $E_k(m_B)$ \\
$A\to B$: zvy�ok \\
$B\to A$: zvy�ok \\
$A,B$ si overia prenos $m_A,m_B$ secure cestou \\
{\bf �toky:}\\
Eva: mus� vedie� rie�i� DH probl�m \\
Oscar: teoreticky m��e oklama� jed\-n�\-ho, ak zvl�dne naru�i� aj posledn� krok
}

\Urob{
\centerline{\large Shamirov 3-prech. protokol}
treba $E,D$ aby $E_a(D_b(x))=D_b(E_a(x))$ \\
$A\to B$: $E_{k_1}(x)$ \\
$B\to A$: $E_{k_2}(E_{k_1}(x))$ \\
$A\to B$: $D_{k_1}(E_{k_2}(E_{k_1}(x)))=E_{k_2}(x)$ \\
{\bf �toky:}\\
- xor nie je dobr� funkcia \\
Oscar: vie sa tv�ri� ako $B$
}

\Urob{
\centerline{\large Wide Mouth Frog}
pou��vame timestampy $T_x$, trusted autoritu $T$, k���e $KX$ medzi $X$ a $T$ \\
$A\to T$: $A,\{T_A,B,K\}_{KA}$ \\
$T\to B$: $\{T_B,A,K\}_{KB}$ \\
{\bf �toky:}\\
- nonces nezafunguj� \\
- d� sa rozb�ja� k��� a po�as toho si refreshova� timestampy, rie�enie je r�zny form�t posielan�ch
spr�v v 1. a 2. kroku 
}

\Urob{
\centerline{\bf\large ZO SYLABOV CH�BA}
- Yahalom + �al�ie haluzn� protokoly \\
- �toky proti nim a BAN logika \\
- kon�trukcia HMAC \\
- neinterakt�vne d�kazy \\
- overite�n� zdie�anie tajomstva \\
- elektronick� vo�by \\
- symetrick� �ifry 
}

\vfill

\copyright Mi�oF. 2003
}\end{minipage}
\begin{minipage}{\mypagewidth}\vbox to 28cm{
\Urob{
\centerline{\large Needham-Schroeder protokol}
$T$ je TA, $N_x$ s� nonces \\
$A\to T$: $A,B,N_A$ \\
$T\to A$: $\{N_A,B,K,\{K,A\}_{KB}\}_{KA}$ \\
$A\to B$: $\{K,A\}_{KB}$ \\
$B\to A$: $\{N_B\}_K$ \\
$A\to B$: $\{N_B-1\}_K$ \\
{\bf �tok:}\\
�to�n�k rozbije $K$, za�ne od 3. kroku a presved�� $B$ o autenticite $K$
}

\Urob{
\centerline{\large Opraven� NS protokol}
$A\to B$: $A$ \\
$B\to A$: $\{A,N_B\}_{KB}$ \\
$A\to T$: $A,B,N_A,\{A,N_B\}_{KB}$ \\
$T\to A$: $\{N_A,B,K,\{K,N_B,A\}_{KB}\}_{KA}$ \\
$A\to B$: $\{K,N_B,A\}_{KB}$ 
}

\Urob{
\centerline{\large NS Public-Key}
$A\to B$: $\{N_A,A\}_{KB}$ \\
$B\to A$: $\{N_A,N_B\}_{KA}$ \\
$A\to B$: $\{N_B\}_{KB}$ \\
session key: $f(N_A,N_B)$ \\
{\bf �tok:}\\
1. $A\to E$: $\{N_A,A\}_{KE}$ \\
1'. $E(A)\to B$: $\{N_A,A\}_{KB}$ \\
2'. $B\to E(A)$: $\{N_A,N_B\}_{KA}$ \\
2. $E\to A$: $\{N_A,N_B\}_{KA}$ \\
3. $A\to E$: $\{N_B\}_{KE}$ \\
3'. $E(A)\to B$: $\{N_B\}_{KB}$ 
}

\Urob{
\centerline{\large Interakt. dokaz. syst�my}
prover $P$ neobmedzen�, verifier $V$ polynomi�lny pravdepodobnostn�, ak $x\in L$, $V$ skoro ur�ite akceptuje,
inak skoro ur�ite neakceptuje \\
IDS je zero-knowledge, ak z prepisu komunik�cie $P$ a $V$ nevieme zisti� ni�, �o by sme bez nej
nevedeli, form�lne ak $\exists S$, ktor� bude generova� rovnak� komunik�cie (resp. computational
zero knowledge, ak je v�stup $S$ v BPP nerozl��ite�n� od komunik�cie od komunik�cie)
}

\Urob{
\centerline{\large ZK d�kaz pre NIG}
m�me dva grafy $G_1$, $G_2$, $P$ chce presved�i� $G$, �e nie s� izomorfn� \\
protokol: ve�a k�l: \\
1. $V$ d� challenge $\varphi(G_i)$ \\
2. $P$ n�jde $j$ aby $G_j\sim \varphi(G_i)$ \\
3. ak $i\not=j$, s� izom. $\then$ $V$ rejectne 
}

\Urob{
\centerline{\large ZK d�kaz pre IG}
detto �e s� izomorfn� \\
protokol: ve�a k�l: \\
1. $P$ zverejn� $G=\varphi(G_i)$ \\
2. $V$ d� challenge $j$, chce izomorfizmus $G$ a $G_j$ \\
3. $P$ mu ho n�jde
}

\Urob{
\centerline{\large (Feige-)Fiat-Shamir}
S� zn�me $x_1,\ldots,x_k$, tvrd�me, �e vieme ich odmocniny $u_i \pmod n$ \\ 
$P$ zvol� $v\in_R Z_n$, zverejn� $y=v^2 \bmod n$ \\
$V$ zvol� $c_1,\ldots,c_k\in\{0,1\}^k$, zverejn� \\
$P$ zverejn� $z=v\cdot\prod u_i^{c_i}$ \\
$V$ over� $z^2\equiv y\cdot\prod x_i^{c_i}\pmod n$ 
}

\vfill}\end{minipage}
\begin{minipage}{\mypagewidth}\vbox to 28cm{
\Urob{
\centerline{\large Shamirova secret-sharing sch�ma}
$n$ �ud�, treba $t$ z nich, aby mali secret $s$ \\
Zostr. polyn�m $f$ stup�a $<t$ tak, aby $f(0)=s$ \\
$i$-ty �lovek dostane $(i,f(i))$ \\
{\bf �toky:}\\
- ak 1 klame, zrekon�truuj� zle, on si to vie opravi� \\
- rie�enie: obmedzenie vo�by $s$ na men�� interval, aj ke� $t-1$ podv�dza, posledn�ho neoblbn� 
}

\Urob{
\centerline{\large Blakleyho secret-sharing sch�ma}
share: nadrovina v $E_t$
}

\Urob{
\centerline{\large Ide�lna sch�ma}
$S(P_i)$ -- mo�n� shary pre $P_i$ \\
$K$ -- priestor secretov \\
$\rho_i = {\lg |K|\over \lg S(P_i)}$, $\rho = \min \rho_i$ \\
Pre perfektn� sch�mu $\rho\leq 1$, ide�lna je ak $\rho=1$
}

\Urob{
\centerline{\large Chaffing \& Winnowing}
posielame spr�vy, k nim MAC k�dy, pomedzi to posielame balast s random bitmi namiesto MAC k�du,
cenzor nevie, ktor� spr�vy s� z�va�n�
}

\Urob{
\centerline{\large Bit commitment}
m�me $f:\{0,1\}\times X \to Y$ tak�, �e: \\
- z $f(v,r)$ nevieme ur�i� $v$ \\
- nevieme $r_0,r_1$ aby $f(0,r_0)=f(1,r_1)$ \\
napr. $f(v,r)=H(v\|r)$ \\
{\bf Pou�itie:}\\
m�me bit $v$, hod�me si $x$, zverejn�me $f(v,x)$,
t�m sa zavia�eme k $v$, hocikedy m��eme zverejni�
$x$ a dok�za� to 
}

\Urob{
\centerline{\large Oblivious transfer I}
$A$ m� secret $s$, $B$ ho m��e dosta�, $A$ nem� vedie�, �i ho $B$ m� \\
1. $A$ zvol� $p$, $q$, po�le $n=pq$ \\
2. $B$ zvol� $u\in Z_n^*$, po�le $z=u^2\bmod n$ \\
3. $A$ po�le $B$ niektor� odmocninu $z$ \\
4. s pp=1/2 vie $B$ faktorizova�
}

\Urob{
\centerline{\large Oblivious transfer II}
$A$ m� secrety $s_1,\ldots s_n$, $B$ m��e dosta� 1, $A$ nem� vedie�, ktor�\\
$A$ m� verejn� fciu $E$, tajn� $D$ \\
1. $A$ zverejn� n�hodn� $x_1,\ldots x_n$ \\
2. $B$ zvol� n�h. $a$, por�ta $v=x_i\oplus E(A)$, po�le $v$ \\
3. $A$ spo��ta hodnoty $y_j=D(v\oplus x_j)\oplus s_j$, zverejn� $y_j$ \\
4. $B$ si zoberie $y_i$ a spo��ta $s_i$
}

\Urob{
\centerline{\large D�my porovn�vaj� vek}
$A$ m� $i$ rokov, $B$ m� $j$ \\
$A$ m� funkcie $E$ (public), $D$ (private) \\
1. $B$ si zvol� ve�k� $x$, spo��ta $k=E(x)$, po�le $k-j$ \\
2. $A$ vyp. $y_l=D((k-j)+l)$ pre $l\leq 100$ \\
3. $A$ zvol� $p\ll x$, vyp. $z_l=y_l \bmod p$ \\
(mus� by� $\forall u,v; 0<z_u<p-1$ a $|z_u-z_v|\geq 2$, inak 
gen. nov� $p$) \\
4. $A$ zverejn� $z_1,\ldots,z_i,z_{i+1}+1,\ldots,$ $z_{100}+1,p$ \\
5. $B$ over� $z_j \equiv x \pmod p$
}
%\Urob{
%\centerline{\large HMAC}
%}

% 53-62 -- utoky

\vfill}\end{minipage}

\end{document}
