Calculating pow(a,b) mod n

问题:

I want to calculate a^b mod n for use in RSA decryption. My code (below) returns incorrect answers. What is wrong with it?

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;
}

回答1:

You can try this C++ code. I\'ve used it with 32 and 64-bit integers. I\'m sure I got this from SO.

template <typename T>
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;
}

You can find this algorithm and related discussion in the literature on p. 244 of

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

---

Note that the multiplications result * base and base * base are subject to overflow in this simplified version. If the modulus is more than half the width of T (i.e. more than the square root of the maximum T value), then one should use a suitable modular multiplication algorithm instead - see the answers to Ways to do modulo multiplication with primitive types.

回答2:

In order to calculate pow(a,b) % n to be used for RSA decryption, the best algorithm I came across is Primality Testing ¹⁾ which is as follows:

 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;
}

See below reference for more details.

---

¹⁾ Primality Testing : Non-deterministic Algorithms – topcoder

回答3:

Usually it\'s something like this:

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

    a = (a * a) % n;
    b /= 2;
}

return res;

回答4:

The only actual logic error that I see is this line:

if (b % n == 1)

which should be this:

if (b % 2 == 1)

But your overall design is problematic: your function performs O(b) multiplications and modulus operations, but your use of b / 2 and a * a implies that you were aiming to perform O(log b) operations (which is usually how modular exponentiation is done).

回答5:

Doing the raw power operation is very costly, hence you can apply the following logic to simplify the decryption.

From here,

Now say we want to encrypt the message m = 7,
c = m^e mod n = 7^3 mod 33 = 343 mod 33 = 13.
Hence the ciphertext c = 13.

To check decryption we compute
m\' = c^d mod n = 13^7 mod 33 = 7.
Note that we don\'t have to calculate the full value of 13 to the power 7 here. We can make use of the fact that
a = bc mod n = (b mod n).(c mod n) mod n
so we can break down a potentially large number into its components and combine the results of easier, smaller calculations to calculate the final value.

One way of calculating m\' is as follows:-
Note that any number can be expressed as a sum of powers of 2. So first compute values of
13^2, 13^4, 13^8, ... by repeatedly squaring successive values modulo 33. 13^2 = 169 ≡ 4, 13^4 = 4.4 = 16, 13^8 = 16.16 = 256 ≡ 25.
Then, since 7 = 4 + 2 + 1, we have m\' = 13^7 = 13^(4+2+1) = 13^4.13^2.13^1
≡ 16 x 4 x 13 = 832 ≡ 7 mod 33

回答6:

Are you trying to calculate (a^b)%n, or a^(b%n) ?

If you want the first one, then your code only works when b is an even number, because of that b/2. The \"if b%n==1\" is incorrect because you don\'t care about b%n here, but rather about b%2.

If you want the second one, then the loop is wrong because you\'re looping b/2 times instead of (b%n)/2 times.

Either way, your function is unnecessarily complex. Why do you loop until b/2 and try to multiply in 2 a\'s each time? Why not just loop until b and mulitply in one a each time. That would eliminate a lot of unnecessary complexity and thus eliminate potential errors. Are you thinking that you\'ll make the program faster by cutting the number of times through the loop in half? Frankly, that\'s a bad programming practice: micro-optimization. It doesn\'t really help much: You still multiply by a the same number of times, all you do is cut down on the number of times testing the loop. If b is typically small (like one or two digits), it\'s not worth the trouble. If b is large -- if it can be in the millions -- then this is insufficient, you need a much more radical optimization.

Also, why do the %n each time through the loop? Why not just do it once at the end?

回答7:

Calculating pow(a,b) mod n

1. A key problem with OP\'s code is a * a. This is int overflow (undefined behavior) when a is large enough. The type of res is irrelevant in the multiplication of a * a.

   The solution is to ensure either:

   • the multiplication is done with 2x wide math or
   • with modulus n, n*n <= type_MAX + 1

2. There is no reason to return a wider type than the type of the modulus as the result is always represent by that type.

   // unsigned long int decrypt2(int a,int b,int n)
   int decrypt2(int a,int b,int n)
   

3. Using unsigned math is certainly more suitable for OP\'s RSA goals.

---

// (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

回答8:

int\'s are generally not enough for RSA (unless you are dealing with small simplified examples)

you need a data type that can store integers up to 2²⁵⁶ (for 256-bit RSA keys) or 2⁵¹² for 512-bit keys, etc

回答9:

This(encryption) is more of an algorithm design problem than a programming one. The important missing part is familiarity with modern algebra. I suggest that you look for a huge optimizatin in group theory and number theory. If n is a prime number, pow(a,n-1)%n==1 (assuming infinite digit integers).So, basically you need to calculate pow(a,b%(n-1))%n; According to group theory, you can find e such that every other number is equivalent to a power of e modulo n. Therefore the range [1..n-1] can be represented as a permutation on powers of e. Given the algorithm to find e for n and logarithm of a base e, calculations can be significantly simplified. Cryptography needs a tone of math background; I\'d rather be off that ground without enough background.

回答10:

use fast exponentiation maybe..... gives same o(log n) as that template above

    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;
}

回答11:

#include <cmath>
...
static_cast<int>(std::pow(a,b))%n

but my best bet is you are overflowing int (IE: the number is two large for the int) on the power I had the same problem creating the exact same function.

回答12:

I\'m using this function:

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

I parse the variable result because pow give you back a double, and for using mod you need two variables of type int, anyway, in a RSA decryption, you should just use integer numbers.