Formatting summaryHEADmaster

1 files changed, 326 insertions, 218 deletions

diff --git a/Summary/Summary.tex b/Summary/Summary.tex
index 8673d16..4b8dbee 100644
--- a/Summary/Summary.tex
+++ b/Summary/Summary.tex
@@ -18,7 +18,7 @@
 \usepackage{xcolor}
 \definecolor{shadecolor}{gray}{0.90}
 
-\title{Cryptography -- Summary}
+\title{Cryptography --- Summary}
 \author{Camil Staps}
 
 \DeclareMathOperator{\ord}{ord}
@@ -26,35 +26,40 @@
 \DeclareMathOperator{\lsb}{lsb}
 \DeclareMathOperator{\Adv}{Adv}
 
-\let\from\leftarrow
+\let\from\leftarrow%
 
-\newcommand{\define}[2]{\begin{shaded*}\textbf{#1}
-
-#2\end{shaded*}}
+\newcommand{\define}[2]{\begin{shaded*}\textbf{#1}\par#2\end{shaded*}}
 
 \begin{document}
 
 \maketitle
 
-%\emph{A summary of the most important ideas and definitions from the Cryptography course given at the Radboud University Nijmegen, spring 2015.}
-%
-%\emph{A picture says more than a thousand words, so it would be wise to look up illustrations in the slides or on the web.}
-
 \section{Stream Ciphers}
-\define{Pseudo Random Generator (PRG)}{A function $G:\{0,1\}^s\to\{0,1\}^n$ where $n>>s$ which is efficiently computable by a deterministic algorithm.}
+\define{Pseudo Random Generator (PRG)}{
+	A function $G:\{0,1\}^s\to\{0,1\}^n$ where $n>>s$ which is efficiently
+	computable by a deterministic algorithm.
+}
 
-\define{Linear Feedback Shift Register (LFSR)}{$L$ 1-bit memory cells that are shifted into the output. Every step, a feedback function determines what value is shifted in.}
+\define{Linear Feedback Shift Register (LFSR)}{
+	$L$ 1-bit memory cells that are shifted into the output. Every step, a
+	feedback function determines what value is shifted in.
+}
 
-The feedback function can be computed and analysed using matrix multiplication and the connection polynomial.
+The feedback function can be computed and analysed using matrix multiplication
+and the connection polynomial.
 
-LFSRs are linear and thus not useful for cryptography. Typically, several LFSRs are combined using a non-linear combining function.
+LFSRs are linear and thus not useful for cryptography. Typically, several LFSRs
+are combined using a non-linear combining function.
 
 \define{Semantic Security (one-time key)}{
-    For an encryption algorithm $E:K\times M\to C$, pick $b\from_R\{0,1\}$. The adversary chooses $m_0,m_1\in M$ with $|m_0|=|m_1|$ and receives $E(k,m_b)$.
+	For an encryption algorithm $E:K\times M\to C$, pick $b\from_R\{0,1\}$. The
+	adversary chooses $m_0,m_1\in M$ with $|m_0|=|m_1|$ and receives
+	$E(k,m_b)$.
 
-    $$\Adv_{\text{SS}}[A,E]=\left|\Pr[EXP(0)=1]-\Pr[EXP(1)=1]\right|$$
+	$$\Adv_{\text{SS}}[A,E]=\left|\Pr[EXP(0)=1]-\Pr[EXP(1)=1]\right|$$
 
-    This should be negligible for all efficient $A$ for $E$ to be semantically secure.
+	This should be negligible for all efficient $A$ for $E$ to be semantically
+	secure.
 }
 
 A stream cipher from a secure PRG is semantically secure.
@@ -62,323 +67,419 @@ A stream cipher from a secure PRG is semantically secure.
 \section{Block Ciphers}
 
 \subsection{Randomness}
-\define{Unpredictability}{When no efficient adversary can predict bit $i+1$ given bits $0\dots i$ with non-negligible probability.}
+\define{Unpredictability}{
+	When no efficient adversary can predict bit $i+1$ given bits $0\dots i$ with
+	non-negligible probability.
+}
 
 Randomness is often measured by \emph{statistical tests}.
 
 \define{Advantage of statistical test $A$ against PRG $G:K\to\{0,1\}^n$}{
-    $$\Adv_{\text{PRG}}[A,G]=\left|\Pr_{k\from K}[A(G(k))=1]-\Pr_{r\from_R\{0,1\}^n}[A(r)=1]\right|$$
+	$$\Adv_{\text{PRG}}[A,G]=\left|\Pr_{k\from
+	K}[A(G(k))=1]-\Pr_{r\from_R\{0,1\}^n}[A(r)=1]\right|$$
 }
 
-$G$ is said to be secure iff the advantage of all efficient statistical tests $A$ against it is negligible.
+$G$ is said to be secure iff the advantage of all efficient statistical tests
+$A$ against it is negligible.
 
 A secure PRG is equivalent to an unpredictable PRG.
 
 \define{Pseudo Random Function (PRF)}{
-    A function $F:K\times X\to Y$ with an efficient algorithm to compute $F(k,x)$.
+	A function $F:K\times X\to Y$ with an efficient algorithm to compute
+	$F(k,x)$.
 }
 
-For a PRF $F:K\times X\to Y$ we define $$\mathrm{Funs}[X,Y]=\{f:X\to Y\}, \quad |\mathrm{Funs}[X,Y]|=|Y|^{|X|},$$ $$S_F=\{F(k,\cdot) \mid k\in K\}, \quad |S_F|=|K|, \quad S_F \subseteq \mathrm{Funs}[X,Y].$$ 
+For a PRF $F:K\times X\to Y$ we define $$\mathrm{Funs}[X,Y]=\{f:X\to Y\}, \quad
+|\mathrm{Funs}[X,Y]|=|Y|^{|X|},$$ $$S_F=\{F(k,\cdot) \mid k\in K\}, \quad
+|S_F|=|K|, \quad S_F \subseteq \mathrm{Funs}[X,Y].$$ 
 
-\define{Security of a PRF}{A PRF $F:K\times X\to Y$ is secure iff a random function $f \from_R \mathrm{Funs}[X,Y]$ is indistinguishable from a random function $g\from_R S_F$.}
+\define{Security of a PRF}{
+	A PRF $F:K\times X\to Y$ is secure iff a random function $f \from_R
+	\mathrm{Funs}[X,Y]$ is indistinguishable from a random function $g\from_R
+	S_F$.
+}
 
-In the security game, an adversary would (repeatedly) ask the result of the function application of either a function from $S_F$ or one from $\mathrm{Funs}[X,Y]$, depending on $b$, and then guess $b'$.
+In the security game, an adversary would (repeatedly) ask the result of the
+function application of either a function from $S_F$ or one from
+$\mathrm{Funs}[X,Y]$, depending on $b$, and then guess $b'$.
 
-Given a secure PRF $F:K\times\{0,1\}^n\to\{0,1\}^n$ we can build a secure PRG $G:K\to\{0,1\}^{nt}$ where $G(k)=F(k,0)||F(k,1)||\dots||F(k,t)$.
+Given a secure PRF $F:K\times\{0,1\}^n\to\{0,1\}^n$ we can build a secure PRG
+$G:K\to\{0,1\}^{nt}$ where $G(k)=F(k,0)||F(k,1)||\dots||F(k,t)$.
 
 \define{Pseudo Random Permutation (PRP)}{
-    A function $E:K\times X\to X$ with an efficient algorithm to compute $E(k,x)$ where $E$ has an inverse $D$ that is also efficiently computable.
+	A function $E:K\times X\to X$ with an efficient algorithm to compute $E(k,x)$
+	where $E$ has an inverse $D$ that is also efficiently computable.
 
-    Or: a PRF with $X=Y$ where $F$ is efficiently invertible.
+	Or: a PRF with $X=Y$ where $F$ is efficiently invertible.
 }
 
-For a PRP $E:K\times X\to X$ we define $$\mathrm{Perms}[X]=\{f:X\to X \mid \text{$f$ is a bijection}\},$$ $$S_E=\{E(k,\cdot) \mid k\in K\}, \quad |S_E|=|K|, S_E \subseteq \mathrm{Perms}[X].$$
+For a PRP $E:K\times X\to X$ we define $$\mathrm{Perms}[X]=\{f:X\to X \mid
+\text{$f$ is a bijection}\},$$ $$S_E=\{E(k,\cdot) \mid k\in K\}, \quad
+|S_E|=|K|, S_E \subseteq \mathrm{Perms}[X].$$
 
-\define{Security of a PRP}{A PRP $E:K\times X\to X$ is secure iff a random function $f\from_R\mathrm{Perms}[X]$ is indistinguishable from a random function $g\from_R S_E$.}
+\define{Security of a PRP}{
+	A PRP $E:K\times X\to X$ is secure iff a random function
+	$f\from_R\mathrm{Perms}[X]$ is indistinguishable from a random function
+	$g\from_R S_E$.
+}
 
 The security game for PRPs is similar to the one for PRFs.
 
-A secure PRP is a secure PRP as long as $X$ is sufficiently large (e.g. the ciphertext space of a modern cipher as AES-128, $2^{128}$).
+A secure PRP is a secure PRP as long as $X$ is sufficiently large (e.g.\ the
+ciphertext space of a modern cipher as AES-128, $2^{128}$).
 
 \subsection{Chosen Plaintext Attacks}
 
 \define{CPA-Security (many-time key)}{
-    For a cipher $(E,D)$ over $(K,M,C)$, pick $b\from_R\{0,1\}$.
-
-    The adversary receives $c_1=E(k,m_{i,b}$ for $i\in[1,q]$ and $m_{i,0},m_{i,1}\in{M}$ with $|m_{i,0}|=|m_{i,1}|$ and outputs $b'$.
-
-    $$\Adv_{\text{CPA}}[A,E]=|\Pr[EXP(0)=1]-\Pr[EXP(1)=1]|$$
+	For a cipher $(E,D)$ over $(K,M,C)$, pick $b\from_R\{0,1\}$.
+	
+	The adversary receives $c_1=E(k,m_{i,b}$ for $i\in[1,q]$ and
+	$m_{i,0},m_{i,1}\in{M}$ with $|m_{i,0}|=|m_{i,1}|$ and outputs $b'$.
+	
+	$$\Adv_{\text{CPA}}[A,E]=|\Pr[EXP(0)=1]-\Pr[EXP(1)=1]|$$
 }
 
-Deterministic ciphers are insecure under CPA (adversary sends $(m,m)$ and $(m,m')$). It can be made secure using randomised encryption or nonce-based encryption (either with a counter, or picked randomly). The CPA model can be extended in the natural way to include nonce-based encryption.
+Deterministic ciphers are insecure under CPA (adversary sends $(m,m)$ and
+$(m,m')$). It can be made secure using randomised encryption or nonce-based
+encryption (either with a counter, or picked randomly). The CPA model can be
+extended in the natural way to include nonce-based encryption.
 
 \subsection{Real world block ciphers}
 Typically done using 
 
 \begin{itemize}
-    \item Applying a round function multiple times, usually with a different round key (i.e. there is a round key derivation algorithm needed)
-    \item Substitution-permutation network
+	\item Applying a round function multiple times, usually with a different
+		round key (i.e.\ there is a round key derivation algorithm needed)
+	\item Substitution-permutation network
 \end{itemize}
 
 \subsubsection{The Feistel structure}
-Divide input in two halves. Put the right halve through a round function with the round key. The new right half is the XOR of the left half with the output of the round function. The left half is the old right half. Repeat this.
+Divide input in two halves. Put the right halve through a round function with
+the round key. The new right half is the XOR of the left half with the output
+of the round function. The left half is the old right half. Repeat this.
 
 \subsubsection{Wide Trail Strategy}
-One bit difference in the plaintext should have massive consequences for the ciphertext. One bit difference in the ciphertext should have massive consequences for the plaintext.
+One bit difference in the plaintext should have massive consequences for the
+ciphertext. One bit difference in the ciphertext should have massive
+consequences for the plaintext.
 
 Use a good permutation-substitution network.
 
 \subsection{Modes of operation}
-Wikipedia has nice visualisations; see \url{https://en.wikipedia.org/wiki/Block\_cipher\_mode\_of\_operation}.
+Wikipedia has nice visualisations; see
+\url{https://en.wikipedia.org/wiki/Block\_cipher\_mode\_of\_operation}.
 
 \define{ECB (Electronic Code Book) Mode}{Simply apply $E$ and $D$.}
 
-\define{CBC (Cipher Block Chaining) Mode}{XOR message block with previous ciphertext block before encrypting. The first block can use an IV, or the encryption of a nonce using a different key.}
+\define{CBC (Cipher Block Chaining) Mode}{
+	XOR message block with previous ciphertext block before encrypting. The first
+	block can use an IV, or the encryption of a nonce using a different key.
+}
 
-CBC-IV with predictable IV is insecure under CPA (sending $m_{1,0}=m_{1,1}=0$ gives $c_1=(IV_1,\pazocal{E}(K,0\oplus IV_1))$; then compute $IV_2$ and ask $m_{2,0}=IV_1\oplus IV_2, m_1\not\in\{0,m_{2,0}\}$. Check if $c_2(IV_2,\pazocal{E}(K,IV_1))=c_1$, in which case $b=0$).
+CBC-IV with predictable IV is insecure under CPA (sending $m_{1,0}=m_{1,1}=0$
+gives $c_1=(IV_1,\pazocal{E}(K,0\oplus IV_1))$; then compute $IV_2$ and ask
+$m_{2,0}=IV_1\oplus IV_2, m_1\not\in\{0,m_{2,0}\}$. Check if
+$c_2(IV_2,\pazocal{E}(K,IV_1))=c_1$, in which case $b=0$).
 
-\define{OFB (Output Feedback) Mode}{Iterate $E$ over an IV ($E(E(\dots E(IV)\dots))$), then use that as a stream cipher (i.e. XOR with the message).}
+\define{OFB (Output Feedback) Mode}{
+	Iterate $E$ over an IV ($E(E(\dots E(IV)\dots))$), then use that as a stream
+	cipher (i.e. XOR with the message).
+}
 
-\define{CFB (Cipher Feedback) Mode}{Similar, but compute $E$ over the previous ciphertext (i.e. after XORing with the message).}
+\define{CFB (Cipher Feedback) Mode}{
+	Similar, but compute $E$ over the previous ciphertext (i.e.\ after XORing
+	with the message).
+}
 
-\define{CTR (Counter) Mode}{Use a nonce/IV $N$ and a counter to generate a stream with $E(N||0)\;||\;E(N||1)\;||\;\dots\;||\;E(N||q)$, and XOR the message with that stream.}
+\define{CTR (Counter) Mode}{
+	Use a nonce/IV $N$ and a counter to generate a stream with
+	$E(N||0)\;||\;E(N||1)\;||\;\dots\;||\;E(N||q)$, and XOR the message with that
+	stream.
+}
 
 \section{Integrity}
 
 \begin{itemize}
-    \item Accidental errors (noise)
-        
-        Use CRC or ECC (simple checksums)
-    \item Simple manipulations
-        
-        Use hash functions (doesn't stop active attacker)
-    \item Active attacks (need to prevent an attacker from creating a valid integrity digest on some data)
-        
-        Use MACs (requires origin authentication)
-    \item Repudiation attacks (one cannot deny communication later)
-        
-        Use digital signatures
+	\item Accidental errors (noise)
+
+		Use CRC or ECC (simple checksums)
+	\item Simple manipulations
+
+		Use hash functions (doesn't stop active attacker)
+	\item Active attacks (need to prevent an attacker from creating a valid
+		integrity digest on some data)
+
+		Use MACs (requires origin authentication)
+	\item Repudiation attacks (one cannot deny communication later)
+
+		Use digital signatures
 \end{itemize}
 
 \subsection{Hash functions}
-\define{Cryptographic hash function}{A function $h:\{0,1\}^*\to\{0,1\}^n$ with the properties
-
-    \begin{description}
-        \item[Collision resistance] It is infeasible to find $m,m'$ with $m\neq m'$ and $h(m)=h(m')$
-        \item[Pre-image resistance] Given $h(m)$, it is infeasible to compute $m$ 
-        \item[Second pre-image resistance] Given $m$ it is infeasible to find $m'\neq m$ with $h(m)=h(m')$
-    \end{description}
+\define{Cryptographic hash function}{
+	A function $h:\{0,1\}^*\to\{0,1\}^n$ with the properties
+
+	\begin{description}
+		\item[Collision resistance] It is infeasible to find $m,m'$ with $m\neq
+			m'$ and $h(m)=h(m')$
+		\item[Pre-image resistance] Given $h(m)$, it is infeasible to compute
+			$m$ 
+		\item[Second pre-image resistance] Given $m$ it is infeasible to find
+			$m'\neq m$ with $h(m)=h(m')$
+	\end{description}
 }
 
-From a block cipher one can make a hash function by using CBC mode, a fixed key and a fixed IV, and outputting the last ciphertext block only.
+From a block cipher one can make a hash function by using CBC mode, a fixed key
+and a fixed IV, and outputting the last ciphertext block only.
 
 \subsubsection{Merkle-Damg{\aa}rd iterating mode}
-Use a fixed-input-length compression function, and repeatedly feed blocks of input to it, starting with an IV. The hash function inherits properties of the compression function.
+Use a fixed-input-length compression function, and repeatedly feed blocks of
+input to it, starting with an IV. The hash function inherits properties of the
+compression function.
 
 \subsubsection{The sponge construction}
 Generalisation of a hash function: XOF.
 
-\define{Extendable Output Function (XOF)}{A function $f:\{0,1\}^*\to \{0,1\}^{nk}$ for all $k\in\mathbb{N}^+$ and some $n\in\mathbb{N}$.}
+\define{Extendable Output Function (XOF)}{
+	A function $f:\{0,1\}^*\to \{0,1\}^{nk}$ for all $k\in\mathbb{N}^+$ and some
+	$n\in\mathbb{N}$.
+}
 
-Using a $b$-bit permutation $f$ with $b=r+c$ ($r$ for rate, $c$ for capacity). $r$ bits of (padded) input are XOR-ed with the previous `outer state', then put through $f$ together with the $c$-bit `inner state'. After full absorption, the $r$-bit outer state may be outputted as many times as you want, while also applying $f$.
+Using a $b$-bit permutation $f$ with $b=r+c$ ($r$ for rate, $c$ for capacity).
+$r$ bits of (padded) input are XOR-ed with the previous `outer state', then put
+through $f$ together with the $c$-bit `inner state'. After full absorption, the
+$r$-bit outer state may be outputted as many times as you want, while also
+applying $f$.
 
 This reduces the problem to building a strong permutation.
 
 \subsection{Message Authentication Codes}
 
 \define{MAC}{
-    $I=(S,V)$ over $(K,M,T)$ with
-    \begin{align*}
-        S : K \times M &\to T\\
-        V : K \times M \times T &\to \{\text{``yes''},\text{``no''}\}
-    \end{align*}
-    $$\forall_{k\in{K},m\in{M}}\left[V(k,m,S(k,m)) = \text{``yes''}\right]$$
+	$I=(S,V)$ over $(K,M,T)$ with
+	\begin{align*}
+		S : K \times M &\to T\\
+		V : K \times M \times T &\to \{\text{``yes''},\text{``no''}\}
+	\end{align*}
+	$$\forall_{k\in{K},m\in{M}}\left[V(k,m,S(k,m)) = \text{``yes''}\right]$$
 }
 
 \define{Chosen message attack \& existential forgery}{
+	Existenial forgery, to create a \emph{new} valid message-tag pair $(m,t)$.
 
-    Existenial forgery, to create a \emph{new} valid message-tag pair $(m,t)$.
-
-    Adversary may send $q$ messages $m_1,\dots,m_q$ to the challenger and receives $t_1,\dots,t_q$ where $t_i=S(k,m_i)$. After this, the adversary has to guess a \emph{new} pair $(m,t)$. The challenger outputs 1 iff $V(k,m,t)=\text{``yes''}$.
+	Adversary may send $q$ messages $m_1,\dots,m_q$ to the challenger and
+	receives $t_1,\dots,t_q$ where $t_i=S(k,m_i)$. After this, the adversary has
+	to guess a \emph{new} pair $(m,t)$. The challenger outputs 1 iff
+	$V(k,m,t)=\text{``yes''}$.
 
-    $$\Adv_{\text{MAC}}[A,I] = \Pr[\text{Challenger outputs 1}]$$
+	$$\Adv_{\text{MAC}}[A,I] = \Pr[\text{Challenger outputs 1}]$$
 }
 
-A secure PRF $F:K\times X\to Y$ gives a secure MAC with $S(k,m):=F(k,m)$ if $1/|Y|$ is negligible.
+A secure PRF $F:K\times X\to Y$ gives a secure MAC with $S(k,m):=F(k,m)$ if
+$1/|Y|$ is negligible.
 
 \subsubsection{CBC-MAC}
 
 \define{CBC-MAC}{
-    Pad the data. Encrypt using the block cipher of choice in CBC mode. Take the final block of the MAC.
+	Pad the data. Encrypt using the block cipher of choice in CBC mode. Take
+	the final block of the MAC.
 }
 
 ECBC-MAC uses a second key $k_1\neq k$ to encrypt the last block.
 
-HMAC uses repeatedly feeding blocks from $k||m$ to a hash (slides) or hashing $k||m$ directly.
+HMAC uses repeatedly feeding blocks from $k||m$ to a hash (slides) or hashing
+$k||m$ directly.
 
 \subsection{Authenticated Encryption}
-Protection against a CPA attack (\textbf{confidentiality}) and existential unforgeability under a chosen message attack (\textbf{integrity}).
+Protection against a CPA attack (\textbf{confidentiality}) and existential
+unforgability under a chosen message attack (\textbf{integrity}).
 
 \define{Authenticated Encryption (AE) system}{
-    A pair $(E,D)$ over $(K,M,N,C)$ where
-    \begin{align*}
-        E: K\times M\times N &\to C \\
-        D: K\times C\times N &\to M \cup \{\bot\}
-    \end{align*}
-    that provides semantic security against CPA and ciphertext integrity.
+	A pair $(E,D)$ over $(K,M,N,C)$ where
+	\begin{align*}
+		E: K\times M\times N &\to C \\
+		D: K\times C\times N &\to M \cup \{\bot\}
+	\end{align*}
+	that provides semantic security against CPA and ciphertext integrity.
 }
 
 \define{Ciphertext Integrity}{
-    Adversary may send $q$ messages $m_1,\dots,m_q$ to the challenger and receives $c_1,\dots,c_q$ where $c_i=E(k,m_i)$. After this, the adversary has to guess a \emph{new} ciphertext $c$. The challenger outputs 1 iff $D(k,c)\neq\bot$.
+	Adversary may send $q$ messages $m_1,\dots,m_q$ to the challenger and
+	receives $c_1,\dots,c_q$ where $c_i=E(k,m_i)$. After this, the adversary has
+	to guess a \emph{new} ciphertext $c$. The challenger outputs 1 iff
+	$D(k,c)\neq\bot$.
 
-    $$\Adv_{\text{CI}}[A,E]=\Pr[\text{Challenger outputs 1}]$$
+	$$\Adv_{\text{CI}}[A,E]=\Pr[\text{Challenger outputs 1}]$$
 }
 
-Encrypt-and-MAC (SSH), MAC-then-Encrypt (SSL), Encrypt-then-MAC (IPsec; this is the best).
+Encrypt-and-MAC (SSH), MAC-then-Encrypt (SSL), Encrypt-then-MAC (IPsec; this is
+the best).
 
 \section{Public Key Crypto}
-To resolve key management, distribution and revocation problems with symmetric key crypto.
+To resolve key management, distribution and revocation problems with symmetric
+key crypto.
 
-Typically using a \emph{trapdoor one-way function} (one-way, unless you know the (key to the) trapdoor), e.g. factorisation or discrete log.
+Typically using a \emph{trapdoor one-way function} (one-way, unless you know
+the (key to the) trapdoor), e.g. factorisation or discrete log.
 
 \define{Public-key Encryption system}{
-    A triple $(G,E,D)$ over $(PK,SK,M,C)$ where
-    \begin{align*}
-        G &: \dots \to PK \times SK \quad \text{(randomised key generation)}\\
-        E &: PK \times M \to C \quad \text{(randomised encryption)}\\
-        D &: SK \times C \to M \quad \text{(deterministic decryption)}
-    \end{align*}
-    and
-    $$\forall_{pk\in{PK},sk\in{SK},m\in{M}}\left[D(sk,E(pk,m))=m\right].$$
+	A triple $(G,E,D)$ over $(PK,SK,M,C)$ where
+	\begin{align*}
+		G &: \dots \to PK \times SK \quad \text{(randomised key generation)}\\
+		E &: PK \times M \to C \quad \text{(randomised encryption)}\\
+		D &: SK \times C \to M \quad \text{(deterministic decryption)}
+	\end{align*}
+	and
+	$$\forall_{pk\in{PK},sk\in{SK},m\in{M}}\left[D(sk,E(pk,m))=m\right].$$
 }
 
-\define{Semantic Security for Randomised PK Encryption (against eavesdropping only)}{
-    Challenger picks $b\from_R\{0,1\}$ and $(pk,sk)\from G$. Adversary receives the public key. She sends $m_0,m_1\in{M}$ with $|m_0|=|m_1|$ and receives $c=E(pk,m_b)$. She then outputs $b'$.
+\define{Semantic Security for Randomised PK Encryption (against eavesdropping
+	only)}{
+	Challenger picks $b\from_R\{0,1\}$ and $(pk,sk)\from G$. Adversary receives
+	the public key. She sends $m_0,m_1\in{M}$ with $|m_0|=|m_1|$ and receives
+	$c=E(pk,m_b)$. She then outputs $b'$.
 
-    $$\Adv_{\text{SS}}[A,E]=|\Pr[EXP(0)=1]-\Pr[EXP(1)=1]|$$
+	$$\Adv_{\text{SS}}[A,E]=|\Pr[EXP(0)=1]-\Pr[EXP(1)=1]|$$
 
-    $\Adv_{\text{SS}}[A,E]$ is negligible for all efficient $A$ $\leftrightarrow$ $E$ is secure under IND-CPA (indistinguishable under chosen plaintext attacks).
+	$\Adv_{\text{SS}}[A,E]$ is negligible for all efficient $A$ $\leftrightarrow$
+	$E$ is secure under IND-CPA (indistinguishable under chosen plaintext
+	attacks).
 }
 
 \define{Discrete logarithm problem}{
-    Let $G$ be a finite group and $g$ one of its generators. Write $G=\{1,g,g^2,\dots,g^{q-1}\}$ where $q=|G|$.
+	Let $G$ be a finite group and $g$ one of its generators. Write
+	$G=\{1,g,g^2,\dots,g^{q-1}\}$ where $q=|G|$.
 
-    The problem is to find $x$ from $b=g^x$.
+	The problem is to find $x$ from $b=g^x$.
 }
 
 \define{Chosen Ciphertext Attack (CCA) Security}{
-    $\pazocal{E}=(G,E,D)$ over $(M,C)$, $b\from_R\{0,1\}$, $(pk,sk)\from G$.
+	$\pazocal{E}=(G,E,D)$ over $(M,C)$, $b\from_R\{0,1\}$, $(pk,sk)\from G$.
 
-    Adversary receives $pk$.
+	Adversary receives $pk$.
 
-    Phase 1: adversary receives $m_i=D(k,c_i)$ for $c_i\in\{c_0,\dots,c_q\}$.
+	Phase 1: adversary receives $m_i=D(k,c_i)$ for $c_i\in\{c_0,\dots,c_q\}$.
 
-    Adversary receives $c=E(pk,m_b)$ after sending $m_0,m_1\in{M}$, $|m_0|=|m_1|$.
+	Adversary receives $c=E(pk,m_b)$ after sending $m_0,m_1\in{M}$,
+	$|m_0|=|m_1|$.
 
-    Phase 2: adversary receives $m_i=D(k,c_i)$ for $c_i\in\{c_0,\dots,c_q\}$ and $c_i\neq c$.
+	Phase 2: adversary receives $m_i=D(k,c_i)$ for $c_i\in\{c_0,\dots,c_q\}$ and
+	$c_i\neq c$.
 
-    Adversary outputs $b'$.
+	Adversary outputs $b'$.
 
-    $$\Adv_{\text{CCA}}[A,\pazocal{E}]=|\Pr[EXP(0)=1]-\Pr[EXP(1)=1]|$$
+	$$\Adv_{\text{CCA}}[A,\pazocal{E}]=|\Pr[EXP(0)=1]-\Pr[EXP(1)=1]|$$
 
-    $\pazocal{E}$ is semantically secure under IND-CCA if for all efficient $A$ $\Adv_{\text{CCA}}[A,\pazocal{E}]$ negligible is.
+	$\pazocal{E}$ is semantically secure under IND-CCA if for all efficient $A$
+	$\Adv_{\text{CCA}}[A,\pazocal{E}]$ negligible is.
 }
 
 \subsection{RSA}
 
 \define{RSA}{
-    \begin{enumerate}
-        \item Choose primes $p,q$
-        \item Take $N=pq$, recall $\phi(N)=(p-1)(q-1)$
-        \item Pick $e$ co-prime to $\phi(N)$
-        \item Let $pk=(N,e)$, $sk=(N,d)$ where $ed\equiv1\pmod{\phi(N)}$
-    \end{enumerate}
-    
-    Then $E((N,e),m)=m^e\pmod{N}$ and $D((N,d),c)=c^d\pmod{N}$. Typically done using square-and-multiply.
+	\begin{enumerate}
+		\item Choose primes $p,q$
+		\item Take $N=pq$, recall $\phi(N)=(p-1)(q-1)$
+		\item Pick $e$ co-prime to $\phi(N)$
+		\item Let $pk=(N,e)$, $sk=(N,d)$ where $ed\equiv1\pmod{\phi(N)}$
+	\end{enumerate}
+
+	Then $E((N,e),m)=m^e\pmod{N}$ and $D((N,d),c)=c^d\pmod{N}$. Typically done
+	using square-and-multiply.
 
-    Problem: to recover $x$ from $C=x^e\pmod{N}$.
+	Problem: to recover $x$ from $C=x^e\pmod{N}$.
 }
 
-Textbook RSA is insecure because it is deterministic (not secure under IND-CCA), and changes to ciphertexts are predictable. In practice, padding is used (e.g. OAEP, section \ref{sec:oaep}).
+Textbook RSA is insecure because it is deterministic (not secure under
+IND-CCA), and changes to ciphertexts are predictable. In practice, padding is
+used (e.g. OAEP, section \ref{sec:oaep}).
 
-There exist side-channel attacks against RSA when square-and-multiply is implemented in the natural way; power consumption reveals location of the ones in the key.
+There exist side-channel attacks against RSA when square-and-multiply is
+implemented in the natural way; power consumption reveals location of the ones
+in the key.
 
 \subsection{Elliptic Curve Cryptography (ECC)}
 
-Much smaller keylengths than RSA (and no exponential growth when technology advances).
+Much smaller keylengths than RSA (and no exponential growth when technology
+advances).
 
 \begin{itemize}
-    \item ECC protocol, built on
-    \item Point/Div. multiplication, built on
-    \item Group operations, built on
-    \item Finite field arithmetic
+	\item ECC protocol, built on
+	\item Point/Div. multiplication, built on
+	\item Group operations, built on
+	\item Finite field arithmetic
 \end{itemize}
 
 \define{Elliptic Curve}{
-    $\pazocal{E}$ over $GF(p)$ is an equation of the form $$y^2=x^3+ax+b$$ where $4a^3+27b^2\neq0$, $a,b\in GF(p)$.
+	$\pazocal{E}$ over $GF(p)$ is an equation of the form $$y^2=x^3+ax+b$$ where
+	$4a^3+27b^2\neq0$, $a,b\in GF(p)$.
 }
 
 \define{Point on an Elliptic Curve $\pazocal{E}$}{
-    An $P=(x,y)$ with $x,y\in GF(p)$ that satisfies $\pazocal{E}$.
-
-    The order of $P$ is the smallest $m$ s.t. $mP=O$. %todo what is O??? (lect12-slide5)
+	An $P=(x,y)$ with $x,y\in GF(p)$ that satisfies $\pazocal{E}$.
+	
+	The order of $P$ is the smallest $m$ s.t. $mP=O$. %todo what is O??? (lect12-slide5)
 }
 
 \define{Addition on an elliptic curve}{
-    For $P=(x_1,y_1)$ and $Q=(x_2,y_2)$ we can calculate $P+Q=R=(x_3,y_3)$ with
-    \begin{align*}
-        x_3 &= \lambda^2 - x_1 - x_2\\
-        y_3 &= \lambda(x_1 - x_3) - y_1
-    \end{align*}
-    where $\lambda$ is the slope of the line through $P$ and $Q$ (or the tangent of $\pazocal{E}$ on $P$ when $P=Q$), i.e.
-    $$\lambda = 
-    \begin{cases}
-        \frac{y_2-y_1}{x_2-x_1} &\text{if $P\neq Q$}\\
-        \frac{3x_1^2+a}{2y_1} &\text{if $P=Q$}
-    \end{cases}$$
+	For $P=(x_1,y_1)$ and $Q=(x_2,y_2)$ we can calculate $P+Q=R=(x_3,y_3)$ with
+	\begin{align*}
+		x_3 &= \lambda^2 - x_1 - x_2\\
+		y_3 &= \lambda(x_1 - x_3) - y_1
+	\end{align*}
+	where $\lambda$ is the slope of the line through $P$ and $Q$ (or the tangent
+	of $\pazocal{E}$ on $P$ when $P=Q$), i.e.
+	$$\lambda = 
+	\begin{cases}
+		\frac{y_2-y_1}{x_2-x_1} &\text{if $P\neq Q$}\\
+		\frac{3x_1^2+a}{2y_1} &\text{if $P=Q$}
+	\end{cases}$$
 }
 
-Scalar multiplication can be done using double-and-add, similar to square-and-multiply.
+Scalar multiplication can be done using double-and-add, similar to
+square-and-multiply.
 
 \define{EC Key Pair generation}{
-    Domain parameters: 
-    
-    \begin{itemize}
-        \item $GF(p)$, a finite field
-        \item $\pazocal{E}(GF(p))$, an elliptic curve over $GF(p)$
-        \item $G\in\pazocal{E}(GF(p))$, a generator in $\pazocal{E}$
-    \end{itemize}
+	Domain parameters:
+
+	\begin{itemize}
+		\item $GF(p)$, a finite field
+		\item $\pazocal{E}(GF(p))$, an elliptic curve over $GF(p)$
+		\item $G\in\pazocal{E}(GF(p))$, a generator in $\pazocal{E}$
+	\end{itemize}
 
-    Algorithm:
+	Algorithm:
 
-    \begin{enumerate}
-        \item Select $d\from_R[1,n-1]$
-        \item Compute $Q=dG$
-        \item Take $Q$ as public key and $d$ as private key
-    \end{enumerate}
+	\begin{enumerate}
+		\item Select $d\from_R[1,n-1]$
+		\item Compute $Q=dG$
+		\item Take $Q$ as public key and $d$ as private key
+	\end{enumerate}
 }
 
 \define{Diffie-Hellman in ECC setting}{
-    Use $d_A,d_B$ as privates and $Q_A=d_AG,Q_B=d_BG$ as publics. Both sides can compute $d_Ad_BG$.
+	Use $d_A,d_B$ as privates and $Q_A=d_AG,Q_B=d_BG$ as publics. Both sides can
+	compute $d_Ad_BG$.
 }
 
 \subsection{Digital Signatures}
 
 \define{Digital Signature}{
-    A crypto primitive that provides
+	A crypto primitive that provides
 
-    \begin{itemize}
-        \item Data origin authentication of the signer
-        \item Non-repudiation
-    \end{itemize}
+	\begin{itemize}
+		\item Data origin authentication of the signer
+		\item Non-repudiation
+	\end{itemize}
 
-    Typically a pair $(S,V)$ for \emph{signing} and \emph{verification}.
+	Typically a pair $(S,V)$ for \emph{signing} and \emph{verification}.
 }
 
-Should be \emph{easy to sign}, \emph{easy to verify}, \emph{hard to forge}. Should prevent \emph{modification attacks} and \emph{existential forgery}.
+Should be \emph{easy to sign}, \emph{easy to verify}, \emph{hard to forge}.
+Should prevent \emph{modification attacks} and \emph{existential forgery}.
 
 \subsubsection{With RSA}
-$S(m)=h^d(m)\pmod{N}$ where $h$ is a hash function. 
+$S(m)=h^d(m)\pmod{N}$ where $h$ is a hash function.
 
 $V(m,s)$ checks if $s^e\bmod{N}=h(m)$.
 
@@ -386,44 +487,45 @@ $V(m,s)$ checks if $s^e\bmod{N}=h(m)$.
 For a message $m$, compute a hash $h=H(m)$.
 
 \define{DSA Signing}{
-    \begin{enumerate}
-        \item Choose $k\from_R(0,q)$
-        \item Compute $r=g^k\bmod{p}\pmod{q}$
-        \item Compute $s=h+rx/k\bmod{q}$
-        \item Output $(r,s)$
-    \end{enumerate}
+	\begin{enumerate}
+		\item Choose $k\from_R(0,q)$
+		\item Compute $r=g^k\bmod{p}\pmod{q}$
+		\item Compute $s=h+rx/k\bmod{q}$
+		\item Output $(r,s)$
+	\end{enumerate}
 }
 
 \define{DSA Verification}{
-    \begin{enumerate}
-        \item Compute $a=h/s\pmod{q}$
-        \item Compute $b=r/s\pmod{q}$
-        \item Compute $v=g^ay^b\bmod{p}\pmod{q}$
-        \item Accept iff $v=r$
-    \end{enumerate}
+	\begin{enumerate}
+		\item Compute $a=h/s\pmod{q}$
+		\item Compute $b=r/s\pmod{q}$
+		\item Compute $v=g^ay^b\bmod{p}\pmod{q}$
+		\item Accept iff $v=r$
+	\end{enumerate}
 }
 
 \subsubsection{With ECC}
-Consider a message $m$ with hash $e=\mathrm{SHA-1}(m)$ and a public key $Q=dP$ with private key $d$.
+Consider a message $m$ with hash $e=\mathrm{SHA-1}(m)$ and a public key $Q=dP$
+with private key $d$.
 
 \define{ECC Signing}{
-    \begin{enumerate}
-        \item Choose $k\from_R[1,n-1]$
-        \item Compute $kP=(x_1,y_1)$ and $r=x_1$, both $\bmod n$
-        \item Compute $k^{-1}\bmod n$
-        \item Compute $s=k^{-1}(e+dr)\bmod n$
-        \item Output $(r,s)$
-    \end{enumerate}
+	\begin{enumerate}
+		\item Choose $k\from_R[1,n-1]$
+		\item Compute $kP=(x_1,y_1)$ and $r=x_1$, both $\bmod n$
+		\item Compute $k^{-1}\bmod n$
+		\item Compute $s=k^{-1}(e+dr)\bmod n$
+		\item Output $(r,s)$
+	\end{enumerate}
 }
 
 \define{ECC Verification}{
-    \begin{enumerate}
-        \item Verify $r,s\in[1,n-1]$
-        \item Compute $w=s^{-1}\bmod n$
-        \item Compute $u_1=ew\bmod n$ and $u_2=rw\bmod n$
-        \item Compute $u_1P+u_2Q=(x_1,y_1)$ and $v=x_1\bmod n$
-        \item Accept iff $v=r$
-    \end{enumerate}
+	\begin{enumerate}
+		\item Verify $r,s\in[1,n-1]$
+		\item Compute $w=s^{-1}\bmod n$
+		\item Compute $u_1=ew\bmod n$ and $u_2=rw\bmod n$
+		\item Compute $u_1P+u_2Q=(x_1,y_1)$ and $v=x_1\bmod n$
+		\item Accept iff $v=r$
+	\end{enumerate}
 }
 
 \subsection{Optimised Asymmetric Encryption Padding (OAEP)}
@@ -432,38 +534,44 @@ Consider a message $m$ with hash $e=\mathrm{SHA-1}(m)$ and a public key $Q=dP$ w
 Using two hash functions $G$ and $H$.
 
 \define{OAEP}{
-    \begin{enumerate}
-        \item Pad message $m$ by appending \texttt{01} and zeros, yielding $m'$
-        \item Pick a random $r$
-        \item Compute $X=G(r)\oplus m'$
-        \item Compute $Y=r\oplus H(X)$
-        \item Encrypt $X||Y$, e.g. with RSA
-    \end{enumerate}
+	\begin{enumerate}
+		\item Pad message $m$ by appending \texttt{01} and zeros, yielding $m'$
+		\item Pick a random $r$
+		\item Compute $X=G(r)\oplus m'$
+		\item Compute $Y=r\oplus H(X)$
+		\item Encrypt $X||Y$, e.g. with RSA
+	\end{enumerate}
 }
 
 \subsection{Diffie-Hellman key exchange}
-Protocol for two clients to agree on a shared secret over an unsecure channel.
+Protocol for two clients to agree on a shared secret over an insecure channel.
 
 \define{Diffie-Hellman key exchange}{
-    Alice picks $a\from_R G$; Bob picks $b\from_R G$.
-    \begin{align*}
-        A \to B &: g^a \bmod p\\
-        B \to A &: g^b \bmod p
-    \end{align*}
-    Both can compute $(g^a)^b=g^{ab}=(g^b)^a$.
+	Alice picks $a\from_R G$; Bob picks $b\from_R G$.
+	\begin{align*}
+		A \to B &: g^a \bmod p\\
+		B \to A &: g^b \bmod p
+	\end{align*}
+	Both can compute $(g^a)^b=g^{ab}=(g^b)^a$.
 }
 
-How to do this with three parties in one round? With two additive groups $G_1,G_2$ and a bilinear pairing $\phi:G_1\times G_2\to G_T$.
+How to do this with three parties in one round? With two additive groups
+$G_1,G_2$ and a bilinear pairing $\phi:G_1\times G_2\to G_T$.
 
 \define{Bilinear Pairing}{
-    A mapping $\phi:G_1\times G_2\to G_T$ such that $\phi$ is
-    \begin{itemize}
-        \item Bilinear: $$\forall_{P\in G_1,Q\in G_2}\left[\phi(aP,bQ)=\phi(P,Q)^{ab}\right]$$
-        \item Non-degenerate: $$\exists_{P\in G_1,Q\in G_2}\left[\phi(P,Q)\neq1\right]$$
-        \item Computable efficiently
-    \end{itemize}
+	A mapping $\phi:G_1\times G_2\to G_T$ such that $\phi$ is
+	\begin{itemize}
+		\item Bilinear: $$\forall_{P\in G_1,Q\in
+			G_2}\left[\phi(aP,bQ)=\phi(P,Q)^{ab}\right]$$
+		\item Non-degenerate: $$\exists_{P\in G_1,Q\in
+			G_2}\left[\phi(P,Q)\neq1\right]$$
+		\item Computable efficiently
+	\end{itemize}
 }
 
-One-round tripartite Diffie-Hellman with domain parameter $P$ and secrets $a,b,c$ can now be done by sending $aP,bP,cP$, such that every party can compute $\phi(P,P)^{abc}$. It relies on it being hard to compute $\phi(P,P)^{abc}$ given $P,aP,bP,cP$.
+One-round tripartite Diffie-Hellman with domain parameter $P$ and secrets
+$a,b,c$ can now be done by sending $aP,bP,cP$, such that every party can
+compute $\phi(P,P)^{abc}$. It relies on it being hard to compute
+$\phi(P,P)^{abc}$ given $P,aP,bP,cP$.
 
 \end{document}