Uso de un coprocesador para inversión modular.

Procedimiento para el uso de un coprocesador (16) para la determinación del inverso modular x de un valor deentrada u con respecto a un módulo v,

en el que:

- a partir del valor de entrada u se determina un primer valor ampliado U con una longitud de bits aumentada conrespecto al valor de entrada u, de tal manera que en una sección de bits del primer valor ampliado U se encuentra lainformación del valor de entrada u, en el que la determinación del primer valor ampliado U comprende lamultiplicación del valor de entrada u por un factor de ampliación f y en el que f >2v,

- a partir del módulo v se determina un segundo valor ampliado V con una longitud de bits aumentada con respectoal módulo v, de tal manera que en una sección de bits del segundo valor ampliado V se encuentra la información delmódulo v, en el que la determinación del segundo valor ampliado V comprende la multiplicación del módulo v por elfactor de ampliación f,

- el coprocesador (16) está previsto para cálculos de números enteros con al menos la longitud de bits aumentada,

- al menos uno de los valores ampliados U, V contiene una perturbación en una posición de bit, que está distanciadade aquellas posiciones de bit, en las que se encuentra la información del valor de entrada u o del módulo v,

- partiendo de los dos valores ampliados U y V mediante el uso del coprocesador (16) se realizan etapas (34) deprocesamiento de un procedimiento euclídeo, siempre que se cumpla una condición de realización predeterminada,y

- el inverso modular x se determina en función del resultado de las etapas (34) de procesamiento realizadas.

Tipo: Patente Europea. Resumen de patente/invención. Número de Solicitud: E06013333.

Solicitante: GIESECKE & DEVRIENT GMBH.

Nacionalidad solicitante: Alemania.

Dirección: PRINZREGENTENSTRASSE 159 81677 MUNCHEN ALEMANIA.

Inventor/es: SEYSEN,MARTIN,DR.

Fecha de Publicación: .

Clasificación Internacional de Patentes:

  • G06F7/72 SECCION G — FISICA.G06 COMPUTO; CALCULO; CONTEO.G06F TRATAMIENTO DE DATOS DIGITALES ELECTRICOS (computadores en los que una parte del cálculo se efectúa hidráulica o neumáticamente G06D, ópticamente G06E; sistemas de computadores basados en modelos de cálculo específicos G06N). › G06F 7/00 Métodos o disposiciones para el tratamiento de datos actuando sobre el orden o el contenido de los datos tratados (circuitos lógicos H03K 19/00). › que utilizan la aritmética de restos.

PDF original: ES-2404410_T3.pdf

 


Fragmento de la descripción:

Uso de un coprocesador para inversión modular

La invención se refiere, en general, al campo técnico de la criptografía y, en especial, a una técnica prevista con fines criptográficos para la inversión modular mediante el uso de un coprocesador. En particular, la invención está prevista para su utilización en soportes de datos portátiles que, por ejemplo, pueden estar configurados como tarjetas con chip en distintas formas de construcción o como módulos de chip.

Como los soportes de datos portátiles deben ser económicos y pequeños, por regla general presentan una capacidad de cálculo sólo relativamente reducida y relativamente poco espacio de memoria. Por otro lado, los soportes de datos portátiles se utilizan a menudo para aplicaciones críticas para la seguridad tales como, por ejemplo, transacciones financieras o funciones de identificación electrónicas. Por ello es deseable realizar en soportes de datos portátiles procedimientos criptográficos seguros (“intensos”) .

Una serie de procedimientos criptográficos conocidos con clave pública, por ejemplo los procedimientos conocidos por el nombre de RSA y Diffie-Hellman, contienen cálculos en un grupo multiplicativo con un número entero grande como módulo. Para poder realizar tales procedimientos de manera eficaz se han creado microcontroladores, que además del propio núcleo de procesador presentan un coprocesador criptográfico. Este tipo de coprocesadores están optimizados por regla general para multiplicaciones de números enteros modulares con longitudes de bits de aproximadamente 512 bits a 1024 bits. La patente estadounidense 5.961.578 muestra a modo de ejemplo un microcontrolador de este tipo.

Un desarrollo más reciente es el uso de procedimientos criptográficos, que se basan en curvas elípticas (“procedimientos EC”) . A diferencia del procedimiento RSA mencionado anteriormente los procedimientos EC requieren longitudes de bits de clave considerablemente menores de normalmente 160 bits a 256 bits. Sin embargo, en los procedimientos EC otras opciones como la multiplicación modular, concretamente en particular la suma, resta e inversión modular, desempeñan un papel importante.

La duración de ejecución total del procedimiento EC se ve influida en particular mediante las inversiones modulares necesarias. Cuando una inversión modular no se realiza con el apoyo de un coprocesador, por ejemplo puede requerir un factor 100 más de tiempo que una multiplicación modular. Así, por ejemplo, en el procedimiento de firma ECDSA conocido con una longitud de bits de clave de 160 bits a 192 bits se usa aproximadamente el 20% de la duración de ejecución para inversiones modulares. Por tanto, cada aceleración de las inversiones modulares afecta en una medida perceptible sobre la duración de ejecución total del procedimiento de firma ECDSA y otros procedimientos EC.

Así, existe la necesidad de un procedimiento eficaz para la inversión modular. En particular existe la necesidad de utilizar coprocesadores en sí conocidos de manera eficaz para la inversión modular.

Un procedimiento conocido y a menudo utilizado para la inversión modular es el procedimiento euclídeo ampliado, que se basa en el procedimiento ya propuesto por Euclides para la determinación del máximo común divisor (gcd = greatest common divisor) de dos valores de entrada u, v. Mediante una operación adicional, en el procedimiento euclídeo ampliado se determinan además del valor gcd (u, v) también los coeficientes A, ! de una combinación lineal de los valores de entrada u, v con Au -!v = gcd (u, v) y IAI < v. Como existe un inverso modular u-1 del valor u con el módulo v sólo para gcd (u, v) = 1, se aplica Au -!v = 1 y por tanto u-1 = A (mod v) para el coeficiente A calculado mediante el procedimiento euclídeo ampliado.

El procedimiento euclídeo no ampliado y el procedimiento euclídeo ampliado se describen como los algoritmos A y X en las páginas 334 - 343 del libro “The Art of Computer Programming” de D. E. Knuth, tomo 2, 3ª edición, Addison-Wesley, 1997. Por las operaciones adicionales necesarias el esfuerzo de cálculo necesario para el procedimiento euclídeo ampliado es claramente mayor que el esfuerzo para el procedimiento euclídeo no ampliado. Por tanto es deseable proporcionar un procedimiento para la inversión modular, que al menos para algunos casos de aplicación requiera menos tiempo de cálculo que el procedimiento euclídeo ampliado.

Por tanto la invención tiene como objetivo proponer una técnica para la inversión modular, mediante la que pueda utilizarse un coprocesador de una manera especialmente favorable.

Según la invención este objetivo se soluciona por completo o en parte mediante un procedimiento con las características de la reivindicación 1, un producto de programa informático según la reivindicación 6 y un soporte de datos portátil según la reivindicación 7. Las reivindicaciones dependientes definen características opcionales de algunas configuraciones de la invención.

La invención parte de la idea básica de realizar etapas de procesamiento de un procedimiento euclídeo no ampliado con valores, que presentan una longitud de bits mayor que el módulo y/o el valor que va a invertirse y que por ello en el presente documento se denominan “valores ampliados”. Es un hallazgo sorprendente que en estos valores ampliados puede incluirse información a partir de la que finalmente puede determinarse fácilmente el inverso deseado, aún cuando no se realice el procedimiento euclídeo ampliado.

En general mediante la invención se aumenta la longitud de bits de los cálculos, aunque se reduce el número de operaciones de cálculo en comparación con un procedimiento euclídeo ampliado. Así, por ejemplo, en algunas formas de realización de la invención puede dividirse por la mitad aproximadamente el número de las operaciones necesarias, mientras que aproximadamente se duplica la longitud de bits. En el caso de constelaciones como las denominadas al principio, en las que, por ejemplo, debe realizarse un procedimiento EC con una longitud de bits de clave de 160 bits a 256 bits mediante el uso de un coprocesador, que está configurado para cálculos con 512 bits ó 1024 bits, sin embargo, la longitud de bits mayor no desempeña ningún papel, mientras que el número reducido de operaciones lleva a una reducción aproximadamente lineal del tiempo de cálculo.

En algunas configuraciones en los valores ampliados la información del valor de entrada y/o del módulo se ha desplazado a posiciones de bit más elevadas. Esto puede ocurrir mediante una multiplicación por un factor de ampliación, que a su vez puede ser una segunda potencia o un múltiplo de una segunda potencia. Se entiende que esta multiplicación puede implementarse de manera eficaz, por ejemplo mediante una operación de desplazamiento. Según la invención al menos uno de los valores ampliados contiene además una perturbación en una posición de bit de valor bajo. Así, por ejemplo, puede fijarse el bit de valor más bajo del primer valor ampliado.

Las etapas de procesamiento corresponden según la invención a las etapas de procesamiento de un procedimiento euclídeo, por ejemplo de un procedimiento euclídeo clásico no ampliado o de un procedimiento euclídeo con la configuración según Lehmer. Sin embargo, esto no quiere decir necesariamente que las etapas de procesamiento se realicen con la misma frecuencia que en el caso de un procedimiento euclídeo. Más bien, en algunas configuraciones el procedimiento descrito en el presente documento se finaliza antes de lo que sería el caso en un procedimiento euclídeo habitual.

Según la invención el coprocesador está optimizado para cálculos de números enteros con al menos la longitud de bits aumentada, por ejemplo, duplicada. Este puede ser el caso por ejemplo cuando el coprocesador está configurado para cálculos RSA o procedimientos similares y se utiliza el procedimiento según la invención para cálculos EC.

El producto de programa informático según la invención presenta instrucciones de programa para implementar el procedimiento según la invención. Un producto de programa informático de este tipo puede ser, por ejemplo, una memoria de semiconductor o un disquete o un CD-ROM. En particular un producto de programa informático de este tipo puede estar previsto para su uso en la fabricación o inicialización de tarjetas con chip.

En configuraciones preferidas el producto de programa informático y/o el soporte de datos portátil está perfeccionado con características que corresponden a las características descritas anteriormente y/o mencionadas en las reivindicaciones de procedimiento dependientes.

... [Seguir leyendo]

 


Reivindicaciones:

1. Procedimiento para el uso de un coprocesador (16) para la determinación del inverso modular x de un valor de entrada u con respecto a un módulo v, en el que:

- a partir del valor de entrada u se determina un primer valor ampliado U con una longitud de bits aumentada con respecto al valor de entrada u, de tal manera que en una sección de bits del primer valor ampliado U se encuentra la información del valor de entrada u, en el que la determinación del primer valor ampliado U comprende la multiplicación del valor de entrada u por un factor de ampliación f y en el que f > 2v,

-a partir del módulo v se determina un segundo valor ampliado V con una longitud de bits aumentada con respecto al módulo v, de tal manera que en una sección de bits del segundo valor ampliado V se encuentra la información del módulo v, en el que la determinación del segundo valor ampliado V comprende la multiplicación del módulo v por el factor de ampliación f,

- el coprocesador (16) está previsto para cálculos de números enteros con al menos la longitud de bits aumentada,

- al menos uno de los valores ampliados U, V contiene una perturbación en una posición de bit, que está distanciada de aquellas posiciones de bit, en las que se encuentra la información del valor de entrada u o del módulo v,

- partiendo de los dos valores ampliados U y V mediante el uso del coprocesador (16) se realizan etapas (34) de procesamiento de un procedimiento euclídeo, siempre que se cumpla una condición de realización predeterminada, y

- el inverso modular x se determina en función del resultado de las etapas (34) de procesamiento realizadas.

2. Procedimiento según la reivindicación 1, caracterizado porque el factor de ampliación f es una segunda potencia, de modo que en los valores ampliados U, V la información del valor de entrada u y del módulo v se ha desplazado a posiciones de bit más elevadas.

3. Procedimiento según la reivindicación 1 ó 2, caracterizado porque las etapas (34) de procesamiento contienen una reducción modular realizada mediante el uso del coprocesador (16) .

4. Procedimiento según una de las reivindicaciones 1 a 3, caracterizado porque las etapas (34) de procesamiento, partiendo de los dos valores ampliados U y V, corresponden a una serie de asignaciones (U, V) := (V, U mod V) .

5. Procedimiento según una de las reivindicaciones 1 a 4, caracterizado porque el procedimiento está previsto para una aplicación criptográfica en un soporte (10) de datos portátil, en particular para un procedimiento EC.

6. Producto de programa informático, que presenta instrucciones de programa, para hacer que un microcontrolador

(12) realice un procedimiento con las características de una de las reivindicaciones 1 a 5.

7. Soporte (10) de datos portátil, en particular una tarjeta con chip o módulo de chip, que está configurado para la realización de un procedimiento con las características de una de las reivindicaciones 1 a 5.


 

Patentes similares o relacionadas:

Sistema y método de exponenciación del teorema chino del resto de uso único para algoritmos criptográficos, del 6 de Noviembre de 2019, de Thales Dis France SA: Un método para operar un aparato de criptografía para realizar una operación de descifrado que tiene una operación de exponenciación X, protegiendo el método al […]

Multiplicador no modular, procedimiento para multiplicación no modular y dispositivo computacional, del 17 de Julio de 2019, de Winbond Electronics Corp: Un multiplicador no modular, que comprende: una interfaz , que está configurada para recibir números A y B enteros de n bits; y circuitería […]

Procedimiento de cálculo, dispositivo de cálculo y producto de software de cálculo para dominio de Montgomery, del 16 de Enero de 2019, de Winbond Electronics Corp: Un procedimiento de cálculo, que comprende: recibir, en un circuito multiplicador de Montgomery, un par de coordenadas (x, y) de […]

Método, dispositivo y medio legible por ordenador no transitorio para cálculo criptográfico, del 4 de Julio de 2018, de Winbond Electronics Corp: Un método para cálculo criptográfico, que comprende: recibir , en un circuito multiplicador de Montgomery que tiene un tamaño de bloque predeterminado, un par de […]

Procedimiento para codificar o decodificar con seguridad un mensaje, del 31 de Agosto de 2016, de SIEMENS AKTIENGESELLSCHAFT: Procedimiento para codificar o decodificar de forma segura un mensaje o para generar o verificar una firma digital de un mensaje, en el que con […]

Procedimiento de procesamiento criptográfico de datos y dispositivo asociado, del 18 de Septiembre de 2013, de OBERTHUR TECHNOLOGIES: Procedimiento de procesamiento criptográfico de datos aplicado dentro de una entidad electrónica, en el que sedetermina, a partir de un primer punto en una […]

Criptografía sobre una curva elíptica simplificada, del 7 de Agosto de 2013, de MORPHO: Un procedimiento de ejecución de un cálculo criptográfico en un componente electrónico que comprende unaetapa de obtención de un punto P(X,Y) a partir de al menos un […]

DISPOSITIVO Y PROCEDIMIENTO DE EJECUCIÓN DE UN ALGORITMO CRIPTOGRÁFICO, del 29 de Diciembre de 2011, de GEMALTO SA: Dispositivo de ejecución de un algoritmo criptográfico que incluye medios de cálculo , medios de memorización de datos y medios de comunicación […]

Utilizamos cookies para mejorar nuestros servicios y mostrarle publicidad relevante. Si continua navegando, consideramos que acepta su uso. Puede obtener más información aquí. .