\documentstyle[spanish]{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 Oto\~no, 1998}  }
       \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{14}{5 de Mayo}{Manuel Reyes\footnotemark}
\footnotetext{La primera parte
completando el cap'itulo 2 de la clase 10 de 1996, por Ricardo Valenzuela}


% TRANSCRIPCION DE LA CATEDRA COMIENZA AQUI


\section{Implementaci'on RSA}

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  $b$ $\in$ \{ 1 ... $\varphi$(n)-1 \} tal que:
$ab \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.
En la parte 4 usamos el Algoritmo de Euclides.
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$.


Ejemplo: $x=3,$ $n=5,~~c=5(=101=c_3c_2c_1)$
\[
\begin{array}{cccc}
    i & c_i & z(=xz\mypmod n,~if~c_i=1)  & z^2\mypmod n \\
      &     & 1 &  1\\     
    3 &  1  & 1\cdot 3 \mypmod 5 = 3 & 3^2\mypmod 5=9\mypmod 5 =4\\
    2 &  0  & 4 &  4^2\mypmod 5 =16\mypmod 5=1\\
    1 &  1  & 1\cdot 3 \mypmod 5 = 3 &
\end{array}
\]
$3^5\mypmod 5=243\mypmod 5=3$.



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. 

\bigskip

Para implementar la parte 1, es necesario estudiar algoritmos
de generaci'on de primos, equivalentemente testear si un n'umero
es primo o descomponerlo. 

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. Seg'un Schneier DES es 100 veces m'as
r'apido que RSA a nivel de software
y 1000 veces m'as r'apido a nivel de hardware.
 
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 
elegido al azar suficientemente grande.

Un test de primalidad es una prueba probabilista 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=pq$, 
encontrar los dos factores $p$ y $q$. 

\bigskip

\subsection{Algoritmo de b'usqueda de n'umeros primos}

?`C'omo se encuentra un n'umero primo en un intervalo $\{N+1,...,2N\}$
con $N$ un natural ($N$ m'as o menos como $2^l$).

Supongamos que tenemos un algoritmo $A$ probabilista
de tipo Montecarlo tal que
\[
    A(n)= \{ \begin{array}{lc}
                1 & {\rm si}~ n~{\rm es~primo}\\
                0 & {\rm con~~probabilidad~~}\geq 1-\xi~~{\rm si~}n~ {\rm
     es~compuesto}
             \end{array} 
\]
Este algoritmo permite encontrar un n'umero primo en el conjunto $\{N+1,...
,2N\}$ mediante el siguiente algoritmo de tipo Montecarlo
\begin{itemize}
\item[$i)$] Elegir $n\in\{N+1,...,2N\}$, $n$ impar al azar (uniformemente).
\item[$ii)$] Se ejecuta $k$ veces en la entrada $n$ el algoritmo $A$.
\item[$iii)$] Si las $k$ ejecuciones entregan las salidas ``1'',
entonces ser'a primo con alta probabilidad.
En caso contrario, si alguna ejecuci'on responde ``0'',
entonces ser'a compuesto.
\end{itemize}

\subsubsection{Estimaci'on de la probabilidad de error de un algoritmo de tipo
Montecarlo}

Encontremos pues la probabilidad de que nuestro n'umero
sea realmente primo, dado que el algoritmo respondi'o $k$ veces ``1''.
Definamos las afirmaciones:

$E$: un entero $n\in\{N+1,...,2N\}$, $n$ impar es compuesto.\\
$F$: el algoritmo $A$ entrega como salida 1, $k$ veces.

Consideremos
\[
    P(E/F)=\frac{P(F/E)P(E)}{P(F/E)P(E)+P(F/E^c)P(E^c)}
\]
y  $P(F/E^c)=1$, $P(F/E)\geq\xi^k$ por independencia de las $k$ ejecuciones.
Por otro lado, si definimos $\pi(x)=|\{p/1<p\leq x,~~{\rm primo}\}|$,
tendremos
\[
       P(E^c)=\frac{\pi(2N)-\pi(N)}{N/2},
\]
por la elecci'on con probabilidad uniforme sobre los impares del conjunto
$\{N+1,...,2N\}$.

Para continuar con las estimaciones aprovechemos el siguiente teorema,
que es uno de los grandes logros de la maten'atica del siglo pasado.

\noindent {\bf Teorema (de los n'umeros primos):}
\[
          \lim_{n\rightarrow\infty} \frac{\pi(n)}{n/\ln(n)}=1
\]
Observaci'on: La aproximaci'on $n/\ln n$ de $\pi(n)$ es buena para valores
de $n$ bastante razonables. Por ejemplo
 $\pi(n)>n/\ln(n)$ para todo $n\geq 17$ y
$\pi(n)<n/(\ln(n)-4)$ para todo $n\geq 55$.

Volvamos a nuestras estimaciones. Tenemos 
\begin{eqnarray*}
       P(E^c)&\approx&2  (\frac{2}{\ln N}-\frac{1}{\ln n})\\
             &\approx&\frac{2}{\ln N}
\end{eqnarray*}
de donde $P(E)=1-\frac{2}{\ln N}$ y con ello
\[
       P(E/F)\approx\frac{ \epsilon^k(1-\frac{2}{\ln N}) } { \epsilon^k(1-
      \frac{2}{\ln N}) + \frac{2}{\ln N} } \leq \epsilon^k\frac{\ln N}{2}
\]
Eligiendo 
\[
     k=\frac{\ln (\frac{2}{\ln N}\delta)}{\ln \epsilon}
\]
se tiene que $P(E/F)\leq\delta$.

Asi que, si queremos que nuestro candidato a primo lo sea con probabilidad
de al menos $1-\delta$, debemos usar $k=\frac{\ln (\frac{2}{\ln N}\delta)}{\ln \epsilon}$ veces nuestro algoritmo.










\end{document}










