\documentclass[a4paper]{article}

\usepackage[english]{babel}
\usepackage[utf8x]{inputenc}
\usepackage{amsmath}
\usepackage{enumerate}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{xspace}

        \newtheorem{theorem}{Theorem}
        \newtheorem{lemma}{Lemma}
        \newtheorem{proposition}{Proposition}
        \newtheorem{corollary}{Corollary}
        \newtheorem{definition}{Definition}
        \newtheorem{assumption}{Assumption}
        \newtheorem{claim}{Claim}
        \newtheorem{problem}{Problem}
        \newtheorem{construction}{Construction}
\DeclareMathOperator*{\expe}{\mathbb{E}}

\newcommand{\class}[1]{{\ensuremath{\mathsf{#1}}}}
\newcommand{\enc}{\ensuremath{\class{Enc}}\xspace}
\newcommand{\dec}{\ensuremath{\class{Dec}}\xspace}

\usepackage{graphicx}
\usepackage[colorinlistoftodos]{todonotes}

\title{CSE 5852: Problem Set 2}
\date{Due: September 28, 2016}
%\author{You}

\begin{document}
\maketitle

\section{Defining integrity}
\begin{enumerate}[a)]
\item \textbf{15 pts} In class we considered message unforgeability against chosen message attack.  Formalize an alternative definition that provides security against messages drawn from a message distribution.

\item \textbf{15 pts} Our definition in class is secure for a single message.  Present a modified experiment that provides security for $k$-messages.  Think carefully about the order of events.
\end{enumerate}


\section{Number Theory}
In this section we will prove some items that were asserted in class.  Be careful about what manipulations you make and why you're allowed to make them.  

\begin{enumerate}[a)] 
\item \textbf{7 pts} Prove that if $a_1 = a_2 \mod n$ then $n | (a_1 - a_2)$.
\item \textbf{12 pts} Prove that for any $a_1, a_2$, \[a_1 \mod b + a_2 \mod b \equiv a_1 + a_2 \mod b\] and \[(a_1\mod b)(a_2 \mod b) \equiv a_1a_2 \mod b.\]
\item \textbf{5 pts} Compute $248^{15} \mod 252$ without using numbers with more than three decimal digits.  Show your work.
\item \textbf{5 pts} Compute $7^{128} \mod 9$.  Show your work.
\item \textbf{12 pts} Let $n$ be an integer, show that for any $a$ such that $\gcd(a, n)=1$ there exists an  inverse $\mod n$.  That is, $\exists a^{-1} \in\mathbb{Z}_n$ such that $a\cdot a^{-1} = 1$.
\item \textbf{12 pts} Let $p$ be a prime.  For an integer $a\in \{1,..., p-1\}$ show the values $a\mod p, 2\cdot a\mod p, 3\cdot a,..., (p-1)a\mod p$ are unique.  What value is $\mathbb{Z}_p$ is not included in this set of values?
\item \textbf{7 pts} \emph{Fermat's Little Theorem} Show that for any $a\in \{1,...,p-1\}$, $a^{p-1} = 1 \mod p$.
\end{enumerate}

\section{Message Authentication Codes/Message Integrity}
We will consider extensions to the integrity protections we built using a universal hash function.  In this question we consider extensions to this construction.  

\begin{enumerate}[a)]
%\item \textbf{10pts} 
%Suppose that we want to save on key space.  We will also shorten the final tag space so that $|T| = \sqrt{|M|}$.  Define a new MAC whose key length is approximately $|\mathcal{M}| + |T|$.  If necessary you may use multiple different primes in your construction or work over different groups. Prove that your new MAC is a universal hash function.  Be precise about what the group of each operation in your computation.
%
%\textbf{Hint:} For any length $\ell$ the set of binary strings with the $\oplus$ operation is a group with the identity $0$ and each string as its own inverse.  You may want to use this group in your construction.  (Alternatively, the question may be answered by working over two different prime groups.)

\item \textbf{10pts}
Show that the MAC we presented in class is insecure if used to protect two (distinct) messages.  Show how to completely recover the key.
\end{enumerate}
%\bibliographystyle{alpha}
%\bibliography{crypto}

\end{document}