PDF de programación - Generación de números aleatorios para aplicaciones en criptografía cuántica

Generación de números aleatorios para aplicaciones en

criptografía cuántica.

Catalina M. Rivera Mesías *Andrés Camilo Barajas Ramírez **

Asesor: David Guzman

Departamento de Física

Universidad de los Andes

Bogotá, Noviembre 15 de 2011

Resumen

La generación de números aleatorios es muy importante en el cifrado de comuni-
cación y en especial, en la encriptación cuántica de información. Como parte de un
proyecto de gran envergadura que tiene ésto como su eje principal, hemos desarrol-
lado dos posibles métodos para la obtención de secuencias binarias que servirán para
la codificación de mensajes: la implementación de un generador de secuencias pseu-
doaleatorias en una FPGA, y la adaptación de este mismo dispositivo como memoria y
receptor de eventos ocasionados en la medición de estados entrelazados de probabilidad
de 1/2. Presentamos los avances y logros obtenidos, y las dificultades y posibles solu-
ciones que deben ser sobrepasadas para la implementación efectiva de estos sistemas
en el proyecto general.

1. Marco Teórico

1.1. Generador de secuencias pseudoaleatorias

Un generador de números pseudoaleatorios es un algoritmo que permite obtener secuen-
cias de números cuyas propiedades se asemejan en alto grado a la de los números aleatorios.
Estas secuencias sin embargo son determinadas por condiciones iniciales y por el algoritmo
en si mismo. Se utilizan por ejemplo en simulaciones de sistemas físicos en donde algunas de
sus propiedades son de carácter aleatorio (como por ejemplo las velocidades de las partículas
en un gas).
Una de las características mas particulares de estas secuencias es su carácter reproducible:
con el conocimiento del algoritmo utilizado y las condiciones iniciales, se puede obtener la
misma secuencia de datos. Esta propiedad es deseable cuando se realizan simulaciones pues
permite rastrear fácilmente la presencia de errores, pero es de gran vulnerabilidad cuando es
utilizada para encriptar flujos de información.
El carácter pseudoaleatorio de estas secuencias, las hace susceptibles a presentar periodici-
dad, falta de uniformidad o la presencia de patrones de correlación.

*[email protected]
**[email protected]

1.2. Generador cuántico de números aleatorios

Es posible utilizar los principios de la mecánica cuántica para crear secuencias aleatorias.
[2]Un q-bit es un sistema cuántico de dos niveles que en general puede presentarse en un

|↑ + eiϕ sin θ

|↓ con 0 ≤ θ ≤ π y 0 ≤ ϕ < 2π. Cuan-

estado de superposición |ϕ = cos θ

2

2

do se logran obtener experimentalmente y de manera sistemática q-bits cuyas amplitudes
de probabilidad sean ambas iguales a 1√
se pueden generar secuencias aleatorias por medio
de la medición del observable en el cuál se tiene descrito el estado. Esto presenta una gran
ventaja con respecto al método mencionado anteriormente ya que cada uno de los valores
que toma la secuencia es impredecible hasta el instante en que se realiza la medición.

2

Para llevar éstas ideas a la práctica se hace necesario programar una tarjeta electrónica
FPGA (Field- Programable Gate Array ) que reciba la información de los detectores de fo-
tones y a partir de ella sea capaz de generar la secuencia binaria correspondiente.

El lenguaje de programación que permite programar la tarjeta es VHDL. Una de las ven-
tajas de éste lenguaje es que permite describir el comportamiento del sistema que se quiere
modelar, a través de simulaciones sin tener que sintetizar el programa en el hardware real.
Esto hace más fácil la verificación y optimización del programa. Una de las diferencias con
respecto a los lenguajes de programación estándar como C, Matlab, etc; es que la ejecución
del código no es secuencial sino que por el contrario las señales que van siendo modificadas
se van evaluando constantemente. Como consecuencia de esto se tiene que por lo general el
uso de ciclos como for y while entre otros, no son sintetizables. Usualmente para ejecutar
una orden repetidas veces se hace uso de los cambios del reloj que viene incluido en la FPGA.

Ahora bien, para hacer la conexión entre la FPGA y el computador, es decir el usuario,
utilizamos [4] LabVIEW (Laboratory Virtual Instrumentation Engineering Workbench); una
plataforma y entorno de desarrollo para diseñar sistemas, con un lenguaje de programación
visual gráfico. En LabVIEW los programas se diseñan gráficamente, implementando blo-
ques prediseñados con cierta funcionalidad que también pueden ser creados para objetivos
particulares. Se deben programar dos partes: el panel frontal, es decir, el interfaz con el
usuario que permite visualizar el estado de las variables del problema durante la ejecución
del programa; y el diagrama de bloques; que es el programa propiamente dicho, donde se
define su funcionalidad. Aquí se colocan íconos que realizan una determinada función y se
interconectan entre sí. Para nuestro caso, es importante notar que en LabVIEW los ciclos
sí están permitidos.

2. Metodología y Resultados

2.1. Generador de Congruencia lineal

2.1.1. Algoritmo

El generador escogido para realizar la secuencia pseudoaleatoria es el generador de con-
gruencia lineal el cual se caracteriza por ser un algoritmo de sencilla implementación. Este
es el generador interno implementado por diversos lenguajes de programación y se define por
medio de la siguiente relación de recurrencia:

en donde a, c y m son valores constantes dentro del generador; mod representa a la

función módulo que se define como

xn+1 = mod(axn + c, m)

(2.1)

mod(r, s) = r −r



s

(2.2)
tal que . representa la función parte entera. De allí que se deba cumplir que los valores de
c y m sean menores que los de a. La escogencia de estos valores repercute en características del
desarrollo de la secuencia, como por ejemplo, su periodicidad: ésta puede ser como máximo el
valor de m, y pueden presentarse casos con periodos mucho menores que este valor. También
es importante el valor inicial xn, el cual es denominado como la semilla de la secuencia.En
particular, para la implementación realizada se tomaron los siguiente valores

s

Constante

m
a
c
x0

Valor
224

1140671485
12820163
327680

Estos valores fueron tomados del generador de Microsoft Visual Basic, por tener con-
stantes cuyos valores no sobrepasan las capacidades de memoria de la FPGA, y por generar
un buen desarrollo de la secuencia [3].

2.1.2.

Implementación

El código utilizado para la implementacion de este algoritmo se encuentra en el anexo
4.1. Mediante este código, la FPGA tiene 3 posibles estados determinados por la variable
lógica de entrada reset, y por el valor de la variable entera interna counter, los cuales son
resumidos a continuación

Reset

Counter

0

Resultado
En espera

1
0
0

Menor que long

Llenando la secuencia

Igual o mayor que long

Secuencia llena: en espera

Este proceso se activa con el cambio de las variable xor inicie y reset o de la variable
clock. Cada vez que una de estas se activa, se evalúa el valor de las variables detalladas en la
tabla anterior. En particular, si las variables dan para llenar la secuencia, la FPGA determina
el siguiente valor de la formula de recurrencia; es decir,en este caso cada vez que se activa el
proceso, se halla un nuevo valor en la secuencia. Por este motivo, el proceso se halla atado al
reloj de la FPGA, lo cual asegura que el llenado se realizara de forma ininterrumpida. Visto
de esta manera, la FPGA va a estar siempre llenando la secuencia, a menos de que reset se
encuentre activado.

Otro detalle a observar, es la condición del tercer caso, que toma como posibilidad que
counter sea mayor que la cantidad long. Aunque en principio, esto no debería ser posible
observando la estructura del programa, se debe tener en cuenta que es posible que el reloj de
la FPGA active el proceso, aun cuando las operaciones definidas en su interior no se hayan

realizado completamente. Esto podría ser la causa de que la secuencia obtenida presente
bloques grandes de ceros o de unos y por lo tanto se disminuya en gran medida su grado de
aleatoriedad. En la figura 1 se muestra el diagrama utilizado para la activación, lectura y
escritura de la secuencia obtenida en LabVIEW

Figura 1: Diagrama del programa utilizado en LabVIEW

Este diagrama realiza de forma secuencial el siguiente proceso

A. LabVIEW establece contacto con la FPGA e ingresa el programa que esta ejecutara.

Luego de esto entra en el primer bucle general

B. Inicialmente se activa y desactiva reset para asegurar que todas las variables comienzan

de forma adecuada

C. El programa entra en un bucle interno, en el cual consulta continuamente a la FPGA
si la secuencia se lleno, por medio del bloque ReadCountZest . De ser así, el programa
sale de esta rutina y pasa el siguiente bloque

D. Se realiza la lectura de la secuencia de los datos por medio del bloque ReadCountZest.
Este bloque en particular, lee segmentos de 24 bits de la secuencia, por lo que el
procedimiento debe ser repetido varias veces si la secuencia es mayor tiene mayor
longitud; por esto, este bloque es un for que repite la operación por el numero de veces
que el usuario determine

E. Finalmente, se procede a escribir el valor leído en el archivo escogido en la interfaz.

Este procedimiento se repite de forma continua hasta que se detiene el programa con el botón
Stop de la interfaz.

2.2. Generación cuántica de secuencias aleatorias

El montaje propuesto consistía en la medición de fotones en estados entrelazados mediante

el montaje de la figura 2

Figura 2: Montaje propuesto

En particular, el objetivo era programar la FPGA de forma que esta percibiera y registrara
los fotones que llegan a los detectores y lograr establecer comunicación entre la FPGA y el
computador (por medio de LabVIEW) para guardar las secuencias obtenidas en es