\documentstyle[12pt]{article}

\textwidth=6in
\oddsidemargin=0.25in
\evensidemargin=0.25in
\topmargin=-0.1in
\footskip=0.8in
\parindent=0.0cm
\parskip=0.3cm
\textheight=8.00in
\setcounter{tocdepth} {3}
\setcounter{secnumdepth} {2}
\newtheorem{theorem}{Teorema}
\newtheorem{exercise}{Ejercicio}
\newtheorem{corollary}{Corolario}
\newtheorem{lemma}{Lema}
\newtheorem{observation}{Observaci\'on}
\newtheorem{comentary}{Comentario}
\newtheorem{proposition}{Proposici\'on}
\newtheorem{definition}{Definici\'on}
\def\squarebox#1{\hbox to #1{\hfill\vbox to #1{\vfill}}}
\newcommand{\qedbox}{\vbox{\hrule\hbox{\vrule\squarebox{.667em}\vrule}\hrule}}
\newcommand{\qed}{\nopagebreak\mbox{}\hfill\qedbox\smallskip}
\newcommand{\startproof}{\noindent{\em Dem:}\hspace{1em}}
\newenvironment{dem}{\startproof}{\qed}
\newenvironment{proof}{{\bf Dem:}\hspace{1em}}{\qed\newline}


\newcommand{\catedra}[3]{
   \pagestyle{headings}
   \thispagestyle{plain}
   \newpage
   \noindent
   \begin{center}
   \makebox[0in]{\framebox{
      \vbox{
    \hbox to 6in { {\bf MA-53G Intr. a la Criptograf\'{\i}a
                        \hfill Semestre Primavera, 1996}  }
       \vspace{4mm}
       \hbox to 6in { {\Large \hfill C\'atedra No. #1 : #2 \hfill} }
       \vspace{2mm}
       \hbox to 6in { {\it Transcriptor: #3 \hfill} }
      }
   }}
   \end{center}
   \markboth{C\'atedra No. #1 : #2}{C\'atedra No. #1 : #2}
   \vspace*{4mm}
}

% LISTA DE MACROS PERSONALES COMIENZA AQUI

\renewcommand{\emph}[1]{{\em #1}}
\newcommand{\plain}{{\cal P}}
\newcommand{\cipher}{{\cal C}}
\newcommand{\key}{{\cal K}}
\newcommand{\encrip}{{\cal E}}
\newcommand{\decrip}{{\cal D}}

\newcommand{\modulo}{{\cal Z}}
\newcommand{\kernel}{\mbox{\rm Ker}}
\newcommand{\determ}[1]{\mbox{\rm det}(#1)}
\newcommand{\mcd}[2]{\mbox{\rm mcd}(#1,#2)}
\newcommand{\mcm}[2]{\mbox{\rm mcm}(#1,#2)}
\newcommand{\set}[2]{\{#1\,|\,#2\}}
\newcommand{\smidge}{{\kern .05em}}	
\newcommand{\Colon}{{\smidge\colon\;\:}}
\newcommand{\eqdef}{\stackrel{\rm def}{=}}

\newcommand{\chapref}[1]{\mbox{Capitulo~\ref{#1}}}
\newcommand{\secref}[1]{\mbox{Secci\'on~\ref{#1}}}
\newcommand{\ssecref}[1]{\mbox{Secci\'on~\ref{#1}}}
\newcommand{\apref}[1]{\mbox{Ap\'endice~\ref{#1}}}
\newcommand{\thref}[1]{\mbox{Teorema~\ref{#1}}}
\newcommand{\defref}[1]{\mbox{Definici\'on~\ref{#1}}}
\newcommand{\corref}[1]{\mbox{Corolario~\ref{#1}}}
\newcommand{\lemref}[1]{\mbox{Lema~\ref{#1}}}
\newcommand{\propref}[1]{\mbox{Proposici\'on~\ref{#1}}}
\newcommand{\figref}[1]{\mbox{Figura~\ref{#1}}}
\newcommand{\tablref}[1]{\mbox{Tabla~\ref{#1}}}
\newcommand{\eqref}[1]{\mbox{(\ref{#1})}}
\newcommand{\ineqref}[1]{\mbox{(\ref{#1})}}
\newcommand{\comref}[1]{\mbox{Comentario~\ref{#1}}}
\newcommand{\mypmod}[1]{\,(\mbox{\rm mod}\,#1)}

% FIN LISTA DE MACROS PERSONALES

\begin{document}

% LOS DATOS IDENTIFICATORIOS DE LA CATEDRA TRANSCRITA VAN AQUI
% (modificar los parametros en invocacion de la siguiente macro:
%	primer parametro: No. de catedra transcrita
%	segundo parametro: fecha de catedra transcrita
%	tercer parametro: Nombre del transcriptor
\catedra{9}{3 de Septiembre}{Marcos Kiwi\footnotemark}
\footnotetext{\ Basada en una
  transcripci\'on parcial por Francisco Vald\'es}

% TRANSCRIPCION DE LA CATEDRA COMIENZA AQUI


\section{Pendientes}
%
Uno de los puntos pendientes que nos quedaba verificar acerca de RSA 
  era que la funci\'on de decripci\'on correspond\'{\i}a a la funci\'on
  inversa de la funci\'on de encripci\'on.
Primero recordemos que en el criptosistema de \emph{RSA} se tiene que  
  $\plain=\cipher=\modulo_{n}$,  donde $n = p q$ ($p$ y $q$ primos). 
Adem\'as, en RSA el conjunto de claves es 
  $\key = \{ (p,q,e,d) \,|\,  n = p  q $, $e d \equiv 1\mypmod{\varphi(n)}\}$, 
  donde $\varphi(n)$ es la funci\'on de Euler.
Para $K=(p,q,e,d) \in\key$ se tiene que las reglas de encripci\'on y
  decripci\'on vienen dadas respectivamente por
\begin{eqnarray*}
e_{k}(x) & = & x^{e} \bmod n\,, \qquad \forall x\in\plain\,, \\
d_{k}(y) & = & y^{d} \bmod n\,, \qquad \forall y\in\cipher\,.\\
\end{eqnarray*}
Finalmente recordemos que la parte p\'ublica de la clave 
  era la tupla $(n,e)$.

Queremos verificar que cualquiera sea el texto plano $x$ y la
  clave $k=(p,q,e,d)\in \key$ se
  tiene que $d_{k}(e_{k}(x)) = x$. 
Para ello notar que existe un entero $t$ tal que $e d = t \varphi(n) + 1$.
Luego, si $x$ es primo relativo con $n$, entonces
\[
x^{ed} \;\equiv\; x^{t\varphi(n) + 1} 
       \;\equiv\; (x^{\varphi(n)})^{t}x
       \;\equiv\;  x \mypmod n\,. 
\]
Donde la \'ultima congruencia se deduce del Teorema de Euler.
Por otro lado, si $x$ no es primo relativo con $n$, suponemos sin perdida 
  de generalidad que $x$ no es primo relativo con $p$ y que es primo
  relativo con $q$ (si $x\in\plain = \modulo_{n}$ entonces $x$ debe ser
  primo relativo con $p$ o con $q$).
Luego, 
\[\begin{array}{ccccc}
  x^{ed} & \equiv & x & \equiv & 0 \mypmod{p}\,, \\
  x^{ed} & \equiv & (x^{q-1})^{t(p-1)}x & \equiv & x \mypmod{q}\,. \\
\end{array}
\]
Donde la segunda congruencia es consecuencia del peque\~no Teorema de 
  Fermat y puesto que si $n=pq$ entonces $\varphi(n)=(p-1)(q-1)$.
Luego, tanto $x$ como $x^{ed}$ son soluciones del mismo sistema de
  congruencias. 
Pero como $p$ y $q$ son primos relativos, el 
  Teorema Chino del Resto permite concluir que $x^{ed}$ y 
  $x$ son congruentes m\'odulo $n$, i.e. $x^{ed}\equiv x \mypmod{n}$.
En otras palabras, $d_{k}(e_{k}(x))=x$ como queriamos demostrar.

\section{M\'as Teor\'{\i}a de N\'umeros (Continuaci\'on)}
%
Ahora que hemos retomado nuestro estudio de Teor\'{\i}a de
  N\'umeros aprovechamos para probar un resultado que habiamos 
  mencionado antes y que concierne a la funci\'on $\varphi$ de Euler.
\begin{lemma}
La funci\'on $\varphi$ de Euler es multiplicativa, i.e. si $m$ y $n$ son
  primos relativos
\begin{eqnarray*}
\varphi(mn) & = &  \varphi(m) \varphi(n)\,.
\end{eqnarray*}
\end{lemma}
\begin{proof}
La idea de la demostraci\'on es identificar cada elemento de 
  $\modulo_{mn}^{*}$ con un \'unico elemento de 
  $\modulo_{m}^{*}\times\modulo_{n}^{*}$.
Sea $j \in \{1, \ldots , mn \}$ y sean
  $j_{1} =  j \bmod n$, $j_{2} = j \bmod m$.
Notar que $j_{1}$ es primo relativo con $n$ si y s\'olo si
  $j$ es primo relativo con $n$.
Analogamente, $j_{2}$ es primo relativo con $n$ si y s\'olo si
  $j$ es primo relativo con $n$.
Luego, por el Teorema Chino del Resto, 
  los $j\in \{1,\ldots,mn\}$ que son  primos relativos a $mn$ se
  pueden asociar $1$ a $1$ con los pares $(j_{1},j_{2})$ tales que 
  $j_{1}\in \{1,..,n\}$, $j_{2} \in \{1,..,m\}$,
  $j_{1}$ es primo relativo con $n$, y $j_{2}$ es 
  primo relativo con $m$.
Sigue que, $\varphi(mn)=\varphi(m) \varphi(n)$.
\end{proof}

\begin{lemma}
Para todo $n$ entero positivo, se tiene que 
  $\displaystyle \sum_{d|n}^{} \varphi(d) = n$.
\end{lemma}
\begin{proof}
Sea $f(n) = \sum_{d|n}^{} \varphi(d)$. 
Se quiere probar que $f(n)=n$.
Notar que la afirmaci\'on es evidente si $n$ es primo, pues
  en este caso $f(n) = \varphi(1) + \varphi(n) = 1 + (n-1)$.
M\'as aun, si $n=p^{k}$ donde $p$ es primo,
\[ f(p^{k}) \;=\; \sum_{i=0}^{k} \varphi(p^{i}) 
            \;=\; 1 + \sum_{i=1}^{k}(p^{i} - p^{i-1})
            \;=\; p^{k}\,.
\]
Luego, para concluir que $f(n)=n$ con $n$ arbitrario, 
  bastar\'a aplicar el Teorema Fundamental de la Aritm\'etica y 
  probar que $f$ es una funci\'on multiplicativa, i.e.
  $f(mn) = f(m)f(n)$ si $m$ y $n$ son primos relativos. 
Sean entonces $m$ y $n$ primos relativos y $d$ un divisor de $mn$, entonces
  existen  $d_{1}$ y $d_{2}$ primos relativos (univocamente determinados)
  tales que $d = d_{1}d_{2}$, $d_{1}|m$, $d_{2}|n$.
Luego
\[
f(mn) \;=\; \sum_{d|mn}^{} \varphi(d)
      \;=\; \sum_{d_{1}|m}^{} \sum_{d_{2}|n}^{} \varphi(d_{1}d_{2})
      \;=\; \sum_{d_{1}|m}^{} \varphi(d_{1}) \sum_{d_{2}|n}^{} \varphi(d_{2})
      \;=\; f(m) f(n)\,.
\]
\end{proof}			   

\section{Cuerpos finitos}
%
Un cuerpo es un conjunto, dotado de dos operaciones; adici\'on y
multiplicaci\'on. Ambas operaciones son asociativas y conmutativas,
hay un elemento neutro para la adici\'on, $0$, y un elemento neutro
para la multiplicaci\'on, $1$, todo elemento tiene inverso aditivo y
todo elemento distinto de $0$ tiene inverso multiplicativo, y la
multiplicaci\'on distribuye con respecto a la adici\'on.  Un cuerpo
$F$ se denomina cuerpo finito si $|F|$ es finito.  Si sumando la
identidad reiterativamente nunca obtenemos el neutro aditivo el cuerpo
se dice de caracter\'{\i}stica $0$ (e.g. el cuerpo de los n\'umeros
reales). 

Para un entero no-negativo $q$ 
  denotaremos por $F_{q}$ el cuerpo con $q$ elementos.
Sea $1$ el neutro multiplicativo en $F_{q}$, y sea 
  $p$ el menor entero positivo tal que
\begin{eqnarray*}
\underbrace{1+1+1+ \ldots +1}_{p\,\, veces} & = & 0\,. 
\end{eqnarray*}
Dicho entero $p$ existe pues necesariamente debe ocurrir que
  como $F_{q}$ tiene cardinalidad finita entonces 
  existen dos enteros $i> j$ tales que  
\begin{eqnarray*}
\underbrace{1+1+1+ \ldots +1}_{i\,\, veces} & = &
\underbrace{1+1+1+ \ldots +1}_{j\,\, veces}\,.
\end{eqnarray*}
Luego, $p$ es a lo m\'as $i-j$.
Por otro lado, 
  es importante notar que $p$ es necesariamente primo, pues si $p=kl$
  para $k$ y $l$ enteros entonces
\[
0 \;=\; \underbrace{1+\ldots+1}_{p} \;=\; 
        \underbrace{(1+\ldots+1)}_{k} \underbrace{(1+\ldots+1)}_{l}\,. 
\]
Como $F_{q}$ es un cuerpo, no tiene divisores del cero, luego 
  o $k$ o $l$ deben ser iguales a la unidad, i.e. $p$ es primo.
A $p$ se le denomina la caracter\'{\i}stica de $F_{q}$.
Si $F_{q}$ es de caracter\'{\i}stica $p$ entonces 
  contiene un cuerpo $F_{p}$ isomorfo a $\modulo_{p}$, 
  denominado cuerpo primo.
En efecto
\begin{eqnarray*}
F_{p} & = & \{0,1,1+1, .. , \underbrace{1+ .. +1}_{(p-1)\,\, veces}\}\,,
\end{eqnarray*}
dotado de las operaciones adici\'on y multiplicaci\'on heredadas de 
  $F_{q}$ es un cuerpo isomorfo a $\modulo_{p}$.
		     
Ahora probaremos la importante afirmaci\'on que dice que 
  que si $F_{q}$ tiene ca\-rac\-te\-r\'{\i}s\-ti\-ca $p$ entonces $q$
  debe ser una potencia de $p$.
Observemos antes que $F_{q}$ es un espacio vectorial sobre $F_{p}$, i.e.
  las operaciones $+\Colon F_{q} \times F_{q} \to F_{q}$, 
  $\cdot\Colon F_{p}\times F_{q} \to F_{q}$, satisfacen
\begin{enumerate}
\item
$(F_{q},+)$ es un grupo abeliano.

\item Cualquiera sean los  escalares $\alpha,\beta \in F_{p}$, y los elementos 
   $x,y\in F_{q}$ se tiene que 
\begin{enumerate}
\item $\alpha (x+y) = \alpha x + \alpha y$.

\item $(\alpha\beta)x=\alpha(\beta x)$.

\item $(\alpha+\beta)x=\alpha x+\beta x$.

\item $1\cdot x = x$.
\end{enumerate}
\end{enumerate}
Luego,  como $F_{q}$ es un conjunto finito sigue que $F_{q}$ (visto como
  espacio vectorial) tiene dimensi\'on finita $k$.
Tomando una base de tama\~no $k$ de $F_{q}$ es f\'acil 
  establecer una biyecci\'on entre $F_{q}$ y 
  $\{(\lambda_{1},\ldots,\lambda_{k}) \,|\,\lambda_{i} \in F_{p}\}$.
De lo anterior se concluye que $q = |F_{q}| = p^{k}$.
Por lo tanto se puede concluir que s\'olo existen cuerpos finitos cuya
  cardinalidad es una potencia de un n\'umero primo $p$.\footnote{\ Aunque 
  no lo probaremos cabe destacar que existe un \'unico cuerpo (salvo 
  isomorfismos) de cardinalidad $q$.} 
\end{document}

