%This should be a TeX file.  Please change the extention of this file from crytography.txt to crytography.tex
%\documentclass[landscape,troispoints,pdf,colorBG,slideColor]{prosper}
%\documentclass[landscape,wcshiu,pdf,colorBG,slideColor]{prosper}
\documentclass[landscape,winter,pdf,colorBG,slideColor]{prosper}
%\hypersetup{pdfpagemode=FullScreen}
\usepackage{epsfig}%use insert figure
\usepackage{array}
\usepackage{amssymb}%Use Miscell. symbols
\usepackage{picinpar}%for window
\usepackage{enumerate}%for enumerate environment
\usepackage{hhline}%for make double line in table
\usepackage{color}
\usepackage{tabularx}
\usepackage{amsmath} % instead of amstex
\usepackage{mathrsfs} % Use \mathscr in Math Mode
\newcommand{\ex}[1]{\vskip5mm \noindent {\bf Example {#1} }}
\renewcommand{\baselinestretch}{1.5}
\renewcommand{\arraystretch}{0.9}%default is 1
%\usepackage{times}
%\usepackage{fancyheadings}
\def\Z{\mathbb{Z}}
\def\N{\mathbb{N}}
\def\P{\mathbb{P}}
\def\R{\mathbb{R}}
\def\Q{\mathbb{Q}}
\def\pf{\vskip3mm \noindent {\bf Proof: }}
\def\rsq{\hspace*{\fill $\Box$}}
\def\di{\displaystyle}
\def\uf{\usefont{T1}{ptm}{m}{n}\fontsize{14.4pt}{13pt}}
%\FontText{%
 % \mellow\usefont{T1}{ptm}{m}{n}\fontsize{14.4pt}{14pt}\selectfont}{%
 % \black\usefont{T1}{ptm}{m}{n}\fontsize{14.4pt}{14pt}\selectfont}

\title{Cryptography} %\subtitle{which rocks}
\author{W.C. Shiu}
\email{wcshiu@hkbu.edu.hk} \institution{Department of mathematics\\Hong Kong
Baptist University}

\begin{document}
\maketitle


\begin{slide}{Crytosystem}

Encryption function $E$: transfers plaintext to ciphertext\\
Decryption function $D$: transfers ciphertext to plaintext

$D$ is the inverse function of $E$ and vice versa.
\end{slide}

\overlays{4}{
\begin{slide}{Public Key Cryptosystem}

Each user provide a public key, i.e., publish the encryption function $E$.

\medskip
Keep the decryption function $D$ in security.
\bigskip
\FromSlide{2}
Suppose Mary wants to send a plaintext $m$ to Peter.

\begin{enumerate}[1.]
\FromSlide{3}
\item She uses Peter's encryption function $E_P$ to change the message $m$ to
$c=E_P(m)$.
\FromSlide{4}
\item When Peter receives the ciphertext message $c$. He uses his decryption
function transfers the message to $D_P(c)=D_P(E_P(m))=m$.
\end{enumerate}
\end{slide}}

\overlays{3}{
\begin{slide}{A Public Key Cryptosystem\\ -- RSA
Cryptosystem}

\onlySlide*{1}{RSA : Rivest, Shamir, Adleman}
\bigskip

\FromSlide{2} Suppose a user's public key is $(n,b)$.

\bigskip

\FromSlide{3}The security of RSA is based on the hope that the encryption function
 $E(m)=m^b\mod n$ is one-way, so it will be computational infeasible for any
 opponent to decrypt a ciphertext.
 \end{slide}}

\overlays{3}{
\begin{slide}{Number Theory\\ -- Some Basic Knowledge}
{\uf\it  Suppose $a$ and $m$ are relative prime, i.e., $(a,m)=1$. Then there
are integers $s$ and $t$ such that $as+mt=1$.} Here $s$ and $t$ can be found by
using Euclidean algorithm.
\bigskip

\FromSlide{2}Suppose $n$ is an integer greater than 1. Let $\Z_n=\{0,1,\cdots,
n-1\}$ be the ring of the complete residue system modulo $n$.
\bigskip
\FromSlide{3}{\uf Theorem: \it Let $m\ge 2$. Suppose $(a,m)=1$. Then there is a
unique $b\in \Z_m$ such that $ab\equiv 1\pmod{m}$. $b$ is called the {\red inverse} of $a$
 and is denoted by $a^{-1}$.}
\end{slide}
}
\overlays{2}{
\begin{slide}{Number Theory\\-- Some Basic Knowledge}

Let $\phi(m)$ denote the number of positive integers less than or equal to $m$
that are relatively prime to $m$. This function is called the {\red Euler
$\phi$-function}.

\bigskip
\FromSlide{2}{\uf Euler's Theorem: {\it If $(a,m)=1$, then $a^{\phi(m)}\equiv
1\pmod{m}$.}}
\end{slide}
}

\overlays{3}{
\begin{slide}{RSA Cryptosystem}



 \FromSlide{2} Let $n=pq$, where $p$ and $q$ are primes (very large).
Choose a unit $a\in \Z_{\phi(n)}$ (i.e., $(a, \phi(n))=1$). Then there is a $b$
such that $ab\equiv 1\pmod{\phi(n)}$. Thus, we have $ab=t\phi(n)+1$ for some
$t\ge 1$.

\FromSlide{3}Suppose $x\in \Z_n^*$, the set of units of $\Z_n$. Then
\begin{align*}
(x^b)^a & \equiv x^{t\phi(n)+1}\pmod{n}\\
& \equiv (x^{\phi(n)})^t x\pmod{n}\\
& \equiv x\pmod{n}.
\end{align*}

We leave an exercise for you to show that $(x^b)^a\equiv x\pmod{n}$ if
$x\in\Z_n\setminus \Z_n^*$.
\end{slide}
}
\overlays{2}{
\begin{slide}{RSA Cryptosystem}
In order to setup the system, we follow the following steps
\begin{enumerate}
\item Generate two large primes $p$ and $q$.
\item Compute $n=pq$ and $\phi(n)=(p-1)(q-1)$.
\item Choose a random number $b$ ($0<b<\phi(n)$) such that $(b,\phi(n))=1$.
\item Compute $a=b^{-1}\pmod{\phi(n)}$ using the Euclidean algorithm.
\item Publish $(n,b)$ as public key.
\end{enumerate}
\FromSlide{2}In practice, $n$ is very large. Using the best algorithms
known and
fastest computers, it would take centuries to factor a 200 digit modulus $n$.
\end{slide}}

\overlays{6}{
\begin{slide}{Example 1}
\untilSlide*{3}{Suppose Peter chooses $p=101$ and $q=113$. Then $n=11413$ and
$\phi(n)=100\times 112=11200=2^65^2 7$. Choose $b$ which is not divisible by
$2,5$ or 7.}

\medskip
\onlySlide*{2}{In practice, Peter will not factor $\phi(n)$. He will verify that
$(\phi(n),b)=1$ using the Euclidean algorithm.}
\medskip

\onlySlide*{3}{Suppose Peter chooses $b=3533$.
Then by Euclidean algorithm he will get $a=b^{-1}=6597 \mod{11200}$.}

\FromSlide{4}Peter's secret key is $a=6597$. Peter publishes
$n=11413$ and $b=3533$ in a directory as a public key.
\medskip

\FromSlide{5}Suppose Mary wants to send the plaintext 9726 to Peter.
She computes
$$9726^{3533} \equiv 5761\pmod{11413}$$
and sends the ciphertext 5761 over the channel.
\medskip

\FromSlide{6}When Peter receives the
ciphertext 5761, he uses his secret key to compute
$$5761^{6597} \equiv 9726 \pmod{11413}.$$
\end{slide}}

\overlays{4}{
\begin{slide}{Possible plaintext message units $\ne $ possible ciphertext message units}
Suppose we are working in an $N$-letter alphabet. Let $k<l$ be
suitably chosen positive integers, such that for example $N^k$ and $N^l$ have
approximately 200 decimal digits.

\medskip
\FromSlide{2}We take as our plaintext message units all
blocks of $k$ letters, which we regard as $k$-digit base-$N$ integers.

\medskip
\FromSlide{3}Similarly take ciphertext message units to be blocks of $l$ letters in our
$N$-letter alphabet.

\medskip
\FromSlide{4}Then each user must choose his/her large primes $p$ and
$q$ so that $n=pq$ satisfies $N^k < n <N^l$.
\end{slide}
}

\overlays{5}{
\begin{slide}{Example 2}
Let $N=26$, $k=3$ and $l=4$.
\medskip
\FromSlide{2}
\untilSlide*{4}{Suppose we want to send the message ``{\red YES}" to a user $A$ with public key $(n_A,
e_A)=(46927, 39423)$.
\medskip
\FromSlide{3}Then we find the numerical equivalent of ``{\red YES}":
$$24\times 26^2+ 4\times 26+18=16346$$
and compute $16346^{39423}\equiv 21166\pmod{46927}$.}

\FromSlide{4}$$21166=1\times 26^3 + 5\times 26^2 + 8\times 26 +2$$
this is equivalent of ``{\red BFIC}".
\medskip

\FromSlide{5}The user $A$ knows the secret key $(n_A, d_A)=(46927,
26767)$.
\medskip

So $A$ computes $21166^{26767}\equiv 16346\pmod{46927}$ and get the
message ``{\red YES}".
\end{slide}
}

\overlays{2}{
\begin{slide}{Numerical Signature}

{\it 在進行秘密通訊中，如何才能鑒別收方收到的訊息確實是發方傳出的呢？\\
且發方如何確保內容沒有被收方竄改呢？}

\bigskip

\FromSlide{2}{\it 銀行B在網上收到用戶A說要轉帳十萬圓，那麼銀行必須要確定該訊息
是否由A發出。\\
同時，如果A事後否認曾發過此訊息，銀行必須能夠提出證明這訊息確實由A發出。}
\end{slide}
}

\overlays{5}{
\begin{slide}{Numerical Signature}
Suppose user $A$ wants to send a signatured message $m$ to
user $B$. He uses the following steps:
\begin{enumerate}
\FromSlide{2}\item $A$ uses his own decryption function to change the plaintext to
$s=D_A(m)$.
\FromSlide{3}\item $A$ uses the public key of user $B$ to transfer $s$ to be
$E_B(s)=E_B(D_A(m))$. And then sends to $B$.
\FromSlide{4}\item When $B$ receives the ciphertext message $E_B(s)$, by using her decryption
function transfers the message to $D_B(E_B(s))=s$.
\FromSlide{5}\item $B$ uses the public key of $A$ to transfer $s$ to $E_A(s)=E_A(D_A(m))=m$.
\end{enumerate}
\end{slide}}

\begin{slide}{}
\begin{center}
{\blue \Huge\bf
The end\\[1cm]
{\it 謝謝}}
\end{center}
\end{slide}
\end{document}