ES2203612T3 - Metodo para ejecucion de protocolos criptograficos de teoria de numeros y/o de correccion de error. - Google Patents
Metodo para ejecucion de protocolos criptograficos de teoria de numeros y/o de correccion de error.Info
- Publication number
- ES2203612T3 ES2203612T3 ES93110069T ES93110069T ES2203612T3 ES 2203612 T3 ES2203612 T3 ES 2203612T3 ES 93110069 T ES93110069 T ES 93110069T ES 93110069 T ES93110069 T ES 93110069T ES 2203612 T3 ES2203612 T3 ES 2203612T3
- Authority
- ES
- Spain
- Prior art keywords
- mod
- calculating
- vartheta
- checking
- verifying device
- 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
- 238000000034 method Methods 0.000 title claims abstract description 36
- 238000012937 correction Methods 0.000 title claims description 5
- 230000003071 parasitic effect Effects 0.000 claims description 7
- 238000012795 verification Methods 0.000 claims description 6
- 230000015654 memory Effects 0.000 claims description 5
- 230000006870 function Effects 0.000 claims description 3
- 230000008901 benefit Effects 0.000 abstract description 3
- 238000004364 calculation method Methods 0.000 description 6
- 238000012986 modification Methods 0.000 description 4
- 230000004048 modification Effects 0.000 description 4
- 244000045947 parasite Species 0.000 description 4
- 230000008569 process Effects 0.000 description 4
- 230000009467 reduction Effects 0.000 description 3
- 238000013461 design Methods 0.000 description 2
- 230000004075 alteration Effects 0.000 description 1
- 238000013459 approach Methods 0.000 description 1
- 230000005540 biological transmission Effects 0.000 description 1
- 230000001419 dependent effect Effects 0.000 description 1
- 230000000694 effects Effects 0.000 description 1
- 230000006886 spatial memory Effects 0.000 description 1
- 238000012360 testing method Methods 0.000 description 1
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/32—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols including means for verifying the identity or authority of a user of the system or for message authentication, e.g. authorization, entity authentication, data integrity or data verification, non-repudiation, key authentication or verification of credentials
- H04L9/3218—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols including means for verifying the identity or authority of a user of the system or for message authentication, e.g. authorization, entity authentication, data integrity or data verification, non-repudiation, key authentication or verification of credentials using proof of knowledge, e.g. Fiat-Shamir, GQ, Schnorr, ornon-interactive zero-knowledge proofs
-
- 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/32—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols including means for verifying the identity or authority of a user of the system or for message authentication, e.g. authorization, entity authentication, data integrity or data verification, non-repudiation, key authentication or verification of credentials
- H04L9/3247—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols including means for verifying the identity or authority of a user of the system or for message authentication, e.g. authorization, entity authentication, data integrity or data verification, non-repudiation, key authentication or verification of credentials involving digital signatures
Landscapes
- Engineering & Computer Science (AREA)
- Computer Security & Cryptography (AREA)
- Computer Networks & Wireless Communication (AREA)
- Signal Processing (AREA)
- Storage Device Security (AREA)
Abstract
SE CONOCEN DIFERENTES METODOS PARA CONTROL DE ACCESO, SIGNATURA DIGITAL E IDENTIFICACION QUE UTILIZAN MULTIPLICACIONES MODULARES. SE PRESENTA UN PROTOCOLO QUE PUEDE SER EJECUTADO AL MISMO TIEMPO COMO UN ESQUEMA FIAT-SHAMIR DONDE TODAS AS MULTIPLICACIONES MODULARES SON SUSTITUIDAS POR MULTIPLICACIONES ESTANDARES. LA VENTAJA DEL NUEVO METODO SOBRE EL PROTOCOLO CLASICO FIAT-SHAMIR ES QUE LOS CALCULO SON HECHOS MUCHO MAS RAPIDAMENTE.
Description
Método para ejecutar protocolos criptográficos de
teoría de números y/o de corrección de errores.
La presente inveción se refiere a un método para
ejecutar protocolos criptográficos de teoría números y/o de
corrección de errores.
El algoritmo de Montgomery descrito en "Modular
Multiplication without Trial Division", Mathematics of
Computation, Vol. 44, pp.519-521, es un proceso para
calcular A*B*2^{-|n|} módulo n en memoria espacial
O(Log(n)) (0: orden).
En Fiat, Feige y Shamir,
"Zero-Knowledge Proofs of Identity", Journal of
Cryptology, vol. 1, pp. 77-94, se describe un
esquema de autentificación (Fiat-Shamir).
Ver también, los documentos
EP-A-0252499 y
EP-A-0325238.
Un objeto de la presente invención es describir
un método de construcción de un esquema de autentificación similar a
Fiat-Shamir adecuado para los entornos de Montgomery
sin introducir ninguna cabecera en el número de multiplicaciones
modulares solicitadas para la ejecución del protocolo normal. Este
objeto se alcanza por el método descrito en la reivindicación 1.
Un resultado muy reciente descrito en Arazi,
"Modular Multiplication is Equivalent in Complexity to a Standard
Multiplication", Fortress U&T Internal Report (1992),
Fortress U&T Information Safeguards, P.O. Box. 1350,
Beer-Sheva, IL-84110, Israel,
establece (de modo implícito) que A*B*2^{-|n|} mod n puede
calcularse con la misma complejidad (en cuanto a tiempo y hardware)
que A*B (no mod n).
Esta reducción teórica del problema de
multiplicación modular, aplicada recientemente al diseño del
multiplicador modular de hardware más rápido actualmente, es muy
importante, puesto que implica que el protocolo presentado de aquí
en adelante puede ejecutarse al mismo tiempo como un esquema
Fiat-Shamir, donde todas las multiplicaciones
modulares son substituidas por multiplicaciones estándar.
El hecho de no tener que precalcularse constantes
de antemano, y la pequeña cantidad de RAM requerida para la
ejecución del software del nuevo protocolo hace muy conveniente
aplicaciones de tarjeta inteligente, por ejemplo, en sistemas de TV
de pago.
La ventaja del nuevo método sobre el protocolo
Fiat-Shamir convencional es que los cálculos se
realizan de una manera mucho más rápida. Además, puede aplicarse la
misma filosofía con el fin de transformar o adaptar otros esquemas
de teoría de números para ejecución rápida.
A lo largo de toda esta solicitud, |n| designa la
longitud de n (en bits), y ||n|| el peso Hamming de n.
En el algoritmo de Montgomery para multiplicación
modular mencionado anteriormente, se supone que n es par. No se
imponen otras limitaciones respecto del módulo.
Mucho más simplificado, este algoritmo
"Kernel" funciona de la siguiente manera:
Supongamos X[i] designa los X i^{ésimo}
bit (con X[0] como LSB) y K = 4^{|n|} mod n.
A partir de la referencia Montgomery citada
anteriormente puede demostrarse que c = A*B*2^{-|n|} mod n y
que:
Kernel (K, Kernel (A, B)) = A*B mod n.
Una aproximación más amplia y completa es
presentada por Arazi mencionado anteriormente, donde se demuestra
formalmente cómo puede reducirse la complejidad del cálculo Kernel
(A, B) de A*B.
Si fuera posible transformar el esquema de
Fiat-Shamir de tal modo que los parásitos de
Montgomery (2^{-|n|}) no alteraran el protocolo (utilizando
solamente una operación Kernel en lugar de cada multiplicación
modular), entonces sería posible realizar el esquema de
Fiat-Shamir aproximadamente en la mitad del tiempo
requerido con un multiplicador de Montgomery completo.
Además, no sería necesario el precálculo o el uso
de la constante K del método de Montgomery.
Este método para solución del problema es
bastante nuevo, puesto que por contraposición al proceso
convencional de diseño de herramientas de cálculo para ejecución
cómoda de protocolos de teoría de números, se transforma aquí un
esquema criptográfico con el fin de cumplir una limitación de
cálculo dada.
De manera ventajosa, después de una adecuada
modificación de la relación entre las claves públicas y privadas,
pueden utilizarse los parásitos de Montgomery útiles en lugar de
producir alteración.
Desde ahora, D designará el factor parásito 2-|n|
mod n y se presupone la disponibilidad de un
semi-multiplicador de Montgomery (que es un
procedimiento Kernel que realiza solamente la operación A*B*D mod
n).
La clave pública de Fiat-Shamir
v_{j}-s se define de nuevo por:
D^{3}*v_{j}*s^{2}_{j} \equiv 1 mod n.
Se supone que los v_{j} son ya conocidos por el
verificador (por ejemplo por el método de Fiat y Shamir
F(ID/j).
Paso
1
Un dispositivo de comprobación toma un número
aleatorio R y calcula Z = R^{2}D mod n = Kernel (R, R) y lo envía
a un dispositivo verificador.
Paso
2
El dispositivo verificador envía el vector
binario aleatorio e hasta el dispositivo de comprobación.
Paso
3
El dispositivo de comprobación calcula y envía al
dispositivo verificador:
y = r \pi si D^{||e||} mod n.
\hskip0,3cme_{i}=1
Este valor es calculado fácilmente por:
y=Kernel(s_{i1}, Kernel (s_{i2},...
Kernel(S_{i||e||}, r))...).
Aquí, ij designan los índices ||e|| seleccionados
por el vector e.
Paso
4
El dispositivo verificador calcula (de un modo
similar al del paso previo):
A = Kernel(v_{i1}, ...
Kernel(v_{i2}, .. Kernel(v_{i}^{||e||},
Kernel(y, y)))...)
= y^{2} D \pi v_{i}D^{||e||-1}D mod n
\hskip0,3cme_{i}=1
= r^{2} \pi v_{i}s_{i} ^{2}D^{2}
^{||e||} D^{||e||}D mod n.
\hskip0,3cme_{i}=1
= r^{2} \pi v_{j}s_{j} ^{2}D^{3}
^{||e||}D mod n = r^{2}D mod n
\hskip0,3cme_{i}=1
y comprueba si A = Z.
El dispositivo de comprobación puede ser una
tarjeta inteligente que comprende un microprocesador y medios RAM
que almacena en medios de memoria no volátil, las claves secretas si
y el módulo n, por lo que con la tarjeta inteligente conectada a un
lector de tarjeta inteligente para un decodificador de TV de pago
que comprende el dispositivo verificador que evalúa la clave pública
v se almacena también el módulo n en los medios de memoria.
En principio, el método de la invención consiste
en calcular protocolos criptográficos de teoría de números y/o de
corrección de errores, utilizando un dispositivo de comprobación que
almacena en medios de memoria claves secretas s_{i} y un módulo n,
y un dispositivo verificador que evalúa un conjunto de claves
públicas v_{i}, por lo que la relación entre las claves públicas
v_{j} y las claves secretas s_{j}, se modifica de tal manera que
se saldan o cancelan los parásitos inducidos al utilizar un método
modular similar a Montgomery.
Más específicamente, la relación entre las claves
públicas y las claves secretas se modifica frente a la relación
entre dichos protocolos originales introduciendo en dicha relación
dependencia sobre el factor parásito constante de Montgomery.
Las formas de realización adicionales ventajosas
del método de la invención resultarán de las reivindicaciones
dependientes respectivas.
De manera similar, la invención puede aplicarse
también al método de firma digital de
Fiat-Shamir.
En Quisquater and Guillou, "A Practical
Zero-Knowledge Protocol Fitted to Security
Microprocessor Minimizing Both Transmision and Memory",
Proceedings of Eurocrypt'88 Lecture Notes in Computer Science,
Springer-Verlag (Ed. C.G. Günter) 330 (1988),
páginas 123-128, se describe un esquema de
autentificación muy popular. El esquema de identificación
Quisquater-Guillou original es el siguiente:
La relación básica entre la clave secreta B y una
identidad de usuario ID (dispositivo de comprobación) es:
f(ID)*B^{v} = 1 mod n. Otra denominación abreviada para
f(ID) es J. El parámetro v es decidido por la autoridad.
Paso
1
El dispositivo de comprobación toma un número
aleatorio r y envía su ID y T = r^{v} mod n al dispositivo
verificador.
Paso
2
El dispositivo verificador toma un d<v
aleatorio, calcula J = f(ID) y envía d al dispositivo de
comprobación.
Paso
3
El dispositivo de comprobación calcula y envía U
= r*B^{d} mod n al dispositivo verificador.
Paso
4
El dispositivo verificador comprueba que T =
J^{d}U^{v} mod n.
Esta identidad debería cumplirse, puesto que:
J^{d}U^{v} = J^{d}
(r*B^{d})^{v}= (J*B^{v})^{d}r^{v} =
1^{d}r^{v} = r^{v} = T mod n.
Aplicando aquí el método de la invención, el
cálculo puede acelerarse utilizando un
semi-multiplicador de Montgomery (procesador). De
nuevo, se modifica la relación entre las claves públicas y privadas:
f(ID)*B^{v}D^{v}+1 = 1 mod n, pero exactamente se ejecuta
el mismo protocolo mientras se sustituyen las multiplicaciones por
operaciones Kernel:
Paso
1
El dispositivo de comprobación toma un número
aleatorio r y envía su ID y T = r^{v}D^{v-1} mod
n al dispositivo verificador. El factor D^{v-1} es
añadido por el algoritmo de exponenciación convencional de
"cuadrado y multiplicación", donde todas las multiplicaciones
son substituidas por procedimientos Kernel. De manera más precisa,
este algoritmo Kernel_Exponenciación es:
A partir de esto puede probarse fácilmente
que:
Kernel_Exponenciación(A, p) =
A^{p}D^{p-1}, mod n (T se obtiene por
Kernel_Exponenciación(r, v)).
Paso
2
El dispositivo verificador toma un número
aleatorio d<v, calcula
J=f(ID) y envía d al dispositivo de
comprobación.
Paso
3
El dispositivo de comprobación calcula y envía
U=r*B^{d}D^{d} mod n al dispositivo verificador.
U es calculado por:
Kernel(Kernel_Exponenciación (B, d), r)
Paso
4
El dispositivo verificador comprueba que T =
J^{d}U^{v}D^{d+v-1} mod n.
El valor
J^{d}U^{v}D^{d+v-1} es calculado por:
Kernel(Kernel_Exponenciación(J,d),
Kernel_Exponenciación (U, v)),
Esta comprobación debería ser verdadera puesto
que:
J^{d}U^{v}D^{d+v-1} =
J^{d}(r*B^{d}D^{d})^{v}D^{d+v-1}
= (J*B^{v})^{d}r^{v}D^{d*v+d+v-1}
=
D^{-d(v+1)}r^{v}D^{d(v+1)}D^{v-1}
= r^{v}D^{v-1} = T.
Schnorr, en "Efficient Identification and
Signatures for Smart Cards" Proceedings of Eurocrypt 89 Lecture
Notes in Computer Science, Springer-Verlag (Ed. G.
Brassard) 435 (1990), pp. 239-252, (ver también
EP-A-0384475) es un sistema en el
que la relación entre las claves pública (v) y secreta (s) es v =
\alpha^{-s} mod p.
\alpha es elegido por la autoridad de tal
manera que \alpha^{q} = 1 mod p. q es una clave pública
publicada por la autoridad.
Paso
1
El dispositivo de comprobación toma un número
aleatorio r, calcula x = \alpha^{r} mod p y envía x al
dispositivo verificador.
Paso
2
El dispositivo verificador toma un número
aleatorio e y lo envía al dispositivo de comprobación.
Paso
3
El dispositivo de comprobación envía otra vez y =
r+s*e mod q.
Paso
4
El dispositivo verificador ensaya que x =
\alpha^{y}v^{e} mod p.
El método de la invención puede aplicarse de
nuevo con el fin de acortar el tiempo de cálculo. La única
modificación a introducir está en la relación entre las claves
pública y secreta que es:
v*D^{s+1}\alphas = 1 mod p.
Paso
1
El dispositivo de comprobación toma un número
aleatorio r, calcula x = \alpha^{r}D^{r-1} mod
p y envía x al dispositivo verificador.
x = Kernel_Exponenciación(\alpha,
r).
Paso
2
El dispositivo verificador toma un número
aleatorio e y lo envía al dispositivo de comprobación.
Paso 3:
El dispositivo de comprobación envía otra vez y =
r+s*e mod q.
Paso
4
El dispositivo verificador comprueba que x=
\alpha^{y}v^{e} D^{y+e-1} mod p comprobando
que:
x=Kernel(Kernel_Exponenciación(\alpha,y),Kernel_Exponenciación
(v, e)).
Esta comprobación debería ser cierta puesto
que:
\alpha^{y}v^{e}D^{y+e-1}
= \alpha^{r+s*e}v^{e}D^{y+e-1} =
\alpha^{r+s*e}
(\alpha^{-s}D^{-(1+s)})^{e}D^{y+e-1}
=
\alpha^{r}D^{-(s+1)e}D^{r+s*e+e-1}
= \alpha^{r}D^{r-1} = x.
El esquema de firma descrito en El Gamal, "A
public-key cryptosystem and a signature scheme based
on the discrete logarithm", IEEE Transactions on Information
Theory, vol. 31, Nº 4, pp. 469.472, 1985, está basado en el problema
de logaritmo discreto.
La clave pública es definida como un entero p =
g^{s} mod q, donde s es la clave secreta del usuario y p, q y g
son públicas. Para firmar un mensaje m, el usuario toma un número
aleatorio k, calcula u = g^{k} mod q y calcula v de forma que m =
s*u+k*v mod (q-1), siendo {u, v} la firma del
mensaje m.
Después de la recepción, la validez de la firma
puede comprobarse puesto que p^{u}u^{v} = g^{s*u}g^{k*v} =
g^{s*u}g ^{m-s*u} = g^{m} mod q, estando m y g
disponibles.
\newpage
Con el fin de aprovechar el procedimiento
Kernel_Exponenciación de la invención, sin modificar el protocolo,
la clave pública acaba de ser redefinida como p =
g^{s}D^{s-1} mod q.
P puede calcularse fácilmente por
Kernel_Exponenciación(g, s).
Para firmar, el usuario tomará un número
aleatorio k y calculará u = g^{k}D^{k-1}mod q =
Kernel_Exponenciación (g, k), mientras que la definición de v
permanece igual (a saber: m = s*u+k*v mod
(q-1)).
Para comprobar la validez de la firma, el
receptor calculará:
Kernel(Kernel_Exponenciación(p,u),Kernel_Exponenciación
(u,v)) =
(p^{u}D^{u-1})(u^{v}D^{v-1})D
= (p^{u}D^{u-1})(u^{v}D^{v}) =
(p^{u}D^{u-1})(g^{k}D^{k-1})^{v}D^{v}
=
(p^{u}D^{u-1})(g^{k}D^{k})^{v}
= (p^{u}D^{u-1})(g*D)^{k*v} =
(p^{u}D^{u-1})(g*D)^{m-s*u}
=
(g^{s}D^{s-1})^{u}D^{u-1}g^{m-s*u}D^{m-s*u}
= g^{s*u}D^{s*u}
D^{-u}D^{u-1}g^{m-s*u}D^{m-s*u}
=
g^{m}D^{m-1} mod q, y se
comparará naturalmente este valor con el resultado de:
Kernel_Exponenciación(g, m).
La norma de firma digital (DSS) es una nueva
norma que se aplica para la firma de mensajes. Muy
simplificadamente, la DSS funciona de la siguiente manera:
Se seleccionan dos números primos p y q, y un
entero g. Se calcula y = g^{x} mod p, divulgándose p, q, g e y,
siendo x la clave privada del usuario.
El procedimiento para firmar el mensaje M es el
siguiente:
El dispositivo de firma calcula la clave del
mensaje M en una serie comprimida m.
El dispositivo de firma calcula r=(g^{k} mod p)
mod q y s=(m+x*r)/k mod q y envía la firma {r, s} al dispositivo
verificador.
El dispositivo verificador controlará la firma
comprobando que ((g^{m*sE(-1)mod q}y^{r*sE(-1)mod
q})mod p) mod q = r,
con sE(-1)=s^{-1}
Con el fin de adaptar este proceso al método de
la invención, solamente la relación entre las claves es modificada,
pero se distinguirán dos procesos diferentes:
Kernel_{q}(A, B) calculando
A*B*\vartheta mod q y
Kernel_{p} (A, B) calculando A*B*D mod p.
Aquí, el nuevo protocolo es: Definir de nuevo y =
g^{\vartheta x}D^{\vartheta x-1} mod p.
El dispositivo de firma calcula:
r1 = Kernel_Exponenciaciónp(g,
k)=g^{k}D^{k-1} mod p,
r = Kernel _{q}(r1, 1) =
(g^{k}D^{k-1} mod p)\vartheta mod q
y
s = Kernel _{q}(1/k, (m +
Kernel_{q}(x, r))) =
\vartheta(m+x*r*\vartheta)/k mod q
y envía la firma {r, s} al dispositivo
verificador.
El dispositivo verificador controlará la firma
calculando:
W = s^{s-1} mod q
u1 = Kernel_{q}(m, w) = m w \vartheta
mod q
u2 = Kernel_{q}(r, w) = r w \vartheta
mod q
v1 = Kernel_Exponenciación_{p}(q, u1) =
g^{u1}D^{u1-1} mod p
v2 = Kernel_Exponenciación_{p}(y, u2) =
y^{u2}D^{u2-1} mod p
v3 = Kernel_{p}(v1, v2) =
g^{u1}D^{u1-1}
y^{u2}D^{u2-1} D mod p =
g^{u1}y^{u2}D^{u1+u2-1} mod
p = g^{u1} (g^{\vartheta x}D^{\vartheta
x-1})^{u2}D^{u1+u2-1}
mod p =
g^{mw\vartheta } g^{\vartheta xrw \vartheta}
D^{\vartheta x(u2+u1-1)} mod p =
g^{w(m \vartheta +xr \vartheta\vartheta)} D^{\vartheta
x(u2+u1-1)} mod p = g^{k}D^{\vartheta
x(u2+u1-1)} mod p = D^{\vartheta xrw
\vartheta +mw \vartheta -1} g^{k} mod p =
g^{k}D^{k-1} mod p
v = Kernel_{q} (v3, 1) =
(g^{k}D^{k-1} mod p)\vartheta mod q
y comprobará que v = r.
Para r el firmante puede calcular también
r = (g^{k}D^{k-1} mod
p)C*\vartheta mod q
comprobando mediante el dispositivo verificador
que v3*\vartheta*C = r mod q,
donde C es una constante arbitraria.
Para r el firmante puede calcular también
r = (g^{k}D^{k-1} mod
p)*f(M)* \vartheta mod q
comprobando mediante el dispositivo verificador
que v3*\vartheta*f(M) = r mod q, donde f(M) es una
función pública del mensaje a firmar.
De manera ventajosa, sin coste extra (comparado
con el DSS original), la seguridad del esquema propuesto puede
mejorarse puesto que los pasos:
r = Kernel_{q}(r1, 1) (al calcular la
firma) y
v = Kernel_{q}(v3, 1) (al verificar la
firma)
pueden sustituirse respectivamente por:
r = Kernel_{q} (r1, f(m)) (cuando se
calcula la firma) y
v = Kernel_{q} (v3, f(m)) (cuando se
verifica la firma),
donde f designa cualquier función pública (por
ejemplo, |q| LBS bits de m).
Con un microprocesador tipo 68HC05 que funciona a
3,5 MHz, la operación Kernel (para números de 512 bit) fue ejecutado
en menos de 135 ms, la utilización de la RAM fue menor de 70 bytes.
Una versión Kernel-cuadrado funciona en 85 ms pero
requiere doble espacio de RAM.
En el artículo de Arazi citado anteriormente se
muestra que "Es posible calcular A*B*D mod n en |n| +1 ciclos de
reloj. Es decir, se realiza una multiplicación modular con la misma
complejidad (en cuanto a tiempo y a hardware) que la operación de
multiplicación estándar".
Por lo tanto, es posible ejecutar un control de
identidad Fiat-Shamir (y firma, con modificaciones
similares del esquema) con hardware y tiempo equivalentes a los
requeridos para ejecutar protocolos sin reducciones modulares.
La misma estrategia de modificación de la
relación entre las claves públicas y secretas con el fin de saldar o
cancelar el efecto de constantes parásitas introducidas por
herramientas de reducción modular puede aplicarse a una gran
variedad de protocolos de autentificación y de firma de teoría de
números.
La invención puede aplicarse también a bancos,
control de acceso o aplicaciones militares.
Claims (9)
1. Método para ejecutar protocolos criptográficos
de teoría de números y/o de corrección de error utilizando un
dispositivo de comprobación, por ejemplo, una tarjeta inteligente -
que almacena, en medios de memoria, una clave secreta y un módulo, y
un dispositivo verificador que evalúa las claves publicas,
caracterizado porque la relación entre las claves públicas
(v_{j}) y las claves secretas (s_{j}) se modifica respecto a la
relación entre dichas claves en dichos protocolos originales,
introduciendo en dicha relación dependencia respecto del factor
parásito constante de Montgomery.
2. Método de acuerdo con la reivindicación 1,
caracterizado porque para la firma digital y/o la
identificación se utiliza un protocolo
Fiat-Shamir:
- -
- substituyendo todas las operaciones de multiplicación por una operación Kernel que toma como entrada un par de números A y B, emitiendo el número A*B*D mod n, donde D es un factor parásito constante, siendo n un módulo Fiat-Shamir estándar;
- -
- substituyendo la relación entre las claves públicas y secretas por D^{3}v_{j}s_{j}^{2} \equiv 1 mod n.
3. Método de acuerdo con la reivindicación 1,
caracterizado porque para la firma digital y/o la
identificación se utiliza un protocolo
Quisquarter-Guillou:
- -
- substituyendo todas las operaciones de multiplicación modular por una operación Kernel tomando como entrada un par de números A y B y emitiendo el número A*B*D mod n, donde D es un factor parásito constante y n es un módulo Quisquater-Guillou;
- -
- substituyendo la relación entre las claves pública y secreta por f(ID) (B*D)^{v}D = 1 mod n.
4. Método de acuerdo con la reivindicación 1,
caracterizado porque para la firma digital y/o la
identificación se utiliza un protocolo Schnorr:
- -
- substituyendo todas las operaciones de multiplicación modular por una operación Kernel tomando con entrada un par de números A y B y emitiendo el número A*B*D mod n, donde D es un factor parásito constante y p es el módulo primo Schnorr estándar;
- -
- substituyendo la relación entre las claves pública y secreta por v*D^{s-1}\alphas = 1 mod p.
5. Método de acuerdo con la reivindicación 1,
caracterizado porque para la firma digital y/o la
identificación se utiliza un protocolo El-Gamal:
- -
- substituyendo todas las operaciones de multiplicación modular por una operación Kernel tomando como entrada un par de números A y B, emitiendo el número A*B*D mod n, donde D es un factor parásito constante y q es el módulo primo El-Gamal;
- -
- substituyendo la relación entre las claves pública y secreta por g^{s}D^{s-1} = 1 mod q;
- -
- substituyendo la definición de u por u = g^{k}D^{k-1} mod q.
6. Método de acuerdo con la reivindicación 1,
caracterizado porque se utiliza una norma de firma
digital:
- a)
- Calculando la clave mediante el dispositivo de comprobación de un mensaje M para firmar en una serie comprimida m;
- b)
- Calculando mediante el dispositivo de comprobación r = (g^{k}D^{k-1} mod p) mod q;
- c)
- Calculando mediante el dispositivo de comprobación s = \vartheta(m+x*r*\vartheta)/k mod q;
- d)
- Enviando la firma (r, s) desde el dispositivo de comprobación al dispositivo verificador;
- e)
- Calculando mediante el dispositivo verificador w = s^{-1} mod q;
- f)
- Calculando mediante el dispositivo verificador u1 = m w \vartheta mod q;
- g)
- Calculando mediante el dispositivo verificador u2 = r w \vartheta mod q;
- h)
- Calculando mediante el dispositivo verificador v1 = g^{u1}D^{u1-1} mod p;
- i)
- Calculando mediante el dispositivo verificador v2 = y^{u2}D^{u2-1} mod p;
- j)
- Calculando mediante el dispositivo verificador v3 = v1*v2+D mod p;
- k)
- Comprobando mediante el dispositivo verificador que v3 = r mod q.
7. Método de acuerdo con la reivindicación 1,
caracterizado porque se utiliza una norma de firma
digital:
- a)
- Calculando la clave mediante el dispositivo de comprobación un mensaje M para firmar en una serie comprimida m;
- b)
- Calculando mediante el dispositivo de comprobación r = (g^{k}D^{k-1} mod p) C* \vartheta mod q;
- c)
- Calculando mediante el dispositivo de comprobación s = \vartheta (m+x*r*\vartheta)/k mod q;
- d)
- Enviando la firma /r, S) desde el dispositivo de comprobación al dispositivo verificador;
- e)
- Calculando mediante el dispositivo verificador w = s^{-1} mod q;
- f)
- Calculando mediante el dispositivo verificador u1 = m w \vartheta mod q;
- g)
- Calculando mediante el dispositivo verificador u2 = r w \vartheta mod q;
- h)
- Calculando mediante el dispositivo verificador v1 = g^{u1}D^{u1-1} mod p;
- i)
- Calculando mediante el dispositivo verificador v2 = y^{u2}D^{u2-1} mod p;
- j)
- Calculando mediante el dispositivo verificador v3 = v1*v2+D mod p;
- k)
- Comprobando mediante el dispositivo verificador que v3*\vartheta*C = r mod q, donde C es una constante arbitraria.
8. Método de acuerdo con la reivindicación 1,
caracterizado porque se utiliza una norma de firma
digital:
- a)
- Calculando la clave mediante el dispositivo de comprobación un mensaje M para firmar en una serie comprimida m;
- b)
- Calculando mediante el dispositivo de comprobación r = (g^{k}D^{k-1} mod p)*f(M)*\vartheta mod q;
- c)
- Calculando mediante el dispositivo de comprobación s = \vartheta (m + x* r*\vartheta)/k mod q;
- d)
- Enviando la firma (r, s) desde el dispositivo de comprobación al dispositivo verificador;
- e)
- Calculando mediante el dispositivo verificador w = s^{-1} mod q;
- f)
- Calculando mediante el dispositivo verificador u1 = m w \vartheta mod q;
- g)
- Calculando mediante el dispositivo verificador u2 = r w \vartheta mod q;
- h)
- Calculando mediante el dispositivo verificador v1 = g^{u1}D^{u1-1} mod p;
- i)
- Calculando mediante el dispositivo verificador v2 = y^{u2}D^{u2-1} mod p;
- j)
- Calculando mediante el dispositivo verificador v3 = v1*v2+D mod p;
- k)
- Comprobando mediante el dispositivo verificador que v3*\vartheta*f(M) = r mod q, donde f(M) es una función pública del mensaje a firmar.
9. Método de acuerdo con cualquiera de las
reivindicaciones 1 a 8, caracterizado porque las operaciones
x = y^{potencia}D^{potencia-1} módulo N se
realizan por un procedimiento de exponenciación, cuya estructura
algorítmica es:
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| EP92401869 | 1992-06-30 | ||
| EP92401869 | 1992-06-30 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| ES2203612T3 true ES2203612T3 (es) | 2004-04-16 |
Family
ID=27675822
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| ES93110069T Expired - Lifetime ES2203612T3 (es) | 1992-06-30 | 1993-06-24 | Metodo para ejecucion de protocolos criptograficos de teoria de numeros y/o de correccion de error. |
Country Status (3)
| Country | Link |
|---|---|
| EP (1) | EP0578059B1 (es) |
| DE (1) | DE69333121T2 (es) |
| ES (1) | ES2203612T3 (es) |
Families Citing this family (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| DE69832535D1 (de) * | 1998-03-18 | 2005-12-29 | Kent Ridge Digital Labs Singap | Verfahren zum austausch digitaler daten |
| DE19820605A1 (de) | 1998-05-08 | 1999-11-11 | Giesecke & Devrient Gmbh | Verfahren zur sicheren Verteilung von Software |
| GB0228760D0 (en) * | 2002-12-10 | 2003-01-15 | Koninkl Philips Electronics Nv | Efficient implementation of zero knowledge protocols |
| FR2880149B1 (fr) | 2004-12-23 | 2007-03-30 | Oberthur Card Syst Sa | Procede de traitement de donnees et dispositif associe |
| KR101094339B1 (ko) | 2010-03-31 | 2011-12-19 | 고려대학교 산학협력단 | 오류주입 공격에 안전한 피아트 샤미르 개인 식별 장치, 방법 및 그 기록 매체 |
-
1993
- 1993-06-24 EP EP93110069A patent/EP0578059B1/en not_active Expired - Lifetime
- 1993-06-24 ES ES93110069T patent/ES2203612T3/es not_active Expired - Lifetime
- 1993-06-24 DE DE1993633121 patent/DE69333121T2/de not_active Expired - Fee Related
Also Published As
| Publication number | Publication date |
|---|---|
| EP0578059A1 (en) | 1994-01-12 |
| DE69333121D1 (de) | 2003-09-04 |
| DE69333121T2 (de) | 2004-04-15 |
| EP0578059B1 (en) | 2003-07-30 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| Guillou et al. | A practical zero-knowledge protocol fitted to security microprocessor minimizing both transmission and memory | |
| US5131039A (en) | Optionally moderated transaction systems | |
| Chan et al. | Easy come—easy go divisible cash | |
| Camenisch et al. | Digital payment systems with passive anonymity-revoking trustees | |
| Fiat et al. | How to prove yourself: Practical solutions to identification and signature problems | |
| US4969189A (en) | Authentication system and apparatus therefor | |
| Schnorr | Efficient signature generation by smart cards | |
| Okamoto | Provably secure and practical identification schemes and corresponding signature schemes | |
| Camenisch et al. | Compact e-cash | |
| US4935962A (en) | Method and system for authentication | |
| EP0522473B1 (en) | Cryptographic identity verification method | |
| Traoré | Group signatures and their relevance to privacy-protecting offline electronic cash systems | |
| Brands | Off-line electronic cash based on secret-key certificates | |
| EP0325238A2 (en) | Improved variants of the Fiat-Shamir identification and signature scheme | |
| Tsiounis | Efficient electronic cash: new notions and techniques | |
| EP0746923A4 (en) | EFFICIENT ELECTRONIC CURRENCY | |
| Beullens et al. | PKP-based signature scheme | |
| US6959085B1 (en) | Secure user identification based on ring homomorphisms | |
| US7228418B1 (en) | Authentication and signature method for messages using reduced size of binary units of information content and corresponding systems | |
| Pointcheval | The composite discrete logarithm and secure authentication | |
| Viswanathan et al. | A three phased schema for sealed bid auction system design | |
| US6148084A (en) | Restrictedly blindable certificates on secret keys | |
| JP4945026B2 (ja) | 減少した計算組を伴う認証または署名プロセス | |
| BÜTÜN et al. | A blind digital signature scheme using elliptic curve digital signature algorithm | |
| EP0578059B1 (en) | Method for executing number-theoretic cryptographic and/or error-correcting protocols |