CONGRUENCIAS Y CRIPTOSISTEMAS

\documentclass{article}[14pt]
%\documentclass{article}
\usepackage[utf8]{inputenc}
\usepackage{geometry} [a4paper,14pt,lmargin=1.5cm,rmargin=1.5cm,Botton=1.5cm,top=1.5cm]
\usepackage{ifthen}
\usepackage[spanish,activeacute]{babel}
\usepackage{fancyhdr}
\pagestyle{fancy}
\usepackage{lastpage}
\usepackage{graphicx}
\usepackage{wrapfig}
\usepackage{color}
\usepackage{amsmath}
\usepackage[T1]{fontenc}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{mathrsfs}
\usepackage{cancel}
\usepackage[all]{xy}
\usepackage{pstricks}
\usepackage{pst-all}
\usepackage{pst-solides3d}
\usepackage{fancybox}
\usepackage{tikz}
\usepackage{tikz-3dplot}
\usepackage{gnuplottex}
\tikzset{flippedeventlabel/.append style={align=center}} \usetikzlibrary{matrix.skeleton} \usetikzlibrary[shapes,arrows,positioning,fit,backgrounds,intersections,shadows,calc,shadings]
\usetikzlibrary{positioning}
\usetikzlibrary{decorations.text} \usetikzlibrary{decorations.pathmorphing} \pgfdeclarelayer{background layer}
\pgfdeclarelayer{foreground layer}
\pgfsetlayers{background layer,main,foreground layer}
\usepackage{color,colortbl}
\usepackage{lscape}
\usepackage{pgfplots}
\pgfplotsset{compat=newest}
\usetikzlibrary{datavisualization} \usetikzlibrary[shapes,arrows.meta,positioning,fit,backgrounds,intersections,shadows,calc,datavisualization.formats.functions] \usetikzlibrary{patterns} \usepackage[colorlinks=true,linkcolor=magenta,citecolor=blue,filecolor=magenta,urlcolor=blue]{hyperref}
\urlstyle{same}
\renewcommand{\thefootnote}{\fnsymbol{footnote}}
\newcounter{i}
%Paquete de estilo de referencias
\begin{document}

\pagecolor{white!95!green!25!blue!10}
%\pagecolor{green!30!blue!25}
\tikz
{\shadedraw (0,0) node[right,left color=black, right color=red,text width=7.5cm,rounded corners=10pt]
{
\begin{center}
\textcolor{white}{\textbf{Seguridad en Redes y Cifrado De Texto}}\\
\textcolor{yellow}{Nimrod Rodríguez}\\
\href{CODIGO-LATEX}{\underline{\textcolor{white}{enlace:} \textcolor{green}{Código \LaTeX} }}
\end{center}
}}

\begin{center}
\shadowbox{Introducción}
\end{center}
\qquad Los problemas de seguridad en redes se pueden dividir, de forma general, en cuatro áreas interrelacionadas: \textcolor{blue}{confidencialidad}, \textcolor{magenta}{autentificación}, \textcolor{red}{no repudio} y \textcolor{orange!50!red}{control de integridad}; para un enfoque más amplio \cite{tanen2003}. La seguridad es un tema amplio que trata una multitud de pecados. En su forma más simple, se ocupa de garantizar que los curiosos no puedan leer, o peor aún, modificar en secreto mensajes dirigidos a otros destinatarios. Tiene que ver con la gente que intenta acceder a servicios remotos no autorizados. También se encarga de mecanismos para verificar que el mensaje
supuestamente enviado por una autoridad fiscal que indica algo como: “\textcolor{red}{Usted tiene derecho a entablar una demanda contra \textsf{\textbf{WowSpiesbook}}}”, en realidad venga de ella y no de la mafia. La seguridad también se hace cargo
del problema de la captura y reproducción de mensajes legítimos, y de las personas que intentan negar que enviaron ciertos mensajes.\\

A continuación, dos casos del cifrado de texto, uno muy elemental ya no utilizado; y el criptosistema RSA, aún vigente. Ambos basados en la modulación aritmética, el primero a un nivel muy elemental utilizando una sola clave, mientras que el segundo más avanzado, haciendo uso de dos claves, una pública y una confidencial, definidas mediante la teoría de congruencias; además impone la dificultad del cálculo en la factorización de enteros considerablemente grandes, como barrera contra los ataques. Sin embargo, como ya es sabido, dicha dificultad se vería superada por la inminente fabricación e implementación de los ordenadores cuánticos, via el algoritmo de Shor (1994), del cual también se da una pequeña ilustración.

\section{Cifrado Por Desplazamiento} Suponga que tanto emisor como destinatario poseen la llave k=11 en su aplicación de mensajería, para un cifrado por desplazamiento, y que el texto llano a enviar es:


\begin{align}
\textcolor{blue}
{yovotareporfulanito}
\end{align}
Primero, la aplicación del emisor convierte el texto llano a una secuencia de enteros, usando la correspondencia arábiga \\
\pgfmathsetmacro{\r}{0}
\foreach \l in {a,b,c,d,e,f,g,h,i,j,k,l,m,n,$\~n$ ,o,p,q,r,s,t,u,v,w,x,y,z}
{
\tiny{$\l$ $\mapsto$ $\arabic{i}$}
\addtocounter{i}{1}
}\\
(Note que son 27 caracteres numerados de 0 a 26), obteniendo lo siguiente:
\begin{align}
\foreach \u in{25,15,22,15,20,0,18,4,16,15,18,5,21,11,0,13,8,20,15}
{
\textcolor{blue}{\u \ }
}
\end{align}
sumando la llave $k=11$ y obteniendo el resultado módulo 27\footnote{Aqui el módulo m=27 es en correspondencia al número de letras del alfabeto a,b,...,ñ,...z. Cuando la suma es mayor que 26, después de este valor seguiría 0,1,2,..., según el excedente.}, se obtiene:

\begin{align}
\foreach \u in{25,15,22,15,20,0,18,4,16,15,18,5,21,11,0,13,8,20,15}
{
\pgfmathsetmacro {\x}{\u +11}
\pgfmathfloatparsenumber{\x}
\pgfmathfloattoint{\pgfmathresult}
\pgfmathsetmacro{\m}{\pgfmathresult}
\pgfmathsetmacro{\y}{\pgfmathresult -26}
\pgfmathfloatparsenumber{\y}
\pgfmathfloattoint{\pgfmathresult}
\pgfmathsetmacro{\n}{\pgfmathresult}
\textcolor{red}{\ifthenelse{\m >26}{\n \ }{\m \ }}
}
\end{align}

Así, esta codificación arábiga corresponde al cifrado del texto llano, que el emisor enviará al destinatario, el cual sería:
\begin{align}
\textcolor{red}{kzhzfldobzdpgvlxsfz}
\end{align}
Ahora, el destinatario, teniendo la llave k=11, y el texto cifrado (4) en su aplicación, esta aplica la codificación arábiga correspondiente, obteniendo (3); luego resta la llave k=11, escribiendo los resultados módulo 27 para obtener (2), que es la codificación arábiga del mensaje original, de la cual se obtiene el texto llano (1), originalmente enviado. \\

Este cifrado es de tipo simétrico, debido a que los dos extremos utilizan una misma llave, tanto para \textit{cifrar} como para \textit{descifrar}; es muy inseguro y ya no se usa, a no ser como para ilustrar en forma simple, lo que podría ser el cifrado de "extremo a extremo".
\section{RSA Un Caso Asimétrico Vigente}
Su nombre deriva de las iniciales de sus creadores: Ronald Rivest, Adi Shamir, y Leonard Adleman, profesionales de las ciencias computacionales con grandes reconocimientos, entre ellos el premio Touring; y notables logros en diversas áreas de la investigación, algunos de ellos a partir de haber combinado con éxito, su esfuerzo en este pequeño, pero robusto algoritmo, que aún esta vigente. El precio de su vigencia, es tener que utilizar números primos $p$ y $q$, muy grandes para que cualquier ataque tenga como principal desafio la factorización de $n$. Así que los principales esfuerzos se dan, por un lado, en métodos más eficientea para generar numeros primos muy grandes y por otro (la de los ataques) métodos más eficientes para la factorización de enteros muy grandes.\\

\begin{tikzpicture}[scale =1,information text/.style={rounded corners=7pt,inner sep=2ex}]
\shadedraw (0,5)[xshift=1.85cm] node[left,text width=10cm, information text,scale=1,left color=blue,right color=green]
{\begin{minipage}{10cm}\bf\color{white}

\tikz \draw (0,0) node[fill=black,text width=10cm]
{
\textcolor{yellow}{El Criptosistema RSA\cite{Stinson2019}}\\
 Sea $n=pq$, con $p$ y $q$ números primos. Sean $\mathcal{P}=\mathcal{C}=\mathbb{Z}_n $ (El anillo finito de enteros modulo $m$) y defina $$\mathcal{K}=\{(n,p,q,a,b):\ ab\equiv 1\ \pmod{\varphi (n)}\}.$$
Para $K = (n, p, q, a, b)$, defina
$$e_K (x)\equiv x^b \pmod{n}$$ y
$$d_K (y)\equiv y^a \pmod{n}$$
Aquí $x, y \in \mathbb{Z}_n$. Los valores $n$ y $b$ constituyen la clave pública, en tanto los valores $p$, $q$ y $a$ forman la clave privada del sistema asimétrico.
};
\end{minipage}};
\end{tikzpicture}

\begin{tikzpicture}[scale =1,information text/.style={rounded corners=7pt,inner sep=2ex}]
\shadedraw (0,5)[xshift=1.85cm] node[left,text width=10cm, information text,scale=1,left color=green,right color=blue]
{\begin{minipage}{10cm}\bf\color{white}

\tikz \draw (0,0) node[fill=black,text width=10cm]
{
\textcolor{yellow}{Algoritmo RSA}\\
\begin{enumerate}
\item Generar dos números primos grandes\footnote{\textcolor{red!35}{${}^a$ Un estándar inicial sería de 1024 bytes}}, $p$ y $q$, $p\neq p.$
\item $n\to pq$; $\varphi (n) \to (p-1)(q-1)$
\item Genere o elija aleatoriamente $b$, tal que:  $1<b<\varphi (n)$, y $(b, \varphi (n))=1$. Acá $(\ ,\ )$ refiere el Máximo Común Divisor.
\item $a\to b^{-1} \mod\varphi (n)$
\item La llave pública es el par $[n,b]$ y la llave privada consiste en la terna $[p,q,a]$.
\end{enumerate}
};
\end{minipage}};
\end{tikzpicture}

\subsection*{Ejemplo:} Suponga que Roberto escoge $p=521$ y $q=541$. Entonces $n=281861$ y  $\varphi (n)=(p-1)(q-1)=(520)(540)=280800$. Entonces un entero $b$ puede usarse como un exponente de encriptación si y solamente si $(\varphi (n),n)=1$. (En todo lo anterior, técnicamente resulta indiscreto hacer referencia a la factorización tanto de $n$ como de $\varphi (n)$, incluso, a cualquier otro hecho teórico que se derive de ello). Suponga también que Roberto tiene como escoger o generar aleatoriamente $b$, y escoge $b=5069$, entonces $b^{-1}= 193829$\footnote{Aunque $b^{-1}$ puede calcularse con cualquier algoritmo que valide el residuo unitario, por el tamaño de $\varphi (n)$, es mejor utilizar la siguiente calculadora online de Wolfram: \href{CALCU-INVERSO}{\underline{Calculadora $b^{-1}$ Mod n}} Las operaciones en (5) y (6) superan la unidad de aritmética de muchos dispositivos, por lo que es mejor y más directo usar el "Math Input" del sitio: \href{MATH-INPUT}{\underline{Wolfram Alpha}} }. Así, $a = b^{-1}$ sería el exponente de uso confidencial para el descifrado, el cual junto con $n=281,861$ Roberto colocaria en un registro para que Alicia pueda utilizarlos en el otro extremo. Suponga ahora que Alicia desea enviar a Roberto el texto llano $x = 3571$, entonces utiliza para el cifrado:
\begin{equation}
x^b \pmod {n} =  3571^{5069} \pmod {281861}= 82500 =x'
\end{equation}
Cuando Roberto recibe el texto cifrado $x' = 82500$, utiliza la clave confidencial para decifrar y calcula:
\begin{equation}
(x')^a \pmod {n} = 82500^{193829} \pmod {281861} = 3571 = x
\end{equation}\\

Naturalmente, existen otros algoritmos sobre cifrado asimétrico, pues este es uno de los temas más amplios y exhaustivos en redes de informática, en lo referente a seguridad. Para un enfoque matemático lea \cite{Stinson2019}.\\
\section{Algoritmo de Shor (Versión Clásica)}
Cuando conocí este algoritmo, se me vino a la mente el refrán "No hay mejor cuña sino del mismo palo". El matemático Peter Shor le dedicó buen tiempo a la factorización de enteros, y de la misma teoría de congruencias obtuvo el siguiente algoritmo, cuya única dificultad, es el tiempo que le llevaría a un ordenador clásico realizar dichos cálculos, los cuáles son de un orden considerablemente grande, para poder obtener la clave privada del RSA, a partir de la clave pública. La versión cuántica de este algoritmo difiere en la forma compleja de calcular el período.\\

\begin{tikzpicture}[scale =1,information text/.style={rounded corners=7pt,inner sep=2ex}]
\shadedraw (0,5)[xshift=1.85cm] node[left,text width=10cm, information text,scale=1,left color=yellow,right color=red]
{\begin{minipage}{10cm}\bf\color{white}

\tikz \draw (0,0) node[fill=black,text width=10cm]
{
\textcolor{yellow}{Algoritmo Shor (versión clásica)}\\
\begin{enumerate}
\item Dado $n > 2$ (supuestamente conocido), elija un entero $m < n$, que sea primo relativo con $n$.
\item Determine la secuencia o sucesión para el período $f$ de $m$. Si $f$ es impar, abandone, vuelva al paso (1) y elija otro $m$.
\begin{align*}
1\times m \mod n &= r_1 \\
r_1\times m \mod n &= r_2 \\
\hspace{1cm}\vdots\\
r_{\frac{f}{2}-1}\times m \mod n &= r_{\frac{f}{2}} \\
\hspace{1cm}\vdots\\
r_{f-1}\times m \mod n &= r_f = r_1
\end{align*}
\textcolor{red!40}{Note que como $f$ es el período} $r_f = r_1$
\item En la sucesión anterior, tome como $r$ el residuo correspondiente al término $\frac{f}{2}$ (ya que f es par).
\item Elija como candidatos de rompimiento los enteros $r-1$ y $r+1$. En caso de que $r+1 = n$, abandone y regrese al paso (1) eligiendo otro $m$.

\item Determine $p=(r-1, n)$ y $q=(r+1, n)$. Esto puede hacerlo mediante cualquier programa basado en el algoritmo para calcular el MCD. El resultado daría: $$n = p \times q$$
\end{enumerate}
};
\end{minipage}};
\end{tikzpicture}\\

\pagebreak
Como ilustración, veamos la forma clásica en que el algoritmo de Shor factoriza $n = 281861$.
\begin{itemize}
\item[PASO 1:] Elegimos un $m<n$ que sea primo relativo con $n = 281861$, esto puede hacerse requiriendo que el Máximo Común Divisor sea $1$, es decir $(m,281861)=1$. Suponga $m = 14$.
\item[PASO 2:] Calculamos el período $\mod 281861$. Utilizando un programa \texttt{QpythonAppConsole} en android, obtenemos que $f = 14040$, el cual es par, por lo que continuamos al siguiente paso, tomando nota que el programa nos da           $$r_{\frac{f}{2}}= r_{7020} = 28133$$
\item[PASO 3:] Así que establecemos $r = r_{\frac{f}{2}} = 28133$.
\item[PASO 4:] Elegimos como candidatos de rompimiento: $r-1= 28133-1= 28132$ y $r+1= 28133+1= 28134$. Aquí verificamos que $r+1= 28134 \ne 281861$, así que seguimos.
\item[PASO 5:] Ahora resta solamente calcular el MCD en ambos casos para obtener los factores (excepto el orden de $p$ y de $q$) $$p=(28132,281861) = 541$$
$$q=(28134,281861) = 521$$
Por lo tanto $$n=281861=541\times 521$$
\end{itemize}
\begin{figure}[!ht]
\centering
\includegraphics[scale=0.3]{ShorAlgol.png}
\caption{\href{ALGORITMO-PDF}{\underline{\textcolor{red}{\textbf{\texttt{Algoritmo}}}}} de Shor para el presente ejemplo, en \href{QPYTHON3L}{\underline{\textcolor{green!90!blue!80!black}{\textbf{\texttt{\Large{QP}ython3L}}}}} para android}
\end{figure}
\pagebreak
\renewcommand
\refname{Bibliografía}
\begin{thebibliography}{3}
\bibitem{Stinson2019} STINSON, Douglas R. \& PATERSON, Maura B. \underline{Cryptography
Theory and Practice.}
Fourth Edition CRC Press
Taylor \& Francis Group
6000 Broken Sound Parkway NW, Suite 300.
Boca Raton, FL 33487-2742
© 2019 by Taylor \& Francis Group, LLC
\bibitem{tanen2003} TANENBAUM, Andrew S.\& WETHERALL, David J.  \underline{Redes de Computadoras.} © Pearson-Prentice Hall, Educación. México 2003.

\end{thebibliography}
\end{document}