\documentclass[12pt]{amsart}

\input{../../TeX/macros}

\usepackage{fullpage}

\begin{document}

\title[Math 75 Homework \#5]{Math 75: Mathematical Cryptography \\ Homework \#5}
\date{Due Wednesday, 4 May 2016}

\maketitle

\section*{Problems}

\begin{problab}{1}
Let $k \geq 2$, let $A=(\Z/2\Z)^k$, and define the maps 
\begin{align*} 
s,g: A \times A &\to A \times A \\
s(x,y) &= (y,x) \\
g(x,y) &= 
\begin{cases}
(x,y), & y \neq (0,0,\dots,0); \\
(x + \underbrace{(1,1,...,1)}_{k},(0,0,\dots,0)), & y=(0,0,\dots,0).
\end{cases}
\end{align*}

\begin{enumalph}
\item Prove that $s^2$ and $g^2$ are the identity on $A \times A$.
\item Prove that $(sg)^4=sgsgsgsg$ moves only $3$ elements of $A \times A$, i.e. 
\[ \#\{(x,y) \in A \times A:(sg)^4(x,y) \neq (x,y)\}=3. \]
\item Prove that $(sg)^{12}$ is the identity.
\end{enumalph}
\end{problab}

\begin{problab}{2}
Encrypt the message $001100001010$ using two rounds of SDES and key $111000101$.  \emph{[Hint: After one round, the output is $001010010011$.]}
\end{problab}

\begin{problab}{3}
In the Rijndael field $F=\F_2[X]/(X^8+X^4+X^3+X+1)$, where bytes are associated to polynomials modulo $X^8+X^4+X^3+X+1$, compute the product $01010010 \cdot 10010010 \in F$.
\end{problab}

\begin{problab}{4}
\begin{enumalph}
\item Find all monic irreducible polynomials of degree $4$ in $\F_2[X]$.
\item Verify that the Rijndael polynomial 
\[ f(X)=X^8+X^4+X^3+X+1 \] is irreducible in $\F_2[X]$.  
\emph{[Hint: If it has a factor, it must have degree at most $4$.]}
\end{enumalph}
\end{problab}

\begin{problab}{5}
Put $f(X)=X^8+X^4+X^3+X+1 \in \F_2[X]$, and let 
\[ a=00001100=X^3+X^2 \in F=\F_2[X]/(f). \]  
\begin{enumalph}
\item Compute $a^5$.  
\item Find the inverse $b^{-1} \in F$ of $b=X^2=00000100$.
\item Multiply $b^{-1}a$ and verify that $b^{-1}a = X+1$ in $F$.
\end{enumalph}
\end{problab}

\end{document}