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=M
e
mod n;
⑤解密时,密文为 C,解密后明文 M’= C
d
mod n
二、分步实现
1.产生指定位数的大随机数,如 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。这种情况下,特殊化处
理,多次产生直到产生的是所要的为止。其它时候可以左右移位来满足最高位的需求。
2.产生指定位数的素数
①由 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)。
3.公钥 e 的选取
默认选择 e=65537,但是计算(e,φ(n))可能不为 1,这种情况下,就随机选择一个 17 位的 e,使用
findprime(),选择好以后存在 e 的路径中。
4.d 的产生,求逆
评论0