Diseño e implementación de PRNG caótico con
distribución variable en el tiempo
Design and Implementation of a Chaotic-Time-Varying Distribution PRNG
Raúl Eduardo Lopresti
1
, Maximiliano Antonelli
2
, Julio Dondo
3
y Luciana De Micco
4
Instituto de Investigaciones Científicas y Tecnológicas en Electrónica (ICYTE)
Facultad de Ingeniería, Universidad Nacional de Mar del Plata (FI-UNMdP)
Consejo Nacional de Investigaciones Científicas y Técnicas (CONICET)
1
lopresti@fi.mdp.edu.ar
2
maxanto@fi.mdp.edu.ar
4
ldemicco@fi.mdp.edu.ar
Dto. de Electrónica
Facultad de Ciencias Físico-Matemáticas y Naturales, Universidad Nacional de San Luis (UNSL)
3
jdondo@unsl.edu.ar
Resumen—Gran parte de las aplicaciones electrónicas
requieren de números pseudoaleatorios, en general, para
mejorar su funcionamiento. Tal es el caso de los sistemas de
encriptación, codificación y modulación digital. Si, además,
los números pseudoaleatorios varían dinámicamente su
función densidad de probabilidad (PDF) es posible potenciar
el efecto causado. En este trabajo se presenta el diseño e
implementación de un circuito capaz de entregar números
pseudoaleatorios que varían su PDF en el tiempo. Para ello,
se utilizan como base mapas caóticos, los que son diseñados
según las PDF deseadas. Luego, la implementación se realiza
mediante Reconfiguración Parcial Dinámica (RPD) la cual
permite modificar, en tiempo de ejecución, parte del circuito
para variar la PDF de la salida generada.
Palabras clave: Generador de números pseudoaleatorios;
Función Densidad de Probabilidad; Reconfiguración Parcial
Dinámica; Caos.
Abstract—Many electronic applications require pseudo-
random numbers, in general, to improve their performance.
Such is the case of encryption, coding and digital modulation
systems. In addition, it is possible to enhance the effect if the
pseudorandom numbers dynamically vary their probability
density function (PDF). In this article, a circuit that generates
pseudo-random numbers that are capable of varying their
PDF in time is presented. To this aim, chaotic maps are used
as a base, which are designed according to the desired PDF.
Then, the implementation is done through Dynamic Partial
Reconfiguration (RPD) which allows modifying, at run time,
part of the circuit to vary the PDF of the generated output.
Keywords: Pseudorandom number generator, Probability
Density Function, Dynamic Partial Reconfiguration, Chaos.
I. INTRODUCCIÓN
La pandemia COVID-19 ha producido una aceleración en
el crecimiento del tráfico y en la, ya creciente, migración
de datos digitales a los centros de datos y la nube pública.
El incremento en el tráfico fue impulsado en gran medida
por el uso de conferencias a través de internet, reuniones
o clases virtuales, así como juegos en línea y streaming
de video. Todo incremento en la recolección de datos
aumenta los posibles problemas de privacidad, tanto en la
transmisión como en el almacenamiento de los mismos.
El cifrado es la base principal de la seguridad de datos
para evitar ataques y robo de información. Recientemente
han surgido técnicas de cifrado que varían en el tiempo
distintas partes de sus bloques constituyentes utilizando
secuencias pseudoaleatorias. Ejemplo de esto es la variación
dinámica aleatoria de los codificadores constituyentes de un
codificador turbo, esto es propuesto y desarrollado en [1]. En
[2]–[5] los autores proponen sistemas de encriptación en los
que se varía en tiempo de ejecución la clave de encriptación
empleada. Lo que proponemos en este artículo es avanzar
a un nivel mayor de seguridad variando dinámicamente la
PDF de los números aleatorios generados. Recientemente
se ha hecho posible este tipo de implementación gracias al
desarrollo de la tecnología RPD. Esta tecnología permite la
implementación de bloques con alto grado de complejidad,
ocupando un área mínima, y permitiendo su integración
con el resto del sistema. Mediante RPD es posible la
reconfiguración en tiempo de ejecución de una partición
específica en una FPGA (Field Programmable Gate Array).
La generación clásica de números pseudoaleatorios con
distintas distribuciones de probabilidad es un problema
estudiado principalmente en ingeniería de software y se basa
en el desarrollo de algoritmos a ejecutarse sobre plataformas
secuenciales [6]. Estos algoritmos parten de generadores de
números pseudoaleatorios con distribución uniforme de base
y son en general muy complejos. Por su parte, los mapas
caóticos son capaces de generar secuencias de números con
apariencia aleatoria y dada la estructura de estos mapas
permiten una ejecución concurrente. Esto los hace ideales
para su implementación en dispositivos tales como FPGAs.
En cuanto a las características de los datos generados la
distribución (Invariant Density Probability Function, IPDF)
que tendrán los números aleatorios generados y la velocidad
con la que se “mezclan"(constante de mixing) depende
únicamente de la estructura del mapa. De esta forma es
posible “sintetizar” un mapa caótico a partir de la IPDF
y la constante de mixing deseadas, esto es conocido como
Problema Inverso de Perron-Frobenius (IFPP) [7].
Recibido: 15/03/22; Aceptado: 08/05/22
Creative Commons License - Attribution-NonCommercial-
NoDerivatives 4.0 International (CC BY-NC-ND 4.0)
https://doi.org/10.37537/rev.elektron.6.1.156.2022
Original Article
Revista elektron, Vol. 6, No. 1, pp. 46-51 (2022)
ISSN 2525-0159
46
En este artículo se presenta la implementación de un
circuito, basado en mapas caóticos, capaz de variar en el
tiempo la PDF de su datos de salida. La RPD permite
ahorrar recursos de la FPGA implementando distintos cir-
cuitos (multiplexados en el tiempo) en el espacio que ocupa
uno sólo. Todo el circuito está confinado en una pequeña
área de la FPGA. El bloque desarrollado, además de ser
empleado para incrementar la seguridad en algoritmos de
encriptamiento, abre un nuevo abanico de posibilidades de
implementar en FPGAs algoritmos concurrentes.
II. DISEÑO DE MAPAS CTICOS CON
CARACTERÍSTICAS PREESTABLECIDAS
Existen muchos estudios que abordan la búsqueda de una
solución al IFPP [7]–[9]. Este trabajo empleó la desarrollada
por Rogers et. al. [10] quienes presentan una solución basada
en la teoría de matrices positivas. Este método es usado
exitosamente en [11] para implementar en una FPGA un
generador de ruido con distribución Gaussiana. El método
se basa en una matriz estocástica (matriz A) que describirá
la dinámica del mapa caótico a diseñar. Cada componente
de esta matriz expresa la probabilidad de transición de un
intervalo a otro. El autovector asociado al autovalor unitario
de la matriz A se corresponde con la IPDF del mapa. Por lo
tanto, diseñando adecuadamente esta matriz se consigue el
comportamiento deseado. La limitación del método es que
sólo puede generar mapas que posean densidades invariantes
lineales por tramos. Por lo tanto se deberán crear tantos
tramos (filas y columnas de la matriz redA) como sean
necesarios para conseguir la aproximación requerida.
Para definir la matriz se particiona el intervalo (0, 1) en
n subintervalos, I
1
, ..., I
n
. La probabilidad de transición
p
i,j
del intervalo I
i
al intervalo I
j
se corresponde con el
recíproco del elemento a
i,j
de la matriz A:
A =
β
1
+ α
1
(1 β
1
) α
1
(1 β
2
) ...
α
1
(1 β
n
)
α
2
(1 β
1
) β
2
+ α
2
(1 β
2
)
... ...
α
n
(1 β
1
) ... β
n
+ α
n
(1 β
n
)
.
(1)
La matriz A es una matriz estocástica por lo que es
siempre positiva cuando α
i
0 y 0 < β
i
< 1 i ϵ
1, ..., n. De la teoría de matrices positivas se sabe que uno
de los autovalores de la matriz A es unitario, y su autovector
asociado, x
p
, corresponde a la densidad IPDF del proceso
gobernado por A, y tiene la siguiente forma:
x
p
=
α
1
1 β
1
, ...,
α
n
1 β
n
. (2)
Eligiendo debidamente los valores de α
i
y β
i
se consi-
gue que el autovector correspondiente al autovalor unitario
presente valores determinados, y así se consigue que los nú-
meros generados por el mapa tengan la densidad invariante
deseada. Los pasos son los siguientes:
1. Se establecen los n puntos que se empelarán para
aproximar la PDF deseada. Considerando que una
mayor cantidad de puntos resultan en una mejor
aproximación, pero implican un mapa con más tramos
(esto se verá más adelante).
2. Estos puntos se igualan al vector de la IPDF x
p
(ec.
2).
3. Se establece un valor para todos los parámetros β
i
(o
α
i
) y se despejan los restantes.
4. Una vez establecidos los valores de los β
i
y los α
i
se
arma la matriz A según la ecuación 1.
5. El mapa caótico resultante presentará n tramos de
igual tamaño (correspondientes con cada columna de
la matriz A). Cada elemento fila de una columna dada
representa el porcentaje de ocupación de esa fila en el
ancho total del tramo de la columna correspondiente
(Fig. 2). Cabe destacar que la forma del mapa en cada
tramo no esta establecida por la metodología, donde
una posibilidad es utilizar funciones lineales como las
empleadas en la Fig. 2.
6. Finalmente iterando en el mapa caótico obtenido, se
generan secuencias cuya PDF coincide con la aproxi-
mada en el punto 1.
Figura 1. Ejemplo de aproximación de PDF, en este caso se tomaron tres
puntos (n = 3). Aquí x
p
= (0,108; 0,8; 0,002). En azul la PDF original,
en línea punteada la aproximación tomada a dicha PDF.
Figura 2. Mapa caótico lineal por tramos generado a partir de la matriz A
correspondiente.
III. DISEÑO E IMPLEMENTACIÓN DEL PRNG
El generador a implementar debe ser capaz de variar
en tiempo de ejecución las distribuciones de los datos
que genere. Por ello se definieron las PDFs a emplear,
se determino con cuántos puntos aproximarlas y en base
a ello se diseñaron los mapas caóticos que generarán los
datos con tales PDFs, mediante el método descripto en la
sección anterior. De esta forma, todos los mapas caóticos a
implementar tienen una estructura lineal por tramos como
la de la Fig. 2. Se ideó un diseño que cumpliera con las
siguientes especificaciones:
El diseño tiene que ser simple para que pueda trasla-
darse de manera directa a hardware y para que requiera
pocos recursos en una FPGA.
Debe ser simulado en una computadora de escritorio
(PC) trabajando con números de punto flotante para ve-
rificar la correcta implementación del método descrito
en el apartado anterior.
Revista elektron, Vol. 6, No. 1, pp. 46-51 (2022)
ISSN 2525-0159
47
http://elektron.fi.uba.ar
Tiene que ser traducido a variables de punto fijo y
ser simulado en PC para obtener una primera aproxi-
mación del comportamiento funcional que tendría el
circuito ya implementado en hardware, permitiendo a
la vez determinar la cantidad de bits necesarios para
conseguir los resultados deseados.
Debe implementarse en un procesador embebido a fin
de comparar su desempeño con el de una implementa-
ción puramente en lógica programable.
Los resultados de las simulaciones en PC deben ser
almacenados para una posterior comparación con los
datos que genere el diseño ya implementado en FPGA
a fin de validar su correcto funcionamiento, tanto para
la versión con procesador como para la versión con
solo lógica programable
Por lo tanto, el desarrollo contó con las etapas que se
describen en los siguientes apartados.
III-A. Elaboración y prueba del algoritmo en PC
Se escogió implementar los tramos de los mapas caóticos
mediante ecuaciones lineales, de la forma de pendiente y
ordenada al origen, a fin de que la implementación requie-
ra menos cálculos y utilice menos recursos de hardware.
Entonces, el algoritmo consultará una tabla previamente
almacenada en la que se define el mapa caótico. La tabla
tiene tantas filas como tramos del mapa caótico (n), cada
una de estas filas almacena un valor de pendiente (m) y
de ordenada al origen (b). La secuencia se genera con un
algoritmo iterativo de cuatro pasos, el mismo se presenta en
la Fig. 3 y se describen a continuación:
Figura 3. Algoritmo que implementa el mapa caótico para la generación
de secuencias con una determinada PDF.
1. Se establece un valor inicial x
0
para la secuencia
caótica x[k]. Este valor es equivalente a lo que se
conoce como semilla en muchos algoritmos aleatorios.
2. Se determina a cuál tramo i de la ecuación (tramo
del mapa caótico) corresponde el valor actual de la
secuencia.
3. Se obtienen de la tabla almacenada los valores de
ordenada al origen b
i
y pendiente m
i
correspondientes
al tramo i.
4. Con estos tres datos se calcula el nuevo valor de la
secuencia (x[k + 1] = m
i
x[k] + b
i
), el cual se utiliza
para calcular el subsiguiente valor repitiendo los pasos
del 2 al 4 de este algoritmo.
Inicialmente se implementó el algoritmo en una PC me-
diante un software de simulación utilizando aritmética de
punto flotante con el objetivo de validar el mismo. Luego se
iteró el algoritmo utilizando distintas aritméticas. Se utilizó
primero aritmética de punto flotante (estándar IEEE754),
tanto en precisión simple (32 bits) como en precisión doble
(64 bits). Con el objetivo de reducir los recursos empleados
y simplificar su implementación en hardware se utilizó
también aritmética de punto fijo con distintas cantidades de
bits (n
bits
).
La representación numérica juega un papel importante
debido a la sensibilidad a las condiciones iniciales, inherente
a los mapas caóticos [12]. Aquí entra una relación de com-
promiso entre precisión numérica y área de circuito. A modo
gráfico en la Fig 4 se muestra las PDFs obtenidas en el caso
de aproximar la PDF triangular con 13 puntos (en negro)
y las PDFs generadas iterando en los mapas obtenidos para
distintas aritméticas (en celeste). Se generaron secuencias de
40.000 datos cada una y se eliminó el transitorio descartando
los primeros 10.000 datos. Se puede ver que en punto fijo
con 24 bits la aproximación no es buena (Fig. 4.a), con 38
bits la PDF obtenida se ajusta a la deseada (Fig. 4.b). En
el caso de trabajar con punto flotante, utilizando precisión
simple (Fig. 4.c) no se ajusta a la PDF deseada, en cambio,
precisión doble se ajusta a la PDF deseada (Fig. 4.d).
(a) Punto fijo (n
bits
= 22)
JSD = 0,00398
(b) Punto fijo (n
bits
= 38)
JSD = 0,00005
(c) Punto flotante precisión simple
JSD = 0,00126
(d) Punto flotante precisión doble
JSD = 0,00005
Figura 4. En azul histogramas generados iterando en los mapas caóticos
con diferentes aritméticas (punto fijo y punto flotante), en negro IPDF del
mapa caótico.
Revista elektron, Vol. 6, No. 1, pp. 46-51 (2022)
ISSN 2525-0159
48
http://elektron.fi.uba.ar