c++ 我的“RSA算法”代码并不适用于所有数字

pvabu6sv  于 2022-11-27  发布在  其他
关注(0)|答案(1)|浏览(116)

我写了这段代码,但它并不适用于所有数字。(RSA算法)

using namespace std;
int main () {
    int x;
    int p = 13;
    int q = 11;
    long n = p * q;
    long φ = (p - 1) * (q - 1);
    long e = φ - 1;
    long d = φ + e;
    cout<<"Plz enter a number.\n";
    cin>>x;
    long y = pow (x,e);
    long a = y % n;
    long b = pow (a,d);
    long c = b % n;
    cout<<"Original = "<<x<<endl;
    cout<<"Encrypted = "<<a<<endl;
    cout<<"Decrypted = "<<c<<endl;
    return 0;
}

对于某些数字,加密和解密显示相同数字,对于较大数字,它们显示随机数

yizd12fk

yizd12fk1#

简单地说,你不能在加密或解密阶段使用pow,因为首先,它是一个浮点函数,即使是整数参数的结果也不能保证是最好的返回值,转换为int可能会截断。
第二,你得到的数字很大,即使是很小的 n = pq amd,它也很可能是整数类型溢出,产生未定义的结果。
有更快的方法来获得结果,但有一种方法是自己计算幂,记住在RSA中它是模 n
所以,与其

long y = pow(x, e);

然后是y % n,写如下

long y = 1;
for (long i = 0; i < e; ++i){
    y = y * e % n;
}

有一些更快的方法可以被不错的RSA实现所使用,但是这一种方法有助于理解该方法。
此外,避免在源代码中出现isalnum将返回false的任何字符。
(我还没有仔细检查你的数学,特别是卡迈克尔函数,或者模乘逆函数。)

相关问题