实验原理

说明

M 代表明文，m 代表明文分组，C 代表密文，(e,n) 代表公钥，(d,n) 代表私钥。其中n是随机选取的两个大素数 p 和 q的乘积。

图 1-2 RSA密码算法参数说明

RSA 密码算法

RSA 密码算法主要分为两个部分，一是生成公私钥对，二是要根据公钥和私钥进行加密和解密。下图是一个非常简单的RSA密码算法示例。但是一般情况需要加密的明文通常包含数字以外的字符，而且随机大素数只有位数足够多（比如1024位，目前安全的是2048位）RSA算法才相对安全。下图是一个简化的示例， p 和 q选择的非常小，只做演示用。

图 1-3 RSA密码算法示例

算法的关键步骤如下：

公钥：随机选择两个的大素数 p 和 q ， n 是二者的乘积，即 n = pq ，使 $Φ(n)＝（p-1）(q-1)$ ，Φ(n) 为欧拉函数。随机选取正整数 e，使其满足 $gcd(e, Φ(n))=1$ ，即 e和 Φ(n) 互素，则将 (n,e) 作为公钥。
私钥：求出整数 d，使其满足 $e×d=1 mod Φ(n)$ ，则将 (n,d) 作为私钥。
加密算法：对于明文 M 分组的每个m，由 $c=E(m) = m^e mod n$ ，得到密文 c。
解密算法：对于密文 C 的每个密文分组，由 $m =D(c)= c^d mod n$ ，得到明文 m。

说明

如果窃密者获得了n，e和密文C，为了破解密文他必须计算出私钥d，为此需要先分解n为p和q。为了提高破解难度，达到更高的安全性，一般商业应用要求n的长度不小于2048bit。

说明

本次实验我们不考虑RSA算法的攻击部分，如果有兴趣的同学可以通过如下网站查看CTF比赛中部分关于RSA攻击的示例。https://www.ruanx.net/rsa-solutions/

1 密钥生成

选择大素数 $p$ 和 $q$ （如果用C语言不配置gmp可以选择四位数的十进制（随机数范围可以为10000），其他语言要求至少128位的大素数，最好体会下1024位的速度）
计算 $n = p * q$ ，计算 $ｎ$ 的欧拉函数 $φ(n) = (p - 1) * (q - 1)$
选择一个与 $φ(n)$ 互质的整数 $e$
将 $e$ 对 $φ(n)$ 求逆得到 $d$ ，即 $e * d ≡ 1 \quad mod \quad φ(n)$
将 $(e,n)$ 作为公钥， $(d,n)$ 作为私钥

1.1 生成大素数 $p$ 和 $q$

本次实验对大素数的要求不高，最少是一个四位数的十进制，也就是至少14位的2进制。首先需要生成一个随机的数，然后再判定该数是不是素数。

关于素数判定，我们应该还能想到大一的C语言编程，判断一个数 x 是不是素数，当时大家是从 2 到根号 x 逐一判断，如果都不能被 n 整除，那就是素数，但是如果是1024位的呢？效率是不是超低？

这里给大家介绍一个概率性的素性检测法：Miller-Rabin算法，它本质上是一种概率算法，存在误判的可能性，但是出错的概率非常小，而且效率是比较高。

原理和算法描述参考理论课件《FC-L8-数论基础v2》 36页和 37页。

图 1-4 Miller-Rabin算法

图 1-5 Miller-Rabin算法示例

说明

如果有同学对各种素数检测比较感兴趣，可以参考链接，上面总结了素数检测逐步提供效率和概率的几个经典方法：https://www.cnblogs.com/merk11/p/15599022.html。

1.2 求e和d

欧几里德（Euclid）算法是数论中的一个基本技术，是求两个正整数的最大公因子的简化过程。而扩展的Euclid算法不仅可求出两个正整数的最大公因子，而且当两个正整数互素时，还可求出其中一个数关于另一个数的乘法逆元。两个算法的伪代码如下：

Euclid（f, d）
  1. X←f; Y←d；
  2. if Y=0 then return X=gcd(f,d)；
  3. R=X mod Y；
  4. X=Y；
  5. Y=R；
  6. goto 2。

Extended Euclid(f, d) （设 f >d） 
  1. (X1,X2,X3)←(1,0,f);(Y1,Y2,Y3)←(0,1,d);
  2.  if Y3=0 then return  X3=gcd(f, d)；no inverse;
  3. if  Y3=1 then return  Y3=gcd(f, d)；Y2=d^-1 mod f;
  4. Q=X3/Y3 ；
  5. (T1,T2,T3)←(X1-QY1,X2-QY2,X3-QY3);
  6. (X1,X2,X3)←(Y1,Y2,Y3);
  7. (Y1,Y2,Y3)←(T1,T2,T3);
  8. goto 2。

e可以位随机生成的一个小于 φ(n) 的整数，利用欧几里德判断 e 是否符合的互质要求，否则在令 $e += 1$ 继续寻找。根据e，可以利用扩展的欧几里得求 d。

2 加密和解密

因为RSA算法的加密和解密运算都用到幂运算和取模运算，根据取模运算的性质，我们可以使用快速幂取模的方式来进行快速且不溢出的运算。

  //m为底数，e为指数，n
  quick_pow(m,e,n) 
    ans = 1
    while e:
        if e & 1:
            ans = (ans * m) % n
        m = m * m % n
        e >>= 1
    return ans