¿Alguna vez te has preguntado qué sería de Internet sin la Criptografía? Ya no sólo se trata de mantener tu intimidad cuando consultas tu correo electrónico. Gracias a la Criptografía es posible hacer usos de Internet como el comercio electrónico o transacciones bancarias de una forma segura. Con el uso de certificados digitales es posible realizar transacciones con entidades públicas y hasta el DNI incorpora una de estas firmas electrónicas.
Cabe preguntarse si realmente son seguras. Obviamente existen diferentes ataques del tipo man in the middle que son muy efectivos, pero ¿se puede atacar directamente el problema de romper el cifrado de una comunicación digital?
Vamos a hacer un experimento para tratar de sacar algunas conclusiones.
Aunque existen diferentes métodos de cifrado, el rey indiscutible en Internet es RSA. Se trata de un sistema de cifrado asimétrico donde hay dos claves: Una privada que sólo conoce la dueña de la clave (pongamos que se llama Alicia) y una clave pública que conoce todo el mundo. Si alguien (pongamos que se llama Bob) quisiera enviar un mensaje cifrado a Alicia, podría cifrarlo con la clave pública de ésta y así, sólo Alicia podría descifrarla con su clave privada.
RSA nos brinda otra serie de características que nos permiten no sólo cifrar mensajes, sino generar firmas que certifiquen que un mensaje es de quién dice ser. No vamos a entrar en demasiado detalle ya que existe bastante literatura al respecto, y lo que aquí nos interesa es estudiar la robustez del cifrado.
En mi otro blog escribí ya hace tiempo un artículo sobre RSA que puedes consultar si quieres conocer los detalles de funcionamiento del mismo.
A modo de resumen te recuerdo que la fortaleza de RSA se basa en el problema de la factorización de números enteros. No se sabe a ciencia cierta qué tipo de complejidad tiene este problema. Parece claro que no es de tipo P, pero tampoco NP-completo. En general, y hasta que se demuestre otra cosa, lo supondremos un problema NP.
Como ya se ha dicho, RSA tiene dos claves. Los pasos para calcularlas son los siguientes.
Si Bob quiere enviar un mensaje cifrado a Alicia sólo tiene que partir el texto en bloques y representarlos como números enteros para realizar la siguiente operación sobre cada bloque:
bloque_cifrado = M^E mod N
Alicia por su parte podrá descifrar el mensaje con su clave privada de la siguiente manera:
M = bloque_cifrado^D mod N
Es decir, que si interceptamos el mensaje de Bob, la única manera (que sepamos) de descifrarlo es tener la clave privada. La pregunta del millón es ¿se puede conseguir la clave privada a partir de la pública?
La respuesta es sencilla: en teoría sí. Aunque en la práctica la cosa se complica un poco.
¿Cómo sería el proceso?
Con la clave pública tenemos n y e. Es necesario factorizar n para conseguir p y q. Una vez obtenidos calculamos: phi(N) = (p-1)*(q-1)
Finalmente calculamos el inverso de e mod phi(n), con lo que obtenemos d. La clave privada es (n,d).
¿Fácil no?
Si no me crees vamos a hacer la prueba con un certificado digital autofirmado que he creado para la ocasión.
Si quieres hacer pruebas tu mismo con el certificado, puedes copiar el texto anterior (todo) y guardalo en un archivo llamado cert.pem
Vamos a usar openssl para obtener información del certificado.
La parte que nos interesa es la clave pública, que está compuesta por el módulo (N) y el exponente (E). Es este caso N es:
01:64:55:a9:07:aa:52:7f:77:a3:ad:a8:a2:84:ca:
89:fc:aa:34:27:30:d8:1e:9a:01:57:62:6d:48:0f:
a9:32:d5:58:30:ae:e6:6f:1b:92:4b:61:03:37:4a:
c9
Y E es 0x10001 en hexadecimal (65537 en decimal).
Si queremos obtener p y q debemos empezar por factorizar N para obtener estos dos números primos. Precisamente, en la dificultad de factorizar un valor tan grande es donde radica la fortaleza de RSA. Para tratar de factorizarlo vamos a usar un método muy eficiente llamado Criba especial del cuerpo de números (special number field sieve, SNFS). En concreto usaremos una implementación de Jason Stratos Papadopoulos llamada msieve.
Nótese cómo hemos editado el módulo N como un valor hexadecimal que comprende msieve quitando el carácter :.
41 horas más tarde, en un iMac dual core hemos obtenido el siguiente resultado:
Es decir, ya tenemos los siguientes valores decimales para p y q:
p = 1195078297408071670062867234011814103034097953789536883
q = 2735395455347575783048721615040574052878491576701795027
Para realizar los cálculos he usado el paquete matemático SAGE.
Ya podemos calcular phi(N):
phi(N) = (p-1)*(q-1) = 3269011743514557801630370122176217187665256597037828217522270221163621767264574952415112744144580866631148932
El inverso de PHI(N) es: d=2774098419451029679992569607165880630666695845770462735821002767139399493208711658735775138709444510699167613
Lo he calculado con sage usando: d=inverse_mod(65537, phi)
Por lo tanto, la clave privada de Alicia es (n, d):
(3269011743514557801630370122176217187665256597037828221452743973919269220376163801467500900057170397122480841, 2774098419451029679992569607165880630666695845770462735821002767139399493208711658735775138709444510699167613)
Como se puede comprobar, hemos transformado N de su valor hexadecimal a decimal usando la siguiente instrucción en SAGE:
n=int("016455a907aa527f77a3ada8a284ca89fcaa342730d81e9a0157626d480fa932d55830aee66f1b924b6103374ac9", 16)
Te estarás preguntando que cómo es posible que con un ordenador personal y en sólo 41 horas hayamos podido romper la seguridad de RSA. Bueno, la cosa tiene truco. Si te fijas en la clave pública, es de sólo 361 bits. Un valor muy bajo. Lo habitual es que la clave sea, al menos, de 1024 bits. Y en el caso del DNI electrónico español, la clave es de 2048 bits.
Estarás pensando que de 361 a 1024 tampoco hay tanta diferencia, y que usando ordenadores más potentes, una clave de 1024 bits puede romperse fácilmente en un tiempo razonable ¿no?
Pues la realidad es que no. Cada vez que añadimos un bit a nuestra clave, la dificultad para factorizarla crece exponencialmente. Cada vez que añades un bit a la clave, se dobla la dificultad para romperla. Es decir, que si en vez de 361 bits la hacemos de 362, tardaríamos 82 horas en vez de 41. Imagina con 1024 bits…
En la práctica, el crecimiento de la complejidad no sería exactamente como lo acabo de describir, pero nos permite hacernos una idea intuitiva de como crece la fortaleza de la clave con su tamaño.
La moraleja de todo esto es que RSA es un sistema suficientemente seguro siempre y cuando usemos una clave lo suficientemente grande y con sus factores p y q, así como d y e, adecuadamente seleccionados. En la práctica, un valor de 1024 bits puede considerarse seguro aunque, por supuesto, si la clave es de 2048 bits será aun mejor, aunque también necesitaremos más potencia de cálculo para el cifrado/descifrado de la información.
Cabe preguntarse si realmente son seguras. Obviamente existen diferentes ataques del tipo man in the middle que son muy efectivos, pero ¿se puede atacar directamente el problema de romper el cifrado de una comunicación digital?
Vamos a hacer un experimento para tratar de sacar algunas conclusiones.
Aunque existen diferentes métodos de cifrado, el rey indiscutible en Internet es RSA. Se trata de un sistema de cifrado asimétrico donde hay dos claves: Una privada que sólo conoce la dueña de la clave (pongamos que se llama Alicia) y una clave pública que conoce todo el mundo. Si alguien (pongamos que se llama Bob) quisiera enviar un mensaje cifrado a Alicia, podría cifrarlo con la clave pública de ésta y así, sólo Alicia podría descifrarla con su clave privada.
RSA nos brinda otra serie de características que nos permiten no sólo cifrar mensajes, sino generar firmas que certifiquen que un mensaje es de quién dice ser. No vamos a entrar en demasiado detalle ya que existe bastante literatura al respecto, y lo que aquí nos interesa es estudiar la robustez del cifrado.
En mi otro blog escribí ya hace tiempo un artículo sobre RSA que puedes consultar si quieres conocer los detalles de funcionamiento del mismo.
A modo de resumen te recuerdo que la fortaleza de RSA se basa en el problema de la factorización de números enteros. No se sabe a ciencia cierta qué tipo de complejidad tiene este problema. Parece claro que no es de tipo P, pero tampoco NP-completo. En general, y hasta que se demuestre otra cosa, lo supondremos un problema NP.
Como ya se ha dicho, RSA tiene dos claves. Los pasos para calcularlas son los siguientes.
- Elegimos dos números primos a los que llamaremos P y Q. Estos primos han de ser enteros muy grandes para que la clave sea segura.
- Efectuamos la operación N=P*Q. N es el módulo de la clave.
- Calculamos la función phi(N)=(P-1)*(Q-1), que nos dice el número de enteros más pequeños que N que son primos relativos de N.
- Buscamos un entero E menor que phi(N) y además primo relativo con phi(N). Este será el exponente de la clave pública.
- Buscamos un entero D tal que D*E=1 mod phi(N) (inversa del modulo Phi(N)). Este valor es el exponente de la clave privada.
- La clave pública es el par (N, E) y la privada es el par (N, D).
Si Bob quiere enviar un mensaje cifrado a Alicia sólo tiene que partir el texto en bloques y representarlos como números enteros para realizar la siguiente operación sobre cada bloque:
bloque_cifrado = M^E mod N
Alicia por su parte podrá descifrar el mensaje con su clave privada de la siguiente manera:
M = bloque_cifrado^D mod N
Es decir, que si interceptamos el mensaje de Bob, la única manera (que sepamos) de descifrarlo es tener la clave privada. La pregunta del millón es ¿se puede conseguir la clave privada a partir de la pública?
La respuesta es sencilla: en teoría sí. Aunque en la práctica la cosa se complica un poco.
¿Cómo sería el proceso?
Con la clave pública tenemos n y e. Es necesario factorizar n para conseguir p y q. Una vez obtenidos calculamos: phi(N) = (p-1)*(q-1)
Finalmente calculamos el inverso de e mod phi(n), con lo que obtenemos d. La clave privada es (n,d).
¿Fácil no?
Si no me crees vamos a hacer la prueba con un certificado digital autofirmado que he creado para la ocasión.
-----BEGIN CERTIFICATE----- MIICOjCCAfagAwIBAgIJAKYinSdmBS95MA0GCSqGSIb3DQEBBQUAMIGKMQswCQYD VQQGEwJFUzEOMAwGA1UECAwFU3BhaW4xDzANBgNVBAcMBk1hbGFnYTENMAsGA1UE CgwEQUNNRTERMA8GA1UECwwIU2VjdXJpdHkxETAPBgNVBAMMCGZha2VjZXJ0MSUw IwYJKoZIhvcNAQkBFhZmYWtlY2VydEBmYWtlZG9tYWluLmVzMB4XDTEzMDcxMzEw MzAxOFoXDTEzMDgxMjEwMzAxOFowgYoxCzAJBgNVBAYTAkVTMQ4wDAYDVQQIDAVT cGFpbjEPMA0GA1UEBwwGTWFsYWdhMQ0wCwYDVQQKDARBQ01FMREwDwYDVQQLDAhT ZWN1cml0eTERMA8GA1UEAwwIZmFrZWNlcnQxJTAjBgkqhkiG9w0BCQEWFmZha2Vj ZXJ0QGZha2Vkb21haW4uZXMwSTANBgkqhkiG9w0BAQEFAAM4ADA1Ai4BZFWpB6pS f3ejraiihMqJ/Ko0JzDYHpoBV2JtSA+pMtVYMK7mbxuSS2EDN0rJAgMBAAGjUDBO MB0GA1UdDgQWBBS6c3y1YYZ32CV8zeepe3tgUmlFCzAfBgNVHSMEGDAWgBS6c3y1 YYZ32CV8zeepe3tgUmlFCzAMBgNVHRMEBTADAQH/MA0GCSqGSIb3DQEBBQUAAy8A APet8r4gU+E/xES7MuShiNIVaE0xIo0kxv69zOco6M3law6y9/HOcDqayzQDdg== -----END CERTIFICATE-----
Si quieres hacer pruebas tu mismo con el certificado, puedes copiar el texto anterior (todo) y guardalo en un archivo llamado cert.pem
Vamos a usar openssl para obtener información del certificado.
alberto$ openssl x509 -noout -in cert.pem -text
Certificate:
Data:
Version: 3 (0x2)
Serial Number: 11971303552045100921 (0xa6229d2766052f79)
Signature Algorithm: sha1WithRSAEncryption
Issuer: C=ES, ST=Spain, L=Malaga, O=ACME, OU=Security, CN=fakecert/emailAddress=fakecert@fakedomain.es
Validity
Not Before: Jul 13 10:30:18 2013 GMT
Not After : Aug 12 10:30:18 2013 GMT
Subject: C=ES, ST=Spain, L=Malaga, O=ACME, OU=Security, CN=fakecert/emailAddress=fakecert@fakedomain.es
Subject Public Key Info:
Public Key Algorithm: rsaEncryption
Public-Key: (361 bit)
Modulus:
01:64:55:a9:07:aa:52:7f:77:a3:ad:a8:a2:84:ca:
89:fc:aa:34:27:30:d8:1e:9a:01:57:62:6d:48:0f:
a9:32:d5:58:30:ae:e6:6f:1b:92:4b:61:03:37:4a:
c9
Exponent: 65537 (0x10001)
X509v3 extensions:
X509v3 Subject Key Identifier:
BA:73:7C:B5:61:86:77:D8:25:7C:CD:E7:A9:7B:7B:60:52:69:45:0B
X509v3 Authority Key Identifier:
keyid:BA:73:7C:B5:61:86:77:D8:25:7C:CD:E7:A9:7B:7B:60:52:69:45:0B
X509v3 Basic Constraints:
CA:TRUE
Signature Algorithm: sha1WithRSAEncryption
00:f7:ad:f2:be:20:53:e1:3f:c4:44:bb:32:e4:a1:88:d2:15:
68:4d:31:22:8d:24:c6:fe:bd:cc:e7:28:e8:cd:e5:6b:0e:b2:
f7:f1:ce:70:3a:9a:cb:34:03:76
La parte que nos interesa es la clave pública, que está compuesta por el módulo (N) y el exponente (E). Es este caso N es:
01:64:55:a9:07:aa:52:7f:77:a3:ad:a8:a2:84:ca:
89:fc:aa:34:27:30:d8:1e:9a:01:57:62:6d:48:0f:
a9:32:d5:58:30:ae:e6:6f:1b:92:4b:61:03:37:4a:
c9
Y E es 0x10001 en hexadecimal (65537 en decimal).
Si queremos obtener p y q debemos empezar por factorizar N para obtener estos dos números primos. Precisamente, en la dificultad de factorizar un valor tan grande es donde radica la fortaleza de RSA. Para tratar de factorizarlo vamos a usar un método muy eficiente llamado Criba especial del cuerpo de números (special number field sieve, SNFS). En concreto usaremos una implementación de Jason Stratos Papadopoulos llamada msieve.
./msieve -v 0x016455a907aa527f77a3ada8a284ca89fcaa342730d81e9a0157626d480fa932d55830aee66f1b924b6103374ac9
Nótese cómo hemos editado el módulo N como un valor hexadecimal que comprende msieve quitando el carácter :.
41 horas más tarde, en un iMac dual core hemos obtenido el siguiente resultado:
prp55 factor: 1195078297408071670062867234011814103034097953789536883 prp55 factor: 2735395455347575783048721615040574052878491576701795027
Es decir, ya tenemos los siguientes valores decimales para p y q:
p = 1195078297408071670062867234011814103034097953789536883
q = 2735395455347575783048721615040574052878491576701795027
Para realizar los cálculos he usado el paquete matemático SAGE.
Ya podemos calcular phi(N):
phi(N) = (p-1)*(q-1) = 3269011743514557801630370122176217187665256597037828217522270221163621767264574952415112744144580866631148932
El inverso de PHI(N) es: d=2774098419451029679992569607165880630666695845770462735821002767139399493208711658735775138709444510699167613
Lo he calculado con sage usando: d=inverse_mod(65537, phi)
Por lo tanto, la clave privada de Alicia es (n, d):
(3269011743514557801630370122176217187665256597037828221452743973919269220376163801467500900057170397122480841, 2774098419451029679992569607165880630666695845770462735821002767139399493208711658735775138709444510699167613)
Como se puede comprobar, hemos transformado N de su valor hexadecimal a decimal usando la siguiente instrucción en SAGE:
n=int("016455a907aa527f77a3ada8a284ca89fcaa342730d81e9a0157626d480fa932d55830aee66f1b924b6103374ac9", 16)
Te estarás preguntando que cómo es posible que con un ordenador personal y en sólo 41 horas hayamos podido romper la seguridad de RSA. Bueno, la cosa tiene truco. Si te fijas en la clave pública, es de sólo 361 bits. Un valor muy bajo. Lo habitual es que la clave sea, al menos, de 1024 bits. Y en el caso del DNI electrónico español, la clave es de 2048 bits.
Estarás pensando que de 361 a 1024 tampoco hay tanta diferencia, y que usando ordenadores más potentes, una clave de 1024 bits puede romperse fácilmente en un tiempo razonable ¿no?
Pues la realidad es que no. Cada vez que añadimos un bit a nuestra clave, la dificultad para factorizarla crece exponencialmente. Cada vez que añades un bit a la clave, se dobla la dificultad para romperla. Es decir, que si en vez de 361 bits la hacemos de 362, tardaríamos 82 horas en vez de 41. Imagina con 1024 bits…
En la práctica, el crecimiento de la complejidad no sería exactamente como lo acabo de describir, pero nos permite hacernos una idea intuitiva de como crece la fortaleza de la clave con su tamaño.
La moraleja de todo esto es que RSA es un sistema suficientemente seguro siempre y cuando usemos una clave lo suficientemente grande y con sus factores p y q, así como d y e, adecuadamente seleccionados. En la práctica, un valor de 1024 bits puede considerarse seguro aunque, por supuesto, si la clave es de 2048 bits será aun mejor, aunque también necesitaremos más potencia de cálculo para el cifrado/descifrado de la información.
Comentarios
Publicar un comentario