8.1: Criptografía

En esta sección se discuten algunos aspectos elementales de la criptografía, que se refieren a la codificación y decodificación de mensajes. En criptografía, un mensaje (word) se transforma en una secuencia\(a\) de enteros, reemplazando cada letra en el mensaje por un conjunto específico y conocido de enteros que representan esta letra, y formando así un entero grande\(a\) por concatenación. Entonces este entero\(a\) se transforma (es decir, se codifica) en otro entero\(b\) mediante el uso de una congruencia de la forma\(b=a^k(mod\ m)\) para algunos elegidos\(k\) y\(m\), como se describe a continuación, con\(k\) desconocido excepto para el emisor y el receptor. \(b\)luego se envía al receptor quien lo decodifica de\(a\) nuevo usando una congruencia de la forma\(a=b^{\bar{k}}(mod\ m)\), donde\(\bar{k}\) se relaciona\(k\) y solo es conocido por el remitente y el receptor, y luego simplemente transforma los enteros en\(a\) back a letras y revela el mensaje de nuevo. En este procedimiento, si un tercero intercepta el número entero\(b\), la posibilidad de transformarlo en\(a\), aunque\(m\) y los enteros que representan las letras del alfabeto son exactamente conocidos, es casi imposible de hacer (es decir, tiene una probabilidad fantásticamente pequeña de ser alcanzado) si no\(k\) se sabe, que prácticamente el mensaje transformado no será revelado salvo al receptor pretendido.

Los resultados básicos sobre congruencias para permitir el procedimiento anterior se encuentran en los dos lemmas siguientes, donde\(\phi\) en los enunciados está la\(\phi\) función -de Euler.

Dejar\(a\) y\(m\) ser dos enteros, con\(m\) positivo y\((a,m)=1\). Si\(k\) y\(\bar{k}\) son enteros positivos con\(k\bar{k}=1(mod\ \phi(m))\), entonces\(a^{k\bar{k}}=a(mod\ m)\).

\(k\bar{k}=1(mod\ \phi(m))\)por lo tanto\(k\bar{k}=q\phi(m)+1\) (\(q\geq 0\)). De ahí\(a^{k\bar{k}}=a^{q\phi(m)+1}=a^{q\phi(m)}a\). Pero por el teorema de Euler, si\((a,m)=1\) entonces\(a^{\phi(m)}=1(mod\ m)\). Esto da eso\[(a^{\phi(m)})^qa=1(mod\ m)a=a(mod\ m),\] y por lo tanto eso\(a^{k\bar{k}}=a(mod\ m)\), y el resultado sigue.

También necesitamos lo siguiente.

Dejar\(m\) ser un entero positivo, y dejar\(r_1, r_2,\cdots, r_n\) ser un módulo de sistema de residuos reducido\(m\) (es decir, con\(n=\phi(m)\) y\((r_i,m)=1\) para\(i=1,\cdots,n\)). Si\(k\) es un entero tal que\((k,\phi(m))=1\), entonces\(r_1^k, r_2^k,\cdots, r_n^k\) forma un módulo de sistema de residuo reducido\(m\).

Antes de dar la prueba, hay que señalar que el lema anterior es de hecho una declaración if-y-only-if, es decir,\((k,\phi(m))=1\) si y solo si\(r_1^k, r_2^k,\cdots, r_n^k\) forma un módulo de sistema de residuos reducido\(m\). Sin embargo solo necesitamos la parte if, como en el lema.

Supongamos primero eso\((k,\phi(m))=1\). Mostramos que\(r_1^k, r_2^k,\cdots, r_n^k\) es un módulo de sistema de residuos reducidos\(m\). Asumir lo contrario, es decir\(r_i^k=r_j^k(mod\ m)\), asumir que\(\exists i,j\) tal que, en cuyo caso\(r_i^k\) y\(r_j^k\) pertenecería a la misma clase y así no\(r_1^k, r_2^k,\cdots, r_n^k\) formaría un sistema de residuos reducidos. Entonces, desde\((k,\phi(m))=1\),\(\exists\bar{k}\) con\(k\bar{k}=1(mod\ \phi(m))\), y así\[r_i^{k\bar{k}}=r_i(mod\ m)\hspace{0.5cm}and\hspace{0.5cm}r_j^{k\bar{k}}=r_j(mod\ m)\] por el lema anterior. Pero si\(r_i^k=r_j^k(mod\ m)\) entonces\((r_i^k)^{\bar{k}}=(r_j^k)^{\bar{k}}(mod\ m)\), y desde\(r_i^{k\bar{k}}=r_i(mod\ m)\) y\(r_j^{k\bar{k}}=r_j(mod\ m)\), entonces\(r_i=r_j(mod\ m)\) dando eso\(r_i\) y\(r_j\) pertenecer a la misma clase modulo\(m\), contradiciendo que\(r_1, r_2,\cdots, r_n\) forman un sistema de residuos reducidos. Así\(r_i\neq r_j\) implica que\(r_i^k\neq r_j^k\) si\((k,\phi(m))=1\).

Ahora para hacer criptografía, se procede de la siguiente manera. \(S\)Sea una frase dada en términos de letras y espacios entre las palabras que se pretende transformar a un destino con la posibilidad de ser interceptada y revelada por un tercero.

1. \(S\)Transforme en un entero (grande)\(a\) reemplazando cada letra y cada espacio entre palabras por un cierto número entero representativo (por ejemplo, números enteros de tres o cuatro dígitos para cada letra). \(a\)se forma concatenando los números enteros representativos que se producen.
2. Elija un par\(p_1\) y\(p_2\) de números primos muy grandes, cada uno (por ejemplo) del orden de un entero de cien dígitos, y estos deben mantenerse estrictamente conocidos solo por el remitente y el receptor. Entonces formar el producto\(m=p_1p_2\), que es en sí mismo un número muy grande hasta el punto de que las posibilidades de que alguien revele la factorización\(p_1p_2\) del número primo de\(m\) es increíblemente pequeña, aunque conozca este entero\(m\). Ahora uno tiene, por resultados estándar concernientes a la\(\phi\) -función, eso\(\phi(p_1)=p_1-1\) y\(\phi(p_2)=p_2-1\), y que, ya que\(p_1\) y\(p_2\) son relativamente primos,\(\phi(m)=\phi(p_1)\phi(p_2)=(p_1-1)(p_2-1)\). Así\(\phi(m)\) es un número muy grande, del orden de\(m\) sí mismo, y por lo tanto\(m\) tiene un sistema de residuos reducido que contiene un número muy grande de enteros del orden de\(m\) sí mismo. De ahí que casi cada entero menor que\(m\), con una probabilidad del orden\(1-1/10^{100}\) (casi 1), se encuentra en un sistema\(r_1, r_2,\cdots, r_{\phi(m)}\) de residuos reducido de\(m\). Así, casi todos los enteros positivos menores\(m\) que son relativamente primos con\(m\), con probabilidad del orden\(1-1/10^{100}\).
3. Ahora dado que casi todos los enteros positivos más pequeños que\(m\) es relativamente primo con\(m\), el entero\(a\) en sí es casi con certeza relativamente primo con\(m\), y por lo tanto está en un sistema de residuos reducido para\(m\). De ahí que por el lema 17 anterior, si\(k\) es un entero (grande) tal que\((k,\phi(m))=1\), entonces\(a^k\) pertenece a un sistema de residuos reducidos para\(m\), y existe un positivo único\(b\) menor que\(m\) con\(b=a^k(mod\ m)\).
4. Enviar\(b\) al destino donde\(\phi(m)\) y\(k\) se conozcan. El destino puede determinar un\(\bar{k}\) tal que\(k\bar{k}=1(mod\ \phi(m))\), y luego encuentra lo único\(c\) tal que\(c=b^{\bar{k}}(mod\ m)\). Ahora desde, casi con certeza,\((a,m)=1\), entonces casi con certeza\(c=a\) desde entonces\(c=b^{\bar{k}}(mod\ m)=(a^k)^{\bar{k}}(mod\ m)=a^{k\bar{k}}(mod\ m)\), y que por lema 16, viene dado por\(a(mod\ m)\) casi seguro ya que\((a,m)=1\) casi con certeza. Ahora el destino se traduce de\(a\) nuevo a letras y espacios para revelar la oración\(S\). Tenga en cuenta que si algún tercero intercepta\(b\), es casi seguro que no pueden revelar el número entero\(a\) ya que la probabilidad de que lo sepan\(\phi(m)=p_1p_2\) es casi nula, aunque sepan\(m\) y\(k\). En este caso prácticamente no podrán determinar un\(\bar{k}\) con\(k\bar{k}=1(mod\ \phi(m))\), recuperarlo\(a\) y transformarlo en\(S\).

Colaboradores y Atribuciones

• Template:ContribRaji