這個微小的RSA實現爲什麼會給出錯誤的結果？

我試圖實現一個簡單的RSA加密/解密過程，我很確定我有正確的方式。儘管在加密後似乎沒有打印出正確的解密值。有任何想法嗎？。這個微小的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，用於測試）

在這裏，我的字符「A」轉換成其數字值這當然是65.當我加密此使用c = m^e MOD n值（其中m是轉換後的值，即，65）它給我C作爲25.

現在，扭轉過程中，我做m = c^d MOD n，這使我m 30 ...這確實是不正確，因爲它應該是65，不是？

我究竟在哪裏出錯了？

[編輯]

是我d計算正確嗎？

來源

2011-06-09 silent

如果'e'不爲零，它會工作嗎？ – Jay 2011-06-09 14:15:51

'int e = 0'只有一個虛擬的，e用在第一個for循環中要使用的實際e值重寫 – silent 2011-06-09 14:22:39

@Jay同樣用於'int d = 0'，我剛初始化它在開始時爲0，以便我可以在第二秒爲循環指定實際的'd'值 – silent 2011-06-09 14:26:15

加密消息m必須小於n。您不能使用大於n的值，因爲計算是以模n完成的。在你的情況m=65和n=35。所以你實際上得到了正確的答案n，因爲65 % 35 == 30。

來源

2011-06-09 14:44:07 interjay

我正在計算'd'嗎？ – silent 2011-06-09 14:59:07

@ sil3nt：這是正確的，但在p和q非常大時不可行。通常會使用[擴展歐幾里德算法]（http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm），請參閱[模塊乘法反相]（http://en.wikipedia.org/wiki/Modular_multiplicative_inverse）。 – interjay 2011-06-09 15:05:05

這是由於有m大於或等於n像@ interjay已經回答。

但是我發現你的代碼存在另一個問題，我的gcc4.1.2編譯器輸出24加密值不是25。這是因爲您使用pow()函數，然後將結果（它是double類型）轉換爲int，導致精度損失。

不要使用pow()功能，而是使用square and multiply modulo n算法計算c = m^e MOD n和m = c^d MOD n。它比pow()更快，您不需要將結果不安全地向下轉換爲整數。

來源

2011-06-09 15:11:04 dragon135

這個微小的RSA實現爲什麼會給出錯誤的結果？

回答

相關問題