Avances recientes en el criptoanálisis del criptosistema de Chor-Rivestaplicaciones criptográficas

Resumen

En el presente trabajo se estudian los criptosistemas de clave pública denominados 'de mochila' de alta densidad, En particular, se lleva a cabo un análisis pormenorizado del criptosistema de Chor-Rivest. Estos tipos de criptosistemas se denominan de mochila por estar basados en el problema computacional del mismo nombre. El primero de ellos fue propuesto por Merkle y Hellman y roto posteriormente por Shamir y Brickell. Más tarde, en 1985, Chor y Rivest propusieron otros criptosistema que ha permanecido invulnerable hasta que Vaudenay, en 2001, propuso un criptoanálisis para algunos de los parámetros originales. De forma más precisa, Chor y Rivest propusieron un criptosistema de tipo mochila, basado en la aritmética de cuerpos finitos, F_{q^h}, siendo q un primo, o la potencia de un primo, cercano a 200 y h menor = q un entero cercano a 25. Este criptosistema se caracteriza porque para la generación de las claves se requiere del cómputo de logaritmos en el cuerpo finito. Problema que, como es sabido, es considerado muy difícil desde el punto de vista computacional. Sin embargo, la seguridad de este criptosistema no se basa en el problema del cómputo de logaritmos discretos, sino en la dificultad de resolver un problema de mochila de alta densidad. El ataque propuesto por Vaudenay determina una clave privada equivalente a la empleada por el destinatario. Para ello, se busca la norma de generador del grupo multiplicativo F_{q^s}*, siendo s un divisor de h verificando s menor = sqrt{h+1/4}+1/2. Una vez calculada dicha norma, se determina la permutación empleada en la fase de generación de las claves. Conociendo ambos parámetros, Vaudenay demuestra cómo es posible determinar una clave equivalente a la clave privada original. Posteriormente se analiza el ca so en el que los parámetros q y h del cuerpo finito sobre el que se lleva a cabo la aritmética del criptosistema de Chor-Rivest sean tales que no permitan llevar a cabo, de forma efectiva, el a