Dispositivo y procedimiento para generar una secuencia de bits aleatorios.

Dispositivo (1) para generar una secuencia de bits aleatorios con un circuito oscilante anular digital (2) quepresenta al menos una primera ruta de realimentación (R8) y una segunda ruta de realimentación (R14) y queestá configurado tal que se realiza en instantes que pueden predeterminarse una conmutación entre las rutas derealimentación (R8,

R14) y en un nodo de salida (4) del circuito oscilante anular (2) puede tomarse una señalaleatoria (OS) con una evolución aleatoria del nivel de señal,

caracterizado porque el circuito oscilante anular (2) presenta además un nodo de entrada (3) y estáconfigurado tal que cuando tiene lugar un cambio de estado de una señal de arranque lógica (ST) acoplada alnodo de entrada (3), tiene lugar una oscilación.

Dispositivo y procedimiento para generar una secuencia de bits aleatorios.

La invención se refiere a dispositivos y procedimientos para generar bits aleatorios y secuencias de bits aleatorios. Ello sirve por ejemplo para implementar un generador de números aleatorios.

En aplicaciones relevantes para la seguridad se necesitan a menudo números aleatorios, que se presentan en forma digital como secuencias de bits aleatorios. Por ejemplo en procedimientos de autentificación asimétricos es necesario generar y utilizar números aleatorios. En particular en tags RFID (etiquetas de identificación por radiofrecuencia) con funcionalidad de seguridad han de generarse los correspondientes números aleatorios con un coste del hardware especialmente bajo. Es deseable al respecto utilizar solamente circuitos lógicos digitales, que pueden implementarse económicamente.

En el pasado se utilizaron generadores de números aleatorios por ejemplo utilizando fuentes de ruido analógicas, cuyas señales se digitalizan. No obstante, los circuitos híbridos analógico/digitales son costosos de implementar.

Un generador de números aleatorios que prácticamente presenta exclusivamente circuitos lógicos digitales se describe en el documento WO 2006/015624 A1. En esta solicitud de patente internacional se propone utilizar fluctuaciones de fase aleatorias de osciladores anulares constituidos a partir de puertas (gatter) digitales. No obstante, según el documento WO 2006/015624 A1 solamente son adecuados osciladores anulares muy especiales, a saber, osciladores anulares Fibonacci o Galois con características especiales para su utilización en un generador de números aleatorios. En un circuito eléctrico así constituido se parte de que los osciladores anulares no deben presentar ningún punto fijo. Esta condición puede representarse en particular para circuitos oscilantes Fibonacci o Galois mediante ecuaciones matemáticas, que deben cumplirse según el documento WO 2006/015624 A1. Por lo tanto en la correspondiente implementación ha de comprobarse primeramente si un oscilador anular presenta puntos fijos. Por ello es un inconveniente que la posibilidad de elección de circuitos oscilantes adecuados sea muy limitada.

El documento Keerat Brar y colab.: “True Random Number Generators” (generadores de números aleatorios auténticos) , Course Cr y ptography and Computer Network Security ECE646, Fall 2007, George Manson University, Department of Electrical and Computer Engineering, Fairfax, Virginia, USA, páginas 1-5, diciembre 2007, da a conocer un oscilador anular Fibonacci con una ruta de realimentación, con ayuda del cual pueden generarse números pseudo-aleatorios.

El documento WO 2009/109959 A1 da a conocer un sistema para generar números pseudo-aleatorios con un circuito oscilante anular, que puede presentar diversas configuraciones y un componente de aleatorización que alterna entre las configuraciones del circuito oscilante anular en función de un flujo de números pseudo-aleatorios.

Es por lo tanto una tarea de la presente invención lograr un dispositivo mejorado para generar bits aleatorios.

Esta tarea se resuelve mediante un dispositivo con las características de la reivindicación 1.

Según ello presenta un dispositivo para generar una secuencia de bits aleatorios un circuito oscilante anular digital con al menos una primera ruta de realimentación y una segunda ruta de realimentación. Entonces se realiza en instantes que pueden predeterminarse una conmutación entre las rutas de realimentación y en un nodo de salida del circuito oscilante anular puede tomarse una señal aleatoria con una evolución aleatoria del nivel de la señal. El circuito oscilante anular presenta además un nodo de entrada y está configurado tal que cuando tiene lugar un cambio de estado de una señal de arranque lógica acoplada al nodo de entrada, tiene lugar una oscilación.

En circuitos oscilantes anulares digitales está realimentado por lo general un número impar de puertas lógicas (gatter) . Esto significa que la salida de una de las puertas lógicas está combinada con la entrada de otra puerta lógica. De esta manera pueden resultar oscilaciones que bajo determinadas condiciones asumen formas de señal no predecibles, es decir, representan señales aleatorias. Se prevé ahora disponer de varias rutas de realimentación posibles entre las que puede conmutarse. De esta manera pueden lograrse una característica aleatoria mejorada para la señal aleatoria. Mediante la conmutación, que provoca características de oscilación variables en el oscilador anular, pueden generarse así bits aleatorios sin un gran coste.

Debido a procesos térmicos o de mecánica cuántica, dentro de los componentes semiconductores utilizados para implementar el oscilador, resultan por ejemplo fluctuaciones de fase o jitter, que provocan evoluciones internas aleatorias de la señal o del potencial. Los componentes lógicos, por ejemplo un número impar de circuitos inversores, pueden estar acoplados, por ejemplo para formar un oscilador anular, en forma de cascada para constituir un anillo. Por lo general depende la frecuencia de oscilación básica de la cantidad de circuitos inversores o lógicos utilizados. Debido a los distintos retardos que se presentan en el tratamiento de la señal por causa de los distintos componentes lógicos, no resulta por lo general una fase constante, sino una fluctuación de fase o jitter, con lo que a menudo se presentan formas de señal irregulares.

No obstante, no puede partirse básicamente de que también para largos periodos exista siempre una "curva de oscilación" absolutamente aleatoria. Cada circuito oscilante anular presenta en su curva de señal, tras su activación o arranque, evoluciones aleatorias en el tiempo del nivel de la señal, que básicamente pueden desembocar, desde luego también después de un proceso de estabilización de la señal, en una curva determinística.

Mediante la conmutación de las rutas de realimentación, se evita no obstante que el transitorio de arranque se estabilice por ejemplo en un punto fijo. Puede modificarse por ejemplo, controlada por impulsos o periódicamente, la correspondiente realimentación del circuito oscilante anular. Incluso cuando el concepto básico del correspondiente oscilador anular tiende a oscilaciones periódicas y esto parece por lo tanto a priori inadecuado para generar señales aleatorias, se logra mediante la conmutación que tales oscilaciones potencialmente periódicas se vean perturbadas. Se establece así de esta manera siempre un comportamiento de la oscilación aleatorio no periódico, a partir del que puede obtenerse una gran entropia para la generación a continuación de valores de bits aleatorios. Es posible entonces utilizar también osciladores anulares Fibonacci o Galois más cortos, con lo que se reduce el costo de hardware y de implementación. Una conmutación tiene lugar por ejemplo tal que se conmuta entre al menos dos realimentaciones Galois o Fibonacci distintas.

El dispositivo para generar una secuencia de bits aleatorios tiene por lo tanto en particular la ventaja de que es fácil de implementar y no tienen que realizarse cálculos como los que son necesarios según el estado de la técnica para excluir un punto fijo. Como circuitos oscilantes anulares puede tomarse así un surtido mayor de osciladores. Además, los osciladores anulares generales, que se encuentran en uno o en otro estado de servicio en función de la realimentación ajustada, tienen la ventaja de que incluso cuando se alcanza el punto fijo, lo cual no es nocivo en el dispositivo propuesto para generar una secuencia de bits aleatorios en cuanto a la calidad de la aleatoriedad, el consumo de energía desciende fuertemente. Esto es así en particular en una implementación de las correspondientes configuraciones de circuitos en tecnología CMOS.

La conmutación entre rutas de realimentación posibilita la utilización de sólo unos pocos componentes lógicos conectados en serie. De esta manera se logra un ahorro de energía adicional. Se prevé por ejemplo en un ejemplo de ejecución solamente un equipo de conmutación adicionalmente, que en instantes predeterminados realiza una conmutación de la ruta de realimentación. Esto puede realizarse por ejemplo en función de una señal de conmutación. La señal de conmutación corresponde preferiblemente a un impulso externo, con el que se realiza periódicamente una conmutación entre las rutas de realimentación.

Mediante la implementación especialmente económica, que preferiblemente presenta... [Seguir leyendo]

1. Dispositivo (1) para generar una secuencia de bits aleatorios con un circuito oscilante anular digital (2) que presenta al menos una primera ruta de realimentación (R8) y una segunda ruta de realimentación (R14) y que está configurado tal que se realiza en instantes que pueden predeterminarse una conmutación entre las rutas de realimentación (R8, R14) y en un nodo de salida (4) del circuito oscilante anular (2) puede tomarse una señal aleatoria (OS) con una evolución aleatoria del nivel de señal,

caracterizado porque el circuito oscilante anular (2) presenta además un nodo de entrada (3) y está configurado tal que cuando tiene lugar un cambio de estado de una señal de arranque lógica (ST) acoplada al nodo de entrada (3) , tiene lugar una oscilación.

2. Dispositivo (1) según la reivindicación 1, en el que está previsto un equipo de conmutación (28) que en instantes predeterminados realiza una conmutación de la ruta de realimentación (RS) .

3. Dispositivo (1) según la reivindicación 2, en el que el equipo de conmutación (28) conmuta en función de una señal de conmutación (CT1) entre las rutas de realimentación (R8, R14) .

4. Dispositivo (1) según una de las reivindicaciones 1 -3, en el que se realiza periódicamente una conmutación.

5. Dispositivo (1) según una de las reivindicaciones 1 -4, en el que el circuito oscilante anular (2) presenta varios elementos lógicos (12-27) conectados en serie.

6. Dispositivo (1) según la reivindicación 5, en el que están previstos al menos siete componentes lógicos (12-27) conectados en serie.

7. Dispositivo (1) según la reivindicación 5 ó 6, en el que los componentes lógicos (13-27) son inversores.

8. Dispositivo (1) según una de las reivindicaciones 1 -7, tal que el dispositivo (1) presenta un elemento de memoria intermedia (8) acoplado al nodo de salida (4) , que en función de la señal aleatoria (OS) memoriza un nivel lógico.

9. Dispositivo (1) según la reivindicación 7 u 8, en el que el elemento de memoria intermedia (8) memoriza un nivel lógico correspondiente a la señal aleatoria (OS) en función de una señal de exploración (CLK) .

10. Dispositivo (1) según la reivindicación 9, tal que el dispositivo (1) presenta un equipo de generación de la señal de exploración (6) , que en instantes predeterminados genera un cambio de estado lógico de la señal de exploración (CLK) .

11. Dispositivo (1) según una de las reivindicaciones 1 -10, tal que el dispositivo (1) presenta un equipo de generación de señal rectangular (7) acoplado al nodo de entrada (3) , que genera la señal de arranque (ST) con niveles lógicos cambiantes.

12. Dispositivo (1) según una de las reivindicaciones 1 -11, tal que el dispositivo (1) presenta un equipo de control (5) que según una programación origina la toma de un valor de bit aleatorio en el nodo de salida (4) o elemento de memoria intermedia (8) y/o la generación de la señal de arranque (ST) y/o de la señal de conmutación (CT1) .

13. Dispositivo (1) según una de las reivindicaciones 1 -12, en el que el circuito oscilante anular (2) está realizado a modo de un oscilador anular Galois u oscilador anular Fibonacci.

14. Dispositivo (1) según una de las reivindicaciones 1 -13, tal que el dispositivo (1) esta implementado como circuito FPGA.

15. Chip RFID con un dispositivo (1) según una de las reivindicaciones 1 -14 y un equipo criptográfico, en el que se utilizan varios bits aleatorios (ZB) obtenidos de la señal aleatoria (OS) por el equipo criptográfico para realizar una autentificación criptográfica, para generar una firma criptográfica y/o para generar una clave criptográfica.

16. Generador de números aleatorios con un dispositivo (1) según una de las reivindicaciones 1 – 14,

en el que se captan varios valores de nivel lógico de la señal aleatoria (OS) tomados en el nodo de salida (4) o de niveles lógicos (ZB) memorizados por un elemento de memoria intermedia (8) como valores de bits de un número aleatorio (ZZ) .

17. Procedimiento para generar una secuencia de bits aleatorios, en el que en función de la evolución de un nivel lógico de una señal aleatoria (OS) tomada de un circuito oscilante anular digital (2) , se determinan valores de bits aleatorios (ZB) , presentando el circuito oscilante anular digital (2) al menos una primera ruta de realimentación (R8) y una segunda ruta de realimentación (R14) y en instantes predeterminados se realiza una conmutación entre las rutas de realimentación (R8, R14) , pudiendo tomarse en un nodo de salida (4) del circuito oscilante anular (2) una señal aleatoria (OS) con una evolución del nivel lógico aleatoria,

caracterizado porque el circuito oscilante anular (2) presenta además un nodo de entrada (3) y está configurado tal que cuando tiene lugar un cambio de estado de una señal lógica de arranque (ST) acoplada al nodo de entrada (3) , tiene lugar una oscilación.

18. Procedimiento según la reivindicación 17, en el que se realizan las siguientes etapas: -activación (S1) de un circuito oscilante anular digital (2) ; -conmutación (S2) entre la primera y la segunda ruta de realimentación (R8, R14) ; -toma (S2, S21) de uno o varios valores de nivel lógico de una señal aleatoria (OS) oscilante generada por

el circuito oscilante anular (2) .

19. Procedimiento según la reivindicación 17 ó 18, en el que el circuito oscilante anular (2) se activa varias veces para generar varios valores de bits aleatorios.

20. Procedimiento según una de las reivindicaciones 17 – 19, en el que se conmuta periódicamente entre las rutas de realimentación (R8, R14) .

21. Procedimiento según una de las reivindicaciones 17 – 20, en el que en función de la evolución de la señal aleatoria (OS) se determina un valor de bit aleatorio (S21, S22) .