jueves, 17 de noviembre de 2016

¿Nos importa una "mierda" nuestra privacidad?

¿Te importa tu privacidad cuando navegas por Internet, o cuando pones contenidos en redes sociales,..., o no te preocupa en absoluto y éste es un tema para los raros como yo?.

Mi opinión, muy breve:

1.- No, no nos importa hasta que pasa "algo". ¡Como es "gratis" a mí que me importa! (hasta que pase algo que me afecte directamente a mí).

2.- El nuevo Reglamento Europeo de Protección de datos (RGPD) "no hay por donde cogerlo"; en mi opinión conlleva un escenario de pérdida de derechos fundamentales respecto a privacidad y protección de datos de carácter personal.

3.- Una regulación "homogeneizadora" suele devenir indefectiblemente en una regulación más laxa, como creo que es el caso. ¡Que no nos vendan otra cosa!.

4.- Esa supuesta regulación "homogeneizadora" responde exclusivamente, en mi opinión, a intereses económicos, y no precisamente los nuestros.

La vieja y pusilánime Europa, que dice defender los "derechos fundamentales" de sus ciudadanos, y mejor haría defendiendo los "derechos humanos" de todos, incluidos los de los refugiados (asunto muchísimo más importante), se pliega a los intereses comerciales de los lobby.

5.- Lo dicho:

¡La LOPD ha muerto, viva el TTIP (con permiso de Donald)!.

¿Qué opináis?. Asunto para el debate: ¿Nos importa una "mierda" nuestra privacidad?.

martes, 8 de noviembre de 2016

Criptografía (XXXVII): criptología para todos (IV)

Hace ya más de un año empecé a escribir sobre criptología en este humilde blog, con el único objetivo de aprender, pasármelo bien y compartir lo que voy aprendiendo sobre ella de la forma más comprensible de la que sea capaz y espero que sin cometer demasiados errores.

Echando la vista atrás veo que son ya más de treinta entradas las que he escrito sobre ello, y en este post hago un pequeño resumen, primero a modo de clasificación de los sistemas criptográficos según su tipología, tanto clásicos como modernos, y segundo a modo de índice de las entradas que he escrito en este blog.

La clasificación que realizo no pretende ser exhaustiva (los sistemas criptográficos presentan demasiadas variantes para considerarlas todas; algunas de las cuales, además, me resultan difíciles de catalogar), sino que se trata de una primer aproximación conforme a lo que he ido entendiendo (por supuesto y como siempre encantado de recibir aportaciones y las correcciones que sean oportunas sobre lo aquí expuesto).

Una clasificación que a mí me parece adecuada (poniendo para cada tipo un ejemplo de sistema criptográfico de los que he tratado y de los que hablaré en este blog) podría ser la siguiente:
Dicho esto, el índice de las entradas sobre criptología en este blog, intentando ordenarlas un poco, es el siguiente:

1.- Criptología clásica:

     1.1.- Cifrado Vigenère:
             1.1.1.- Cifrado Vigenère y criptoanálisis Kasiski (ejemplo de ambos).
             1.1.2.- Otro ejemplo de criptoanálisis Kasiski al cifrado Vigenère.
             1.1.3.- Resolución de dudas planteadas en este blog sobre el primer ejemplo.
             1.1.4.- Cifrado Vigenère y criptoanálisis basado en el Índice de coincidencia (IC):
                         1.1.4.1.- Criptoanálisis IC cifrados sust. polialfabética con claves periódicas.
                         1.1.4.2.- Ejemplo de ataque a un criptograma basado en el IC

     1.2.- Cifrado ADFGVX:
             1.2.1.- Ejemplo de cifrado y descifrado.
             1.2.2.- Criptoanálisis Painvin.
             1.2.3.- Ejemplo de cifrado ADFGVX y criptoanálisis Painvin.
             1.2.4.- Otro ejemplo de criptoanálisis al cifrado ADFGVX:
                        1.2.4.1.- Planteamiento del ejemplo.
                        1.2.4.2.- Longitud de la clave utilizada en el cifrado.
                        1.2.4.3.- Orden de los caracteres de la clave antes de su ordenación alfabética.
                        1.2.4.4.- Análisis de frecuencias.

      1.3.- Cifrado de Hill:
              1.3.1.- Ejemplo de cifrado y descifrado.
              1.3.2.- Criptoanálisis Gauss Jordan.            

     1.4.- Cifrado cinta móvil:
              1.4.1.- Método de cifrado y ejemplo de criptograma.

     1.5.- La máquina Enigma:
             1.5.1.- ¿Qué era y cómo funcionaba?.
                         1.5.1.1.- Primera aproximación.
                         1.5.1.2.- Segunda aproximación.
                         1.5.1.3.- Tercera aproximación.
             1.5.2.- Vulnerabilidades de la máquina Enigma.
             1.5.3.- Criptoanálisis de la máquina Enigma:
                        1.5.3.1.- El ataque polaco:
                                      1.5.3.1.1.- Deducción del cableado de los rotores y del reflector.  
                                      1.5.3.1.2.- El catálogo de características.
                                      1.5.3.1.3.- Cambios en la operativa de la máquina (la "clave de sesión").
                                      1.5.3.1.4.- Nuevo método de criptoanálisis: las hojas Zygalski.
                                      1.5.3.1.5.- Ejemplo de criptoanálisis basado en las hojas Zygalski.
                                      1.5.3.1.6.- La bomba criptológica de Marian Rejewski.
                        1.5.3.2.- El criptoanálisis británico (Bletchley Park):
                                      1.5.3.2.1.- La bomba de Turing.
                                      1.5.3.2.2.- Nueva versión mejorada: la bomba de Turing-Welchman.
             1.5.4.- Cronología de la máquina Enigma:
                        1.5.4.1.- La pequeña historia de la máquina Enigma (I) (1918 - 1939).
                        1.5.4.2.- La pequeña historia de la máquina Enigma (II) (1918 hasta hoy).   
             1.5.5.- La máquina Enigma en el cine:
                        1.5.5.1.- "The Imitation Game" - Descifrando Enigma (I).
                        1.5.5.2.- "The Imitation Game" - Descifrando Enigma (II).

2.- Criptología moderna:

     2.1.- El algoritmo RSA:
             1.2.1.- Cifrado y descifrado.
             1.2.2.- Autenticidad (identidad del emisor e integridad del mensaje).

3.- Otros:

     3.1.- Criptología para todos:
              3.1.1.- Conceptos básicos de criptografía y algunos criptosistemas clásicos.
              3.1.2.- Conceptos básicos de criptoanálisis y algunos criptosistemas clásicos.
              3.1.3.- Conceptos básicos de criptografía moderna.

     3.2.- ¿Sabías que...?:
              3.2.1.- Los jeroglíficos egipcios.
              3.2.2.- El cifrado de los caballeros templarios.
              3.2.3.- El cifrado francmasón.
              3.2.4.- El cifrado en la literatura:
                         3.2.4.1.- "El escarabajo de oro" (Edgar Allan Poe).
                         3.2.4.2.- "El símbolo perdido" (Dan Brown).
             3.2.5.- Criptosistemas utilizados en la guerra civil española:
                         3.2.5.1.- La cinta móvil.
                         3.2.5.2.- Ejemplo de criptoanálisis de un mensaje cifrado con la cinta móvil:
                                       3.2.5.2.1.- Primera fase del criptoanálisis.
                                       3.2.5.2.2.- Segunda fase del criptoanálisis.
Iré actualizando este índice a medida que vaya escribiendo nuevas entradas.

martes, 1 de noviembre de 2016

Gimnasia mental (XXVI): la cesta y los huevos

Dos problemas muy similares a resolver utilizando el teorema chino del resto.

1.- Una cesta tiene un conjunto de huevos: si se sacan en grupos de 2, de 3, de 4, de 5 y de 6 queda siempre un huevo en la cesta. En cambio, si se sacan en grupos de 7 no queda ninguno.

2.- Otra cesta tiene un conjunto de huevos: si se sacan en grupos de 2 queda 1, si en grupos de 3 quedan 2, si en grupos de 4 quedan 3, si en grupos de 5 quedan 4, si en grupos de 6 quedan 5 y si se sacan en grupos de 7 no queda ninguno.

¿Cuál es el número más pequeño de huevos que hay en cada cesta?.

Bueno, hay diferentes maneras de resolverlo, además de empleando el teorema chino del resto, del que he hablado al principio del post.

Voy poniendo algunas de ellas, incluidas las que se van proponiendo en forma de comentario a este post. 

a) La fuerza bruta, es decir, "a lo bestia”:

Para cada número entero positivo comprobamos el resto de dividirlo entre 2, 3, 4, 5, 6 y 7 hasta encontrar el menor de ellos cuyo resto sea 1 y 0 cuando se divide dicho número por 2 y 7, respectivamente, y para la primera cesta 1 cuando se divide entre 3, 4, 5 y 6, y para la segunda 2, 3, 4 y 5 cuando se divide entre 3, 4, 5 y 6, respectivamente.

Un método nada original y muy poco eficiente, pero si no tenemos ganas de pensar y con el ordenador…
Por tanto, en la primera cesta hay un número mínimo de 301 huevos y en la segunda de 119.

b) Refinando un poco la fuerza bruta:

Llamando X al número de huevos de cada una de las dos cestas, es evidente que de ambos enunciados se deduce que X es un múltiplo de 7 y, además, que es impar.

Teniendo en cuenta lo indicado anteriormente, para cada X múltiplo de 7 e impar buscamos el número entero positivo más pequeño de X cuyo resto de dividirlo entre 3, 4, 5 y 6 sea 1, para la primera cesta, y sea 2, 3, 4 y 5, respectivamente, para la segunda.

Algo mejoramos, ya que restringimos bastante los casos a examinar.
Por tanto, en la primera cesta hay un número mínimo de 301 huevos y en la segunda de 119.

c) Utilizando el mínimo común múltiplo: que es el método que propone mi tocayo Mikel en el primer comentario a este post.

El mínimo común múltiplo de 2, 3, 4, 5, 6 es: mcm(2,3,4,5,6) = 22 x 31 x 51 = 60.

Con este método seremos mucho más eficientes en la búsqueda de las soluciones.

c.1) Primera cesta: X - 1 debe ser múltiplo de 2, 3, 4, 5 y 6 y, por tanto, de 60.

Para cada X = 60Y + 1 (donde Y = 1, 2, 3…) buscamos el valor más pequeño de X que sea múltiplo de 7. Para Y = 5: X = 60 x 5 + 1 = 301, que es múltiplo de 7.
Por tanto, en la primera cesta hay un número mínimo de 301 huevos.

c.2) Segunda cesta: X + 1 debe ser múltiplo de 2, 3, 4, 5 y 6 y, por tanto, de 60.

Para cada X = 60Y - 1 (donde Y = 1, 2, 3…) buscamos el valor más pequeño de X que sea múltiplo de 7. Para Y = 2: X = 60 x 2 - 1 = 119, que es múltiplo de 7. 
Por tanto, en la segunda cesta hay un número mínimo de 119 huevos.

d) Aplicando el teorema chino del resto:

El enunciado del teorema sería algo así: si n1, n2, …, ni son números enteros positivos primos entre sí (mcd(ni,nj) = 1 para i ¹ j) y a1, a2,.. ai son números enteros, entonces el sistema de congruencias simultáneas X º aj (mod nj), donde 1 £ j £ i, tiene solución única módulo N (N = n1 x n2 x … x ni) dada por:
Dicho esto, siendo X el número de huevos de cada una de las dos cestas, podemos plantear los siguientes sistemas de congruencias simultáneas.

d.1) Primera cesta:

º 1 mod 2, es decir, 2 debe dividir a X - 1.

º 1 mod 3, es decir, 3 debe dividir a X - 1.

º 1 mod 4, es decir, 4 debe dividir a X - 1.

º 1 mod 5, es decir, 5 debe dividir a X - 1.

º 1 mod 6, es decir, 6 debe dividir a X - 1.

º 0 mod 7, es decir, 7 debe dividir X - 0.

Para poder aplicar el teorema chino del resto los módulos deben ser coprimos entre sí, por lo que nos quedamos con el siguiente sistema de congruencias simultáneas:

º 1 mod 3.

º 1 mod 4.

º 1 mod 5.

º 0 mod 7.

Y ahora calculamos el valor de X de la siguiente forma:

N = 3 x 4 x 5 x 7 = 420.

N1 = N / n1 = 420 / 3 = 140; (N1)-1 = 2.

N2 = N / n2 = 420 / 4 = 105; (N2)-1 = 1.

N3 = N / n3 = 420 / 5 = 84; (N3)-1 = 4.

N4 = N / n4 = 420 / 7 = 60; (N4)-1 = 2.

X = 1 x 140 x 2 + 1 x 105 x 1 + 1 x 84 x 4 + 0 x 60 x 2 = 280 + 105 + 336 = 721 mod 420 = 301.

Comprobamos que 2 y 6 dividen a 300 y, por tanto, en la primera cesta hay un número mínimo de 301 huevos.

d.2) Segunda cesta:

º 1 mod 2, es decir, 2 debe dividir a X - 1.

º 2 mod 3, es decir, 3 debe dividir a X - 2.

º 3 mod 4, es decir, 4 debe dividir a X - 3.

º 4 mod 5, es decir, 5 debe dividir a X - 4.

º 5 mod 6, es decir, 6 debe dividir a X - 5.

º 0 mod 7, es decir, 7 debe dividir X - 0.

Para poder aplicar el teorema chino del resto los módulos deben ser coprimos entre sí, por lo que nos quedamos con el siguiente sistema de congruencias simultáneas:

º 2 mod 3.

º 3 mod 4.

º 4 mod 5.

º 0 mod 7.

Y ahora calculamos el valor de X de la siguiente forma:

N= 3 x 4 x 5 x 7 = 420.

N1 = N / n1 = 420 / 3 = 140; (N1)-1 = 2.

N2 = N / n2 = 420 / 4 = 105; (N2)-1 = 1.

N3 = N / n3 = 420 / 5 = 84; (N3)-1 = 4.

N4 = N / n4 = 420 / 7 = 60; (N4)-1 = 2.

X = 2 x 140 x 2 + 3 x 105 x 1 + 4 x 84 x 4 + 0 x 60 x 2 = 560 + 315 + 1.344 = 2.219 mod 420 = 119.

Comprobamos que 2 divide a 118 y 6 divide a 114 y, por tanto, en la segunda cesta hay un número mínimo de 119 huevos.

jueves, 27 de octubre de 2016

Criptografía (XXXVI): el algoritmo RSA (II)

En el post anterior puse un ejemplo de cifrado utilizando el algoritmo RSA y decía que este algoritmo se utiliza, además, para validar por parte del receptor la autenticidad del mensaje, es decir, tanto que la persona que lo ha enviado es el emisor legítimo (es quien dice ser), como que el mensaje no ha sido interceptado y alterado por un tercero (integridad), y en éste trataré sobre esto último.

Para ello es necesario hablar en primer lugar de las funciones hash, que obtienen un resumen del mensaje en forma de número, de tamaño fijo mucho menor que el mensaje original, asociado unívocamente a éste (es prácticamente imposible encontrar otro mensaje que dé como resultado el mismo resumen) e irreversible (es prácticamente imposible obtener el mensaje a partir del resumen), y que después el emisor cifrará con su clave privada.

1.- Para firmar digitalmente un mensaje (Mel emisor obtiene un resumen del mismo mediante una función hash (h), que como ya he dicho lo representa de una manera única.

2.- El emisor cifra el resumen del mensaje (h(M)) utilizando su clave privada (d, n). Ésto sólo puede hacerlo él mismo, ya que es el único que posee su clave privada, y cualquiera que tenga la clave pública del emisor (e, n) estará en condiciones de descifrar el resumen, que llamaremos firma o signatura (S), y verificarla. Para ello, el emisor realiza la siguiente operación: S = (h(M))d mod n.

3.- El emisor envía al receptor el mensaje y la firma digital cifrados (C, S). Ya comenté en el post anterior cómo se cifran y descifran los mensajes y en éste me centro únicamente en la firma.

4.- El receptor descifra ambos y obtiene M y h(M). En el caso de la firma utilizando la clave pública del emisor y mediante la siguiente expresión: h(M) = Se mod n.

5.- El receptor calcula ahora el resumen del mensaje que ha descifrado en el paso anterior, es decir, realiza la siguiente operación: h'(M).

6.- Si h'(M) = h(M) se acepta la firma como válida, en caso contrario se rechaza. Si la firma es válida el receptor se asegura de que el mensaje ha sido originado realmente por el emisor y de que el mensaje no ha sido interceptado y alterado por un tercero.

Ejemplos de funciones hash son los algoritmos MD5 y SHA-3.

miércoles, 26 de octubre de 2016

Criptografía (XXXV): el algoritmo RSA (I)

En este post me propongo contar, como siempre de la forma más comprensible de la que sea capaz, lo que voy aprendido sobre RSA, un algoritmo de cifrado asimétrico que debe su nombre a las iniciales de los apellidos de sus tres inventores: Ronald Rivest, Adi Shamir y Leonard Adleman, que lo desarrollaron en 1977.

Como en todo criptosistema de clave pública un usuario dispone de dos claves: una pública, que debe estar en posesión de cualquier persona que pretenda enviarle un mensaje cifrado, y otra privada, que el usuario utilizará para descifrar los mensajes que le envíen y que sólo él posee. Es decir, el emisor cifrará el mensaje con la clave pública del receptor y sólo éste podrá descifrarlo utilizando su clave privada.

El algoritmo RSA sirve también para firmar digitalmente un mensaje, es decir, para que el receptor valide que el emisor es realmente quien lo ha enviado y para comprobar que no ha sido interceptado y alterado por terceros (integridad).

Decía en este post que, debido a que los criptosistemas asimétricos presentan una complejidad de cálculo significativamente mayor que los criptosistemas simétricos, que los hace significativamente más lentos que estos últimos, en la práctica se utilizan sistemas criptográficos híbridos.
Es decir, el texto en claro se cifra mediante una clave de sesión, correspondiente a cada mensaje particular y generada aleatoriamente, y la clave de sesión se cifra utilizando la clave pública del receptor, de tal manera que sólo el receptor puede descifrar la clave de sesión mediante su clave privada (criptografía asimétrica) y posteriormente descifrar el texto en claro mediante la clave de sesión (criptografía simética).

Una vez dicho esto, los mensajes a enviar se representan mediante números y la seguridad del algoritmo RSA se basa en el elevado coste computacional de encontrar los dos factores primos de un número muy grande resultado del producto de éstos, y se considera que será seguro hasta que no se conozca una forma eficiente de hallarlos. Por tanto, se trata de un problema que es muy fácil de resolver en un sentido (multiplicar dos número primos), pero cuya resolución en sentido contrario (conocido el producto hallar esos dos factores) se vuelve inabordable en un tiempo razonable para números lo suficientemente grandes, por mucha potencia de cálculo de la que se disponga con los ordenadores actuales.

Como digo, en el algoritmo RSA las cláves pública y privada se calculan a partir del producto de dos números primos grandes, de la siguiente manera:

1.- Se eligen aleatoriamente dos números primos grandes (p y q) y se calcula el producto (n). Es decir, n = pq.

2.- Se calcula la función de Euler del módulo n, que para dos números primos es: j(n) = (p - 1)(q - 1).

3.- Se escoge un número e, en el intervalo 1 < ej(n)que sea coprimo o primo relativo con j(n), es decir, de forma que el máximo común divisor de ej(n) sea 1 (mcd(e, j(n))= 1). La clave pública será (e, n).

4.- Se calcula, mediante el algoritmo extendido de Euclides, el inverso mutiplicativo (d) de e módulo j(n), es decir, que satisfaga: de º 1 mod (j(n)). La clave privada será (d, n).

El cifrado del mensaje (m) lo realiza el emisor con la clave pública del receptor mediante la siguiente expresión: c = me mod (n), y el receptor lo descifra con su clave privada mediante la expresión: m = cd mod (n).

¿Fácil, no?, pues yo no me he enterado de nada y como he dicho que lo que voy a intentar explicar de una forma comprensible pongo el siguiente ejemplo para ver si lo entiendo (con números pequeños, para facilitar su comprensión por parte de torpes como yo).

1.- Para generar un par de claves:

1.1.- Elijo dos números primos, por ejemplo: p = 53 y q = 997, y calculo su producto: n = pq = 53 x 997 = 52.841.

1.2.- Calculo 
j(n) = (p - 1)(q - 1) = (53-1)(997-1) = 52 x 996 = 51.792.

1.3.- Escojo un número natural e que sea primo relativo con 51.792, por ejemplo 7, ya que el máximo común divisor de 7 y 51.792 es 1. La clave pública será (7, 52.841).

1.4.- Calculo el inverso multiplicativo (d) de e módulo j(n):

a) 51.792 = 7.398  x 7 + 6.

b) 7 = 1 x 6 + 1.

c) 1 = 7 - 1 x 6.

d) 6 = 51.792 - 7.398 x 7.

e) 1 = 7 - 1 x (51.792 -7.398 x 7) = -1 x 51.792 + 7.398 x 7 + 7 = -1 x 51.792 + 7.399 x 7.

Por tanto, el inverso multiplicativo (d) de e módulo j(n) es 7.399 y la clave privada será (7.399, 52.841).

2.- Y ahora voy intentar ver si los resultados obtenidos me permiten cifrar y descifrar un mensaje (M) con ese par de claves. Hay que recordar lo que he dicho anteriormente sobre criptografía híbrida, es decir, que RSA se utiliza sólo para cifrar la clave de sesión y no para cifrar el texto en claro, porque en la práctica es un sistema mucho más lento que la criptografía simétrica. Por tanto, aunque sería posible cifrar también el propio texto en claro siempre que se transforme previamente la información de éste en un conjunto de números, lo que voy a hacer no pasa de ser un mero ejercicio teórico para ver si lo he comprendido correctamente.

a) Texto en claro (M) = "CIFRADORSA".

b) Como el módulo es 52.841, que en binario es: 1100111001101001 ((1 x 20) + (0 x 21) + (0 x 22) + (1 x 23) + (0 x 24) + (1 x 25) +  (1 x 26) + (0 x 27) + (0 x 28) + (1 x 29) + (1 x 210) + (1 x 211) + (0 x 212) + (0 x 213) +  (1 x 214) + (1 x 215)  = 1 + 8 + 32 + 64 + 512 +1.024 +2.048 + 16.384 + 32.768 = 52.841), es decir, 16 bits, deberemos cifrar bloques con una longitud máxima de 16 bits (2 bytes) inferiores a dicho valor. Por ejemplo, cifraremos los siguientes bloques: "CI", "FR", "AD", "OR", "SA" convirtiendo cada uno de ellos en un bloque de 2 bytes (1 byte por cada carácter).

c) Para ello, por ejemplo, transformamos esos bloques a números según el valor decimal de cada uno de ellos en código ASCII, de la siguiente manera:

"CI" = 01000011 01001001 = m1 = 17.225.
"FR" = 01000110 01010010 = m2 = 18.002. 
"AD" = 01000001 01000100 m3 = 16.708.
"OR" = 01001111 01010010 m4 = 20.306.
"SA" = 01010011 01000001 m5 = 21.313.

d) Cifrado: el emisor utiliza para ello la clave pública del receptor (7, 52.841), obteniéndose los siguientes bloques del criptograma:

c1 = 17.2257 mod 52.841 = 1.855.
c2 = 18.0027 mod 52.841 = 25.633.
c3 = 16.7087 mod 52.841 = 52.061.
c4 = 20.3067 mod 52.841 = 16.353.
c5 = 21.3137 mod 52.841 = 20.222.

e) Descifrado: el receptor utiliza su clave privada (7.399, 52.841):

m1 = 1.8557.399 mod 52.841 = 17.225 = 01000011 01001001 = "CI".
m2 = 25.6337.399 mod 52.841 = 18.002 = 01000110 01010010 = "FR".
m3 = 52.0617.399 mod 52.841 = 16.708 = 01000001 01000100 = "AD".
m4 16.3537.399 mod 52.841 = 20.306 = 01001111 01010010 = "OR".
m5 20.2227.399 mod 52.841 = 21.313 = 01010011 01000001 = "SA".

Texto en claro (M) = "CIFRADORSA".

En el siguiente post, teniendo en cuenta todo lo comentado en éste, hablaré de cómo puede el receptor validar la autenticidad del mensaje recibido, tanto identidad del emisor como integridad (no modificación) del mensaje.