Loading
Apuntes
Study Reminders
Support
Text Version

Construcción de MACs seguros teóricos de la información

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 la Criptografía Prof. Dr. Ashish Choudhury (ex) Fundación Infosys Fundación de Desarrollo Profesional Profesor Indios Instituto de Tecnología – Bangalore Conferencia – 26 Información-Los MACs teóricos continuaron Hola a todos, por lo que, esto es una continuación de la conferencia anterior, y en esta conferencia, veremos las construcciones formales de información teóricamente seguros códigos de autenticación de mensajes. (Consulte el apartado Tiempo de la diapositiva: 00:39) Así que ahora vamos a definir lo que llamamos campo. Por lo tanto, usted puede imaginar que el campo es un tipo especial de grupo porque tendrá ahora dos operaciones que denotamos como más y la multiplicación. Por lo tanto, este plus y la multiplicación son notaciones, no significa necesariamente el numérico o el entero más y la multiplicación del entero. Por lo tanto, tiene un conjunto de operaciones F y 2 sobre los elementos del conjunto F, a saber, (+,.) operaciones. Para que F sea un campo, las siguientes propiedades deben ser satisfechas, la primera propiedad que requerimos es que el conjunto (F, +) debe satisfacer todos los axiomas del grupo de Abelian, a saber, la propiedad de cierre, la propiedad de asociatividad, la existencia del elemento de identidad, la existencia del elemento inverso, y la propiedad de computatividad. Lo que hacemos es que si de hecho el (F, +) satisface los axiomas del grupo, entonces el correspondiente elemento de identidad que denotamos por 0, de nuevo el 0 no es un 0 numérico. Es sólo una etiqueta especial para el elemento de identidad, que está presente en el conjunto (F, +). De la misma manera, si el conjunto (F, +) satisface los axiomas del grupo, eso significa para cada elemento a, debe haber un aditivo inverso y ese aditivo inverso denotamos por -a. Una vez más, esto -a no debe interpretarse como el numérico – a, es sólo una etiqueta especial para el inverso del elemento a con respecto a +. Por lo tanto, la primera propiedad que requerimos de F es que el conjunto (F, +) debe satisfacer los axiomas del grupo y la segunda propiedad que requerimos para que el conjunto F sea denominado como un campo es que si tomamos el conjunto de todos los elementos (F-{0}) o el aditivo inverso o el elemento de identidad con respecto a la operación más, entonces ese conjunto debe constituir un grupo con respecto a “.” definido sobre el conjunto de elementos sobre el F. Eso significa, el cierre debe ser satisfecho, la asociatividad debe ser satisfecha, la existencia de la identidad debe ser satisfecha, cada elemento no cero en este conjunto F debe tener un inverso multiplicativo, y también debe satisfacer la propiedad de la commutatividad. Por lo tanto, si de hecho el (F-{0},.) satisface el grupo axiomas que significa que debemos tener un elemento de identidad, que denotamos por 1, I stress aquí este no significa el numérico o el entero uno. Es sólo una etiqueta para el elemento de identidad especial no cero presente en el conjunto F, que constituye el elemento de identidad con respecto a la operación de punto y ya que tendremos el inverso de cada elemento distinto de cero con respecto a la operación de punto que inversa, que término como el inverso multiplicativo será denotado por esta notación. De nuevo, esto no significa necesariamente 1/a porque como he dicho que esta operación de punto es una operación abstracta, no puede ser necesariamente la operación de multiplicación numérica. Por lo tanto, las 2 propiedades que requerimos de la F con respecto a + y. son los siguientes: requerimos (F, +) para constituir un grupo y requerimos un conjunto de elementos no cero para constituir un grupo con respecto a la operación de punto. La tercera propiedad que requerimos de un campo es la propiedad de distributividad, es decir, requerimos que la operación de puntos sea distributiva sobre la operación más. Eso significa un. (b + c) = a .b + a. c. Si ese es el caso, entonces decimos que el conjunto F junto con la operación más y el punto de operación constituye un campo y vamos a estar interesados en el campo finito y básicamente los campos finitos son aquellos campos en los que el conjunto F consiste en número finito de elementos. (Consulte el tiempo de la diapositiva: 05:00) Vamos a ver nuestro ejemplo de candidato para el campo finito porque nuestra construcción de SUF se basará en un campo finito. Así que déjenme definir el conjunto Zp para consistir de todos los enteros en el rango de cero a p-1 donde p es el mejor. Ahora déjenme definir un tipo especial de operación más sobre el conjunto Zp. La operación más se define de la siguiente manera: a + b: = (a + b) mod p. Así que cualquier resto que obtuviste dividiendo el número a + b con respecto al módulo p ese resto será llamado como la suma de a y b en este set Zp que es la forma en que estoy definiendo mi operación más. Así que se puede ver claramente que esta operación más se define de una manera especial. Eso no es simplemente la operación entera más y déjenme definir una operación de punto correspondiente sobre el dicho conjunto Zp. Por lo tanto, la operación de punto se define de la siguiente manera: a. b: = (a. b) mod p. Es fácil de ver, de hecho podemos demostrar que hay un teorema bien conocido que establece que el conjunto de Zp junto con esta operación más que hemos definido y con respecto a la operación de punto que hemos definido satisface los axiomas de campo. A saber, podemos demostrar que el conjunto Zp es un grupo abeliano. Por lo tanto, puede ver fácilmente que satisface la propiedad de cierre porque si hay 2 números del conjunto Zp y añádalo de acuerdo con esta definición, el resto {0, .. p-1}. Así que el cierre se satisface con respecto a más. La forma en que hemos definido plus satisfará la propiedad de la asociatividad. El elemento 0 de Zp, el numérico 0, y de hecho constituye el elemento de identidad con respecto a esta operación más. Para cada elemento ‘ a ’ s. Zp, tenemos un elemento correspondiente p-a también presente en Zp de modo que la suma de ‘ p-a ’ y ‘ a ‘ con respecto a esta operación plus le dará el elemento de identidad a saber 0 y la operación plus es conmutativa. Esto significa que el conjunto (Zp, +) satisface los axiomas del grupo y de la misma manera podemos demostrar que si consideramos el conjunto de elementos no cero, es decir, Zp – {0} y nos centramos en {1, … p-1} y consideramos la operación de punto, entonces de nuevo satisface ese axiomas de grupo y podemos demostrar que esta operación más está satisfaciendo la propiedad de distribución con respecto a esta operación de punto. Eso significa que puedes probar que este set Zp junto con esta operación de más operación y punto constituye un campo y si quieres verificar eso, vamos a ver un ejemplo aquí. Entonces, estoy tomando mi primer p= 5. Por lo tanto, eso significa que Z5 = {0, 1, 2, 3, 4} y lo que he hecho aquí es que he hecho la tabla de la operación más, la forma más operación funcionará en el conjunto {0, 1, 2, 3, 4}. El (i, j) th entry w.r.t “ + ” denota el resultado de i + j donde plus se define como i + j módulo p. Por lo tanto, por ejemplo 1 + 1 mod 5 = 2. Del mismo modo, 3 + 3 = 6 mod 5 = 1 y ahora puede verificar desde esta tabla que siempre obtiene una respuesta que pertenece al conjunto 0, 1, 2, 3, 4. Así que el cierre está satisfecho, usted tiene 0 como el elemento de identidad, cada elemento tiene un aditivo correspondiente inversa y así sucesivamente. La entrada (i, j) th w.r.t “. ” básicamente denota i. j mod 5, donde i y j pertenece al conjunto de elementos no cero de Z5 y de nuevo se puede ver que todos los axiomas del grupo están satisfechos para los elementos no cero 1, 2, 3, 4. (Consulte el tiempo de la diapositiva: 09:43) Por lo tanto, ahora vamos a suponer que se nos da el campo a saber, Zp y dos operaciones más y punto y nuestro objetivo es básicamente construir un SUF porque una vez que tenemos un SUF, entonces sabemos cómo construir o utilizarlo para construir la información teóricamente segura MAC. Por lo tanto, el SUF que vamos a diseñar es el siguiente: el espacio clave será el producto cartesiano de Zp y Zp, a saber, la clave constará de 2 elementos del conjunto Zp y el componente de mensaje del SUF que vamos a diseñar será un elemento del conjunto Zp. Por lo tanto, el espacio de mensajes Zp y el espacio de salida del SUF que vamos a construir Zp de forma, a saber, la salida será un elemento del conjunto Zp y la construcción es la siguiente: así que, como he dicho que la clave consistirá de 2 elementos del conjunto Zp, déjenme denotarlos por (a, b) y la clave será uniformemente y aleatoriamente recogidos del espacio clave. Esto significa que una Zp de forma aleatoria va a ser un valor uniformemente aleatorio y b es independiente de un y distribuido uniformemente sobre el conjunto de Zp. Así que esa es la clave. El mensaje m de Zp y si desea calcular el valor del SUF con la clave k en esta entrada m, a. m + b donde el punto y la operación más se corresponde con el punto y la operación más sobre este campo finito Zp i.e a. m = a. m mod p y + w.r.t mod p. Por lo tanto, el punto y la operación más son el punto y más del campo correspondiente, aquí que es Zp en este caso. Por lo tanto, básicamente la manera de entender este SUF es la siguiente: La clave aquí se puede imaginar como una línea recta. Por lo tanto, recuerde que una línea recta tiene una ecuación de la forma y = mx + c, donde m es la pendiente de la línea y c la intersección de la línea. Por lo tanto, (a, b) básicamente se puede imaginar como la (m, c) que define una línea recta y la salida de este SUF que puede imaginar como el punto en la línea recta determinada por el valor x = m. Por lo tanto, si sustituyo un valor de x aquí, obtengo un punto correspondiente en la línea definida por la pendiente m y la intersección c. Por lo tanto, esa es la forma en que estoy calculando el valor de este SUF. Así que es una manera sencilla de interpretar la construcción de este SUF. Ahora, tenemos que demostrar si esta construcción constituye un SUF o no y vamos a reclamar aquí que la función h que hemos definido como esta, de hecho, constituye un SUF. Por lo tanto, recuerde, la definición de SUF es que para cada par de mensajes (m, m ’), m ≠ m ’ y para cada Tag-Ver (t, t ’), pr [hk (m) = t] = pr [hk (m ’) = t ’] bajo una clave desconocida k, para cada keyk. Por lo tanto, para probar que consideremos un arbitrario (m, m ’), m ≠ m ’ y un par arbitrario de etiqueta candidata del espacio de etiquetas o espacio de salida. La afirmación aquí es que siempre existe una clave única que denotan por (a, b) tal que ha, b (m) =t y ha, b (m ’) = t ’. Esto se debe a que si efectivamente t tiene que ser la salida del SUF h que hemos construido para la entrada m con respecto a la clave (a, b), entonces esta ecuación debe contener y de la misma manera, si t ’ es de hecho la salida del SUF h para la entrada m ’ bajo la clave (a, b), entonces esta condición tiene que mantener. Por lo tanto, puesto de una manera diferente, básicamente ambas ecuaciones juntas implican que si de hecho quiero que ha, b (m) =t y ha, b (m ’) = t ’, entonces ambas condiciones deben mantenerse simultáneamente. Esto significa que debe tomar este valor y b debe tomar este valor. Por lo tanto, observe que esto (m – m ’) -1 básicamente que denota la inversa multiplicativa porque estamos haciendo todo esto más operación, punto de operación sobre el campo. Debemos considerar esto (m – m ’) -1 ≠ 1/(m – m ’). No, no estamos haciendo la aritmética entera aquí, estamos haciendo la aritmética de campo finito aquí. Así que, eso significa (a, b) debe tomar estos 2 valores y si pongo todo en un contexto diferente, lo que básicamente requiere aquí es que si a toda la probabilidad de que de hecho la salida de mi SUF para la entrada m es t y la salida de SUF en la entrada m ’ es t ’ bajo la clave (a, b) es de hecho igual a t ’ sostiene. Para eso, me hace falta un para tomar este valor y mi requisito b para tomar este valor, pero recuerde que la clave (a, b) que he elegido para el SUF se distribuye uniformemente sobre el Zp X Zp. Esto significa que un se selecciona uniformemente sobre el conjunto Zp y así es b. Entonces, ¿cuál es la probabilidad de que mi a realmente ocupe este valor? Bueno, es 1/tag-espacio o 1/Zp, y cuál es la probabilidad de que de hecho mi b también tome este valor que también es 1/Zp. Juntos la probabilidad de que un toma este valor y b tome este valor será el producto de 1/Zp * 1/Zp, que es igual que 1/ Γ 2 porque mi espacio de etiquetas tampoco es nada más que el Zp y que prueba el teorema que de hecho la función h que hemos construido aquí constituye un SUF. (Consulte el tiempo de la diapositiva: 16 :29) Así que, aunque ahora tenemos una construcción candidata de una única información-MAC seguro teórico. La información-MAC seguro MAC que hemos construido, allí la probabilidad de éxito de falsificación es 1/p porque la probabilidad de éxito era de la construcción genérica que teníamos, allí la probabilidad de éxito de la falsificación era de 1/Γ, ya que el espacio de etiquetas aquí no es nada más que Zp y | Zp | = p, aunque la información candidata-teorética única MAC seguro que hemos construido, allí la probabilidad de éxito es 1/p. Por lo tanto, si aseguramos que la p es significativamente grande, entonces la probabilidad de forja del adversario se vuelve insignificante, pero la desventaja de esta construcción es que la clave que estamos usando aquí es el doble de grande que el mensaje. A saber, la clave Zp X Zp, pero el mensaje de Zp. Por lo tanto, lo que haremos ahora es que veremos una construcción más eficiente de una sola vez información teorética MAC seguro donde vamos a autenticar un mensaje de un tamaño más grande, a saber, que consistirá de varios elementos de Zp usando la clave (a, b). Sin embargo, antes de entrar en eso, tratemos de entender que por qué el MAC que hemos construido usando el candidato SUF sobre el campo es sólo información de una sola vez-seguro teórico. Por lo tanto, el algoritmo de generación de etiquetas aquí es básicamente el valor de la línea recta definida por la pendiente a e interceptar b en la entrada m. Ahora, imagine con respecto a la misma clave k, sender autentica 2 mensajes, m y m ’? Por lo tanto, el remitente autentica el mensaje m y la etiqueta será t = a. m + b e imaginar que en lugar de utilizar la clave (a, b) para autenticar un solo mensaje, el remitente termina autenticando otro mensaje, a saber, reutilizar la clave para autenticar otro mensaje diferente m ’ y la etiqueta para ello será t ’ = a. m ’ + b. Ahora, imagina que hay un adversario, que observa el mensaje y esta etiqueta correspondiente y el mismo adversario observa este mensaje m ’ y la etiqueta correspondiente t ’. Ahora es muy simple para el adversario recuperar la llave consistente de (a, b) porque desde el punto de vista de ese adversario, había 2 incógnitas, a saber, a y b y ahora él está consiguiendo un sistema de ecuaciones lineales y 2 incógnitas y él tiene dos ecuaciones tales que son linealmente independientes y él puede resolver el sistema de ecuaciones lineales sobre el campo finito y terminar recuperando a, b que es la clave. Una vez que el adversario recupera la llave (a, b), puede crear una falsificación en cualquier mensaje nuevo y enviarla al receptor. Por eso es por eso que la seguridad del MAC que hemos construido usando el SUF sobre el campo finito le da la garantía de seguridad para autenticar solamente un solo mensaje. Utilizando una clave (a, b) puede autenticar sólo un único mensaje, no puede volver a utilizar la misma clave para autenticar más de un mensaje. Así que ahora volviendo a nuestra pregunta anterior que es posible modificar la única información-MAC seguro teorético donde podemos autenticar un mensaje de tamaño más grande usando la misma clave (a, b) y resulta que es posible hacer eso y que MAC modificado también se llama popularmente como Carter y Wegman MAC y lo que el MAC hace es que permite autenticar el mensaje que consiste de hasta l elementos del campo Zp. Por lo tanto, imagine que tiene un mensaje m que consiste en decir v número de elementos del campo, donde v podría ser cualquier valor en el rango 1 a l y la clave para la autenticación es (a, b). Ahora, el algoritmo de generación de etiquetas es el siguiente: lo que hace un algoritmo de generación de etiquetas es computa este valor. Por lo tanto, puede interpretar este valor t para que sea el siguiente. Entonces, ¿qué es exactamente esto? Si usted trata esta cosa en particular que está allí en el soporte, usted puede interpretarlo como el valor de un polinomio de grado v + 1, donde los coeficientes del polinomio son 1, m1, m2, hasta mv. Así que usted tiene un polinomio en una variable decir x de grado v + 1 con estos coeficientes y básicamente usted está evaluando ese polinomio en a y añadiendo el valor b y que le dan la etiqueta en el mensaje que desea autenticar. Así que es una manera de interpretar este MAC Carter-Wegman y en cierto sentido, básicamente, esto es una generalización de la única MAC segura de TI que acabamos de construir. En la construcción anterior, había una línea recta que usted puede imaginar, un polinomio de grado 1 porque usted tiene un mensaje que consiste simplemente en un solo elemento. Pero ahora tienes un mensaje = (m1, .. mv), v elementos para autenticar que en realidad estás definiendo un polinomio de grado v + 1 y t: = av + 1 + m1 av + m2 av-1 + .. + b para obtener la etiqueta general. Ahora, es posible que te estés preguntando que a pesar de que tienes v número de elementos en el mensaje, por qué estás definiendo un polinomio de grado v + 1. Lo dejo como un ejercicio para que identifiques lo que pasa si defino un polinomio de grado v en lugar de v + 1 y terminos evaluándolo en la tecla (a, b) y obtengo la etiqueta. Resulta que si modificamos esta construcción y en lugar de definir un polinomio de grado v + 1, tomamos un polinomio de grado v, entonces la construcción resultante no te va a dar un MAC seguro. (Consultar Tiempo de Slide: 22:37) Así que, ahora, yo reclamo que el MAC Carter-Wegman que hemos construido le da una autenticidad única, donde la probabilidad de éxito de falsificación es (l + 1 )/p. Eso significa, imagina que hay un adversario que aprende el valor de la etiqueta según el MAC que hemos construido sobre algún mensaje y donde también se conoce el mensaje m, pero la clave (a, b) no es conocida por el adversario y ahora supongamos que el adversario quiere llegar con una falsificación en un mensaje m * que es diferente de m y para producir la falsificación, también da salida a la etiqueta correspondiente, que denoro por t *.Ahora, nuestro objetivo es analizar cuál es la probabilidad de éxito que (m*, t *) efectivamente constituye una falsificación válida. Eso significa lo que es pr [t * = Tag-gena, b (m *)]? Quiero decir que la probabilidad de que esto ocurra es una (l + 1 )/p. Para esto, primero intentemos entender que si tengo un mensaje m para el cual la etiqueta es t, entonces usted puede decir que el mensaje m consiste de v el número de elementos del campo, donde v es cualquier cosa en el rango 1 a l. Entonces el polinomio correspondiente definido por los elementos de m de grado v + 1 será: f (X) = X v + 1 + m1. Xv + m2. Xv-1 + .. + mv. X esto y de la misma manera imaginar el mensaje m * g (X) = Xu + 1 + m * 1. Xu + m * 2. Xu-1 + .. + m*u. X. Ahora, en base a estos 2 polinomios, déjenme definir la diferencia polinomial que me llamo h (X), que es la diferencia del polinomio f (X) y g (X). Ahora, puesto que el valor t es la etiqueta del mensaje m bajo la tecla a, sostiene que la t no es nada más que el valor del f polinomio en la entrada a + b porque así es como el Carter-Wegman habría sido calculado en el mensaje m, y si quieres que t * también debería ser un MAC en el mensaje m *, Carter-Wegman MAC en el mensaje m * bajo la misma clave desconocida (a, b). Entonces debe sostener que t * debe ser el valor del polinomio g en la entrada a + b. Eso significa juntos ambas condición si sostienen que significa que t-t * debe ser el valor de la h polinomio o la diferencia polinomio en la entrada a. Ahora, eso significa que la probabilidad de que t * sea de hecho el MAC Carter-Wegman para el mensaje m * bajo la clave (a, b) para que eso se mantenga, debe mantener en el valor a o la parte de la llave debe constituir una raíz del polinomio h (x) – t-t *. Porque si usted ve a debe constituir una raíz del polinomio h (x)-t – t *. Si tomo este polinomio y si de hecho un resulta ser una raíz de esto, entonces de hecho obtenemos que t es igual a la MAC del mensaje m y t * es un MAC del mensaje m *, pero ¿qué es exactamente el grado del polinomio h (x)-t – t *? Bueno, es un polinomio de grado hasta l + 1 porque recuerda mi v, el número de elementos en el mensaje podría ser cualquier cosa en el rango 1 a l, por lo que en el peor de los casos podría ser l. De la misma manera, el número de elementos en el mensaje m * podría ser hasta l. Eso significa, el grado de f (x) polinomio podría ser cualquier cosa en el rango de 1 a l + 1 o 0 a l + 1 y de la misma manera, el grado de g (x) podría ser máximo l + 1. Es por eso que la diferencia polinomio h (x) podría tener un grado de 2l + 1 y si tengo un polinomio de diferencia cuyo grado es l + 1, entonces puede tener hasta l + 1 raíces. Así que básicamente, para que t * sea la etiqueta del mensaje m * bajo la llave (a, b), debería ser el caso de que a debe ser una de las 1 + 1 raíces posibles del polinomio h (x) cuyo grado es l + 1. Para la probabilidad de que de hecho una es una de esas raíces es (l + 1)/p porque hay l + 1 raíces candidatas y la raíz podría ser cualquier valor de set Zp. Así es como obtenemos la probabilidad de éxito de la falsificación para este Carter-Wegman una vez MAC. De nuevo, es interesante ver que por qué exactamente este MAC es seguro una vez, por qué no podemos autenticar 2 mensajes m y m ’ bajo la misma clave desconocida (a, b). Resulta que si tratamos de autenticar m con la clave (a, b) y obtener una etiqueta t como por el esquema Carter-Wegman, y si tengo otro mensaje m ’ y si autentica el mismo mensaje reutilizando la misma clave que por el proceso Carter-Wegman y obtener la etiqueta t ’, entonces básicamente adversario aprende mucha información sobre la clave (a, b). Básicamente puede recuperar la llave completa (a, b) resolviendo un sistema de 2 linealmente independiente y una vez que aprende la clave (a, b), puede llegar con una falsificación en cualquier mensaje m * y reenviado al receptor que será aceptado. Así que es por eso que usando este MAC Carter-Wegman, podemos autenticar sólo un mensaje, no podemos reutilizar la misma clave para autenticar múltiples mensajes y resulta que formalmente podemos probar esto. Olvídese de Carter-Wegman MAC, si usted tiene cualquier tipo de información teorética MAC seguro, entonces con el fin de autenticar múltiples mensajes, usted tiene que aumentar proporcionalmente el tamaño de la clave, usted no puede tener una clave de algún tamaño fijo fijo y esperar que su esquema es la información teóricamente segura y al mismo tiempo le da la garantía de autenticar el número arbitrario de mensajes. En función del tamaño de la clave, se obtiene la restricción en el número máximo de mensajes que se pueden autenticar en presencia de un adversario computacionalmente sin límites. Esto es en contraste con MACs computacionalmente seguros donde podemos usar la misma clave para autenticar básicamente un gran número arbitrario de mensajes, número polinomio de mensajes porque allí el adversario está computacionalmente acotado, pero tan pronto como vamos al mundo computacionalmente ilimitado, obtenemos las restricciones en el número de mensajes que usted puede autenticar usando la clave. Así que, eso me lleva al final de esta conferencia. Permítanme resumir lo que hemos discutido en esta conferencia. En esta conferencia, hemos visto las construcciones de los MACs seguros de la información-teorética, que le da la garantía de seguridad incluso contra un adversario computacionalmente sin límites. Sin embargo, si el adversario es computacionalmente ilimitado, no podemos obtener la garantía de falsificación cero que significa que siempre hay una probabilidad de error no cero que se asociará en el esquema porque el adversario siempre puede adivinar el valor de la etiqueta en nuestro mensaje que nunca fue autenticado por el remitente en las sesiones anteriores. También vimos una construcción genérica de información-MAC seguro teórico dado funciones fuertemente universales y hemos visto la construcción de una función fuertemente universal basada en el álgebra de campo finito y también hemos visto una información muy eficiente-seguro teórico