Шифрование RSA в C ++

Я хочу зашифровать (RSA) символ до целого числа, используя его значение ASCII. Например. 'a' зашифровано как 48.

Для шифрования: c=pow(m,e)%n, где c - зашифрованный текст, m - простой текст, а (e, n) - открытый ключ.

Если pow (m, e) большое, скажем 67 ^ 7, оно не поместится в int или long. Но если я использую double, я не могу использовать его с оператором модуля%. Итак, я написал эту функцию для шифрования с помощью цикла for:

int encrypt(int m, int e, int n)
{
    int res=m, i;
    for(i=0; i<e-1;i++)
        res=(res*res)%n;
    return res;
}

Это сработало для 67 ^ 7mod11, что составляет 67, но потом я узнал, что это не совсем правильно. Где я ошибся?


c++ encryption rsa math
person Frozen Crayon    schedule 22.08.2013    source источник
comment
Вы делаете e-1 квадрат, поэтому вычисляете m^(2^(e-1)) по модулю n. Вам понадобится res = (res*m)%n; для простого возведения в степень с помощью алгоритма повторного умножения.   -  person Daniel Fischer    schedule 22.08.2013
comment
Не могли бы вы написать это как ответ, чтобы я принял его?   -  person Frozen Crayon    schedule 22.08.2013
comment
+1 к @DanielFischer. Я собирался перейти к построению цепочки по модулю, только чтобы увидеть, что он уже есть, но в итерации не хватало одного цикла и использовался неправильный множитель. Ага. Хорошо поймал!   -  person WhozCraig    schedule 22.08.2013

Ответы (2)


arrow_upward
5
arrow_downward

Ваша петля

for(i=0; i<e-1;i++)
    res=(res*res)%n;

квадраты e-1 по модулю n, это означает, что вычисляется m^(2^(e-1)) по модулю n. Чтобы вычислить m^e по модулю n с помощью простого алгоритма, используйте

for(i = 0; i < e-1; ++i)
    res = (res*m) % n;

вместо.

Для более быстрого алгоритма, когда показатель степени больше, вы можете использовать возведение в степень путем повторного возведения в квадрат:

res = 1;
while (e > 0) {
    if (e % 2 != 0) {
        res = (m*res) % n;
    }
    m = (m*m) % n;
    e /= 2;
}
return res;
person Daniel Fischer    schedule 22.08.2013

arrow_upward
0
arrow_downward

Обычно при использовании параметров шифрования вы используете "big int" вместо int. Именно по этой причине.

Здесь есть несколько предложений: Библиотека Bigint (bigbit)

person TomF    schedule 22.08.2013
comment
Я не должен использовать внешнюю библиотеку. Сейчас я пытаюсь сделать это дома, но мне нужно выполнить это в Fedora в колледже, где нет доступа в Интернет. - person Frozen Crayon; 22.08.2013
comment
Что ж, тогда все, что я могу сказать, это реализовать большой int ... В любом случае это будет глупая практика, особенно если вы собираетесь валять дурака с компьютеризированной криптографией. - person TomF; 22.08.2013