El algoritmo Cayley-Purser era 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 nombró en honor al matemático Arthur Cayley . Desde entonces se ha descubierto que tiene fallas como algoritmo de clave pública, pero fue objeto de considerable atención de los medios.
Historia
Durante una experiencia laboral con Baltimore Technologies, Michael Purser le mostró a Flannery un artículo inédito que describía un nuevo esquema criptográfico de clave pública utilizando 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 Tecnología y Científicos Jóvenes de ESAT de 1998 con un proyecto que describía las técnicas criptográficas ya existentes desde el cifrado Caesar hasta RSA . Esto le valió el premio Intel Student Award, 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 un trabajo original para agregar a su proyecto de exhibición, Flannery le pidió permiso a Michael Purser para incluir trabajo basado en su esquema criptográfico.
Por consejo de su padre matemático, Flannery decidió usar matrices para implementar el esquema de Purser, ya que la multiplicación de matrices tiene la propiedad necesaria de no ser conmutativa. Como el algoritmo resultante dependería de la multiplicación, sería mucho más rápido que el algoritmo RSA que usa un paso exponencial . Para su proyecto Intel Science Fair, Flannery preparó una demostración en la que se cifró el mismo texto sin formato utilizando RSA y su nuevo algoritmo Cayley-Purser y, de hecho, mostró una mejora significativa en el tiempo.
Al regresar a la Exposición de Tecnología y Científicos Jóvenes de 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 reemplazaría a RSA, sabiendo que cualquier nuevo sistema criptográfico tendría que pasar la prueba del tiempo antes de que pudiera 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, periódicos de todo el mundo informaron la historia 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 competencias posteriores, incluida una competencia europea en la que ganó un premio importante.
Descripción general
La notación utilizada en esta discusión es como en el artículo original de Flannery.
Generación de claves
Como RSA, Cayley-sobrecargo comienza mediante la generación de dos grandes números primos 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:
Este grupo se elige porque tiene un orden grande (para semiprime grande n ), igual a ( p 2 −1) ( p 2 - p ) ( q 2 −1) ( q 2 - q ).
Dejar y ser dos de tales matrices de GL (2, n ) elegidas de manera que. Elija un número natural r y calcule:
La clave pública es , , , y . La clave privada es.
Cifrado
El remitente comienza generando un número natural aleatorio sy calculando:
Luego, para cifrar un mensaje, cada bloque de mensajes se codifica como un número (como en RSA) y se colocan de cuatro en cuatro como elementos de una matriz de texto plano. . Cada está encriptado usando:
Luego y se envían al receptor.
Descifrado
El receptor recupera la matriz de texto plano original vía:
Seguridad
Recuperando la clave privada de es computacionalmente inviable, al menos tan difícil como encontrar raíces cuadradas mod n (ver residuo cuadrático ). Podría recuperarse de y si el sistema podría resolverse, pero la cantidad de soluciones para este sistema es grande siempre que los elementos del grupo tengan un orden grande, lo que puede garantizarse para casi todos los elementos.
Sin embargo, el sistema se puede romper al encontrar múltiples de resolviendo para en la siguiente congruencia:
Observe que existe una solución si para algunos y
Si es conocida, - un múltiplo de . Cualquier múltiplo de rendimientos . Esto presenta una debilidad fatal para el sistema, que aún no se ha reconciliado.
Esta falla no excluye 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 a cifrado simétrico, que es más rápido que Cayley-Purser.
Ver también
Referencias
- Sarah Flannery y David Flannery. En código: un viaje matemático . ISBN 0-7611-2384-9