南邮 | 算法分析与设计实验四：密码算法

题目：构造一个简单的RSA公开**系统。

程序代码

#include <iostream>
using namespace std;
int MOD;

//Óɹ«¿ªÃÜÔ¿eºÍn£¬Çó˽ÓÐÃÜÔ¿d
int ext_euclid(int a, int b, int &x, int &y) 
{ 
    if(b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    int gcd = ext_euclid(b, a % b, x, y);
    int t = x % MOD;
    x = y % MOD;
    y = ((t - a / b * x) % MOD + MOD) % MOD;
    return gcd;
}


int main()
{
    int p, q, i, d;
    cout << "ÇëÊäÈëÒ»¸öÖÊÊý p (for example: 101) :";
    cin >> p;
    cout << "ÇëÊäÈëÒ»¸öÖÊÊý q (for example: 113) :";
    cin >> q;
    int n = p * q;
    cout<<"·Ö×é¼ÓÃÜʱ£¬Ã¿¸ö·Ö×éµÄ´óС n ²»Äܳ¬¹ý p*q=";
    cout << n << endl;

    //ÇóµÃ¦Õ(n)=(p-1)*(q-1)µÄÖµ
    MOD = (p - 1) * (q - 1);
    cout << "Ä£¦Õ(n)=(p-1)*(q-1)=";
    cout << MOD << endl << endl;

    //Ñ¡È¡Óë¦Õ(n)»¥ÖʵĹ«Ô¿e
    int e;
    cout << "ÊäÈëÓë¦Õ(n)»¥ÖʵĹ«Ô¿ e (for example: 3533):";
    cin >> e;

    //ÓÉeºÍ¦Õ(n)Éú³É˽Կd
    int x, y;
    ext_euclid(e, MOD, d, y);
    while(d < 0) 
        d += MOD;
    cout << "ͨ¹ýµ÷ÓÃÀ©Õ¹Å·¼¸ÀïµÂËã·¨£¬ÇóµÃÃÜÔ¿dΪ£º" << d << endl;

    //ÀûÓÃÉú³ÉµÄ¹«Ô¿{e,n}¶ÔÃ÷ÎÄM½øÐмÓÃÜ
    int M, C;
    cout << "ÏÖÔÚ¹«Ô¿{e,n}¡¢Ë½Ô¿{d,n}¾ùÒÑÉú³ÉÍê±Ï¡£\n\nÇëÊäÈëÐèÒª´«ÊäµÄÃ÷ÎÄÄÚÈݽøÐмÓÃÜ(for example: 9726):";
    cin >> M;
    C = 1;
    for(i = 1; i <= e; i++)
        C = C * M % n;
    cout << "Ã÷ÎÄM=" << M << "¾­¼ÓÃܺóµÃµ½ÃÜÎÄC=M^e(mod n):" << C << endl;

    //ÀûÓÃÉú³ÉµÄ˽Կ˽Կ{e,n}¶ÔÃÜÎÄC½øÐнâÃÜ
    M = 1;
    for(i = 1; i <= d; i++)
        M = M * C % n;
    cout << "ÃÜÎÄC=" << C << "¾­½âÃܺóµÃµ½Ã÷ÎÄM=C^d(mod n):" << M << endl;
    return 0;
}

实验结果

质数p：101

质数q：113

公钥e：3533

明文内容：9726