\documentclass[11pt]{article}
\usepackage{amsfonts,amsthm,amsmath,amssymb}
\usepackage{array}
\usepackage{epsfig}
\usepackage{fullpage}
\usepackage{color}
%%%%%%%%%%%%%%% MACROS specific to this PSET %%%%%%%%%%%%%%%%%%%%%%
\newcommand{\lat}{\mathcal{L}}
\newcommand{\basis}{\mathbf{B}}
\newcommand{\vol}{\mathsf{vol}}
\newcommand{\sh}{\lambda_1}
%\newcommand{\det}{\mathsf{det}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\N}{\mathbb{N}}
%%%%%%%%% Vectors and Matrices
\newcommand{\vecv}{\mathbf{v}}
\newcommand{\vecb}{\mathbf{b}}
\newcommand{\vecbt}{\widetilde{\vecb}}
\newcommand{\vecs}{\mathbf{s}}
\newcommand{\vect}{\mathbf{t}}
\newcommand{\vecy}{\mathbf{y}}
\newcommand{\matB}{\mathbf{B}}
\newcommand{\poly}{\mathsf{poly}}
\newcommand{\Span}{\mathsf{Span}}
\newcommand{\dist}{\mathsf{dist}}
\def\rot{\mathsf{Rot}}
\def\bydef{\stackrel{\Delta}{=}}
\def\matA{\mathbf{A}}
\def\vecy{\mathbf{y}}
\def\vece{\mathbf{e}}
\def\vecz{\mathbf{z}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\title{MAT 301 Problem Set 1\\{\large Posted: January 6, 2012}\\{\large Due: January 16, 2012}\\{\large Worth: 100 points}}
\author{}
\date{}
\begin{document}
\maketitle
%\input{pset-preamble.tex}
%\lecture{1}{Vinod Vaikuntanathan}{September 13, 2011}{October 3, 2011}
\def\sslwe{\mathsf{ssLWE}}
\def\lwe{\mathsf{LWE}}
% Macros for vectors
\def\veca{\mathbf{a}}
\def\vecs{\mathbf{s}}
\def\vecc{\mathbf{c}}
\vspace*{-0.7in}
\subsection*{Problem $1$: Number Theory Review (60 points)}
\begin{enumerate}
\item {\bf (15 points)} Compute the multiplicative inverse of $a \pmod{n}$ for the following values of $a$ and $n$:
\begin{itemize}
\item $a = 5$, $n = 17$.
\item $a = 21$, $n = 63$.
\item $a = 5$, $n = 24$.
\end{itemize}
\item {\bf (15 points)} Compute the values of the Euler Totient Function (also called the Euler Phi Function) $\phi(n)$ for the
following values of $n$: (a) $n=2012$, (b) $n=2011$ (c) $n = 262144$.
\item Find {\em all numbers} $n$ such that:
\begin{itemize}
\item {\bf (15 points)} $\phi(n) = 13$.
\item {\bf (15 points)} $\phi(n) = 2$.
\noindent
{\tt [Hint: In order to limit your search space, you can use the fact that $\phi(n) \geq \sqrt{n}$ for all $n$ except $n=2$ and $n=6$.]}
\end{itemize}
\end{enumerate}
\subsection*{Problem $2$: Breaking Ciphers (20 points)}
The following ciphertext is encrypted under either the Caesar Cipher, the Vigenere Cipher
(with a key composed of two random shifts) {\em or} the Scytale cipher. I am not going to tell you which.
Decrypt it.
\[ \Large{\texttt{LZAKAKSJWSDDQWSKQHJGTDWEKWL}} \]
Which scheme was used to encrypt the message?
%In this problem, we will explore the substitution cipher, and ways of breaking it. A substitution cipher
%is a {\em symmetric} encryption scheme (as are all the other schemes we saw in class), and works as follows:
%The key is a {\em random permutation} mapping the English alphabet to itself. Namely, the key is a function $\phi$
%such that:
%\[ \phi: \{A,B,\ldots,Z\} \mapsto \{A,B,\ldots,Z\}\]
%To encrypt an English sentence, you take each character and apply the mapping to it. Decrypting is simply the
%process of applying the {\em inverse mapping} $\phi^{-1}$ to each character in the ciphertext.
%For example,
%\begin{itemize}
%\item $\mathsf{KeyGen}$:
%\item
%\item
%\end{itemize}
\subsection*{Problem $3$: The One-Time Pad (20 points)}
When using the one-time pad encryption with key $K = 0^{\ell}$ (namely, a string of $\ell$ zeroes)
to encrypt a message of length $\ell$ bits, the ciphertext is equal to the message! In other words, the message will be
transmitted in in the clear! This sounds bad.
A proposal to ``strengthen'' the one-time pad is to choose the key at random among all strings of $\ell$ ones and
zeroes, except for the all-zeroes string. Formally, we write this as $K \in_R \{0,1\}^{\ell} \setminus \{0^{\ell}\}$.
Somewhat paradoxically, this modification turns out to {\bf weaken} the security of the scheme, the exact opposite of what was
intended! Argue why this is the case.
\end{document}