Модульное возведение в степень переполняется при использовании нескольких чисел uint_32 - PullRequest
Новая
       17

Модульное возведение в степень переполняется при использовании нескольких чисел uint_32

0 голосов
/ 28 августа 2018

Я пытаюсь реализовать подпись и проверку ключа RSA. Я использую модульное возведение в степень, где я сталкиваюсь с ошибками, возможно, из-за целочисленного переполнения. 

uint64_t modmult(uint64_t a,uint64_t b,uint64_t mod)
{

    if (a == 0 || b < mod / a)
        return ((uint64_t)a*b)%mod;
    uint64_t sum;
    sum = 0;
    while(b>0)
    {
        if(b&1)
            sum = (sum + a) % mod;
        a = (2*a) % mod;
        b>>=1;
    }
    return sum;
}
uint64_t modpow( uint64_t a,uint64_t b,uint64_t mod)
{

    uint64_t product,pseq;
    product=1;
    pseq=a%mod;
    while(b>0)
    {
        if(b&1)
            product=modmult(product,pseq,mod);
        pseq=modmult(pseq,pseq,mod);
        b>>=1;
    }
    return product;
}

вызов функции 

long long d = 2897297195663230443;
uint64_t n = 10136926879504331723;
modpow(1233,d,n);

n - это кратное двух беззнаковых простых чисел uint32_t (4063800743,2494444861) модульное возведение в степень результат 3148683887780272464, но должен быть 9640529604970470922

По сути, эта реализация не обрабатывает 64-целые беззнаковые значения n скважина

1 Ответ

0 голосов
/ 28 августа 2018

Проблема состоит в том, что из-за того, что модуль> 2 63 , шаг a + sum в вашей подпрограмме modmult может переполниться, потеряв немного. То же самое может случиться с 2*a.

Один из способов решения этой проблемы - добавить подпрограмму modadd: 

uint64_t modadd(uint_64_t a, uint64_t b, uint64_t mod) {
    if (a >= mod) a %= mod;    // precondition -- might not be needed if the caller can guarentee it.
    if (b >= mod) b %= mod;    // precondition -- might not be needed if the caller can guarentee it

    a += b;
    if (a >= mod || a < b) a -= mod;
    return a;
}

Затем используйте modadd(sum, a, mod) и modadd(a, a, mod) в вашей modmult рутине.

...