Epónimos relacionados con las matemáticas

procedimiento de cifrado/descifrado ElGamal se refiere a un esquema de cifrado basado en el problema matemático del logaritmo discreto. Es un algoritmo de criptografía asimétrica basado en la idea de Diffie-Hellman y que funciona de una forma parecida a este algoritmo discreto.

El algoritmo de ElGamal puede ser utilizado tanto para generar firmas digitales como para cifrar o descifrar.

Fue descrito por Taher Elgamal en 1984¹ y se usa en software GNU Privacy Guard, versiones recientes de PGP, y otros sistemas criptográficos. Este algoritmo no está bajo ninguna patente lo que lo hace de uso libre.

La seguridad del algoritmo se basa en la suposición que la función utilizada es de un sólo sentido debido a la dificultad de calcular un logaritmo discreto.

El procedimiento de cifrado (y descifrado) está basado en cálculos sobre un grupo cíclico cualquiera ${\displaystyle G\,}$ lo que lleva a que la seguridad del mismo dependa de la dificultad de calcular logaritmos discretos en ${\displaystyle \,G}$.

El algoritmo original

Mostremos el criptosistema propuesto inicialmente por Tahar ElGamal en su artículo.

Generación de la clave

Para generar la clave, Alicia escoge un número primo ${\displaystyle p\,}$ cualquiera tal que el logaritmo discreto no es soluble en un tiempo asumible en ${\displaystyle Z_{p}^{*}}$ (grupo multiplicativo módulo un primo p). Esto último se traduce en que ${\displaystyle p-1\,}$ tenga un factor primo grande (lo que hace que el problema del logaritmo discreto sea difícil² ).

Además Alicia elige dos números aleatorios ${\displaystyle g\,}$ (el generador del grupo cíclico (${\displaystyle {Z}_{p}^{*})}$ y ${\displaystyle a\,}$ (que actuará como clave privada) tal que ${\displaystyle a\in \{0,\ldots ,p-1\}}$.

Alicia calcula el valor de ${\displaystyle K=\,g^{a}{\pmod {p}}}$. La clave pública será ${\displaystyle (g,p,K)}$, mientras que el valor de ${\displaystyle a}$ lo mantendrá en secreto. Despejando a de la ecuación ${\displaystyle K=\,g^{a}{\pmod {p}}}$ obtenemos la relación siguiente entre los componentes de la clave pública y la clave privada ${\displaystyle \log _{g}{K}{\pmod {p}}=a}$ con lo que el criptosistema es seguro siempre que sea difícil hallar el logaritmo discreto.

Cifrado

Supongamos que Bruce tiene un texto claro que quiere enviar cifrado a Alicia. Lo primero por hacer es convertir este texto en un entero m entre 1 y ${\displaystyle p-1}$ (${\displaystyle m\in Z_{p}}$). Esto no es parte del cifrado, sino que es una manera de codificar estándar, conocida por todos. Luego Bruce escoge arbitrariamente un número ${\displaystyle b\in \{2,\ldots ,p-1\}}$ (que mantendrá secreto) para finalmente calcular:

${\displaystyle y_{1}=g^{b}\,{\pmod {p}}}$

${\displaystyle y_{2}=K^{b}\,m\,{\pmod {p}}}$

El mensaje cifrado final corresponde a la tupla ${\displaystyle \,C_{b}(m,b)=(y_{1},y_{2})}$

Descifrado

Para descifrar aprovechamos que:

${\displaystyle y_{1}^{-a}y_{2}{\pmod {p}}=(g^{b})^{-a}K^{b}m{\pmod {p}}=g^{-ab}(g^{a})^{b}m{\pmod {p}}=(g^{a})^{-b}(g^{a})^{b}m{\pmod {p}}=m{\pmod {p}}}$

Por tanto para descifrar se tiene que realizar el siguiente cálculo:

${\displaystyle y_{1}^{-a}y_{2}{\pmod {p}}}$

donde ${\displaystyle y_{1}^{-a}}$ representa el inverso de ${\displaystyle y_{1}^{a}}$ módulo ${\displaystyle p}$ lo que indica que que para calcular el descifrado, es necesario conocer ${\displaystyle a}$, que es la clave privada de Alicia.

Por el pequeño teorema de Fermat se demuestra que ${\displaystyle y_{1}^{-a}=y_{1}^{p-1-a}}$ y lo podemos aplicar.

Demostración: El pequeño teorema de Fermat indica que ${\displaystyle x^{p-1}{\pmod {p}}=1}$ con p primo y x>0 coprimo con p. Elevando a ${\displaystyle a}$ la expresión obtenemos que ${\displaystyle {x^{p-1}}^{a}{\pmod {p}}=1^{a}=1}$. Por tanto ${\displaystyle x^{(p-1)\cdot a}{\pmod {p}}=x^{ap-a}{\pmod {p}}=x^{a}\cdot x^{p-1-a}{\pmod {p}}=1}$. Despejando ${\displaystyle x^{p-1-a}{\pmod {p}}=x^{-a}{\pmod {p}}}$

Ejemplos

Simple

Alicia elige los valores:

${\displaystyle p=17\,}$ (primo aleatorio y suponemos que p-1=15 tiene un factor primo grande lo cual no es cierto)

${\displaystyle g=3\,}$ (generador aleatorio)

${\displaystyle a=6\,}$ (clave privada aleatoria)

Alicia calcula

${\displaystyle K=g^{a}\,{\pmod {p}}=3^{6}\,{\pmod {17}}=15\,}$ (valor calculado)

Por tanto la clave pública será ${\displaystyle \,(g,p,K)=\,(17,3,15)}$.

Bruce tiene el texto claro

${\displaystyle \,m=9}$ (el cual está entre 1 y p-1)

Bruce escoge un ${\displaystyle \,b=5}$ aleatorio entre 2 y p-1 Bruce calcula

${\displaystyle y_{1}=g^{b}{\pmod {p}}=3^{5}{\pmod {17}}=5}$

${\displaystyle y_{2}=K^{b}m{\pmod {p}}=15^{5}\cdot 9{\pmod {17}}=1}$.

Por lo que el texto cifrado es ${\displaystyle C_{b}(m,b)=(y_{1}=5,y_{2}=1)}$

Para descifrar Alicia usa la clave privada ${\displaystyle \,(a=6)}$ y el Pequeño Teorema de Fermat:

${\displaystyle m=y_{1}^{p-1-a}y_{2}{\pmod {p}}=5^{10}\cdot 1{\pmod {17}}=9}$.

Complejo

Veamos una aplicación más real del algoritmo:

Alicia elige los valores:

${\displaystyle p=15485863}$ (primo aleatorio y para ${\displaystyle p-1=15485862=3*2*7^{2}*52673}$ suponemos que 52673 es sufientemente grande)

${\displaystyle g=7}$ (generador aleatorio)

${\displaystyle a=21702}$ (clave privada aleatoria)

Alicia calcula

${\displaystyle K=g^{a}{\pmod {p}}=7^{2}1702{\pmod {15485863}}=8890431}$ (valor calculado)

Por tanto la clave pública será ${\displaystyle (g,p,K)=(7,15485863,8890431)}$.

Bruce tiene el texto claro "HIJO"

${\displaystyle m=7\cdot 26^{3}+8\cdot 26^{2}+9\cdot 26+14=128688}$ (el cual está entre 1 y p-1)

Bruce escoge un ${\displaystyle b=480}$ aleatorio entre 2 y p-1

Bruce calcula

${\displaystyle y_{1}=g^{b}{\pmod {p}}=7^{4}80{\pmod {15485863}}=12001315}$

${\displaystyle y_{2}=K^{b}m{\pmod {p}}=8890431^{4}80\cdot 1286889{\pmod {15485863}}=8263449}$.

Por lo que el texto cifrado es ${\displaystyle C_{b}(m,b)=(y_{1}=12001315,y_{2}=8263449)}$ que al decodificarlo queda:

${\displaystyle y_{1}=12001315=1*26^{5}+0*26^{4}+6*26^{3}+21*26^{2}+11*26+1}$=BAGVLB

${\displaystyle y_{2}=8263449=18*26^{4}+2*26^{3}+4*26^{2}+0*26+1}$=SCEAZ

Con lo que el mensaje a enviar es (BAGVLB,SCEAZ)

Para descifrar Alicia usa la clave privada ${\displaystyle (a=21702)}$:

${\displaystyle y_{1}^{-a}y_{2}{\pmod {p}}=14823281\cdot 8263449{\pmod {15485863}}=128688}$ ya que por el pequeño teorema de fermat tenemos

${\displaystyle y_{1}^{-a}{\pmod {p}}=y_{1}^{p-1-a}{\pmod {p}}=12001315^{15464160}=14823281}$

Generalización

Lo único que se utiliza de la congruencia módulo ${\displaystyle p}$ es que el conjunto ${\displaystyle (\mathbb {Z} /p)^{\times }=\{x\in \mathbb {Z} :1\leq x$

 forma un grupo con las operaciones módulo ${\displaystyle p}$ y que en dicho grupo el problema del logaritmo discreto resulta difícil.

Por lo tanto, puede cambiarse en este criptosistema al grupo ${\displaystyle (\mathbb {Z} /p)^{\times }}$ por cualquier otro grupo ${\displaystyle G}$ en el que el logaritmo discreto sea complicado.

Por ejemplo, resulta bastante efectivo utilizar como grupo una curva elíptica sobre ${\displaystyle \mathbb {Z} /p}$ (véase Criptografía de curva elíptica), ya que no se conoce un algoritmo de tiempo subexponencial capaz de resolver el problema del logaritmo discreto en curvas elípticas en general.³

Propiedades

Efectividad

Hasta el momento el algoritmo ElGamal de cifrado/descifrado puede ser considerado un algoritmo efectivo.

Un adversario con la habilidad de calcular logaritmos discretos podría ser capaz de romper un cifrado ElGamal. Sin embargo, en la actualidad, el algoritmo de computación de logaritmos discretos (cuando trabajamos módulo un primo) es subexponencial con una complejidad de λ = 1/3, la misma que la de factorizar dos números primos, y por tanto, no es accesible de realizar tal tarea en números grandes en un tiempo razonable. El logaritmo discreto es aún más difícil si trabajamos en otros grupos (como por ejemplo, curvas elípticas).

Véase Récords en logaritmos discretos para una muestra de las posibilidades que da la computación actual a la hora de resolver este problema.

Maleabilidad

Existe un caso en que este algoritmo se vuelve maleable. Esto implica que bajo un ataque específico la seguridad de ElGamal se puede quebrar. Este ataque usa el hecho de tener el texto cifrado ${\displaystyle C_{b}=(B,M)\,}$ del texto claro ${\displaystyle m\,}$ (ambos conocidos). Sabiendo esto se puede llegar a que el texto cifrado ${\displaystyle C_{b}=(B,k*M)\,}$ corresponde al texto plano ${\displaystyle k*m\,}$. Si ahora la persona que cifró el mensaje anterior genera otro texto cifrado ${\displaystyle C_{b}=(B,M')\,}$ (utilizando el mismo ${\displaystyle b\,}$ con el que cifró anteriormente) el adversario debería ser capaz de llegar al texto plano ${\displaystyle m'\,}$ correspondiente siguiente los siguientes pasos:

Calcular ${\displaystyle k=M'/M\,}$

Buscar un ${\displaystyle m'\,}$ tal que ${\displaystyle \,m'=m*k{\pmod {p}}}$ tomando en cuenta que ${\displaystyle m'\,}$ al igual que ${\displaystyle m\,}$ cumple con estar entre ${\displaystyle 0\,}$ y ${\displaystyle p-1\,}$

Tomando el peor caso, el atacante obtendrá dos textos claros (debido a la función módulo).

Rendimiento

El análisis de rendimiento del algoritmo ElGamal es similar al de RSA. Concretamente tenemos el siguiente análisis

Sea ${\displaystyle \,n}$ el módulo usado en ElGamal. Los procesos de cifrado y descifrado de ElGamal toman tiempos ${\displaystyle \,O(\log n)}$.

Homomórfico

El cifrado ElGamal es un cifrado homomórfico en la multiplicación. En efecto si:

• ${\displaystyle E(m_{1})=(g^{b_{1}}{\pmod {p}},K^{b_{1}}\,m_{1}\,{\pmod {p}})}$
• ${\displaystyle E(m_{2})=(g^{b_{2}}{\pmod {p}},K^{b_{2}}\,m_{2}\,{\pmod {p}})}$

entonces:

${\displaystyle E(m_{1})\cdot E(m_{2})=(g^{b_{1}}{\pmod {p}},K^{b_{1}}\,m_{1}\,{\pmod {p}})\cdot (g^{b_{2}}{\pmod {p}},K^{b_{2}}\,m_{2}\,{\pmod {p}})=(g^{b_{1}+b_{2}}{\pmod {p}},K^{b_{1}+b_{2}}\,m_{1}\,{\pmod {p}})=E(m_{1}\cdot m_{2})}$

Prueba de conocimiento del texto original

Este tipo de cifrado permite probar el conocimiento del texto original cifrado sin tener que revelarlo (esta propiedad en inglés se llama plaintext aware). Por ejemplo esto es muy útil en sistemas de voto electrónico para asegurarnos de que el elector es el que realmente ha cifrado sus intenciones de voto y no las suministradas por un posible atacante. Para hacer la demostración se aprovecha del Algoritmo de identificación de Schnorr. ⁴

Para un texto cifrado de ElGamal ${\displaystyle (M,G)=(g^{b},K^{b}m)}$, con el algoritmo de identificación de Schnorr, se prueba que P conoce b. Como la clave pública es ${\displaystyle (g,p,K)}$ entonces si P conoce b, entonces se puede recuperar m calculando ${\displaystyle m=G/K^{b}=K^{b}m/K^{b}}$. Por tanto el protocolo prueba que P conoce el texto original m.⁵

Prueba de recifrado

El Protocolo de Chaum-Pedersen puede ser usado para que un texto cifrado ${\displaystyle (G',M')=(Gy^{s},Mg^{s})}$ es un recifrado de ${\displaystyle (G.M)=(my^{r},g^{r})}$ sin revelar el factor de aleatorización s. La prueba de demostrar por el Protocolo de Chaum-Pedersen que ${\displaystyle log_{y}(G'/G)=log_{g}(M'/M)}$ o lo que es lo mismo ${\displaystyle log_{y}(Gy^{s}/G)=log_{g}(Mg^{s}/M)}$ que en ambos casos es igual a ${\displaystyle s}$. Esto implica que existe un valor s que lo hace posible.⁶

Prueba de cifrado de uno de los textos claros predefinidos

El Protocolo de Cramer-Damgard-Schoenmakers permite demostrar que un texto cifrado con ElGamal es el correspondiente a un texto claro de entre los posibles (los textos claros posibles tienen que estar predeterminados) sin revelar cual es. Esto es muy útil para votaciones electrónicas que usan este tipo de cifrado.

Durante 1984 y 1985 ElGamal desarrolló un nuevo criptosistema de clave pública basado en la intratabilidad computacional del problema del logaritmo discreto: obtener el valor de a partir de la expresión

es, como hemos comentado para RSA, computacionalemente intratable por norma general. 

Aunque generalmente no se utiliza de forma directa, ya que la velocidad de cifrado y autenticación es inferior a la obtenida con RSA, y además las firmas producidas son más largas (Digital Signature Standard), del NIST (National Institute of Standards and Technology) estadounidense. 

En este sistema, para generar un par clave pública/privada, se escoge un número primo grande, , y dos enteros y , , , y se calcula

La clave pública será el número , y la privada el número . 

Para firmar un determinado mensaje, el emisor elige un entero aleatorio , , no usado con anterioridad y con la restricción que sea relativamente primo a , y computa

,

donde es el inverso de ; así,

.

La firma del mensaje estará entonces formada por y ; un potencial receptor puede usar la clave pública y para calcular y comprobar si coincide con :

El criptosistema de ElGamal tiene una característica determinante que lo distingue del resto de sistemas de clave pública: en el cifrado se utiliza aparte de la clave pública del receptor, la clave privada del emisor.

El cifrado Vernam es un algoritmo de criptografía inventado por Gilbert Vernam, ingeniero AT&T Bell Labs, en 1917.

Funcionamiento

En terminología moderna, un cifrado de Vernam es un cifrado de flujo en el que el texto en claro se combina, mediante la operación XOR, con un flujo de datos aleatorio o pseudoaleatorio del mismo tamaño, para generar un texto cifrado. El uso de datos pseudoaleatorios generados por un generador de números pseudoaleatorios criptográficamente seguro es una manera común y efectiva de construir un cifrado en flujo. El RC4 es un ejemplo de cifrado de Vernam que se utiliza con frecuencia en Internet.

Utilización

Posteriormente a la invención del cifrado de Vernam, Joseph Mauborgne propuso que la cinta de papel contuviera información completamente aleatoria. Las dos ideas, combinadas con el uso único de las claves, implementan la libreta de un solo uso, aunque ninguno de los dos inventores utilizó ese nombre.

Claude Shannon, también de Bell Labs, demostró que la libreta de un solo uso es irrompible (trabajo realizado entre 1940 y 1945; publicado por primera vez en la Bell Labs Technical Journal, 1948/49). Es el primer y único método de cifrado para el que existe tal demostración.

El método Vernam fue utilizado durante la segunda guerra mundial por espías de diversas nacionalidades, a los que se les daba una secuencia binaria aleatoria con la recomendación de utilizarla con un único proceso de cifrado.

Variantes

En la actualidad el cifrado de Vernam puede ser utilizado con diferentes codificaciones para el alfabeto, entre ellas, se puede utiliza la codificación ASCII, sin embargo, por utilizar la operación XOR, el criptograma puede tener códigos de control de la tabla ASCII, es decir, no imprimibles, por lo que es necesario representar el criptograma con el número de código ASCII, generalmente se utiliza la numeración hexadecimal para utilizar solo dos dígitos por símbolo.

Algoritmo de Vernam

Vernam. (Sustitución – Polialfabética – No-periódica)

Existen 2 formas para el cifrado de Vernam:

1. Vernam- suma módulo 2

• La operación de cifrado es la función XOR.
• Usa una secuencia cifradora binaria y aleatoria S que se obtiene a partir de una clave secreta K compartida por emisor y receptor.
• El algoritmo de descifrado es igual al de cifrado por la involución de la función XOR.
• La clave será tan larga o más que el mensaje y se usará una sola vez.
• Los valores de cada letra se obtienen de una tabla ascii

2. Vernam- suma módulo 27

• La operación de cifrado es la función suma.
• Se numera nuestro alfabeto comenzando del 0.
• Finalizando la suma del Mcla con la clave K, se aplicará el mod 27 a cara resultado.