Removed spaces in path

1 files changed, 0 insertions, 219 deletions

diff --git a/Assignment 3/CamilStaps-assignment3.tex b/Assignment 3/CamilStaps-assignment3.tex
deleted file mode 100644
index da7d433..0000000
--- a/Assignment 3/CamilStaps-assignment3.tex
+++ /dev/null
@@ -1,219 +0,0 @@
-\documentclass[a4paper]{article}
-
-\usepackage{amsmath,amssymb,amsthm,url,graphicx,comment,enumerate,color,array,inconsolata,minted,subcaption,adjustbox}
-\usepackage[margin=2cm]{geometry}
-
-\title{Homework $3$}
-\author{Camil Staps (s4498062)}
-
-\newcommand{\R}{\mathbb R}
-\newcommand{\Q}{\mathbb Q}
-\newcommand{\Z}{\mathbb Z}
-\newcommand{\N}{\mathbb N}
-\newcommand{\F}{\mathbb F}
-\newcommand{\Zstar}{\Z^{^*}}
-
-\DeclareMathOperator{\ord}{ord}
-\DeclareMathOperator{\lcm}{lcm}
-\DeclareMathOperator{\lsb}{lsb}
-\DeclareMathOperator{\Prob}{Pr}
-\DeclareMathOperator{\Adv}{Adv}
-
-\DeclareMathAlphabet{\pazocal}{OMS}{zplm}{m}{n}
-
-\usepackage{tikz}
-\usetikzlibrary{shapes.multipart,shapes.gates.logic.IEC,shapes.arrows,positioning,decorations.markings}
-
-\begin{document}
-\maketitle
-
-\section*{Solution}
-
-\begin{enumerate}
-\item  
-	\begin{enumerate}
-	\item 
-		\begin{enumerate}
-		\item 
-			\begin{minipage}[t]{\linewidth}
-			\centering
-			\adjustbox{valign=t}{%
-			\begin{tikzpicture}[LFSR/.style={rectangle split, rectangle split horizontal=true, rectangle split parts=#1, draw, anchor=center}, ARROW/.style={draw,thick,single arrow,single arrow head extend=3pt,transform shape}]]
-			\node[LFSR=5] (register) {\nodepart{one}$s_4$\nodepart{two}$s_3$\nodepart{three}$s_2$\nodepart{four}$s_1$\nodepart{five}$s_0$};
-			\node[circle, inner sep=0, below=6mm of register.one south] (xor) {\scalebox{1}{$\oplus$}};
-			\draw[->] (register.one south) -- (xor);
-			\draw[->] (register.two south) |- (xor);
-			\draw (register.three south) |- (xor);
-			\draw (register.five south) |- (xor);
-			\draw (xor.west) -- ++(left:4mm) node[anchor=north] (hook1) {};
-			\draw[->] (hook1) |- (register.one west);
-			\draw[->] (register.five east) -- ++(right:4mm) node[anchor=west] {$\dots$};
-			\end{tikzpicture}
-			}
-			\end{minipage}
-
-		\item 
-			$$M = \begin{pmatrix}
-			0 & 1 & 0 & 0 & 0 \\
-			0 & 0 & 1 & 0 & 0 \\
-			0 & 0 & 0 & 1 & 0 \\
-			0 & 0 & 0 & 0 & 1 \\
-			1 & 0 & 1 & 1 & 1
-			\end{pmatrix}$$
-
-		\item
-			That bit stream contains $0^L$. We know that $0 \oplus \dots \oplus 0 = 0$, so after $0^L$, only zeros can follow. However, this is not the case. Therefore, this bit stream cannot be a part of the output of this LFSR.
-
-		\item 
-			% In figure \ref{fig:1ai} we see that $c_L=1$. We then check if $C(X)$ is an irreducible polynomial. Since $C(X)=\dots+1$ and $\deg(C(X))=5$, we only need to consider products of two polynomials $f_1,f_2$ for which $\deg(f_1)+\deg(f_2)=5$ and both polynomials have a term $1$. We then check all possible combinations:
-
-			% \begin{table}[h]
-			% \centering
-			% \begin{tabular}{>{$}l<{$} >{$}l<{$} | >{$}l<{$}}
-			% f_1(x) 						& f_2(x) 			& (f_1 \circ f_2)(x) = (f_2 \circ f_1)(x) \\\hline
-			% x^4 + x^3 + x^2 + x + 1		& x + 1				& x^5 + 1 \\
-			% x^4 + x^3 + x^2 + 1			& x + 1				& x^5 + x^2 + x + 1 \\
-			% x^4 + x^3 + x + 1			& x + 1				& x^5 + x^3 + x^2 + 1 \\
-			% x^4 + x^3 + 1				& x + 1				& x^5 + x^3 + x + 1\\
-			% x^4 + x^2 + x + 1			& x + 1				& x^5 + x^4 + x^3 + 1\\
-			% x^4 + x^2 + 1				& x + 1				& x^5 + x^4 + x^3 + x^2 + x + 1\\
-			% x^4 + x + 1					& x + 1				& x^5 + x^4 + x^2 + 1\\
-			% x^4 + 1						& x + 1				& x^5 + x^4 + x + 1\\
-
-			% x^3 + x^2 + x + 1			& x^2 + x + 1		& x^5 + x^3 + x^2 + 1\\
-			% x^3 + x^2 + x + 1			& x^2 + 1			& x^5 + x^4 + x + 1\\
-			% x^3 + x^2 + 1				& x^2 + x + 1		& x^5 + x + 1\\
-			% x^3 + x^2 + 1				& x^2 + 1			& x^5 + x^4 + x^3 + x + 1\\
-			% x^3 + x + 1					& x^2 + x + 1		& x^5 + x^4 + 1\\
-			% x^3 + x + 1					& x^2 + 1			& x^5 + x^2 + x + 1\\
-			% x^3 + 1						& x^2 + x + 1		& x^5 + x^4 + x^3 + x^2 + x + 1\\
-			% x^3 + 1						& x^2 + 1			& x^5 + x^3 + x^2 + 1\\
-			% \end{tabular}
-			% \end{table}
-
-			% Since $C(X)$ does not appear in the rightmost column of this table, it is an irreducible polynomial.
-
-			In the figure above we see that $c_L=1$. Using sage, we find that $C(X)$ is a primitive polynomial:
-
-			\begin{minted}[tabsize=0]{python}
-			sage: Z2P.<x> = GF(2)[]                 
-			sage: (x^5+x^3+x^2+x+1).is_primitive()  
-			True
-			\end{minted}
-
-			The period of this LFSR is then $2^L-1=31$.
-
-		\item
-			We construct the states using matrix multiplication. As an example we show $M\cdot s_1$:
-			$$M\cdot s_1 = \begin{pmatrix}0 & 1 & 0 & 0 & 0 \\0 & 0 & 1 & 0 & 0 \\0 & 0 & 0 & 1 & 0 \\0 & 0 & 0 & 0 & 1 \\1 & 0 & 1 & 1 & 1\end{pmatrix} \cdot \begin{pmatrix}0 \\ 0 \\ 0 \\ 0 \\ 1\end{pmatrix} = \begin{pmatrix}0 \\ 0 \\ 0 \\ 1 \\ 1\end{pmatrix} = s_3$$
-			We can then continue with $M\cdot s_3$. Using that method, we find the state sequence $s_1$, $s_3$, $s_6$, $s_{12}$, $s_{25}$, $s_{18}$, $s_4$, $s_9$, $s_{19}$, $s_7$, $s_{15}$, $s_{31}$, $s_{30}$, $s_{29}$, $s_{27}$, $s_{23}$, $s_{14}$, $s_{28}$, $s_{24}$, $s_{17}$, $s_2$, $s_5$, $s_{10}$, $s_{21}$, $s_{11}$, $s_{22}$, $s_{13}$, $s_{26}$, $s_{20}$, $s_8$, $s_{16}$, $s_1$, which indeed contains $31$ different states (all states except $s_0$).
-		\end{enumerate}
-
-	\item
-		We know with sage that these two polynomials are primitive:
-
-		\begin{minted}[tabsize=0]{python}
-		sage: (x^3+x+1).is_primitive()
-		True
-		sage: (x^5+x^2+1).is_primitive()
-		True
-		\end{minted}
-
-		Therefore, the two LFSRs have period $2^L-1$, that is, $7$ for $\text{LFSR}^f$ and $31$ for $\text{LFSR}^g$. Of course, there is also the obvious period $1$ for both LFSRs if we start with $s_0$. 
-
-		Combining this we find the periods illustrated in table \ref{tab:1b}.
-
-		\begin{table}
-		\setlength\extrarowheight{2pt}
-		\centering
-		\begin{tabular}{l | l | l | l | l}
-		Period $\text{LFSR}^f$ & Initial state (e.g.) & Period $\text{LFSR}^g$ & Initial state (e.g.) & Combined period \\\hline
-		$1$	&	\texttt{000} 	&	$1$		& \texttt{00000}	& $2^{1\cdot1}-1=1$ \\
-		$1$ &	\texttt{000}	&	$31$ 	& \texttt{00001}	& $2^{1\cdot31}-1=2^{31}-1$ \\
-		$7$	&	\texttt{001} 	&	$1$		& \texttt{00000}	& $2^{7\cdot1}-1=2^7-1$ \\
-		$7$ &	\texttt{001}	&	$31$ 	& \texttt{00001}	& $2^{7\cdot31}-1=2^{217}-1$ \\
-		\end{tabular}
-		\caption{}
-		\label{tab:1b}
-		\end{table}
-	\end{enumerate}
-
-\item
-	\begin{proof}
-	Given a certain ciphertext $c$ we define the set $M_c$ as the set with all plaintexts that could give $c$ using some key and this cipher:
-	$$M_c \stackrel{\text{def}}{=} \{m\in\pazocal{M} \mid \exists_{k\in\pazocal{K}}[E(k,m) = c]\}$$
-	For all $k\in\pazocal{K}, c\in\pazocal{C}$ we have $D(k,c) = c-k\pmod{256} \in \{0,\dots,255\} = \pazocal{M}$. Therefore, for any $c\in\pazocal{C}$, we have $|M_c| = |\pazocal{K}| = |\pazocal{M}|$, meaning that given a certain ciphertext, any plaintext in $\pazocal{M}$ could be the plaintext corresponding to that ciphertext. Hence, seeing the ciphertext does not give us information about the plaintext, or:
-	$$\forall_{m\in\pazocal{M},c\in\pazocal{C}}\left[\Prob(m = m' \mid c) = \Prob(m = m')\right].$$
-	Therefore, this cipher has perfect secrecy.
-	\end{proof}
-
-\item
-	\begin{enumerate}
-	\item
-		$L_2 = R_1 = L_0 \oplus F(k_1,R_0)$ and $R_2 = L_1 \oplus F(k_2,R_1) = R_0 \oplus F(k_2, L_0 \oplus F(k_1, R_0))$.
-	\item
-		We are only interested in the left parts of the encryptions, which we shall denote as $L_{2,0}$ and $L_{2,1}$ for the left parts of the could-be encryptions of $m_0$ and $m_1$, respectively. Following the equations found in the last exercise, we have $L_{2,0} = 1^{32} \oplus F(k_1,1^{32}) = \overline{F(k_1,1^{32})}$ and $L_{2,1} = 0^{32} \oplus F(k_1,1^{32}) = F(k_1,1^{32})$. Therefore, in case $F_2$ was used, we have $L_{2,0} = \overline{L_{2,1}}$. For a random permutation this happening has the very small chance of $\frac1{2^{64}}$.
-
-		If an adversary thus checks whether $L_{2,0} \stackrel?= \overline{L_{2,1}}$ and finds out it's true, he has a non-negligible advantage with which he can assume $F_2$ was used. In case this equation does \emph{not} hold, he has a non-negligible advantage with which he can assume a random permutation was used.
-	\end{enumerate}
-
-\item
-	\begin{enumerate}
-	\item
-		One key has an effective length of $56$ bits. With two keys we have an effective keylength of $2\cdot56=112$ bits. This gives $|\pazocal{K}| = 2^{112}$. The amount of encryptions we have to perform for exhaustive key search is then $2^{112-1}$.
-	\item
-		$D^{2DES}(k_1||k_2, c) = D^{DES}(k_1, D^{DES}(k_2, c))$.
-	\item
-		\begin{proof}
-		\begin{align*}
-		m &= D^{DES}(k_1, D^{DES}(k_2, c)) \\
-		E^{DES}(k_1, m) &= E^{DES}(k_1, D^{DES}(k_1, D^{DES}(k_2, c))) \\
-			&\qquad\text{(Encryption and decryption with $k_1$ cancel out)} \\
-		E^{DES}(k_1, m) &= D^{DES}(k_2, c) 
-		\end{align*}
-		\end{proof}
-	\item
-		$A = 2^{56}$ since the keylength of one DES key is $56$. A ciphertext block encrypted with DES is $64$ bits long. Without overhead we have then $B=64\cdot2^{56}$.
-
-		We have a block length of $64$ and a key length of $56$. If we compute the encryptions of some plaintext using all possible keys, and the decryptions of some ciphertext using all possible keys, we have two lists of $2^{56}$ 64-bit candidates for a middle point in 2DES. Following the birthday paradox, the probability two values from the two lists are the same is high enough to reasonably expect false alarms\footnote{See \url{http://en.wikipedia.org/wiki/Birthday_problem#Probability_table}}.
-	\item
-		See the python files for the answers to exercise i through iv. See \texttt{Readme.md} for explanation and usage information.
-
-		I found the keypair $k_1=\mathtt{0101010101164613}, k_2=\mathtt{0101010102a719c2}$ using:
-
-		\begin{verbatim}
-		$ ./break.py -p 0123456789ABCDEF -c e0ac28c346fb8de5 -l 24
-		Making dictionary (p:0123456789abcdef;l:24)... 417.513822s
-		Finding matches... 419.125502s
-		Key generation:      102.954099s
-		Decryption:          269.473773s
-		Matching dictionary: 15.134741s
-		k1: 0101010101164613; k2: 0101010102a719c2
-		\end{verbatim}
-
-		This was done on a Lenovo U410, i7-3517U @ 1.9GHz with 8GB RAM and 16GB /swap. It takes about seven minutes to create the dictionary, and again seven minutes to try all keys for the second key and find matches. On lilo, this takes a bit less than five minutes each.
-
-		With $l=24$ we're likely to find only one possible keypair since the chance on false alarms is much lower. For higher $l$, in particular $l=56$, the chance on false alarms is much higher, meaning that the first keypair is most likely \emph{not} the actual keypair. More plaintext-ciphertext pairs can then help to find the right keypair. We do that in this case only for verification:
-
-		\begin{verbatim}
-		$ ./break.py -p 1122334455667788 -c 49e4857e94f9655d -l 24
-		Making dictionary (p:1122334455667788;l:24)... 386.554364s
-		Finding matches... 424.907323s
-		Key generation:      106.151418s
-		Decryption:          271.449573s
-		Matching dictionary: 15.2167599999s
-		k1: 0101010101164613; k2: 0101010102a719c2
-		$ ./break.py -p 99aabbccddeeff00 -c b5a2eefb51b04401 -l 24
-		Making dictionary (p:99aabbccddeeff00;l:24)... 394.505993s
-		Finding matches... 431.637707s
-		Key generation:      109.764972s
-		Decryption:          274.681545s
-		Matching dictionary: 14.4759990001s
-		k1: 0101010101164613; k2: 0101010102a719c2
-		\end{verbatim}
-
-		An adversary uses a method like \texttt{nthKey} instead of trying all $2^{64}$ possible 64-bit strings since some of the bits are parity bits. If he would try all $2^{64}$ possible 64-bit strings, he would waste time and storage on trying keys that aren't valid anyway.
-	\end{enumerate}
-\end{enumerate}
-
-\end{document}