Criptografía y funciones HASH, poco a poco

20 enero 2013
Licencia Creative Commons
Este obra está bajo una licencia Creative Commons Atribución 3.0 Ecuador.

La Criptografía moderna

 0 0 ==> 1

Función HASH

Función que recibe como entrada un mensaje y entrega como salida un código o valor hash. Las de mayor importancia son las criptográficas hash que entregan la huella digital o resumen del mensaje que permiten mantener la integridad de los datos buscando que la salida sea, en lo posible, una imagen únicamente de un solo elemento del dominio de mensajes. Otra característica es que la salida o código siempre tendrá una longitud constante para todo valor del dominio de entrada por lo que también se la conoce como función Resumen.

La razón de ser de esta página

Todo avanza vertiginosamente y el conocimiento de esas cosas nuevas debe llevar el mismo ritmo y más. Si no colaboramos en esta vorágine paradójicamente el conocimiento que ahora es de muchos puede convertirse en bien de pocos.


Las funciones


Los pares ordenados (x,y1) y (x,y2) son pares de una función si y solo si y1=y2. Partiendo de esta definición entonces las relaciones y, z, w son funciones, mientras que r no lo es. Las relaciones, elementos del álgebra relacional, que no sean funciones están desechadas en el ámbito hash, ya que de partida entregarían como mínimo dos códigos, que resulta inservible por no ser imagen única del mensaje.

   Función inyectiva

   Si  (x1,y1) y (x2,y1) pertenecen a la funcíón, ésta es inyectiva si y solo si x1=x2. Entonces únicamente
   las funciones z, w arriba mostradas son inyectivas. En general la función inyectiva garantiza que el
   código o imagen generados corresponda a un único mensaje.  Las funciones hash no son inyectivas, 
   por lo que la unicidad del mensaje se garantiza con funciones de una sola vía o "virtualmente
   inyectivas".


   En el ejemplo la obtención del valor x tal que f(x)=100, es muy simple ya que basta con aplicar el
   antilogaritmo.

   Colisiones en el dominio de las funciones

   Si para un par de valores a1 y a2 pertenecientes al dominio de la función existe una imagen y, tal que
   f(a1) = f(a2) =y, entonces existe una colisión. Toda función no inyectiva presenta colisiones y por ende
   las funciones hash al no ser inyectivas van a presentar colisiones en su dominio, problema a resolver
   con otras técnicas.

  Funciones resistentes a colisiones

   Una función f es resistente a colisiones si conocido f(x) para un valor x perteneciente al dominio, es
   computacionalmente inviable conseguir x' tal que f(x) = f(x'). Toda función inyectiva es completamente
   resistente a colisiones.
    

  Funciones fuertemente resistentes a colisiones

   Una función f es resistente a colisiones si conocido f(x) para un valor x perteneciente al dominio,
   resulta computacionalmente inviable conseguir x' tal que f(x) = f(x').

   Función de doble vía

   Son las funciones cuyo cálculo de la inversa computacionalmente no es muy complicado, en un
   entorno dado.

         Ejemplo cotidiano Nº 1    

         Si matemáticamente es fácil determinar la inversa, computacionalmete no hay la menor
         complicación


         Ejemplo cotidiano Nº 2

         Aunque para la función mostrada no siempre es posible obtener la fórmula de la inversa,
         computacionalmente es sencillo obtener X1 una vez dado Y1 con un simple algoritmo.



   Función de una sola vía

   Son las funciones cuyo cálculo de inversa es computacionalmente complicado. Implica esto que si m
   es imagen de un mensaje x, conseguir el valor de x tal que f(x)=m resulta altamente complicado.  

    Función de paridad

    Es una función especial, que asigna el valor 1 si el vector de entrada cuyas coordenadas son 1 y 0
    tiene un número impar de unos (1s).


      Características de la función de paridad
      - No inyectiva
      - No resistente a colisiones
      - Doble vía

         Ejemplo cotidiano Nº 1

         Carlos, va a partir al exterior. Dejó su maleta en el guardametas del aeropuerto y olvidó la clave que
         es un número perteneciente al intervalo {1,255}. Afortunadamente la dejó escrita en un papel en la
         mesa de su cuarto en su ciudad natal. LLama y pide se la manden en un mensaje en binario
         con bit de paridad.

         Su padre, consigue el número 127 anotado en el papel y como algo sabe de números tiene una
         disyuntiva: mandarlo como una cadena de 8 bits más bit de paridad para el 127 o como tres
         cadenas  de 3 bits + bit de paridad para 1, 2 y 7.


          A continuación se muestra la cadena de 8 bits, con el bit de paridad.



         Cuando llegó encontró el maletero vacío. ¿Cómo pudo pasar esto?

         1. Alguien entró a la sala de maleteros e hizo en cada maletero 255 intentos, como máximo, y logró
             abrirlo.
         2. Alguien capturó el mensaje y como no iba encriptado rápidamento lo descifró y en cada
            maletero hizo un intento como máximo hasta conseguir el de Carlos.


   Función dígito validador cédula ecuatoriana

   La cédula ecuatoriana tiene las características siguientes:


   Tomar los dígitos que ocupan las posiciones impares y multiplícarlos por 2

   1 x 2 =   2
   0 x 2 =   0
   2 x 2 =   4
   3 x 2 =   6
   5 x 2 = 10

   Si alguno es mayor o igaul a 10, restarle 9

   1 x 2 =   2
   0 x 2 =   0
   2 x 2 =   4
   3 x 2 =   6
   5 x 2 = 10 - 9 =1

   Sumar los subtotales = 2 + 4 + 6 +1 = 13



  Sumar los dígitos que ocupan las posiciones pares. El dígito validador no se considera, pues es el
  dígito a validar.

  1 + 0 + 9 + 4  = 14

  Finalmente sumar los dos subtotales ==> 13 + 14 = 27 y restarlo de la centena inmediata superior

  30 - 27 = 3, que es el dígito validador.

  Características adicionales de la función dígito validador de la cédula ecuatoriana

      - No inyectiva
      - No resistente a colisiones
      - Doble vía

         Ejemplo cotidiano Nº 1

         He oído que Loja es una de las provincias con mayor índice de graduados universitarios.
         Para de una buena vez determinarlo se pide diseñe una base de datos para almacenar la data
         correspondiente: cédula, títulos obtenidos, universidad, fecha de registro.

         Premisas
         Si tiene títulos entonces están registrados en la SENESCyT
         Si está vivo entonces está registrado en el CNE

         Pasos
         Iniciar con la cédula semilla 110000000?
         Conseguir el validador.
         Acceder a la página del CNE, para saber si está vivo.
         Acceder a la página de la SENESCyT para obtener los títulos.
         Cargar datos en la base de datos, si amerita.
         Repetir mientras...


         Ejemplo cotidiano Nº2

         El Instituto Ecuatoriano de Seguridad Social (IESS) atiende solicitudes de citas con el siguiente
         protocolo: Quienes tienen cédula que terminan en 1 o 6 deben llamar los lunes, si la cédula termina
         en 2 0 7 deben llamar los días martes y así sucesivamente. Mientras que otra institución trabaja de
         igual forma pero con los penúltimos dígitos de la cédula.

         Se pide:
         Diga cuál de los dos sistemas es más justo en la provincia deBolívar.

   Propiedades que debe satisfacer una función hash h(x) para usos criptográficos 

   1- Fácil de computar para todo x perteneciente a dominio de h(x)
   2- De una sola vía
   3- Resistente a colisiones
   4- Fuertemente resistente a colisiones

   





En constante edición


Bibliografía

1. Funciones HASH, disponible en página_01
2. Perramon,  Xavier. MECANISMOS DE PROTECCIÓN, disponible en página_02

1 comentario: