ES2296862T3 - Dispositivo de salida de matriz numerica, procedimiento de salida de matriz numerica, dispositivo de encriptacion y dispositivo de desencriptacion. - Google Patents
Dispositivo de salida de matriz numerica, procedimiento de salida de matriz numerica, dispositivo de encriptacion y dispositivo de desencriptacion. Download PDFInfo
- Publication number
- ES2296862T3 ES2296862T3 ES02022986T ES02022986T ES2296862T3 ES 2296862 T3 ES2296862 T3 ES 2296862T3 ES 02022986 T ES02022986 T ES 02022986T ES 02022986 T ES02022986 T ES 02022986T ES 2296862 T3 ES2296862 T3 ES 2296862T3
- Authority
- ES
- Spain
- Prior art keywords
- unit
- matrix
- integer
- value
- vector
- 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
-
- 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/30—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy
- H04L9/3093—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy involving Lattices or polynomial equations, e.g. NTRU scheme
Landscapes
- Engineering & Computer Science (AREA)
- Pure & Applied Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Mathematical Analysis (AREA)
- Mathematical Optimization (AREA)
- Mathematical Physics (AREA)
- Physics & Mathematics (AREA)
- Algebra (AREA)
- Computing Systems (AREA)
- Theoretical Computer Science (AREA)
- Computer Security & Cryptography (AREA)
- Computer Networks & Wireless Communication (AREA)
- Signal Processing (AREA)
- Storage Device Security (AREA)
Abstract
Dispositivo de encriptación (10) para encriptar un mensaje, que comprende: una unidad de salida de valores de función (40) que puede funcionar para calcular un valor de función del mensaje utilizando una función de conversión de un sentido; caracterizado porque presenta un dispositivo de salida de matriz numérica (100) que puede funcionar para generar un vector de n elementos dependiendo del valor de función que se utiliza como entero de entrada mayor o igual a 0, en el que cada uno de los n elementos seleccionado es uno de los K valores de entero predeterminados diferentes, comprendiendo dicho dispositivo de salida de matriz numérica (100): una unidad de determinación de matriz inicial (110) que puede utilizarse para elegir un vector de n elementos como vector inicial, y una unidad de cambio adaptada para recibir el valor de función como entrada y operativa para cambiar un elemento del vector inicial elegido por la unidad de determinación de matriz inicial, incluyendo dicha unidad de cambio: una unidad de división que puede funcionar para dividir primero el valor de función por un entero positivo específico c que es menor o igual a n, y generar un resto, y a continuación dividir repetidamente el cociente obtenido mediante la división por el entero específico c, reduciendo al mismo tiempo del entero específico c en una unidad por cada división, empezando por n y acabando por 2, y generar restos y una unidad de sustitución (120) adaptada para sustituir repetidamente el c-ésimo elemento del vector inicial por un elemento del vector inicial situado en una posición correspondiente a cada uno de los restos generados repetidamente por la unidad de división; una unidad de generación de texto de encriptación (50) operativa para generar un texto de encriptación del mensaje, utilizando el polinomio correspondiente al vector de n elementos generado por el dispositivo de salida de matriz numérica (100).
Description
Dispositivo de salida de matriz numérica,
procedimiento de salida de matriz numérica, dispositivo de
encriptación y dispositivo de desencriptación.
La presente invención se refiere a un
dispositivo de salida de matriz numérica que convierte un entero en
una matriz y, en particular, se refiere al dispositivo de salida de
matriz numérica que se utiliza como técnica de seguridad de la
información en las técnicas de encriptación, las técnicas de
corrección de errores y las técnicas de firma digital.
Un procedimiento de comunicación privado es un
procedimiento que permite la comunicación con el interlocutor de la
comunicación particular sin que se produzca ninguna fuga del
contenido de la comunicación hacia cualquier otra persona. Un
procedimiento de firma digital es un procedimiento de comunicación
que confirma al interlocutor la validez del contenido de la
comunicación y de la identidad del remitente de la comunicación. En
este procedimiento de firma, se utiliza un procedimiento de
encriptación denominado "encriptación de clave pública". La
encriptación de clave pública es un procedimiento que permite
gestionar con facilidad las claves de encriptación diferentes de
los participantes de una comunicación cuando existe más de un
interlocutor, siendo este procedimiento una tecnología obligatoria
y fundamental para la comunicación con varios interlocutores. En
resumen, la clave de encriptación de este procedimiento es
diferente de la clave de desencriptación y se trata como una clave
pública, mientras que la clave de desencriptación se trata como una
clave privada. La encriptación de clave pública se describe en
detalle en el documento "Modern Encryption", Industry Book,
1997, de Tatsuaki Okamoto e Hiroshi Yamamoto (denominado en lo
sucesivo "Documento 1").
Un tipo de encriptación de clave pública es la
denominada "encriptación NTRU". En la encriptación NTRU, el
tamaño del código de encriptación es pequeño comparado con el código
de la encriptación de curva elíptica. La encriptación NTRU puede
instalarse en las CPU de bajo rendimiento, tales como las utilizadas
en los electrodomésticos. En consecuencia, este procedimiento de
encriptación presenta un gran potencial en el futuro.
La encriptación NTRU se describe en detalle en
el documento "NTRU: A ring based public key cryptosystem",
Jeffrey Hoffstein, Jill Pipher y Joseph H. Silverman, Lecture Notes
in Computer Science, 1423, pp. 267-288,
Springer-Verlag, 1998 (denominado en lo sucesivo
"Documento 2").
A continuación, se describirá la encriptación
NTRU.
En general, todos los polinomios para
f(X) se expresan de la siguiente forma:
El polinomio f(X) se expresa en relación
con un vector n-dimensional (f_{0}, f_{1},
f_{2}, ..., f_{N-1}). Asimismo, entre estos
vectores n-dimensionales, el vector que representa
n1 término(s) de valor 1, n2 término(s) de valor -1 y
otro(s) (n-n1-n2)
término(s) de valor 0 se expresa como L (n, n1, n2).
En la encriptación NTRU, las claves de
desencriptación tratadas como claves privadas (denominadas en lo
sucesivo "claves privadas") f(v) y Fp(v) se
expresan mediante una fórmula indicada a continuación. El código
adjunto a (v), tal como f(v) y Fp(v), indica un
polinomio.
La clave privada f(v) \in un conjunto
de polinomios Lf conjunto de polinomios Lf = L (263, 51, 50):
Clave privada Fp(v) = clave
privada f(v)^{-1}mod
p
En resumen, un conjunto de polinomios Lf es un
conjunto de polinomios que presenta 51 términos 1, 50 términos -1 y
162 términos 0 en su factor f_{0}, f_{1}, f_{2},...,
f_{N-1}. La clave privada f es un polinomio que
pertenece al conjunto de polinomios Lf. Asimismo, p es un entero,
tal como 3.
Por otra parte, la clave de encriptación que es
pública (denominada en lo sucesivo "clave pública") h(v)
se expresa en la fórmula siguiente:
Clave pública h(v) = clave
privada f(v)^{-1} x polinomio g(v)(mod
q)
Polinomio g(v) \in un
conjunto de polinomios Lg = L(263, 24,
24)
La clave pública h (v) en este caso es un
polinomio, y q es, por ejemplo, el entero 2^{7}.
La encriptación NTRU se ejecuta basándose en la
fórmula siguiente y utilizando la clave pública h(v). En esta
encriptación, se genera un texto de encriptación e1(v) para
la entrada de un mensaje m1(v).
Texto de encriptación e1(v)
= p polinomio \phi (v) x clave pública h(v) +
m1(v)(mod
q)
Polinomio \phi (v) \in un
conjunto de polinomios L\phi = L(263, 16,
16)
En este caso, el polinomio \phi(v) es
uno de los polinomios del conjunto de polinomios L\phi
seleccionado aleatoriamente.
Mientras tanto, el texto de encriptación
e1(v) se desencripta mediante las claves privadas f(v)
y Fp(v) anteriores en las dos etapas siguientes, obteniéndose
el mensaje m1'(v).
(1) a (v) = clave privada f(v) x texto de
encriptación e 1 (v)(mod q)
(2) m1'v = clave privada Fp(v) x a
(v)(mod p)
\vskip1.000000\baselineskip
Existen dos tipos de ataques para romper el
código: los ataques pasivos y los ataques activos. Los tipos de
encriptación tales como la encriptación RSA, la encriptación ElGamal
y la encriptación NTRU se crean basándose en el supuesto de que
sólo se necesita encriptación contra los ataques pasivos. Los
ataques pasivos, los ataques activos, la encriptación RSA y la
encriptación EIGamal se describen en detalle en el Documento 1.
Recientemente, se ha propuesto la utilización de
una tecnología de sistemas resistentes a ataques, que convierte los
procedimientos de encriptación general en sistemas resistentes a
ataques, como tecnología de perfeccionamiento del algoritmo de
encriptación para aumentar el nivel de protección contra cualquier
tipo de ataques.
Existe un procedimiento para utilizar una
función resumen denominada FOSRT en la técnica de sistemas
resistentes a ataques.
El procedimiento FOSRT y su aplicación a la
encriptación NTRU se describen en detalle en el documento
"Protecting NTRU Against Chosen Ciphertext and Reaction
Attacks", Jeffrey Hoffstein y Joseph H. Silverman, NTRU
Cryptosystems Technical Report 016, 2000 (denominado en lo sucesivo
"Documento 3"). La función resumen se describe en detalle en el
Documento 1.
A continuación, se describe un procedimiento
FOSRT concreto.
La encriptación con la función FOSRT se ejecuta
a través de las tres etapas indicadas a continuación, generándose
el texto de encriptación E para la entrada del mensaje M. En la
primera etapa, se encadena un número aleatorio R1 con el mensaje M,
obteniéndose un mensaje encadenado M || R1.
En la segunda etapa, se obtiene un valor de
función resumen para el mensaje M || R1 basándose en la función
resumen:
En la tercera etapa, el mensaje M || R1 y el
valor de función resumen ha se encriptan basándose en el
algoritmo de encriptación, obteniéndose un texto de encriptación
E:
A continuación, se describe la desencriptación
FOSRT.
En la primera etapa, el texto de encriptación E
se desencripta y se obtiene un mensaje M || R1'.
En la segunda etapa, se obtiene un valor de
función resumen ha' del mensaje M || R1', basándose en la función
resumen.
En la tercera etapa, la encriptación se ejecuta
basándose en el mensaje M || R1', el valor de la función resumen
ha' y el mismo algoritmo utilizado para la encriptación anterior,
obteniéndose un texto de encriptación E'.
En la cuarta etapa, si el texto de encriptación
E y el texto de encriptación E' no son coherentes, a continuación
no se obtiene ninguna salida. Si los textos son coherentes, el
mensaje M || R1' se divide en el mensaje M' y el numero aleatorio
R1', y se obtiene el mensaje deseado M'.
A continuación, se describe un procedimiento
para la encriptación y la desencriptación cuando se aplica la
función FOSRT a la encriptación NTRU.
La encriptación se ejecuta a través de 3 etapas
y genera el texto de encriptación e(v) para la entrada del
mensaje
M(v).
M(v).
En la primera etapa, se encadena un vector
aleatorio R(v) al mensaje M(v) y se obtiene el mensaje
m(v) (m(v) = M(v) || R(v)).
En la segunda etapa, se calcula un valor de
función resumen H (m(v)) del mensaje m (v), basándose en la
función resumen.
En la tercera etapa, se obtiene el texto de
encriptación e (v) basándose en la fórmula:
texto de
encriptación e (v) = pH(m(v)) x clave pública
h(v) + m(v) (mod
q).
Por otra parte, la desencriptación del texto de
encriptación e (v) se ejecuta a través de las cinco etapas
siguientes.
En la primera etapa, se obtiene un polinomio
a(v) basándose en a(v) = clave privada f(v) x
texto de encriptación
e(v)(mod q).
e(v)(mod q).
En la segunda etapa, se obtiene un mensaje m'(v)
basándose en m'(v) = clave privada Fp(v) x a(v)(mod
p).
En la tercera etapa, se calcula un valor de
función resumen H(m'(v)) del mensaje m'(v) y se obtiene un
texto de encriptación e'(v) basándose en el texto de encriptación
e'(v) = pH (m'(v)) x clave pública h(v) + m'(v)(mod q).
En la cuarta etapa, se comprueba si el texto de
encriptación e'(v) es coherente con el texto de encriptación
e(v).
En la quinta etapa, si el texto de encriptación
e'(v) es coherente con el texto de encriptación e(v), se
divide m'(v) = M'(v) || R'(v) (M'(v) es un mensaje desencriptado
y R'(v) es un vector aleatorio) y se obtiene el mensaje M'(v).
Como se ha indicado anteriormente, cuando en los
procedimientos de encriptación y desencriptación se aplica la
función FOSRT a la encriptación NTRU, es necesario que los valores
de función resumen, H(M(v)) y H(m'(v)),
pertenezcan a un conjunto de polinomios L\phi expresado, por
ejemplo, como L (263, 16, 16).
El conjunto de polinomios L\phi está asociado
con un conjunto de vectores que presenta 16 términos 1, 16 términos
-1 y 231 términos 0 entre sus factores f_{0}, f_{1},
f_{2},..., f_{N-1}.
Por consiguiente, en asociación con el valor de
función resumen, es necesario obtener la matriz
n-dimensional que consta de tres valores (16
términos 1, 16 términos -1 y 231 términos 0).
No obstante, cuando en los procedimientos de
encriptación y desencriptación se aplica la función FOSRT a la
encriptación NTRU, estos valores de función resumen
(H(m(v) y H(m'(v)) son un entero.
Por consiguiente, para aplicar la función FOSRT
a la encriptación NTRU, debe obtenerse la matriz
n-dimensional que presenta n1 término(s) 1,
n2 término(s) -1 y otro(s) elemento(s) de valor
-1, basándose en los valores de función resumen
H(m(v)) y H(m'(v)). (En este caso, n, n1 y n2
son enteros positivos).
Para obtener la matriz
n-dimensional basándose en los valores de función
resumen H (m(v)) y H (m'(v)), es necesario que el
procedimiento cumpla las condiciones siguientes:
(1) Debe obtenerse siempre la misma salida para
la misma entrada.
(2) Debe existir una distribución bien
equilibrada de entradas y salidas. La condición (1) significa que no
debe obtenerse un valor diferente de salida para la misma entrada.
La condición (2) significa que en ningún caso debe obtenerse
frecuentemente sólo un valor de salida concreto para las entradas.
Cuando se aplica la función FOSRT a la encriptación NTRU, la
desencriptación no será posible si el emisor y el receptor no son
capaces de crear la matriz n-dimensional para la
salida. Si la condición (1) no se cumple, no se realizará el
procedimiento de encriptación. Asimismo, si la condición (2) no se
cumple, no se conservará el equilibrio de la distribución de salida
para la entrada de la función resumen, puesto que la matriz no se
genera de manera uniforme basándose en el valor de salida del valor
de función resumen. Por consiguiente, el nivel de seguridad de la
función resumen disminuye, con lo cual también disminuye el nivel de
seguridad de la encriptación NTRU cuando se aplica la función
FOSRT.
A continuación, se describirá un procedimiento
autoexplicativo para obtener la matriz n-dimensional
que presenta 1 término(s) 1, n 2 término(s) -1 y otros
elementos de valor 0.
La Figura 1 es un diagrama de flujo que
representa el procedimiento para obtener la matriz
n-dimensional.
En este procedimiento de conversión, se
introducen n1, n2 y un entero X como valor de función resumen y se
genera la matriz n-dimensional VJ que presenta n1
término(s) 1, n2 término(s) -1 otro(s)
(n-n1-n2) término(s) 0. Se
supone que el i-ésimo elemento (por la izquierda) de la matriz VJ es
VJ[i] (N.B. "i" es un entero de 1 a n).
En primer lugar, se dispone que todos los
elementos de la matriz VJ formen una matriz de 0 (etapa S901).
A continuación, se dispone que el valor de
recuento c1 de un contador c1' sea 1 (etapa S902).
A continuación, se dispone que VJ[c1] = 1
(etapa S903).
A continuación, se incrementa el valor de
recuento c1 del contador c1' (etapa 904).
A continuación, se determina si el valor de
recuento c1 es > n1 (etapa 905). Si el valor de recuento c1 no
es > n1 (es decir, se responde "No" en la etapa S905), se
ejecuta un procedimiento para VJ[c1] = 1 otra vez (etapa
S903).
Si el valor de recuento c1 es > n1 ("Sí"
en la etapa S905), VJ[c1] = -1 (etapa S906).
A continuación, se incrementa el valor de
recuento c1 (c1 \leftarrow c1+1) (etapa 907).
A continuación, se determina si el valor de
recuento c1 es > n1+n2 (etapa 908). Si el valor de recuento c1
no es > n1+n2 ("No" en la etapa S908), se ejecuta un
procedimiento para VJ[c1] = -1 otra vez (etapa S906).
Si el valor de recuento c1 es >n1+n2
("Sí" en la etapa S908), se genera la matriz VJ y se termina el
procedimiento.
En este procedimiento, la matriz VJ de salida,
independientemente del entero de entrada X, contiene la matriz
original que presenta n1 término(s) 1, n2 término(s)
-1 y otros elementos de valor 0.
Por otra parte, como procedimiento de
comunicación privado, se dispone de un procedimiento de encriptación
de clave común que encripta un mensaje de envío con una clave y lo
desencripta con la misma clave. En el procedimiento de encriptación
de clave común es posible crear un texto de encriptación a través de
una operación de sustitución de datos. El siguiente ejemplo ilustra
cómo se realiza dicha operación.
En este procedimiento de sustitución, se utiliza
una matriz m[1], m[2], ..., m[n] y una clave Ke
(un entero positivo) como entrada y se genera un texto de
encriptación e[1], e[2], ..., e[n]. En el
ejemplo, se supone que se dispone de antemano de dos tabuladores de
dimensiones de tablas [j] [i] (1 \leq j \leq n1, 1 \leq i
\leq n).
En primer lugar, se establece el valor del
recuento c del contador c' en 1.
A continuación, se substituye
e[Tab[K][c]] por m[c]. Este procedimiento se
ejecuta hasta que el valor de recuento c del contador c' llega a
n.
Cuando el valor de recuento c del contador c'
llega a n, se obtiene el texto de encriptación e y el
procedimiento termina.
Aunque es posible considerar que dicho
procedimiento de sustitución se aplica al procedimiento mencionado
anteriormente para obtener la matriz n dimensional basándose en el
valor de la función resumen, es necesario disponer de n*n
término(s) de tablas.
No obstante, el resultado de salida del
procedimiento autoexplicativo para obtener la matriz n dimensional
mencionado anteriormente tiende hacia un tipo y no satisface la
condición (2) anterior (distribución bien equilibrada de entradas y
salidas). En este caso, se pierde el efecto de la aplicación de la
función FOSRT y el nivel de seguridad es vulnerable a los ataques
pasivos. Por consiguiente, cuando se aplica la función FOSRT a la
encriptación NTRU mediante este procedimiento, se plantea el
problema de la disminución del nivel de seguridad en la encriptación
NTRU.
Asimismo, aunque para obtener la matriz
n-dimensional se aplique el procedimiento de
sustitución utilizado como sistema de encriptación de clave común
mencionado anteriormente, la utilización de una tabla de memoria que
requiere una enorme cantidad de memoria también plantea un
problema.
En el documento US6081597, publicado el
27-06-2000, se describe el
procedimiento y el aparato del criptosistema NTRU. Este
criptosistema permite elegir las claves de encriptación de forma
esencialmente aleatoria, a partir de un gran conjunto de vectores
binarios, siendo las longitudes de estas claves comparables a las
longitudes de las claves de los criptosistemas de técnica anterior
más ampliamente utilizados.
En el documento US5142579, publicado el
25-08-1992, se describe un sistema y
un procedimiento criptográfico de clave pública basado en un
problema "difícil" desde el punto de vista informático y
NP-completo.
La presente invención se ejecuta basándose en la
consideración de los problemas anteriores, y su objetivo es
proporcionar un dispositivo de salida de matrices que genere una
matriz n-dimensional bien equilibrada basándose en
un valor entero, tal como el valor de salida de una función resumen,
sin utilizar una cantidad tan elevada de memoria.
Estos objetivos se alcanzan de conformidad con
el objeto de las reivindicaciones independientes.
Para alcanzar el objetivo anterior, el
dispositivo de salida de matrices es un dispositivo de salida de
matriz numérica que genera diversas matrices
n-dimensionales que constan de n enteros de valor K,
cada uno de los cuales es uno de los K tipos de enteros posibles,
dependiendo del entero de entrada, que comprende: una unidad de
determinación de matriz inicial operativa para elegir
provisionalmente una matriz inicial, y una unidad de cambio
operativa para convertir un elemento de la matriz inicial elegida
por la unidad de determinación de matriz inicial en la matriz
n-dimensional basándose en el entero de entrada.
De esta manera, sin utilizar una cantidad tan
elevada de memoria, es posible obtener de manera uniforme la matriz
n-dimensional basada en el entero, a la vez que es
posible conservar la uniformidad gracias a los valores enteros
distribuidos uniformemente, tales como el valor de función resumen,
etc.
El dispositivo de salida de matriz numérica
puede ser, en este caso, un dispositivo de salida de matrices, en
el que la unidad de determinación de matriz inicial elige
provisionalmente como matriz inicial una de las matrices
n-dimensionales que constan de los n enteros de
valor K, y la unidad de cambio sustituye el elemento de la matriz
inicial elegida por la unidad de determinación de matriz inicial
basándose en el entero de entrada y genera la matriz inicial
sustituida.
Asimismo, el dispositivo de salida de matrices
anterior puede ser un dispositivo de salida de matrices en el que
la unidad de determinación de matriz inicial elige provisionalmente,
como matriz inicial, una matriz en la que todos los elementos son
el entero de valor K P3, y la unidad de cambio sustituye el elemento
de matriz, que está situado en una posición basada en el entero de
entrada entre el elemento de matriz del entero P3 de la matriz
inicial elegida por la unidad de determinación de matriz inicial,
por el otro entero de valor K P1, y genera la matriz inicial
sustituida.
El dispositivo de salida de matrices también
puede ser un dispositivo en el que el entero de entrada viene
indicado por un número plural de bits de información, y la unidad de
cambio incluye una unidad de separación operativa para partir el
entero en información individual partida que consta de un número
específico de bits de información, y una tercera unidad de
sustitución de enteros operativa para sustituir el elemento de
matriz, que está situado en una posición basada en la información
partida entre el elemento de matriz del entero P3 de la matriz
inicial, por otro entero P1 de los valores K.
Para alcanzar los objetivos anteriores, se
dispone de un procedimiento de salida de matriz numérica para
generar diversas matrices n-dimensionales que
constan de n enteros de valor K, cada uno de los cuales es uno de
los K tipos de enteros posibles, dependiendo del entero de entrada,
que incluye: una etapa de elección de matriz inicial para elegir
provisionalmente una matriz inicial y una etapa de cambio para
convertir un elemento de la matriz inicial elegida en la etapa de
elección de matriz inicial en las matrices
n-dimensionales, basándose en el entero de
entrada.
Según esta estructura, puede esperarse el mismo
efecto que el descrito anteriormente.
Además, el dispositivo de encriptación de la
presente invención es un dispositivo que encripta un mensaje, que
comprende: una unidad de salida de valores de función operativa para
calcular el mensaje con una función de conversión de un sentido y
proporcionar el resultado como un valor de función; una unidad de
salida de matriz numérica que incluye una unidad de determinación
de matriz inicial que elige provisionalmente una matriz inicial;
una unidad de cambio que convierte un elemento de la matriz inicial
elegida por la unidad de determinación de matriz inicial en una
matriz n-dimensional basándose en el valor de
función generado por la unidad de salida de valores de función, que
es operativa para generar diversas matrices
n-dimensionales que constan de n enteros de valor
K, cada uno de los cuales es uno de los K tipos de enteros posibles,
dependiendo del valor de función; y una unidad de generación de
texto de encriptación operativa para generar un texto de
encriptación basándose en la matriz generada por la unidad de salida
de matriz numérica.
De esta manera, es posible conservar la
uniformidad y obtener la matriz n-dimensional
basándose en el valor entero distribuido uniformemente mediante una
función de conversión de un sentido, tal como el valor de función
resumen de un mensaje, y aumentar el nivel de seguridad del texto de
encriptación.
Éstos y otros objetivos, ventajas y
características de la presente invención se pondrán más claramente
de manifiesto a partir de la descripción siguiente, considerada
conjuntamente con los dibujos adjuntos, que ilustran una forma de
realización particular de la presente invención. En los dibujos:
La Figura 1 es un diagrama de flujo que
representa un procedimiento de generación de matrices
convencional;
La Figura 2 es un diagrama de bloques que
representa la estructura de un dispositivo de encriptación
relacionado con una primera forma de realización, y la Figura 2B es
un diagrama de bloques que representa la estructura de un
dispositivo de desencriptación;
La Figura 3 es un diagrama de bloques que
representa la estructura de la unidad de salida de matrices
anterior;
La Figura 4 es un diagrama que representa el
estado de una matriz generada por la unidad de salida de matrices
anterior;
La Figura 5 es un diagrama de flujo que
representa una acción de la unidad de salida de matrices
anterior;
La Figura 6 es un diagrama de bloques que
representa la estructura de la unidad de salida de matrices
relacionada con una segunda forma de realización;
La Figura 7 es un diagrama de flujo que
representa una acción de una primera unidad de asignación de números
de la unidad de salida de matrices anterior;
La Figura 8 es un diagrama que representa el
estado de una matriz generada por la primera unidad de asignación de
números de la unidad de salida de matrices anterior;
La Figura 9 es un diagrama de flujo que
representa una acción de una segunda unidad de asignación de números
de la unidad de salida de matrices anterior;
La Figura 10 es un diagrama que representa el
estado de la matriz generada por la segunda unidad de asignación de
números de la unidad de salida de matrices anterior;
La Figura 11 es un diagrama de bloques que
representa la estructura de la unidad de salida de matrices
relacionada con una tercera forma de realización de la presente
invención;
La Figura 12 es un diagrama que representa el
estado de la matriz generada por la primera unidad de asignación de
números de la unidad de salida de matrices anterior;
La Figura 13 es un diagrama que representa el
estado de la matriz generada por la segunda unidad de asignación de
números de la unidad de salida de matrices anterior;
Las Figuras 14A, 14B y 14C son diagramas que
representan el estado de la matriz establecida en cada unidad de la
unidad de salida de matrices anterior;
La Figura 15 es un diagrama que representa la
estructura de la unidad de salida de matrices relacionada con una
cuarta forma de realización;
La Figura 16 es un diagrama de flujo que
representa una acción de la unidad de salida de matrices
anterior;
La Figura 17 es un diagrama que representa la
entrada de un entero en la unidad de salida de matrices
anterior;
La Figura 18 es un diagrama que representa el
estado de la matriz generada por la unidad de salida de matrices
anterior y
La Figura 19 es una vista que representa el
aspecto de un teléfono móvil que presta servicio al dispositivo de
encriptación que contiene la unidad de salida de matrices de la
presente invención.
Primera forma de
realización
A continuación, se describirá un dispositivo de
encriptación relacionado con la primera forma de realización de la
presente invención, haciendo referencia a los diagramas.
La Figura 2(a) es un diagrama de bloques
que representa la estructura del dispositivo de encriptación en
relación con la primera forma de realización de la presente
invención.
El dispositivo de encriptación 10 incluye un
dispositivo de generación de números aleatorios 20, una unidad de
encadenamiento 30, una unidad de función resumen 40, una unidad de
salida de matrices 100 y una unidad de generación de texto de
encriptación 50, que genera un texto de encriptación e (v) basado en
un mensaje M (V) obtenido y una clave pública h (v). El símbolo
(v), tal como el de un mensaje M (v), una clave pública h (v) y un
texto de encriptación e (v), indica un polinomio. Además, se
utilizan los mismos símbolos que en los ejemplos convencionales.
La unidad de generación de números aleatorios
20, la unidad de encadenamiento 30, la unidad de función resumen
40, la unidad de salida de matrices 100 y la unidad de generación de
texto de encriptación 50 que componen el dispositivo de
encriptación 10 ejecutan respectivos procedimientos a través del
software de un microordenador, y estos procedimientos se ejecutan
utilizando una CPU y unas memorias.
Como se describe en el ejemplo convencional, el
dispositivo de encriptación 10 aplica la función FOSRT, que es un
sistema resistente a los ataques, a la encriptación NTRU y genera
una encriptación que presenta un nivel de seguridad más alto de
encriptación NTRU.
La unidad de generación de números aleatorios 20
genera un vector aleatorio R (v).
La unidad de encadenamiento 30 encadena el
vector R (v) generado por la unidad de generación de números
aleatorios 20 con un mensaje M (v), genera un mensaje m (v) y lo
pasa a la unidad de función resumen 40 y la unidad de generación de
texto de encriptación 50.
La unidad de función resumen 40 aplica la
función resumen al mensaje m (v), siendo dicha función resumen una
función de un solo sentido, para generar un valor de función resumen
H (m) y pasarlo a la unidad de salida de matrices 100. En este
caso, la función resumen es la función de un solo sentido, y el
valor de función resumen H (m) generado por la unidad de función
resumen 40 es un entero que, en lo sucesivo, se denominará "entero
X".
La unidad de salida de matrices 100 genera la
matriz n-dimensional V basándose en el entero X
obtenido de la unidad de función resumen 40, y pasa dicha matriz a
la unidad de generación de texto de encriptación 50.
La unidad de generación de texto de encriptación
50 genera el texto de encriptación e (v) basándose en el polinomio
\phi (v) correspondiente a la matriz n-dimensional
V obtenida en la unidad de salida de matrices 100, el mensaje m (v)
de la unidad de encadenamiento 30, la clave pública h (v) y la
fórmula del texto de encriptación e (v) = p polinomio \phi (v)
x
clave pública h (v) + m (v) (mod q), y pasa dicho texto al exterior, p y q son enteros; por ejemplo, p es 3 y q es 2^{7}.
clave pública h (v) + m (v) (mod q), y pasa dicho texto al exterior, p y q son enteros; por ejemplo, p es 3 y q es 2^{7}.
La Figura 2(b) es un diagrama de bloques
que representa la estructura del dispositivo de desencriptación en
relación con la primera forma de realización de la presente
invención.
El dispositivo de desencriptación 15 contiene
una unidad de desencriptación 25, una unidad de función resumen 45,
una unidad de salida de matrices 105, una unidad de generación de
texto de encriptación 55, una unidad de determinación 65 y una
unidad de separación 35, que desencripta el texto de encriptación e
(v), que ha sido encriptado por el dispositivo de encriptación 10,
basándose en el texto de encriptación de entrada e (v), una clave
privada f (v), Fp (v) y una clave pública h (v), y genera el mensaje
original M' (v).
La unidad de desencriptación 25, la unidad de
función resumen 45, la unidad de salida de matrices 105, la unidad
de generación de texto de encriptación 55, la unidad de
determinación 65 y la unidad de separación 35 que componen el
dispositivo de desencriptación 15 ejecutan respectivos
procedimientos a través del software del microordenador, y los
procedimientos se realizan utilizando la CPU y las memorias.
La unidad de desencriptación 25 obtiene el
mensaje m' (v), que es un valor de desencriptación correspondiente
al mensaje original, a partir del texto de encriptación e (v) de
entrada basándose en las fórmulas siguientes:
a (v) = clave
privada f (v) x texto de encriptación e (v) (mod
q)
m' (v) = clave
privada Fp (v) x a (v) (mod
p)
La unidad de función resumen 45 calcula el valor
de función resumen H (m') del mensaje m' (v) y lo pasa a la unidad
de salida de matrices 105. El valor de función resumen H (m')
obtenido en la unidad de función resumen 45 es un entero que, en lo
sucesivo, se denominará "entero X'".
La unidad de salida de matrices 105 genera la
matriz n-dimensional V' basándose en el entero X'
obtenido en la unidad de función resumen 45 y la pasa a la unidad
de generación de texto de encriptación 55.
La unidad de generación de texto de encriptación
55 genera un texto de encriptación e' (v) basándose en el polinomio
\phi' (v) correspondiente a la matriz
n-dimensional V' obtenida en la unidad de salida de
matrices 105, el mensaje m' (v) de la unidad de desencriptación 25,
la clave pública h (v) y la fórmula del texto de encriptación e'
(v) = p polinomio \phi' (v) x clave pública h (v) + m' (v)(mod q),
y pasa dicho texto a la unidad de determinación 65.
La unidad de determinación 65 obtiene el texto
de encriptación e (v) y el texto de encriptación e' (v), decide si
ambos son coherentes o no y pasa el mensaje m' (v) a la unidad de
separación 35 si decide que ambos textos son coherentes.
La unidad de separación 35 divide el mensaje m'
(v) de la unidad de determinación 65 en un mensaje M' (v) y un
vector aleatorio R' (v) y genera el mensaje original M' (v).
A continuación, se describe la unidad de salida
de matrices 100 del dispositivo de encriptación 10 con referencia a
los diagramas. Puesto que la unidad de salida de matrices 105 del
dispositivo de desencriptación 15 presenta la misma estructura que
la unidad de salida de matrices 100 y realiza la misma acción, su
descripción se omite.
La Figura 3 es un diagrama de bloques que
representa la estructura de la unidad de salida de matrices 100.
Esta unidad de salida de matrices 100 utiliza el
entero X como entrada y genera una matriz V que pertenece a L (n,
n1, n2). En este caso, L (n, n1, n2) es la matriz
n-dimensional completa que presenta n1
término(s) 1, n2 término(s) -1 y otro(s)
(n-n1-n2) término(s) 0,
siendo n, n1 y n2 predefinidos en la unidad de salida de matrices
100. La unidad de salida de matrices 100 consta de una unidad de
determinación de matriz inicial 110 y una unidad de sustitución de
elementos de matriz 120.
La unidad de determinación de matriz inicial 110
tiene como finalidad realizar una primera elección de la matriz V y
generar la matriz de elección inicial V1 indicada a
continuación.
En este caso, V1[i] es el i-ésimo
elemento de matriz (elemento) (por la izquierda), siendo i un entero
de 1 a n, de la matriz de elección inicial V1.
La Figura 4 es un diagrama que representa el
estado de la matriz V en cada fase de la unidad de salida de
matrices 100. La Figura 4 indica cada estado de la matriz V; por
ejemplo (n=8, n1=3, n2=2) en el caso de L (8, 3, 2). En la Figura
4, el estado de matriz de la parte superior representa la matriz de
elección inicial V1 elegida por la unidad de determinación de matriz
inicial 110.
La unidad de sustitución de elementos de matriz
120 introduce la matriz de elección inicial V1 obtenida en la
unidad de determinación de matriz inicial 110 y el entero X y genera
la matriz n-dimensional V que presenta n1
término(s) 1, n2 término(s) -1 y otro(s)
(n-n1-n2) término(s) 0. La
finalidad de dicha acción es cambiar un elemento de la matriz de
elección inicial V1 elegida por la unidad de determinación de matriz
inicial 110.
A continuación, se describen los procedimientos
ejecutados por la unidad de sustitución de elementos de matriz
120.
La Figura 5 es un diagrama de flujo que
representa los procedimientos ejecutados por la unidad de
sustitución de elementos de matriz 120.
Se considerará que el valor del contador c' es
el valor de recuento c.
En primer lugar, la unidad de sustitución de
elementos de matriz 120 substituye un argumento Y por el entero X y
substituye la matriz de elección inicial V1 por la matriz V; es
decir, se substituye V[j] por V1[i] para todos los
valores i (i es un entero de 1 a n) (etapa S101).
A continuación, la unidad de sustitución de
elementos de matriz 120 establece el valor de recuento c del
contador c' en n (etapa S102).
A continuación, en la unidad de sustitución de
elementos de matriz 120, el cociente del argumento Y dividido por el
valor de recuento c se trata como S y el resto como R (etapa
S103).
A continuación, la unidad de sustitución de
elementos de matriz 120 toma en consideración
tmp\leftarrowV[c] (etapa S104), para sustituir un registro
tmp por el c-ésimo elemento V[c] de la matriz V.
A continuación, la unidad de sustitución de
elementos de matriz 120 toma en consideración V[c]
\leftarrowV[R+1] (etapa S105), para sustituir el c-ésimo
elemento de la matriz V por el (R+1)-ésimo elemento de la matriz
V.
A continuación, la unidad de sustitución de
elementos de matriz 120 toma en consideración
V[R+1]\leftarrow tmp (etapa S106), para sustituir
el (R+1)-ésimo elemento de la matriz V por el contenido del registro
tmp. Mediante el procesamiento de este registro tmp=V[c],
V[c]=V[R+1], V[R+1]=tmp (etapa S104 a etapa S
106), se sustituye el c-ésimo elemento y el (R+1)-ésimo
elemento.
A continuación, la unidad de sustitución de
elementos de matriz 120 sustituye el argumento Y por el cociente S
(etapa S107).
A continuación, la unidad de sustitución de
elementos de matriz 120 determina si el valor de recuento c es 2 o
no (etapa S108). Si se determina que el valor de recuento c es 2
("Sí" en la etapa S108), la unidad de sustitución de elementos
de matriz 120 genera la matriz V (etapa S110) y termina el
procedimiento.
Por otra parte, si la unidad de sustitución de
elementos de matriz 120 determina que el valor de recuento c no es
2 ("No" en la etapa S108), entonces se reduce el valor de
recuento c (c\leftarrowc-1) (etapa S109) y se
continúa con el procedimiento para obtener S para el cociente del
argumento Y dividido por el valor de recuento c, y R para su resto
(etapa S103).
De esta manera, la unidad de sustitución de
elementos de matriz 120 repite el procedimiento en cada etapa,
empezando por el procedimiento para obtener el cociente S y el resto
R (etapa S103) y terminando por el procedimiento para reducir el
valor de recuento c (etapa S109), para cada caso en el que el valor
de recuento c del contador c' es un valor entre n y 2. Una vez que
cada elemento de la matriz V ha sido sustituido y el procedimiento
para el valor de recuento c = 2 ha finalizado, la unidad de
sustitución de elementos de matriz 120 genera la matriz V.
A continuación, se describen todas las acciones
de la unidad de salida de matrices 100. En la unidad de salida de
matrices 100, la unidad de determinación de matriz inicial 110 elige
primero la matriz de elección inicial V1 de la matriz
n-dimensional que presenta n1 término(s) 1,
n2 término(s) -1 y otros términos 0, y la pasa a la unidad de
sustitución de elementos de matriz 120.
A continuación, la unidad de sustitución de
elementos de matriz 120 obtiene la matriz de elección inicial V1
generada por la unidad de determinación de matriz inicial 110 y el
entero X introducido en la unidad de salida de matrices 100,
sustituye cada elemento de la matriz de elección inicial V1
basándose en el entero X y genera la matriz
n-dimensional V que presenta n1 término(s) 1,
n2 término(s) -1 y otro(s) elemento(s) que son
0.
Las acciones de esta unidad de salida de
matrices 100 se describen haciendo referencia a un ejemplo
particular.
Las acciones de esta unidad de salida de
matrices 100 se describen utilizando números de entrada particulares
(por ejemplo, el entero X = 39356, n=8, n1=3, n2=2.
Primeramente, la unidad de determinación de
matriz inicial 110 elige la matriz de elección inicial V1 que cumple
n=8, n1=3, n2=2, y la pasa a la unidad de sustitución de elementos
de matriz 120 (Véase la Figura 4).
A continuación, la unidad de sustitución de
elementos de matriz 120 sustituye el argumento Y por el entero X de
entrada, toma en consideración el argumento Y = 39356 y sustituye la
matriz V por la matriz de elección inicial V_{1} (etapa S101).
A continuación, la unidad de sustitución de
elementos de matriz 120 toma en consideración el valor de recuento
c=8 (etapa S102).
A continuación, la unidad de sustitución de
elementos de matriz 120 calcula el cociente S y el resto R, y toma
en consideración el cociente S=4919 y el resto R=4 (etapa S103).
A continuación, la unidad de sustitución de
elementos de matriz 120 sustituye el (R+1)-ésimo elemento de la
matriz V, correspondiente al quinto elemento "-1" por el octavo
elemento "0" (etapa S104 a etapa S106) y crea el estado de
matriz indicado en la matriz V2 de la Figura 4.
A continuación, la unidad de sustitución de
elementos de matriz 120 sustituye el argumento Y por 4919 (etapa
S107).
A continuación, debido a que el valor de
recuento c es = 8 y no = 2 ("No" en la etapa S108), la unidad
de sustitución de elementos de matriz 120 reduce el valor de
recuento c para que c = 7 (etapa S109).
A continuación, la unidad de sustitución de
elementos de matriz 120 calcula el cociente S y el resto R otra vez
a partir del argumento Y=4919, y el valor de recuento = 7, y obtiene
el cociente S=702 y el resto R=5 (etapa S103).
A continuación, la unidad de sustitución de
elementos de matriz 120 sustituye el sexto elemento "0" por el
séptimo elemento "0" por la izquierda de la matriz V (etapa
S104 a etapa S106) y crea el estado de matriz indicado en la matriz
V3 de la Figura 4.
De este modo, la unidad de sustitución de
elementos de matriz 120 sustituye elementos de la matriz V basándose
en el cociente S y el resto R cuando el argumento Y se divide por
el valor de recuento c, en cada caso en el que el valor de recuento
c es un valor entre n y 2 (repetición de los procedimientos de la
etapa S103 a la etapa S109), y ejecuta el procedimiento de
sustitución de cada elemento de la matriz de elección inicial V1. A
continuación, cuando el procedimiento anterior ha terminado para el
caso del valor de recuento c=2, la unidad de sustitución de
elementos de matriz 120 genera la matriz V.
A continuación, se describe el caso de una
matriz V generada por la unidad de salida de matrices 100 que se ha
generado de manera bien equilibrada basándose en el entero de
entrada X.
Basándose en el entero X que satisface
0\leqX\leq (n!-1) (n ! significa "n factorial" y, en
particular, n! = nX (n-1) X...X2X1), la unidad de
salida de matrices 100 genera de manera uniforme la matriz
L(n, n1, n2). La descripción siguiente se basa en la premisa
de que X está limitado a ser 0 \leqX\leq (n! -1).
En la unidad de sustitución de elementos de
matriz 120, se sustituyen los elementos de la matriz de elección
inicial V1. A continuación, la atención se centrará en particular en
los elementos de la matriz de elección inicial V1 sustituidos por
la unidad de sustitución de elementos de matriz 120. Para facilitar
la comprensión exhaustiva de la siguiente descripción, en la
estructura de la unidad de sustitución de elementos de matriz 120
anterior, el resto resultante del procedimiento de R \leftarrow
Ymod c (etapa S103) se trata como R_i cuando el valor de recuento c
es i (i=n, n-1, n-2,..., 3,2).
Globalmente, la descripción se estructura de la
siguiente forma:
(1) se indica que el procedimiento de
sustitución no se duplica;
(2) mediante el razonamiento de (1), se indica
que entre el contenido de procesamiento del entero X y la unidad de
sustitución de elementos de matriz 120 se establece una relación
biunívoca;
(3) se calculan cuántos tipos del entero X dan
por resultado la misma matriz.
El cálculo (3) permite determinar que el número
de tipos del entero X es idéntico independientemente de la matriz V,
demostrándose de ese modo que la salida está bien equilibrada con la
entrada.
En primer lugar, se considerará el punto (1), es
decir, se explicará porqué "el procedimiento de sustitución no se
duplica".
En realidad, esto significa que no se sustituye
repetidamente el mismo valor, ya que el valor con respecto al cual
se ha realizado el procedimiento de sustitución no se tiene en
cuenta como sujeto para la sustitución en los procedimientos
subsiguientes.
\vskip1.000000\baselineskip
\bullet Cuando el valor de
recuento n del contador c' es
n.
El significado de las acciones de la etapa S104,
S105 y S106 (en lo sucesivo, denominadas "procedimiento de
sustitución cuando el valor de recuento c es n") es que el
n-ésimo elemento V1 [n] de la matriz de elección inicial V1 es
sustituido por el (R_n + 1)-ésimo elemento V1 [R_n +1]. R_n es el
resto cuando el argumento Y se divide por n, es decir, puede ser
cualquier número entre 0 y n-1.
\vskip1.000000\baselineskip
\bullet Cuando el valor de
recuento c es
n-1
En este momento, el n-1-ésimo
elemento de la matriz V, que está en el estado en el que el
procedimiento de sustitución acaba de finalizar cuando el valor de
recuento c es n, es sustituido por el
(R_(n-1) +1)-ésimo elemento. Debido a que en
este caso R_(n -1) es el resto cuando el argumento Y se
divide por el valor del contador (n-1), el valor
puede ser cualquier número entre 0 y n-2. Por
consiguiente, el (n-1)-ésimo elemento de la matriz
V, que está en el estado en el que procedimiento de sustitución
acaba de finalizar cuando el valor de recuento c es
n-1, es el (R_(n-1)+1)-ésimo
elemento de la matriz V en el momento en el que el procedimiento de
sustitución acaba de finalizar cuando el valor de recuento c es n.
Asimismo, debe observarse que el n-ésimo elemento de la matriz V,
en el estado en el que el procedimiento de sustitución ha finalizado
cuando el valor de recuento c es n, no se trata como sujeto para la
sustitución.
\vskip1.000000\baselineskip
\bullet Cuando el valor de
recuento c es n-2 o
inferior
Cuando el valor de recuento c es
n-2 o inferior, se da la misma situación que en el
caso en el que el valor de recuento c es n-1. El
i-ésimo elemento de la matriz V en el estado en el que el
procedimiento de sustitución ha finalizado cuando el valor de
recuento c es el (R_i+1)-ésimo elemento de la matriz V en el estado
en el que el procedimiento de sustitución ha finalizado cuando el
valor de recuento c es (i+1). Debe observarse que el procedimiento
de sustitución cuando el valor de recuento c es (i+1) se ejecuta
antes del procedimiento de sustitución cuando el valor de recuento
c es i. Después de ese momento, el i-ésimo elemento de la matriz V
no será sustituido nunca por otros valores. Dado que
j\leqi-1, R_j es el resto cuando el argumento Y se
divide por j para que de ese modo se cumpla R j\leqj -1. A
continuación, (R_j+1) \leq i-1 < i.
Una vez que ha terminado el procedimiento de la
unidad de sustitución de elementos de matriz 120, es decir, en el
estado en el que todos los procedimientos para los valores de
recuento n a 2 de han finalizado, cada elemento de la matriz V
corresponde a cada elemento de la matriz de elección inicial V1 que
ha sido sustituido.
A continuación, se describe la unicidad del
procedimiento de la unidad de sustitución de elementos de matriz
120.
El razonamiento anterior (la sustitución no se
duplica) se utiliza para explicar porqué el contenido de
procesamiento del entero X y la unidad de sustitución de elementos
de matriz 120 establecen una relación biunívoca.
\vskip1.000000\baselineskip
\bullet Relación entre el entero
X y la
serie
Se supone que el entero X es un entero que
cumple 0\leqX\leq(n!-1). En este caso, cuando el valor de
recuento c del contador c' es c, el valor del argumento Y en la
etapa S103 es Y_c, el cociente S es S_c y el resto R es R_c (el
valor de R_c es el definido anteriormente). En este caso, si la
acción realizada en la etapa S103 se expresa mediante una fórmula,
entonces:
No obstante, 0\leqR_c\leq
(c-1). Asimismo, si la acción realizada en la etapa
S107 se expresa mediante una fórmula, entonces:
Resumiendo y aplicando al caso de c=n,
(n-1), ..., 2, entonces:
(teniendo en cuenta que X=Y_n)
En este caso R_i es un entero que cumple
0\leqR_i\leqi-1. A partir del entero X, resulta
obvio que R_2, R_3, ..., R_(n-2),
R_(n-1), R_n se eligen unívocamente. Lo
opuesto también es obvio. Por consiguiente, la relación entre el
entero X que cumple 0\leqX\leq(n ! -1) y R_2, R_3,...,
R_(n-2), R_(n-1), R_n
es biunívoca.
\vskip1.000000\baselineskip
\bullet Relación entre la serie y
la
sustitución
Como se ha indicado previamente, en la primera
forma de realización, cada elemento de la matriz de elección
inicial V1 es sustituido de conformidad con el entero X para generar
la matriz V. Como se ha mencionado anteriormente, esta sustitución
se decide mediante la serie R_n, R_(n-1),
R_(n-2), ..., R_3, R_2. En el momento de la
finalización del procedimiento de sustitución cuando el valor de
recuento c es n, el n-ésimo elemento de la matriz V es el
(R_n+1)-ésimo elemento de la matriz de elección inicial V1. A partir
de ese momento, el n-ésimo elemento de la matriz V no será
sustituido. Del mismo modo, en el momento de la finalización del
procedimiento de sustitución cuando el valor de recuento c es i, el
n-ésimo elemento de la matriz V es el (R_i+1)-ésimo elemento de la
matriz V en el momento de la finalización del procedimiento de
sustitución cuando el valor de recuento c es (i+1). A partir de
entonces, el i-ésimo elemento de la matriz V no será sustituido,
hecho que significa que entre el n-ésimo elemento y el i-ésimo
elemento de V, los elementos no cambiarán. Esto es debido, también,
a que en el momento de la finalización del procedimiento de
sustitución cuando el valor de recuento es (i+1) la matriz V es
elegida mediante la serie R_n, R_(n-1), ...,
R_(i+1).
Asimismo, el procedimiento de sustitución de n
término(s) de elementos de la matriz de elección inicial V1
se considera un procedimiento de "sustitución original de n
término(s)". En la "sustitución original de n
término(s)" opcional, la sustitución puede realizarse
mediante contenido de procesamiento de la unidad de sustitución de
elementos de matriz 120 citado anteriormente. Para expresar la
sustitución, se utiliza una cadena ordenada, que se obtiene
sustituyendo n término(s) del elemento secuencial
V[1], V[2], ..., V[n] como entrada. Por
ejemplo, una sustitución se expresa de la siguiente forma:
\vskip1.000000\baselineskip
\vskip1.000000\baselineskip
No obstante, como conjunto {1,2,...,n} =
{\sigma1, \sigma2,...,\sigman}.
En este momento, resultag obvio que el valor de
\sigma se elige utilizando R_n. Asimismo, el valor de
\sigma(n-1) se elige utilizando los
valores de R_n y R_(n-1), y es evidente que
se selecciona uniformemente entre todos los valores distintos a
\sigman. Lo mismo es aplicable a lo siguiente. El valor de
\sigma se elige utilizando R_n, R_(n-1),
..., R_(i+1) y utilizando todos los valores excepto
\sigman, \sigma(n-1), ...,
\sigma(i+1). Por consiguiente, de conformidad con la
unidad de sustitución de elementos de matriz anterior 120, se elige
el procedimiento de sustitución para toda la matriz de elección
inicial V1. En consecuencia, se deduce que en el procedimiento de
sustitución la relación entre el entero X que cumple
0\leqX\leq(n! -1) y la matriz de elección inicial V1 es
biunívoca. Lo expuesto hasta aquí se basa en la idea de que un
elemento se considera diferente si la información de emplazamiento
(es decir, el índice) del elemento es diferente, sin tener en
cuenta si el valor del elemento de la matriz de elección inicial V1
es idéntico o no. No obstante, en realidad, cada elemento de la
matriz de elección inicial V1 se compone de n1 término(s) 1,
n2 término(s) -1 y (n-n1-n2)
término(s) 0. Si el conjunto de emplazamientos del(de
los) n1 término(s) 1 es idéntico en la matriz V generada, el
valor de la matriz V también es idéntica. Lo mismo es aplicable
al(a los) n2 término(s) -1 y el (los)
(n-n1-n2) término(s) 0. Se
describirá con qué frecuencia puede generarse la misma matriz de
salida.
A continuación, se describe la uniformidad de la
salida de la unidad de sustitución de elementos de matriz 120.
Como se ha mencionado anteriormente, la relación
entre el entero que cumple 0\leqX\leq(n ! -1) y "n
término(s) de sustitución original" es biunívoca.
Asignando el símbolo \tau a la conversión y aplicándolo al entero
X, la unidad de sustitución de elementos de matriz 120 genera \tau
(V1) como V. Las decisiones de \tau a \tau (V1) se toman
unívocamente. Para \tau 0, se indicará cuántas conversiones \tau
1 cumplen \tau 0 (V1) = \tau 1.(V1).
n1 término(s) 1 de \tau 0 (V1) se
mantienen igual al valor de \tau 0 (V1) aunque se cambie su
posición. Del mismo modo, el resultado de \tau 0 (V1) no cambia
aunque se cambien las posiciones para n2 término(s) -1 y
(n-n1-n2) término(s)
0.
No obstante, si se cambia una posición de 1 por una posición de 0 o si se cambia la posición de 1 por una posición de -1, el resultado de \tau 0 (V1) es diferente. Por consiguiente, cualquier \tau 1 posible existe sólo para una combinación de cambio de posición en n1 término(s) 1 y n2 término(s) -1 y (n-n1-n2) término(s) 0. Debido a que existen n1 término(s) 1,
entonces hay (n1) ! tipos de conversión. Del mismo modo, para las sustituciones de n2 término(s) -1 y (n-n1-n2) término(s) 0, hay (n2) ! y (n-n1-n2) ! tipos de conversión para cada una. Por consiguiente, existen (n1) ! x (n2) ! x (n-n1-n2) ! tipos de \tau 1.
No obstante, si se cambia una posición de 1 por una posición de 0 o si se cambia la posición de 1 por una posición de -1, el resultado de \tau 0 (V1) es diferente. Por consiguiente, cualquier \tau 1 posible existe sólo para una combinación de cambio de posición en n1 término(s) 1 y n2 término(s) -1 y (n-n1-n2) término(s) 0. Debido a que existen n1 término(s) 1,
entonces hay (n1) ! tipos de conversión. Del mismo modo, para las sustituciones de n2 término(s) -1 y (n-n1-n2) término(s) 0, hay (n2) ! y (n-n1-n2) ! tipos de conversión para cada una. Por consiguiente, existen (n1) ! x (n2) ! x (n-n1-n2) ! tipos de \tau 1.
Por lo tanto, puede decirse que la unidad de
salida de matrices 100 de la primera forma de realización puede
convertir n ! tipos de enteros X en n ! / ((n1) ! x (n2) ! x
(n-n1-n2) !) tipos de sustituciones.
La descripción anterior pone de manifiesto también que la
uniformidad se elige utilizando n1 y n2, independientemente de los
tipos de sustitución.
Como se ha indicado anteriormente, la unidad de
salida de matrices 100 puede generar de manera uniforme la matriz
n-dimensional basándose en el entero X de entrada.
Asimismo, según la descripción anterior, es evidente que la unidad
de salida de matrices 100 siempre genera la misma salida para la
misma entrada.
Aunque hasta aquí lo expuesto se refiere al caso
de X<n !, puede aplicarse el mismo tipo de razonamiento al caso
de X > n ! tomando el resto de X dividido por n !.
Se considerará un caso en el que se utiliza un
parámetro particular. Cuando n=263, n1=16 y n2=16, la matriz que
pertenece a L(n, n1, n2) presenta n ! / ((n1) ! x (n2) ! x
(n-n1-n2) ! = 2^163 tipos. x^ y
indica la y-ésima potencia de X. n ! = 2^ 1741. Como longitud de
salida de la función resumen para conservar la uniformidad de la
distribución de la función resumen, se requieren 1741 bits o más.
Aunque actualmente no existe ninguna función resumen que presente
1741 bits o más como salida, se dispone de un sistema para calcular,
utilizando la función resumen, un valor de función resumen que
tiene una longitud superior a la longitud de salida de la función
resumen. Por consiguiente, aunque se necesita un valor de función
resumen que presente 1741 bits o más como salida, no existe ningún
problema que obstaculice la estructura del procedimiento de
encriptación de seguridad.
Según esta forma de realización, la unidad de
salida de matrices 100 puede generar de manera uniforme la matriz
n-dimensional basándose en el entero X de entrada.
Por esta razón, en el caso en el que se aplica la función FOSRT a
la encriptación NTRU, la unidad de salida de matrices 100 puede
generar de manera uniforme la matriz n-dimensional,
basándose en el valor de función resumen H (m) obtenido en la unidad
de función resumen 40. Es posible conservar la uniformidad de la
función resumen distribuida por la unidad de función resumen 40.
Por consiguiente, el dispositivo de encriptación 10 puede generar el
texto de encriptación e (v) con un alto nivel de seguridad.
Por otra parte, puesto que la unidad de salida
de matrices 100 establece la matriz V basándose sólo en el entero X,
no es necesario utilizar ninguna tabla de memoria, sino sólo una
pequeña cantidad de memoria.
Además, puesto que la unidad de salida de
matrices 105 del dispositivo de desencriptación 15 de la Figura
2(b) presenta la misma estructura que la unidad de salida de
matrices 100, es posible desencriptar el texto de encriptación
encriptado por el dispositivo de encriptación 10.
Aunque en la presente forma de realización se
supone que el procedimiento ejecutado por cada unidad que compone
el dispositivo de encriptación 10 y el dispositivo de
desencriptación 15 se realiza a través del software del
microordenador, dicho procedimiento también puede ser activado por
medio de hardware, tal como un circuito eléctrico o un CI.
Además, la estructura no se limita únicamente a
la estructura supuesta que genera la matriz basándose en el valor
de la función resumen utilizando la unidad de salida de matrices 100
del dispositivo de encriptación 10.
Asimismo, la unidad de salida de matrices 100
indicada en la Figura 3 incluye la unidad de determinación de
matriz inicial 110 y la unidad de sustitución de elementos de matriz
120, siendo operativa la unidad de sustitución de elementos de
matriz 120 para sustituir cada elemento de la matriz de elección
inicial V1 elegida por la unidad de determinación de matriz inicial
110 basándose en el entero X; no obstante, también es posible que
la unidad de salida de matrices (denominada en lo sucesivo "unidad
de salida de matrices 100a") sea operativa para ejecutar el
mismo procedimiento que la unidad de sustitución de elementos de
matriz 120, en el que se introduce el entero X y la matriz de
elección inicial predefinida, se sustituye la matriz de elección
inicial V1 basándose en el entero X y se genera la matriz V.
Debido a que la unidad de salida de matrices
100a estructurada de este modo ejecuta el mismo procedimiento que
la unidad de sustitución de elementos de matriz 120, ésta puede
conservar la uniformidad de la distribución de la función resumen,
no utilizar ninguna tabla y sustituir la matriz V1 sólo a partir de
la información del entero X. Por consiguiente, dicha unidad no
requiere una gran cantidad de memoria.
La unidad de salida de matrices 100a también
puede ser un dispositivo de encriptación o un procedimiento de
encriptación en el que se utiliza el entero X como clave, la matriz
de elección inicial V1 como mensaje y la matriz V como texto de
encriptación. Además, la unidad de salida de matrices 100a puede ser
un dispositivo de encriptación o un procedimiento de encriptación
en el que se utiliza la unidad de salida de matrices 100a.
Segunda forma de
realización
A continuación, se describirá el dispositivo de
encriptación en relación con la segunda forma de realización de la
presente invención.
El dispositivo de encriptación de la presente
forma de realización es una unidad de salida de matrices 200 que
presenta una estructura diferente a la unidad de salida de matrices
100 del dispositivo de encriptación 10 de la Figura 2(a).
Puesto que la estructura de las otras partes es común, su
descripción se omite.
La Figura 6 es un diagrama de bloques que
representa la estructura de la unidad de salida de matrices 200 de
la presente forma de realización.
Esta unidad de salida de matrices 200 introduce
el entero X y genera la salida V20 que pertenece a L (n, n1, n2).
En este caso, L(n, n1, n2) indica toda la matriz
n-dimensional que presenta n1 término(s) 1,
n2 término(s) -1 y otro(s)
(n-n1-n2) término(s) 0,
siendo n, n1 y n2 predefinidos en la unidad de salida de matrices
200.
La unidad de salida de matrices 200 consta de
una primera unidad de asignación de números 210 y una segunda
unidad de asignación de números 220 que ejecutan procedimientos, de
la misma forma que la unidad de salida de matrices 100, a través
del software del microordenador o el hardware (p. ej., un circuito
eléctrico).
La primera unidad de asignación de números 210
utiliza el entero X como entrada y pasa la matriz
n-dimensional V10, que presenta n1
término(s) 1 y otro(s) elemento(s) de valor 0,
y el entero X1, que se obtiene realizando un cálculo específico con
el entero X, a la segunda unidad de asignación de números 220. La
primera unidad de asignación de números 210 elige provisionalmente
un elemento de matriz cuya totalidad de elementos son 0 y cambia el
valor de los elementos de matriz de 0 a 1 basándose en el entero
X.
La segunda unidad de asignación de números 220
introduce la matriz V10 obtenida en la primera unidad de asignación
de números 210 y el entero X1 y genera la matriz
n-dimensional V20 que presenta n1 término(s)
1, n2 término(s) -1 y otro(s)
(n-n1-n2) término(s) 0. La
segunda unidad de asignación de números 220 cambia el valor del
elemento de la matriz generada por la primera unidad de asignación
de números 210 de 0 a -1.
A continuación, se describen en primer lugar las
acciones de la primera unidad de asignación de números 210.
La Figura 7 es un diagrama de flujo que
representa el procedimiento ejecutado por la primera unidad de
asignación de números 210. La primera unidad de asignación de
números 210 ejecuta el procedimiento en las etapas indicadas a
continuación. En la descripción siguiente, el i-ésimo elemento (por
la izquierda) de la matriz V10 va a ser V10[i]. Asimismo, el
valor del contador c1' va a ser el valor de recuento c1, y el valor
del contador c2' va a ser el valor de recuento c2.
La Figura 8 representa el estado de la matriz
V10 de la primera unidad de asignación de números 210 en cada fase
de la matriz.
En primer lugar, la primera unidad de asignación
de números 210 sustituye el argumento Y1 por el entero X
(etapa S201).
(etapa S201).
A continuación, la primera unidad de asignación
de números 210 establece en 0 (entero P1) todos los elementos de la
matriz V10 (etapa S202). La matriz inicial se elige en este
momento.
A continuación, la primera unidad de asignación
de números 210 establece el valor de recuento c1 del contador c1' en
1 (etapa S203).
A continuación, la primera unidad de asignación
de números 210 establece el valor de recuento c2 del contador c2' en
n (etapa S204).
A continuación, la primera unidad de asignación
de números 210 genera el cociente S y el resto R del argumento Y1
(dividendo) dividido por el valor de recuento c2 (divisor) (etapa
S205).
A continuación, la primera unidad de asignación
de números 210 establece en 1 (entero P2) el (R+1)-ésimo elemento
por la izquierda de los elementos con valor 0 de la matriz V10
(etapa S206).
A continuación, la primera unidad de asignación
de números 210 sustituye el argumento Y1 por el cociente S (etapa
S207).
A continuación, la primera unidad de asignación
de números 210 determina si el valor de recuento c1 es = n1 (etapa
S208). Si el valor de recuento c1 no es = n1 ("No" en la etapa
S208), la primera unidad de asignación de números 210 incrementa el
valor de recuento c1 (c1\leftarrowc1+1), puesto que el número del
elemento de valor 1 de la matriz V10 no ha llegado a n1
término(s). Entonces se continúa con el procedimiento para
reducir el valor de recuento c2
(c2\leftarrowc2-1) (etapa S209). A continuación,
la primera unidad de asignación de números 210 ejecuta el
procedimiento para obtener el cociente S y el resto R del argumento
Y1 dividido por el valor de recuento c2 otra vez (etapa S205).
Por otra parte, si la primera unidad de
asignación de números 210 determina que el valor de recuento c1 es
= n1 ("Sí" en la etapa S208), la matriz V10 y el valor del
argumento Y1 (el entero X1) se pasan a la segunda unidad de
asignación de números 220 (etapa S210), puesto que el número de
elementos de valor 1 de la matriz V10 ha llegado a n1
término(s), y el procedimiento se termina.
De este modo, la primera unidad de asignación de
números 210 repite las etapas del procedimiento comprendidas entre
la obtención del cociente S y el resto R hasta que el valor de
recuento c1 del contador c1' llega a n1 (etapa S205) y el
incremento del valor de recuento c1 y la reducción del valor de
recuento c2 (etapa 209). A continuación, cuando el valor de
recuento c1 del contador c1' llega a n1, es decir, cuando el número
de 1 entre los elementos de la matriz V10 ha llegado a n1
término(s), la primera unidad de asignación de números 210
pasa la matriz V10 a la segunda unidad de asignación de números
220.
A continuación, se describen las acciones de la
primera unidad de asignación de números 210 con referencia a
ejemplos concretos. La descripción se proporciona con un ejemplo
para el caso en el que el entero X que se introduce realmente es =
5644 y la matriz n-dimensional V 10 generada por la
primera unidad de asignación de números 210 es una matriz
octodimensional (n=8) que presenta 3 términos (n1-3)
1 y otros 5 términos 0.
En primer lugar, la primera unidad de asignación
de números 210 sustituye el argumento Y1 por 5644 (etapa
S201).
S201).
A continuación, la primera unidad de asignación
de números 210 cambia el estado de la matriz V10 al estado en el que
todos los elementos son de valor 0 (etapa S202), representado en la
matriz V11 de la Figura 8.
A continuación, la primera unidad de asignación
de números 210 establece el valor de recuento c1 en 1 (etapa S203) y
establece el valor de recuento c2 en 8 (etapa S204).
A continuación, la primera unidad de asignación
de números 210 genera el cociente S = 705 y el resto R = 4 a partir
del argumento Y1 = 5644 y el valor de recuento c2 = 8 (etapa
S205).
A continuación, la primera unidad de asignación
de números 210 establece en 1 el (R+1)-ésimo elemento por la
izquierda de los elementos que son 0 en la matriz V10, es decir, el
quinto elemento V10[5], y cambia el estado de la matriz V10
al estado representado en la matriz V12 de la Figura 8 (etapa
S206).
A continuación, la primera unidad de asignación
de números 210 sustituye el argumento Y1 por 705 (el cociente S)
(etapa S207).
A continuación, debido a que el valor de
recuento c1 es = 1 y el valor de recuento c1 no es = 3 (=n1)
("No" en la etapa S208), la primera unidad de asignación de
números 210 establece el valor de recuento c1 en 2 (incremento) y
establece el valor de recuento c2 en 7 (decremento) (etapa
S209).
A continuación, la primera unidad de asignación
de números 210 genera el cociente S y el resto R otra vez a partir
del argumento Y1=705 y el valor de recuento c2=7 (etapa S205). El
cociente S es 100 y el resto S es 5.
A continuación, la primera unidad de asignación
de números 210 establece en 1 el sexto elemento por la izquierda de
los elementos que son 0 en la matriz V10. El estado de la matriz V10
antes de este establecimiento es el estado representado en la
matriz V12 de la Figura 8. El elemento 0 de la matriz V12 es un
elemento distinto a V12[5]. Puesto que el sexto elemento de
los elementos que son 0 en la matriz V12 es V12[7], el valor
0 de V12[7] se cambia por 1 (etapa 206). Por esta razón, la
matriz se convierte en la matriz V13 representada en la Figura
8.
De esta manera, la primera unidad de asignación
de números 210 establece el elemento 0 de la matriz V10 en 1 de
conformidad con el resto R, hasta que el número del elemento de
valor 1 de la matriz V10 pasa a ser de n1
término(s) (n1=3, en este ejemplo). Cuando el número del elemento 1 pasa a tener 3 términos como se representa en la matriz V14 de la Figura 8, esta matriz se pasa a la segunda unidad de asignación de números 220 como matriz
V10.
término(s) (n1=3, en este ejemplo). Cuando el número del elemento 1 pasa a tener 3 términos como se representa en la matriz V14 de la Figura 8, esta matriz se pasa a la segunda unidad de asignación de números 220 como matriz
V10.
A continuación, se describen las acciones de la
segunda unidad de asignación de números 220.
La Figura 9 es un diagrama de flujo que
representa el procedimiento ejecutado por la segunda unidad de
asignación de números 220.
La Figura 10 representa el estado de la matriz
V20 de la segunda unidad de asignación de números 220 en cada fase
de la matriz.
En la descripción siguiente, se supone que el
i-ésimo elemento (por la izquierda) de la matriz V20 es
V10[i]. Se supone también que el valor del contador c1' es
el valor de recuento c1, y que el valor del contador c2' es el valor
de recuento c2.
En primer lugar, la segunda unidad de asignación
de números 220 sustituye el argumento Y2 por el valor del argumento
Y1 (entero X1) obtenido en la primera unidad de asignación de
números 210 (etapa S301).
A continuación, la segunda unidad de asignación
de números 220 sustituye la matriz V20 por la matriz V10 obtenida en
la primera unidad de asignación de números 210 (etapa S302).
A continuación, la segunda unidad de asignación
de números 220 establece el valor de recuento c1 en 1 (etapa
S303).
A continuación, la segunda unidad de asignación
de números 220 establece el valor de recuento c2 en
(n-n1) (etapa S304).
A continuación, la segunda unidad de asignación
de números 220 genera el cociente S y el resto R del argumento Y2
(dividendo) dividido por el valor de recuento c2 (divisor) (etapa
S305).
A continuación, la segunda unidad de asignación
de números 220 establece en -1 el (R+1)-ésimo elemento por la
izquierda de los elementos que son 0 en la matriz V20 (etapa
S306).
A continuación, la segunda unidad de asignación
de números 220 sustituye el argumento Y2 por el cociente S (etapa
S307).
A continuación, la segunda unidad de asignación
de números 220 determina si el valor de recuento c1 es = n2 (etapa
S308). Si la segunda unidad de asignación de números 220 determina
que el valor de recuento c1 no es = n2 ("No" en la etapa
S308), se incrementa el valor de recuento c1 (c1\leftarrowc1+1),
puesto que el número del elementos de valor -1 de la matriz V20 no
ha llegado a n2 término(s). Entonces, el procedimiento
continúa para reducir el valor de recuento c2
(c2\leftarrowc2-1) (etapa S309). A continuación,
la segunda unidad de asignación de números 220 ejecuta el
procedimiento para generar el cociente S y el resto R del argumento
Y2 dividido por el valor de recuento c2 otra vez (etapa S305).
\newpage
En cambio, si la segunda unidad de asignación de
números 220 determina que el valor de recuento c1 es = n2
("Sí" en la etapa S308), se genera la matriz V20 (etapa S310),
ya que el número del elemento de valor -1 de la matriz V20 ha
llegado a n2 término(s), y el procedimiento se termina.
De este modo, la segunda unidad de asignación de
números 220 repite las etapas del procedimiento comprendidas entre
la generación del cociente S y el resto R (etapa S305) hasta que el
valor de recuento c1 es =n2 y el incremento del valor de recuento
c1 y la reducción del valor de recuento c2 (etapa S309). Cuando el
valor de recuento c1 llega a =n2, se genera la matriz V20, porque
el número del elemento de valor -1 de los elementos de la matriz V20
ha llegado a n2 término(s) (n2=2 en este ejemplo).
A continuación, se describen las acciones de la
segunda unidad de asignación de números 220 con referencia a un
ejemplo concreto. El entero X1 obtenido realmente en la primera
unidad de asignación de números 210 va a ser = 150, y la matriz
n-dimensional V20 generada por la segunda unidad de
asignación de números 220 será, por ejemplo, la matriz
octodimensional (n=8) que presenta 3 términos (n1=3) 1, dos términos
(n2=2) -1 y otros 3 términos 0.
En primer lugar, la segunda unidad de asignación
de números 220 sustituye el argumento Y2 por 150 (etapa S301).
A continuación, la segunda unidad de asignación
de números 220 sustituye la matriz V20 por la matriz V10, que
presenta 3 términos 1 y otros 5 términos 0, generada por la primera
unidad de asignación de números 210. La matriz V21 de la Figura 10
es la matriz que se introduce como matriz sustituta (etapa
S302).
A continuación, la segunda unidad de asignación
de números 220 establece en 1 el valor de recuento c1 (etapa S303) y
establece en n-n1=8-3=5 el valor de
recuento c2 (etapa S304).
A continuación, la segunda unidad de asignación
de números 220 genera el cociente S=30 y el resto R=0 a partir del
argumento Y2=150 y el valor de recuento c2=5 (etapa S305).
A continuación, la segunda unidad de asignación
de números 220 establece en -1 el primer elemento por la izquierda
(es decir, V20[1]) de los elementos 0 de la matriz V20 (etapa
S306). En la matriz V22 de la Figura 10, se representa este estado
de matriz.
A continuación, la segunda unidad de asignación
de números 220 establece el argumento Y2 en 30 (el cociente S)
(etapa S307).
A continuación, debido a que el valor de
recuento c1=1 y que el valor de recuento c1 no es n2 (=2) ("No"
en la etapa S308), la segunda unidad de asignación de números 220
establece el valor de recuento c1 en 2 (incremento) y el valor de
recuento c2 en 4 (decremento) (etapa S309).
A continuación, la segunda unidad de asignación
de números 220 genera el cociente S y el resto R a partir del
argumento Y2=30 y el valor de recuento c2=4, otra vez (etapa S305).
El cociente S es = 7 y el resto R es = 2.
A continuación, la segunda unidad de asignación
de números 220 establece en -1 el (R+1)-ésimo elemento por la
izquierda de los elementos que son 0 de la matriz V20 (es decir, el
tercer elemento). El estado de la matriz V20 antes del
establecimiento es el de la matriz V22 representada en la Figura 10,
y el elemento 0 es V22[3], V22[4], V22[6],
V22[8]. Debido a que el tercer elemento por la izquierda de
los elementos que son 0 en la matriz V22 es V22[6], el valor
0 de V22[6] se establece en -1 (etapa S306). El estado de la
matriz después de este establecimiento es el de la matriz V23
representada en la Figura 10.
A continuación, la segunda unidad de asignación
de números 220 sustituye el argumento Y2 por 7 (el cociente S)
(etapa S307).
A continuación, en este momento, debido a que el
valor de recuento c1 es =2, es decir, el valor de recuento c1 es
=n2 ("Sí" en la etapa S308), la segunda unidad de asignación de
números 220 genera la matriz V20 (etapa S310). Esta matriz 20
generada está en el estado representado en la matriz V23 de la
Figura 10.
De este modo, la unidad de salida de matrices
200 genera la matriz n-dimensional que presenta n1
término(s) 1, n2 término(s) -1 y
(n-n1-n2) término(s) 0, a
partir del entero X que es el valor de la función resumen H (m).
La unidad de salida de matrices 200 mencionada
genera de forma uniforme la matriz L(n, n1, n2), basándose
en el entero X que cumple 0\leqX\leq(((n
!)/(n-n1-n2) !) -1). La descripción
siguiente se limita al entero X que cumple 0\leqX\leq(((n
!)/(n-n1-n2) !) -1).
La primera unidad de asignación de números 210
establece en 1 el elemento de la matriz V10 que se halla en la
ubicación basada en el entero X. A continuación, se centrará la
atención en el procedimiento detallado mediante el cual se
establece este elemento en 1. Asimismo, del mismo modo que en la
primera forma de realización, en la estructura de la primera unidad
de asignación de números 210, el resto de la etapa S205 del valor de
recuento c2 es R_c2. Globalmente, la descripción se estructura de la
siguiente forma:
(1) se indica que el procedimiento de asignación
no se duplica;
(2) mediante el razonamiento de (1), se indica
que entre el número X y el contenido de procesamiento de la unidad
de sustitución de elementos de matriz se establece una relación
biunívoca;
(3) se calculan cuántos tipos del número X dan
por resultado la misma matriz.
Independientemente de la matriz, es posible
determinar que el número de tipos del entero X es idéntico en el
cálculo de (3), demostrándose de ese modo que la salida está
uniformemente distribuida en relación con la entrada.
En primer lugar, se explicará porqué "el
procedimiento de asignación no se duplica".
La asignación del valor (1 ó -1) en la misma
posición de la matriz no se produce diversas veces; es decir, una
vez que se ha realizado la asignación, la posición en cuestión no se
tiene en cuenta como sujeto para la asignación en ningún
procedimiento posterior.
\vskip1.000000\baselineskip
\bullet Cuando el valor de
recuento c2 es
n
En la etapa S206, el (R_n+1)-ésimo elemento del
elemento de valor 0 de la matriz V10 se establece en 1. En este
caso, cuando el valor de recuento c2 es n, todos los elementos de
V10 son 0 antes de que el (R_n+1)-ésimo elemento se establezca en
1. Por consiguiente, esto significa que simplemente se establece en
1 el (R_n+1)-ésimo elemento.
\vskip1.000000\baselineskip
\bullet Cuando el valor de
recuento c2 es
n-1
En la etapa S206, el
(R_(n-1)+1)-ésimo elemento de los elementos
que son 0 de la matriz V10 se establece en 1. Debido a que el
elemento que es 0 en la matriz V10 se trata como sujeto para ser
establecido en 1, debe tenerse en cuenta que el (R_n)-ésimo
elemento establecido en el momento en el que el valor de recuento c2
es n no se trata como sujeto. Cuando el
(R_(n-1)+1)-ésimo elemento de los elementos
que son 0 en la matriz V10 es
R_(n-1)<R_n, entonces éste es simplemente
el (R_(n-1)+1-ésimo elemento de la matriz
V10. En el caso en el que R_(n-1)>R_n,
éste es el (R_(n-1)+2)-ésimo elemento de la
matriz V10.
Como se ha mencionado anteriormente, el elemento
establecido en 1 cuando el valor de recuento c2 es i no se
considera sujeto para ser establecido en 1 en la etapa en la que el
valor de recuento c2 es i+1 y posteriormente. Por consiguiente, el
elemento que ya se ha establecido una vez no vuelve a
establecerse.
\vskip1.000000\baselineskip
\bullet Cuando el procedimiento
de la primera unidad de asignación de números 210 ha
finalizado
Cuando todos los procedimientos han finalizado
en el momento en el que el valor de recuento c2 está comprendido
entre n y (n-n1+1), la matriz V10 presenta n1
término(s) 1 y otros (n-n1) término(s)
0. La descripción anterior de la primera unidad de asignación de
números 210 es aplicable también a la segunda unidad de asignación
de números 220. En el momento en el que el procedimiento de la
segunda unidad de asignación de números 220 ha finalizado, la matriz
V20 presenta n1 término(s) 1, n2 término(s) -1 y otros
(n-n1-n2) término(s) 0.
A continuación, se hará referencia a la unicidad
del procedimiento de la primera unidad de asignación de números 210
y la segunda unidad de asignación de números.
El razonamiento anterior (la asignación del
valor no se duplica) se utiliza para explicar porqué se establece
una relación biunívoca entre el entero X y el contenido de
procesamiento de la unidad de asignación de números es 1 a 1.
\vskip1.000000\baselineskip
\bullet Relación entre el entero
X y la
serie
Se supone que el entero X es un entero que
cumple 0\leqX\leq((n
!)/(n-n1-n2) !)-1).
En este momento, de la misma manera que en la primera forma de
realización, cuando el valor de recuento c2 es I, el resto R de la
etapa S205 de la primera unidad de asignación de números se supone
que es R_i, y el resto R de la etapa S305 en la que se ejecuta el
mismo procedimiento para la segunda unidad de asignación de números
también es R_i. El valor de recuento c2 de la primera unidad de
asignación de números 210 es el rango comprendido entre n y
n-n1+1. El valor de recuento c2 de la segunda unidad
de asignación de números 220 es el rango comprendido entre
n-n1 y n-n1-n2+1.
Por consiguiente, debe observarse que no se produce solapamiento
entre el valor de recuento c2 de la primera unidad de asignación de
números y el de la segunda unidad de asignación de números.
Entonces, el entero X, indicado a continuación, se expresa de la
misma manera que en la primera forma de realización.
Por consiguiente, el entero X establece una
relación biunívoca con la serie
R_(n-n1-n2+1), ..., R_n.
\vskip1.000000\baselineskip
\bullet Asignación de series y
enteros
Cuando el contador c2 es i de conformidad con
R_i(n-n1-n2+1\leqi\leqn),
se establece el valor 1 en el caso en el que el (R'_i+1)-ésimo
elemento de la matriz V20 cumple
n-n1+1\leqi\leqn, y se establece el valor -1 en
el caso en el que el (R'_i+1)-ésimo elemento de la matriz V20 cumple
n-n1-n2+1\leqi\leqn-n1.
Entonces, introduciendo el valor del contador c2 cuando se
establece una secuencia (1 ó -1), la serie
R_(n-n1-n2+1), ...,R_n y la
anterior establecen una relación biunívoca.
Cuando el valor de recuento c2 es j (j\neqi),
el (R'_i+1)-ésimo elemento se establece en y (y es 1 ó -1). Cuando
el valor de recuento c2 es i, se obtiene la misma matriz V20 para
establecer el (R'_i+1)-ésimo elemento en y, aunque el valor del
recuento c2 sea sustituido cuando se establece y. No hay otra forma
de generar la misma matriz V. Si se aplica el mismo razonamiento
que en la primera forma de realización, este tipo de sustitución
del valor de recuento c2 presenta (n1) ! término(s) para el
caso de y=1 y (n2) ! término(s) para el caso de y=-1. Por
consiguiente, el entero X que genera la misma matriz V20 presenta
(n1) ! x (n2) ! tipos.
La matriz pertenece a L(n, n1, n2) y
presenta n ! /(n1) ! x (n2) ! x
(n-n1-n2) !) tipos. Por
consiguiente, la unidad de salida de matrices 200 de la segunda
forma de realización puede generar de manera uniforme n ! /((n1) !
x (n2) ! x (n-n1-n2) !) tipos de
matrices basándose en n ! /(n-n1-n2)
! tipos del entero X.
A partir de lo anterior, resulta obvio también
que la unidad de salida de matrices 200 siempre genera la misma
salida para la misma entrada.
Aunque la descripción anterior hace referencia
al caso en el que X<n !/(n-n1-n2)
!, ésta puede aplicarse también al caso en el que X>n !
/(n-n1-n2) ! obteniendo el resto de
X dividido por (n ! /(n-n1-n2)
!).
A continuación, se indica una diferencia entre
el efecto de la primera forma de realización y el efecto de la
segunda forma de realización.
En la primera forma de realización, el valor de
recuento c del contador c' puede fluctuar entre n y 2. En cambio,
en la primera unidad de asignación de números 210 y la segunda
unidad de asignación de números 220 de la segunda forma de
realización, el valor de recuento c2 del contador c2' fluctúa entre
n y (n-n1-n2+1). Por consiguiente,
el valor del entero X presenta n ! tipos en la primera forma de
realización, mientras que presenta (n !
/(n-n1-n2)!) tipos en la segunda
forma de realización. Entonces, comparado con la primera forma de
realización, el tipo de entrada de la segunda forma de realización
puede reducirse hasta (1/(n-n1-n2)
!), y la longitud binaria de la entrada necesaria puede ser más
corta.
A continuación, se describe un caso en el que se
utilizan parámetros concretos. Cuando n=263, n1=16 y n2=16, la
matriz que pertenece a L(n, n1, n2) y tiene una longitud de n
! /(n1) ! x (n2) ! x (n-n1-n2) !) =
2^ 163 bits. Entonces,
n ! /(n-n1-n2) ! = 2 ^ 255 bits. Para conservar una función resumen de distribución bien equilibrada, es necesario que la función resumen tenga una longitud de salida de 255 bits o más. En comparación con la primera forma de realización, la longitud de salida de la función resumen necesaria es 1466 bits inferior y, por lo tanto, es más eficaz.
n ! /(n-n1-n2) ! = 2 ^ 255 bits. Para conservar una función resumen de distribución bien equilibrada, es necesario que la función resumen tenga una longitud de salida de 255 bits o más. En comparación con la primera forma de realización, la longitud de salida de la función resumen necesaria es 1466 bits inferior y, por lo tanto, es más eficaz.
Según la presente forma de realización, la
unidad de salida de matrices 200 puede generar de manera uniforme
la matriz n-dimensional basándose en el entero X.
Por consiguiente, cuando se aplica la función FOSRT a la
encriptación NTRU, es posible mantener la uniformidad de la
distribución bien equilibrada de la función resumen, utilizando la
unidad de salida de matrices 200 en lugar de la unidad de salida de
matrices 100 del dispositivo de encriptación 10 de la Figura
2(a), y disponiendo que esta unidad de salida de matrices 200
genere de manera uniforme la matriz n-dimensional
basándose en el valor de función resumen H (m) obtenido en la unidad
de función resumen 40. En consecuencia, esto permite aumentar el
nivel de seguridad del texto de encriptación generado por el
dispositivo de encriptación 10.
\newpage
Además, debido a que la unidad de salida de
matrices 200 establece la matriz V20 únicamente a partir de la
información del entero X, no necesita utilizar ninguna tabla de
memoria, sino sólo una pequeña cantidad de memoria.
Asimismo, en lugar de la unidad de salida de
matrices 105 del dispositivo de desencriptación 15 de la Figura
2(b), el texto encriptado puede ser desencriptado utilizando
la unidad de salida de matrices 200.
Aunque la presente forma de realización es
operativa para utilizar la unidad de salida de matrices 200 para el
dispositivo de encriptación 10 y generar la matriz basándose en el
valor de la función resumen, dicha forma de realización no se limita
a esto.
Tercera forma de
realización
A continuación, se describirá un dispositivo de
encriptación relacionado con la tercera forma de realización de la
presente invención. En comparación con el dispositivo de
encriptación 10 de la Figura 1, el dispositivo de encriptación de
la presente forma de realización incluye una unidad de salida de
matrices 300 que difiere en cuanto a estructura de la unidad de
salida de matrices 100. Puesto que los demás componente son
idénticos, su explicación se omite.
La unidad de salida de matrices 300 de la
presente invención se describe con referencia a los diagramas.
La Figura 11 es un diagrama de bloques que
representa la estructura de la unidad de salida de matrices 300 de
la presente forma de realización.
La unidad de salida de matrices 300 introduce el
entero X y genera la matriz V40 que pertenece a L (n, n1, n2). En
este caso, n, n1 y n2 son valores predefinidos y proporcionados a la
unidad de salida de matrices 300.
La unidad de salida de matrices 300, que consta
de una primera unidad de asignación de números 310 y una segunda
unidad de asignación de números 320, ejecuta el procedimiento a
través del software de un microordenador y de hardware, tal como un
circuito eléctrico, de la misma manera que la unidad de salida de
matrices 100.
La primera unidad de asignación de números 310
introduce el entero X y genera la matriz
n-dimensional V30, que presenta n1
término(s) 1 y otros elementos que son 0, y el entero X2
obtenido realizando un cálculo específico con el entero X. La
primera unidad de asignación de números 310 elige provisionalmente
el elemento de matriz que presenta el valor 0 en todos los
elementos de matriz y cambia el valor 0 de los elementos de matriz
al valor 1, basándose en el entero X.
La segunda unidad de asignación de números 320
introduce la matriz V30 y el entero X2 obtenidos en la primera
unidad de asignación de números 310 y genera la matriz
n-dimensional V40 que presenta n1 término(s)
1, n2 térmi-
no(s) -1 y otro(s) n(n-n1-n2) término(s) de valor 0. La segunda unidad de asignación de números 320 cambia el elemento de matriz que presenta el valor 0 en la matriz generada por la primera unidad de asignación de números 310 al valor -1.
no(s) -1 y otro(s) n(n-n1-n2) término(s) de valor 0. La segunda unidad de asignación de números 320 cambia el elemento de matriz que presenta el valor 0 en la matriz generada por la primera unidad de asignación de números 310 al valor -1.
A continuación, se describen las acciones de la
primera unidad de asignación de números 310.
La Figura 12 es un diagrama de flujo que
representa el procedimiento de la primera unidad de asignación de
números 310. La primera unidad de asignación de números 310 ejecuta
las etapas siguientes. En la exposición siguiente, se supone que el
i-ésimo elemento (por la izquierda) de la matriz V30 es
V30[i]. El contador c1' es el valor de recuento c1 y el
contador c2' es el valor de recuento c2. C (a, t) representa el
número de combinación cuando se seleccionan t término(s) de
s término(s). Para concretar, C (s, t) = s !
/((s-t) ! x t !).
Para empezar, la primera unidad de asignación de
números 310 sustituye el argumento Z1 por el entero X, y convierte
la matriz V30 en una matriz n-dimensional cuya
totalidad de elementos presenta el valor 0 (etapa S401). En este
momento, se elige la matriz inicial.
A continuación, la primera unidad de asignación
de números 310 establece el valor de recuento c1 del contador c1' en
n1, y el valor de recuento c2 del contador c2' en 1 (etapa
S402).
A continuación, la primera unidad de asignación
de números 310 determina si el argumento Z1 cumple Z1 \geq C
(n-c2, c1) (etapa S403). Cuando la primera unidad de
asignación de números 310 determina que el argumento Z1 cumple Z1
\geq C (n-c2, c1) ("Sí" en la etapa S403), se
sustituye el argumento Z1 por Z1-C
(n-c2, c1), el valor de recuento c1 del contador
c1' se reduce (c1\leftarrowc1-1) y el
(n-c2+1)-ésimo elemento de la matriz V30 se
establece en 1
(V30[n-c2+1]\leftarrow1) (etapa
S404). A continuación, la primera unidad de asignación de números
310 incrementa el valor de recuento c2 del contador c2' (etapa
S406).
Por otra parte, cuando la primera unidad de
asignación de números 310 determina que el argumento Z1 no cumple
Z1 \geq C (n-c2, c1) ("No" en la etapa S403),
el (n-c2+1)-ésimo elemento de la matriz V30 se
establece en 0
(V30(n-c2+1)\leftarrow0) (etapa
S405). A continuación, la primera unidad de asignación de números
310 incrementa el valor de recuento c2 del contador c2' (etapa
S406).
De este modo, según la relación de tamaños entre
el argumento Z1 y C (n-c2, c1), el
(n-c2+1)-ésimo elemento de la matriz V30 se
establece en 0 ó 1.
A continuación, cuando el valor de recuento c2
se incrementa (etapa S406), la primera unidad de asignación de
números 310 determina que el valor de recuento cumple c2>n (etapa
S407).
Cuando la primera unidad de asignación de
números 310 determina que el valor de recuento c2 no cumple c2 >
n ("No" en la etapa S407), se ejecuta otra vez el procedimiento
de determinación para determinar si el argumento Z1 cumple Z1
\geq C (n-c2, c1) (etapa S403), y repite las
etapas del procedimiento comprendidas entre la determinación de la
etapa S403 y la determinación del cumplimiento por el valor de
recuento de la condición c2>n (etapa S407) hasta que el valor de
recuento c2 cumple > n.
Por otra parte, cuando la primera unidad de
asignación de números 310 determina que el contador c2 cumple
c2>n ("Sí" en la etapa S407), pasa la matriz V30 y el entero
X2 (entero X2 = entero X/C (n, n1)) a la segunda unidad de
asignación de números 320.
A continuación, se describen las acciones de la
primera unidad de asignación de números 310 con referencia a un
ejemplo particular. En el ejemplo, el entero X que realmente se
introduce es 50, y la matriz generada por la primera unidad de
asignación de números 310 es la matriz V30 (por ejemplo, la matriz
octodimensional (n=8) que presenta 4 (n1=4) términos 1 y otros 4
términos 0).
En la Figura 14(a), se representa el
estado de matriz de cada fase de la matriz V30.
En primer lugar, la primera unidad de asignación
de números 310 substituye el argumento Z1 por 50 (etapa S401).
A continuación, la primera unidad de asignación
de números 310 establece el valor de recuento c1 del contador c1' en
4, y el valor de recuento c2 del contador c2' en 1 (etapa S402).
En este caso, puesto que el argumento Z1 (=50)
es \geq C (7, 4) (=35) ("Sí" en la etapa S403), la primera
unidad de asignación de números 310 establece el argumento
Z1\leftarrow50-35=15, el valor de recuento c1=3 y
el octavo elemento por la izquierda en la matriz V30,
V30[8]=1 (etapa S404). El estado de la matriz V30 en este
momento es el de la matriz V31 representada en la Figura 14.
A continuación, la primera unidad de asignación
de números 310 incrementa el valor de recuento c2 hasta 2 (etapa
S406).
Debido a que el valor de recuento c2 no es >8
("No" en la etapa S407), la primera unidad de asignación de
números 310 no genera la matriz V30 y determina otra vez (etapa
S403) la relación de tamaños del argumento Z1 y C
(n-c2, c1).
En este caso, debido a que el argumento Z1 (=15)
es < C (6, 3) (=20) ("No" en la etapa S403), la primera
unidad de asignación de números 310 establece en 0 el séptimo
elemento por la izquierda de la matriz V30, V30[7] (etapa
S405). El estado de la matriz V30 en este momento es el de la matriz
V32 indicada en la Figura 14.
De esta manera, según la relación de tamaños del
argumento Z1 y C (n-c2, c1), se establecen los
valores 1 ó 0 en secuencia para cada elemento de la matriz V30.
Cuando se han establecido todos los elementos, la primera unidad de
asignación de números 310 pasa la matriz V30 a la segunda unidad de
asignación de números 320.
El procedimiento anterior se denomina algoritmo
de Schalkvijk. El algoritmo de Schalkvijk se describe en detalle en
el documento "An Algorithm for Source Coding", Schalkvijk,
IT72-18, 1972 (en lo sucesivo, denominado
"Documento 4").
A continuación, se describen las acciones de la
segunda unidad de asignación de números 320.
La Figura 13 es un diagrama de flujo que
representa el procedimiento de la segunda unidad de asignación de
números 320. La segunda unidad de asignación de números 320 ejecuta
las etapas siguientes.
Se supone que el i-ésimo elemento (por la
izquierda) de la matriz V40 es V40[i]. Además, el valor del
contador c1' es el valor de recuento c1 y el valor del contador c2'
es el valor de recuento c2.
En primer lugar, la segunda unidad de asignación
de números 320 sustituye el argumento X2 por el entero obtenido en
la primera unidad de asignación de números 310 para el argumento Z2,
sustituye la matriz V40 por la matriz V30 y dispone que la matriz W
sea la (n-n1)-ésima matriz, cuya totalidad de
elementos son 0 (etapa S501).
A continuación, la segunda unidad de asignación
de números 320 establece en n2 el valor de recuento c1 del contador
c1'y establece en 1 el valor de recuento c2 del contador c2' (etapa
S502).
\newpage
A continuación, la segunda unidad de asignación
de números 320 determina si el argumento Z2 cumple Z2\geqC
(n-n1-c2, c1) (etapa S503). Cuando
se determina que Z2\geqC (n-n1-c2,
c1) ("Sí" en la etapa 503), el argumento Z2 es sustituido por
Z2-C (n-n1-c2, c1),
el valor de recuento c1 es reducido
(c1\leftarrowc1-1) y el
(n-n1-c2+1)-ésimo elemento de la
matriz W se establece en -1 (etapa S504). A continuación, la segunda
unidad de asignación de números 320 incrementa el valor de recuento
c2 (etapa S506).
Por otra parte, cuando la segunda unidad de
asignación de números 320 determina que Z2 no es \geq C
(n-n1-c2, c1) ("No" en la
etapa S503), se establece el
(n-n1-c2+1)-ésimo elemento de la
matriz W en 0 (etapa S505). A continuación, la segunda unidad de
asignación de números 320 incrementa el valor de recuento c2 (etapa
S506).
De este modo, según la relación de tamaños entre
el argumento Z2 y C (n-n1-c2, c1),
el (n-n1-c2+1)-ésimo elemento de la
matriz W se establece en 0 ó 1.
A continuación, cuando la segunda unidad de
asignación de números 320 incrementa el valor de recuento c2 (etapa
S506), se determina si el valor de recuento c2 cumple
c2>n-n1 (etapa S507). Cuando la segunda unidad de
asignación de números 320 determina que c2 no cumple
c2>n-n1 ("No" en la etapa S507), se realiza
otra vez la determinación para averiguar si el argumento Z2 es
\geq C (n-n1-c2, c1) (etapa S503),
y se repite el procedimiento desde la etapa S503 hasta la etapa
S507 de determinación de c2>n-n1, hasta que c2
cumple c2>n-n1.
En resumen, la segunda unidad de asignación de
números 320 establece el
(n-n1-c2+1)-ésimo elemento de la
matriz W en 0 ó 1 según la relación de tamaños entre el argumento
Z2 y C (n-n1-c2, c1) en cada caso en
el que el valor de recuento c2 es un valor entre 1 y
(n-n1).
Por otra parte, cuando la segunda unidad de
asignación de números 320 determina si c2 es
>n-n1 ("Sí" en la etapa S507), el
procedimiento continúa para establecer el valor de recuento c1 en 1
y el valor de recuento c2 en 1 (etapa S508).
A continuación, la segunda unidad de asignación
de números 320 determina si el c1-ésimo elemento de la matriz V40,
V40[c1] es 1 (etapa S509). Si se determina que V40[c1]
= 1 ("Sí" en la etapa S509), se incrementa el valor de
recuento c1 (c1\leftarrowc1+1) (etapa S512) y se ejecuta el
procedimiento de determinación anterior (S509).
Por otra parte, cuando la segunda unidad de
asignación de números 320 determina que V40[c1] no es =1
("No" en la etapa S509), se sustituye el c2-ésimo elemento de
la matriz V40, V40[c1], por el c2-ésimo elemento de la
matriz W, W[c2], y se incrementa el valor de recuento c2
(c2\leftarrowc2+1) (etapa S510).
A continuación, la segunda unidad de asignación
de números 320 determina si el valor de recuento c2 cumple c2 >n
- n1 (etapa S511). Cuando se determina que el valor de recuento c2
no cumple c2>n-n1 ("No" en la etapa S512),
se continúa con el procedimiento para incrementar el valor de
recuento c1 (c1\leftarrowc1+1) (etapa S512).
Por otra parte, cuando se determina que el valor
de recuento c2 cumple c2 > n - n1, la segunda unidad de
asignación de números 320 pasa la matriz V40 al exterior y el
procedimiento se termina.
Durante el procedimiento anterior comprendido
entre la etapa S508 de establecimiento del valor de recuento c1 en
1 y del valor de recuento c2 en 1 y la etapa S512 de generación de
la matriz V40, se lleva a cabo la sustitución en secuencia del
c1-ésimo elemento 0 de V[c1], por los elementos de
W[c2].
Las acciones de la segunda unidad de asignación
de números 320 se describen con referencia a un ejemplo concreto.
En el ejemplo, se supone que el entero X2 introducido realmente es
=20, y que la matriz V40 generada por la primera unidad de
asignación de números 320 es, por ejemplo, la matriz octodimensional
(n=8) que presenta 4 términos (n1=4) 1, 2 términos (n2=2) -1 y otros
2 términos 0.
La Figura 14 (b) representa el estado de la
matriz en cada fase de la matriz V40 y la Figura 14(c)
representa el estado de la matriz en cada fase de la matriz W.
En primer lugar, la segunda unidad de asignación
de números 320 establece en 20 el argumento Z2, sustituye, por
ejemplo, la matriz V40 por una matriz que presenta el estado de la
matriz V41 de la Figura 14(b) generada por la primera unidad
de asignación de números 310, y convierte la matriz W en la matriz
(n-n1)-dimensional
(tetradimensional), cuya totalidad de elementos son 0 (etapa
S501).
A continuación, la segunda unidad de asignación
de números 320 establece el valor de recuento c1 del contador c1' en
2 y establece el contador c2 en 1 (etapa S502).
A continuación, la segunda unidad de asignación
de números 320 determina la relación de tamaños entre el argumento
Z2 y C (n-n1-c2, c1) (etapa S503).
Debido a que el argumento Z2 (=20) es \geqC (3, 2) (=3) ("Sí"
en la etapa S503), la segunda unidad de asignación de números 320
establece el argumento Z2 en 20-3 = 17, el valor de
recuento c1 en 1 y el cuarto elemento por la izquierda de la matriz
W (es decir, W[n-n1-c2+1] en
-1 (etapa S504). Este estado de la matriz es el representado en la
matriz W1 de la Figura 14(c).
De este modo, cada elemento de la matriz W se
establece en 0 ó -1. La matriz W2 de la Figura 14(c) es un
ejemplo de estado de matriz de todos los elementos establecidos.
A continuación, cuando todos los elementos de la
matriz W se han establecido ("Sí" en la etapa S507), la segunda
unidad de asignación de números 320 establece el valor de recuento
c1 del contador c1' en 1 y el valor del recuento c2 del contador
c2' en 1 (etapa S508). En un procedimiento subsiguiente, se
sustituye el elemento 0 de la matriz V41 por cada elemento de la
matriz W.
En este momento, se supone que el estado de la
matriz V40 es el de la matriz V41 y que el estado de la matriz W es
el de la matriz W2. En primer lugar, puesto que el c1-ésimo elemento
de la matriz V41, es decir V41[1], es =0 ("No" en la
etapa S509), se sustituye V41[1] por el c2-ésimo elemento de
la matriz W (0 = W[1]). La matriz V42 de la Figura
14(b) se halla en dicho estado.
De este modo, la segunda unidad de asignación de
números 320 sustituye el elemento 0 de la matriz V41 por todos los
elementos de la matriz W2 (desde la etapa S509 hasta la etapa S512
del procedimiento), y genera la matriz 41. La matriz V43 de la
Figura 14(b) se halla en el estado en el que el elemento 0 de
la matriz V41 es sustituido por el elemento 2.
A continuación, se describen todas las acciones
de la unidad de salida de matrices 300. En primer lugar, la primera
unidad de asignación de números 310 introduce el entero X y pasa la
matriz n-dimensional V30, que presenta n1
término(s) 1 y otros elementos que son 0, y el entero X2
(entero X2 = entero X/C (n, n1)), a la segunda unidad de asignación
de números 320.
A continuación, la segunda unidad de asignación
de números 320 introduce la matriz V30, que se obtiene en la
primera unidad de asignación de números 310, y el entero X2, y
genera la matriz n-dimensional V40 que presenta n1
término(s) 1, n2 término(s) -1 y otros elementos que
son 0.
La presente forma de realización pone en
práctica el algoritmo de Schalkvijk. Para concretar, el algoritmo
de Schalkvijk se utiliza cuando se elige la ubicación de asignación
para el elemento 1 en la matriz V30 de la primera unidad de
asignación de números 310, y cuando se elige la ubicación de
asignación para el elemento -1 en la matriz V40 de la segunda unidad
de asignación de números 320.
La unidad de salida de matrices 300 convierte el
entero X, que cumple 0\leqX\leqC (n, n1) x C
(n-n1, n2) (=n !/((n1) ! x (n2) ! X
(n-n1-n2) !), en L(n, n1,
n2), en una relación biunívoca.
A continuación, se describirá la conversión de
relación 1 a 1, limitando el ejemplo al entero X que cumple
0\leqX\leqC (n, n1)XC (n-n1, n2).
En la primera unidad de asignación de números
310 y la segunda unidad de asignación de números 320, se elige la
ubicación de asignación para 1 y -1 utilizando el algoritmo de
Schalkvijk. Si el objeto se limita a los tipos de salida para la
entrada o menos, se sabe que el algoritmo de Schalkvijk puede
convertir el objeto en la correspondencia 1 a 1. Descrito en
detalle en el Documento 4 mencionado. Por consiguiente, la unidad
de salida de matrices 300 de la tercera forma de realización genera
la matriz V4 (que mantiene la relación 1 a 1 con el entero X).
Entonces, se supone que la unidad de salida de matrices 300 genera
de manera uniforme la matriz, basándose en el entero X de
entrada.
A continuación, se indicará la diferencia entre
el efecto de la tercera forma de realización y el efecto de la
primera y la segunda forma de realización.
En la primera forma de realización, el valor del
entero X para un valor de salida, existen (n1) ! x (n2) ! x
(n-n1-n2) ! tipos para su valor de
entrada. En la segunda forma de realización, existen (n1) ! x (n2) !
tipos. En comparación, esta relación se convierte en la relación 1
a 1 en la tercera forma de realización. De este modo, la longitud
binaria necesaria para la entrada se mantiene en un valor mínimo
para conservar la uniformidad de la entrada.
A continuación, se describe el caso en el que se
utiliza un parámetro particular. Cuando n=263, n1=16 y n2=16, la
matriz que pertenece a \phi (n, n1, n2) es n ! /((n1) ! x (n2) ! x
(n - n1 -n2) !) = 2^{n} 163. Por consiguiente, la longitud de
salida de la función resumen puede ser de sólo 163 bits o más, que
es 92 bits inferior a la que se requiere en la segunda forma de
realización.
No obstante, es necesario calcular C (n - n1,
c2) y C (n - n1 - n2, c2) en la primera unidad de asignación de
números y la segunda unidad de asignación de números del dispositivo
de salida de matrices 300 de la tercera forma de realización.
Puesto que el cálculo incluye un cálculo factorial, el volumen de
cálculo se incrementa. En cambio, el volumen del cálculo de la
primera y la segunda forma de realización permanece bajo, debido a
que éstos no incluyen el cálculo factorial.
De este modo, según la presente forma de
realización, la unidad de salida de matrices 300 puede generar de
manera uniforme la matriz n-dimensional basándose en
el entero X. Entonces, de conformidad con lo anterior, se aplica la
función FOSRT a la encriptación NTRU y se utiliza la unidad de
salida de matrices 300 en lugar de la unidad de salida de matrices
100 del dispositivo de encriptación 10 de la Figura 2 (a). Es
posible, pues, conservar la distribución bien equilibrada de la
función resumen, disponiendo que la unidad de salida de matrices
300 genere de manera uniforme la matriz
n-dimensional basándose en el valor de función
resumen H (m) obtenido en la unidad de función resumen 40. En
consecuencia, el nivel de seguridad del texto de encriptación
generado por el dispositivo de encriptación 10 puede ser
aumentado.
Además, debido a que la unidad de salida de
matrices 300 establece la matriz V40 sólo a partir del entero X, no
es necesario utilizar una tabla de memoria, sino sólo una pequeña
cantidad de memoria.
Otra posibilidad es que el texto encriptado sea
desencriptado mediante la unidad de salida de matrices 300 en lugar
de la unidad de salida de matrices 105 del dispositivo de
desencriptación 15 de la Figura 2 (b).
Aunque la presente forma de realización es
operativa para generar la matriz basándose en el valor de la función
resumen cuando se utiliza la unidad de salida de matrices 300 del
dispositivo de encriptación 10, esto no constituye una limitación
para la misma.
\vskip1.000000\baselineskip
Cuarta forma de
realización
A continuación, se describe el dispositivo de
encriptación relacionado con la cuarta forma de realización de la
presente invención. El dispositivo de encriptación de la presente
forma de realización se compone de la unidad de salida de matrices
400 que presenta diferencias en cuanto a estructura con la unidad de
salida de matrices 100 del dispositivo de encriptación 10 de la
Figura 2. La descripción de la parte de estructura que es común a
las otras formas de realización se omite.
La unidad de salida de matrices 400 de la
presente forma de realización se describe haciendo referencia a los
diagramas.
La Figura 15 es un diagrama de bloques que
representa la estructura de la unidad de salida de matrices 400 de
la presente forma de realización.
Esta unidad de salida de matrices 400 introduce
el entero X y genera la matriz V50 que pertenece a L (n, n1, n2). L
(n, n1, n2) es la matriz n-dimensional completa que
presenta n1 término(s) 1, n2 término(s) -1 y
otro(s) (n-n1-n2)
término(s) 0, siendo n, n1 y n2 predefinidos en la unidad de
salida de matrices 400. La unidad de salida de matrices 400 elige
provisionalmente el elemento de matriz cuya totalidad de elementos
de matriz son 0, y cambia los elementos de matriz que son 0 a 1 y -1
basándose en el entero X.
La unidad de salida de matrices 400 ejecuta el
procedimiento a través del software del microordenador o de
hardware, tal como un circuito eléctrico, de la misma manera que la
unidad de salida de matrices 100.
A continuación, se describen las acciones de la
unidad de salida de matrices 400.
En primer lugar, la unidad de salida de matrices
400 pasa la matriz V50 al estado de matriz en el que todos los
elementos son 0.
A continuación, la unidad de salida de matrices
400 divide el entero X en partes de 8 bits. El entero X se indica
mediante un conjunto de información binaria expresada en 2 valores
de 0 y 1. Como se representa en la Figura 17, el entero X se divide
en (n1 + n2) término(s) por cada 8 bits.
La Figura 17 es un diagrama que representa el
estado en el que el entero X se ha dividido en: información partida
D[0], información partida D[1], ..., información
partida D[n1 + n2-1]. Cada elemento de
información partida D[0], información partida D[1],
..., información partida D[n1 + n2-1]
representa un entero de 8 bits de información.
En este caso, si la información partida de 8
bits D[0] representa el entero Q, la unidad de salida de
matrices 400 establece el valor 1 si el (Q+1)-ésimo elemento (en lo
sucesivo, denominado p0-ésimo elemento) es 0. Subsiguientemente, la
unidad de salida de matrices 400 establece el valor 1 si el p1-ésimo
elemento representado por p1 = (p0+D[1]) mod n es
0.
De esta manera, la unidad de salida de matrices
400 establece el valor 1 en secuencia si el pi-ésimo elemento
representado por pi = (P (i-1) + D[i] mod n
(en este caso, i = 1\simn1 + n2-1) de la matriz
V50 basada en la información partida D[i] es 0. Asimismo, el
pi-ésimo elemento de la matriz V50 se refiere al pi-ésimo elemento
por la izquierda de la matriz V50.
En este momento, la unidad de salida de matrices
400 no establece el valor 1 si el pi-ésimo elemento de la matriz
V50 no es 0, toma en consideración pi\leftarrow(pi+1) mod n
y establece en 1 el elemento 0 situado a la derecha del pi-ésimo
elemento.
Como se ha indicado anteriormente, la unidad de
salida de matrices 400 ejecuta el procedimiento para establecer en
1 el elemento de la matriz V50. Cuando existen n1 término(s)
1, la unidad de salida de matrices 400 ejecuta el procedimiento
para establecer el elemento -1, basándose en la información partida
D[i], hasta que el número de elementos -1 de la matriz V50
llega a n2 término(s).
A continuación, se describen en detalle las
acciones de la unidad de salida de matrices 400.
La Figura 16 es un diagrama de flujo que
representa el procedimiento ejecutado por la unidad de salida de
matrices 400. La unidad de salida de matrices 400 ejecuta las etapas
siguientes. El valor del contador c1' va a ser el valor de recuento
c1 y el valor del contador c2' va a ser el valor de recuento c2.
En primer lugar, la unidad de salida de matrices
400 sustituye el argumento Y10 por el entero X (etapa S601).
A continuación, la unidad de salida de matrices
400 pasa la matriz V50 al estado en el que todos los elementos son 0
(etapa S602).
A continuación, la unidad de salida de matrices
400 divide el entero X en partes de 8 bits, obteniéndose:
información partida D[0], información partida D[1],
..., información partida D[n1+n2-1] (etapa
S603).
A continuación, la unidad de salida de matrices
400 establece el valor de recuento c1 del contador c1' en 0 (etapa
S604).
A continuación, la unidad de salida de matrices
400 establece el valor de recuento c2 del contador c2' en
D[0] + 1 (etapa S605). Por consiguiente, el valor de recuento
c2 pasa a ser el valor del entero Q+1 representado por la
información partida de 8 bits D[0].
A continuación, la unidad de salida de matrices
400 determina si el c2-ésimo elemento V50[c2] de la matriz
V50 es 0 (etapa S605). Si dicho elemento no es 0 ("No" en la
etapa S606), el valor de recuento c2 se establece como
c2\leftarrow(c2+1)mod n (etapa S607), y la unidad de
salida de matrices 400 determina otra vez si el elemento
V50[c2] es 0 o no (etapa S606). Por otra parte, cuando la
unidad de salida de matrices 400 determina que V50[c2] es 0
("Sí" en la etapa S606), el elemento V50[c2] se
establece en 1 (etapa S608).
Según estos procedimientos, es decir, el
procedimiento para determinar si el elemento V50[c2] es 0
(etapa S606), el procedimiento para
c2\leftarrow(c2+1)mod n (etapa S607) y el
procedimiento para V50[c2]\leftarrow1, si el
elemento V50[c2] no es 0, se realiza una búsqueda en
secuencia del elemento 0 situado a la derecha de V50[c2] y se
establece en 1.
A continuación, la unidad de salida de matrices
400 determina si el valor de recuento c1 del contador c1' cumple
c1>n1-1 (etapa S609).
Cuando la unidad de salida de matrices 400
determina que el valor de recuento c1 del contador c1' cumple
c1<n1-1 ("Sí" en la etapa S609), se
incrementa el valor de recuento c1(c1\leftarrowc1+1), se
establece el valor de recuento c2 como
c2\leftarrow(c2+D[c1])mod n (etapa S610) y se
determina otra vez si V50[c2] es 0 (etapa S605).
Por consiguiente, el procedimiento para
establecer el elemento en 1 se ejecuta hasta que el número de
elementos 1 de la matriz V50 llega a n1 término(s).
Por otra parte, cuando la unidad de salida de
matrices 400 determina que el valor de recuento c1 no cumple
c1<n1-1 ("No" en la etapa S609), se supone
que el número de elementos 1 de la matriz V50 es de n1
término(s). Por consiguiente, para establecer el elemento en
-1 en la matriz V50, se establece el valor de recuento c1 en 0
(etapa S611) y se establece el valor de recuento c2 como
c2\leftarrow(c2+D[n1]mod n (etapa S612).
A continuación, la unidad de salida de matrices
400 determina si el elemento V50[c2] de la matriz V50 es 0
(etapa S614). Si el elemento no es 0 ("No" en la etapa S614),
se establece el valor de recuento c2 como
c2\leftarrow(c2+1)mod n (etapa S613) y se determina
otra vez si el elemento V50[c2] es 0 (etapa S614). Por otra
parte, cuando la unidad de salida de matrices 400 determina que
V50[c2] es 0 ("Sí" en la etapa S614), el elemento
V50[c2] se establece en -1 (etapa S615).
Según estos procedimientos (es decir, el
procedimiento para determinar si el elemento V50[c2] es 0
(etapa S614), el procedimiento para
c2\leftarrow(c2+1)mod n (etapa S613) y el
procedimiento para V50[c2]\leftarrow -1(etapa
S615), si el elemento V50[c2] no es 0, se realiza una
búsqueda secuencial del elemento situado a la derecha de
V50[c2] y éste se establece en -1.
A continuación, la unidad de salida de matrices
400 determina si el valor de recuento c1 del contador c1' cumple
c1>n2-1 (etapa S616).
Cuando la unidad de salida de matrices 400
determina que c1 cumple c1<n2-1 ("Sí" en la
etapa S616), se incrementa el valor de recuento c1
(c1\leftarrowc1+1) y se establece el valor de recuento c2 como
c2\leftarrow(c2+D[c1+n1]mod n (etapa S617), y
se determina otra vez si V50[c2] es 0 (etapa S614).
\newpage
\global\parskip0.900000\baselineskip
Por otra parte, cuando la unidad de salida de
matrices 400 determina que no se cumple c1>n2-1
("No" en la etapa S616), se genera la matriz V50, puesto que el
número de elementos -1 de la matriz V50 llega a n2
término(s).
A continuación, se describe un ejemplo concreto
conjuntamente con el diagrama de flujo de la Figura 16.
La Figura 18 representa el estado de la matriz
V50 en cada fase de la unidad de salida de matrices 400.
La matriz V50 es la matriz de 251 dimensiones
(n=251), y n1=50, n2=50. Cuando el entero X se divide en partes de 8
bits, la información partida puede adoptar la siguiente forma, por
ejemplo: información partida D[0]=139 e información partida
D[1]=130.
Según el presente ejemplo concreto, el valor de
recuento c2 es = D[0]+1=140 en el diagrama de flujo de la
Figura 16 (etapa S605).
A continuación, debido a que todos los elementos
de la matriz V50 son 0, el 140-ésimo elemento V50[140] por
la izquierda de la matriz V50 se establece en 1 (etapa S608). Este
estado de la matriz corresponde al de la matriz V51 representada en
la Figura 18, en la cual el 140-ésimo elemento es 1 y los demás
elementos son 0.
A continuación, debido a que el número de
elementos 1 de la matriz V50 no es de 50 términos ("No" en la
etapa S609), el valor de recuento c2 se establece como
c2\leftarrow(c2+D[1]mod n (etapa S610) para
ejecutar el procedimiento de establecimiento del elemento de la
matriz V50 en 1. El valor de recuento c2 llega a ser =
(140+130)mod 251 =19 mod 251, y el 19-ésimo elemento
V51[19] por la izquierda de la matriz V51 se establece en 1.
Este estado de matriz es el representado en la matriz V52 de la
Figura 18, en la que se observa que el 19-ésimo y el 140-ésimo
elemento por la izquierda son 1 y los demás elementos son 0.
De este modo, cuando cada elemento de la matriz
V50 presenta el valor 1, si el elemento de la posición que va a
establecerse (por ejemplo V50[120]) ya ha sido 1, entonces se
busca el elemento de la derecha para hallar el elemento 0,
estableciéndose en 1 el primer elemento de valor 0 hallado. A
continuación, si todos los elementos hasta V50[251] son 0, se
retrocede hasta el extremo izquierdo V50[1] y se establece el
elemento 0 en 1.
El elemento -1 de la matriz V50 se establece
secuencialmente de la misma manera.
Como se ha indicado anteriormente, la unidad de
salida de matrices 400 elige de manera uniforme el primer elemento
1 de la matriz V50, basándose en la información partida D[0]
hallada por el entero X. A continuación, basándose en la
información partida D[i] hallada por el entero X a partir del
primer elemento 1 elegido, se elige la ubicación para establecer el
siguiente elemento, permitiendo de ese modo que la matriz V50 se
distribuya de manera uniforme a partir del entero X para establecer
los valores 1 ó -1.
En este momento, el entero que X que se va a
introducir requiere (n1+n2) término(s) de información partida
de 8 bits para que la unidad de salida de matrices 400 elija n1
término(s) 1 y n2 término(s) -1 de la matriz V50. Por
esta razón, puede seleccionarse un entero X de valor alto en la fase
de diseño para tener suficiente margen para establecer cada elemento
de la matriz V50.
De este modo, según la presente forma de
realización, la unidad de salida de matrices 400 puede generar de
manera uniforme la matriz n-dimensional basándose en
el entero X. Por esta razón, cuando se aplica la función FOSRT a la
encriptación NTRU, se utiliza la unidad de salida de matrices 400 en
lugar de la unidad de salida de matrices 100 del dispositivo de
encriptación 10 de la Figura 2(a), y la unidad de salida de
matrices 400 genera de manera uniforme la matriz
n-dimensional basándose en el valor de función
resumen H (m) obtenido en la unidad de función resumen 40. Por
consiguiente, es posible conservar la distribución bien equilibrada
de la función resumen y aumentar el nivel de seguridad del texto de
encriptación generado por el dispositivo de encriptación 10.
Además, puesto que la unidad de salida de
matrices 400 establece la matriz V50 sólo a partir del entero X, no
es necesario utilizar ninguna tabla de memoria, sino sólo una
pequeña cantidad de memoria.
Para desencriptar el texto encriptado, puede
utilizarse la unidad de salida de matrices 200 en lugar de la
unidad de salida de matrices 105 del dispositivo de desencriptación
15 de la Figura 2(b).
Aunque la presente forma de realización permite
que la unidad de salida de matrices 100 sea utilizada para que el
dispositivo de encriptación 10 genere la matriz basándose en el
valor de la función resumen, esto no constituye una limitación para
la misma.
El dispositivo de encriptación 10 descrito en
cada forma de realización puede instalarse y utilizarse en un
dispositivo de teléfono portátil 500 como el representado en la
Figura 19, o puede utilizarse en las transacciones eléctricas o el
comercio eléctrico de Internet.
Además, aunque en las formas de realización 1,
2, 3 y 4 la matriz que genera cada unidad de salida de matrices
presenta n1 término(s) 1, n2 término(s) -1 y otros
elementos que son 0, esta matriz puede presentar otros números de
términos 1 y -1. Asimismo, aunque en las formas de realización 1, 2,
3 y 4 cada unidad de salida de matrices genera 3 valores (1, -1 y
0), éstas también pueden generar 2 valores, 4 valores o más.
\global\parskip1.000000\baselineskip
Es posible, asimismo, disponer de un
procedimiento de encriptación que utilice una de las formas de
realización 1, 2, 3 ó 4.
Como resulta obvio a partir de la descripción
anterior, gracias al dispositivo de salida de matriz numérica que
genera diversas matrices n-dimensionales que constan
de n enteros de valor K, cada uno de los cuales es uno de los K
tipos de enteros posibles, dependiendo del entero de entrada, y que
comprende: una unidad de determinación de matriz inicial operativa
para elegir provisionalmente una matriz inicial, y una unidad de
cambio operativa para convertir un elemento de matriz de la matriz
inicial elegida por la unidad de determinación de matriz inicial en
las matrices n-dimensionales basándose en el entero
de entrada, es posible obtener la matriz
n-dimensional basándose en el entero (p. ej., el
valor de salida de la función resumen) sin necesidad de utilizar
una cantidad tan elevada de memoria. Puede generarse, por
consiguiente, una matriz n-dimensional que conserva
el equilibrio gracias a la distribución uniforme de los valores
enteros obtenida mediante la función resumen.
Asimismo, a través del dispositivo de salida de
matriz numérica de la presente invención, en el que la unidad de
cambio incluye una unidad de división operativa para dividir el
entero de entrada por un entero concreto y generar un resto, y una
unidad de sustitución operativa para sustituir el elemento de matriz
de la matriz inicial basándose en el resto generado por la unidad
de división, es posible obtener la matriz
n-dimensional bien equilibrada basándose en los
valores enteros distribuidos uniformemente por las funciones
resumen, etc. sin necesidad de utilizar una cantidad tan elevada de
memoria.
Además, con el dispositivo de salida de matriz
numérica, en el que la unidad de cambio incluye una unidad de
división operativa para dividir el entero de entrada por un entero
específico y generar un resto, y una unidad de asignación de
enteros operativa para sustituir por el entero P1 el elemento de
matriz que está situado en una posición basada en el resto generado
por la unidad de división entre el elemento de matriz del entero P3
de la matriz inicial, puede obtenerse la matriz
n-dimensional que sigue conservando el equilibrio
basado en los valores enteros distribuidos uniformemente por la
función resumen sin necesidad de utilizar una cantidad tan elevada
de memoria.
Asimismo, el dispositivo de encriptación de la
presente invención que encripta un mensaje y que comprende: una
unidad de salida de valores de función operativa para calcular el
mensaje con una función de conversión de un sentido y generar el
resultado como un valor de función; una unidad de salida de matriz
numérica que incluye una unidad de determinación de matriz inicial
que elige provisionalmente una matriz inicial y una unidad de
cambio que convierte un elemento de la matriz inicial elegida por la
unidad de determinación de matriz inicial en una matriz
n-dimensional basada en el valor de función generado
por la unidad de salida de valores de función, y que es operativa
para generar diversas matrices n-dimensionales que
constan de n enteros de valor K, cada uno de los cuales es uno de
los K tipos de enteros posibles, dependiendo del valor de función;
y una unidad de generación de texto de encriptación operativa para
generar un texto de encriptación basándose en la matriz generada
por la unidad de salida de matriz numérica, permite obtener una
matriz n-dimensional bien equilibrada, basándose en
los enteros distribuidos uniformemente por la función de un sentido
(p. ej., el valor de función resumen de un mensaje), y aumentar de
ese modo el nivel de seguridad del texto de encriptación.
Claims (11)
1. Dispositivo de encriptación (10) para
encriptar un mensaje, que comprende:
una unidad de salida de valores de función (40)
que puede funcionar para calcular un valor de función del mensaje
utilizando una función de conversión de un sentido;
caracterizado porque presenta un
dispositivo de salida de matriz numérica (100) que puede funcionar
para generar un vector de n elementos dependiendo del valor de
función que se utiliza como entero de entrada mayor o igual a 0, en
el que cada uno de los n elementos seleccionado es uno de los K
valores de entero predeterminados diferentes, comprendiendo dicho
dispositivo de salida de matriz numérica (100):
una unidad de determinación de matriz inicial
(110) que puede utilizarse para elegir un vector de n elementos como
vector inicial, y una unidad de cambio adaptada para recibir el
valor de función como entrada y operativa para cambiar un elemento
del vector inicial elegido por la unidad de determinación de matriz
inicial, incluyendo dicha unidad de cambio:
una unidad de división que puede funcionar para
dividir primero el valor de función por un entero positivo
específico c que es menor o igual a n, y generar un resto, y a
continuación dividir repetidamente el cociente obtenido mediante la
división por el entero específico c, reduciendo al mismo tiempo del
entero específico c en una unidad por cada división, empezando por n
y acabando por 2, y generar restos y
una unidad de sustitución (120) adaptada para
sustituir repetidamente el c-ésimo elemento del vector inicial por
un elemento del vector inicial situado en una posición
correspondiente a cada uno de los restos generados repetidamente por
la unidad de división;
una unidad de generación de texto de
encriptación (50) operativa para generar un texto de encriptación
del mensaje, utilizando el polinomio correspondiente al vector de n
elementos generado por el dispositivo de salida de matriz numérica
(100).
2. Dispositivo de encriptación según la
reivindicación 1, en el que:
los K valores enteros predeterminados diferentes
son P_{1}, P_{2, ...,} P_{K},
el dispositivo de salida de matriz numérica
genera un vector de n elementos, en el que cada uno de los n_{1}
elementos es un entero P_{1}, cada uno de los n_{2} elementos es
un entero P_{2},..., y cada uno de los n_{K} elementos es un
entero P_{K}, siendo n = n_{1} + n_{2} +...+ n_{K},
la unidad de determinación de matriz inicial
(110) elige, como vector inicial, un vector predeterminado en el que
cada uno de los elementos n_{1} es un entero P_{1}, cada uno de
los elementos n_{2} es un elemento P_{2}, ..., y cada uno de los
n_{K} elementos es un entero P_{K} y
la unidad de sustitución (120) sustituye el
elemento del vector inicial por un elemento del vector inicial que
está situado en una posición correspondiente al resto.
3. Dispositivo de encriptación según la
reivindicación 2, en el que la unidad de división realiza la
división restando del entero específico de entrada un valor que se
determina de conformidad con el número de veces que se repite la
división, y repite la división, y
la unidad de sustitución (120) realiza la
sustitución para cada uno de los restos generados repetidamente por
la unidad de división de la siguiente manera, sólo en el caso en el
que cada uno de los restos sea mayor o igual al valor que se
determina de conformidad con el número de veces que se repite la
división: se sustituye el elemento P_{1} del vector inicial por el
entero P_{2} un número n_{2} de veces, ..., y, se sustituye el
elemento P_{1} del vector inicial por el entero P_{K} un número
n_{k} de veces, estando situado el elemento de vector P_{1} en
una posición que se determina de conformidad con el resto.
4. Dispositivo de encriptación (10) para
encriptar un mensaje, que comprende:
una unidad de salida de valores de función (40)
que puede funcionar para calcular un valor de función del mensaje
utilizando una función de conversión de un sentido;
caracterizado porque un dispositivo de
salida de matriz numérica (100) que puede funcionar para generar un
vector de n elementos dependiendo del valor de función que se
utiliza como entero de entrada mayor o igual a 0, en el que cada uno
de los n elementos seleccionado es uno de los K valores de entero
predeterminados diferentes, comprendiendo dicho dispositivo de
salida de matriz numérica (100):
\newpage
una unidad de determinación de matriz inicial
(110) que puede funcionar para elegir un vector de n elementos como
vector inicial, y
una unidad de cambio adaptada para recibir el
valor de función como entrada y que puede funcionar para cambiar un
elemento del vector inicial elegido por la unidad de determinación
de matriz inicial, incluyendo dicha unidad de cambio:
una unidad de separación que puede funcionar
para separar el entero en enteros separados, cada uno de los cuales
se compone de un número de bits específico,
una unidad de división que puede funcionar para
dividir primero el valor de función por un entero positivo
específico que es menor o igual a n, y generar un resto, a
continuación determinar repetidamente los restos incrementando en
una unidad cada uno de los enteros separados obtenidos por la unidad
de separación, y finalmente dividir cada uno de los enteros
separados resultantes por el entero específico y
una unidad de sustitución para sustituir por lo
menos un elemento del vector inicial por uno de los K valores de
entero predeterminados diferentes, estando situado el elemento del
vector en una posición que se determina de conformidad con por lo
menos uno de los enteros separados obtenidos por la unidad de
separación y los restos obtenidos por la unidad de división;
una unidad de generación de texto de
encriptación (50) que puede funcionar para generar un texto de
encriptación del mensaje, utilizando el polinomio correspondiente al
vector de n elementos generados por el dispositivo de salida de
matriz numérica (100).
5. Dispositivo de encriptación según la
reivindicación 4, en el que:
los K valores de entero predeterminados
diferentes son P_{1}, P_{2}, ..., y P_{k},
el dispositivo de salida de matriz numérica
(100) genera un vector de n elementos, en el que cada uno de los
n_{1} elementos es un entero P_{1,} cada uno de los elementos
n_{2} es un entero P_{2}, y cada uno de los elementos n_{K} es
un entero P_{K}, siendo n = n_{1}+n_{2}+...+n_{K},
la unidad de determinación de matriz inicial
(110) elige, como vector inicial, un vector en el que cada no de los
n elementos es un entero P_{1} y
la unidad de sustitución (120) sustituye el
elemento P_{1} del vector inicial por uno de los enteros P_{2},
...., P_{K}, estando situado el elemento de vector P_{1} en una
posición correspondiente al resto.
6. Dispositivo de encriptación según la
reivindicación 5, en el que:
la unidad de división divide repetidamente un
cociente por el entero específico un número n de veces y genera
restos, siendo el cociente obtenido mediante la división y
la unidad de sustitución (120) realiza la
sustitución para cada uno de los restos generados repetidamente
mediante la unidad de división, de la siguiente manera: se sustituye
el elemento P_{1} del vector inicial por el entero P2 un número
n_{2} de veces, y se sustituye el elemento P_{1} del vector
inicial por el entero P_{K} un número n_{K} de veces, estando
situado el elemento de vector P_{1} en una posición que se
determina dependiendo del resto.
7. Dispositivo de encriptación según la
reivindicación 4, en el que:
la unidad de cambio genera un valor acumulado
sumando repetidamente, de uno en uno, los enteros separados
obtenidos por la unidad de separación, la unidad de división
determina los restos incrementando repetidamente el valor acumulado
en una unidad y, a continuación, dividiendo el valor acumulado
resultante por el entero específico y
la unidad de sustitución realiza la sustitución
para cada uno de los nuevos valores acumulados de la manera
siguiente: se sustituye el elemento P_{1} del vector inicial por
el entero P_{2} un número n_{2} de veces,... y se sustituye el
elemento P_{1} del vector inicial por el entero P_{K} un número
n_{K} de veces, estando situado el elemento de vector P_{1} en
una posición que se determina dependiendo de uno de los nuevos
valores acumulados y cada uno de los restos obtenidos por la unidad
de división.
8. Dispositivo de encriptación según la
reivindicación 1 ó 4, en el que K es 3 y los K valores de enteros
predeterminados diferentes son 1, -1 y 0.
9. Producto de programa informático para un
dispositivo de encriptación que encripta un mensaje, haciendo el
producto de programa informático que un ordenador, cuando el
producto se ejecuta en un ordenador, ejecute las funciones de las
unidades del dispositivo de encriptación (10) según las
reivindicaciones 1 ó 4.
\newpage
10. Dispositivo de desencriptación (15) que
desencripta un texto encriptado según la reivindicación 1 y genera
un mensaje original, que comprende:
una unidad de desencriptación (25) que puede
funcionar para desencriptar el texto encriptado y generar un valor
desencriptado correspondiente al mensaje original;
una unidad de salida de valores de función (45)
que puede funcionar para calcular un valor de función del valor
desencriptado generado por la unidad de desencriptación (25)
utilizando una función de conversión de un sentido;
un dispositivo de salida de matriz numérica
(100) que puede funcionar para generar un vector de n elementos
dependiendo del valor de función que es utilizado como entero de
entrada que es mayor o igual a 0, siendo cada uno de los n elementos
seleccionados uno de los K valores enteros predeterminados
diferentes, comprendiendo dicho dispositivo de salida de matriz
numérica (100):
una unidad de determinación de matriz inicial
(110) que puede funcionar para determinar un vector de n elementos
como vector inicial, y
una unidad de cambio adaptada para recibir el
valor de función como entrada y que puede funcionar para cambiar un
elemento del vector inicial determinado por la unidad de
determinación de matriz inicial, incluyendo dicha unidad de
cambio:
una unidad de división que puede funcionar para
dividir primero el valor de función por un entero positivo
especifico c que es menor o igual a n, y generar un resto, a
continuación dividir repetidamente el cociente obtenido mediante la
división por el entero específico c, mientras se reduce el entero
específico c en una unidad por cada división empezando por n y
terminando por 2, y finalmente generar restos, y
la unidad de sustitución (120) adaptada para
sustituir repetidamente el c-ésimo elemento del vector inicial por
un elemento del vector inicial situado en una posición
correspondiente a cada uno de los restos generados repetidamente por
la unidad de división;
una unidad de generación de texto de prueba
específica (55) que puede funcionar para generar un texto de prueba
específica encriptado utilizando el polinomio correspondiente al
vector de n elementos generado por el dispositivo de salida de
matriz numérica (105) y
una unidad de salida (65) operativa para decidir
si el texto de encriptación es coherente con el texto de prueba
específica, y generar el mensaje original tras aplicar un
procedimiento específico al valor desencriptado generado por la
unidad de desencriptación (25), en el caso en el que el texto
encriptado sea coherente con el texto de prueba específico.
11. Dispositivo de desencriptación (15) que
desencripta un texto encriptado según la reivindicación 4 y genera
un mensaje original, que comprende:
una unidad de desencriptación (25) que puede
funcionar para desencriptar el texto encriptado y generar un valor
desencriptado correspondiente al mensaje original;
una unidad de salida de valores de función (45)
que puede funcionar para calcular un valor de función del valor
desencriptado generado por la unidad de desencriptación (25)
utilizando una función de conversión de un sentido;
un dispositivo de salida de matriz numérica
(100) que puede funcionar para generar un vector de n elementos
dependiendo del valor de función que es utilizado como entero de
entrada mayor o igual a 0, siendo cada uno de los n elementos
seleccionados uno de los K valores enteros predeterminados
diferentes, comprendiendo dicho dispositivo de salida de matriz
numérica (100):
una unidad de determinación de matriz inicial
(110) que puede funcionar para elegir un vector de n elementos como
vector inicial, y
una unidad de cambio adaptada para recibir el
valor de función como entrada y operativa para cambiar un elemento
del vector inicial elegido por la unidad de determinación de matriz
inicial, incluyendo dicha unidad de cambio:
una unidad de separación que puede funcionar
para separar el entero de entrada en enteros separados, cada uno de
los cuales se compone de un número de bits específico,
una unidad de división que puede funcionar para
dividir primero el valor de función por un entero positivo
especifico que es menor o igual a n, y generar un resto, a
continuación determinar repetidamente los restos incrementando en
una unidad cada uno de los enteros separados obtenidos por la unidad
de separación, y a continuación dividiendo cada uno de los enteros
separados resultantes por el entero específico y
\newpage
una unidad de sustitución que puede funcionar
para sustituir por lo menos un elemento del vector inicial por uno
de los K valores de entero predeterminados diferentes, estando
situado el elemento de vector en una posición determinada de
conformidad con por lo menos uno de los enteros separados obtenidos
por la unidad de separación y los restos obtenidos por la unidad de
división,
una unidad de generación de texto de prueba
específica (55) operativa para generar un texto de prueba específica
encriptado utilizando el polinomio correspondiente al vector de n
elementos generado a partir del dispositivo de salida de matriz
numérica (105) y
una unidad de salida (65) operativa para decidir
si el texto encriptado es coherente con el texto de prueba
específica, y generar el mensaje original tras aplicar un
procedimiento específico al valor de desencriptación generado por la
unidad de desencriptación (25), en el caso en el que el texto
encriptado sea coherente con el texto de prueba específica.
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2001-321651 | 2001-10-19 | ||
| JP2001321651 | 2001-10-19 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| ES2296862T3 true ES2296862T3 (es) | 2008-05-01 |
Family
ID=19138836
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| ES02022986T Expired - Lifetime ES2296862T3 (es) | 2001-10-19 | 2002-10-15 | Dispositivo de salida de matriz numerica, procedimiento de salida de matriz numerica, dispositivo de encriptacion y dispositivo de desencriptacion. |
Country Status (5)
| Country | Link |
|---|---|
| US (1) | US7233662B2 (es) |
| EP (3) | EP2148463A3 (es) |
| DE (1) | DE60223888T2 (es) |
| ES (1) | ES2296862T3 (es) |
| NO (1) | NO326812B1 (es) |
Families Citing this family (10)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US7190791B2 (en) * | 2002-11-20 | 2007-03-13 | Stephen Laurence Boren | Method of encryption using multi-key process to create a variable-length key |
| EP1914925A1 (en) * | 2003-04-24 | 2008-04-23 | Matsushita Electric Industrial Co., Ltd. | Apparatus to generate parameter, for NTRU, NTRU decryption and encryption system, apparatus, method and program implementing said parameter generating unit |
| FR2861235B1 (fr) * | 2003-10-17 | 2005-12-16 | Sagem | Procede de protection d'un algorithme cryptographique |
| WO2005098796A1 (ja) | 2004-03-31 | 2005-10-20 | Nec Corporation | 暗号方式の安全性を保証するパディング適用方法 |
| US7835978B2 (en) * | 2005-12-23 | 2010-11-16 | International Business Machines Corporation | Method and system for linking an anonymous electronic trade order to an identity of a trader |
| US7668852B2 (en) * | 2006-10-31 | 2010-02-23 | Hewlett-Packard Development Company, L.P. | Method for creating sketches of sets to permit comparison |
| US11068982B2 (en) * | 2017-03-21 | 2021-07-20 | Tora Holdings, Inc. | Systems and methods to securely match orders by distributing data and processing across multiple segregated computation nodes |
| US10454681B1 (en) | 2017-11-17 | 2019-10-22 | ISARA Corporation | Multi-use key encapsulation processes |
| US10031795B1 (en) * | 2017-12-22 | 2018-07-24 | ISARA Corporation | Using conversion schemes in public key cryptosystems |
| US10061636B1 (en) * | 2017-12-22 | 2018-08-28 | ISARA Corporation | Conversion schemes for public key cryptosystems |
Family Cites Families (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5142579A (en) * | 1991-01-29 | 1992-08-25 | Anderson Walter M | Public key cryptographic system and method |
| DE69737097T2 (de) * | 1996-08-19 | 2007-07-12 | Ntru Cryptosystems, Inc. | Kryptographisches verfahren und vorrichtung mit öffentlichem schlüssel |
| KR20010002708A (ko) * | 1999-06-17 | 2001-01-15 | 김동균 | 이진 정보 보호 전송방법 |
| GB0013399D0 (en) * | 2000-06-01 | 2000-07-26 | Tao Group Ltd | Decryption of cipher polynomials |
-
2002
- 2002-10-15 ES ES02022986T patent/ES2296862T3/es not_active Expired - Lifetime
- 2002-10-15 EP EP20090174508 patent/EP2148463A3/en not_active Withdrawn
- 2002-10-15 EP EP20070012355 patent/EP1841123A1/en not_active Withdrawn
- 2002-10-15 EP EP02022986A patent/EP1304829B1/en not_active Expired - Lifetime
- 2002-10-15 DE DE60223888T patent/DE60223888T2/de not_active Expired - Lifetime
- 2002-10-16 US US10/270,596 patent/US7233662B2/en not_active Expired - Lifetime
- 2002-10-18 NO NO20025013A patent/NO326812B1/no not_active IP Right Cessation
Also Published As
| Publication number | Publication date |
|---|---|
| EP1304829B1 (en) | 2007-12-05 |
| US7233662B2 (en) | 2007-06-19 |
| EP1841123A1 (en) | 2007-10-03 |
| EP2148463A3 (en) | 2015-04-22 |
| DE60223888D1 (de) | 2008-01-17 |
| NO20025013L (no) | 2003-04-22 |
| EP1304829A3 (en) | 2004-06-09 |
| NO326812B1 (no) | 2009-02-23 |
| EP1304829A2 (en) | 2003-04-23 |
| EP2148463A2 (en) | 2010-01-27 |
| NO20025013D0 (no) | 2002-10-18 |
| US20030081770A1 (en) | 2003-05-01 |
| DE60223888T2 (de) | 2008-11-13 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| EP3913850A1 (en) | Key management method and related device | |
| JP5491638B2 (ja) | 代理計算システム、計算装置、能力提供装置、代理計算方法、能力提供方法、プログラム、及び記録媒体 | |
| GB2538022A (en) | Multiple secrets in quorum based data processing | |
| US20060083370A1 (en) | RSA with personalized secret | |
| JP5562284B2 (ja) | 再暗号化システム、再暗号化装置、能力提供装置、再暗号化方法、能力提供方法、及びプログラム | |
| ES2296862T3 (es) | Dispositivo de salida de matriz numerica, procedimiento de salida de matriz numerica, dispositivo de encriptacion y dispositivo de desencriptacion. | |
| Newman et al. | Public key management for network security | |
| CN109923829B (zh) | 对秘密值达成一致 | |
| JP5596616B2 (ja) | 情報提供システム、仲介装置、仲介方法、情報提供方法、及びプログラム | |
| JP7783643B2 (ja) | 複数のサブネットを有する分散ネットワーク | |
| JP2017126970A (ja) | 共有鍵生成プログラム、共有鍵生成方法および情報処理端末 | |
| WO2016073056A2 (en) | Method and apparatus for computing over cocks ciphertexts | |
| JP4208230B2 (ja) | 配列出力装置、配列出力方法、暗号化装置、および復号化装置 | |
| RU2417410C2 (ru) | Способ хранения и использования криптографического ключа | |
| Koo et al. | Key Reduction in Multi-Key and Threshold Multi-Key Homomorphic Encryptions by Reusing Error | |
| CN118592008A (zh) | 生成共享私钥 | |
| Manajaih | Modular arithmetic in RSA cryptography | |
| JP5929757B2 (ja) | 暗号処理装置および暗号処理方法 | |
| JP5964759B2 (ja) | 計算システム | |
| Chang et al. | Novel Encryption Scheme Based on Continued Fraction and Permutation | |
| Muyinda | Elliptic curve cryptography | |
| HK40092956A (en) | Distributed networks having a plurality of subnets | |
| HK40092956B (en) | Distributed networks having a plurality of subnets | |
| CN118972037A (zh) | 支持门限的多方安全计算方法、逻辑电路和计算设备 | |
| Yurchenko et al. | A Secure SDN Framework Based on Ultra-Low Power Microcontrollers |