1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
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}
|
