ES2349725T3 - Procedimiento, dispositivo y sistema para verificar puntos determinados sobre una curva elíptica. - Google Patents
Procedimiento, dispositivo y sistema para verificar puntos determinados sobre una curva elíptica. Download PDFInfo
- Publication number
- ES2349725T3 ES2349725T3 ES06830128T ES06830128T ES2349725T3 ES 2349725 T3 ES2349725 T3 ES 2349725T3 ES 06830128 T ES06830128 T ES 06830128T ES 06830128 T ES06830128 T ES 06830128T ES 2349725 T3 ES2349725 T3 ES 2349725T3
- Authority
- ES
- Spain
- Prior art keywords
- points
- point
- coordinate
- scalar
- computer
- 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.)
- Active
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
- G06F7/60—Methods or arrangements for performing computations using a digital non-denominational number representation, i.e. number representation without radix; Computing devices using combinations of denominational and non-denominational quantity representations, e.g. using difunction pulse trains, STEELE computers, phase computers
- G06F7/72—Methods or arrangements for performing computations using a digital non-denominational number representation, i.e. number representation without radix; Computing devices using combinations of denominational and non-denominational quantity representations, e.g. using difunction pulse trains, STEELE computers, phase computers using residue arithmetic
- G06F7/724—Finite field arithmetic
- G06F7/725—Finite field arithmetic over elliptic curves
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F2207/00—Indexing scheme relating to methods or arrangements for processing data by operating upon the order or content of the data handled
- G06F2207/72—Indexing scheme relating to groups G06F7/72 - G06F7/729
- G06F2207/7219—Countermeasures against side channel or fault attacks
- G06F2207/7261—Uniform execution, e.g. avoiding jumps, or using formulae with the same power profile
Landscapes
- Physics & Mathematics (AREA)
- Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Mathematical Analysis (AREA)
- Mathematical Optimization (AREA)
- Pure & Applied Mathematics (AREA)
- Computational Mathematics (AREA)
- Theoretical Computer Science (AREA)
- Computing Systems (AREA)
- Mathematical Physics (AREA)
- General Engineering & Computer Science (AREA)
- Complex Calculations (AREA)
- Image Processing (AREA)
- Image Generation (AREA)
Abstract
Procedimiento criptográfico para verificar puntos determinados sobre una curva elíptica, que se realiza sobre una plataforma de hardware, en el que - se proporciona una curva elíptica, - se elige o determina al menos una coordenada de al menos un primer punto, que se encuentra sobre la curva elíptica, - se multiplica el primer punto según un algoritmo Montgomery-Leiter por un valor escalar, utilizándose en el algoritmo sólo una coordenada del primer punto, caracterizado porque - como resultado de la multiplicación escalar se obtienen otros puntos, que incluyen al menos una coordenada del correspondiente resultado del primer punto multiplicado por el escalar y del primer punto multiplicado por un escalar aumentado en un valor, - los puntos determinados incluyen al menos el primer punto y los otros puntos, - se comprueba si los puntos determinados pueden encontrarse sobre una recta, - los puntos determinados se reconocen como verificados en el caso de que puedan encontrarse sobre una recta.
Description
Procedimiento, dispositivo y sistema para
verificar puntos determinados sobre una curva elíptica.
La invención se refiere a un procedimiento, un
dispositivo y un sistema para verificar puntos determinados sobre
una curva elíptica.
Los procedimientos criptográficos basados en
curvas elípticas son muy eficientes, lo que se debe en particular a
que en estos procedimientos, contrariamente a en los procedimientos
criptográficos conocidos hasta ahora, no se conoce ningún método de
ataque con tiempo de ejecución subexponencial. Dicho de otra manera,
esto significa que la ganancia en seguridad por cada bit de los
parámetros de seguridad utilizados en procedimientos basados en
curvas elípticas es mayor y con ello pueden utilizarse para la
aplicación práctica longitudes de clave más cortas.
Con ello, los procedimientos criptográficos a
base de curvas elípticas dan mayor rendimiento y precisan de una
anchura de banda inferior a la de otros procedimientos
criptográficos para transmitir los parámetros del sistema, para un
grado comparable de seguridad alcanzable.
Como ejemplo, describiremos aquí a grandes
rasgos el conocido procedimiento Diffie-Hellman para
acordar una clave común entre dos interlocutores de comunicación
basándose en curvas elípticas. Aquí conoce el primer interlocutor
de comunicación A un parámetro de seguridad r_{a} y el segundo
interlocutor de comunicación B un parámetro de seguridad r_{b}.
Una vez que ambos interlocutores de comunicación se han puesto de
acuerdo respecto a una curva elíptica y a un punto común P sobre
esta curva elíptica, determina el interlocutor de comunicación A
un
valor
valor
y el interlocutor de comunicación B
un
valor
A continuación de ello, transmite el
interlocutor de comunicación A el valor Q_{a} al interlocutor de
comunicación B y el interlocutor de comunicación B transmite al
interlocutor de comunicación A el valor Q_{b}. En otra
multiplicación escalar determina ahora el interlocutor de
comunicación A la clave común
y el interlocutor de comunicación B
la misma clave
común
Estas multiplicaciones escalares constituyen así
un módulo esencial en procedimientos criptográficos a base de
curvas elípticas. La utilización de curvas elípticas es
especialmente ventajosa, ya que la operación de inversión
sólo puede calcularse con un
considerable coste de cálculo. Según el actual estado de
conocimientos, puede calcularse la multiplicación escalar en tiempo
polinómico, pero sólo es invertible en tiempo
exponencial.
\vskip1.000000\baselineskip
No obstante, Los procedimientos criptográficos
conocidos a base de curvas elípticas pueden ser dañados en los
llamados ataques de canal lateral.
Los ataques de canal lateral son una clase de
métodos para el análisis criptográfico. Contrariamente a los
ataques clásicos a aplicaciones criptográficas, no intenta entonces
un atacante romper el algoritmo matemático abstracto que sirve de
base, sino que ataca una implementación especial de un procedimiento
criptográfico. Para ello utiliza el atacante magnitudes de medida
físicas fácilmente accesibles de la implementación concreta, como
por ejemplo el tiempo de ejecución del cálculo, el consumo de
corriente y la radiación electromagnética del procesador durante el
cálculo o el comportamiento de la implementación en faltas
inducidas. Los valores de medida físicos de un único cálculo pueden
analizarse directamente por ejemplo en un análisis de flujo sencillo
SPA, o bien un atacante registra los valores de medida de varios
cálculos por ejemplo con un osciloscopio con memoria y evalúa los
valores de medida a continuación estadísticamente, por ejemplo en un
análisis de flujo diferencial, DPA. Los ataques de canal lateral
son a menudo bastante más eficientes que las técnicas
criptoanalíticas y pueden incluso romper procedimientos que desde el
punto de vista de los algoritmos se consideran como seguros, cuando
la implementación de estos algoritmos no está asegurada contra
ataques de canal lateral. Así se ha detectado que la implementación
concreta de procedimientos criptográficos que se basan en curvas
elípticas es de una gran importancia para el grado definitivo
resultante de seguridad alcanzable en las correspondientes
aplicaciones. En particular para smart card (tarjetas inteligentes)
y aplicaciones embedded (alojadas) son imprescindibles tales
contramedidas frente a ataques de canal lateral.
Un ejemplo de estos ataques de canal lateral es
el llamado análisis de faltas. En el mismo intenta un atacante
provocar, mediante una manipulación selectiva de los parámetros de
servicio de una implementación de un procedimiento criptográfico,
faltas transitorias o permanentes durante el cálculo criptográfico.
El ataque es posible, ya que el fabricante sólo puede garantizar el
correcto funcionamiento de un componente, como por ejemplo de una
smart card o de un sistema embedded, en unas condiciones de entorno
fijamente predeterminadas. Existe en consecuencia una amplia banda
de posibilidades técnicas para generar tales faltas, tales como la
manipulación de la generación de impulsos de reloj, temperatura
excesiva o demasiado baja, destellos de luz o perturbaciones
selectivas mediante un láser, destrucción parcial de los circuitos
eléctricos, emisión energética, etc. Las diferencias entre las
salidas del circuito cuando funciona correctamente y cuando funciona
incorrectamente pueden dar a un atacante, en función del modelo de
faltas utilizado por la implementación, informaciones sobre datos
secretos, como por ejemplo sobre claves secretas. En algunos
procedimientos criptográficos es suficiente un único resultado de
cálculo falso para proporcionar de inmediato la clave secreta. Por
ello las implementaciones relevantes para la seguridad deben tener
contramedidas adecuadas para proteger frente a un análisis de
faltas.
Las contramedidas conocidas hasta ahora abarcan
desde sensores que vigilan las condiciones del entorno y cuando las
condiciones de servicio son inadmisibles impiden la ejecución de los
cálculos criptográficos, hasta medidas de protección algorítmicas.
Con las medidas de protección algorítmicas puede realizarse por
ejemplo dos veces el cálculo criptográfico y compararse entre sí
ambos resultados. No obstante, esto tiene el inconveniente de un
coste de cálculo duplicado y ello lleva implícito un tiempo de
cálculo al menos duplicado. En otra contramedida conocida para
proteger frente a análisis de faltas, se introducen invariantes en
resultados intermedios del procedimiento criptográfico, que deben
mantenerse iguales durante todo el cálculo. Antes de que se emita el
resultado del cálculo, comprueba el aparato si la invariante sigue
siendo válida aún al final del cálculo. En el caso de que se haya
presentado una falta, ya no se cumple con gran probabilidad la
invariante. No obstante, este procedimiento tiene de nuevo el
inconveniente de que deben realizarse varios pasos de cálculo
adicionales y con ello se formulan elevadas exigencias a la
capacidad de cálculo necesaria y al espacio de memoria disponible.
Otra contramedida se conoce por la solicitud de patente europea EP 1
443 393 A2.
En entornos especiales en los que deben
implementarse procedimientos criptográficos, como por ejemplo smart
cards o chips RFID (de identificación por radio frecuencia), han de
tenerse en cuenta no obstante exigencias especiales en cuanto a la
capacidad de cálculo disponible y al espacio de memoria existente.
Pero en estos entornos tienen los procedimientos antes descritos
para prevenir ataques de canal lateral, en particular análisis de
faltas, el inconveniente de que no pueden utilizarse en tales
sistemas debido a sus elevadas exigencias a la capacidad de cálculo
y al espacio de memoria disponible.
Así tiene la invención como problema básico
ofrecer un procedimiento, un dispositivo, así como un sistema para
prevenir ataques de canal lateral, en particular ataques de canal
lateral basados en el análisis de faltas, en los que se logre
respecto a las soluciones conocidas hasta ahora una reducción
adicional de la necesidad de tiempo de cálculo, así como una
reducción del espacio de memoria necesario.
En el marco de la invención se resuelve esta
tarea mediante un procedimiento y un dispositivo con las
características de las reivindicaciones 1 y 8. Ventajosos
perfeccionamientos de la presente invención se indican en las
reivindicaciones dependientes.
En el marco de la invención se pone a
disposición, en un procedimiento criptográfico para verificar puntos
determinados sobre una curva elíptica, una curva elíptica. Entonces
se elige o determina al menos una coordenada de al menos un primer
punto que se encuentra sobre la curva elíptica. Este primer punto se
multiplica según un algoritmo Montgomery-Leiter por
un valor escalar, utilizándose en el algoritmo sólo una coordenada
del primer punto. Como resultado de la multiplicación escalar, se
obtienen otros puntos, que incluyen al menos una coordenada del
correspondiente resultado del primer punto multiplicado por el valor
escalar y del primer punto multiplicado por un valor escalar
aumentado en un determinado valor. Los puntos determinados incluyen
así el primer punto y los otros puntos. A continuación se comprueba
si los puntos determinados pueden encontrarse sobre una línea
recta. Los puntos determinados se reconocen como verificados,
siempre que puedan encontrarse sobre una recta. El procedimiento es
adecuado de manera ventajosa para utilizarse en entornos con
recursos de ordenador limitados, ya que se averigua de si los
puntos determinados se encuentran sobre una recta con un reducido
coste de cálculo.
Preferiblemente se evalúa un polinomio para
comprobar los puntos determinados, dando como resultado la
evaluación del polinomio exactamente un valor determinado cuando
los puntos a comprobar se encuentran sobre una recta. Esto tiene el
ventajoso efecto de que el procedimiento para la verificación puede
realizarse con una cantidad aún más reducida de multiplicaciones y
sumas y con ello se reduce aún más el costo de cálculo
necesario.
\newpage
Según otra configuración ventajosa de la
presente invención, se realiza, tras una cantidad que puede
predeterminarse de bits procesados por completo del valor escalar,
una verificación de los puntos determinados. Esto aporta la ventaja
de que puede realizarse una verificación tras cada paso del
algoritmo y con ello aumenta aún más la seguridad o bien puede
realizarse una verificación por ejemplo sólo tras realizarse el
algoritmo, para aumentar así la velocidad de la multiplicación
escalar.
Según el dispositivo correspondiente a la
invención para verificar puntos determinados sobre una curva
elíptica, presenta el dispositivo medios organizados tal que pueden
realizarse las siguientes etapas de procedimiento: Se pone a
disposición una curva elíptica y se elige o determina al menos una
coordenada de al menos un primer punto sobre la curva elíptica. El
primer punto se multiplica según un algoritmo
Montgomery-Leiter por un valor escalar,
utilizándose en el algoritmo sólo una coordenada del primer
punto.
Como resultado de la multiplicación escalar se
obtienen otros puntos adicionales, que incluyen al menos una
coordenada del correspondiente resultado del primer punto
multiplicado por el valor escalar y del primer punto multiplicado
por un valor escalar aumentado en un cierto valor. Así incluyen los
puntos determinados al menos un primer punto y los otros puntos. A
continuación se comprueba si los puntos determinados pueden
encontrarse sobre una recta, reconociéndose los puntos determinados
como verificados cuando los mismos pueden encontrarse sobre
una
recta.
recta.
Según el sistema correspondiente a la invención
para verificar puntos determinados sobre una curva elíptica con un
primer ordenador y un segundo ordenador, pueden conectarse entre sí
el primer ordenador y el segundo ordenador. Primeramente se acuerda
una curva elíptica y al menos una coordenada de al menos un primer
punto que se encuentra sobre la curva elíptica entre el primer
ordenador y el segundo ordenador. El primer ordenador presenta una
unidad de procesador que está equipada tal que pueden realizarse las
siguientes etapas de procedimiento: El primer punto se multiplica
según un algoritmo Montgomery-Leiter por un valor
escalar, utilizándose en el algoritmo sólo una coordenada del
primer punto. Como resultado de la multiplicación escalar, se
obtienen otros puntos, que al menos incluyen una coordenada del
correspondiente resultado del primer punto multiplicado por el
escalar y del primer punto multiplicado por un escalar aumentado en
un cierto valor. Los puntos determinados incluyen así al menos el
primer punto y los otros puntos. A continuación se comprueba si los
puntos determinados pueden encontrarse sobre una recta. Los puntos
determinados se reconocen como verificados en el caso de que los
mismos puedan encontrarse sobre una recta. Los puntos determinados y
verificados se transmiten desde el primer ordenador al segundo
ordenador, transmitiéndose para los puntos que se encuentran sobre
la curva elíptica en cada caso sólo una de las coordenadas del
correspondiente punto. El segundo ordenador presenta una unidad de
procesador que está equipada tal que pueden realizarse las
siguientes etapas del procedimiento: Los puntos transmitidos por el
primer ordenador son recibidos y los puntos determinados recibidos
se procesan adicionalmente, utilizándose en todo el procesamiento
adicional sólo una de las coordenadas del correspondiente punto
sobre la curva elíptica.
La presente invención se describirá a
continuación más en detalle en base ejemplos de ejecución basándose
en el dibujo. Se muestra en
figura 1 una representación esquemática de una
curva elíptica sobre los números reales.
Una curva elíptica E se describe en general
mediante una fórmula cúbica de la siguiente forma
siendo a_{1}, a_{2}, a_{3},
a_{4}, a_{6} elementos fijos de un cuerpo finito K, que
parametrizan la curva elíptica E. En este contexto hay que observar
que en función de la característica del cuerpo K la ecuación de la
curva elíptica E puede transformarse en ecuaciones de curvas más
sencillas.
\vskip1.000000\baselineskip
Tal como ya se ha indicado antes, constituye la
multiplicación escalar de puntos de la curva elíptica por números
enteros el fundamento de todos los procedimientos criptográficos
basados en curvas elípticas. Sea ahora S un número entero, P un
punto de la curva elíptica E y Q = n * P el múltiplo n del punto P.
Dados los puntos P y Q, se designa el cálculo de un valor escalar n
con Q = n * P como el problema logarítmico discreto para curvas
elípticas. Cuando se eligen adecuadamente el cuerpo finito K y los
parámetros de la curva elíptica E, no es posible con los medios
algorítmicos actuales en un tiempo aceptable resolver el problema
logarítmico discreto.
Un punto P de una curva elíptica E viene dado
por su coordenada x y su coordenada y. En base a la ecuación de la
curva elíptica E existen para un valor de x como máximo dos valores
de y diferentes y_{1} e y_{2}, con lo que los puntos (x,
y_{1}) y (x, y_{2}) son puntos sobre la curva elíptica. Para
fijar así un punto sobre la curva elíptica E inequívocamente, es
necesario, además de la coordenada x, un bit de información
adicional.
En el caso de una curva elíptica E sobre cuerpos
primos finitos, es suficiente por ejemplo el llamado Least
Significant Bit (LSB), bit significativo mínimo de la coordenada y o
bien el signo de la coordenada y del correspondiente punto como
información adicional.
Estas características de curvas elípticas se
aprovechan en el llamado algoritmo
Montgomery-Leiter, que es un método usual para
implementar la multiplicación escalar sobre curvas elípticas. El
algoritmo Montgomery-Leiter puede implementarse tal
que para el cálculo de la coordenada x de un múltiplo escalar de un
punto P se utilice sólo la coordenada x de P. Puesto que el
Montgomery-Leiter es a la vez un método muy bueno
para contrarrestar análisis de flujo sencillos, se implementa a
menudo en sistemas criptográficos que corren sobre sistemas
embedded.
Según el procedimiento que se describe a
continuación de un algoritmo Montgomery-Leiter, se
calcula un múltiplo n * P de un punto P que se encuentra sobre una
curva elíptica.
El valor escalar n = (n1,...,n1), dado en
representación binaria, se procesa bit a bit, comenzando en el
llamado Most Significant Bit o bit más significativo (MSB, N1).
Partamos de que designa a continuación u_{i}
el valor de la representación binaria (n_{1},...,n_{i}) para
todos los valores i de 1 a l. Como resultados intermedios se
calculan en la correspondiente ronda número i (iteración número i)
los puntos Q_{i} = u_{i} * P y R_{i} = (u_{i} + 1) * P
según la siguiente norma, representada en un pseudocódigo:
Según el primer procedimiento parcial antes
descrito, se asigna primeramente a un punto de inicialización
Q_{0} el valor 0, que corresponde a una inicialización de estas
variables.
A una variable adicional R se le asigna en una
etapa de inicialización adicional como variable de inicialización
R_{0} el valor del punto P.
En una etapa adicional se asigna en el bucle de
cálculo propiamente dicho en cada iteración para el valor escalar
n_{i} considerado en cada caso, para el caso de que el valor
escalar n_{i} tenga el valor 1, al valor de una primera variable
intermedia Q relativa a la iteración i (denominada Q_{i}) la suma
del valor de la primera variable intermedia
Q_{i-1} relativa a la iteración precedente
i-1 y al valor de la segunda variable intermedia
R_{i}-1 relativa a la iteración precedente
i-1. Al valor de la segunda variable intermedia
R_{i} en la iteración i se le asigna el doble del valor de la
segunda variable intermedia relativa a la iteración precedente
i-1.
Si el valor escalar n_{i} no es igual a 1,
entonces se asigna a la segunda variable intermedia R_{i} en la
iteración i la suma de los valores de la suma de la primera variable
intermedia R_{i}-1 en la iteración precedente y
al valor de la primera variable intermedia Q_{i}-1
en la iteración precedente i-1.
A la primera variable intermedia Q_{i}
relativa a la iteración i, se le asigna el doble del valor de la
primera variable intermedia Q_{i-1} relativa a la
iteración precedente i-1.
Según el pseudocódigo antes descrito, se emite
el valor que resulta de la variable intermedia Q_{1} en la última
iteración 1 como resultado de esta operación cuando todos los
valores escalares n_{i} del escalar n están procesados. A
elección pueden emitirse las variables intermedias R_{i} y Q_{i}
tras cada iteración o tras una cantidad que puede predeterminarse
de etapas de iteración como valor de resultado intermedio. Cuando
el cálculo de los resultados en el algoritmo de
Montgomery-Leiter está libre de faltas, se
encuentran tras cada etapa de iteración las variables intermedias
en la forma
que son diferentes en la diferencia
sólo en el punto
P.
\vskip1.000000\baselineskip
En consecuencia calcula el
Montgomery-Leiter a la vez las coordenadas x de los
puntos n * P así como (n+1) * P. Puesto que la coordenada y de la
diferencia entre ambos resultados se conoce, puede reconstruirse al
final del bucle a partir de las coordenadas x calculadas el punto n
* P completo.
Partiendo de ello, ha de comprobarse un método
sencillo para asegurar una multiplicación escalar sobre curvas
elípticas al final del cálculo en cuanto a si el resultado sigue
siendo un punto sobre la curva elíptica. Para ello debe comprobarse
simplemente si las coordenadas del punto del resultado cumplen la
ecuación de la curva elíptica.
No obstante, en entornos especiales sobre los
que deben implementarse procedimientos criptográficos, como por
ejemplo smart cards o chips RFID, han de tenerse en cuenta
exigencias especiales en cuanto a la capacidad de cálculo
disponible y al espacio de memoria existente. En estos entornos
tienen no obstante el procedimiento antes descrito para verificar
los puntos determinados sobre la curva elíptica el inconveniente de
que una reconstrucción completa del punto del resultado y una
utilización subsiguiente en la ecuación de la curva elíptica,
formula considerables exigencias a la es-
tructura de ordenador existente y con ello trae como consecuencia una necesidad de tiempo de cálculo bastante mayor.
tructura de ordenador existente y con ello trae como consecuencia una necesidad de tiempo de cálculo bastante mayor.
Otro procedimiento para verificar puntos
determinados sobre una ecuación de curva elíptica partiendo del
algoritmo Montgomery-Leiter sería renunciar a las
coordenadas y, con lo que en este caso se está obligado, tras
utilizar la coordenada x, a comprobar la posibilidad de solución de
una ecuación cuadrática en y. También este procedimiento tiene el
inconveniente esencial de que no puede realizarse en sistemas con
recursos de cálculo limitados.
A continuación se describe más en detalle el
procedimiento correspondiente a la invención para verificar puntos
determinados sobre una curva elíptica en base a un ejemplo de
ejecución.
Según la ley de adición de la curva elíptica,
resulta que, para un cálculo libre de faltas de los resultados, los
puntos u_{i}.P, - (u_{i} + 1).P y P se encuentran sobre una
recta.
Esto puede verse a modo de ejemplo en la figura
1. La figura 1 muestra una curva elíptica 1, en la que están
señalados los puntos 2 P_{1} = P, 3 P_{2} = n * P y 4 P_{1} +
P_{2} = (n+1) * P. Para estos puntos rige:
Tal como se deriva de la ley de adición de la
curva elíptica y puede observarse en la figura 1, se encuentran los
puntos P_{1}, P_{2} y -(P_{1} + P_{2}) sobre una recta 5.
Este fenómeno se utiliza en el procedimiento correspondiente a la
invención para verificar puntos determinados sobre una curva
elíptica. Para ello se utiliza un polinomio cuadrático. Si se
cumple este polinomio cuadrático para las coordenadas determinadas
de los puntos del algoritmo Montgomery-Leiter,
P_{1} + P_{2} = R_{i} = (u_{i}+ 1).P, P_{2} = Q_{i} =
u_{i}.P y P_{1} = P se reconocen los puntos determinados como
verificados.
Supongamos que en un ataque mediante resultados
erróneos de la multiplicación escalar intenta un atacante
selectivamente inducir una falta dentro del
Montgomery-Leiter. En una smart card o en un chip
RFID esto se realiza por ejemplo mediante oscilaciones de
temperatura o de tensión, sometiendo a una radiación, etcétera. Si
se induce la falta sólo dentro del cálculo del
Montgomery-Leiter, han de distinguirse ante todo dos
casos.
En el primer caso origina la falta inducida que
el resultado tras un recorrido completo del bucle dentro del
Montgomery-Leiter no sea ningún punto válido de la
curva. Esto significa que al menos uno de ambos resultados R_{i}
y Q_{i} no posee ninguna coordenada x de un punto sobre la curva
elíptica. En este caso la prueba con el polinomio cuadrático
descubrirá esta falta.
En el segundo caso se induce ciertamente una
falta con éxito, pero los resultados siguen siendo coordenadas x
válidas de puntos sobre la curva elíptica. En este ejemplo de
ejecución suponemos que antes de la falta la entrada es u_{i}.P
y (u_{i} + 1).P. Tras el siguiente recorrido del bucle, se
obtiene, bajo la suposición de que la falta se induce en el primer
componente, n'.P y (2u_{i+1}+2).P o bien n'.P y (2u_{i+1}+1).P,
en función del valor del bit procesado. Resulta que ambos resultados
ya no se diferencian en P y por lo tanto los puntos P, n'.P y
(2u_{i+1}+2).P o bien -(2u_{i+1}+1).P ya no pueden encontrarse
sobre una recta. Por ello también en este caso el polinomio
cuadrático descubrirá esta
falta.
falta.
Este procedimiento para la verificación
eficiente de la integridad de un resultado de cálculo, constituye
un módulo importante para formular protocolos de criptografía
low-cost asimétricos resistentes a faltas, que se
utilizan por ejemplo en smart cards, chips RFID o sistemas embedded.
Puesto que usualmente se renuncia en estos protocolos a coordenadas
y, sólo es posible una comprobación de si se trata de un componente
de un punto válido con la solución de una ecuación cuadrática. Esta
comprobación incluye algunas operaciones costosas en cálculo, con
lo que la misma no procede para un protocolo
low-cost. La evaluación del polinomio cuadrático
puede realizarse tal como se muestra a continuación con un reducido
coste de cálculo, con lo que este procedimiento es especialmente
adecuado para utilizarlo en una aplicación
low-cost.
A continuación se indican a modo de ejemplo
polinomios cuadráticos, que pueden utilizarse para la verificación
sencilla del resultado de una multiplicación escalar mediante el
Montgomery-Leiter. Entonces se diferencia la curva
característica del cuerpo mediante el que está definida la curva
elíptica.
En una curva característica del cuerpo K = 2
viene definida la curva elíptica mediante la ecuación:
Los valores x_{1}, x_{2}, x_{3} pueden ser
exactamente entonces coordenadas x de puntos que se encuentran
sobre una recta cuando el polinomio
tiene el valor 0. En la
representación proyectiva de coordenadas rige x_{1} =
X_{1}/Z_{1}, x_{2} = X_{2}/Z_{2}, x_{3} =
X_{3}/Z_{3} y el punto infinitamente lejano posee la
representación X \neq 0 y Z = 0. Con ello resulta en la
representación proyectiva el siguiente polinomio para la
verificación:
Si el cuerpo K tiene la curva característica 3,
entonces viene dada la curva elíptica por la ecuación:
Los valores x1, x2, x3 pueden ser entonces
exactamente coordenadas x de puntos que se encuentran sobre una
recta cuando el polinomio
asume el valor
0.
\newpage
En la representación de coordenadas proyectiva
resulta el siguiente polinomio para la verificación:
Para una curva característica del cuerpo K >
3, viene dada la curva elíptica por la ecuación
Los valores x_{1}, x_{2}, x_{3} pueden
entonces ser exactamente coordenadas x de puntos que se encuentran
sobre una recta, cuando el polinomio
asume el valor
0.
\vskip1.000000\baselineskip
En la representación proyectiva de coordenadas
resulta el siguiente polinomio para la verificación:
Para representaciones proyectivas alternativas,
por ejemplo coordenadas de Jacob, deben adaptarse
correspondientemente las representaciones. No obstante, se observa
ya aquí que según la presente invención la verificación de puntos
determinados sobre la curva elíptica puede realizarse mediante un
conjunto de multiplicaciones y adiciones y con ello respecto a
soluciones conocidas hasta ahora resulta una considerable reducción
en coste de cálculo.
La presente invención no queda limitada a los
ejemplos de ejecución aquí descritos.
Claims (9)
-
\global\parskip0.900000\baselineskip
1. Procedimiento criptográfico para verificar puntos determinados sobre una curva elíptica, que se realiza sobre una plataforma de hardware,en el que- -
- se proporciona una curva elíptica,
- -
- se elige o determina al menos una coordenada de al menos un primer punto, que se encuentra sobre la curva elíptica,
- -
- se multiplica el primer punto según un algoritmo Montgomery-Leiter por un valor escalar, utilizándose en el algoritmo sólo una coordenada del primer punto,
caracterizado porque- -
- como resultado de la multiplicación escalar se obtienen otros puntos, que incluyen al menos una coordenada del correspondiente resultado del primer punto multiplicado por el escalar y del primer punto multiplicado por un escalar aumentado en un valor,
- -
- los puntos determinados incluyen al menos el primer punto y los otros puntos,
- -
- se comprueba si los puntos determinados pueden encontrarse sobre una recta,
- -
- los puntos determinados se reconocen como verificados en el caso de que puedan encontrarse sobre una recta.
\vskip1.000000\baselineskip
- 2. Procedimiento según la reivindicación 1, en el queen cada caso se memoriza una coordenada de los puntos determinados.
\vskip1.000000\baselineskip
- 3. Procedimiento según la reivindicación 1, en el quese utiliza como una de las coordenadas de los puntos determinados la coordenada x.
\vskip1.000000\baselineskip
- 4. Procedimiento según la reivindicación 1, en el quese evalúa un polinomio para comprobar los puntos determinados, dando como resultado la evaluación del polinomio exactamente un valor determinado cuando los puntos a comprobar se encuentran sobre una recta.
\vskip1.000000\baselineskip
- 5. Procedimiento según la reivindicación 4, en el queel polinomio para comprobar los puntos determinados evalúa las coordenadas en representación de coordenadas proyectiva y/o afín.
\vskip1.000000\baselineskip
- 6. Procedimiento según la reivindicación 1, en el que
- -
- el valor escalar se encuentra en representación binaria,
- -
- el valor escalar se procesa bit a bit comenzando en el llamado Most Significant Bit (MSB), bit más significativo.
\vskip1.000000\baselineskip
- 7. Procedimiento según la reivindicación 6, en el quetras una cantidad que puede predeterminarse de bits procesados del valor escalar, se realiza una verificación de los puntos determinados.
\vskip1.000000\baselineskip
- 8. Dispositivo para verificar puntos determinados sobre una curva elíptica, en particular según un procedimiento según una de las reivindicaciones 1 a 7, en el queel dispositivo presenta medios que están equipados tal que pueden realizarse las siguientes etapas del procedimiento:
- -
- se proporciona una curva elíptica,
\global\parskip1.000000\baselineskip
- -
- se elige o determina al menos una coordenada de al menos un primer punto, que se encuentra sobre la curva elíptica,
- -
- se multiplica el primer punto según un algoritmo Montgomery-Leiter por un valor escalar, utilizándose en el algoritmo sólo una coordenada del primer punto,
caracterizado porque- -
- como resultado de la multiplicación escalar se obtienen otros puntos, que incluyen al menos una coordenada del correspondiente resultado del primer punto multiplicado por el escalar y del primer punto multiplicado por un escalar aumentado en un valor,
- -
- los puntos determinados incluyen al menos el primer punto y los otros puntos,
- -
- se comprueba si los puntos determinados pueden encontrarse sobre una recta,
- -
- los puntos determinados se reconocen como verificados en el caso de que puedan encontrarse sobre una recta.
\vskip1.000000\baselineskip
- 9. Sistema para verificar puntos determinados sobre una curva elíptica, en particular según un procedimiento según una de las reivindicaciones 1 a 7 con un primer ordenador y un segundo ordenador, pudiendo conectarse entre sí el primer ordenador y el segundo ordenador,
- -
- en el que se acuerda entre el primer ordenador y el segundo ordenador una curva elíptica y al menos una coordenada de un primer punto, que se encuentra sobre la curva elíptica,
- -
- en el que el primer ordenador es un dispositivo según la reivindicación 8,
- -
- y en el que los puntos determinados y verificados se transmiten desde el primer ordenador al segundo ordenador, transmitiéndose para puntos que se encuentran sobre la curva elíptica en cada caso sólo una de las coordenadas del correspondiente punto,
- -
- en el que el segundo ordenador presenta una unidad de procesador que está equipada tal que pueden realizarse las siguientes etapas de procedimiento:
- -
- se reciben los puntos transmitidos por el primer ordenador,
- -
- se procesan adicionalmente los puntos recibidos, determinados, utilizándose en todo el procesamiento adicional sólo una de las coordenadas del correspondiente punto sobre la curva elíptica.
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| DE102006002891A DE102006002891B4 (de) | 2006-01-20 | 2006-01-20 | Verfahren, Vorrichtung und System zum Verifizieren von auf einer elliptischen Kurve ermittelten Punkten |
| DE102006002891 | 2006-01-20 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| ES2349725T3 true ES2349725T3 (es) | 2011-01-10 |
Family
ID=38222225
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| ES06830128T Active ES2349725T3 (es) | 2006-01-20 | 2006-11-27 | Procedimiento, dispositivo y sistema para verificar puntos determinados sobre una curva elíptica. |
Country Status (6)
| Country | Link |
|---|---|
| US (1) | US7774160B2 (es) |
| EP (1) | EP1987421B1 (es) |
| AT (1) | ATE478375T1 (es) |
| DE (2) | DE102006002891B4 (es) |
| ES (1) | ES2349725T3 (es) |
| WO (1) | WO2007087911A2 (es) |
Families Citing this family (7)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CA2701573C (en) * | 2007-10-30 | 2014-05-20 | Blackberry Limited | Fault detection in exponentiation and point multiplication operations using a montgomery ladder |
| US20110093714A1 (en) * | 2009-10-20 | 2011-04-21 | Infineon Technologies Ag | Systems and methods for asymmetric cryptographic accessory authentication |
| US8621212B2 (en) * | 2009-12-22 | 2013-12-31 | Infineon Technologies Ag | Systems and methods for cryptographically enhanced automatic blacklist management and enforcement |
| US8630411B2 (en) | 2011-02-17 | 2014-01-14 | Infineon Technologies Ag | Systems and methods for device and data authentication |
| EP2525524B1 (en) * | 2011-05-12 | 2016-08-10 | Nxp B.V. | Transponder, reader and methods for operating the same |
| US9087192B2 (en) | 2013-09-10 | 2015-07-21 | Infineon Technologies Ag | Electronic circuit and method for monitoring a data processing |
| US9590805B1 (en) * | 2014-12-23 | 2017-03-07 | EMC IP Holding Company LLC | Ladder-based cryptographic techniques using pre-computed points |
Family Cites Families (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CA2252078C (en) * | 1998-10-28 | 2009-02-17 | Certicom Corp. | Power signature attack resistant cryptographic system |
| FR2796177B1 (fr) * | 1999-07-09 | 2001-10-12 | Oberthur Card Systems Sas | Procede de cryptographie mis en oeuvre entre deux entites echangeant des informations |
| DE10156708B4 (de) * | 2001-11-19 | 2005-09-29 | Infineon Technologies Ag | Verfahren und Vorrichtung zum Multiplizieren und Verfahren und Vorrichtung zum Addieren auf einer elliptischen Kurve |
| US7388957B2 (en) * | 2003-01-28 | 2008-06-17 | Matsushita Electric Industrial Co., Ltd. | Elliptic curve exponentiation apparatus that can counter differential fault attack, and information security apparatus |
| WO2005015526A1 (ja) * | 2003-08-06 | 2005-02-17 | Fujitsu Limited | 楕円曲線暗号装置，楕円曲線暗号方法，楕円曲線暗号プログラムおよび同プログラムを記録したコンピュータ読取可能な記録媒体 |
-
2006
- 2006-01-20 DE DE102006002891A patent/DE102006002891B4/de not_active Expired - Fee Related
- 2006-11-27 ES ES06830128T patent/ES2349725T3/es active Active
- 2006-11-27 US US12/223,031 patent/US7774160B2/en active Active
- 2006-11-27 EP EP06830128A patent/EP1987421B1/de not_active Not-in-force
- 2006-11-27 AT AT06830128T patent/ATE478375T1/de active
- 2006-11-27 WO PCT/EP2006/068919 patent/WO2007087911A2/de not_active Ceased
- 2006-11-27 DE DE502006007709T patent/DE502006007709D1/de active Active
Also Published As
| Publication number | Publication date |
|---|---|
| DE102006002891B4 (de) | 2009-06-04 |
| EP1987421B1 (de) | 2010-08-18 |
| WO2007087911A2 (de) | 2007-08-09 |
| DE102006002891A1 (de) | 2007-08-02 |
| US20090024352A1 (en) | 2009-01-22 |
| WO2007087911A3 (de) | 2007-10-18 |
| DE502006007709D1 (de) | 2010-09-30 |
| US7774160B2 (en) | 2010-08-10 |
| EP1987421A2 (de) | 2008-11-05 |
| ATE478375T1 (de) | 2010-09-15 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US11151290B2 (en) | Tamper-resistant component networks | |
| US9571289B2 (en) | Methods and systems for glitch-resistant cryptographic signing | |
| US8850221B2 (en) | Protection against side channel attacks with an integrity check | |
| ES2236903T3 (es) | Metodo y dispositivo mejorados para la proteccion de programas de codigos publicos contra ataques producidos por la secuencia de operaciones por fallos. | |
| ES2730691T3 (es) | Procedimiento y sistema para la comunicación segura entre una etiqueta RFID y un dispositivo de lectura | |
| CN105991292B (zh) | 用于操作安全椭圆曲线密码系统的系统和方法 | |
| CN100356342C (zh) | 信息处理装置 | |
| EP2211265B1 (en) | Elliptic curve arithmetic processing unit and elliptic curve arithmetic processing program and method | |
| CN104424428B (zh) | 用于监视数据处理的电子电路和方法 | |
| US11171780B2 (en) | Systems and methods for operating secure elliptic curve cryptosystems | |
| ES2287745T3 (es) | Procedimiento para la aplicacion asegurada de un algoritmo de criptografia de tipo rsa y componente correspondiente. | |
| ES2827873T3 (es) | Método de determinación de una suma de integridad, programa informático y entidad electrónica asociados | |
| Tunstall | Smart card security | |
| BR112013012216B1 (pt) | proteção contra as escutas passivas | |
| EP3447509B1 (en) | Method of testing the resistance of a circuit to a side channel analysis | |
| JP2007328789A (ja) | 入力データに関するアドレスを使用して入力データを符号化するための暗号システム、エラー検出回路、及びそれの動作方法 | |
| Park et al. | Cloning hardware wallet without valid credentials through side-channel analysis of hash function | |
| US7454625B2 (en) | Method and apparatus for protecting a calculation in a cryptographic algorithm | |
| Karp et al. | Security-oriented code-based architectures for mitigating fault attacks | |
| US20240193300A1 (en) | Data processing device and method for processing secret data | |
| ES2385070T3 (es) | Procedimiento de preservación de la seguridad de una ramificación condicional, soporte de informaciones, programa y sistema asegurado para ese procedimiento | |
| US12169570B2 (en) | Data processing device and method for processing secret data | |
| US20090024352A1 (en) | Method, Device and System For Verifying Points Determined on an Elliptic Curve | |
| ES2371333T3 (es) | Dispositivo y procedimiento de ejecución de un algoritmo criptográfico. | |
| US20090024887A1 (en) | Semiconductor storage device, data write method and data read method |