RSA算法正确性验证

RSA算法求解公钥和私钥

代码

#include<iostream>
#include<cstring>
using namespace std;

int P2p(int fn,int e){
    // cout<<fn<<" "<<e<<endl;
    if(fn == 1 || e == 1) return 1;
    if(fn > e){
        return (fn*P2p(fn % e, e) + 1)/e;
    }
    return (e*P2p(fn,e % fn)-1)/fn;
}

int Encrypt(int C,int e,int p,int q){
    int n = p*q,M=1;
    // 低效加密算法（可以使用二进制优化）
    while(e--){
        M = (M*C) % n;
    }
    return M;
}

int Decrypt(int M,int d,int p,int q){
    int n=p*q,C=1;
    while(d--){
        C = (C*M) % n;
    }
    return C;
}


int main(){
    // RSA(p,q,e)已知公钥求私钥，已知私钥求公钥算法
    int p,q,e;
    cin>>p>>q>> e;
    int d=P2p((p-1)*(q-1),e);
    // cout<<d<<endl;
    char str[]="HAPPY WEEK END";
    for(int i=0;i<5;i++){
        int M = str[i] - 'A' + 1;
        int C = Encrypt(M,d,p,q);
        cout <<C<<" "<<char(Decrypt(C,e,p,q)-1+'A')<<endl;
    }// 验证RSA加密解密算法的正确性
    return 0;
}