这些话加在前面吧，因为这是修改的内容
程序出现了BUG
在计算幂取模的时候出现了错误
其实最重要的是私钥d可能会是负数，我并没有取整数的模（一直错在这，我以为可以。。。。）
其实此次学习最重要的是发现了-1右移等于-1吧。。。
代码我就直接替换掉新的了。。。
花了几天的时间终于搞定了NSGA-II，周三晚开完会讨论之后无误就来发表
今晚烦燥，就来复习信安基础了，做了个简单的RSA
只能计算Int范围内的，即p,q的选取在int范围内而且p*q不能超过int
写了也算一个学习经历吧，就到这里记录一下
代码里Miller_Robin是不需要的，只是写一下
Miller_Robin和Prime_Linear函数都是直接贴模板的，稍微作了点改动吧~
其实一看就知道，没注释的就是我写的，注释的就不是我的（太懒了，不喜欢写注释，反正这个写着自己看Orz)
其实为了自己看的懂，还做了“无用功”，有些输入的提示
下面是结果
p=11,q=17
e=7 --->通过扩展欧几里得求出 d=23
明文M=88 --->C=11
密文C=11 --->M=88
如果哪位对弱菜我的小程序感兴趣，测试之后发现有BUG还望提出啊Orz.........................
下面就上代码了~~~~
#include<cstdio> #include<cstring> #include<ctime> #include<cstdlib> const int maxn = 10000000; bool IsNotPrime[maxn]; // 判断是否为素数. int PrimeList[maxn]; // 素数列表. int PrimeNum; void Prime_Linear(void) { // 速度比朴素筛法快2倍以上，该筛法进行稍微修改即可用于求欧拉函数Phi[]. int i, j; memset(IsNotPrime, 0, sizeof(IsNotPrime)); // 初始赋值所有数都是素数. IsNotPrime[1] = 1; IsNotPrime[0] = 1; // 0和1不是素数. PrimeList[0]=2; for (i = 4; i < maxn; i += 2) IsNotPrime[i] = 1; // 除2以外的所有偶数都不是素数. PrimeNum = 1; for (i = 3; i < maxn; i += 2) { if (!IsNotPrime[i]) { // 如果是素数则加入素数列表. PrimeList[PrimeNum++] = i; } // 注意：这里与朴素筛法不同，即使合数也要进行筛. // 因为这里素数只筛它的素数倍，那么有些合数就可能没被筛掉. // 而这些合数就需要合数来晒，而且只要筛到它的最小质因子倍即可(想想为什么?). for (j = 0; j < PrimeNum && i * PrimeList[j] < maxn; j++) { IsNotPrime[i * PrimeList[j]] = 1; if (i % PrimeList[j] == 0) { // 说明PrimeList[j]是i的最小质因子，即i * PrimeList[j]的最小质因子，则跳出. break; } } } } int Modular_Exponent(int a, int b, int MOD) { // a ^ b mod MOD. int temp(1); int aa(a); while (b) { if (b & 1) temp = 1LL * temp * aa % MOD; aa = 1LL * aa * aa % MOD; b >>= 1; } return temp; } // Carmicheal number: 561,41041,825265,321197185 bool Miller_Rabin(int n, int time = 20) { // 如果是素数，则返回1，否则返回0. if (n == 1 || (n != 2 && !(n % 2)) || (n != 3 && !(n % 3)) || (n != 5 && !(n % 5)) || (n != 7 && !(n % 7))) return 0; while (time--) { if (Modular_Exponent(((rand() & 0x7fff << 16) + rand() & 0x7fff + rand() & 0x7fff) % (n-1) + 1, n - 1, n) != 1) return 0; } return 1; } void ext_gcd(int a,int b,int&x,int&y){ if(!b){ x=1,y=0; return; } ext_gcd(b,a%b,x,y); int t=x; x=y; y=t-a/b*y; } int gcd(int a,int b){return b?gcd(b,a%b):a;} int init(int p,int q,int &e){ //Prime_Linear(); int eular_n=(p-1)*(q-1); puts("please input a prime nunber as your public key"); while(true){ scanf("%d",&e); if(IsNotPrime[e] || gcd(e,eular_n)!=1){ puts("wrong input,please input again~"); continue; } break; } int d,y; ext_gcd(e,eular_n,d,y); return (d+eular_n)%eular_n; } void exponent(int a,const int e,int n,int select){ int ret=1; int b=e; for(;b;b=(b==-1)?0:(b>>1),a=(int)((long long)a)*a%n) //for(;b;b/=2,a=(int)((long long)a)*a%n) if(b&1) ret=(int)((long long)ret)*a%n; switch(select){ case 1:printf("your ciphertext is %d\n",ret%n);break; case 2:printf("your plaintext is %d\n",ret%n); } } int main(){ Prime_Linear();//初始化，素数打表 //for(int i=0;i<10;i++)printf("%d\n",PrimeList[i]); //for(int i=0;i<10;i++)printf("%d\n",IsNotPrime[i]); int p,q,e; loop: puts("please input two prime number"); scanf("%d%d",&p,&q); //if(!Miller_Rabin(p)||!Miller_Rabin(q) || if(IsNotPrime[p] || IsNotPrime[q] || (long long)p+(long long)q>(~0U>>1)){ puts("your inputs is wrong,please input again~"); goto loop; } int d=init(p,q,e); //printf("%d\n",d); int select; while(true){ puts("please select it"); puts("1: encryption"); puts("2: decryption"); while(true){ scanf("%d",&select); if(select!=1 && select!=2){ puts("wrong input,please input again~"); continue; } break; } //puts("yes"); switch(select){ case 1:puts("please input a message");break; case 2:puts("please input a cyphertext"); } int m; scanf("%d",&m); switch(select){ case 1:exponent(m,e,p*q,select);break; case 2:exponent(m,d,p*q,select); } } }