ES2266248T3 - Procedimiento y dispositivo para la produccion de una secuencia sendo-aleatoria mediante un logaritmo discreto. - Google Patents
Procedimiento y dispositivo para la produccion de una secuencia sendo-aleatoria mediante un logaritmo discreto. Download PDFInfo
- Publication number
- ES2266248T3 ES2266248T3 ES01967345T ES01967345T ES2266248T3 ES 2266248 T3 ES2266248 T3 ES 2266248T3 ES 01967345 T ES01967345 T ES 01967345T ES 01967345 T ES01967345 T ES 01967345T ES 2266248 T3 ES2266248 T3 ES 2266248T3
- Authority
- ES
- Spain
- Prior art keywords
- link
- pseudo
- output
- discrete
- logarithm
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Lifetime
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
- G06F7/58—Random or pseudo-random number generators
- G06F7/582—Pseudo-random number generators
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
- H04L9/06—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols the encryption apparatus using shift registers or memories for block-wise or stream coding, e.g. DES systems or RC4; Hash functions; Pseudorandom sequence generators
- H04L9/065—Encryption by serially and continuously modifying data stream elements, e.g. stream cipher systems, RC4, SEAL or A5/3
- H04L9/0656—Pseudorandom key sequence combined element-for-element with data sequence, e.g. one-time-pad [OTP] or Vernam's cipher
- H04L9/0662—Pseudorandom key sequence combined element-for-element with data sequence, e.g. one-time-pad [OTP] or Vernam's cipher with particular pseudorandom sequence generator
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L2209/00—Additional information or applications relating to cryptographic mechanisms or cryptographic arrangements for secret or secure communication H04L9/00
- H04L2209/12—Details relating to cryptographic hardware or logic circuitry
Landscapes
- Engineering & Computer Science (AREA)
- Physics & Mathematics (AREA)
- Theoretical Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Mathematical Optimization (AREA)
- Computer Security & Cryptography (AREA)
- Signal Processing (AREA)
- Mathematical Analysis (AREA)
- Computer Networks & Wireless Communication (AREA)
- Pure & Applied Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- Computational Mathematics (AREA)
- Error Detection And Correction (AREA)
- Measuring Or Testing Involving Enzymes Or Micro-Organisms (AREA)
- Tests Of Electronic Circuits (AREA)
- Peptides Or Proteins (AREA)
- Emergency Protection Circuit Devices (AREA)
- Vehicle Body Suspensions (AREA)
- Compression, Expansion, Code Conversion, And Decoders (AREA)
Abstract
Procedimiento para la generación de una secuencia seudo-aleatoria en el que se desplazan elementos (ã) de la secuencia seudo-aleatoria con intermedio de un registro de desplazamiento (1) que tiene múltiples celdas de memoria (2) conectadas en serie, los valores de salida de cómo mínimo dos celdas de memoria (2) se enlazan entre sí, y el resultado del enlace es realimentado a una entrada (6) de una de las celdas de memoria (2) del registro de desplazamiento (1), caracterizado porque es tomado el logaritmo discreto de los elementos (ã) de la secuencia seudo-aleatoria y porque el logaritmo discreto ya es calculado cuando son enlazados los valores de salida del registro de desplazamiento (1).
Description
Procedimiento y dispositivo para la producción
de una secuencia seudo-aleatoria mediante un
logaritmo discreto.
La presente invención describe un procedimiento
para la generación de una secuencia seudo-aleatoria,
según el preámbulo de la reivindicación 1, y un dispositivo para
generar una secuencia seudo-aleatoria, según el
preámbulo de la reivindicación 12.
En la generación de secuencias aleatorias se
diferencian básicamente dos variantes. Las secuencias aleatorias
verdaderas son generadas sobre la base de efectos físicos, por
ejemplo, la desintegración radiactiva. Estas secuencias aleatorias
verdaderas pueden tener aplicación particularmente en la
criptografía. En la otra variante, las secuencias
seudo-aleatorias son generadas mediante un
dispositivo designado también como generador
(seudo)aleatorio. Este dispositivo puede formarse, por
ejemplo, mediante un ordenador, en el que se procesa un algoritmo.
Además de esta realización como software, las secuencias
seudo-aleatorias se pueden generar con registros de
desplazamiento, que se encuentran en el hardware, que la mayoría de
las veces están realimentados linealmente. En consecuencia, la
diferencia fundamental entre las secuencias
seudo-aleatorias y las secuencias aleatorias
verdaderas puede consistir en que, conociendo la disposición del
circuito o bien el algoritmo, es posible una repetición o bien la
reconstrucción de la misma secuencia
seudo-aleatoria.
Un procedimiento de esta clase y una disposición
de circuito para la generación de una secuencia
seudo-aleatoria son conocidos por el documento EP 0
616 429 A1. Esta disposición de circuito está realizada mediante un
registro de desplazamiento realimentado, en el que están dispuestas
varias celdas de memoria conectadas en serie
(flip-flops). Como mínimo, son procesados dos
valores de salida de diferentes celdas de memoria y conectados entre
sí en un dispositivo de enlace. El resultado del enlace es
retornado a la entrada del registro de desplazamiento.
Naturalmente, pueden utilizarse una serie de ramas de
realimentación. El enlace de ambos valores de salida de las dos
celdas de memoria tiene lugar en el procedimiento conocido o en la
disposición de circuito conocida como una adición de módulo 2, que
es realizada mediante una puerta (O) exclusiva. El procedimiento
conocido o bien la disposición de circuito conocida encuentra
aplicación, por ejemplo, en el llamado cifrado de corriente.
Además, por el documento WO 99/22484 se conoce un procedimiento y un
dispositivo para la generación de secuencias cifradas numéricas. En
este caso, una relación iterativa y una ecuación inicial son
elegidas de tal manera que ni para la relación iterativa ni para la
ecuación inicial se utilice dos veces el mismo par de elementos de
un registro de desplazamiento. Además, en el documento USA 6.098.192
se muestra un dispositivo y un procedimiento para determinar el
logaritmo de un elemento con menos complicaciones que lo que
exigiría la utilización de tablas de consulta predeterminadas
fijas. Finalmente, por el documento Long D. L. y otros, "The
discrete Logarithm Hides 0 (Log N) Bits", Siam Journal On
Computing, Society for Industrial and Applied Mathematics, EEUU,
tomo 17, Nr. 2, abril 1988 (1988-04), páginas
363-372, XP002901485, ISSN:
0097-5397, se publica como pueden ser evaluadas las
llamadas funciones unidireccionales y como pueden reconstruirse a
partir de una información encriptada al menos partes de la
información sin encriptar.
El objetivo de la presente invención es dar a
conocer otra posibilidad para generar una secuencia
seudo-aleatoria, que dificulte sacar conclusiones
sobre la información encriptada a partir de la información sin
encriptar y que, además, es sencilla de implementar.
Se consigue este objetivo mediante un
procedimiento para la generación de una secuencia
seudo-aleatoria que presenta las características
mencionadas en la reivindicación 1. En un registro de desplazamiento
realizable por hardware o por software con múltiples celdas de
memoria dispuestas en serie, los elementos de la secuencia
seudo-aleatoria son desplazados a través del
registro de desplazamiento. A partir de como mínimo dos niveles de
registros de desplazamiento se enlazan entre sí los valores de
salida. El resultado del enlace puede ser acoplado con la entrada
de uno de los niveles de registro de desplazamiento de la cadena de
registros de desplazamiento. De acuerdo con la invención, el
procedimiento se distingue porque los elementos de la secuencia
pseudo-aleatoria son calculados logarítmicamente de
forma discreta. De este modo resulta, respecto del procedimiento
conocido, una nueva secuencia seudo-aleatoria. La
logaritmación discreta significa que no se logaritmiza toda la
secuencia seudo-aleatoria, sino el de los elementos
individuales de la secuencia seudo-aleatoria. En
este caso, puede estar previsto enlazar entre sí mediante
logaritmación dos elementos de la secuencia
seudo-aleatoria.
En un ejemplo de realización especialmente
preferente se logaritmiza de forma discreta modificada. Debido a
que el logaritmo en el lugar cero no está definido, mientras se
suponga el valor cero de un elemento no se logaritmiza, sino que se
fija entonces un valor predeterminable.
En un ejemplo de realización, la logaritmización
discreta ya se realiza al enlazar los valores de salida de los
niveles de registro de desplazamiento. Básicamente, también sería
imaginable generar primero la secuencia
seudo-aleatoria y a continuación la logaritmización
discreta a la salida de la cadena de registros de desplazamiento,
tal como se ha descrito anteriormente. Naturalmente es posible la
logaritmización discreta de forma múltiple. De este modo, pueden
generarse a la vez otras secuencias
seudo-aleatorias.
En un ejemplo de realización preferente se ha
previsto que se logaritmiza de forma discreta en base a una tabla
logarítmica que contiene valores de salida y valores de resultado.
Es decir, que el valor de salida de una celda de memoria se compara
con los valores de la tabla logarítmica, se elige el resultado
compatible con el valor de salida y se reenvía el mismo como
resultado del enlace a la entrada de una celda de memoria.
En un ejemplo de realización se ha previsto que
uno de los valores de salida a enlazar es preenlazado con un valor
prefijado antes de este enlace, es decir, antes de la
logaritmización discreta. Particularmente, se ha previsto para este
preenlace un enlace lógico, preferentemente una adición. En
consecuencia, cuando en una adición el valor de salida del registro
de desplazamiento es enlazado con un valor cero, el ramal de
realimentación es conectado o bien activado de esta manera porque
siempre es reenviado el valor de salida del registro de
desplazamiento. Cuando el valor de salida del registro de
desplazamiento es enlazado con un uno, podría desconectarse de este
modo el ramal de realimentación. Naturalmente, para el preenlace
también pueden utilizarse valores predefinidos distintos de cero o
uno.
En un ejemplo de realización puede preverse que
se realice el preenlace sobre la base de una tabla de preenlaces,
comprendiendo los valores de salida y de resultado o mediante
circuitos lógicos.
Un ejemplo de realización preferente se destaca
porque los logaritmos discretos son tomados con la ayuda del
llamado logaritmo de Zech o bien logaritmo de Jacobi. Cuando los
logaritmos discretos son tomados utilizando la tabla mencionada
anteriormente, los valores resultantes en esta tabla son
determinados mediante el logaritmo de Zech o bien de Jacobi. Por
consiguiente, la tabla logarítmica se basa en los logaritmos de Zech
o bien de Jacobi en sí conocidos.
Un ejemplo de realización, especialmente
preferente, se destaca porque la realimentación se realiza de manera
tal que es generada una secuencia seudo-aleatoria
con una longitud de período máxima. Es decir, que al menos una de
las ramas de realimentación está dispuesta en salidas específicas de
los niveles de registro de desplazamiento. Para la determinación de
las conexiones de realimentación o bien de la rama de realimentación
que entrega la máxima longitud de período de la secuencia
seudo-aleatoria, en la literatura especializada se
conocen tablas (por ejemplo W. Peterson, E. Weldon,
Error-Correcting Codes, segunda edición, MIT Press,
Cambridge, séptima impresión 1984 o R. Lidl, H. Niederreiter,
Finite Fields, Cambridge University Press 1984).
El objetivo mencionado anteriormente también se
consigue mediante un dispositivo para la generación de una
secuencia seudo-aleatoria que presenta las
características de la reivindicación 12. Este dispositivo comprende
varias celdas de memoria conectadas en serie, formando un registro
de desplazamiento. Además, está dispuesta una rama de
realimentación que conecta dos salidas de registro diferentes con
una entrada de registro. Además, se encuentra previsto un elemento
de enlace para los valores de entrada de los niveles de registro
que, por el lado de la entrada, está conectado con las salidas de
registro y, por el lado de salida, con la entrada de registro.
Según la invención, el dispositivo se caracteriza por un elemento
para la logaritmización discreta de los elementos de la secuencia
seudo-aleatoria. De esta manera, con el dispositivo
según la invención, se realiza otra fuente para la generación de
secuencias seudo-aleatorias que entrega secuencias
seudo-aleatorias que difieren de las secuencias
aleatorias conocidas por el actual estado de la técnica.
Es preferente un ejemplo de realización en el
que el elemento usado para la logaritmización discreta se encuentre
en la rama de la realimentación y forme el elemento de enlace que
toma discretamente los logaritmos de los valores de salida de los
registros. Sin embargo, también puede estar previsto
alternativamente que el elemento para la logaritmización discreta
esté dispuesto al final de la cadena del registro de desplazamiento,
tal como se ha descrito anteriormente en relación con el
procedimiento según la invención.
Es preferente un ejemplo de realización en el
que el elemento es un elemento de memoria en el que está almacenada
la tabla logarítmica que contiene valores de salida y de resultado.
Alternativamente, el elemento también puede estar implementado
mediante módulos lógicos, o sea como hardware.
En un ejemplo de realización está previsto que
entre una de las salidas de registro y el elemento de enlace se
encuentre dispuesto un elemento de preenlace del que una de las
entradas está conectada con dicha salida de registro, cuya otra
entrada es capaz de recibir un valor predefinido y cuya salida está
conectada con la entrada del elemento de enlace. De esta manera es
concebible conectar y desconectar la rama de realimentación o bien
una pluralidad de ramas de realimentación, es decir, activarlas o
desactivarlas.
El elemento de preenlace puede ser un circuito
lógico, particularmente una puerta (O) exclusiva. Sin embargo, el
elemento de preenlace en una realización alternativa también puede
implementarse mediante un elemento de memoria en el que se
encuentran almacenados los resultados del preenlace en función de
los valores de entrada.
Otras configuraciones resultan de las
reivindicaciones.
La invención se explica a continuación sobre la
base de ejemplos de realización con referencia al dibujo, en el que
muestran:
la figura 1, un registro de desplazamiento
lineal realimentado binario, con un elemento para la formación del
logaritmo discreto,
la figura 2, un registro de desplazamiento
lineal realimentado terciario, con un elemento para la formación
del logaritmo discreto,
\newpage
la figura 3, un registro de desplazamiento
lineal general realimentado, con un elemento para la formación de
un logaritmo discreto,
la figura 4, un registro de desplazamiento
lineal realimentado a través del cuerpo GF (2^{2}) = GF (4),
la figura 5, un registro de desplazamiento
lineal realimentado a través del cuerpo GF (2^{2}) = GF (4),
estando el elemento para la formación del logaritmo discreto
dispuesto en la rama de realimentación, y
la figura 6, un registro de desplazamiento
lineal general realimentado, que presenta en las ramas de
realimentación un elemento para la formación del logaritmo
discreto.
La figura 1 muestra sólo de forma ilustrativa un
ejemplo de una cadena de registros de desplazamiento (1) que
presenta una cantidad (m) de celdas de memoria (2) conectadas en
serie. Por consiguiente, la entrada de un nivel de registro de
desplazamiento está conectada con la salida del nivel de registro
precedente. El último nivel de registro de desplazamiento forma la
salida (3) de la cadena (1) de la que puede tomarse la secuencia
seudo-aleatoria a generar. Para la generación de
secuencias seudo-aleatorias se utilizan en la
mayoría de los casos las llamadas cadenas de registro (1)
realimentadas linealmente, que pueden ser fabricadas de forma
integral en hardware, o sea usando elementos lógicos rápidos, con lo
que puede conseguirse una velocidad de procesamiento muy rápida.
Como ya se ha citado, la figura 1 muestra una cadena de
desplazamiento binaria de este tipo. Cada nivel de registro de
desplazamiento (2) es alimentado con una sincronización (T), de
manera que con cada señal de sincronización es cargado, en la celda
de memoria (4) del nivel de registro de desplazamiento (2), el
valor activo en la entrada de un nivel de registro de desplazamiento
(2), y el elemento de la secuencia seudo-aleatoria
almacenada previamente en la celda de memoria (4) está disponible a
la salida del registro (5). Para la sincronización se dispone
preferentemente de un reloj central. La entrada de cada celda de
memoria se muestra en la figura 1 con el numeral (6).
En la rama de realimentación (7) de la cadena de
registro de desplazamiento binaria (1) se encuentra dispuesto un
elemento de enlace (8), cuyas entradas (9) y (10) están conectadas a
salidas de registro (5). La salida (11) del elemento de enlace (8)
está conectada con la entrada (6) de un nivel de registro de
desplazamiento, preferentemente con el primero. En el ejemplo de
realización mostrado el elemento de enlace es un dispositivo de
adición que suma los valores de salida contiguos a las entradas (9)
y (10) del registro, siendo 0 + 0 = 0, 0 + 1 = 1 + 0 = 1 y 1 + 1 =
0 mod 2. Esta adición de módulo 2 puede realizarse de forma
especialmente sencilla mediante un elemento lógico, implementado
como puerta (O) exclusiva. De esta manera queda claro que dada la
ocupación inicial de las celdas de memoria (4) de la cadena de
registros de desplazamiento (1), mostrada en la figura 1, puede
generarse una secuencia seudo-aleatoria usando
elementos 0100111010.... Esta secuencia
seudo-aleatoria se encuentra en la salida (3) de la
cadena de registros de desplazamiento o bien puede ser tomada en
esta salida (3).
Se ha previsto que la secuencia
seudo-aleatoria dispuesta en la salida (3) se
calcula logarítmicamente de forma discreta. Para este fin, un
elemento de cálculo logarítmico (12) que realiza la logaritmización
discreta de los elementos de la secuencia
seudo-aleatoria es conectado detrás de la salida
(3). Para la logaritmización discreta puede disponerse que un
elemento de la secuencia seudo-aleatoria sea
enlazado con otro elemento de la secuencia
seudo-aleatoria. Sin embargo, también puede
disponerse que un elemento de la secuencia
seudo-aleatoria sea enlazado con un valor (W)
predefinido contiguo al elemento (12).
A la salida de elementos (13) se presenta
entonces la secuencia seudo-aleatoria calculada
logarítmicamente de forma discreta. Preferentemente se realiza una
logaritmación discreta, es decir, mientras un elemento de la
secuencia seudo-aleatoria presente el valor 0, el
elemento es fijado a un valor resultante predefinible, debido a
que, como es sabido, la formación de un logaritmo de 0 no es
posible.
Una ventaja del registro de desplazamiento (1)
realimentado linealmente es que es relativamente sencillo determinar
los parámetros para conseguir la longitud de período máxima posible
de la secuencia seudo-aleatoria. Como parámetro han
de ser indicadas las salidas de registro (5), cuyos valores de
salida deben ser enlazados con el elemento de enlace (8).
Consecuentemente, debe estar indicada la posición de las conexiones
de realimentación, con lo que también debe indicarse a que entrada
de registro (6) debe conectarse la salida (11) del elemento de
enlace. Una cadena de registros de desplazamiento (1) lineal binaria
realimentada de una longitud (m), o sea la cantidad de niveles de
registros de desplazamiento (2), puede generar una secuencia binaria
seudo-aleatoria, que se repite sólo después de
2^{m} - 1 bits. Tablas con conexiones de realimentación que
indican la longitud máxima de períodos se encuentran en la
literatura (por ejemplo, W. Peterson, E. Weldon,
Error-Correcting Codes, segunda edición, MIT Press,
Cambridge, séptima impresión 1984 o R. Lidl, H. Niederreiter, Finite
Fields, Cambridge University Press, 1984).
Naturalmente, también es posible utilizar
secuencias no binarias en lugar de secuencias de registros de
desplazamiento binarias. Una cadena de registros de desplazamiento
(1) no binaria se muestra en la figura 2. A diferencia de la cadena
de registros de desplazamiento (1), según la figura 1, entre la
entrada (10) del elemento de enlace (8) y la salida de registro (5)
está intercalado un elemento de preenlace (14). Dicho elemento posee
dos entradas de preenlace (15) y (16), así como una salida de
preenlace (17), conectadas a la entrada (10) del elemento de
preenlace (8). El elemento de preenlace (14) en una forma de
realización preferente ejecuta una multiplicación. En consecuencia,
en la cadena de registros de desplazamiento (1), el elemento de
enlace (8) y el elemento de preenlace (14) representan la suma y la
multiplicación módulo 3, es decir, se realiza la suma o bien la
multiplicación de las cifras del conjunto {0, 1, 2} y se resta el
valor 3 del resultado cuando el mismo es mayor de 2. De allí, a la
salida (3) de la cadena de registros de desplazamiento (1) resulta
una secuencia seudo-aleatoria con los elementos
00111021121010022201221202 001.... Esta secuencia
seudo-aleatoria es, como en la cadena de registros
de desplazamiento (1), según la figura 1, alimentada al elemento de
logaritmización (12). Otra diferencia consiste en que en la rama de
realimentación (7) se encuentra dispuesto otro elemento de
multiplicación (18), idéntico al elemento de preenlace (14). La
entrada (19) del elemento de multiplicación está conectada con la
salida (11) del elemento de enlace (8). La segunda entrada (20) del
elemento de multiplicación recibe para la función módulo 2 el
parámetro de entrada apropiado. La salida (21) del elemento de
multiplicación (18) está conectada a la entrada (6) del primer
nivel de registros de desplazamiento (2). Por lo demás, componentes
iguales o de efecto igual en la figura 1 son designados en la figura
2 con el mismo
numeral.
numeral.
La figura 3 muestra una cadena de registros de
desplazamiento (1), que utiliza como alfabeto GF(q) un
llamado cuerpo de ampliación binario con q = 2^{m}. Son
convenientes con cuerpos de ampliación binarios porque los mismos
son muy indicados para el formato binario usado habitualmente en el
procesamiento de datos. La cadena de registros de desplazamiento
(1) realimentada linealmente tiene entonces la forma mostrada en la
figura 3. Consecuentemente, tal como se indica en la figura 2,
están dispuestos elementos de preenlace (14) situados cada uno
entre la salida de un nivel de registros de desplazamiento y la
entrada del elemento de enlace (8). Como puede verse en la figura
3, cada salida de registro de desplazamiento (5) puede estar
realimentada a través de un elemento de preenlace (14) y un
elemento de enlace (8), o sea dirigido a una entrada (6) de otro
nivel de registro de desplazamiento, siendo naturalmente las
operaciones de enlace realizadas en relación con las figuras 1 y 2
implementadas en los elementos de preenlace (14) y en los elementos
de enlace (8). Partes iguales o de efectos iguales se designan en
la figura 3 con los mismos numerales de las figuras 1 y 2.
A continuación se observa, en base a la figura
3, una cadena de registros de desplazamiento (1) sobre el alfabeto
GF (q), caracterizando GF (q) un cuerpo con q = p^{m} elementos,
donde q es una potencia de números primos. Está demostrado que
esencialmente se mantiene la estructura de los niveles de registros
de desplazamiento realimentados lineales en comparación con el
actual estado de la técnica. Sin embargo, como muestran las figuras
1 a 4, la secuencia seudo-aleatoria es manipulada
por la media de la formación del logaritmo discreto mínimamente
modificada, en la que las operaciones de cálculo necesarias para la
formación del logaritmo son traspuestas en un conjunto de números
en el que las operaciones necesarias pueden ser realizadas
fácilmente por la mayoría de las calculadoras/procesadores. En
lugar de la multiplicación en el elemento de preenlace (14) se
realiza ahora la adición módulo p^{m}-1 y en
lugar de la adición en el elemento de enlace (8) una operación
sustitutiva correspondiente, pudiendo realizarse esta operación
sustitutiva, por ejemplo, mediante una tabla. En consecuencia, en
el elemento de enlace (8) puede estar contenida una memoria para una
tabla de este tipo, en la que en función de los valores de entrada
se elige un valor resultante respectivo.
Las secuencias seudo-aleatorias
obtenidas son diferentes a las secuencias que, según el estado
actual de la técnica, son generadas por registros de desplazamiento
realimentados. Sin embargo, debido a la estructura de la cadena de
registros de desplazamiento alimentada en forma lineal puede
determinarse exactamente la longitud de período de la secuencia
seudo-aleatoria. La longitud de período está dada
por la longitud de período del registro de desplazamiento
subordinado.
Si se toma, por ejemplo, la cadena de registros
de desplazamiento (1) mostrada en la figura 4 con la cantidad m = 3
niveles de registros de desplazamiento sobre el cuerpo GF (2^{2})
= (00,01,10,11), se consigue una secuencia
seudo-aleatoria con la longitud de período
4^{3}-1 = 63. En la figura 4 se muestran en la
celda de memoria (4) de cada registro de desplazamiento (2) los
distintos elementos del cuerpo GF.
Para que se pueda calcular con los elementos del
cuerpo GF, pueden utilizarse, por ejemplo, las dos tablas mostradas
a continuación para la adición y multiplicación en este cuerpo.
Consecuentemente, estas tablas contienen valores de salida que
tienen asignados de forma unívoca valores de resultado
correspondientes. O sea, estas tablas pueden ser llamadas y
procesadas en elementos de enlace (8) y (14).
\vskip1.000000\baselineskip
| + | 00 | 01 | 10 | 11 |
| 00 | 00 | 01 | 10 | 11 |
| 01 | 01 | 00 | 11 | 10 |
| 10 | 10 | 11 | 00 | 01 |
| 11 | 11 | 10 | 01 | 00 |
| + | 00 | 01 | 10 | 11 |
| 00 | 00 | 00 | 00 | 00 |
| 01 | 00 | 01 | 10 | 11 |
| 10 | 00 | 10 | 11 | 01 |
| 11 | 00 | 11 | 01 | 10 |
\vskip1.000000\baselineskip
La adición de extensiones algebraicas binarias
GF es bastante sencilla, concretamente un elemento de enlace (O)
exclusivo en forma de componente, mientras que contrariamente, la
multiplicación en extensiones algebraicas es más complicada. Puede
realizarse mediante circuitos especiales o mediante tablas.
Con la asignación inicial de las celdas de
memoria (4) mostrada en la figura 4 con 00, 00 y 01 se consigue
para la cadena de registros de desplazamiento, según la figura 4, la
secuencia 00 00 01 11 10 00 11 00 00 11 10 01 00 10 00 00 10 01 11
01.... De la secuencia seudo-aleatoria así obtenida
se logaritmiza de forma discreta, como en los ejemplos según las
figuras 1 a 3, mediante el elemento (12). De esta manera se remite a
las descripciones de las figuras precedentes.
En lugar de los elementos (12), mostrados en las
figuras 1 a 4, para la formación modificada del logaritmo discreto
en la salida (3) de la cadena de registros de desplazamiento (1), se
describe a continuación, sobre la base de las figuras 5 y 6, una
forma de realización preferente de cadenas de registros de
desplazamiento (1) para la generación de secuencias
seudo-aleatorias. La imagen discreta es, como ya se
ha mencionado, la formación modificada del logaritmo discreto que
se explica en detalle más adelante. La diferencia esencial respecto
de los ejemplos de realización descritos anteriormente consiste
ahora en utilizar aquellas estructuras de la cadena de registros de
desplazamiento (1) de los registros de desplazamiento realimentadas
(2) que realizan enlaces en los elementos de enlace (8) y (14),
pero no como se ha descrito anteriormente como una adición o
multiplicación, sino sustituyendo con la formación del logaritmo
discreto. Esto quiere decir que el elemento (12), hasta ahora
conectado a la salida (3), es en adelante trasladado a la rama de
realimentación (7). De esta manera, el elemento de enlace (8) se
encarga de la toma modificada del logaritmo discreto.
Las operaciones matemáticas requeridas son
relocalizadas a un conjunto numérico en el que las operaciones
necesarias para el enlace pueden realizarse fácilmente por las
calculadoras/procesadores. En lugar de la multiplicación del campo
Galois en el elemento de preenlace (14) se realiza esencialmente la
adición módulo p^{m}-1 y en lugar de la adición
en el elemento de enlace (8) una operación sustitutiva
correspondiente que puede realizarse, por ejemplo, con módulos
lógicos o también con una tabla. Esta operación sustitutiva está
designada en las figuras 5 y 6 con la indicación de la referencia
-. El elemento de enlace (8') en la rama de realimentación (7)
(figura 5) o bien los elementos lógicos (8') en la rama de
realimentación (7) (figura 6) realizan, consecuentemente, la
formación modificada del logaritmo discreto. Contrariamente, en los
elementos de preenlace (14) o bien en el elemento de preenlace
(14') se realiza la adición módulo p^{m}-1.
A continuación se describe la función de las
cadenas de registros de desplazamiento (1), según las figuras 5 y
6. Es sabido que en un cuerpo finito GF (p^{m}) cada elemento de
cuerpo \gamma diferente de 0 puede representarse como potencia de
un llamado elemento primitivo \alpha, es decir, como
\alpha^{i} para i = 0....p^{m}-2. Para el
campo Galois GF (2^{2}) se obtiene, por ejemplo,
\dotable{\tabskip\tabcolsep\hfil#\hfil\+#\hfil\+\hfil#\hfil\tabskip0ptplus1fil\dddarstrut\cr}{
i \+ \hskip3cm \+ \gamma = \alpha ^{i} \cr \+\+\cr 0
\+ \+ 01\cr 1 \+ \+ 10\cr 2 \+ \+
11\cr}
El logaritmo discreto para los elementos de
cuerpo \gamma es definido como sigue:
log \ (\gamma)
= i \hskip0.5cm para \hskip0.5cm \gamma = \alpha^{i}, \ i =
0...p^{m}-2.
Si además se agrega la modificación log
(\gamma)= p^{m}-1 para \gamma = 0, se obtiene
la definición mínimamente modificada del logaritmo discreto,
apropiada para la sustancia de la invención.
Para el caso GF (2^{2}) se obtiene para los
elementos \gamma la siguiente tabla:
| \gamma | log (\gamma) | |
| 00 | 11 (corresponde a 3) | |
| 01 | 00 (corresponde a 0) | |
| 10 | 01 (corresponde a 1) | |
| 11 | 10 (corresponde a 2) |
En esta tabla los valores integrales de log
(\gamma) son suministrados como notación binaria. Por la
corrección matemática debe mencionarse que la formación del
logaritmo conduce a valores integrales y no a elementos del cuerpo
finito. Sin embargo, no es relevante para el uso de los elementos de
la secuencia seudo-aleatoria, es decir de los bits.
La definición introducida para el logaritmo de 0 lleva a que la
función logarítmica se convierta en una función biyectiva
(biunívoca) de GF (p^{m}) sobre
(0,1,...p^{m}-1). Mediante la logaritmización con
ayuda del logaritmo discreto de base \alpha = 10, la secuencia
seudo-aleatoria descrita en relación a la figura 4
se convierte en la secuencia 11 11 00 10 01 11 10 11 11 10 01 00 11
01 11 11 01 11 11 01 00 10 00... Esta secuencia puede generarse
mediante la cadena de registro de desplazamiento (1), según la
figura 5.
En lugar de la multiplicación en el cuerpo del
campo Galois GF (q) = GF (2^{2}) se ha realizado en lo esencial
una adición módulo 2^{2}-1 = 3 y en lugar de la
adición en el cuerpo finito la operación -, que se explica a
continuación. La asignación inicial de las celdas de memoria (4),
según la figura 4, es trasladada mediante el logaritmo discreto a
la asignación inicial de las celdas de memoria (4) de la figura 5.
El procedimiento es apropiado particularmente para la extensión
binaria. Contrariamente, para registros de desplazamiento binarios
puros (figura 1) conduce sólo a un intercambio de ceros y unos. En
la siguiente tabla se muestran los enlaces en el elemento de enlace
(8'), adición módulo 3 y la operación - para el registro de
desplazamiento (1), según la figura 5, es decir para el cuerpo GF
(2^{2}).
\vskip1.000000\baselineskip
| + | 00 | 01 | 10 | 11 |
| 00 | 00 | 01 | 10 | 11 |
| 01 | 01 | 10 | 00 | 11 |
| 10 | 10 | 00 | 01 | 11 |
| 11 | 11 | 11 | 11 | 11 |
| (+) elemento de enlace de la cadena de registros de desplazamiento (1), según la figura 5 |
\vskip1.000000\baselineskip
| \sim | 00 | 01 | 10 | 11 |
| 00 | 11 | 10 | 01 | 00 |
| 01 | 10 | 11 | 00 | 01 |
| 10 | 01 | 00 | 11 | 10 |
| 11 | 00 | 01 | 10 | 11 |
| \sim elemento de enlace de la cadena de registros de desplazamiento (1), según la figura 5 |
La cadena de registros de desplazamiento (1)
general para cuerpos de ampliación binaria GF (2^{m}) se muestra
en la figura 6. Para la cadena de registros de desplazamiento (1),
según la figura 6, han de repetirse de modo global los pasos
individuales. En primer lugar, se elige una cadena de registros de
desplazamiento (1) correspondiente, según la figura 3, con
operaciones sobre el cuerpo GF(2^{m}). A continuación se
reemplazan las multiplicaciones de cuerpo Galois esencialmente por
una adición módulo 2^{m}-1. La diferencia respecto
de la adición módulo 2^{m}-1 es que para la
asignación de todos los unos, la salida (3) tiene asimismo la
asignación todos los unos. La adición GF (2^{m}) es reemplazada
por la operación \sim, que puede realizarse mediante circuito
lógico o las tablas descritas anteriormente. En el caso de la
implementación por tablas puede usarse el llamado logaritmo Zech
y/o logaritmo Jacobi. Para obtener el resultado de la operación
\sim puede colocarse:
i\sim j =
j\sim i = log \ (\alpha^{i}+\alpha^{j}) = i + log \
\alpha^{(i-z(i-j))}
\hskip0.5cm para \ i >
j
i\sim j =
2^{m}-1 \hskip0.5cm para \ i =
j
\newpage
estando el logaritmo Zech definido
por la ecuación \alpha^{z(k)} = 1+\alpha^{k}. Para el
cuerpo GF (2^{2}) se obtiene entonces la siguiente tabla
logarítmica:
\dotable{\tabskip\tabcolsep\hfil#\hfil\+#\hfil\+\hfil#\hfil\tabskip0ptplus1fil\dddarstrut\cr}{
i \+ \hskip3cm \+ Z (i)\cr \+\+\cr 00 \+ \+ 11\cr
01 \+ \+ 10\cr 10 \+ \+ 10\cr 11 \+ \+
00\cr}
resumiendo, para todas las cadenas
de registros de desplazamiento (1), según las figuras 1 a 5, puede
indicarse un procedimiento para la generación de secuencias
seudo-aleatorias. Este procedimiento se basa
esencialmente en la formación de logaritmos discretos modificados
de secuencias de registros de desplazamiento. La generación de
secuencias seudo-aleatorias no se hace, en una forma
de realización preferente, mediante la posterior formación de
logaritmos (figuras 1 a 4), sino de modo preferente directamente en
la generación de la secuencia seudo-aleatoria, tal
como se muestra en las figuras 5 y 6. El procedimiento es ventajoso
particularmente cuando el tamaño del alfabeto observado, o sea el
cuerpo, es una segunda potencia, por ejemplo 256, pudiendo
representarse este alfabeto con la ayuda de un
byte.
Claims (14)
1. Procedimiento para la generación de una
secuencia seudo-aleatoria en el que se desplazan
elementos (\gamma) de la secuencia
seudo-aleatoria con intermedio de un registro de
desplazamiento (1) que tiene múltiples celdas de memoria (2)
conectadas en serie, los valores de salida de cómo mínimo dos celdas
de memoria (2) se enlazan entre sí, y el resultado del enlace es
realimentado a una entrada (6) de una de las celdas de memoria (2)
del registro de desplazamiento (1), caracterizado porque es
tomado el logaritmo discreto de los elementos (\gamma) de la
secuencia seudo-aleatoria y porque el logaritmo
discreto ya es calculado cuando son enlazados los valores de salida
del registro de desplazamiento (1).
2. Procedimiento, según la reivindicación 1,
caracterizado porque la logaritmación discreta se toma de
una manera modificada tal, que en lugar de la logaritmización de un
elemento (\gamma) con el valor cero se inserta un valor
predeterminable.
3. Procedimiento, según una de las
reivindicaciones anteriores, caracterizado porque la
logaritmización discreta es realizada múltiples veces.
4. Procedimiento, según una de las
reivindicaciones anteriores, caracterizado porque la
logaritmación discreta se toma con la ayuda de una tabla que
contiene los valores de salida y de resultado.
5. Procedimiento, según una de las
reivindicaciones anteriores, caracterizado porque como mínimo
uno de los valores de salida a enlazar entre sí es preenlazado con
un valor predeterminable antes de dicho enlace.
6. Procedimiento, según una de las
reivindicaciones anteriores, caracterizado porque dicho
preenlace es un enlace, preferentemente una adición.
7. Procedimiento, según una de las
reivindicaciones anteriores, caracterizado porque el
preenlace se realiza sobre la base de una tabla de preenlace que
contiene valores de salida y de resultado o mediante circuitos
lógicos.
8. Procedimiento, según una de las
reivindicaciones anteriores, caracterizado porque la
logaritmización discreta es realizada con ayuda del logaritmo de
Zech o bien el logaritmo de Jacobi.
9. Procedimiento, según una de las
reivindicaciones anteriores, caracterizado porque la tabla
logarítmica está basada en el logaritmo de Zech o bien el logaritmo
de Jacobi.
10. Procedimiento, según una de las
reivindicaciones anteriores, caracterizado porque la
realimentación es realizada de manera tal, que se genera una
secuencia seudo-aleatoria con longitud de período
máxima.
11. Dispositivo para la generación de una
secuencia seudo-aleatoria, con un registro de
desplazamiento (1) teniendo múltiples celdas de memoria (2)
conectadas en serie, una rama de realimentación (7) que conecta dos
salidas de registro (5) diferentes a una entrada de registro (6), y
un elemento de enlace (8) para los valores de salida de los
registros (2), estando dicho elemento de enlace (8) conectado por el
lado de la entrada con las salidas de registro (5) y por el lado de
la salida a la entrada de registro (6), caracterizado porque
un elemento (8') está dispuesto para la logaritmización discreta de
los elementos (\gamma) de la secuencia
seudo-aleatoria, y el elemento (8') se encuentra
dispuesto en la rama de realimentación (7) constituyendo el
elemento de enlace (8) que logaritmiza de forma discreta los valores
de salida de los niveles de registro (2).
12. Dispositivo, según la reivindicación 11,
caracterizado porque el elemento (8') es un elemento de
memoria en el que se encuentra almacenada una tabla logarítmica
conteniendo los valores de salida y de resultado.
13. Dispositivo, según la reivindicación 11 ó
12, caracterizado porque entre una de las salidas de registro
(5) y el elemento de enlace (8, 8') se encuentra un elemento de
preenlace (14), en el que una entrada (15) es conectada con dicha
salida (5) del nivel de registro (2), en el que otra entrada (16)
puede recibir un valor predeterminado, y en el que la salida (17)
está conectada a la entrada (10) del elemento de enlace (8,
8').
14. Dispositivo, según una de las
reivindicaciones 11 a 13, caracterizado porque el elemento de
preenlace (14) es un circuito lógico.
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| DE10061315 | 2000-12-08 | ||
| DE10061315A DE10061315A1 (de) | 2000-12-08 | 2000-12-08 | Verfahren und Vorrichtung zum Erzeugen einer Pseudozufallsfolge |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| ES2266248T3 true ES2266248T3 (es) | 2007-03-01 |
Family
ID=7666435
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| ES01967345T Expired - Lifetime ES2266248T3 (es) | 2000-12-08 | 2001-09-14 | Procedimiento y dispositivo para la produccion de una secuencia sendo-aleatoria mediante un logaritmo discreto. |
Country Status (9)
| Country | Link |
|---|---|
| US (1) | US20040054703A1 (es) |
| EP (1) | EP1342153B1 (es) |
| JP (1) | JP4566513B2 (es) |
| AT (1) | ATE329306T1 (es) |
| CZ (1) | CZ304974B6 (es) |
| DE (2) | DE10061315A1 (es) |
| ES (1) | ES2266248T3 (es) |
| PL (1) | PL362501A1 (es) |
| WO (1) | WO2002046912A1 (es) |
Families Citing this family (11)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US20140055290A1 (en) | 2003-09-09 | 2014-02-27 | Peter Lablans | Methods and Apparatus in Alternate Finite Field Based Coders and Decoders |
| US7865806B2 (en) * | 2006-03-03 | 2011-01-04 | Peter Lablans | Methods and apparatus in finite field polynomial implementations |
| US7580472B2 (en) * | 2004-02-25 | 2009-08-25 | Ternarylogic Llc | Generation and detection of non-binary digital sequences |
| US7696785B2 (en) * | 2004-02-25 | 2010-04-13 | Ternarylogic Llc | Implementing logic functions with non-magnitude based physical phenomena |
| US8374289B2 (en) | 2004-02-25 | 2013-02-12 | Ternarylogic Llc | Generation and detection of non-binary digital sequences |
| US7218144B2 (en) * | 2004-02-25 | 2007-05-15 | Ternarylogic Llc | Single and composite binary and multi-valued logic functions from gates and inverters |
| US7548092B2 (en) | 2004-02-25 | 2009-06-16 | Ternarylogic Llc | Implementing logic functions with non-magnitude based physical phenomena |
| US20060021003A1 (en) * | 2004-06-23 | 2006-01-26 | Janus Software, Inc | Biometric authentication system |
| US7562106B2 (en) * | 2004-08-07 | 2009-07-14 | Ternarylogic Llc | Multi-value digital calculating circuits, including multipliers |
| US20100164548A1 (en) * | 2004-09-08 | 2010-07-01 | Ternarylogic Llc | Implementing Logic Functions With Non-Magnitude Based Physical Phenomena |
| US7933354B2 (en) * | 2006-11-22 | 2011-04-26 | Semtech Corporation | Encoding and decoding architecture and method for pipelining encoded data or pipelining with a look-ahead strategy |
Family Cites Families (13)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US4410989A (en) * | 1980-12-11 | 1983-10-18 | Cyclotomics, Inc. | Bit serial encoder |
| JPH07101840B2 (ja) * | 1989-08-01 | 1995-11-01 | 三菱電機株式会社 | ディジタル雑音信号発生回路 |
| EP0460352B1 (en) * | 1990-06-07 | 1995-11-02 | International Business Machines Corporation | System for test data storage reduction |
| JPH04182828A (ja) * | 1990-11-19 | 1992-06-30 | Fujitsu Ltd | 擬似乱数によるテーブル内エントリー選択方式 |
| US5422895A (en) * | 1992-01-09 | 1995-06-06 | Quantum Corporation | Cross-checking for on-the-fly Reed Solomon error correction code |
| TW256969B (es) * | 1993-01-19 | 1995-09-11 | Siemens Ag | |
| JPH10117128A (ja) * | 1996-10-08 | 1998-05-06 | Kokusai Electric Co Ltd | 疑似雑音系列符号位相制御装置 |
| US6098192A (en) * | 1997-09-17 | 2000-08-01 | Cirrus Logic, Inc. | Cost reduced finite field processor for error correction in computer storage devices |
| US6510228B2 (en) * | 1997-09-22 | 2003-01-21 | Qualcomm, Incorporated | Method and apparatus for generating encryption stream ciphers |
| US6252958B1 (en) * | 1997-09-22 | 2001-06-26 | Qualcomm Incorporated | Method and apparatus for generating encryption stream ciphers |
| EP0929040A3 (en) * | 1997-12-25 | 2007-06-27 | Nippon Telegraph and Telephone Corporation | Microprocessor with data randomizing |
| US6326808B1 (en) * | 1998-12-03 | 2001-12-04 | Vantis Corporation | Inversion of product term line before or logic in a programmable logic device (PLD) |
| US6208618B1 (en) * | 1998-12-04 | 2001-03-27 | Tellabs Operations, Inc. | Method and apparatus for replacing lost PSTN data in a packet network |
-
2000
- 2000-12-08 DE DE10061315A patent/DE10061315A1/de not_active Withdrawn
-
2001
- 2001-09-14 AT AT01967345T patent/ATE329306T1/de active
- 2001-09-14 ES ES01967345T patent/ES2266248T3/es not_active Expired - Lifetime
- 2001-09-14 US US10/450,188 patent/US20040054703A1/en not_active Abandoned
- 2001-09-14 PL PL01362501A patent/PL362501A1/xx not_active Application Discontinuation
- 2001-09-14 DE DE50110078T patent/DE50110078D1/de not_active Expired - Lifetime
- 2001-09-14 CZ CZ2003-1598A patent/CZ304974B6/cs not_active IP Right Cessation
- 2001-09-14 WO PCT/EP2001/010650 patent/WO2002046912A1/de not_active Ceased
- 2001-09-14 EP EP01967345A patent/EP1342153B1/de not_active Expired - Lifetime
- 2001-09-14 JP JP2002548574A patent/JP4566513B2/ja not_active Expired - Lifetime
Also Published As
| Publication number | Publication date |
|---|---|
| CZ304974B6 (cs) | 2015-02-25 |
| ATE329306T1 (de) | 2006-06-15 |
| EP1342153B1 (de) | 2006-06-07 |
| WO2002046912A1 (de) | 2002-06-13 |
| JP4566513B2 (ja) | 2010-10-20 |
| DE50110078D1 (de) | 2006-07-20 |
| DE10061315A1 (de) | 2002-06-13 |
| JP2004515855A (ja) | 2004-05-27 |
| US20040054703A1 (en) | 2004-03-18 |
| PL362501A1 (en) | 2004-11-02 |
| CZ20031598A3 (cs) | 2003-08-13 |
| EP1342153A1 (de) | 2003-09-10 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| EP2000901B1 (en) | Galois field number generator | |
| ES2266248T3 (es) | Procedimiento y dispositivo para la produccion de una secuencia sendo-aleatoria mediante un logaritmo discreto. | |
| EP2291735B1 (en) | Cryptographic system including a random number generator using finite field arithmetics | |
| JP4954941B2 (ja) | 引き起こされた非位取り誤りによる暗号化 | |
| US8139764B2 (en) | Closed galois field cryptographic system | |
| JP2008299330A (ja) | 閉ガロア体組合せ | |
| CN110413257A (zh) | 随机数产生电路 | |
| Cardell et al. | Discrete linear models for the generalized self-shrunken sequences | |
| Deepthi et al. | Design, implementation and analysis of hardware efficient stream ciphers using LFSR based hash functions | |
| US9696965B2 (en) | Input-dependent random number generation using memory arrays | |
| Fúster-Sabater | Generation of cryptographic sequences by means of difference equations | |
| ES2357290T3 (es) | Procedimiento y dispositivo de reducción de un polinomio en un campo finito binario, en particular para una aplicación criptográfica. | |
| Bishoi et al. | Shrinking generators based on σ-LFSRs | |
| Buchmann et al. | Discrete logarithms: Recent progress | |
| JPH10308720A (ja) | Ｍ系列を任意にシフトする回路 | |
| Fúster-Sabater et al. | Strategic attack on the shrinking generator | |
| ES2293665T3 (es) | Metodo para la conversion criptografica de bloques de entrada de l bits de informacion de datos digitales en bloques de salida de l bits. | |
| Mitchell | A nonlinear random number generator with known, long cycle length | |
| JP4374504B2 (ja) | 有限体上の２次多項式の求根回路 | |
| RU2743412C1 (ru) | Устройство для реализации алгоритма шифрования «кузнечик» стандарта гост р 34.12-2015 и алгоритма хэш-функции «стрибог» стандарта гост р 34.11-2012 | |
| JP3936476B2 (ja) | 符号生成器 | |
| JP2980588B1 (ja) | 乱数発生方法及び暗号通信方法並びに乱数発生プログラムを記憶した記憶媒体 | |
| Karpinskyy et al. | Masked encryption algorithm mcrypton for resource-constrained devices | |
| KR20030059500A (ko) | 에스.피.엔(ｓｐｎ) 구조를 가지는 블록 암호를 이용한유사난수 발생기 및 방법 | |
| Tian et al. | On FCSR memory sequences |