|
一、RSA大数加密原理
RSA加密是一种非对称加密，通过对一极大整数做因数分解的困难性来保证信息的安全性。可以在不直接传递密钥的情况下完成解密，这避免了直接传递密钥所造成的被破解的风险，保证了信息的安全性。由一对密钥（公钥和私钥）来进行加解密的过程，两者之间是由数学关系来确定的，通常私钥由个人保存，公钥是公开的。
二、算法描述 1、随机生成两个数组，筛选出素数P和q，且p与q互异； 2、计算n=p*q； 3、筛选出与n互素的数； 4、r=(q-1)*(p-1)； 5、找出e，re = 1 mod (p-1)(q-1)； 6、利用欧几里得扩展算法计算私钥d； 7、得到公钥：n，e；私钥：n，d； 8、对明文进行加密并输出加密后的密文和解密后的明文。
三、源代码 - #include<cstdio>
- #include<cstdlib>
- #include<ctime>
- typedef _int64 ll;
- int prime[10000];
- int nprime[100000];
- bool isPrime[100000]= {false};
- int check_prime() {//筛选出素数
- int p=0;//p，q为两个质数且（p!=q)
- for(int i=0;i<100000; ++i)
- isPrime[i]=true;//利用isPrime判断一个数是否为素数，先假定是一个素数
- isPrime[0]=isPrime[1]=false;//若不是，则将isPrime的值改为false
- for(int k=0; k<100000; ++k) {
- if(isPrime[k]) {
- prime[p++]=k;
- for(int j=2*k;j<100000;j+=k)
- isPrime[j]=false;
- }
- }
- return p;//若为素数则返回该随机得到的值赋给p
- }
- int gcd(int n,int r) {
- return !r?n:gcd(r,n%r);//求r和n的最大公约数
- }
- int check_Nprime(ll n) {//筛选与n互素的数
- int c=0;
- for(int i=2;i<n;++i)
- if(gcd(n,i)==1)
- nprime[c++]=i;
- return c;
- }
- ll extgcd(ll a,ll b,ll &x,ll &y) {
- ll d=a;
- if(b) {
- d=extgcd(b,a%b,y,x);//用欧几里得扩展算法计算私钥d
- y-=(a/b)*x;
- } else {
- x=1;
- y=0;
- }
- return d;
- }
- ll mod_pow(ll x,ll n,ll mod) {//快速幂取模
- ll res=1;
- while(n>0) {
- if(n&1)
- res=res*x%mod;
- x=x*x%mod;
- n>>=1;//移位
- }
- return res;
- }
- int main() {
- srand((int)time(0));
- check_prime();
- int p=prime[rand()%100+200];
- int q=prime[rand()%100+200];
- ll n=p*q;
- printf("\n");
- printf("p=%I64d，q=%I64d，n=%lld\n",p,q,n);
- printf("\n");
- ll r=(q-1)*(p-1);
- ll e=nprime[rand()%check_Nprime(r)];
- ll d,y;
- ll gcd=extgcd(e,r,d,y);
- d=d%(r/gcd)<0?d%(r/gcd)+r/gcd:d%(r/gcd);
- printf("公钥：n=%I64d，e=%I64d\n",n,e);
- printf("\n");
- printf("私钥：n=%I64d，d=%I64d\n",n,d);
- printf("\n");
- printf("请输入明文:");
- int s;
- scanf("%I64d",&s);
- ll C=mod_pow(s,e,n);
- printf("\n");
- printf("加密得到的密文为：%lld\n",C);
- printf("\n");
- printf("解密得到的明文为：%lld\n",mod_pow(C,d,n));
- printf("\n");
- return 0;
- }
四、运行截图
|
发表于 2022-4-19 14:45:27
楼主