REVISTA .SEGURIDAD | 1 251 478, 1 251 477 | REVISTA BIMESTRAL

Criptografía cuántica – Parte II

Implementación del algoritmo de Shor

Recordando el ejemplo de la aplicación teórica del algoritmo de Shor descrito en la anterior entrega de este artículo, el intruso Eve calculó los factores primos p = 5 y q = 3 para el producto de ellos n = 15 y de esta forma obtuvo la llave privada del remitente Bob y descifró el mensaje siguiendo el algoritmo RSA. Siete años después de que Peter Shor publicara su algoritmo[1], en 2001, científicos del Centro de Investigación Almaden de IBM, en San José California, Estados Unidos, consiguieron ejecutar el algoritmo de Shor en una computadora cuántica basada en Resonancia Nuclear Electromagnética, calculando correctamente los factores primos del producto n = 15, utilizando 108 moléculas, cada una de ellas de 7 átomos[2]. A continuación se explicará cómo es que con una computadora cuántica se pudo lograr este desarrollo.

Los bits

La electrónica digital es la base de las computadoras actuales y a través de ésta, el procesamiento de la información se realiza sobre la unidad básica de información, el bit (binary digit o dígito binario), el cual almacena solamente dos posibles valores por unidad de tiempo, comúnmente interpretados como “0” o “1”, nunca los dos valores al mismo tiempo. A estos dos valores lógicos, dependiendo del contexto en que se trabaje, se les otorga una interpretación, por ejemplo, si se trabaja en un ambiente geofísico, el “1” podría interpretarse como el registro de un sismo detectado de ondas p, y el “0” como un registro de un sismo detectado de ondas s. Es posible utilizar varios bits al mismo tiempo para así formar valores de mayor tamaño, por ejemplo, la siguiente tabla muestra la representación en bits de los números decimales 3 y 5:

Las operaciones en una computadora están dadas por el uso de las proposiciones lógicas, por ejemplo la negación (not), la disyunción (or) o la conjunción (and)[3]. Si se quiere hacer el producto de 3 y 5, se hará uso de la proposición lógica conjunción.

La computadora toma los valores en binario de ambos números, ejecuta sobre ellos la operación y obtiene el resultado. Los procesadores solamente pueden ejecutar una operación a la vez por unidad de tiempo. Tomando el ejemplo anterior, supongamos que ahora queremos obtener el valor q de la ecuación 3*q = 15, con una computadora actual habría que encontrar los posibles valores de q probando cada valor posible a través de una operación lógica a la vez, en la siguiente tabla podemos observar los resultados para los posibles valores de q:

Se realizarían 6 operaciones, una por cada ciclo del procesador, para encontrar el resultado correcto; otra opción sería contar con un procesador para cada operación, por lo que se deberá considerar tener al menos 6 procesadores trabajando simultáneamente para obtener el resultado correcto en un solo ciclo del procesador. Es por eso que el cálculo de los factores planteados en el artículo anterior con uno o varios procesadores actuales tomaría un tiempo considerablemente grande.

Los qubits

El término qubit proviene de quantum bit o bit cuántico. La alta velocidad de procesamiento de las computadoras cuánticas en comparación con las computadoras actuales, se debe al uso de propiedades descubiertas en partículas subatómicas que permiten tener a la vez, por ejemplo, todos los valores posibles para un cómputo dado.

Como los bits, un qubit puede tener dos posibles estados, 0 ó 1, para diferenciarlos de los bits clásicos (que se usan en la electrónica digital) se utiliza la notación de Dirac (usada para representar el estado físico de un sistema cuántico[4]), quedando de la forma |0>  o |1> (en alguna literatura relacionada se les suele nombrar como ket uno y ket cero); pero un qubit puede encontrarse en un estado de superposición arbitraria (combinación de sus dos posibles estados), es decir, el qubit puede almacenar tanto |0> o |1> al mismo tiempo durante el cómputo y antes de que se mida su valor[5], esto permitiría realizar múltiples operaciones simultáneamente, pero una vez medido el estado del qubit, éste permanecerá en ese estado.

El estado de superposición del qubit se puede representar por la función:

Ψ= a|0>  + b|1>

En donde los coeficientes a y b son números complejos.

La probabilidad de que se encuentre con un valor |0> o |1> está dada por la norma al cuadrado, es decir:

|a|2+|b|2 = 1

Mientras no se mida el estado del qubit, éste puede permanecer en el estado de superposición, cuando el valor sea medido, el qubit saldrá del estado de superposición, entonces, se tendrá una cierta probabilidad de que se encuentre con un valor |0>  o con un valor |1>. Esto se debe a que todo sistema cuántico posee como propiedad fundamental un carácter probabilístico[6].

De la misma forma que los bits clásicos, los qubits pueden formar arreglos para representar la información, si tomamos el ejemplo de la búsqueda del valor q para la ecuación 3*q = 15 de los bits clásicos anteriores, podemos tener en un solo procesador cuántico todos los posibles valores de q al mismo tiempo con solamente 3 qubits:

Ψ= x0|000>  + x1|001> + … +  x5|101> +  x6|110> +  x7|111>

En donde la función Ψ representa el estado del qubit, los coeficientes xn son números complejos y la norma de xn corresponde a la probabilidad de que la computadora se encuentre en ese estado, es decir:

·         la probabilidad de que la computadora se encuentre en el estado |000> es de |x0|2

·         la probabilidad de que la computadora se encuentre en el estado |001> es de |x1|2

·         …

·         la probabilidad de que la computadora se encuentre en el estado |101> es de |x5|2

·         …

Una vez que se realice la medición del resultado correcto y descartando las opciones erróneas[7], los qubits quedarán como:

Ψ=|101>

Y se romperá el estado de superposición, quedando el valor |101> definido. A este concepto se le conoce como paralelismo cuántico, en general la idea de paralelismo cuántico es recorrer al mismo tiempo todos los posibles valores que podría tomar un cómputo, en este caso un cálculo de una operación de multiplicación.[8]

La superposición cuántica da la posibilidad de que con un arreglo de n qubits se puedan representar 2n valores simultáneos[9]. Por ejemplo, un cómputo sobre 300 qubits lograría el mismo efecto que 2300 cómputos simultáneos sobre bits clásicos[10].

Con esta capacidad de cómputo de las computadoras cuánticas se podrá aplicar con eficiencia el algoritmo de Shor para encontrar en un tiempo razonablemente corto los coeficientes p y q necesarios para calcular las llaves de cifrado y descifrado del algoritmo RSA, el cual es el soporte para protocolos y esquemas de comunicación y cifrado como SSL o PKI.

El espín

Una propiedad del mundo físico que puede ser utilizada para representar al qubit es el espín (del inglés spin, girar), es una propiedad intrínseca del electrón (tal como lo es la masa y la carga eléctrica). Es común encontrar en la literatura relacionada la analogía entre la rotación de un objeto del mundo macroscópico, por ejemplo, un trompo o el movimiento de rotación de la tierra e imaginar al espín como una cantidad (momento magnético) del campo magnético que genera el electrón que gira sobre su propio eje; aunque esta propiedad debe considerarse como un concepto cuántico, sin una analogía detallada de la mecánica clásica.

Dependiendo de la orientación del campo magnético es como se representa el espín, siempre con una cantidad de este campo bien definida. Por ejemplo, el valor del espín del electrón es de ½, y dentro del átomo, si está alineado con el espín del núcleo, se dice que el espín tiene orientación hacia arriba ↑, y si está alineado en la dirección contraria tiene espín hacia abajo ↓. Esta propiedad del electrón se puede usar para representar el valor de un qubit, el valor de |0> puede ser orientación hacia arriba o si tiene orientación hacia abajo se dice que tiene el valor |1>. Se puede representar de la siguiente forma:

a|↑> + b|↓>

a|0> + b|1>

Fortalecimiento en la distribución de claves, el protocolo BB84

Hasta el momento se ha hablado del tema, solamente desde el punto de vista de la resolución por medio de una computadora cuántica de un algoritmo de cifrado actual, como lo es RSA, pero con los descubrimientos sobre el comportamiento de las partículas, también se han planteado el uso de sus propiedades cuánticas para fortalecer las comunicaciones. Un ejemplo de esto es en el envío 

de claves a través del protocolo BB84, creado en 1984 por Charles Bennet y Gilles Brassard[11].

Una forma de implementación de los qubits es a través de fotones, con ellos se pueden obtener cuatro posibles polarizaciones horizontal, vertical, diagonal derecha o diagonal izquierda, es en esta partícula de luz en que se basa el planteamiento del protocolo BB84.

Consideremos de nuevo a tres actores, Alice, Bob y el intruso Eve. En el ejemplo del artículo anterior, Eve interceptaba ilegítimamente la conversación sin que Alice o Bob lo advirtieran.

Para este ejemplo, Alice envía a través de un canal cuántico a Bob un bit al que le aplicó una base, la cual es un estado de polarización de un fotón (polarización horizontal, vertical, diagonal derecha o diagonal izquierda) y es usada como un filtro; entonces Alice envía a Bob |1>--, un bit 1 con una polarización “–“ (polarización horizontal, 0o sobre un plano), Bob aplicará una base elegida de forma previa y aleatoria al bit recibido de Alice, si Bob eligió una base con polarización horizontal, el resultado de aplicarla a lo recibido por Alice será un 1, que es el bit enviado por Alice. En cambio, si aplica una base con polarización vertical, el resultado será 0, que no corresponde al bit enviado por Alice, es decir se produjo un error, en cualquier caso Bob conservará su resultado en secreto.

Una vez que ha finalizado la transmisión de los datos por este canal cuántico, Alice y Bob comparan sus bases públicamente, es decir, por un canal clásico, se quedarán solamente con la información que obtuvieron cuando ambos midieron sobre la misma base, es decir, cuando no hubo errores, este dato será la clave entre ambos[12].

La siguiente tabla ilustrará mejor el concepto, fue tomada del trabajo realizado por Gustavo Rigolin y Andrés Anibal Rieznik. Las primeras cinco líneas corresponden a una transmisión a través de un canal cuántico, las siguientes cinco líneas corresponden a una transmisión por un canal clásico. Y la última es la clave compartida que usarán durante su comunicación. El ejemplo considera la pérdida de bits durante la transmisión.

La base A corresponde a una polarización horizontal, es decir que el fotón tiene una polarización de 0o respecto al plano y la base B corresponde a una polarización diagonal derecha, es decir que el fotón tiene una polarización de 45 o respecto al plano.

Con este planteamiento, se podrá resolver uno de los principales objetivos de la criptografía, la distribución segura de claves criptográficas entre dos partes que inicialmente no comparten ninguna información secreta[14].Las mediciones de Bob hubieran salido erróneas, a pesar de haber elegido la misma base de Alice, si Eve hubiera interceptado los datos al utilizar este protocolo. Alice y Bob eligen unos datos al azar, que anuncian públicamente, con el fin de calcular el porcentaje de error (razón de los datos que no coincidieron), si el error está por encima del 10%, eliminan sus datos y podrían volver a realizar el protocolo[13]. Con esto se tiene certeza sobre la privacidad de su clave secreta al percatarse si es que hubo un intruso durante la comunicación.

Las computadoras cuánticas

En la investigación científica con frecuencia existe una brecha entre el planteamiento de los estudios, los resultados teóricos y su recreación en el mundo real, porque cuando se trata de crear lo propuesto en la teoría, se encuentran complicaciones de tipo técnico. Y la búsqueda del desarrollo de una computadora cuántica no es la excepción.

Se han estudiado y probado diversas técnicas para la creación de una computadora cuántica. Pero, aunque exista esta diversidad de posibilidades de sistemas cuánticos, las computadoras cuánticas deberán cumplir con ciertas características para ser consideradas como tales. En el año 2000, David P. DiVincenzo, investigador de IBM, propuso cinco criterios principales para considerar un sistema cuántico como computadora cuántica[15].

  1. Tener caracterizada la noción de qubit y poder ensamblar varios de ellos.
  2. Contar con un conjunto de compuertas cuánticas primitivas que permitan realizar cualquier algoritmo.
  3. Poder iniciar una lista de qubits en estados puros determinados.
  4. Poder ejecutar la operación de toma de mediciones.
  5. Que los tiempos de coherencia excedan los de aplicación de las compuertas cuánticas primitivas[16].

A partir del cumplimiento de estos criterios es que se han creado diversas propuestas. A continuación se enlistan algunas[17].

·         Resonancia Nuclear Electromagnética

·         Cavidad electrodinámica cuántica

·         Trampas de iones

·         Átomos neutros

·         Técnicas ópticas

·         Superconductividad

·         Técnicas de estado sólido

Como se mencionó al principio, el desarrollo de la computadora cuántica en 2001, por científicos del Centro de Investigación Almaden de IBM, se basó en la Resonancia Nuclear Electromagnética. Este dispositivo está formado por moléculas que se encuentran en una solución líquida a temperatura ambiente, almacena los qubits en el espín de los átomos de cada molécula y las manipula a través de radiación electromagnética. Los núcleos de estas moléculas tienen espín ½ y tienen orientaciones hacia “arriba” o hacia “abajo”.

La factorización de 15 como el producto de 3 por 5 se logró con un conjunto de moléculas, siete espines en cada molécula actuando como siete qubits, sin embargo, el modelo no podría extenderse a más de 10 qubits[18].

Comentarios finales

Otra motivación para el estudio de la computación cuántica se debe a la creación de componentes electrónicos cada vez más pequeños, llegará el momento en que, por el tamaño de éstos, empezarán a aparecer fenómenos de la mecánica cuántica en esos desarrollos.

La computación cuántica es un área que irá en crecimiento, probablemente las primeras computadoras comerciales serán una combinación de la tecnología de la electrónica digital y de la computación cuántica. Con el desarrollo de esta área se abre un mundo de posibilidades, porque las implementaciones no se limitan a una sola técnica.

De la misma forma como avanzan las implementaciones de las primeras computadoras cuánticas, será necesario que la criptografía cuántica avance y pruebe los desarrollos actuales para que pueda ofrecer la confidencialidad y la integridad a este nuevo cómputo.

Por último, enlisto tres enlaces referentes a investigaciones de IBM con el cómputo cuántico.

IBM Says Practical Quantum Computers are Close

IBM Paves The Way Towards Scalable Quantum Computing

IBM Research Advances Device Performance for Quantum Computing

.   .   .

Quiero agradecer a Tonatiuh Sánchez Neri y a Félix Hernández Fuentes por sus acertados comentarios y observaciones a este trabajo, a la editora de la revista Jazmín López Sánchez y al diseñador Abraham Ávila por su apoyo y paciencia para la publicación del mismo; también a la profesora M. en C. Ma. Jaquelina López Barrientos quien motivó durante mi formación académica mi interés por este tema.


[1] El desarrollo del algoritmo de Shor se encuentra disponible en http://arxiv.org/pdf/quant-ph/9508027v2 (ago-2013)

[2] IBM's Test-Tube Quantum Computer Makes History. IBM, 2001. Disponible en  http://www-03.ibm.com/press/us/en/pressrelease/965.wss (ago-2013)

[3] TRELLES, ROSALES. Introducción a la lógica. Pontificia Universidad Católica del Perú. 2ª ed. 2002.

[4] LÉVY, ÉLIE. Diccionario Akal de física, Akal, España, 2008.

[5] ARREOLA, Verónica. Computación Cuántica, México, Universidad Nacional Autónoma de México, Facultad de Ciencias, 2004.

[6] KLIMOV, Andrei B. “Información cuántica: ideas y perspectivas”, en Revista Cinvestav , México, IPN,  v27, n1 enero-marzo, 2008.

[7] El descartar las opciones erróneas se logra con el concepto de interferencia, que es un caso particular de la superposición, se dejará al lector la tarea de profundizar con apoyo de las referencias.

[8] ARREOLA, Verónica. Computación Cuántica, México, Universidad Nacional Autónoma de México, Facultad de Ciencias, 2004.

[9] VARGAS, BRANCH. Quantum computing's state of the art. Revista Avances en Sistemas e Informática, Vol 6 Num 2. Colombia. 2009.

[10] ARREOLA, Verónica. Computación Cuántica. México, Universidad Nacional Autónoma de México, Facultad de Ciencias, 2004.

[11] El documento original puede consultarse en http://researcher.watson.ibm.com/researcher/files/us-bennetc/BB84highest.pdf (ago-2013)

[12] LÓPEZ, Barrientos Ma. Jaquelina. Criptografía, México, Universidad Nacional Autónoma de México, Facultad de Ingeniería, 2009.

[13] ARREOLA, Verónica. Computación Cuántica. México, Universidad Nacional Autónoma de México, Facultad de Ciencias, 2004.

[14] RIGOLIN, RDIEZNIK. Introdução à criptografia quântica. Revista Brasileira de Ensino de Física, v. 27, n. 4, Brasil. 2005. Disponible en http://www.scielo.br/pdf/rbef/v27n4/a04v27n4.pdf (ago-2013)

[15] DIVINCENZO, David P. The Physical Implementation of Quantum Computation. IBM, 2008. Disponible en http://arxiv.org/pdf/quant-ph/0002077v3 (ago-2013)

[16] MORALES-LUNA, Guillermo. “Computación cuántica: un esbozo de sus métodos y desarrollo”. IPN, Revista Cinvestav. v26. 2007.

[17] Ibid.

[18] Ibid.

UNAM

[ CONTACTO ]

Se prohíbe la reproducción total o parcial
de los artículos sin la autorización por escrito de los autores

 

Hecho en México, Universidad Nacional Autónoma de México (UNAM) © Todos los derechos reservados 2017.