Loading
Study Reminders
Support
Text Version

Set your study reminders

We will email you at these times to remind you to study.
  • Monday

    -

    7am

    +

    Tuesday

    -

    7am

    +

    Wednesday

    -

    7am

    +

    Thursday

    -

    7am

    +

    Friday

    -

    7am

    +

    Saturday

    -

    7am

    +

    Sunday

    -

    7am

    +

Foundations of Cryptography Dr. Ashish Choudhury Department of Computer Science Indian Institute of Technology-Bangalore Lecture – 52 RSA Signatures Hola a todos, bienvenidos a esta conferencia. Así que sólo para recapitular, en la última conferencia hemos introducido firmas digitales, hemos visto su definición formal. (Consulte Tiempo de diapositiva: 00:40) En esta conferencia veremos una instanciación de firmas digitales basadas en la función RSA. A saber, primero veremos las firmas RSA simples y los ataques que se pueden lanzar en las firmas RSA simples. Y luego veremos una instanciación de firmas seguras basadas en la función RSA a la que llamamos hash de dominio completo RSA. (Consulte la hora de la diapositiva: 00:55)Así que, comencemos con las signaturas RSA. Y por esto permítanme recordar la permutación de la puerta de trampa de una vía RSA. Tenemos el algoritmo de generación de parámetros, que primero genera los parámetros,,. Aquí, el módulo es el producto de y, escoge y, donde y son inversamente multiplicativo uno del otro. Y luego establecemos el parámetro público para ser, y el parámetro secreto para ser,. Y nuestra función de avance RSA es mod. Y nuestra función inversa es mod. Y hemos probado que ambas funciones son inversas entre sí y también consideramos que es una función candidata de una forma, donde está la puerta de la trampa. Ahora, la firma RSA simple que podemos obtener de esta permutación de puerta de trampa de una vía RSA se obtiene al visualizar o tratar esta función inversa como la función de firma. Esto significa que cualquier entidad que posea puede utilizar la función inversa para calcular la firma y utilizar la función de dirección hacia adelante para que sea la función de verificación. Más específicamente, la firma RSA sin formato sobre el espacio de mensajes Zwed se obtiene de la siguiente manera. El algoritmo de generación de claves ejecuta el algoritmo de Gen RSA para obtener los parámetros y ahora, el parámetro público se establece como la clave de verificación, mientras que la información de la puerta de la trampa se establece como la clave de firma. Para firmar un mensaje que pertenece a Zwized, básicamente calculamos mod, donde estará disponible con el firmante. Y para verificar un mensaje, un par de firmas (, lo que calculamos primero es el valor de la función RSA en el componente de firma, a saber, calculamos mod y lo comparamos con el mensaje recibido. (Consulte la hora de la diapositiva: 02:59)Si la comparación pasa, aceptamos el mensaje, a saber, la salida 1, de lo contrario la salida es 0. Ahora queremos analizar la seguridad de este esquema de firma RSA de avión. Y se podría decir que el siguiente argumento intuitivo debería demostrar que el esquema de firma de RSA es de hecho infalsificable o seguro. El argumento aquí es que si soy un adversario y si no sé el valor de la clave de la firma, es decir, el valor del secreto. Y si mi objetivo es forjar una firma en un mensaje de advertencia, en el que no he visto la firma en el pasado, entonces para forjar una firma básicamente tengo que calcular el valor de (de) mod, donde no sé el valor de. Y uno puede argumentar que esto no es más que una instancia del problema de RSA. Pero si asumo que mi problema RSA es difícil con respecto a esta función de Gen RSA, entonces puedo afirmar con seguridad que este esquema de firma RSA es seguro. Pero resulta que este argumento intuitivo no es correcto. Una de las razones es que la suposición RSA o el problema de RSA es difícil de resolver, sólo si se elige al azar a través de Zwet.RSA. La suposición RSA no dice nada de lo difícil o lo fácil que es calcular (por ejemplo) mod, sin saber el, para cualquier pertenencia a Zwetm. El segundo problema aquí en este argumento intuitivo es que la suposición RSA no dice o no garantiza nada acerca de un adversario acerca de la posibilidad de la computación (ver) mod, dado que el adversario podría haber visto el valor de varios mod para anyof su elección. Porque recuerda, cuando consideramos el juego de forgeability para el esquema de la firma, el adversario es permitido ver una firma de varios mensajes de su elección. Por lo tanto, si el adversario ha enviado un mensaje, habría visto el mod de la firma. Y es posible que haya visto el valor de mod para el número de mensajes polinomio. Y al ver el número polinomio de valores de la forma mod, donde es conocido por el adversario, el objetivo del adversario es llegar con una falsificación, a saber, (...) mod. Por lo tanto, la suposición de RSA no garantiza nada de lo difícil o lo fácil que es para un adversario presentar la falsificación, dado que ha visto la firma, a saber, la salida de la función RSA para varios m de su elección, en el pasado. (Consulte la hora de la diapositiva: 05:41) De hecho, resulta que para esta firma RSA simple, hay varias formas con las que el adversario podría presentar una falsificación. Así que veamos un ataque muy simple al que llamamos como ningún ataque de mensaje. Desde el nombre, podría parecer que no hay ningún mensaje en el que el adversario esté produciendo la falsificación. Pero ese no es el caso, sí hay un mensaje en el que el adversario está produciendo la firma falsificada. La razón por la que no se llama ataque de mensaje será claro para ti pronto. Así que la idea detrás de este ataque es que para forjar una firma válida, el adversario no siempre necesita trabajar en la dirección hacia adelante. Lo que quiero decir con esto es si tenemos en cuenta el espacio del mensaje y el espacio de la firma de esta firma RSA simple, ambos son el conjunto Zwed. Y la firma para un messagecan se produce por el mod de computación. Por lo tanto, si el objetivo del adversario es forjar una firma en un mensaje, tiene que calcular básicamente (por ejemplo) mod, esa es una de las maneras por las cuales el adversario puede producir una firma y esto yo llamo a la firma como productora caminando en la dirección hacia adelante. Pero resulta que el adversario podría llegar o forjar una firma caminando en la dirección hacia atrás también. Es decir, lo que puede hacer es, primero puede recoger una firma al azar o un elemento de grupo aleatorio y tratarlo como una firma. Y entonces puede preguntar en su mente que lo que podría ser el mensaje válido o potencial del espacio de mensajes, para lo cual la firma RSA habría sido la recogida de datos. Y es fácil ver que al escoger una firma aleatoria de firma, el mensaje correspondiente que habría producido la firma no es nada, sino (por ejemplo) mod. Porque si de hecho mi punto de vista es (por ejemplo) mod, entonces esto (el valor de la prueba) constituye una firma RSA válida según el algoritmo de verificación RSA. Y para computar a las personas, el adversario tiene todo a su disposición. Es decir, tiene el valor de y sabe el valor de y sabe el valor de y por lo tanto puede calcular fácilmente el valor. Por lo tanto, básicamente aquí es fácil ver que caminando en la dirección inversa, el adversario podría llegar con una falsificación válida incluso sin ningún acceso al oráculo de la firma. No pide la firma de ningún mensaje de su elección; solo escoge una firma y produce un mensaje correspondiente. Ahora, la razón por la que llamamos esto como un ataque de ningún mensaje es aquí la falsificación se produce caminando en la dirección hacia atrás, el adversario no tiene ningún mensaje para comenzar con para lo que quiere generar una falsificación. Pero aún así en lo que se refiere a la definición de falsificación, la forma en que el adversario ha calculado (el valor de las pruebas) es una falsificación válida. Se trata de una discusión diferente si este adversario que ha producido el adversario caminando en la dirección hacia atrás, tiene sentido en el contexto de la aplicación donde se usa el esquema de la firma subyacente. (Consulte Slide Time: 08:58)Ahora, lo que vamos a hacer después es que vamos a ver un ataque serio donde el adversario ahora tiene un mensaje concreto y veremos cómo usando la ayuda del oráculo de la firma, el adversario puede llegar a la falsificación en cualquier mensaje de la elección del adversario contra esta firma RSA simple. Por lo tanto, de nuevo recordar en el ataque de ningún mensaje, el adversario no tiene control en el mensaje, que obtuvo al caminar en la dirección hacia atrás. Pero un escenario de ataque más realista será donde el adversario tiene un mensaje concreto de su elección en el que quiere forjar la firma del firmante. Así que, permítanme demostrar una instanciación del ataque aquí. Así que según el experimento de falsificación de firmas, el retador habría lanzado el desafío al adversario, a saber, la clave de verificación. Y decir que el objetivo del adversario es forjar la firma en el mensaje. Lo que hace es, escoge 2 mensaje 1, 2 aleatoriamente del conjunto Zwizer, de tal manera que 1 n 2 = 2 =. ¿Y cómo puede escoger tales 1 y 2? Bueno, puede primero elegir al azar 1 del grupo de Zafrise que requiere cantidad polinómica de tiempo. Y luego puede establecer 2 = 1 − 1, que le dará el requerido 2, que de nuevo se puede calcular en cantidad polinómica de tiempo. Ahora, lo que el adversario puede preguntar es, puede pedir el acceso de oráculo de la firma para el mensaje 1 y 2. Namely le pide al retador que firme los mensajes 1 y 2. Así que básicamente este modelo de hecho que en el mundo real el objetivo del adversario es forjar la firma del firmante ’ s, básicamente ahora está influyendo en el firmante para firmar los mensajes 1 y 2. Por lo tanto, según las reglas del juego, el retador firma los mensajes 1 y 2 y da las firmas 1 y 2 respectivamente. Y ahora que el adversario combina estas 2 firmas. Es decir, establece el valor de = 1 n ° 2 y somete la falsificación (por ejemplo, por ejemplo). Y mi afirmación aquí es que la probabilidad de que el adversario aquí gane el juego es 1. Esto se debe a que 1 = (1) mod y 2 = (2) mod y, por lo tanto, a = (de forma) mod, que no es otra cosa que la firma RSA en el mensaje. Por lo tanto, ahora usted tiene un ataque concreto, usando la ayuda del oráculo de la firma, el adversario podría llegar con una firma en cualquier mensaje de su elección, lo que demuestra que esta firma RSA simple no es segura. (Consulte la hora de la diapositiva: 12:00) Por lo tanto, ahora la pregunta es ¿podemos diseñar un esquema de firma segura basado en la función RSA? Y la respuesta es sí, podemos construir lo que llamamos RSA full domain hash signature. Y en un nivel muy alto, esto podría parecer una instanciación del paradigma de hash y signo. Pero en realidad, no es una implementación completa o una instanciación de hash y paradigma de signo. La idea aquí es que de nuevo queremos transformar la serie de bits de mensaje que queremos firmar, antes de firmar utilizando la función RSA. Por lo tanto, lo que hacemos es el espacio de mensaje real que podemos firmar aquí o los otros mensajes que podemos firmar podrían ser una serie de bits arbitraria, los correlacionamos con los elementos de Zwidn aplicando alguna función de transformación, a la que llamo como función, y luego el mensaje transformado real se firma utilizando el esquema de firma RSA que habíamos discutido ahora, el esquema de firma RSA inseguro. Por lo tanto, el algoritmo de generación de claves para esta firma hash de dominio completo es el siguiente; ejecutamos el algoritmo Gen RSA, establecido (para ser la clave de firma y (para ser la clave de verificación. Y hacemos que la función de transformación sea conocida públicamente, lo que correlaciona las series de bits de longitud arbitraria con los elementos de Zwid.Y ahora para calcular la firma en el mensaje, que es una cadena de bits de longitud arbitraria, lo que hacemos es, primero computamos. Es decir, correlacionamos la cadena de bits con un elemento de Zwid.Y luego calculamos el valor de la función de RSA inversa en el, a saber, computar mod, que es nuestra firma. La verificación ocurre de manera canónica. A saber, si está recibiendo (y si desea verificarlo, lo que primero hacemos es calcular ′ = mod. Y aceptamos el mensaje, si y sólo si ′ =, que sería el caso si todo ha sucedido de una manera apropiada. Así que esa es la idea general de este hash de dominio completo RSA. Ahora, uno podría preguntarse que cuáles son las propiedades necesarias que requerimos de la transformación subyacente para asegurar que el esquema general es seguro. Subrayo aquí que esta firma hash de dominio completo no debe ser considerada como una instanciación del paradigma de hash y signo. Porque para la seguridad del paradigma de hash y signo, necesitamos que el esquema de firma de longitud fija sea seguro. Pero el esquema de firma de longitud fija, que en este caso es la firma RSA simple, ya lo hemos demostrado que no es seguro. Sin embargo, resulta que si hacemos algunos supuestos adecuados para esta función de transformación subyacente, entonces esta forma general de destrozar el mensaje primero, y luego firmar según lo inseguro o la firma RSA simple nos da un esquema de firma seguro general. Entonces, vamos a discutir qué son exactamente las propiedades de seguridad que requerimos de la función de transformación? Por lo tanto, la lista de las propiedades necesarias es la siguiente. Definitivamente, requerimos que la función de transformación debe ser resistente a la colisión, es decir, debe ser computacionalmente difícil para el adversario de poli tiempo o un atacante para encontrar un par de mensajes (, tal que. Porque si ese es el caso, eso significa, si el adversario podría llegar con tal par de mensajes, entonces puede primero pedir la firma en el mensaje y una firma en el mensaje será exactamente lo mismo que la firma en el mensaje, por lo que fácilmente podría llegar con una falsificación. El segundo requisito de la función de transformación es que debe evitar cualquier tipo de propiedades algebraicas multiplicativas o agradables que habíamos explotado en el ataque a la firma RSA simple. Eso significa, no debería suceder que debiéramos tener un triplete del para (1, 2) tal que 1) el 2). Porque si es posible para un adversario encontrar tales trillizos en la cantidad polinómica de tiempo, entonces lo que el adversario básicamente puede hacer es, puede pedir la firma en los mensajes 1 y 2 como por este hash de dominio completo. Y dado estos, puede fácilmente obtener una firma en el mensaje, que sería su falsificación. Así que nos gustaría que esta transformación debería ser tal que no debería tener tales propiedades algebraicas agradables. También necesitamos la propiedad un-wayness de esta función de transformación. Es decir, requerimos que dado un arbitrario de Zwate, debería ser difícil encontrar un mensaje, de tal manera que. Esto es para evitar el tipo de ataque de ningún tipo de mensaje. Resulta que definitivamente estas 3 propiedades son necesarias, pero no sabemos si la lista es exhaustiva o no, si necesitamos cualquier cuarta propiedad, quinta propiedad y así sucesivamente. Por lo tanto, ahora somos una especie de atorado. Lo que podemos hacer es, no nos importa si la lista es exhaustiva o no, si asumimos que la función de transformación se modela como un oráculo aleatorio y si usted está en el modelo de oráculo aleatorio, entonces podemos dar una prueba de seguridad completa para esta firma hash de dominio completo. Por lo tanto, usted puede ver que si asumimos que si usted está en el modelo de oráculo aleatorio, entonces definitivamente los 3 requisitos que hemos declarado serán satisfechos. Y la parte superior de que la prueba de que el esquema de la firma es seguro en el modelo de oráculo aleatorio se encarga del hecho de que no se puede lanzar ningún otro ataque. Por lo tanto, no voy a entrar en los detalles formales completos de la prueba de que, de hecho, el esquema de firma es seguro en el modelo de oráculo aleatorio. Si usted está interesado en ver la prueba formal completa, usted puede referirse al libro de Katz-Lindell o por el manuscrito de Boneh-Shoup. Así que eso me lleva al final de esta conferencia.