En el cálculo aritmético modular , la multiplicación modular de Montgomery , más comúnmente denominada multiplicación de Montgomery , es un método para realizar multiplicaciones modulares rápidas. Fue introducida en 1985 por el matemático estadounidense Peter L. Montgomery . [1] [2]
La multiplicación modular de Montgomery se basa en una representación especial de números llamada forma de Montgomery. El algoritmo utiliza las formas de Montgomery de a y b para calcular de manera eficiente la forma de Montgomery de ab mod N. La eficiencia proviene de evitar costosas operaciones de división. La multiplicación modular clásica reduce el producto de doble ancho ab utilizando la división por N y manteniendo solo el resto. Esta división requiere estimación y corrección del dígito del cociente. La forma de Montgomery, en cambio, depende de una constante R > N que es coprima con N , y la única división necesaria en la multiplicación de Montgomery es la división por R. La constante R puede elegirse de manera que la división por R sea fácil, lo que mejora significativamente la velocidad del algoritmo. En la práctica, R siempre es una potencia de dos, ya que la división por potencias de dos se puede implementar mediante desplazamiento de bits .
La necesidad de convertir a y b en la forma Montgomery y su producto a partir de la forma Montgomery significa que calcular un único producto mediante la multiplicación de Montgomery es más lento que los algoritmos convencionales o de reducción de Barrett . Sin embargo, cuando se realizan muchas multiplicaciones seguidas, como en la exponenciación modular , los resultados intermedios se pueden dejar en la forma Montgomery. Entonces, las conversiones inicial y final se convierten en una fracción insignificante del cálculo general. Muchos criptosistemas importantes, como RSA y el intercambio de claves Diffie-Hellman, se basan en operaciones aritméticas módulo un número impar grande y, para estos criptosistemas, los cálculos que utilizan la multiplicación de Montgomery con R una potencia de dos son más rápidos que las alternativas disponibles. [3]
Sea N un entero positivo módulo. El anillo cociente Z / N Z consta de clases de residuos módulo N , es decir, sus elementos son conjuntos de la forma
donde a abarca los números enteros. Cada clase de residuo es un conjunto de números enteros tal que la diferencia de dos números enteros cualesquiera en el conjunto es divisible por N (y la clase de residuo es máxima con respecto a esa propiedad; los números enteros no se excluyen de la clase de residuo a menos que violen la condición de divisibilidad). La clase de residuo correspondiente a a se denota a . La igualdad de clases de residuo se llama congruencia y se denota
Almacenar una clase de residuo completa en una computadora es imposible porque la clase de residuo tiene infinitos elementos. En cambio, las clases de residuo se almacenan como representantes. Convencionalmente, estos representantes son los números enteros a para los cuales 0 ≤ a ≤ N − 1 . Si a es un número entero, entonces el representante de a se escribe a mod N . Al escribir congruencias, es común identificar un número entero con la clase de residuo que representa. Con esta convención, la igualdad anterior se escribe a ≡ b mod N .
La aritmética de las clases de residuos se realiza primero realizando la aritmética de números enteros en sus representantes. La salida de la operación de números enteros determina una clase de residuo, y la salida de la operación modular se determina calculando el representante de la clase de residuo. Por ejemplo, si N = 17 , entonces la suma de las clases de residuos 7 y 15 se calcula hallando la suma de números enteros 7 + 15 = 22 y luego determinando 22 mod 17 , el número entero entre 0 y 16 cuya diferencia con 22 es un múltiplo de 17. En este caso, ese número entero es 5, por lo que 7 + 15 ≡ 5 mod 17 .
Si a y b son números enteros en el rango [0, N − 1] , entonces su suma está en el rango [0, 2 N − 2] y su diferencia está en el rango [− N + 1, N − 1] , por lo que determinar el representante en [0, N − 1] requiere como máximo una resta o una suma (respectivamente) de N . Sin embargo, el producto ab está en el rango [0, N 2 − 2 N + 1] . Almacenar el producto entero intermedio ab requiere el doble de bits que a o b , y determinar eficientemente el representante en [0, N − 1] requiere una división. Matemáticamente, el número entero entre 0 y N − 1 que es congruente con ab se puede expresar aplicando el teorema de la división euclidiana :
donde q es el cociente y r , el resto, está en el intervalo [0, N − 1] . El resto r es ab mod N . La determinación de r se puede realizar calculando q y luego restando qN de ab . Por ejemplo, nuevamente con , el producto 7 ⋅ 15 se determina calculando , dividiendo y restando .
Debido a que el cálculo de q requiere división, es indeseablemente costoso en la mayoría del hardware de las computadoras. La forma Montgomery es una forma diferente de expresar los elementos del anillo en la que se pueden calcular productos modulares sin divisiones costosas. Si bien las divisiones siguen siendo necesarias, se pueden realizar con respecto a un divisor diferente R . Este divisor se puede elegir para que sea una potencia de dos, para la cual la división se puede reemplazar por desplazamiento, o un número entero de palabras de máquina, para las cuales la división se puede reemplazar por omisión de palabras. Estas divisiones son rápidas, por lo que la mayor parte del costo de calcular productos modulares utilizando la forma Montgomery es el costo de calcular productos ordinarios.
El módulo auxiliar R debe ser un entero positivo tal que mcd( R , N ) = 1 . Para fines computacionales también es necesario que la división y la reducción módulo R sean económicas, y el módulo no es útil para la multiplicación modular a menos que R > N . La forma de Montgomery de la clase de residuo a con respecto a R es aR mod N , es decir, es el representante de la clase de residuo aR . Por ejemplo, supongamos que N = 17 y que R = 100 . Las formas de Montgomery de 3, 5, 7 y 15 son 300 mod 17 = 11 , 500 mod 17 = 7 , 700 mod 17 = 3 y 1500 mod 17 = 4 .
La suma y la resta en forma de Montgomery son iguales a la suma y resta modular ordinaria debido a la ley distributiva:
Nótese que al realizar la operación en forma Montgomery no se pierde información en comparación con hacerlo en el anillo de cocientes Z / N Z . Esto es consecuencia de que, como mcd( R , N ) = 1 , la multiplicación por R es un isomorfismo en el grupo aditivo Z / N Z . Por ejemplo, (7 + 15) mod 17 = 5 , que en forma Montgomery se convierte en (3 + 4) mod 17 = 7 .
Sin embargo, la multiplicación en forma Montgomery es aparentemente más complicada. El producto habitual de aR y bR no representa el producto de a y b porque tiene un factor adicional de R :
Para calcular productos en forma Montgomery es necesario eliminar el factor adicional de R. Si bien la división por R es barata, el producto intermedio ( aR mod N )( bR mod N ) no es divisible por R porque la operación de módulo ha destruido esa propiedad. Por ejemplo, el producto de las formas Montgomery de 7 y 15 módulo 17, con R = 100 , es el producto de 3 y 4, que es 12. Como 12 no es divisible por 100, se requiere un esfuerzo adicional para eliminar el factor adicional de R .
La eliminación del factor extra de R se puede realizar multiplicando por un entero R ′ tal que RR ′ ≡ 1 (mod N ) , es decir, por un R ′ cuya clase de residuo es el inverso modular de R mod N . Entonces, trabajando módulo N ,
El número entero R ′ existe debido a la suposición de que R y N son coprimos. Se puede construir utilizando el algoritmo euclidiano extendido . El algoritmo euclidiano extendido determina de manera eficiente los números enteros R ′ y N ′ que satisfacen la identidad de Bézout : 0 < R ′ < N , 0 < N ′ < R , y:
Esto demuestra que es posible realizar la multiplicación en forma Montgomery. Por lo tanto, un algoritmo sencillo para multiplicar números en forma Montgomery es multiplicar aR mod N , bR mod N y R ′ como números enteros y reducirlos módulo N .
Por ejemplo, para multiplicar 7 y 15 módulo 17 en la forma Montgomery, nuevamente con R = 100 , calcule el producto de 3 y 4 para obtener 12 como se indicó anteriormente. El algoritmo euclidiano extendido implica que 8⋅100 − 47⋅17 = 1 , por lo que R ′ = 8. Multiplique 12 por 8 para obtener 96 y reduzca módulo 17 para obtener 11. Esta es la forma Montgomery de 3, como se esperaba.
Si bien el algoritmo anterior es correcto, es más lento que la multiplicación en la representación estándar debido a la necesidad de multiplicar por R ′ y dividir por N . La reducción de Montgomery , también conocida como REDC, es un algoritmo que calcula simultáneamente el producto por R ′ y reduce módulo N más rápidamente que el método ingenuo. A diferencia de la reducción modular convencional, que se centra en hacer que el número sea más pequeño que N , la reducción de Montgomery se centra en hacer que el número sea más divisible por R . Lo hace añadiendo un pequeño múltiplo de N que se elige sofisticadamente para cancelar el residuo módulo R . Dividir el resultado por R produce un número mucho más pequeño. Este número es tanto más pequeño que es casi la reducción módulo N , y calcular la reducción módulo N requiere solo una resta condicional final. Debido a que todos los cálculos se realizan utilizando solo reducción y divisiones con respecto a R , no a N , el algoritmo se ejecuta más rápido que una reducción modular sencilla por división.
La función REDC se ingresa como: números enteros R y N con mcd( R , N ) = 1 , Entero N ′ en [0, R − 1] tal que NN ′ ≡ −1 mod R , Entero T en el rango [0, RN − 1] . salida: Entero S en el rango [0, N − 1] tal que S ≡ TR −1 mod N m ← (( T mod R ) N ′) mod R t ← ( T + mN ) / R si t ≥ N entonces devuelve t − N de lo contrario devuelve t fin si fin de la función
Para comprobar que este algoritmo es correcto, observemos primero que m se elige precisamente de modo que T + mN sea divisible por R. Un número es divisible por R si y sólo si es congruente con cero módulo R , y tenemos:
Por lo tanto, t es un entero. En segundo lugar, la salida es t o t − N , ambas congruentes con t mod N , por lo que para demostrar que la salida es congruente con TR −1 mod N , basta con demostrar que t es TR −1 mod N , t satisface:
Por lo tanto, la salida tiene la clase de residuo correcta. En tercer lugar, m está en [0, R − 1] y, por lo tanto, T + mN está entre 0 y ( RN − 1) + ( R − 1) N < 2 RN . Por lo tanto, t es menor que 2 N y, como es un entero, esto coloca a t en el rango [0, 2 N − 1] . Por lo tanto, reducir t al rango deseado requiere como máximo una única resta, por lo que la salida del algoritmo se encuentra en el rango correcto.
Para utilizar REDC para calcular el producto de 7 y 15 módulo 17, primero convierta a la forma Montgomery y multiplique como enteros para obtener 12 como se indicó anteriormente. Luego aplique REDC con R = 100 , N = 17 , N ′ = 47 y T = 12. El primer paso establece m en 12 ⋅ 47 mod 100 = 64. El segundo paso establece t en (12 + 64 ⋅ 17) / 100. Observe que 12 + 64 ⋅ 17 es 1100, un múltiplo de 100 como se esperaba. t se establece en 11, que es menor que 17, por lo que el resultado final es 11, lo que concuerda con el cálculo de la sección anterior.
Como otro ejemplo, considere el producto 7 ⋅ 15 mod 17 pero con R = 10 . Usando el algoritmo euclidiano extendido, calcule −5 ⋅ 10 + 3 ⋅ 17 = 1 , entonces N ′ será −3 mod 10 = 7 . Las formas de Montgomery de 7 y 15 son 70 mod 17 = 2 y 150 mod 17 = 14 , respectivamente. Su producto 28 es la entrada T a REDC, y dado que 28 < RN = 170 , se satisfacen los supuestos de REDC. Para ejecutar REDC, establezca m en (28 mod 10) ⋅ 7 mod 10 = 196 mod 10 = 6 . Entonces 28 + 6 ⋅ 17 = 130 , entonces t = 13 . Como 30 mod 17 = 13 , esta es la forma de Montgomery de 3 = 7 ⋅ 15 mod 17 .
Muchas operaciones de interés módulo N se pueden expresar igualmente bien en forma Montgomery. La suma, la resta, la negación, la comparación para determinar la igualdad, la multiplicación por un entero que no esté en forma Montgomery y los máximos divisores comunes con N se pueden realizar con los algoritmos estándar. El símbolo de Jacobi se puede calcular siempre que se almacene.
Cuando R > N , la mayoría de las demás operaciones aritméticas se pueden expresar en términos de REDC. Esta suposición implica que el producto de dos representantes mod N es menor que RN , la hipótesis exacta necesaria para que REDC genere una salida correcta. En particular, el producto de aR mod N y bR mod N es REDC(( aR mod N )( bR mod N )) . La operación combinada de multiplicación y REDC a menudo se denomina multiplicación de Montgomery .
La conversión a la forma Montgomery se realiza calculando REDC(( a mod N )( R 2 mod N )) . La conversión fuera de la forma Montgomery se realiza calculando REDC( aR mod N ) . La inversa modular de aR mod N es REDC(( aR mod N ) −1 ( R 3 mod N )) . La exponenciación modular se puede realizar utilizando la exponenciación por cuadrado inicializando el producto inicial a la representación Montgomery de 1, es decir, a R mod N , y reemplazando los pasos de multiplicación y cuadrado por multiplicaciones de Montgomery.
Para realizar estas operaciones es necesario conocer al menos N ′ y R 2 mod N . Cuando R es una potencia de un entero positivo pequeño b , N ′ se puede calcular mediante el lema de Hensel : La inversa de N módulo b se calcula mediante un algoritmo ingenuo (por ejemplo, si b = 2, entonces la inversa es 1), y el lema de Hensel se utiliza repetidamente para encontrar la inversa módulo potencias cada vez más altas de b , deteniéndose cuando se conoce la inversa módulo R ; N ′ es la negación de esta inversa. Las constantes R mod N y R 3 mod N se pueden generar como REDC( R 2 mod N ) y como REDC(( R 2 mod N )( R 2 mod N )) . La operación fundamental es calcular la REDC de un producto. Cuando se necesita una REDC independiente, se puede calcular como la REDC de un producto con 1 mod N . El único lugar donde es necesaria una reducción directa módulo N es en el precálculo de R 2 mod N .
La mayoría de las aplicaciones criptográficas requieren números de cientos o incluso miles de bits de longitud. Estos números son demasiado grandes para almacenarse en una sola palabra de máquina. Normalmente, el hardware realiza una multiplicación con una base B , por lo que realizar multiplicaciones mayores requiere combinar varias multiplicaciones pequeñas. La base B suele ser 2 para aplicaciones microelectrónicas, 2 8 para firmware de 8 bits [4] o 2 32 o 2 64 para aplicaciones de software.
El algoritmo REDC requiere productos módulo R , y típicamente R > N para que REDC pueda usarse para calcular productos. Sin embargo, cuando R es una potencia de B , hay una variante de REDC que requiere productos solo de números enteros del tamaño de una palabra de máquina. Supongamos que los números enteros positivos de precisión múltiple se almacenan en little endian , es decir, x se almacena como una matriz x [0], ..., x [ℓ - 1] tal que 0 ≤ x [ i ] < B para todo i y x = ∑ x [ i ] B i . El algoritmo comienza con un número entero de precisión múltiple T y lo reduce una palabra a la vez. Primero se suma un múltiplo apropiado de N para hacer que T sea divisible por B . Luego se suma un múltiplo de N para hacer que T sea divisible por B 2 , y así sucesivamente. Finalmente, T es divisible por R , y después de la división por R el algoritmo está en el mismo lugar que REDC después del cálculo de t .
La función MultiPrecisionREDC es Entrada: Entero N con mcd( B , N ) = 1 , almacenado como una matriz de p palabras, Entero R = B r , --por lo tanto, r = log B R Entero N ′ en [0, B − 1] tal que NN ′ ≡ −1 (mod B ) , Entero T en el rango 0 ≤ T < RN , almacenado como una matriz de r + p palabras. Salida: entero S en [0, N − 1] tal que TR −1 ≡ S (mod N ) , almacenado como una matriz de p palabras. Establezca T [ r + p ] = 0 (palabra de acarreo adicional) para 0 ≤ i < r. Haga --loop1- Haga que T sea divisible por B i+1 c ← 0 m ← T [ i ] ⋅ N ′ mod B para 0 ≤ j < p do --loop2- Sume m ⋅ N[j] y el acarreo de antes, y encuentre el nuevo acarreo x ← T [ i + j ] + m ⋅ N [ j ] + c T [ i + j ] ← x mod B c ← ⌊ x / B ⌋ fin para para p ≤ j ≤ r + p − i hacer --loop3- Continuar llevando x ← T [ i + j ] + c T [ i + j ] ← x mod B c ← ⌊ x / B ⌋ fin para fin para para 0 ≤ i ≤ p hacer S [ i ] ← T [ i + r ] fin para si S ≥ N entonces devuelve S − N de lo contrario devuelve S fin si fin de función
La comparación y resta final se realiza mediante los algoritmos estándar.
El algoritmo anterior es correcto básicamente por las mismas razones por las que REDC es correcto. Cada vez que se pasa por el i bucle, se elige m de modo que T [ i ] + mN [0] sea divisible por B . Luego, se suma mNB i a T . Debido a que esta cantidad es cero mod N , su suma no afecta el valor de T mod N . Si m i denota el valor de m calculado en la i ésima iteración del bucle, entonces el algoritmo establece S en T + (∑ m i B i ) N . Debido a que MultiPrecisionREDC y REDC producen el mismo resultado, esta suma es la misma que la elección de m que haría el algoritmo REDC.
La última palabra de T , T [ r + p ] (y en consecuencia S [ p ] ), se utiliza solo para almacenar un acarreo, ya que el resultado de la reducción inicial está ligado a un resultado en el rango de 0 ≤ S < 2N . De ello se deduce que esta palabra de acarreo adicional se puede evitar por completo si se sabe de antemano que R ≥ 2N . En una implementación binaria típica, esto es equivalente a decir que esta palabra de acarreo se puede evitar si el número de bits de N es menor que el número de bits de R. De lo contrario, el acarreo será cero o uno. Dependiendo del procesador, puede ser posible almacenar esta palabra como un indicador de acarreo en lugar de una palabra de tamaño completo.
Es posible combinar la multiplicación de precisión múltiple y REDC en un único algoritmo. Este algoritmo combinado suele denominarse multiplicación de Montgomery. Koç, Acar y Kaliski describen varias implementaciones diferentes. [5] El algoritmo puede utilizar tan solo p + 2 palabras de almacenamiento (más un bit de acarreo).
Como ejemplo, sea B = 10 , N = 997 y R = 1000 . Supongamos que a = 314 y b = 271 . Las representaciones de Montgomery de a y b son 314000 mod 997 = 942 y 271000 mod 997 = 813 . Calcule 942 ⋅ 813 = 765846 . La entrada inicial T para MultiPrecisionREDC será [6, 4, 8, 5, 6, 7]. El número N se representará como [7, 9, 9]. El algoritmo euclidiano extendido dice que −299 ⋅ 10 + 3 ⋅ 997 = 1 , por lo que N ′ será 7.
yo ← 0m ← 6 ⋅ 7 módulo 10 = 2y T c- ------- -0 0485670 2 (Después de la primera iteración del primer bucle)1 0485670 22 0485670 23 0487670 0 (Después de la primera iteración del segundo bucle)4 0487670 05 0487670 06 0487670 0yo ← 1m ← 4 ⋅ 7 módulo 10 = 8y T c- ------- -0 0087670 6 (Después de la primera iteración del primer bucle)1 0067670 82 0067670 83 0067470 1 (Después de la primera iteración del segundo bucle)4 0067480 05 0067480 0yo ← 2m ← 6 ⋅ 7 módulo 10 = 2y T c- ------- -0 0007480 2 (Después de la primera iteración del primer bucle)1 0007480 22 0007480 23 0007400 1 (Después de la primera iteración del segundo bucle)4 0007401 0
Por lo tanto, antes de la comparación y resta final, S = 1047. La resta final da como resultado el número 50. Dado que la representación de Montgomery de 314 ⋅ 271 mod 997 = 349 es 349000 mod 997 = 50 , este es el resultado esperado.
Cuando se trabaja en base 2, determinar la m correcta en cada etapa es particularmente fácil: si el bit de trabajo actual es par, entonces m es cero y si es impar, entonces m es uno. Además, debido a que cada paso de MultiPrecisionREDC requiere conocer solo el bit más bajo, la multiplicación de Montgomery se puede combinar fácilmente con un sumador con ahorro de acarreo .
Debido a que la reducción de Montgomery evita los pasos de corrección requeridos en la división convencional cuando las estimaciones de los dígitos del cociente son inexactas, está mayormente libre de las ramas condicionales que son los objetivos principales de los ataques de canal lateral de tiempo y potencia ; la secuencia de instrucciones ejecutadas es independiente de los valores de los operandos de entrada. La única excepción es la resta condicional final del módulo, pero se modifica fácilmente (para restar siempre algo, ya sea el módulo o cero) para hacerla resistente. [4] Por supuesto, es necesario garantizar que el algoritmo de exponenciación construido alrededor de la primitiva de multiplicación también sea resistente. [4] [6]
