\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}[4]{
   \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}}}

% 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{10}{4 de Septiembre}{Ricardo Valenzuela}

% TRANSCRIPCION DE LA CATEDRA COMIENZA AQUI

\section{Teor\'{\i}a de Cuerpos Finitos}
%
Sea $F$ un cuerpo finito, denotamos por $F^{*}$ al conjunto 
$F^{*} = F\verb'\'\{0\}.$
\begin{definition}
Sea $ \alpha \in F^{*} $, el menor entero positivo k tal que 
$ \alpha^{k} = 1 $, se denomina el orden de $\alpha$, y se 
denota $ord(\alpha)$.
\end{definition}
Notar que existe una potencia finita de $\alpha$ igual a 1, ya que
las potencias de $\alpha$ en cuerpo finito $F^{*}_{q}$ no pueden ser
todas distintas, y tal como tenemos $\alpha^{i} = \alpha^{j}$ para $j \verb'<' i$,
tambien tenemos $\alpha^{j-i} = 1 $.\\
\\
Hay $q-1$ elementos no nulos en $ F_{q} $. Por definici\'on de cuerpo
estos elementos forman un grupo abeliano con respecto a la multiplicaci\'on,
esto significa que: 
 la multiplicaci\'on es cerrada,
 la multiplicaci\'on es asociativa,
 la multiplicaci\'on es conmutativa,
 existe neutro multiplicativo,
 todo elemento tiene inverso.
\begin{theorem}
[Lagrange] 
Todo $ \alpha \in F^{*}_{q} $ tiene un orden que divide a $q-1$
\end{theorem}
\begin{proof}
( Primera demostraci\'on ) Sea $ \alpha^{d} = 1 $, 
donde d es el orden de $\alpha$.\\
Sea $S=\{1,\alpha,\alpha^{2},...,\alpha^{d-1}\}$  el conjunto 
de todas las potencias distintas de $\alpha$, y para alg\'un $b \in F^{*}_{q}$ 
sea $bS$ el "coconjunto" de los elementos de la forma $b\alpha^{j}$ 
( por ejemplo, $1S = S$ ). Es f\'acil ver que dos coconjuntos
cualesquiera son id\'enticos o bien distintos (nominalmente : 
si alg\'un $b_{1}\alpha^{i}$ est\'a en $b_{1}S$, $b_{2}\alpha^{j}$ est\'a en $b_{2}S$,
y $b_{1}\alpha^{i}=b_{2}\alpha^{j}$ entonces $b_{1}=b_{2}\alpha^{j-i}$
de donde es f\'acil deducir que $b_{1}S$ es subconjunto de $b_{2}S$ 
y $b_{2}S$ es subconjunto de $b_{1}S$ lo que implica que $b_{1}S=b_{2}S$). 
Y cada coconjunto contiene exactamente $d$ elementos. La uni\'on 
de todos los coconjuntos abarca $F^{*}_{q}$ ( de $q-1$ elementos ), 
esto significa que 
$F^{*}_{q}$ es una uni\'on disjunta de conjuntos de $d$ elementos. 
Por lo tanto d divide a $q-1$ .\\
\end{proof}
\begin{proof}
( Segunda demostraci\'on ) Notar que 
$f : F^{*}_{q} \longrightarrow F^{*}_{q}$ , donde
$f(x) = \alpha x$
es una funci\'on biyectiva, ya que al multiplicar cada elemento 
de $ F^{*}_{q}$ por $\alpha$ obtenemos una permutaci\'on de $F^{*}_{q}, $
porque cada elemento distinto a otro, seguira siendo distinto 
luego de la multiplicaci\'on. Luego:
\begin{eqnarray*}
\prod_{\beta \in F^{*}_{q}}\beta & = & \prod_{\beta \in F^{*}_{q}}f(\beta)\\
\prod_{\beta \in F^{*}_{q}}\alpha\beta & = &
\alpha^{q-1}\prod_{\beta \in F^{*}_{q}}\beta. \\
\end{eqnarray*}
Cancelando, se concluye que
$\alpha^{q-1}=1$.\\
Supongamos que el orden de $ \alpha$ es $d$. Si $d$ no divide a $q-1$, entonces
$r = (q-1)$mod$d$ es no nulo y menor que $d$. Adem\'as $q-1 = td + r$ , 
para alg\'un
t que pertenece a los naturales. Luego,
\begin{eqnarray*}
1=\alpha^{q-1} & = & (\alpha^{d})^{t}\alpha^{r}.
\end{eqnarray*}
Pero el orden de $\alpha$ es $d$, entonces 
$\alpha^{r}=1$.
 Lo que contradice la minimalidad de $d$.
\end{proof}
\begin{definition}
Un cuerpo $G$ se dice c\'{\i}clico si existe un $g\in G$ tal que:
$G = \{ g^{i} :$ i entero $\}$, 
y a $g$ se le llama generador.\\
\end{definition}
Luego, un generador de $ F^{*}_{q} $ es un elemento de orden $q-1$.\\
El siguiente lema nos dice, en particular, que los elementos no nulos de
$ F_{q} $ forman un grupo c\'{\i}clico.
\begin{lemma}
Todo cuerpo finito tiene un generador. Si $g$ es un generador de $ F^{*}_{q}$,
entonces $g^{j}$ es un generador de $F^{*}_{q}$ si y solo si $j$ y $q-1$ son primos
relativos. En particular hay $\varphi(q-1)$ generadores de $F^{*}_{q}$. 
\end{lemma}
\begin{proof}
Sea $d$ el orden de $ \alpha \in F^{*}_{q}$ , es decir, $\alpha^{d} = 1$ y
$\alpha,\alpha^{2},...,\alpha^{d} $ son todas distintas y son soluciones
de la ecuaci\'on:
$ x^{d} = 1 $.
 Por el teorema fundamental del \'algebra, la \'ultima ecuaci\'on
tiene a lo m\'as $d$ soluciones, y todo elemento $ \beta \in F^{*}_{q} $
de orden $d$ satisface esta ecuaci\'on.
Luego, todo elemento $ \beta \in F^{*}_{q}$ de orden $d$ es tal que
$\beta \in \{ \alpha, \alpha^{2}, ... , \alpha^{d} \}$.
Veamos ahora que $\alpha^{j}$ es de orden $d$ si y solo si  mcd$(j,d) = 1$ (*).
En efecto, si $mcd(j,d) = d^{\prime} > 1 $, sigue que 
$ 1 = (\alpha^{d})^{\frac{j}{d^{\prime}}} = (\alpha^{j})^{\frac{d}{d^{\prime}}} $
es decir, $ \alpha$ tiene orden $\frac{d}{d^{\prime}} $.
Contradicci\'on.\\
\\
Para el converso, notemos que
$ mcd(j,d) = 1 $,
implica que existe $u$, $v$ enteros tales que 
$uj + vd = 1$.
Luego, si $ \alpha^{i} $ tuviese orden $d^{\prime}$ menor que d, sigue que 
$ (\alpha^{j})^{d^{\prime}} = 1$ y
$ (\alpha^{d})^{d^{\prime}} = 1$, luego $\alpha^{jd^{\prime}u} = 1 $ 
y $\alpha^{dd^{\prime}v} = 1 $.\\ 
Por lo tanto $\alpha^{jd^{\prime}u+dd^{\prime}v} = 1 $,   
es decir, $ \alpha^{d^{\prime}} = 1 $, lo que contradice la minimalidad de d.\\
Luego, si existe un elemento de orden $d$, entonces hay $ \varphi(d) $ elementos
de orden $d$.\\
Si $d$ no divide a $q-1$ no hay elementos de orden $d$ ( por Lagrange ).
 Si $d$ divide a $q-1$ hay 0 o $ \varphi(d) $ elementos de orden $d$.\\
Finalmente:\\
\begin{eqnarray*}
q-1 & = & \sum_{d|q-1} |\{\alpha:ord(\alpha)=d\}| \leq \sum_{d|q-1} \varphi(d)
 = q-1 
\end{eqnarray*}
es decir
$|\{\alpha:ord(\alpha) = d\}| = \varphi(d)$, 
para cualquier $d$ que divide a $q-1$.\\
\\
En particular, hay $\varphi(q-1)$ elementos de orden $q-1$, es decir 
generadores.\\
Si $g$ es generador de $ F^{*}_{q}$, $g^{j}$ es un generador para todo
$j \in \{ 1,...,q-1\}$, tal que mcd$(j,q-1) = 1. $
(Por afirmaci\'on (*) probada anteriormente.)
\end{proof}
\begin{corollary}
Para todo primo p, existe un $g\in{\bf Z}^{*}_{p}$ cuyas potencias generan 
${\bf Z}^{*}_{p}$.
\end{corollary}


\section{Implementaci\'on de RSA}
%
Existen muchas situaciones donde se quiere saber si un n\'umero 
$n$ grande es primo. Por ejemplo, en la implementaci\'on de 
RSA y en varios criptosistemas, necesitamos encontrar un primo 
"aleatorio" grande.\\
Un test de primalidad es una prueba para saber si un n\'umero 
es o no primo. Si un n\'umero pasa la prueba, \'este puede ser primo. 
Si un n\'umero pasa una gran cantidad de estos test, entonces es 
muy probable que sea primo. Y por lo tanto si un n\'umero no pasa 
la prueba, \'este es definitivamente no primo. Emp\'{\i}ricamente, 
se sabe que es m\'as costoso ( en tiempo ) factorizar un n\'umero 
grande no primo ( fallo en el test de primalidad ) 
que encontrar uno primo del mismo orden de magnitud.\\
La seguridad de RSA se basa en el hecho 
de que es mucho m\'as f\'acil encontrar dos primos extremadamente 
grandes $p$ y $q$ que, conociendo $n$, encontrar los dos factores $p$ y $q$ no 
conocidos tal que $n = pq$. \\ 
\\
Tenemos los siguientes problemas de implementaci\'on :
\begin{enumerate}
\item Elegir $p$ y $q$ primos grandes.
\item Calcular $ n = pq$ y $\varphi(n) = (p-1)(q-1) . $
\item Elegir un exponente de encriptaci\'on $a$ tal que $0 < a < \varphi(n)$
y donde $a$ sea primo relativo con $ \varphi(n) $.
\item Encontrar  $x$ $\in$ \{ 1 ... $\varphi$(n)-1 \} tal que:
$xa \equiv 1 ($mod $\varphi$($n$)) 
\item Publicar $(n,a)$ (No publicar en cualquier Newsgroup.)
\item Calcular $x^{c}$ mod $n$, donde $c$ es a o $b$.
\end{enumerate}
Las partes 2. y 3. sabemos como implementar eficientemente.\\
Para implementar 6. utilizamos el m\'etodo de los cuadrados repetidos, 
es decir, el siguiente algoritmo: 
\begin{tabbing}
---------------------------- \= --- \= \kill
\>$ z = 1$\\
\>for $i = l$ downto 0\\
\>\>$z = z^{2}$\\
\>\>if $c_{i} = 1$ then $z = zx$ mod $n$ \\
\end{tabbing}

Donde $c = c_{1}...c_{l}$ es la representaci\'on binaria de $c$.\\
\\
Todos los n\'umeros a multiplicar tienen $O(log n)$ bits, adem\'as
en cada iteraci\'on tenemos dos multiplicaciones, por lo tanto,
con l iteraciones tenemos que el algoritmo
toma $O(2l(log n)^{2})$ operaciones binarias. \\
Como ya sabemos RSA requiere elegir primos grandes $p$ y $q$ y no 
demasiado similares. 
Hoy en d\'{\i}a sabemos factorizar
n\'umeros de hasta 130 d\'{\i}gitos.
Se recomienda usar n\'umeros $p$ y $q$ de alrededor de 100 d\'{\i}gitos
para que $n$ quede de alrededor de 200 d\'{\i}gitos.
Las implementaciones en hardware de RSA que existen utilizan un 
m\'odulo n de 512 bits ($\approx$ 154 d\'{\i}gitos).
Estas implementaciones logran encriptar 600 Kbits/seg.
Por otro lado DES implementado a nivel de hardware logra 
encriptar 1 Gbit/seg.

\end{document}






