Loading
Apuntes
Study Reminders
Support
Text Version

RSA Public-Key Cryptoystem

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

    +

Fundamentos de Criptografía Dr. Ashish Choudhury Departamento de Informática Instituto Internacional de Tecnología de la Información – Conferencia de Bangalore – 45 RSA Asunción Hola a todos, bienvenidos a esta conferencia. (Consultar tiempo de la diapositiva: 00:42) Así que sólo para recapitular en la última conferencia, hemos visto el Programa de Cifrado Público de Candidatos, el Esquema de Cifrado Público seguro de CPA, principalmente el esquema de encriptación de El Gamal. En esta conferencia y en la siguiente conferencia, discutiremos otro Programa de Cifrado Público Candidato basado en el diferente problema duro, que llamamos hipótesis RSA, que nos llevará a otro esquema de encriptación pública, es decir, el Sistema de Cifrado Público RSA. (Consulte el apartado Tiempo de la diapositiva: 00 :58) Para entender la suposición RSA, primero intentemos entender el conjunto ZN*. Por lo tanto, ZN* básicamente es un conjunto de números enteros de módulo N, que son co-prime al módulo N, es decir, ZN* es la colección de todos los elementos b en el rango {1, …, N-1} de tal manera que el elemento b es co-prime al módulo N. Namely, su GCD es 1. Por ejemplo, el conjunto Z10 * no es más que los elementos 1,3,7 y 9. Debido a que todos estos elementos 1, 3, 7 y 9, son co-prime al módulo 10, y es fácil ver que si el módulo N es primo, entonces el conjunto ZN* básicamente consiste de todos los elementos 1 a N-1. Así que, un hecho bien conocido de la teoría de números cuya prueba me estoy saltando es que el conjunto ZN* junto con el módulo de multiplicación de operación N constituye un grupo y satisface todos los axiomas del grupo. Así que, por ejemplo, he dibujado la matriz para los elementos en Z10 *, es decir, 1, 3, 7 y 9, y el resultado de realizar el módulo de multiplicación de la operación 10 para cualquier par de elementos del conjunto, y ahora usted puede ver que todos los axiomas de los grupos están satisfechos y es por eso que este es un grupo. Por otra parte, un hecho bien conocido de la teoría de números es que tenemos algoritmos de politiempo para calcular el inverso multiplicativo, que denotan por, a-1, para cualquier elemento a en el conjunto ZN*. Y hay un algoritmo bien conocido para eso, que llamamos como el algoritmo GCD de Euclides Ampliados, que vamos a discutir en una de nuestras conferencias posteriores, y el tiempo de ejecución de ese algoritmo es polinomio en el número de bits que necesitamos para representar el módulo N. (Consulte el tiempo de la diapositiva: 02 :47) Por lo tanto, vamos a discutir la función Totient de Euler ’ s, φ función. Así que el Euler ’ s Totient Function, que es el denotado por el símbolo φ (N) es básicamente la cardinalidad del conjunto ZN*, a saber, es el número de elementos en el conjunto 1 a N-1, que son co-prime a su módulo N. Algunos de los hechos conocidos otra vez prestados de la teoría de números son los siguientes. Si N es un primer p, el valor de φ (p) no es más que p -1. Porque hay exactamente p-1 elementos, que son co-prime a p. Por otro lado, si n es el producto de 2 primes distintos, p y q, entonces φ (N) no es más que p-1 veces q-1. Eso significa que hay estos muchos elementos, es decir p-1 veces q-1 elementos en el rango {1, …., N-1}, que será co-prime a su módulo N. Para verificar que, tomemos un ejemplo, digamos N = 10, que usted puede escribir como el producto de 2 y 5, donde 2 y 5 son primos. Así que su p es 2 y su q es 5, entonces sabemos que hay 4 elementos en el set Z10 *, por lo que φ (10) debe ser 4, y 4 no es más que p-1, es decir, 2-1 multiplicado por q-1, que es 5-1, y finalmente otra propiedad interesante que vamos a utilizar de la teoría de números es que, para cualquier elemento a en el ZN*, un φ (N) módulo N es 1. Eso significa que, si N es un primer p, entonces este φ (N) no es otra cosa que p-1, por lo que conseguimos que el módulo de ap-1 sea 1. Esta propiedad o este resultado también se llama como Fermat ’ s Little Theorem, y también obtenemos debido a este hecho, el corolario que si usted tiene algún elemento que pertenece al conjunto ZN*, entonces ax módulo N es exactamente lo mismo que el módulo ax φ (N) módulo N. Eso significa, en el exponente se puede reducir el exponente x a x módulo φ (N). Por lo tanto, la razón de este problema corolario es que, si su x es de todos modos menos que φ (N), tanto L.H.S. como R.H.S. son los mismos, pero si su x es más que φ (N) entonces para calcular el módulo de ax φ (N), lo que puede hacer es reescribir ax como varios lotes de un φ (N) con φ (N) en el exponente. a φ (N) en función de la relación entre x y φ (N), y el último lote tendrá ax módulo φ (N), y todo en el módulo base N. Ahora, sabemos que un φ (N) módulo N es 1, que significa que cada uno de estos lotes, tiene un φ (N) módulo N completo, le va a dar la respuesta 1. Por lo tanto, todos estos lotes te van a dar la respuesta 1, 1, 1, 1 y 1 multiplicada por 1 te va a dar 1. Por lo tanto, finalmente queda con el último lote, que tiene el módulo ax φ (N). Así que, así es como obtenemos este corolario. (Consulte el tiempo de la diapositiva: 06:03) Así que, con todas estas matemáticas en su lugar, ahora vamos a tratar de entender la permutación RSA. Así que esta permutación RSA es una correlación del conjunto ZN* a ZN*, por lo que la forma en que esta permutación se define de la siguiente manera. Imagine, se le da un exponente e, que es mayor que 2, de manera que el exponente e es co-prime a su valor φ (N). Por lo tanto, subrayo que está co-preparado para φ (N), no para N. Ahora, un hecho bien conocido de la teoría de números es que si usted tiene una e, que es co-prime a φ (N), entonces usted puede averiguar la inversa multiplicativa de ese e módulo φ (N). En general, si usted tiene 2 números, decir a y b, tales que GCD de a y b es 1, que significa, a y b son co-prime entre sí, entonces siempre se puede encontrar el inverso multiplicativo de un módulo b. Por lo tanto, mi módulo en este caso es φ (N), porque e es co-prime a φ (N), y si e es co prime a φ (N), mediante el uso del algoritmo Euclid ampliado, puedo encontrar d donde e y d constituyen sus inversos multiplicativos mutuos. Esto significa, e veces d módulo φ (N), y d veces e módulo φ (N) es 1. Ahora, la permutación RSA se define de la siguiente manera. Para ir en la dirección adelante, la función es fe, y para calcular el valor de fe (x) donde x es un miembro de ZN*, básicamente calculamos xe y do mod N. Por otro lado, la función de dirección inversa es básicamente una función de d, a saber, fd (y), y esta función es básicamente si quiero calcular fd (y), computará yd, y luego realizar mod N. I afirma aquí que la función fd es la inversa de la función fe y viceversa. Por lo tanto, para eso considerar cualquier x arbitrario aquí, perteneciente a ZN*, y decir que lo mapa a y, según la función fe, por lo que mi y no es nada más que xe, y ahora vamos a ver lo que obtenemos al invertir este valor y según la función fd. Si reviso esta y como por fd, entonces obtengo xe mod N, y entonces todo elevo a la potencia d mod N. Así que puedo tomar el mod global fuera, y obtengo que esto es lo mismo que xe veces d módulo N, y usando el corolario que hemos declarado en la última diapositiva, el módulo N en el exponente, puedo reducir este exponente e*d a e*d módulo φ (N). Sé que e*d módulo φ (N), que está ahí en el exponente, me da el valor 1, porque he elegido e y d de tal manera que son inversos multiplicativos el uno del otro. Por lo tanto, en el exponente, es e veces d módulo φ (N) reduce a 1, así que por lo tanto obtuve que este módulo N por fax no es más que x módulo N, y desde que he elegido mi x para pertenecer al conjunto ZN*. Eso significa que x es de todos modos menos que N, y si x es menor que N, entonces x módulo N te da x de tal manera que el efecto de mod no ocurre en absoluto. Así que esto demuestra que su función fd y fe son mutuamente inversas entre sí. También demostro aquí ahora que mi función fe (x) es una bijección, y eso significa, es una correlación uno a uno. Para eso, consideremos un par arbitrario de entradas x1, x2, del conjunto ZN*, y digamos las imágenes resultantes de x1 y x2 según la función fe, son y1 y y2. Ahora, si y1 y y2 son los mismos, eso significa, x1e módulo N, es igual que x2e módulo N, eso significa, si elevo ambos lados al exponente d, obtengo x1 ed módulo N es igual que el módulo x2 ed N. Esto básicamente significa que x1 es igual a x2, porque x1 ed módulo N, no es más que x1 y x2 ed módulo N no es más que x2. Así que eso significa, si tomo un arbitrario x1, x2 mapping a la misma y, entonces básicamente terminaré mostrando que x1 es igual a x2, y por lo tanto general obtengo que mi función fe es una permutación aquí. (Consultar Tiempo de Slide: 10 :32) Ahora, discutamos la suposición resultante, que estará relacionada con la suposición RSA, que finalmente discutiremos. Esto se llama la suposición de factoring, y la intuición detrás de este supuesto es que, si se le da el producto de dos grandes números primos arbitrarios, resulta que encontrar los factores principales es de hecho una tarea difícil. Este es un problema muy conocido y bien estudiado estudiado a lo largo de varios siglos. Y hasta ahora, no tenemos algoritmos de politiempo eficientes para factorizar un producto de dos números primos arbitrarios, si esos números primos son elegidos arbitrariamente. Entonces, esta intuición o la dureza de este problema se va a formalizar por un experimento, y para ese experimento, primero definamos un algoritmo, al que llamamos como algoritmo GenModulus. Básicamente escoge dos números primos de n-bit aleatorios, digamos p y q, y hay algoritmos conocidos para escoger números primos aleatorios. No voy a entrar en los detalles exactos de cómo elegir exactamente esos dos números primos al azar, en el tiempo de poli (n). Puedes consultar el libro de Katz y Lindell para el algoritmo exacto. Ahora, una vez que se eligen p y q, se calcula el módulo, es decir N, que es el producto p y q. Ahora, el Supuesto Factoring, con respecto al algoritmo GenModulus, se modela como un experimento, al que llamamos como Factor Experimento, y las reglas de ese experimento son las siguientes. El retador ejecuta el algoritmo GenModulus, genera el parámetro N, p, y q, y el desafío se lanza al adversario, es decir, N, y el desafío para el adversario es llegar con su factorización principal, a saber, p y q. Por lo tanto, envía un par de números, p ’ y q ’, y decimos que la salida del experimento es 1, es decir, el adversario ha ganado el experimento si de hecho, el par p ’, q ’ es exactamente lo mismo que la factorización principal de su módulo N, y decimos que el supuesto de factoring se mantiene con respecto a nuestro algoritmo GenModulus, si por cada adversario de politiempo, la probabilidad de que el adversario podría llegar con la factorización correcta del módulo N, está limitada por una función insignificante. Fíjate que, siempre hay una estrategia de adivinación por parte de un adversario, puede adivinar algún p ’ y q ’, y con probabilidad no cero, puede de hecho con la factorización correcta de N. (Consultar Tiempo de Slide: 13:00) Lo que queremos es básicamente que ningún adversario de politiempo debería ser capaz de hacer nada mejor que eso. Esa es básicamente la intuición de este experimento. Ahora, finalmente vamos a ver la suposición RSA aquí. Por lo tanto, resulta que Factoring Asunción, a pesar de que parece una función candidata de One-Way, eso significa que si le doy el producto de dos números primos grandes arbitrarios y le reto a que se le presente la factorización, entonces que parece una función candidata de una sola manera. Pero sólo en base a esta candidata a la función de una sola manera, no podemos obtener directamente un práctico criptosistema de clave pública. Así que, para sortear eso, introducimos un problema relacionado, al que llamamos como un problema de RSA, cuya dificultad está relacionada con la dureza del problema de factoring. Por lo tanto, este problema RSA se describe con respecto a otro algoritmo de generación de parámetros, que llamamos GenRSA. Por lo tanto, lo que hace el algoritmo GenRSA es, primero ejecuta el algoritmo GenModulus y recoger los primos aleatorios p y q del tamaño n-bits cada uno, y los multiples para obtener el módulo N, y ahora calcula el valor φ (N) y es computable porque φ (N) no es más que el producto de p-1 y q-1. A continuación, este algoritmo GenRSA elige un exponente e tal que e es relativamente primo o co-prime a φ (N). Y puesto que e es co-prime a φ (N), ejecutando el algoritmo Extended Euclid ’ s, se puede calcular el inverso multiplicativo d de e módulo φ (N). En general, este algoritmo GenRSA ahora genera N, p, q, e y d. Intuitivamente, el problema de RSA es, si se le da sólo un módulo público N y el exponente público e, y el elemento aleatorio y de la ZN* set, entonces el reto para usted es calcular la raíz eth de y módulo N sin saber realmente el valor real de d o sin saber la factorización principal de N. I estrés que el reto es calcular el módulo raíz N porque si sólo le reto a calcular la raíz eth sin módulo N, eso es muy fácil de hacer eso. El desafío aquí es calcular el valor de la raíz eth del aleatorio y módulo N, que es formalizado por este experimento que yo llamo como experimento RSA-inv. El experimento es el siguiente, el retador ejecuta el algoritmo GenRSA para generar los parámetros N, p, q, e, d son elegidos al azar del conjunto ZN*. Una vez más, si usted se está preguntando que cómo recoger un elemento al azar del conjunto ZN* es posible en el tiempo de poli (n), bien es posible, usted puede ver el libro de referencia por Katz y Lindell donde el algoritmo se da de cómo elegir elementos aleatorios. Ahora el desafío para el adversario es encontrar la raíz de este azar y justo basado en el conocimiento del módulo público N y el exponente público e. Por lo tanto, tiene que dar salida a un elemento de grupo decir x y decimos que el adversario ha ganado el experimento o la salida del experimento es 1, si y sólo si, x es de hecho la raíz eth del azar y módulo N, es decir, si el módulo N es y. Decimos que la suposición RSA se mantiene con respecto a este algoritmo GenRSA, si por cada algoritmo de politiempo que participa en este experimento, la probabilidad de que pueda llegar a la raíz eth correcta de una y aleatoria es limitada por una probabilidad insignificante. (Consulte el apartado Tiempo de la diapositiva: 16 :23) Ahora, deje que los ’ intenten comparar la suposición RSA y la Asunción de Factoring, porque en un nivel alto, podrían parecer similares a usted. Así que, en su lado izquierdo usted tiene el experimento de factoring donde el desafío para el adversario es llegar con los factores principales del módulo público N. En el lado derecho, usted tiene el experimento de modelado del problema de RSA donde el adversario ahora se le da alguna información adicional como parte de su desafío, a saber, se le da el exponente público e y el azar y del conjunto ZN*, y su objetivo es llegar a la raíz de la raíz de azar y módulo N. Resulta que podemos demostrar que si la asunción de RSA, entonces el supuesto de factoring también se mantiene y esto puede ser demostrado por contrapositivo, a saber, si usted asume que el factoring es computacionalmente fácil, eso significa que es posible que un adversario de politiempo se presente con una factorización principal p, q de un módulo N. Entonces, una vez que factorice su módulo N en su factorización principal de p y q, entonces usted puede calcular fácilmente φ (N) porque φ (N) no es más que p-1 veces q-1. Y si φ (N) es computable en el politiempo y de todos modos se le da a usted, entonces ejecutando el algoritmo Euclides extendido, usted puede calcular el inverso multiplicativo de e, es decir, d, y una vez que computa d, la raíz eth de y no es nada más que el módulo. Por otro lado, deje que los ’ s intenten considerar la relación entre el Supuesto de Factoring y RSA, en el sentido, podemos decir que si Factoring Asunción se mantiene, entonces la suposición RSA se mantiene y no tenemos ninguna respuesta para esto. Esto significa que no podemos probar que si la asunción de RSA no se mantiene y el supuesto de factoring no se mantiene. Es un gran problema abierto porque puede haber una manera de resolver eficazmente el problema de RSA sin tener en cuenta su módulo. Pero podemos tener algún tipo de tradeoff y para la mayoría de las muchas instanciación práctica, este es un clic común, que se utiliza para hacer el proceso de cifrado rápido. Ahora, supongamos que estamos utilizando una instanciación de RSA, donde hemos establecido e para ser 3, y decir que estamos considerando una aplicación en la que los mensajes subyacentes m ∈ ZN*, pero la magnitud de m es estrictamente inferior a la raíz eth del módulo N. Y si se está preguntando que qué tipo de aplicaciones encuentra este tipo de m, si más adelante veremos el cifrado RSA híbrido. A continuación, el tamaño del módulo que usamos normalmente es de tamaño 1024 bits, y el mensaje que nos gustaría cifrar al cifrado RSA híbrido será aproximadamente una serie de bits aleatoria de 300 bits uniformemente y vamos a establecer e para ser 3. Si ese es el caso, entonces el texto de cifrado será m3 módulo N. Pero ya que mi magnitud de m es estrictamente inferior a la raíz de cubo de m, me o m3 módulo N será equivalente al cubo entero y el efecto del mod N no tendrá lugar en absoluto. Y si el adversario es consciente del hecho de que estamos utilizando una aplicación con texto plano subyacente, es de magnitud es estrictamente inferior a la raíz de cubo del módulo N, entonces también será consciente de que el m subyacente, que ha sido cifrado. Su cubo está realmente contenido en el texto de cifrado c, a saber, el cubo entero no el cubo de módulo, y es muy fácil recuperar el desconocido m subyacente de la c con sólo encontrar la raíz de cubo entero del texto de cifrado c, que se puede calcular en poli del tamaño de módulo N cantidad de cálculo. Así que esa es nuestra primera clase de ataque. (Ver Diapositiva: 14 :14) Podemos tener muchos otros tipos de ataques posibles en Plain RSA Cipher, así que imagine por el momento que estamos considerando una aplicación donde el mismo mensaje necesita ser encriptado y enviado a múltiples receptores. Así que, imagínate si decimos que tenemos 3 receptores, el receptor 1, 2, y 3 cada uno de ellos tiene su propio módulo N1, N2 y N3 respectivamente. Pero cada uno de ellos está usando un mismo exponente público decir 3, y por supuesto un exponente de descifrado diferente d1, d2, y d3 donde d1 es el inverso multiplicativo de 3 módulo N1, d2 es el inverso multiplicativo de 3 módulo N2 y así sucesivamente. Por lo tanto, la clave pública, que está disponible en el dominio público son las respectivas claves públicas de los 3 receptores e imagina que tenemos un remitente, que tiene un mensaje aleatorio m ∈ ZN1 *, así como ZN2 *, así como ZN3 * elegidos al azar y dicen que quiere cifrar y enviar un mismo mensaje a los 3 receptores. Así, computará c1 que será el m3 módulo N1, c2 que será el m3 módulo N2 y así sucesivamente. Ahora, suponga que este módulo N1, N2 y N3, son primos entre pares. Si no se supone, por ejemplo, el GCD de Ni y Nj no es 1, no son coprime entre sí. Eso significa que existe un factor común de Ni y Nj, entonces usando ese factor común, es computacionalmente fácil de factorizar ya sea el módulo Ni o Nj y decir por ejemplo si Ni es factorizable, y ya que ei es también conocido públicamente y si conocemos los factores de Ni ’ s, podemos calcular el valor de i). Y una vez que sabemos i) y ei, podemos calcular el valor de di en cantidad polinómica de tiempo. Si di es computable, entonces cualquier encriptamiento que sea destinado al receptor de la ith puede ser descifrado por el adversario. Por lo tanto, es seguro asumir por el momento ese par sabio, todos los módulos N1, N2, y N3, que son co-primos entre sí. Ahora, déjenme definir un módulo N* más grande, que es el producto de todos los tres módulos aquí, es decir, N1, N2 y N3, y como mi texto sin formato subyacente m, que es el remitente ha cifrado ∈ ZN1 *, así como ZN2 *, así como ZN3 *. Esto significa que m es estrictamente inferior a N1, es estrictamente inferior a N2, es estrictamente inferior a N3. Eso significa que el número entero m3 será estrictamente menor que el módulo mayor N* y ahora lo que puedo hacer es que mi módulo N1, N2, y N2, N3 y N1, N3 son co-primos entre sí. Puedo invocar un resultado muy agradable de la Teoría del Número, a la que llamamos como el Teorema Del Resto Chino, que dice que si su módulo individual N1, N2 y N3 son primos. Entonces es posible calcular el valor entero m3 en cantidad polinómica de tiempo, polinomio en el tamaño del módulo N1, N2 y N3 respectivo de tal manera que el m3 recuperado básicamente satisface el sistema de las siguientes ecuaciones modulares. Por lo tanto, se le da el valor c1, que es un entero m3 módulo N1, donde m3 no se conoce, y se le da c2, que es el mismo desconocido m3 módulo N2 y se le da el valor de c3, que es el mismo desconocido m3 módulo N3, y si su N1, N2, y N3, el módulo respectivo que son co-prime entre sí. Entonces lo que básicamente dice el Teorema Del Resto Chino es que es posible recuperar ese m3 desconocido en la cantidad polinómica de la computación. Entonces, aplicando el teorema del resto chino, un adversario que tiene eavesdrop estos tres textos de cifrado c1, c2, c3, puede aplicar el teorema del resto chino, y recuperar el m3 desconocido. Una vez que el entero desconocido m3 se recupera, puede encontrar el m exacto. Por lo tanto, de nuevo este es otro ataque, que es posible en la Plain RSA Cipher incluso si asumimos que un mensaje del remitente es el mensaje m ∈ ZN* establecido. Resulta que podría haber varios otros posibles ataques, que se pueden lanzar en el proceso de cifrado de Plain RSA. (Consulte el apartado Tiempo de la diapositiva: 18 :48) Por lo tanto, esto nos lleva al concepto de lo que llamamos como un criptosistema de clave pública RSA acolchado y básicamente la idea general aquí es que, hemos visto ya que el proceso de cifrado de RSA es un proceso de cifrado determinista. No hay una aleatoriedad interna oculta y si no hay aleatoriedad interna, entonces nunca podremos esperar alcanzar la seguridad de la CPA. Por lo tanto, la idea detrás del proceso de cifrado RSA acolchado es que tratamos de añadir algunas series de bits al azar a los bits de texto plano, que queremos cifrar y convertir todo en un elemento de grupo en el conjunto ZN*, y luego aplicamos la función RSA para el cifrado. Por otro lado, el final del descifrado, vamos a cortar las cadenas de bits al azar, que hemos añadido a las cadenas de bits sin formato antes del cifrado y entonces ese será el texto sin formato recuperado.