当前位置: 代码迷 >> 综合 >> RSA大数运算实现(1024位)(2)
  详细解决方案

RSA大数运算实现(1024位)(2)

热度:59   发布时间:2023-11-22 22:22:03.0

接上一篇文章

??在有了大数运算库之后,实现RSA完全不在话下了!

RSA算法

①随机选择两个大素数p和q,计算n=p·q,以及φ(n)=(p-1)·(q-1) ;
②选择e=65537,如果不满足(e,φ(n))=1,则选择一个随机整数(e,φ(n))=1。
③求出私钥d,使得e·d=1(mod φ(n))。
④加密时,明文为M,密文C=Me mod n;
⑤解密时,密文为C,解密后明文M’= Cd mod n

产生大随机数

产生指定位数的大随机数,如p的bits=524位,q的bits=500位,这样后面可以满足n大致为1024位(可能为1023位)。
①产生位数为bits的大数bignum的函数为int genBN(BN result, int bits),利用sha-1结果产生bits个二进制位的大数result;
②产生方法为,对于从低到高每一位(一位包含了32个二进制位),调用void writerand(char * addr)函数,往addr中写一个随机数,然后调用之前写的SHA-1函数,计算addr出随机数文件的哈希值,然后取32个二进制位(8个十六进制位,也就是8个哈希结果的字符)。
③最高位(最高的可能有1-32个二进制位)需要特殊处理,因为最高如果是要32位,产生的哈希值第一位如果是A以下,如0-9,那最高就没有32位,得到的大数会小于bits。这种情况下,特殊化处理,多次产生直到产生的是所要的为止。其它时候可以左右移位来满足最高位的需求。

产生指定位数素数

??由int findprime(BN a, int bits)函数实现,该函数调用了genBN(BN result, int bits)函数产生随机数,调用了int fermat_b(BN a)费马检测函数对大数进行素性检测,同时它利用了exclu()函数预先产生的前几十个素数的乘积结果,利用了gcd_b(BN a, BN b, BN & result)函数求公因子。同时需要用到SETONEBIT_B(BN num, uint32_t u)函数设置大数num为一个uint32_t的数u。用到了加法函数add_b(BN a, BN b, BN sum),过程如下:

(1)首先读取前20个素数的乘积fac,第20个素数存在temp3中;
(2)随机产生满足位数要求的大数bignum;
(3)求公因子gcd_b(fac,bignum,gcd),如果gcd=1,就拿这个大数去做费马检测步骤(7)。如果gcd比第20个素数还要大,或者很不幸这个大数是偶数gcd=2或者gcd比temp3大,就回到(2);
(4)对大数进行微调,初始化微调变量linshi=2,循环变量i=0;
(5)大数bignum加上linshi,得到调整后的adjnum,对adjnum和fac求最大公因子gcd。
(6)如果gcd为1,就进行费马检测,步骤(7),linshi设为2。如果gcd不是1,且gcd<temp3,则linshi=linshi*gcd,循环变量i++,回到(5);否则重新生成一个,回到(2)。
(7)如果费马检测结果为1,则判定产生的是素数,否则回到(2)。

公钥e的选取

默认选择e=65537,但是计算(e,φ(n))可能不为1,这种情况下,就随机选择一个17位的e,使用findprime(),选择好以后存在e的路径中。

私钥d的产生

①inv_b(BN a, BN n, BN & x)函数实现,该函数调用了gcd_b(BN a, BN b, BN & result)函数,先求公因子判断是否存在逆元,然后才求逆。
②求逆时,对于inv_b(a,n,x),初始化u=1,g=a,v1=0,v3=n.
③用div_l(g,v3,q,t3)计算带余除法,g=q·v3+t3,令t1=u-q·v1 (mod n ),u=v1,g=v3,v1=t1,v3=t3。
④如果v3=0,则把u赋值给x,作为结果,否则回到步骤②。

加密

加密过程为模幂运算 C=Me mod n
①使用模平方算法,配合调用modmul()模乘函数;
②对指数e进行二进制展开,初始化a=1,b=M,m=n。
③对于e的二进制展开,从低到高一位位来判断,b=b*b (mod m),如果这一位为1,则a=a*b(mod n),否则a=a;
④最后e的二进制位都算完了,a就是结果。

解密

解密时因为已知p和q,可以使用中国剩余定理加速解密,加速以后的时间是加速以前的一半:
①中国剩余定理在void crt_b(BN a, BN b, BN p, BN q, BN & result)中实现。
②先计算b11和b22,然后得到其中b11 = b mod p, b22 = b mod q:ab =ab11= b1 mod p ab =ab22 = b2 mod q
③得到方程组 x=b1 mod p
x=b2 mod q
④求逆然后得到结果:
m1=p; m2=q m=m1*m2
M1=m2=q M2=m1=p
M1*M1’=1 mod p M2*M2’=1 mod q
result= b1*M1’*M1 + b2* M2’*M2 mod(m)

测试

1.加密解密过程,用之前产生好的p和q,设置的e=65537,加密时间明显比解密时间短,其中明文是某个文件的哈希值。
在这里插入图片描述

2.当默认的e=65537与φ(n)不互素时,会随机产一个17位的素数,这里产生的为1B011。
在这里插入图片描述

3.完整的从产生密钥、加密、解密的过程如下,时间比较长,尤其产生密钥,一般500位的要平均10秒左右,使用VS打开优化以后则一般2-5秒,快的时候1秒。
在这里插入图片描述

4.采用优化编译时,速度比较快
在这里插入图片描述

5.因为比较难比较到底加解密是否正确,可以调用SHA-1函数来验证,这时SHA-1每次调用必须对初始化向量赋予初值,和之前的mysha1()用来随机寻找素数时的每调用一次都有一个状态时完全不一样,之前那个状态要是每次都是定值,寻找素数很慢,而这里要验证,所以必须初值每次都固定。

代码如下

int main()
{
    BN p, q, n, eula, e, d;BN p_1, q_1;BN plain;//明文BN cry;//加密以后BN dec;//解密以后BN temp1 = {
     0 }, temp2 = {
     0 }, temp3 = {
     0 };//用来测试memset(p, 0, BNSIZE);memset(q, 0, BNSIZE);memset(p_1, 0, BNSIZE);memset(q_1, 0, BNSIZE);memset(n, 0, BNSIZE);memset(eula, 0, BNSIZE);memset(e, 0, BNSIZE);memset(d, 0, BNSIZE);memset(plain, 0, BNSIZE);memset(cry, 0, BNSIZE);memset(dec, 0, BNSIZE);//产生p和q,一般情况下是有了的不用自己产生char p_path[81] = "myp4.txt";char q_path[81] = "myq4.txt";char e_path[81] = "e.txt";char plain_path[81] = "plain.txt";char cipher_path[81] = "cipher.txt";char decry_path[81] = "decry.txt";int ifgen = 0;//是否产生私钥int ifset = 0;cout << "是否要产生私钥p q? 输入1产生,输入0不产生\n";cin >> ifgen;cout << "是否要改变默认文件路径? 输入1改变,输入0不改变\n";cout << "p 存放在" << p_path << endl;cout << "q 存放在" << q_path << endl;cout << "公钥e存放在" << e_path << endl;cout << "明文存放在" << plain_path << endl;cout << "密文存放在" <<cipher_path << endl;cout << "解密文件存放在" << decry_path << endl;cin >> ifset;if (ifset == 1){
    memset(p_path, 0, sizeof(p_path));memset(q_path, 0, sizeof(q_path));memset(e_path, 0, sizeof(e_path));memset(plain_path, 0, sizeof(plain_path));memset(cipher_path, 0, sizeof(cipher_path));memset(decry_path, 0, sizeof(decry_path));cout << "请输入p存放路径"<<endl;cin >> p_path;cout << "请输入q存放路径" << endl;cin >> q_path;cout << "请输入e存放路径" << endl;cin >> e_path;cout << "请输入明文存放路径" << endl;cin >> plain_path;cout << "请输入密文存放路径" << endl;cin >> cipher_path;cout << "请输入解密后存放路径" << endl;cin >> decry_path;cout << "设置以后: " << endl<<endl;cout << "p 存放在" << p_path << endl;cout << "q 存放在" << q_path << endl;cout << "e 存放在" << e_path << endl;cout << "明文存放在" << plain_path << endl;cout << "密文存放在" << cipher_path << endl;cout << "解密文件存放在" << decry_path << endl;}if (ifgen == 1)//为1则产生{
    genpq(p_path, q_path);SETONEBIT_B(e, 10001U);writebn(e_path, e);readbn(p, p_path);readbn(q, q_path);readbn(e, e_path);}else{
    	readbn(p, p_path);readbn(q, q_path);readbn(e, e_path);cout << "p is " << bn2str(p) << endl;cout << "q is " << bn2str(q) << endl;cout << "初始e is " << bn2str(e) << endl;}//获取p/q//计算nmul(p, q, n);cout << "n is " << bn2str(n) << endl;writebn("n.txt", eula);subuint_b(p, 1U, p_1);cout << "p-1 is " << bn2str(p_1) << endl;subuint_b(q, 1U, q_1);cout << "q-1 is " << bn2str(q_1) << endl;mul(p_1, q_1, eula);cout << "φ(n) is " << bn2str(eula) << endl;writebn("fn.txt", eula);//一般公钥e =65537//SETONEBIT_B(e, 10001U);gcd_b(e, eula, temp3);if (cmp_b(temp3, ONE_BN) != 0) {
    while (cmp_b(temp3, ONE_BN) != 0)//如果不互素!!!悲剧了{
    findprime(e, 17);gcd_b(e, eula, temp3);}cout << "之前公钥e与φ(n)不互素,修改以后的e is " << bn2str(e) << endl;writebn("e.txt", e);}//私钥d ed =1 mod φ(n)inv_b(e,eula, d);cout << "d is " << bn2str(d) << endl;writebn("d.txt", d);//获取明文readbn(plain, plain_path);cout << "明文是 is " << bn2str(plain) << endl;//加密int time1 = clock();modexp_b(plain, e,n, cry);printf("加密耗时%d ms\n", clock() - time1);cout << "密文是 is " << bn2str(cry) << endl;writebn(cipher_path, cry);//解密int time2 = clock();//modexp_b(cry, d, n, dec);crt_b(cry, d, p, q, dec);printf("\n解密密耗时%d ms\n", clock() - time2);cout << "解密为 is " << bn2str(dec) << endl;writebn(decry_path, dec);readbn(temp1, plain_path);readbn(temp2, decry_path);cout << endl << "明文为" << bn2str(temp1);cout  << endl<<"解密为" << bn2str(temp2)<<endl;if (checkresult(plain_path, decry_path) == 1)cout << "\n加解密正确!" << endl;elsecout << "\n加解密出现错误!" << endl;system("pause");return 0;
}