Cálculo de pow (a, b) mod n

Quiero calcular un mod de b para usar en el descifrado de RSA. Mi código (a continuación) devuelve respuestas incorrectas. ¿Qué tiene de malo?

unsigned long int decrypt2(int a,int b,int n) { unsigned long int res = 1; for (int i = 0; i < (b / 2); i++) { res *= ((a * a) % n); res %= n; } if (b % n == 1) res *=a; res %=n; return res; } 

Puedes probar este código C ++. Lo he usado con enteros de 32 y 64 bits. Estoy seguro de que obtuve esto de TAN.

 template  T modpow(T base, T exp, T modulus) { base %= modulus; T result = 1; while (exp > 0) { if (exp & 1) result = (result * base) % modulus; base = (base * base) % modulus; exp >>= 1; } return result; } 

Puede encontrar este algoritmo y discusión relacionada en la literatura el p. 244 de

 Schneier, Bruce (1996). Applied Cryptography: Protocols, Algorithms, and Source Code in C, Second Edition (2nd ed.). Wiley. ISBN 978-0-471-11709-4. 

Para calcular pow(a,b) % n que se utilizará para el descifrado de RSA, el mejor algoritmo que encontré es Primality Testing 1) que es el siguiente:

  int modulo(int a, int b, int n){ long long x=1, y=a; while (b > 0) { if (b%2 == 1) { x = (x*y) % n; // multiplying with base } y = (y*y) % n; // squaring the base b /= 2; } return x % n; } 

Consulte la referencia a continuación para obtener más detalles.


1) Prueba de primalidad: Algoritmos no deterministas – topcoder

Por lo general, es algo como esto:

 while (b) { if (b % 2) { res = (res * a) % n; } a = (a * a) % n; b /= 2; } return res; 

El único error lógico real que veo es esta línea:

 if (b % n == 1) 

que debería ser esto:

 if (b % 2 == 1) 

Pero su diseño general es problemático: su función realiza O (b) multiplicaciones y operaciones de módulo, pero su uso de b / 2 y a * a implica que usted tenía el objective de realizar operaciones O (log b) (que es por lo general la exponenciación modular) está hecho).

Realizar la operación de potencia sin procesar es muy costoso, por lo tanto, puede aplicar la siguiente lógica para simplificar el descifrado.

Desde aquí ,

Ahora digamos que queremos encriptar el mensaje m = 7,
c = m ^ e mod n = 7 ^ 3 mod 33 = 343 mod 33 = 13.
De ahí el texto cifrado c = 13.

Para verificar el descifrado calculamos
m ‘= c ^ d mod n = 13 ^ 7 mod 33 = 7.
Tenga en cuenta que no tenemos que calcular el valor completo de 13 a la potencia 7 aquí. Podemos hacer uso del hecho de que
a = bc mod n = (b mod n). (c mod n) mod n
por lo que podemos dividir un número potencialmente grande en sus componentes y combinar los resultados de cálculos más pequeños y más fáciles para calcular el valor final.

Una forma de calcular m ‘es la siguiente:
Tenga en cuenta que cualquier número se puede express como una sum de potencias de 2. Entonces, primero calcule los valores de
13 ^ 2, 13 ^ 4, 13 ^ 8, … al cuadrar repetidamente los valores sucesivos módulo 33. 13 ^ 2 = 169 ≡ 4, 13 ^ 4 = 4.4 = 16, 13 ^ 8 = 16.16 = 256 ≡ 25.
Entonces, dado que 7 = 4 + 2 + 1, tenemos m ‘= 13 ^ 7 = 13 ^ (4 + 2 + 1) = 13 ^ 4.13 ^ 2.13 ^ 1
≡ 16 x 4 x 13 = 832 ≡ 7 mod 33

¿Estás tratando de calcular (a^b)%n , o a^(b%n) ?

Si quieres el primero, entonces tu código solo funciona cuando b es un número par, debido a eso b / 2 . El ” if b%n==1 ” es incorrecto porque no te importa b%n aquí, sino más bien aproximadamente b%2 .

Si quiere el segundo, entonces el ciclo está mal porque está haciendo un bucle b / 2 veces en lugar de (b% n) / 2 veces.

De cualquier forma, tu función es innecesariamente compleja. ¿Por qué bucle hasta b / 2 e intenta multiplicar en 2 a cada vez? ¿Por qué no simplemente bucle hasta b y mulitply en uno cada vez. Eso eliminaría una gran cantidad de complejidad innecesaria y, por lo tanto, eliminaría posibles errores. ¿Estás pensando que harás que el progtwig sea más rápido reduciendo la cantidad de veces a la mitad? Francamente, esa es una mala práctica de progtwigción: micro-optimización. Realmente no ayuda mucho: todavía se multiplica por la misma cantidad de veces, todo lo que hace es reducir el número de veces que se prueba el ciclo. Si b es típicamente pequeño (como uno o dos dígitos), no vale la pena el problema. Si b es grande, si puede ser de millones, entonces esto es insuficiente, necesita una optimización mucho más radical.

Además, ¿por qué el %n cada vez a través del ciclo? ¿Por qué no solo hacerlo una vez al final?

int no son suficientes para RSA (a menos que se trate de pequeños ejemplos simplificados)

necesita un tipo de datos que pueda almacenar enteros hasta 2 256 (para claves RSA de 256 bits) o 2 512 para claves de 512 bits, etc.

Creo que tienes dos problemas. Primero, solo estás buscando un exponente impar una vez al final, no cada vez que pasas por el ciclo; dos, tu cheque para un exponente impar está mal.

Aquí hay una versión recursiva que funciona para un par de ejemplos que encontré en línea.

 unsigned long int decrypt2(int a,int b,int n) { unsigned long int res; if (b == 0) { res = 1; } else if (b % 2 == 1) { res = a * decrypt2( a, b-1, n ); } else { res = decrypt2( a, b/2, n ); res = (res*res)%n; } 

use la exponenciación rápida tal vez ….. da el mismo o (log n) que la plantilla anterior

  int power(int base, int exp,int mod) { if(exp == 0) return 1; int p=power(base, exp/2,mod); p=(p*p)% mod; return (exp%2 == 0)?p:(base * p)%mod; } 

Cálculo de pow (a, b) mod n

  1. Un problema clave con el código de OP es a * a . Esto es un desbordamiento de int (comportamiento indefinido) cuando a es lo suficientemente grande. El tipo de res es irrelevante en la multiplicación de a * a .

    La solución es asegurar ya sea:
    1) la multiplicación se hace con 2x de matemática amplia o
    2) con módulo n , n*n < = type_MAX + 1

  2. No hay razón para devolver un tipo más amplio que el tipo del módulo, ya que el resultado siempre se representa por ese tipo.

     // unsigned long int decrypt2(int a,int b,int n) int decrypt2(int a,int b,int n) 
  3. El uso de matemáticas sin signo es ciertamente más adecuado para los objectives RSA de OP.


 // (a^b)%n // n != 0 // Test if unsigned long long at least 2x values bits as unsigned #if ULLONG_MAX/UINT_MAX - 1 > UINT_MAX unsigned decrypt2(unsigned a, unsigned b, unsigned n) { unsigned long long result = 1u % n; // Insure result < n, even when n==1 while (b > 0) { if (b & 1) result = (result * a) % n; a = (1ULL * a * a) %n; b >>= 1; } return (unsigned) result; } #else unsigned decrypt2(unsigned a, unsigned b, unsigned n) { // Detect if UINT_MAX + 1 < n*n if (UINT_MAX/n < n-1) { return TBD_code_with_wider_math(a,b,n); } a %= n; unsigned result = 1u % n; while (b > 0) { if (b & 1) result = (result * a) % n; a = (a * a) % n; b >>= 1; } return result; } #endif 
 #include  ... static_cast(std::pow(a,b))%n 

pero mi mejor apuesta es que está desbordando int (IE: el número es dos grande para el int) en el poder tuve el mismo problema creando exactamente la misma función.

Estoy usando esta función:

 int CalculateMod(int base, int exp ,int mod){ int result; result = (int) pow(base,exp); result = result % mod; return result; } 

Analizo el resultado de la variable porque pow te devuelve un doble, y para usar mod necesitas dos variables de tipo int, de todos modos, en un descifrado RSA, solo debes usar números enteros.