Tras las noticias referentes al sistema de computación cuántica Orión (posible fake) en TSS queremos informar sobre las bases de la teóricas del aparatito, sus posibles aplicaciones y todo estos “rollos” que nos encantan.
Dividiremos el asunto en 3 partes/post para intentar dar una visión lo más global (¡y pragmática!) posible de las teorías cuántica de la información y de la computación:
1.- Criptografía Clásica
2.- Criptografía Cuántica
3.- Ordenador Cuántico
En este primer artículo explicaremos las particularidades de las funciones de una sola vía, es decir, algoritmos característicos de la criptografía de clave pública. Para ello veremos el funcionamiento del sistema RSA ( acrónimo de Rivest, Adleman y Shamir, creadores del mismo allá por 1977).
Utilizaremos matemáticas básicas y argumentaciones relativamente simples (en vista a las quejas por el "andamiaje" matemático que Ergodic utilizó en el caso de Google).
Cómo se generan las claves:
Aquí tenemos un ejemplo de cifrado/descifrado con RSA. Los parámetros usados aquí son excepcionalmente pequeños y simplemente orientativos con respecto a los que maneja el algoritmo. Realmente la fortaleza de este tipo de encriptación consiste en generar núemeros tan sumamente grandes que su factorización es imposible de realizar en tiempos lo suficientemente cortos (problema NP).
Veamos nuestro ejemplo:
- Elegimos el primer número primo Privado: p=7
- Elegimos el segundo número primo Privado: q=19
Multiplicamos, en nuestro caso obtendremos 133
En nuestro caso será 108
Exponente Público, será 5. No puede ser coprimo del número anterior.
Exponente Privado, será 65
- d lo hayamos de la siguiente forma:
con lo que obtenemos d=(1+(6*18)*3)/5=65
Podemos publicar e y n ya que son la clave pública.
Debemos guardar en lugar seguro d y n pues son la llave privada.
Cifrado de los mensajes:
Bob (emisor) quiere enviar a Alicia un mensaje secreto que solo ella pueda leer.
Supongamos que Bob desea enviar un mensaje M a Alicia. Usará la siguiente función:
Bob ahora tiene m, y conoce n y e, mientras Alicia fue avisada. El entonces calcula el texto cifrado c correspondiente a m. Bob transmite c a Alicia.
La función de cifrado es:
encrypt(m) = me(mod n) = m5(mod 133)
Donde c es el texto cifrado. Para cifrar el valor del texto sin cifrar “6”, nosotros calculamos:
encrypt(6) = 65(mod 133) = 62
Descifrado de mensajes:
Alicia recibe c de Bob, y conoce su clave privada d. Ella puede recuperar m de c por el siguiente procedimiento:
Dado m, ella puede recuperar el mensaje M. El descifrado procede de la siguiente forma:
Donde m es el texto sin cifrar La función de descifrado es:
decrypt(c) = cd(mod n) = c65(mod 133)
Para descifrar el valor del texto cifrado, nosotros calculamos:
decrypt(62) = 6265(mod 133) = 6
Conclusiones:
Todo el "truco" consiste en buscar números lo suficientemente grandes como para que el timepo necesario para desencriptar el mensaje sea inabordable para los ordenadores actuales y futuros. Las claves RSA son normalmente entre 1024-2049 bits de longitud. Algunos expertos creen que las claves de 1024 bits podrían comenzar a ser débiles en poco tiempo; con claves de 4096 bits podrían ser rotas en un futuro. Por lo tanto, si n es suficientemente grande el algoritmo RSA es seguro.
La única forma de romper fácilmente estos mecanismos (es decir, en un corto período de tiempo), sería crear un computador cuántico, aspecto que se tratará en la tercera parte de este “ciclo” de artículos.
La comunidad científica estaba espectante ante la llegada de un nuevo artículo sobre criptografía cuántica de ErTano.
Todavía recuerdo aquella conferencia que ErTano ofreció en la universidad… todos comprendimos el significado de la computación cuántica de la mano de aquel insigne profesor, formado en la UCLA (Universidad de la Cuecas en Langreo, Asturias), doctorado en el MIT (Mieres Institute of Technology), donde, por cierto, mantuvo un romance con una tal Alice… Recuerdo cómo sostenía la atención del público preguntando cuánto eran 7 por 7 a los que estaban sentados en la primera fila… en fin, todo un referente para nosotros y los mecánicos (cuánticos) del futuro.
Desde la Alemania Profunda esperaremos con impaciencia sus próximos artículos.
Un tema muy interesante, sí señor…
Un libro recomendable sobre el tema, que hasta los de letras entendemos: The Code Book, de Simon Singh…
Mítica conferecnia la de ErTano, a la que asistí en pantacas y con la camiseta de la selección brasileña de fútbol. También había gente de Boca, del Milán y del Madrid… es que teníamos pachanga luego…
Breve y bueno (dos veces bueno entonces no?)
Aunque deberías aclarar que Bob usa la clave pública de Alicia (es decir, su e y n) para que ella pueda desencriptarlo con su clave privada (n y d). Me pareció poco claro (hasta parecía que Bob encriptaba con su propia clave pública).
Ah, realmente recomendable la lectura del libro de Simon Singh
1&2.-Gracias a Migg y a Hutz. ¡Ellos estuvieros allí!
3.-Ok, probablemente amplíe el artículo con tus aclaraciones.
No quería que el artículo fuese muy espeso (es lunes y este artículo sólo es el primero de una serie que considero más importante).
Muchas gracias.
Muy bueno. Y lo más interesante empieza ahora… quedo a la espera de las siguientes entregas ; ). Vas a arrearles a los de D-Wave?.
En TSS somos unos geeks un tanto malvados.
¡¡¡Arrear leches e improperios se ha dicho!!!
kaluza seguro que hará un buen trabajo en la la segunda parte.
Dos cosas:
1) Enhorabuena por el artículo, pero no comentas que existen maneras ‘ferpectas’ de cifrar como los one-time pads.
2) Quizir, mezclar Quantum computing con Quantum Cryptography me parece que puede confundir a la gente (quizir, en quantum cryptography el medio es el que previene la lectura, puedes mandar todo en texto plano), o en el mejor de los casos hacer pensar a la gente que el unico problema no polinómico interesante es la factorización de primos
Este Quevedín…… es un crack.
La idea inicial es:
1) Artículo de corte clásico
2) Artículo de corte «novedoso», explicar ideas de criptografía más de vanguardia
3) Artículo «rompedor» para explicar lo difícil que es crear un ordenador cuántico y las posibilidades que tendría si existiese.
Sobre tu primera apreciación, no se nada sobre los one-time pads.
Mándame un mail sobre el tema y es probable que caiga otro artículo sobre el tema.
Gracias por tus «pinceladas». Quevedín siempre está hilando fino
La verdad es que no entendí mucho…
Me perdí en el hecho que phi(n) en realidad es phi(p,q) y que, además, si p=7 y q=19 => phi(p,q)=108, no 103.
Además, eso de 1
Además, eso de 1
Además, eso de 1 «menor que» e «menor que» phi no lo entiendo… Me parece que escatimar en explicaciones matemáticas hace que se entienda menos. Por lo menos eso me pasa a mí.
Es más fácil decir «se define una función blablabla», «se escoge un número x tal que blablabla». Por lo menos eso para mí es más claro que sólo poner igualdades y desigualdades.
Saludos.
PD: sorry que salga tantas veces, pero parece que hay problemas con el caracter «menor que».
En efecto, phi es 108.
El número ha de ser un núermo entre 1 y phi, que no sea coprimo:
108/2=54, no vale
108/3=36, no vale
108/4=27, tampoco
108/5=21.6 este si vale, no es coprimo
Quería relaizar una expliación breve y concisa (pero parece que al interntarlo ha sido incompleta).
Mis disculpas