作业4 RSA和大数因式分解

一、编程/分析作业（1分） 使用C或C++实现RSA算法。提交源程序及测试结果。 调用开源密码算法库，使用RSA加密算法加密一个字符串。 调用开源密码算法库，使用Rabin加密算法加密一个字符串。 二、课后习题 5.5 5.7 5.9 5.14 5.16 5.17 5.23 注： 编程题任选其一 课后习题任选其二。

#include 
#include 
#include 
#define RANDOM 1
#define UNIT 1
/* RANDOM and UNIT are used for creating random big integer */
using namespace std;
typedef __int64 SuperInt;

SuperInt random（void）;
SuperInt quickPowMod（SuperInt aSuperInt bSuperInt r）;
bool Miller_Rabbin（SuperInt n）;
bool testPrime（SuperInt n）;
SuperInt MultiplicativeInverse（SuperInt aSuperInt b）;    /* it is just to calculate b^（-1）mod a */

int main（）
{
    ofstream fout（“key.txt“）;
    BEGIN:SuperInt pqnabPhi_n;
    srand（time（NULL））;
    while（1）
    {
        p=random（）;
        q=random（）;
        if（testPrime（p）&&testPrime（q））
            break;
    }
    n=p*q;
    Phi_n=（p-1）*（q-1）;
    while（1）
    {
        b=random（）;
        if（b>1&&b        {
            a=MultiplicativeInverse（Phi_nb）;
            if（a>0） break;
        }
    }
    if（（a*b）%Phi_n!=1） 
        goto BEGIN;    /* the A must be the right result of b^（-1）mod Phi（n） */
    cout<<“public key is （“<    cout<<“private key is （“<    fout<<“public key is （“<    fout<<“private key is （“<    system（“pause“）;
    return 0;
}

SuperInt random（void）
{
    int ij;
    SuperInt result=0;
    for（i=0;i    {
        SuperInt temp=1;
        for（j=0;j            temp=temp*UNIT;
        result+=rand（）*temp;
    }
    return result;
}

SuperInt quickPowMod（SuperInt aSuperInt bSuperInt r）
{
    SuperInt ans=1buff=a;
    while（b）
    {
        if（b&1）
            ans=（ans*buff）%r;
        buff=（buff*buff）%r;
        b>>=1;
    }
    return ans;
}

bool Miller_Rabbin（SuperInt n）
{
    SuperInt r=0s=n-1j;
    SuperInt a=rand（）;
    if（n%a==0）
        return false;
    while（!（s&1））
    {
        s>>=1;
        r++;
    }
    SuperInt k=quickPowMod（asn）;
    if（k==1）
        return true;
    for（j=0;j        if（k==n-1）
            return true;
    return false;
}

bool testPrime（SuperInt n）
{
    for（int i=0;i<10;i++）
    {
        if（Miller_Rabbin（n）==0）
            return false;
    }
    return true;
}

SuperInt MultiplicativeInverse（SuperInt aSuperInt b）
{
    SuperInt tempA=atempB=btempT=0t=1;
    SuperInt q=tempA/tempB;
    SuperInt r=tempA-q*tempB;
    while（r>0）
    {
        SuperInt temp=（tempT-q*t）%a;
        tempT=t;
        t=temp;
        tempA=tempB;
        tempB=r;
        q=tempA/tempB;
        r=tempA-q*tempB;
    }
    if（tempB!=1） return 0;
    else         return t;
}

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2013-06-27 23:26  RSA算法\
     文件          68  2013-06-14 14:32  RSA算法\key.txt
     文件        2672  2013-06-14 14:31  RSA算法\RSA密钥生成系统.cpp
     文件      479782  2013-06-14 14:32  RSA算法\RSA密钥生成系统.exe
     文件        2146  2013-06-14 16:02  RSA算法\RSA算法.cpp
     文件      477593  2013-06-14 16:02  RSA算法\RSA算法.exe
     文件       58880  2013-06-27 23:26  密码学作业.doc