Put everything on git

4 files changed, 206 insertions, 0 deletions

diff --git a/Assignment 1/CamilStaps-assignment1-freqs.hs b/Assignment 1/CamilStaps-assignment1-freqs.hs
new file mode 100644
index 0000000..6c6cd47
--- /dev/null
+++ b/Assignment 1/CamilStaps-assignment1-freqs.hs
@@ -0,0 +1,39 @@
+import System.Environment
+import Data.String.Utils
+import qualified Data.List as List
+
+main = do
+	args <- getArgs
+	let input = replace " " "" (head args)
+	print $ List.reverse $ List.sort $ countfreqs input 1 []
+	print $ List.reverse $ List.sort $ countfreqs input 2 []
+	print $ List.reverse $ List.sort $ countfreqs input 3 []
+
+-- countfreqs s n []: calculate occurrence statistics of n-grams in s
+countfreqs :: String -> Int -> [Freq] -> [Freq]
+countfreqs "" _ fl = fl
+countfreqs s n fl
+	| length s < n = fl
+	| otherwise = countfreqs (tail s) n (freqsincr fl (take n s) [])
+
+-- freqsincr fl s []: add s to the frequencies in fl
+freqsincr :: [Freq] -> String -> [Freq] -> [Freq]
+freqsincr [] s fl = fl ++ [Freq { item = s, freq = 1}]
+freqsincr (freq:fla) s2 flb
+	| get_item freq == s2 = fla ++ flb ++ [Freq { item = s2, freq = get_freq freq + 1}]
+	| otherwise = freqsincr fla s2 (flb ++ [Freq { item = get_item freq, freq = get_freq freq}])
+
+-- Data type for keeping track of frequencies (Int) of substrings (String)
+data Freq = Freq { item :: String, freq :: Int } deriving (Eq)
+
+get_item :: Freq -> String
+get_item = item
+
+get_freq :: Freq -> Int
+get_freq = freq
+
+instance Ord Freq where
+	f1 `compare` f2 = get_freq f1 `compare` get_freq f2
+
+instance Show Freq where
+	show f = get_item f ++ " (" ++ show (get_freq f) ++ "x)"
\ No newline at end of file
diff --git a/Assignment 1/CamilStaps-assignment1-shift.hs b/Assignment 1/CamilStaps-assignment1-shift.hs
new file mode 100644
index 0000000..35a34e7
--- /dev/null
+++ b/Assignment 1/CamilStaps-assignment1-shift.hs
@@ -0,0 +1,14 @@
+import System.Environment
+import Data.String.Utils
+
+main = do
+	args <- getArgs
+	let input = replace " " "" (head args)
+	print $ map (`shiftN` (read $ args!!1)) input
+
+-- shiftN c i: shift c i times forward (i.e. shiftN 'A' 1 == 'B')
+-- Only for uppercase letters
+shiftN :: Char -> Int -> Char
+shiftN c 0 = c
+shiftN 'Z' i = shiftN 'A' (i-1)
+shiftN c i = shiftN (toEnum ((fromEnum c) + 1)) (i-1)
\ No newline at end of file
diff --git a/Assignment 1/CamilStaps-assignment1.hs b/Assignment 1/CamilStaps-assignment1.hs
new file mode 100644
index 0000000..6bc6a4c
--- /dev/null
+++ b/Assignment 1/CamilStaps-assignment1.hs
@@ -0,0 +1,43 @@
+import System.Environment
+import Data.String.Utils
+import qualified Data.List as List
+
+main = do
+	args <- getArgs
+	let input = replace " " "" (head args)
+	putStrLn $ "Running frequency statistics on: " ++ input
+	print $ List.reverse $ List.sort $ countfreqs input 1 []
+	print $ List.reverse $ List.sort $ countfreqs input 2 []
+	print $ List.reverse $ List.sort $ countfreqs input 3 []
+	print $ map (`shiftN` 18) input
+
+countfreqs :: String -> Int -> [Freq] -> [Freq]
+countfreqs "" _ fl = fl
+countfreqs s n fl
+	| length s < n = fl
+	| otherwise = countfreqs (tail s) n (freqsincr fl (take n s) [])
+
+freqsincr :: [Freq] -> String -> [Freq] -> [Freq]
+freqsincr [] s fl = fl ++ [Freq { item = s, freq = 1}]
+freqsincr (freq:fla) s2 flb
+	| get_item freq == s2 = fla ++ flb ++ [Freq { item = s2, freq = get_freq freq + 1}]
+	| otherwise = freqsincr fla s2 (flb ++ [Freq { item = get_item freq, freq = get_freq freq}])
+
+data Freq = Freq { item :: String, freq :: Int } deriving (Eq)
+
+get_item :: Freq -> String
+get_item = item
+
+get_freq :: Freq -> Int
+get_freq = freq
+
+instance Ord Freq where
+	f1 `compare` f2 = get_freq f1 `compare` get_freq f2
+
+instance Show Freq where
+	show f = get_item f ++ " (" ++ show (get_freq f) ++ "x)"
+
+shiftN :: Char -> Int -> Char
+shiftN c 0 = c
+shiftN 'Z' i = shiftN 'A' (i-1)
+shiftN c i = shiftN (toEnum ((fromEnum c) + 1)) (i-1)
\ No newline at end of file
diff --git a/Assignment 1/CamilStaps-assignment1.tex b/Assignment 1/CamilStaps-assignment1.tex
new file mode 100644
index 0000000..0e0b77d
--- /dev/null
+++ b/Assignment 1/CamilStaps-assignment1.tex
@@ -0,0 +1,110 @@
+\documentclass[a4paper]{article}
+
+\usepackage{a4wide,amsmath,amssymb,url,graphicx,comment,enumerate,color,array,inconsolata,minted,listings}
+
+\title{Homework $1$}
+\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^{^*}}
+
+\begin{document}
+\maketitle
+
+\section*{Solution}
+
+\begin{enumerate}
+\item  \begin{enumerate}
+	\item 	This would work: $p_1$ and $p_2$ share $k_1$ and $k_1'$; $p_1$ and $p_3$ share $k_2$ and $k_2'$; and $p_2$ and $p_3$ share also $k_2$ and $k_2'$. Furthermore, none of the executives has two parts of the key ($k_i$ and $k_i'$ for some $i$).
+	\item 	$p_2$ and $p_3$ can't compute the key together: together they have only $k_1'$ and $k_2'$, they would need either $k_1$ or $k_2$ in addition to that to be able to compute $k$. Therefore, this is not a suitable solution.
+	\item 	$p_1$ can compute $k$ by himself with $k = k_2 \oplus k_2'$, so this is not suitable.
+	\end{enumerate}
+
+\item 	We first compute the one time pad key used, by XOR-ing the ciphertext with the plaintext ``attack by sea''. After that, we XOR the key we found with the plaintext ``attack by air''. Since the first eight bytes of both the plaintext and the key stay the same, we only have to consider the last three bytes.
+
+	\begin{table}[h]
+	\centering
+	{\renewcommand{\arraystretch}{1.2}
+	\begin{tabular}{r | >{\ttfamily}c >{\ttfamily}c >{\ttfamily}c}
+	Plaintext (8-bit ASCII) 			& s 			& e				& a				\\
+	Plaintext (hex)						& 73			& 65			& 61			\\\cline{2-4}
+	Ciphertext (hex)					& 2C			& F4		 	& 71			\\\cline{2-4}
+	Key (XOR of plaintext with ciphertext) & \textbf{5F}& \textbf{91}	& \textbf{10}	\\\cline{2-4}
+	New plaintext (8-bit ASCII)			& a				& i				& r				\\
+	New plaintext (hex)					& 61			& 69			& 72			\\\cline{2-4}
+	New ciphertext (XOR of new plaintext with key) & \textbf{3E} & \textbf{F8} & \textbf{62}
+	\end{tabular}
+	}
+	\end{table}
+
+	The encryption of ``attack by air'' using the same key is thus \texttt{4F 40 20 0D 18 E9 13 33 3E F8 62}.
+
+\item 	\begin{enumerate}
+	\item 	No, node 25 is a child of node 5, so encrypting with this key will give player 25 access.
+	\item 	Yes, this will give players 27 till 30 access. However, 6's parent 2 would give access to player 25 as well.
+	\item 	It would be better to use node 1 which gives access to more players whilst not exposing the movie to player 25.
+	\item 	Yes, per the reason stated before.
+	\item 	Yes, we can't use 26's parent 12 as this would expose the movie to player 25.
+	\item 	Yes, we can't use 11's parent 5 per the reason stated at (a), but using this key won't give player 25 access.
+	\item 	With node 6 we already cover all players with this key, so this is unnecessary.
+	\item 	This key has already been covered with the key in node 1.
+	\end{enumerate}
+
+	Summarising, we need keys $k_1, k_{11}, k_{26}$ and $k_6$.
+
+\item 	We notice that the first eleven letters could correspond to ``Barack Obama'' in plaintext. This gives us:
+
+		\begin{verbatim}BARAC KOBAM A____ ___R_ _A_R_ CA_AM _R_CA __R__ _____\end{verbatim}
+
+		Then we notice we could fit the word ``America(n)'' in, giving:
+
+		\begin{verbatim}BARAC KOBAM AI___ E_IR_ _A_RI CA_AM ERICA __RE_ I_E__\end{verbatim}
+
+		We then realise the plaintext could be ``Barack Obama is the first African American president''. 
+
+\item 	\begin{enumerate}
+	\item 	I wrote a Haskell program which can be found in appendix \ref{App:5a}. The used libraries are used only for basic operations (sorting and reversing lists, replacing substrings in a string) that aren't really part of the main functionality and could be easily written without the libraries. However, this is easier.
+
+		Lines 25 through 37 provide the \texttt{Freq} type which holds a string and an integer, and is used to store the number of occurrences of a substring in a string.
+
+		Lines 13 through 17 provide a method to count $n$-grams occurrences in a string, it returns a list of \texttt{Freq}s. 
+
+		Lines 19 through 23 provide a helper method for \texttt{countfreqs} which takes a list of String occurrences and their frequencies, and a String, and increments the frequency of that String in the list by one.
+
+		The \texttt{main} method reads the first command argument, removes spaces and counts and sorts letter, bigram and trigram occurrences in the string.
+
+	\item 	From the output of the program we find that the trigram \texttt{BPM} occurs the most (7 times) and that the letters \texttt{M}, \texttt{B} and \texttt{P} occur the most as well (respectively 34, 27 and 19 times). From this we guess that \texttt{BPM} could correspond to \texttt{THE} in the plaintext. This would mean a shift of 8.
+
+		We then use the program from appendix \ref{App:5b}, which lets you shift letters in a string. We let it shift $26-8=18$ times, giving:
+
+		\sloppy\texttt{AGOODGLASSINTHEBISHOPSHOSTELINTHEDEVILSSEATTWENTYONEDEGREESANDTHIRTEENMINUTE
+		SNORTHEASTANDBYNORTHMAINBRANCHSEVENTHLIMBEASTSIDESHOOTFROMTHELEFTEYEOFTHEDEA
+		THSHEADABEELINEFROMTHETREETHROUGHTHESHOTFIFTYFEETOUT}
+
+		Or:
+
+		\begin{quote}\itshape
+		A good glass in the bishop's hostel in the devil's seat\\
+		twenty-one degrees and thirteen minutes northeast and by north\\
+		main branch seventh limb east side shoot from the left eye of the death's-head\\
+		a bee line from the tree through the shot fifty feet out.\\
+		\par\raggedleft--- \textup{Edgar Allan Poe}, The Gold-Bug
+		\end{quote}
+	\end{enumerate}
+\end{enumerate}
+
+\appendix
+
+\newpage
+\section{Sourcecode for assignment 5a} \label{App:5a}
+\inputminted[breaklines=true,linenos=true,tabsize=4]{haskell}{CamilStaps-assignment1-freqs.hs}
+
+\newpage
+\section{Sourcecode for assignment 5b} \label{App:5b}
+\inputminted[breaklines=true,linenos=true,tabsize=4]{haskell}{CamilStaps-assignment1-shift.hs}
+
+\end{document}