Почему эта крошечная реализация RSA дает неправильные результаты? - PullRequest
Новая
       12

Почему эта крошечная реализация RSA дает неправильные результаты?

2 голосов
/ 09 июня 2011

Я пытаюсь реализовать простой процесс шифрования / дешифрования RSA, и я почти уверен, что получил правильные уравнения.Хотя, похоже, после шифрования не выводится правильное расшифрованное значение.Любые идеи?. 

//test program
#include <iostream>
#include <string.h>
#include <math.h>
using namespace std;
int gcd(int a, int b);

int main(){
    char character = 'A'; //character that is to be encrypted


    int p = 7;
    int q = 5;
    int e = 0; // just initializing to 0, assigning actual e value in the 1st for loop 


    int n = p*q;
    int phi = (p-1)*(q-1);
    int d = 0; // " " 2nd for loop

    //---------------------------finding 'e' with phi. where "1 < e < phi(n)"
    for (int i=2; i < phi; i++){
        if (gcd(i,phi) == 1){ //if gcd is 1
            e = i;
            break;
        }
    }
    //----------------------------

    //---------------------------finding 'd' 

    for (int i = 2; i < phi; i++){
        int temp = (e*i)%phi;
        if (temp == 1){
            d = i;
            break;
        }
    }

    printf("n:%d , e:%d , phi:%d , d:%d \n",n,e,phi,d);
    printf("\npublic key is:[%d,%d]\n",e,n);
    printf("private key is:[%d,%d]\n",d,n);

    int m = static_cast<int>(character); //converting to a number
    printf("\nconverted character num:%d\n",m);


    //Encryption part  ie. c = m^e MOD n
    int power = pow(m,e); // m^e
    int c = power%n;      // c = m^e MOD n. ie. encrypted character
    printf("\n\nEncrypted character number:%d\n",c);

    //decryption part,  ie. m = c^d MOD n
    power = pow(c,d);
    int m2 = power%n; 
    printf("\n\ndecrypted character number:%d\n",m2);


    return 0;
}

int gcd(int a, int b){
    int r;
    if (a < 0) a = -a;
    if (b < 0) b = -b;
    if (b > a) { 
        r = b; b = a; a = r;
    }
    while (b > 0) {
        r = a % b;
        a = b;
        b = r;
    }
    return a;
}

(Для теста используются простые числа 5 и 7)

Здесь я преобразовываю символ «А» в его числовое значение, котороеконечно 65. Когда я шифрую это значение, используя c = m^e MOD n (где m - преобразованное значение, то есть 65), это дает мне c как 25.

Теперь, чтобы полностью изменить процесс, я делаю m = c^d MOD n,что дает мне m как 30 ... что на самом деле не правильно, потому что это должно быть 65, нет?

Где именно я ошибся?

[править]

Является ли мой расчет d правильным?

Ответы [ 2 ]

6 голосов
/ 09 июня 2011

Зашифрованное сообщение m должно быть меньше n. Вы не можете использовать значения больше n, потому что вычисления выполняются по модулю n. В вашем случае m=65 и n=35. Таким образом, вы действительно получаете правильный ответ по модулю n, потому что 65 % 35 == 30.

2 голосов
/ 09 июня 2011

Это вызвано тем, что m больше или равно n, как @interjay уже ответил.

Но я обнаружил еще одну проблему с вашим кодом, мой вывод компилятора gcc4.1.2 24 для зашифрованного значения не 25. Это потому, что вы используете pow() функцию, а затем конвертируете результат (тип double) в int, что вызывает потеря точности .

Не используйте pow() функцию , вместо этого используйте квадрат и умножьте по модулю n алгоритм для вычисления c = m^e MOD n и m = c^d MOD n. Это быстрее, чем pow(), и вам не нужно будет небезопасно понижать результат до целого числа.

...