lunes, 26 de octubre de 2015

Criptografía

Algoritmos criptográficos

El sistema de compartición de secretos de Shamir es un algoritmo criptográfico. Es una forma de compartición de secretos donde un secreto se divide en partes y se da a cada participante una sola: todas o parte de ellas son necesarias para reconstruir el secreto.
El algoritmo basa su funcionamiento en una propiedad de los polinomios interpoladores1 y fue desarrollado por el criptógrafoisraelí Adi Shamir, que lo presentó en 1979.

Definición matemática

Formalmente, nuestro objetivo es dividir un conjunto de datos D\,\! (por ejemplo, una clave) en n\,\! partes D_1,\cdots,D_n\,\! de manera que:
  1. El conocimiento de k\,\! o más D_i\,\! partes hace que D\,\! sea fácilmente computable.3
  2. El conocimiento de k-1\,\! o menos D_i\,\! partes hace que D\,\! esté indeterminado, en el sentido de que todos sus valores posibles tienen la misma probabilidad de ser verdaderos.
Esta combinación se denomina combinación o esquema de umbral \left(k,n\right)\,\!.2 Si k=n\,\! se requiere la concurrencia de todos los participantes para reconstruir el secreto.

Sistema de compartición de secretos de Shamir

Se pueden dibujar infinitos polinomios de grado 2 que pasen por 2 puntos. Se necesitan 3 puntos para definir un polinomio único de grado 2. Esta imagen sólo tiene fines ilustrativos - El esquema de Shamir utiliza polinómios en un conjunto finito, no representable en un plano bidimensional.
La idea esencial de la combinación de umbral de Shamir es que dos puntos son suficientes para definir una línea recta, tres puntos lo son para definir una parábola, cuatro para definir una curva cúbica y así sucesivamente. Es decir, son necesarios n+1\,\! puntos para definir un polinomio de grado n\,\!.
Supongamos que queremos trabajar con un umbral de \left(k,n\right)\,\! para compartir un secreto S\,\! (cualquier número, sin pérdida de generalidad) siendo k<n\,\!. La elección de los valores de k\,\! y n\,\! determina la fortaleza del sistema.
Eligiendo al azar \left(k-1\right)\,\! coeficientes a_1,\cdots,a_{k-1}\,\!, y siendo a_0=S\,\!, se construye el polinomio f\left(x\right)=a_0+a_1x+a_2x^2+a_3x^3+\cdots+a_{k-1}x^{k-1}\,\!. Calculamos cualesquiera n\,\! puntos a partir del mismo, por ejemplo determinamos que i=1,\cdots,n\,\! de lo que se deriva \left(i,f\left(i\right)\right)\,\!. A todo participante en el secreto se le da un punto (un par de valores, el de entrada y el de salida para el polinomio)
Dado cualquier subconjunto de k\,\! entre estos pares, podemos calcular los coeficientes del polinomio mediante interpolación y luego despejar a_0\,\!, que es el secreto.

Ejemplo de uso

Preparación

Supongamos que el secreto es el número de una tarjeta de crédito: 1234 (S=1234)\,\!.
Queremos dividir el secreto en seis partes (n=6)\,\!, de forma que cualquier subconjunto (k=3)\,\! sea suficiente para reconstruir el secreto. Al azar obtenemos k-1 números: por ejemplo, 166 y 94.
(a_1=166;a_2=94)\,\!
El polinomio con el que operaremos será por lo tanto:
f\left(x\right)=1234+166x+94x^2\,\!
Calculamos seis puntos a partir del polinomio:
\left(1,1494\right);\left(2,1942\right);\left(3,2578\right);\left(4,3402\right);\left(5,4414\right);\left(6,5614\right)\,\!
Damos a cada partícipe un único punto, que comprende el valor x\,\! y f\left(x\right)\,\!).

Reconstrucción

Para reconstruir el secreto bastará con tres puntos.
Considérese
\left(x_0,y_0\right)=\left(2,1942\right);\left(x_1,y_1\right)=\left(4,3402\right);\left(x_2,y_2\right)=\left(5,4414\right)\,\!.
\ell_0=\frac{x-x_1}{x_0-x_1}\cdot\frac{x-x_2}{x_0-x_2}=\frac{x-4}{2-4}\cdot\frac{x-5}{2-5}=\frac{1}{6}x^2-\frac{3}{2}x+\frac{10}{3}\,\!
\ell_1=\frac{x-x_0}{x_1-x_0}\cdot\frac{x-x_2}{x_1-x_2}=\frac{x-2}{4-2}\cdot\frac{x-5}{4-5}=-\frac{1}{2}x^2+\frac{7}{2}x-5\,\!
\ell_2=\frac{x-x_0}{x_2-x_0}\cdot\frac{x-x_1}{x_2-x_1}=\frac{x-2}{5-2}\cdot\frac{x-4}{5-4}=\frac{1}{3}x^2-2x+\frac{8}{3}\,\!
Por lo tanto,
f(x)=\sum_{j=0}^2 y_j\cdot\ell_j(x)\,\!
=1942\cdot\left(\frac{1}{6}x^2-\frac{3}{2}x+\frac{10}{3}\right)+3402\cdot\left(-\frac{1}{2}x^2+\frac{7}{2}x-5\right)+4414\cdot\left(\frac{1}{3}x^2-2x+\frac{8}{3}\right)\,\!
=1234+166x+94x^2\,\!

Teniendo en cuenta que el secreto es el coeficiente de x^0\,\!, el secreto original es S=1234\,\!.







La exponenciación modular es un tipo de exponenciación realizada sobre un módulo. Es particularmente útil en ciencias de la computación, especialmente en el campo de la criptografía.
Una «exponenciación modular» calcula el residuo cuando un número entero positivo b (la base) se eleva a la e-ésima potencia (el exponente), be, y es dividido por el entero positivo m, llamado módulo. En símbolos, esto es, dada la base b, el exponente e, y el módulom, la exponenciación modular c es: c \equiv b^e \pmod{m}
Por ejemplo, dado b = 5, e = 3, y m = 13, la solución, c = 8, es el resto de dividir 5^3 por 13.
Si b, e, y m no son negativos, y b < m, entonces una única solución c existe con la propiedad 0 ≤ c < m.
La exponenciación modular se puede realizar con exponente negativo e encontrando el inverso multiplicativo modular d de b módulo musando el algoritmo extendido de Euclides. Esto es:
c \equiv b^{e} \equiv d^{\left|e\right|} \pmod{m} donde e < 0 y b \cdot d \equiv 1 \pmod{m}
Problemas de exponenciación modular similares al descrito arriba son considerados fáciles de resolver, incluso cuando los números que se manejan son enormes. Por otro lado, el cálculo del logaritmo discreto — es decir, la tarea de encontrar el exponente e si es dado unb, c, y m — se cree que es difícil. Este comportamiento de función unidireccional hace a la exponenciación modular un candidato para su uso en algoritmos criptográficos.

El algoritmo para cálculo de la exponenciación modular

El algoritmo:

Entrada: números enteros a (base), n (exponente), m (módulo)
Devuelve: un entero exp= an mod m
Restricciones:  0 <= a < m,  m >= 2,  n >=0 
función Exponenciación (entero a, entero n, entero m) : entero

 exp:=1
 x:= a mod m
 while (n >0) do
    begin
  if "n es impar" then exp:= (exp*x) mod m
  endif
  x:= (x*x) mod m
  n:= n/2
    endwhile

 return (exp)
end función
La idea detrás de la exponenciación modular rápida consiste en obtener la representación del exponente n en dígitos binarios (dt,dt-1,...,d2,d1), con dt =1, y hallar los distintos cuadrados sucesivos (mod m) de la base a: (a1,a2,a4,...,a2t), para después multiplicar módulo m las potencias a2i correspondientes a los dígitos binarios di que sean "1".
Partiendo de esta idea, el algoritmo arriba mostrado se sirve de un bucle en el que en cada iteración se van generando y multiplicando los cuadrados correspondientes, al mismo tiempo que se va dividiendo el exponente n entre 2 (para obtener los dígitos del exponente en binario)














La Firma de Lamport-Diffie es un esquema de firma digital propuesta por L. Lamport y W. Diffie.1 y que está basada en criptografía simétrica . La firma, en principio, se aplica sobre mensajes sin efectuar ninguna modificación previa de los mismos.

Descripción

Para firmar un mensaje M de n bits, el firmante elige aleatoriamente un vector K constituido por n parejas de claves secretas dadas por:
K=[(k_{10},k_{11}),....,(k_{n0},k_{n1})]
A continuación el firmante calcula dos secuencias de valores R y S dadas por:
S=[(s_{10},s_{11}),...,(s_{n0},s_{n1})]
R=[(r_{10},r_{11}),...,(r_{n0},r_{n1})]
donde los valores del conjunto S se escogen de forma aleatoria y los del conjunto R son sus respectivos cifrados dados por:
r_{ij}=E_{kij}(s{ij})
siendo E_{kij}(....) un criptosistema simétrico de clave kij. La estructura del criptosistema E utilizado determina el número de bits n y la longitud de las secuencias R y S utilizadas luego para la validación. Por ejemplo, si E es el DES, entonces n=64. En estas condiciones, los conjuntos R y S se hacen públicos en un registro de sólo lectura, que sólo puede ser modificado por el firmante. La firma M_f del mensaje M=(m_1,m_2,...,m_n) con m_i un bit que puede valer 0 ó 1, será:
M_f=(k_{1m1},...,k_{nmn}).
La firma M_f del mensaje M es obtenida de la siguiente forma: la componente i de M_f será r_i0 si m_i es 0, en otro caso será r_i1. La autenticidad de la firma M_f se comprueba verificando las relaciones entre los correspondientes valores de las secuencias de validación R y S en función de las claves conocidas. Sea
S_f=(s_{1m1},...,s_{nmn})
obtenido de la misma forma que se calculaba M_f pero ahora en lugar de R, usamos S. Ahora hallamos R'_f
R'_f=(E_{k1m1}(s_{1m1}),...,E_{knmn}(s_{nmn}))
En estas condiciones, el receptor acepta la validez de la firma si dichos valores son respectivamente iguales a los del subconjunto R_f del registro público R (hallado de forma análoga que M_f y S_f, pero esta vez sobre R)

Ejemplo

Sea E_k=M \oplus k un criptosistema simétrico de clave secreta k de n=3 bits. Para computar la firma de M=1011, Primero el firmate elige aleatoriamente el vector binario K de claves secretas, por ejemplo:
K=[(000,011),(110,001),(100,111),(010,101)]
A continuación se elige la secuencia binaria aleatorio S, por ejemplo
S=[(011,001),(010,111),(100,110),(101,000)]
y computa el vector R
R=[(011,010),(100,110),(000,001),(111,101)]
haciendo públicos los conjuntos R y S. Por tanto la firma M_f será:
M_f=(011,010,110,000)
Para verificarla hallamos S_f y R_f:
S_f=(001,010,110,000)
R_f=(010,100,001,101)
Para verificar hallamos R'_f quedando
R'_f=(001 \oplus 011,010 \oplus 110, 110 \oplus 111, 000 \oplus 101)
que coincide con R_f y por tanto el receptor acepta la validez de la firma.

Incovenientes

Es conveniente que el firmate cambie el vector de claves secretas K, así como las correspondientes secuencias de validación contenidas en los registro públicos R y S, cada vez que se aplique la firma. En caso contrario, el secreto podría ser revelado, comprometiendo la seguridad.
Otro inconvenientes es el de la excesiva longitud de la firma, de la clave K y de los vectores R y S implicados. Produciendo un gasto de recursos de almacenamiento y de transmisión. Una forma de paliar un poco este inconveniente es firmar el resultado de aplicar una función hash (realmente un código de detección de manipulaciones).

Publicado por en

No hay comentarios:

Publicar un comentario

Suscribirse a: Enviar comentarios (Atom)