#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <math.h>
int (int e,int fn);
int fun_2(int e,int fn);
int zhuan_huan(int b,int a[],int k);
int js_mod(int a,int b,int n);
*   主函数   *
*************/
void main()
{
    int p,q,e,d,n,fn;
    long m[10000],c[100000];//c[10000]存放加密后的数字密文，m[1000]存放解密后的数字明文，即英文明文在zimu_biao[69]中的下标。
    int i,j;        //i,j用于循环遍历数组
    int mi_yue;    //用户输入的密钥
    int count=1;    //统计输入密钥的次数，count>3时将不允许用户再输入。
    char min_wen[大专栏  RSA加密算法ass="number">10000],re_min_wen[10000];//分别为用户输入的明文、密文，解密后的明文。
//密钥生成
    char zimu_biao[69]="abcdefghijklmnopqrstuvwxyz,ABCDEFGHIJKLMNOPQRSTUVWXYZ 0123456789'.?!";
    printf("请输入您要发送的明文文件（小写英文表示）:n");
    printf("******************************************************n");
    gets(min_wen);
    printf("******************************************************n");
    srand((unsigned) time(NULL));
    printf("n加密开始nn");
    do
    {
    p=rand()%201+101;
    for(i=2;i<=sqrt(p);i++)
        {
            if(p%i==0)
                break;
        }
    }while(i<=sqrt(p));
    do
    {
    q=rand()%201+101;
    for(i=2;i<=sqrt(q);i++)
        {
            if(q%i==0)
                break;
        }
    }while(i<=sqrt(q)||q==p);
    n=p*q;
    fn=(p-1)*(q-1);
    do
    {
        e=rand()%(fn)+1;
    }while(fun_1(e,fn));
    d=fun_2(e,fn);        //求解密指数d
    printf("******************************************************n");
    printf("n明文长度:%dn",strlen(min_wen));
    printf("n您的两个大素数分别为p=%d(保密),q=%d(保密)n模数n=%d(公开),欧拉函数fn=%d(保密)n",p,q,n,fn);
    printf("Public Key:%10d %10d(公钥,公开)n",n,e);
    printf("Private Key:%10d %10d(私钥,保密)nn",n,d);
//明文转换过程
    for(i=0;i<strlen(min_wen);i++)
        for(j=0;j<68;j++)
            if(min_wen[i]==zimu_biao[j])
                m[i]=j;//将字符串明文换成数字，并存到整型数组m里面，即明文的另一种表示方法
//加密过程
    for(i=0;i<strlen(min_wen);i++)
        c[i]=js_mod(m[i],e,n);
    printf("输出密文：n");
    printf("******************************************************n");
    for(i=0;i<strlen(min_wen);i++)
        printf("%d",c[i]);
    printf("n******************************************************n");
//提示用户解密
    printf("nn您有3次输入密钥（只需要输入私钥的d）的机会，3次输入错误将无法解密nn");
    while(1)
        {
            scanf("%d",&mi_yue);
            if(mi_yue==d)
            {
                printf("密钥输入正确，您得到的明文为：nn");
                for(i=0;i<strlen(min_wen);i++)
                    m[i]=js_mod(c[i],d,n);
                for(i=0;i<strlen(min_wen);i++)
                    re_min_wen[i]=zimu_biao[m[i]];
                for(i=0;i<strlen(min_wen);i++)
                    printf("%c",re_min_wen[i]);
                printf("nn");
                break;
            }
            else
            {
                printf("您第%d次输入的密钥错误，请重新输入。。。n",count);
                count++;
                if(count>3)
                {
                    printf("n您已%d次输入的密钥错误，将不允许继续输入n",count-1);
                    break;
                }
            }
        }
}
//判断fn和e是否互素
int (int e,int fn)
{
    int i,null=0;
    for(i=2;i<=fn;i++)
    {
        if(e%i==0&&fn%i==0)
            null=1;
    }
    return null;
}
//扩展欧几里得算法求乘法逆元，即求解密指数d
int fun_2(int e,int fn)
{
    int d=1;
    while((e*d)%fn!=1)
    {
            d++;
    }
    return d;
}
//将十进制数转换成二进制
int zhuan_huan(int b,int a[],int k)
{
    int t,temp=-1;
    while(b>0){
        t=b%2;
        temp++;
        a[temp]=t;
        b=b/2;
    }
    return temp;
}
//快速计算模指数
int js_mod(int a,int b,int n)
{
    int x=0,y=1,k,i,s[1000];
    k=zhuan_huan(b,s,1000);
    for(i=k;i>=0;i--){
        x=2*x;
        y=(y*y)%n;
        if(s[i]==1){
            x++;
            y=(y*a)%n;
        }
    }
    return y;
}