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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
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}
|
