Loading
Apuntes
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 CryptographyDr. Ashish ChoudhuryDepartment of Computer ScienceInternational Institute of Information Technology – BangaloreConferencia – 45RSA AsunciónHola a todos, bienvenidos a esta conferencia.(Consulte el tiempo de la diapositiva: 00:42)Tan 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 la próxima conferencia, discutiremos otro Esquema de Cifrado Público Candidato basado en el problema duro diferente de , que llamamos hipótesis RSA, que nos llevará a otro esquema de cifrado público de , es decir, el Sistema de Cifrado Público RSA.(Consulte Tiempo de Slide: 00:58)Así que para entender la suposición RSA, primero intentemos entender el conjunto ZN*. Por lo tanto, ZN*básicamente es un conjunto de enteros 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 a el 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 para ver que si el módulo N es primo, el conjunto ZN* básicamente consiste en 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 de 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 la realización el módulo 10 de multiplicación de la operación para cualquier par de elementos de el conjunto, y ahora puede ver que todos los axiomas de los grupos están satisfechos y es por eso que es un grupo. Además, un hecho bien conocido de la teoría de números es que tenemos algoritmos de politime para calcular el inverso multiplicativo, que denoté 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 que el 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)Así que, 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. Esto significa que hay estos muchos elementos, a saber, p-1 veces q-1 elementos en el rango {1, …., N-1}, que será co-prime a su módulo N. Para verificar eso, tomemos un ejemplo, digamos N = 10, que 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. Esto significa que, si N es un primer p, entonces este φ (N) no es sino p-1, por lo que tenemos el módulo ap-1 p para ser 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 tiene algún elemento perteneciente al conjunto ZN*, entonces ax módulo N es exactamente el mismo que el módulo ax φ (N) módulo N. Es decir, en el exponente 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 axcomo 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 de tendrá ax módulo φ (N), y todo en el módulo base N. Ahora, sabemos que a φ (N) módulo N es 1, que significa que cada uno de estos lotes, tiene un φ (N) módulo N completo, va para darle la respuesta 1. Por lo tanto, todos estos lotes te van a dar la respuesta 1, 1, 1, 1 y 1 multiplicado por 1 te va a dar 1. Por lo tanto, finalmente queda con el último lote, que tiene ax módulo φ (N). Por lo tanto, 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 es se define de la siguiente manera. Imagine, se le da un exponente e, que es mayor que 2, de modo 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 encontrar el inverso multiplicativo de ese e módulo φ (N).En general, si usted tiene 2 números, diga a y b, de tal manera que GCD de a y b es 1, eso significa, un y b son co-primos entre sí, entonces siempre se puede encontrar el inverso multiplicativo de un módulo b de . 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), utilizando el algoritmo Euclides ampliado, puedo encontrar d donde e y d constituyen sus inversores multiplicativos mutuos.Eso 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 xey hacemos mod N. Por otro lado, la función de dirección inversa es básicamente una función de d, es decir, fd (y), y esta función es básicamente si quiero calcular fd (y), computará yd, y luego realizar mod N.reclamo aquí que la función fd es la inversa de la función fe y viceversa. Por lo tanto, para eso considera cualquier x arbitrario aquí, perteneciente a ZN*, y decir que lo mapeo a y, según la función fe,así que mi y no es nada más que xe, y ahora vamos a dejar que los ’ s vean lo que obtenemos invirtiendo este valor y como por la función fd. Si reviso esta y como por fd, entonces obtengo xe mod N, y luego elevo todo a la potencia d mod N.Así que puedo tomar el mod en general fuera, y obtengo que esto es lo mismo que xetimes 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 entre sí.Así que, en el exponente, es e veces d módulo φ (N) se reduce a 1, por lo tanto, obtengo que estemódulo N 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 le da x de tal manera que el efecto de mod no sucede en absoluto. Así que esto demuestra que su función fd y feson mutuamente inversas entre sí.También demostro aquí ahora que mi función fe (x) es una bijección, y eso significa que es una de uno a uno en el mapeo. Para eso, consideremos un par arbitrario de entradas x1, x2, del conjunto ZN*, y decir las imágenes resultantes de x1 y x2 según la función fe, son y1 y y2. Ahora, si y1 y y2 son iguales, es decir, x1e módulo N, es igual que x2e módulo N, es decir, si elevo ambos lados al exponente d, obtengo x1ed módulo N es el mismo que el módulo x2ed N.Esto básicamente significa que x1 es igual a x2, porque x1ed módulo N, no es más que x1 y x2edel 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 yo en general obtengo que mi función fe es una permutación aquí.(Referir Slide Time: 10:32)Ahora, vamos a discutir 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 esta suposición de es que, si se le da el producto de dos grandes números primos arbitrarios, resulta que es 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 de , si esos números primos son elegidos arbitrariamente. Entonces, esta intuición o la dureza de este problema va a ser formalizada por un experimento, y para ese experimento de , 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 conocidos algoritmos de para escoger números primos aleatorios.No voy a entrar en los detalles exactos de cómo escoges exactamente esos dos números primos de , en el tiempo de poli (n). Puedes consultar el libro de Katz y Lindell para el algoritmo exacto de . Ahora, una vez que se han elegido 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 de 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 a 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 de si de hecho, el par p ’, q ’ es exactamente el mismo que la factorización principal de su módulo N de , y decimos que la suposición de factoring se mantiene con respecto a nuestro algoritmo GenModulus, si por cada adversario de politiempo, la probabilidad de que el adversario pudiera venir con la factorización correcta del módulo N, está limitada por alguna función insignificante de . Tenga en cuenta que, siempre hay una estrategia de adivinación por parte de un adversario, puede adivinar algunos p ’ y q ’, y con una probabilidad distinta de cero, de hecho puede con la factorización correcta de N. (Consultar tiempo de la diapositiva: 13:00)Lo que queremos es básicamente que ningún adversario de politiempo debe 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 de One-Way candidata de , eso significa que si le doy el producto de dos números primos de grandes arbitrarios y le reto a que se le presente la factorización, entonces eso parece una función de One-Way candidata de . 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. Por lo tanto, para conseguirlo, introducimos un problema relacionado con , al que llamamos como un problema RSA, cuya dificultad está relacionada con la dureza del problema de factorización de . Por lo tanto, este problema de RSA se describe con respecto a otro algoritmo de generación de parámetros de , al que llamamos como GenRSA.Por lo tanto, lo que hace el algoritmo GenRSA es, primero ejecuta el algoritmo GenModulus y recoge primos aleatorios p y q de 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 selecciona 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 la inversa de multiplicative 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 de público N y el exponente público e, y el elemento aleatorio y del conjunto de ZN*, entonces el reto para usted es calcular la raíz eth de y módulo N sin saber realmente el valor real de de d o sin conocer la factorización principal de N.Me hace hincapié en que el reto es calcular el módulo de 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 reto aquí es calcular el valor de la raíz eth del módulo y aleatorio N, que es formalizado por este experimento de 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 está preguntándose que cómo recoger un elemento aleatorio del conjunto ZN* es posible en el tiempo de poli (n) , bien es posible, puede ver el libro de referencia de Katz y Lindell donde se da el algoritmo de de cómo elegir elementos aleatorios.Ahora el desafío para el adversario es averiguar la raíz de este azar y simplemente 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 del 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 de forma aleatoria y módulo N, es decir, si xemódulo N es y. Decimos que la suposición RSA se mantiene con respecto a este algoritmo GenRSA, si para cada algoritmo de politime que participa en este experimento, la probabilidad de que pueda venir con la raíz eth correcta de un y aleatorio es limitada por alguna probabilidad insignificante.(Consulte el tiempo de la diapositiva: 16:23)Ahora, deje que los ’ intenten comparar la suposición RSA y la suposición de factoring, porque en un nivel alto de , podrían parecer similares a usted. Por lo tanto, en su lado izquierdo tiene el experimento de factoring donde el desafío para el adversario es llegar a los factores principales del módulo público de N. En el lado derecho, usted tiene el experimento de modelado del problema RSA donde el adversario ahora se le da alguna información adicional como parte de su desafío, es decir, 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 azar y módulo N.Resulta que podemos demostrar que si se mantiene la suposición RSA, entonces la suposición de factoring también se mantiene y esto puede ser probado por contrapositive, a saber, si usted asume que la factorización es computacionalmente fácil, eso significa que es posible que un adversario politime presente una factorización p, q de un módulo N. Entonces, una vez que factorice su módulo N en su factorización de p y q, entonces usted puede calcular fácilmente φ (N) porque φ (N) no es nada más que p-1 veces q-1.Y si φ (N) es computable en politiempo y de todos modos se le da a usted, entonces ejecutando el algoritmo Euclides extendido de , 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 más que el módulo de yd N. Eso significa, esta implicación es realmente cierto. Por otro lado, deje que los ’ s intenten considerar la relación entre el Supuesto 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 puede 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 forma de resolver eficazmente el problema de RSA sin tener que factorizar el módulo. Debido a que una de las formas de resolver el problema de RSA puede ser factorizar la N y luego una vez que se conoce la factorización, aparece con el valor d y así sucesivamente, pero no es necesario que la única manera de resolver el problema de RSA. Puede haber otras formas de calcular para resolver el problema de RSA en una cantidad de tiempo polinómica sin factorizar realmente el módulo, y en ese sentido , hacer que la suposición de RSA sea una suposición muy fuerte en comparación con la toma de la suposición de la factorización de porque es difícil, el problema de factoring parece un problema más , más difícil que resolver el problema de RSA.(Consulte el tiempo de la diapositiva: 19:05)Así que, por último, déjenos discutir cómo exactamente puede utilizar su RSA Permutation como un Trapdoor Permutación porque en nuestra próxima conferencia, vamos a tratar nuestra RSA Permutación como una permutación deTrapdoor, y veremos que cómo podemos formular una instanciación del esquema de cifrado de público a partir de esta Permutación RSA. Por lo tanto, para eso recordemos la definición de Permutación Trapdoor de One-Way .Por lo tanto, es una función de set x al set x, que es fácil de calcular para cualquier entrada del dominio , pero lo difícil de invertir de cualquier entrada aleatoria del codominio, hasta y a menos que se le dé información especial de trapdoor. Por lo tanto, esto se formaliza diciendo que más formalmente tenemos esquema de permutación de trapdoor sobre el set x, que consiste en un algoritmo de Generación de Key, una función de trapdoor f, y su inversa donde el algoritmo de generación de parámetros dará salida a un parámetro público y un parámetro secreto, la función f es básicamente, una función por clave de , tecleada por la clave pública pk y toma valor del set x y le da una salida del conjunto x y es un algoritmo determinista y el correspondiente algoritmo inverso de es operado por una clave secreta, por lo que su clave secreta está actuando básicamente como un información de trapdoor aquí y utilizando esta información de trapdoor, puede invertir correctamente cualquier y desde el codominio de , a saber, el conjunto x. La propiedad de corrección que requerimos del esquema de permutación de trapdoor es que para cada par de parámetros generados por el algoritmo de generación, para cada x de su dominio, si calcula el valor de fpk (x), y dice obtener la salida y, y ahora si invierte eso y con la clave secreta sk, debe recuperar la x, y un segundo requisito de es el requisito de una forma de ser, que básicamente afirma que su función f debe comportarse como una función unidireccional, incluso si un adversario conoce el valor del parámetro pk del public .(Consulte el tiempo de la diapositiva: 21:09)Así que, veamos cómo podemos visualizar la permutación RSA del conjunto ZN* a ZN* como una instanciación de de la Permutación Trapdoor. Por lo tanto, básicamente RSA Trapdoor Permutation consta dede tres algoritmos, el algoritmo de generación de parámetros no es más que el algoritmo GenRSA, es decir, selecciona de forma uniforme números primos de n-bit aleatorios, p y q, calcula el módulo N, y luego calcula el tamaño de ZN*, es decir, φ (N).Recoge el exponente público e, de tal forma que e es co-prime a φ (N). Puesto que e es co-prime a φ (N), ejecutando el algoritmo Euclides ampliado, el inverso multiplicativo de e módulo φ (N) es calculado y los parámetros públicos son N, e, y los parámetros secretos son N, d. La función de dirección de avance , a saber, la función fRSA, y que funciona con la clave pública N, e es como sigue . Para calcular el valor de esta función fRSA en una entrada x básicamente se acaba de producir el módulo de salida N, y el módulo N de xe se puede calcular en el tiempo de poli (n). Veremos más adelante cómo exactamente esta exponenciación del grupo se puede calcular en polinomio en cantidad de tiempo. Por otro lado, si tiene una trampa a saber, un parámetro secreto n, d y si desea invertir cualquier dado y del conjunto ZN*. Básicamente tiene que calcular el módulo de referencia N. Así que, vamos a ver si esta RSA Trapdoor Permutación cumple de hecho el requisito de un esquema de permutación de Trapdoor genérico. Así que el requisito de corrección establece que, debe mantener ese xeseguido de elevarlo a d módulo N, debería darme mi x y ya hemos demostrado que de hecho es el caso cuando demostramos que la función f y la función de RSA inversa son inversas entre sí.Por otro lado, la propiedad One-Wayness de esta permutación RSA, requiere que cualquiera que sepa sólo el parámetro público, es decir, N, e, pero no sepa la información de trapdoor de , diga d, sin el conocimiento de la información de trapdoor, es difícil calcular la raíz eth de cualquier azar y, y resulta que de hecho ese es el caso si el supuesto RSA de se mantiene con respecto al algoritmo de generación de parámetros que significa.Si, de hecho, el problema de RSA es difícil de resolver con respecto a este algoritmo de generación de parámetros de RSA , entonces esta llamada permutación RSA se puede ver como una instanciación de la Permutación de Trapdoor. Por lo tanto, recordemos que en una de nuestras conferencias anteriores, habíamos visto a que de manera genérica podemos convertir Trapdoor Permutation Scheme en un protocolo de acuerdo clave con una noción de secreto débil.Y ahora si instancias Permutación de Trapdoor por una Permutación RSA Trapdoor, entonces por usando la Permutación RSA Trapdoor, en realidad obtenemos un protocolo de intercambio de claves RSA, que te da una noción de secreto débil, es decir, la clave resultante será conocida por el remitente de y el receptor, y el adversario no conocerá la clave completa en su totalidad. En la otra mano la función de registro discreta que habíamos discutido anteriormente, no se puede ver como una instanciación de de la Permutación Trapdoor. Porque sabemos que la función de dirección hacia adelante, es decir, decir gxse puede tratar como su función de dirección de avance de , pero no sabemos cuál debe ser la correspondiente información de trapdoor con la que podemos utilizar e invertir esta función. Eso es una especie de gran desafío que está ahí. Por otro lado, en el contexto de la permutación RSA, tenemos el correspondiente trapecito asociado, a saber, el exponente d, que es el inverso multiplicativo de e, módulo φ (N). Así que eso me lleva al final de esta conferencia. En esta conferencia, hemos introducido la suposición RSA , y hemos visto la relación entre el problema RSA y el problema de factoring . Gracias.