1 files changed, 142 insertions, 0 deletions
diff --git a/Assignment 2/CamilStaps-assignment2.tex b/Assignment 2/CamilStaps-assignment2.tex
new file mode 100755
index 0000000..b604b40
--- /dev/null
+++ b/Assignment 2/CamilStaps-assignment2.tex
@@ -0,0 +1,142 @@
+\documentclass[a4paper]{article}
+
+\usepackage{a4wide,amsmath,amssymb,url,graphicx,comment,enumerate,color,array,inconsolata,minted}
+
+\title{Homework $2$}
+\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}
+
+\begin{document}
+\maketitle
+
+\section*{Solution}
+
+\begin{enumerate}
+\item  
+	\begin{enumerate}
+	\item $\mathbb{Z}_{41}^* = \{1,\dots,40\}$, so $40$.
+	\item No, because $12 \nmid 40$, whilst the Lagrange theorem states that the order of a group is divisible by the orders of all its subgroups.
+	\item We find:
+
+		\begin{itemize}
+		\item $10^1 = 10$
+		\item $10^2 = 100 \equiv 18 \pmod{41}$
+		\item $10^3 \equiv 10 \cdot 18 \equiv 16 \pmod{41}$
+		\item $10^4 \equiv 10 \cdot 16 \equiv 37 \pmod{41}$
+		\item $10^5 \equiv 10 \cdot 37 \equiv 1 \pmod{41}$
+		\item $10^6 \equiv 10 \cdot 1 \equiv 10^1 \pmod{41}$
+		\end{itemize}
+
+		We found five different elements ($10,18,16,37,1$) that can be generated by 10. Since $10^6 \equiv 10^1 \pmod{41}$ we don't have to search further. Hence, $\ord(10)=5$.
+
+	\item We saw already that $10^3 \equiv 16 \pmod{41}$. Then we also know $\log_{10}{16} \equiv 3\pmod{41}$.
+	\item We saw $37 \equiv 10^4 \pmod{41}$. We then also know $37^7 \equiv (10^4)^7 \equiv 10^{28} \equiv (10^5)^5\cdot10^3 \equiv 1^5\cdot10^3 \equiv 10^3 \equiv 16\pmod{41}$ (using our knowledge from 1c).
+	\end{enumerate}
+
+\item
+	\begin{enumerate}
+	\item Yes: we can take $c=3$ and $n'=4$, since
+		\begin{align*}
+		2n + 5 &\le 2n + n \qquad\text{for $n>4$}\\
+			&= 3n.
+		\end{align*}
+
+	\item Yes: we can take $c=2$, because for large enough $n$
+		\begin{align*}
+		-2n^2 + 5n + 10 &\le 0 \qquad\text{(since this describes a parabola opening down)}\\
+		5n + 10 &\le 2n^2\\
+		5 + \frac{10}{n} &\le 2n\\
+		2n + 5 + \frac{10}{n} &\le 4n\\
+			&= 2\cdot2n.
+		\end{align*}
+
+	\item We know\footnote{I'm assuming `$\log$' is used for the base 10 logarithm rather than the natural logarithm. A proof for the same question with the natural logarithm would be very similar, so this should not be a problem.} $\log(n)>1$ for $n>10$ and thus also $n\log(n)>n$ for $n>10$. Hence, $\nexists_{n'\in\mathbb{N}}\forall_{n\in\mathbb{N},n>n'}[n\log(n)\le n]$. We can conclude that $n\log(n)\neq O(n)$.
+
+	\item We know that for $n \ge 1$:
+		\begin{align*}
+		n &\le 10^n \\
+		10^{\log n} &\le 10^n \\
+		\log n &\le n \\
+		n\log n &\le n^2
+		\end{align*}
+
+		So we have $n\log n \le c\cdot n^2$ with $c=1$ for every $n>n'=0$. Therefore, $n\log n = O(n^2)$.
+
+	\item 
+		If we flip the $\ge$ sign in the formula for the $\Omega$-notation, we see $f = O(g) \Leftrightarrow g = \Omega(f)$. We can then rewrite this question to the question whether $n^5=O(2n+5+\frac{10}{n})$.
+
+		We know that for large enough $n$ it holds that $n^4 \ge c\cdot 2$, since for positive increasing $n$ this function also increases. We then also know that $n^5 \ge c\cdot 2n$. We saw already in (b) that $2n+5+\frac{10}{n}\le c\cdot 2n$. Combining the two, we see that $n^5 \ge 2n+5+\frac{10}{n}$ for large enough $n$. Hence, $n^5 \neq O(2n+5+\frac{10}{n})$ and also $2n+5+\frac{10}{n} \neq \Omega(n^5)$.
+	\end{enumerate}
+
+\item 
+	\begin{enumerate}
+	\item \begin{minted}[tabsize=0]{python}
+		sage: Z2P.<x> = GF(2)[]
+		sage: (x^6+x^4+x^3+x+1).is_irreducible()
+		True
+		\end{minted}
+
+	\item Still in $\mathbb{F}_2$:
+
+		\begin{minted}[tabsize=0]{python}
+		sage: (x^7).mod(x^6+x^4+x^3+x+1)
+		x^5 + x^4 + x^2 + x
+		sage: (x^8).mod(x^6+x^4+x^3+x+1)
+		x^5 + x^4 + x^2 + x + 1
+		\end{minted}
+
+		Or, by hand:
+		\begin{align*}
+		x^7 &\equiv x^7 - x(x^6+x^4+x^3+x+1)\\
+			&\equiv x^7 -x^7 -x^5 -x^4 -x^2 -x\\
+			&\equiv x^5 + x^4 + x^2 + x \pmod{x^6 + x^4 + x^3 + x + 1}\\
+		x^8 &\equiv x\cdot x^7\\
+			&\equiv x(x^5+x^4+x^2+x)\\
+			&\equiv x^6 + x^5 + x^3 + x^2 - (x^6+x^4+x^3+x+1)\\
+			&\equiv x^5 + x^4 + x^2 +x + 1 \pmod{x^6 + x^4 + x^3 + x + 1}\\
+		\end{align*}
+
+	\item We have $\{a_1x^5 + a_2x^4 + \dots + a_6x^0 \mid a_i \in \{0,1\}\}$. We have two possibilities for each $a_i\in\{a_1,\dots,a_6\}$, that gives $2^6=64$ elements. The multiplicative group contains the same elements except $0$, and thus has $64-1=63$ elements.
+	\item 
+		\begin{enumerate}
+		\item In the table we read that $x^{56} \equiv x+1 \pmod{x^6+x^4+x^3+x+1}$. We thus have the set $\{x^{56k}\mid k\in\mathbb{N^+}\}=\{x^{56},x^{112},x^{168},\dots\}$ and need to find the smallest $k>1$ such that $x^{56k} \equiv x^{56}$ (because then we've cycled through the whole group).
+
+			We know that $x^{56k}\equiv x^{56k\bmod64}$, so we can reduce the problem to finding the smallest $k>1$ such that $56k\equiv 56\pmod{64}$, or $56(k-1)\equiv 0\pmod{64}$ We then find $k-1=\frac{\lcm{56,64}}{56}=8$, and $k=8+1=9$.
+
+			We can conclude $(x+1)^{9} \equiv x+1$ and that there is no $1<k<9$ for which $(x+1)^k \equiv x+1$. We then see that the multiplicative group generated by $x+1$ is $\{(x+1)^k \mid k \in \{1,2,\dots,8\}\}$, and thus that its order is $9-1=8$.
+
+		\item Similarly, we see in the table that $x^{22} \equiv x^4 + x^3 + x^2$. We now need to find the smallest $k>1$ such that $22k \equiv22 \pmod{64}$. Following the same method as before, we find $k=\frac{\lcm{22,64}}{22}+1=\frac{704}{22}+1=33$, giving as order $k-1=33-1=32$.
+		\end{enumerate}
+	\end{enumerate}
+
+\item 
+	\begin{enumerate}
+	\item $D'_k(c) \stackrel{\text{def}}{=} D_k(c|_{0,|c|-2})$, where $s|_{a,b} \stackrel{\text{def}}{=}$ the substring of $s$ starting at (and including) index $a$ and ending at (and including) index $b$. This essentially discards the bit added to the end of $E_k$ by $E'_k$ and then uses $D_k$ to decrypt the rest.
+	\item She could have one of $m_0=\dots0, m_1=\dots1$ encrypted. Then, by looking at the least significant bit of the ciphertext - the least significant bit of the encrypted plaintext $m_b$ - she can recognise which plaintext was encrypted, and guess $b' = \lsb(E'_k(m_b))$, which, by the definition of $E'_k$, also equals $b$.
+	%\item For $b=0$ we are sure of $W_0$ (where we use the notation from the lecture $W_b \stackrel{\text{def}}{=} E(k,m_b)\;\text{was given}$). Hence, ${\rm Adv}_{SS}[A,E] := |\Prob[W_0]-\Prob[W_1]| = |1-0| = 1$. Similarly, for $b=1$, we have ${\rm Adv}_{SS}[A,E] := |\Prob[W_0]-\Prob[W_1]| = |0-1| = 1$. Therefore, the advantage is $1$ independent of $b$.
+	\item For $b=0$, $m_0$ is encrypted yielding a ciphertext $c$ with $\lsb(c)=0$. The adversary guesses $b'=\lsb(c)=0$, so $\Prob[W_0]=0$. In case $b=1$, $m_1$ is encrypted yielding a ciphertext $c$ with $\lsb(c)=1$. The adversary guesses $b'=\lsb(c)=1$, so $\Prob[W_1]=1$. The advantage is then $\Adv_{SS}[A,E]=|\Prob[W_0]-\Prob[W_1]|=|0-1|=1$. Since this is not negligible, we have proven $\Pi$ to be insecure and at the same time shown the correctness of our answer at (b).
+	\end{enumerate}
+
+\item 
+	\begin{enumerate}
+	\item As always we assume that the adversary has knowledge of the encryption scheme used and the security factor $n$. He thus knows $E'(k,m)=E(k,m)||k$, as well as $D'(k,c)$ and $D(k,c)$, and furthermore can compute the length of the key, since it depends on $n$. Hence, he can split up $E'(k,m)$ in $E(k,m)$ and $k$. He can then compute $D(k,E(k,m))=m$ to find the plaintext. Therefore, this scheme is not secure.
+	\item Without loss of information an adversary can discard either half of a ciphertext, getting $E(k,m)$. We know that $E$ is semantically secure and we've seen that $E'$ does not introduce new information for the adversary as opposed to $E$, and thus can conclude that also $E'$ is semantically secure.
+	\item Without loss of information an adversary can compute $E(k,m) = reverse(E'(k,m))$. We know that $E$ is semantically secure and we've seen that $E'$ does not introduce new information for the adversary as opposed to $E$, and thus can conclude that also $E'$ is semantically secure.
+	\item The adversary is assumed to know $E'=E(0^n,m)$ and $D$. Since $D(k,E(k,m))=m$ we know $m=D(0^n,E(0^n,m))=D(0^n,E'(k,m))$. This last formula uses only information the adversary knows (the ciphertext $E'(k,m)$ and the decryption function $D$), so the adversary can decrypt a text encrypted with $E'$, which means this scheme is insecure.
+	\item The leading zero contains no information about the plaintext and can thus be discarded by the adversary without loss of information. He then has $E(k,m)$, which therefore contains precisely the same information about the key and the plaintext as $E'(k,m)$. Since $E$ is semantically secure, we can now conclude that $E'$ is as well.
+	\end{enumerate}
+\end{enumerate}
+
+\end{document}