Algoritmo de Cayley-Purser

Algoritmo de criptografía de clave pública de 1999

El algoritmo Cayley-Purser fue un algoritmo de criptografía de clave pública publicado a principios de 1999 por la irlandesa Sarah Flannery , de 16 años , basado en un trabajo inédito de Michael Purser, fundador de Baltimore Technologies , una empresa de seguridad de datos de Dublín . Flannery lo bautizó en honor al matemático Arthur Cayley . Desde entonces se ha descubierto que tiene defectos como algoritmo de clave pública, pero fue objeto de considerable atención mediática.

Historia

Durante una pasantía en Baltimore Technologies, Flannery conoció un artículo inédito de Michael Purser que describía un nuevo esquema criptográfico de clave pública que utilizaba la multiplicación no conmutativa . Se le pidió que escribiera una implementación de este esquema en Mathematica .

Antes de esta colocación, Flannery había asistido a la Exposición de Jóvenes Científicos y Tecnología ESAT de 1998 con un proyecto que describía técnicas criptográficas ya existentes, desde el cifrado César hasta el RSA . Esto le había hecho ganar el Premio Intel para Estudiantes, que incluía la oportunidad de competir en la Feria Internacional de Ciencia e Ingeniería Intel de 1998 en los Estados Unidos. Sintiendo que necesitaba algún trabajo original para agregar a su proyecto de exhibición, Flannery le pidió permiso a Michael Purser para incluir un trabajo basado en su esquema criptográfico.

Por consejo de su padre matemático, Flannery decidió utilizar matrices para implementar el esquema de Purser, ya que la multiplicación de matrices tiene la propiedad necesaria de ser no conmutativa. Como el algoritmo resultante dependería de la multiplicación, sería mucho más rápido que el algoritmo RSA, que utiliza un paso exponencial . Para su proyecto de Intel Science Fair, Flannery preparó una demostración en la que se cifraba el mismo texto sin formato utilizando tanto RSA como su nuevo algoritmo Cayley-Purser y, de hecho, mostró una mejora significativa en el tiempo.

Al regresar a la Exhibición de Jóvenes Científicos y Tecnología ESAT en 1999, Flannery formalizó el tiempo de ejecución de Cayley-Purser y analizó una variedad de ataques conocidos, ninguno de los cuales se determinó como efectivo.

Flannery no afirmó que el algoritmo Cayley-Purser fuera a sustituir al RSA, pues sabía que cualquier nuevo sistema criptográfico tendría que superar la prueba del tiempo antes de poder ser reconocido como un sistema seguro. Sin embargo, los medios de comunicación no fueron tan circunspectos y cuando recibió el primer premio en la exposición ESAT, los periódicos de todo el mundo informaron de que una joven genio había revolucionado la criptografía.

De hecho, poco después se descubrió un ataque al algoritmo, pero ella lo analizó y lo incluyó como apéndice en competiciones posteriores, incluida una competición europea en la que ganó un importante premio.

Descripción general

La notación utilizada en esta discusión es la misma que en el artículo original de Flannery.

Generación de claves

Al igual que RSA, Cayley-Purser comienza generando dos primos grandes p y q y su producto n , un semiprimo . A continuación, considere GL (2, n ), el grupo lineal general de matrices 2×2 con elementos enteros y aritmética modular mod n . Por ejemplo, si n = 5, podríamos escribir:

${\displaystyle {\begin{bmatrix}0&1\\2&3\end{bmatrix}}+{\begin{bmatrix}1&2\\3&4\end{bmatrix}}={\begin{bmatrix}1&3\\5&7\end{bmatrix}}\equiv {\begin{bmatrix}1&3\\0&2\end{bmatrix}}}$

${\displaystyle {\begin{bmatrix}0&1\\2&3\end{bmatrix}}{\begin{bmatrix}1&2\\3&4\end{bmatrix}}={\begin{bmatrix}3&4\\11&16\end{bmatrix}}\equiv {\begin{bmatrix}3&4\\1&1\end{bmatrix}}}$

Se elige este grupo porque tiene un orden grande (para un semiprimo grande n ), igual a ( p ² −1)( p ² − p )( q ² −1)( q ² − q ).

Sean y dos matrices de GL(2, n ) elegidas de manera que . Elija un número natural r y calcule: ${\displaystyle \chi }$ ${\displaystyle \alpha }$ ${\displaystyle \chi \alpha \not =\alpha \chi }$

${\displaystyle \beta =\chi ^{-1}\alpha ^{-1}\chi ,}$

${\displaystyle \gamma =\chi ^{r}.}$

La clave pública es , , , y . La clave privada es . ${\displaystyle n}$ ${\displaystyle \alpha }$ ${\displaystyle \beta }$ ${\displaystyle \gamma }$ ${\displaystyle \chi }$

Encriptación

El remitente comienza generando un número natural aleatorio s y calculando:

${\displaystyle \delta =\gamma ^{s}}$

${\displaystyle \epsilon =\delta ^{-1}\alpha \delta }$

${\displaystyle \kappa =\delta ^{-1}\beta \delta }$

Luego, para cifrar un mensaje, cada bloque de mensaje se codifica como un número (como en RSA) y se colocan de cuatro en cuatro como elementos de una matriz de texto simple . Cada uno se cifra mediante: ${\displaystyle \mu }$ ${\displaystyle \mu }$

${\displaystyle \mu '=\kappa \mu \kappa .}$

Luego se envían al receptor. ${\displaystyle \mu '}$ ${\displaystyle \epsilon }$

Descifrado

El receptor recupera la matriz de texto simple original mediante: ${\displaystyle \mu }$

${\displaystyle \lambda =\chi ^{-1}\epsilon \chi ,}$

${\displaystyle \mu =\lambda \mu '\lambda .}$

Seguridad

Recuperar la clave privada de es computacionalmente inviable, al menos tan difícil como encontrar raíces cuadradas módulo n (ver residuo cuadrático ). Se podría recuperar de y si el sistema pudiera resolverse, pero la cantidad de soluciones para este sistema es grande siempre que los elementos del grupo tengan un orden grande, lo que se puede garantizar para casi todos los elementos. ${\displaystyle \chi }$ ${\displaystyle \gamma }$ ${\displaystyle \alpha }$ ${\displaystyle \beta }$ ${\displaystyle \chi \beta =\alpha ^{-1}\chi }$

Sin embargo, el sistema se puede romper encontrando un múltiplo de resolviendo en la siguiente congruencia: ${\displaystyle \chi '}$ ${\displaystyle \chi }$ ${\displaystyle d}$

${\displaystyle d\left(\beta -\alpha ^{-1}\right)\equiv \left(\alpha ^{-1}\gamma -\gamma \beta \right){\pmod {n}}}$

Observe que existe una solución si para algunos y ${\displaystyle i,j\in \left|\gamma \right|}$ ${\displaystyle x,y\in \mathbb {Z} _{n}}$

${\displaystyle x\left(\beta _{ij}^{-1}-\alpha _{ij}\right)\equiv y{\pmod {n}}.}$

Si se conoce, — un múltiplo de . Cualquier múltiplo de da como resultado . Esto presenta una debilidad fatal para el sistema, que aún no ha sido reconciliado. ${\displaystyle d}$ ${\displaystyle d\mathrm {I} +\gamma =\chi '}$ ${\displaystyle \chi }$ ${\displaystyle \chi }$ ${\displaystyle \lambda =\kappa ^{-1}=v^{-1}\chi ^{-1}\epsilon v\chi }$

Esta falla no impide el uso del algoritmo como un algoritmo mixto de clave privada/clave pública, si el remitente transmite en secreto, pero este enfoque no presenta ninguna ventaja sobre el enfoque común de transmitir una clave de cifrado simétrico utilizando un esquema de cifrado de clave pública y luego cambiar al cifrado simétrico, que es más rápido que Cayley-Purser. ${\displaystyle \epsilon }$

Véase también

• Criptografía no conmutativa

Referencias

• Sarah Flannery y David Flannery. En código: un viaje matemático . ISBN  0-7611-2384-9