martes, 14 de febrero de 2017

Criptografía (XLVII): Descifrado RSA, ¿un "trabajo de chinos"?

Uno de los estereotipos con relación a los chinos es que éstos son muy laboriosos, pacientes y meticulosos en el trabajo, por lo que entiendo que el dicho popular "trabajo de chinos" hace referencia a aquel que es largo, tedioso y/o complicado.

Pero, ¿qué tiene que ver ésto con el descifrado utilizando el algoritmo RSA?.

Me explico: tal y como sabemos, en criptografía híbrida, el algoritmo RSA se emplea para cifrar la clave de sesión (un número aleatorio correspondiente a cada mensaje particular) con la clave pública del receptor y que después este último descifra utilizando su clave privada (criptografía asimétrica) para, a su vez, poder después descifrar el criptograma empleando la clave de sesión (criptografía simétrica).

Supongamos que para cifrar el texto en claro se utiliza el algoritmo de criptografía simétrica AES (longitud de la clave de 256 bits). Por tanto, para cifrar la clave de sesión (k) mediante RSA se realizará la siguiente operación: c = ke mod n, donde k tiene un tamaño de 256 bits, para e se recomienda utilizar valores relativamente pequeños para forzar que d tenga un tamaño en bits del orden del módulo, y n de 2048 bits.

Por consiguiente, para el descifrado de la clave de sesión se realizará la siguiente operación: k = cd mod n, donde c puede tener un tamaño de 2048 bits, d será del orden de 2048 bits y n de 2048 bits, lo que efectivamente tiene pinta de ser, por costoso, un auténtico "trabajo de chinos".

Bueno, pues que lo resuelvan los chinos..., y efectivamente también así es, ya que para simplificar los cálculos en el descifrado se suele utilizar el teorema chino del resto.

Utilizando este teorema y mediante los números primos p y q cuyo producto es el módulo (n), los cálculos a realizar en el descifrado, tal y como veremos más adelante, serán sensiblemente más rápidos. Nótese que los números p y q son secretos y, por tanto, que ésto sólo puede realizarlo el receptor del mensaje.

Para ello, junto con su clave privada (d, n), el receptor debe guardar los números primos p y q, y, además, para aplicar de forma óptima este teorema en el descifrado, los siguientes valores:

1.- p1 = p-1 mod q

2.- dp = d mod (p – 1)

3.- dq = d mod (q  1)

De esta forma sólo debemos calcular estos valores un sola vez y evitamos tener que hacerlo en cada descifrado.

Ahora, por lo que he entendido, el descifrado se realizaría de la siguiente manera:

1.- Calculamos:

1.1.- cp = c mod pcq = c mod q

1.2.- k1 = cpdp mod pk2 = cqdq mod q

2.- Resultado: k = k1 + p (((k2  k1) p1) mod q)

Veamos un ejemplo, pero esta vez con números un poco más grandes de aquellos que vengo utilizando en esta serie de posts, aunque todavía mucho más pequeños de los que se emplean actualmente en RSA. De esta forma veremos mejor la ventaja que supone aplicar este teorema en el descifrado.

Previamente al ejemplo, genero un par de claves y realizo la operación de cifrado de una clave de sesión (k):

1.- p = 26.317; q = 30.269; n = p q26.317 x 30.269 = 796.589.273j(n) = (p  1)(q  1) = 26.316 x 30.268 = 796.532.688; e = 65.537; mcd(e, j(n)) = mcd(65.537, 796.532.688) = 1; d = inv(e, j(n)) = inv(65.537, 796.532.688) = 329.140.817 

2.- Clave pública del receptor (e, n): (65.537, 796.589.273)

3.- Clave privada del receptor (d, n): (329.140.817, 796.589.273)

4.- Clave de sesión (k) a cifrar mediante RSA: 505.316.708

5.- Cifrado: c = ke mod n = 505.316.70865.537 mod 796.589.273 = 670.835.545

Y ahora el ejemplo: el receptor tiene guardados, junto a su clave privada (329.140.817, 796.589.273), p = 26.317, q = 30.269 y  los siguientes valores previamente calculados: p1 = p-1 mod q = 17.685; dp = d mod (p – 1) = 329.140.817 mod 26.316 = 6.605; dq = d mod (q  1) = 329.140.817 mod 30.268 = 6.585, con lo que, si lo he entendido bien, el descifrado sería como sigue:

1.- cp = c mod p = 670.835.545 mod 26.317 = 15.215; cq = c mod q =  670.835.545 mod 30.269 = 13.967

2.- k1 = cpdp mod p = 15.2156.605 mod 26.317 = 3.991; k2 = cqdq mod q =  13.9676.585 mod 30.269 = 6.022

3.- k = k1 + p (((k2  k1) p1) mod q) = 3.991 + 26.317 (((6.022  3.991) 17.685) mod 30.269) = 3.991 + 26.317 x 19.201 = 505.316.708

Y, por tanto, parece que "los chinos han hecho bien su trabajo" :), ya que como se puede observar el resultado del descifrado coincide con la clave de sesión (k) que se ha cifrado.

Nótese que el paso más costoso del descifrado es el paso 2, en el que se realizan dos operaciones de exponenciación modular con bases con una longitud de 14 bits, exponentes de 13 bits y módulos de 15 bits, mientras que si no utilizáramos este teorema el descifrado se realizaría mediante la siguiente operación: k = cd mod n = 670.835.545329.140.817 mod 796.589.273 = 505.316.708, es decir, una operación de exponenciación modular con una base de longitud 30 bits, un exponente de 29 bits y un módulo de 30 bits.

Con lo que tal y como se observa, la ventaja fundamental de aplicar este teorema consiste en que mientras la clave privada (d) tiene una longitud del orden del tamaño del módulo (en nuestro caso 29 y 30 bits, respectivamente), dp y dq tienen una longitud aproximadamente de la mitad (en nuestro caso 13 bits) y, además, estos dos últimos valores pueden calcularse previamente una sola vez y guardarse para ser utilizados en descifrados posteriores.   

sábado, 11 de febrero de 2017

Criptografía (XLVI): RSA y los números primos grandes, ¿"la pescadilla que se muerde la cola"?

Tal y como he venido comentado en la serie de posts dedicados al algoritmo RSA, quizá el criptosistema de clave pública más utilizado en la actualidad, éste se basa en la elección de dos números primos aleatorios lo suficientemente grandes (actualmente del orden de 200 dígitos decimales cada uno de ellos) para generar el par de claves (pública y privada) correspondiente a cada usuario.

También decía en un post anterior que no es trivial conocer si un número lo suficientemente grande es primo o compuesto y que, para ello, podíamos caer en la "tentación" de intentar factorizarlo. Craso error, pues tal y como también he venido insistiendo en esta serie de posts, nos enfrentaríamos precisamente con aquello en lo que se basa la fortaleza de este cifrado: actualmente ésto no es posible en un tiempo mínimamente razonable.

Entonces: ¿Cómo seleccionamos aleatoriamente los dos números primos grandes para generar el par de claves correspondiente a un usuario?, es decir, ¿Cómo "determinamos" que los números primos aleatorios elegidos son primos sin intentar factorizarlos?, ¿Es la "pescadilla que se muerde la cola"?.

Pues no, tal y como también decía en este post, afortunadamente existen algoritmos probabilísticos que nos pueden decir con un alto nivel de confianza si un número dado es primo, aunque no haya certeza matemática (100%) al respecto.

Veamos uno de los tests de primalidad más utilizados, el de Miller-Rabiny algunos ejemplos.

Si no lo he entendido mal, el algoritmo para aplicar este test a un número dado para conocer si éste es primo (con un alto nivel de confianza) o compuesto podría ser el siguiente:
Veamos algunos ejemplos:

1.- Partiendo del ejemplo que vengo utilizando en esta serie de posts: ¿es el 997 un número primo?:

Aunque con un número tan pequeño es trivial conocer si es primo o no (ya sabemos que sí lo es) veamos que ocurre aplicando el test de primalidad de Miller-Rabin:
2.- Pero quizá no sea tan trivial saber si el 286.467.789.841 es un número primo. Veamos que ocurre en esta ocasión.
Y como para demostrar que un número es compuesto no hay mejor demostración que enseñar los factores no triviales cuyo producto da ese número: 298.817 x 958.673 = 286.467.789.841.

3.- Y, finalmente: ¿es el 275.415.303.169 un número primo?:
En este caso, el test nos dice que probablemente (con un muy elevado nivel de confianza) este número es primo, aunque como digo no se trata de un test determinista y por tanto creérselo es una cuestión de fe :), aunque yo sé que efectivamente sí lo es.

lunes, 6 de febrero de 2017

Criptografía (XLV): ¿Sabías que...? (IX)

Quizá la aplicación práctica más "palpable" de los números primos se dé actualmente en la criptografía, ya que en ellos descansa en gran medida el secreto de nuestras más preciadas comunicaciones en Internet.

Así, los números primos son la base del algoritmo RSA, posiblemente el criptosistema de clave pública más utilizado en la actualidad, en el cuál el par de claves (pública y privada) correspondiente a cada usuario se calcula a partir de dos números primos aleatorios lo suficientemente grandes.

La fortaleza de este algoritmo reside en el elevado coste computacional de hallar los dos factores primos de un número lo suficientemente grande resultado del producto de ambos, aunque este último sea público y, por tanto, pueda ser conocido por cualquiera, ya que esta tarea no es factible en un tiempo razonable con los algoritmos de factorización conocidos que se pueden implementar hasta la fecha y con la potencia de cálculo de los ordenadores actuales, por mucha de esta última de la que se disponga. Por tanto, esos números primos son fundamentales para salvaguardar la confidencialidad de nuestras comunicaciones en Internet y deben mantenerse en secreto, ya que su conocimiento por parte de terceras personas haría inútil cualquier esfuerzo al respecto.

Sin embargo, pese a esa "palpable" aplicación práctica en la criptografía que comentaba al principio, ni siquiera somos conscientes de que utilizamos todo esto en nuestra vida cotidiana en nuestras relaciones por Internet con las administraciones públicas, entidades bancarias, etc.

Ya he escrito en este blog diferentes entradas sobre el algoritmo RSA (ver primer post) y aquí me centraré en los aspectos básicos de los números primos que a mí me parecen más curiosos y de éstos aplicados a la criptografía.

Dicho ésto, a todos nos enseñaron en el colegio que los números primos son aquellos números naturales mayores que 1 que únicamente son divisibles por sí mismos y por la unidad, y que los números compuestos, en contraposición a éstos, son aquellos números naturales que tienen otro u otros divisores diferentes además de sí mismos y de 1, pero, al menos que yo recuerde, sin darnos mayores explicaciones ni de su historia, ni de para qué sirven.

1.- ¿Es el 1 un número primo o compuesto?:

Pues parece ser que ni una cosa ni otra, pero sólo por convención y de forma relativamente reciente, es decir y en mi opinión, porque "estorba que sea una cosa u otra" :), ya que si fuera primo o compuesto habría que volver a formular importantes teoremas dando explicaciones adicionales.

2.- ¿Desde cuando se conoce la existencia de los números primos?:

No se sabe con certeza, ya que hay quien afirma que este conocimiento podría remontarse bastantes miles de años atrás, pero sí se puede datar con seguridad, como mínimo, alrededor del año 300 a.C.

Así, Euclides define en esa época los números primos y, poco más tarde, Eratóstenes idea un método para hallar todos los números primos menores o iguales que un número dado.

Por tanto, al menos, hace ya más de 2.000 años que los matemáticos vienen estudiando los números primos. Quizá les fascinaron porque, tal y como se dice, son los "átomos" de los que están constituidos todos los números naturales, es decir, cualquier número natural se puede descomponer en un producto de factores primos.

La criba de Eratóstenes para hallar todos los números primos menores o iguales que uno dado consistía en lo siguiente:

1.- Se escriben en forma de tabla todos los números naturales hasta aquel del que queremos hallar todos los números primos menores o iguales que él, incluido este último.

2.- Se tacha el 1, porque como ya he dicho no es un número primo.

3.- Se va hasta el siguiente número no tachado y, si el cuadrado de éste no es mayor que el número del que queremos hallar todos los números primos menores o iguales que él, este número es declarado como primo y se tachan todos los números de la tabla que sean múltiplo de él, y se vuelve a repetir este paso 3.

4.- Cuando el cuadrado del siguiente número no tachado sea mayor que el número del que queremos hallar todos los números primos menores o iguales que él, se declaran como primos todos los números no tachados de la tabla.

Ejemplo: supongamos que queremos obtener todos los números primos menores o iguales a 100. Gráficamente:
Creo que el algoritmo podría ser, más o menos, el siguiente:
En nuestro caso:
3.- ¿Cuántos números primos hay?:

Euclides fue el primero en formular una demostración sobre la infinitud de los números primos: "El conjunto formado por los números primos es infinito".

4.- ¿Es "fácil" determinar si un número dado es primo o compuesto?:

A la condición de que un número sea primo se le denomina primalidad y, por tanto, a la cuestión de determinar si un número dado es primo o compuesto se le conoce como el problema de la primalidad.

Así, a primera vista, éste parece un problema "fácil" (más que a "fácil" la pregunta debería hacer referencia a poco costoso) y basándonos en la criba de Eratóstenes podríamos probar a dividir el número impar en cuestión (evidentemente éste debe ser impar, ya que el único número primo par es el 2) entre todos los números enteros impares positivos comprendidos entre el 3 y el entero más próximo por defecto a la raíz cuadrada del número dado, pero esto es claramente inaceptable cuando el número en cuestión es lo suficientemente grande.

Una vez que desechamos este método, la siguiente "tentación" que podemos tener para dar respuesta a esta pregunta es pensar en factorizar dicho número con métodos más modernos, pero, tal y como he comentado al principio de este post, ésto, de momento, tampoco es posible en un tiempo razonable para números lo suficientemente grandes, como es el caso de RSA.

¿Es ésto importante?. Pues sí, ya que conviene recodar que RSA, el criptosistema de clave pública más utilizado en la actualidad, se basa precisamente en seleccionar aleatoriamente dos números primos grandes (cada uno de ellos del orden de 200 dígitos decimales) para generar el par de claves para cada usuario (pública y privada).

Entonces: ¿cómo se hace en la práctica para seleccionar dos números primos grandes?. Afortunadamente, existen algoritmos probabilísticos, mucho más eficientes que los de factorización, que nos pueden decir con un alto grado de confianza si un número dado es primo o compuesto, ésto es lo que se conoce como tests de primalidad, es decir, se trata de algoritmos no deterministas (no hay certeza matemática del resultado obtenido) que intentan verificar la hipótesis de que un determinado número es compuesto y si no lo consiguen aceptan que es primo con un cierto nivel de confianza.

En un post posterior, para no hacer éste excesivamente largo, compartiré lo que que voy aprendiendo sobre los tests de primalidad y pondré algunos ejemplos.  

5.- ¿Existen diferentes tipos de números primos?:

Hay multitud de clases o tipos de números primos, es decir, de subconjuntos del conjunto de números primos formados por aquellos que comparten unas determinadas características y que reciben un nombre colectivo para identificarlos. Así, entre muchas otras clases, nos encontramos, por ejemplo, con los números primos: pitagóricos, de Wieferich, etc., pero quizá los tipos de números primos con mayor aplicación en la criptografía son los primos fuertes y los primos seguros.

También, como en el caso anterior, en un post posterior compartiré lo que voy aprendiendo sobre los tipos de números primos con aplicación en la criptografía,

jueves, 26 de enero de 2017

Criptografía (XLIV): ataque a RSA mediante factorización (III)

En este post continúo con el pequeño repaso a los métodos de factorización más conocidos: en esta ocasión me referiré al método p - 1 de Pollard.

Al igual que los otros dos métodos de los que he hablado en posts anteriores (Fermat y rho de Pollard), se trata también de un método de factorización de propósito específico, es decir, el tiempo necesario para descomponer el módulo (n) en sus dos factores primos (p y q) depende de las características de estos últimos, en contraposición con los métodos de factorización de propósito general, en el que el tiempo de ejecución depende únicamente del tamaño del módulo.

Por lo que he entendido, el algoritmo podría ser el siguiente (como siempre, si estoy equivocado agradecería las oportunas correcciones a modo de comentario en esta entrada):
En nuestro caso (con el ejemplo que vengo utilizando en esta serie de posts):
En posteriores posts continuaré con este pequeño repaso a los métodos de factorización más conocidos.

lunes, 23 de enero de 2017

Criptografía (XLIII): ataque a RSA mediante factorización (II)

Continúo con el pequeño repaso a algunos de los métodos de factorización más conocidos que inicié en el post anterior y que, en teoría, podrían emplearse para atacar al algoritmo de cifrado RSA.

Digo en teoría porque, como ya he venido insistiendo en esta serie de post, los métodos conocidos y que es posible implementar hasta la fecha no resuelven la factorización del módulo (n) en sus dos factores primos (p y q) en tiempo polinomial y, por tanto, son ineficientes para abordar este problema en un tiempo razonable cuando se trata de números lo suficientemente grandes (ya dije en el post anterior que actualmente se emplea un tamaño para el módulo de 2.048 bits).

En esta ocasión le toca el turno al método de factorización rho de Pollard.

Como siempre utilizaré el ejemplo que vengo usando en esta serie de posts (n = pq = 53 x 997 = 52.841).
En nuestro caso:
Como vemos, en tan sólo 6 iteraciones hemos conseguido factorizar el módulo (52.841) en sus dos factores primos (53 y 997); de forma significativamente más eficiente, en este caso, que con el método de Fermat al que me referí en el post anterior, pero, por lo que voy aprendiendo, no se puede afirmar rotundamente que un método sea más eficiente que otro, sino que esto depende del número concreto a factorizar.

Me pregunto: ¿cuál de estos dos métodos sería más eficiente en el ejemplo que puse en el post anterior en el que los dos factores primos estaban muy cercanos entre sí (n = pq = 991 x 997 = 988.027)?. Asunto que dejo como ejercicio para quien quiera resolverlo (como siempre se admiten conclusiones, etc. en forma de comentario a esta entrada).

En cualquier caso, comentar que se considera que el método de factorización rho de Pollard es eficiente para factorizar números compuestos con factores menores de 1012, lo que está muy por debajo de los utilizados actualmente por RSA.

En posteriores posts continuaré con este pequeño repaso a los métodos de factorización más conocidos.