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.

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.

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.