基于Pari数学软件浅谈RSA算法相关密码题型（基础篇）

0×00 绪论

作为一名密码爱好者，这些年对大大小小各类密码都有过简单的接触，虽不精通，但也算比较熟悉。本人将通过自己粗浅的理解用三到四个篇章为大家理一理与RSA密码算法相关的几类CTF题型。By the way 由于自身只是一名初级选手，在讲述的过程中如有不准确甚至错误的地方，还望各路大牛批评指正！

0×01 RSA算法简介

RSA算法是1978年由Rivest, Shamir和 Adlemen这三位密码学大牛基于大数分解这一困难问题而设计的公钥密码算法，先后被ISO、ITU、 SWIFT等国际化标准组织采纳为国际标准，被广泛应用于加密密钥、数字签名、身份认证、协议设计等领域。

RSA算法又称为RSA公开密钥密码体制——所谓的公开密钥密码体制就是使用不同的加密密钥与解密密钥，是一种“由已知加密密钥推导出解密密钥在计算上是不可行的” 密码体制。RSA是被研究得最广泛的公钥算法，从提出到现在的三十多年里，经历了各种攻击的考验，逐渐为人们接受，普遍认为是目前最优秀的公钥方案之一。

RSA算法是一种非对称密码算法，所谓非对称，就是指该算法需要一对密钥，使用其中一个加密，则需要用另一个才能解密。

RSA算法涉及的参数有n、p、q 、e1、e2等。

其中，n是两个大质数p、q的积， n的表示时所占用的位数，就是所谓的密钥长度。e1和e2是一对相关的值，e1 可以任意取，但要求e1与(p-1)* (q-1)互质；再选择 e2，要求(e2*e1)mod((p-1)*(q-1))=1。(n，e1), (n ，e2)就是密钥对。其中(n，e1)为公钥， (n，e2)为私钥。

RSA加解密的算法完全相同，设A为明文，B为密文，则：

A=B^e1 mod n；B=A^e2 mod n；

e1和e2可以互换使用，即：

A=B^e2 mod n；B=A^e1 mod n;

0×02 Pari简介

这里给各位推荐一款数学软件——Pari。Pari是一款可用于数学领域中数论、多项式、代数、椭圆曲线等方面快速计算且广泛应用于计算机系统的开源软件。

下载链接如下：

http://pari.math.u-bordeaux.fr/download.html

安装过程不断下一步即可，安装完毕双击gp.exe可见下图

该软件对许多常用的数学函数以及算法进行了封装，一旦熟练掌握Pari，我们将在实现算法、解决实际问题中省下大量时间。比如说，在C语言中，我们写下洋洋洒洒几十行代码才完成的扩展欧几里得算法实现求代数的公因子这一功能，在Pari中我们只需一条命令即可完成：

足见用好数学软件的优势！

0×03 举个栗子

题目：

设N=875527115644562664608553823918375721160455389852576158624247，

e1=463884209889475377478742046340962125043690799298268667047773，

已知RSA的公钥(N，e1)及其加密后的密文：

B=825568930611462903672838325065041844731508649912306161613952,

1) 给出N的分解；

2) 求私钥；

3) 求B对应的明文

解题思路：

本题考察的是对RSA加密体制的基本原理，熟悉Pari的同学相信是可以很快解答的。

首先在第一问中，我们所要分解的N值通过binary函数将其转化为二进制后利用 length函数可查看N的二进制长度为200位，即密钥长度为200 位（见图一），稍微有点大但是并不影响我们直接用factor函数对其进行分解（见图二，在我的破台式上也就跑了大概30秒的时间）。

图一

图二

其次是第二问，我们根据公私钥的对应关系(e1*e2)mod((p-1)*(q-1))=1可知，在已知公钥的情况下，可以通过求公钥e1 模((p-1)*(q-1) )的逆来求出私钥e2的值。（这里求(p-1) * (q-1) 的值除了直接计算还有另外一种方法——由于N是合数，且只能分解为质数p*q，所以(p-1)* (q-1) 也可转化为求N的欧拉函数值如图三，当然了，在p、q已知的情况下直接计算是最方便的。）

图三

求公钥e1模((p-1)* (q-1))的逆，难道你准备用Pari 编写扩展欧几里得算法吗？NoNoNo~在Pari中，这一需求只需一条命令即可（如图四）：

图四

这里注意Pari中“%”表示上一计算所得的结果，而“%4”表示步骤第4得到的结果。由图四所示，我们得到私钥值为：e2=123395450536193772421623809932412913266331250297385429371757

最后看第三问，基于前两问的解答，我们已知了公私钥对、N以及密文c ，我们只需对密文c进行解密即可得出明文d。根据明密文A、 B与公私钥e1、e2的关系：

A=B^e2 mod N；B=A^e1 mod N

表面上看明文A只需通过B^e2 mod N计算得到，隐含的坑点是，加入直接计算A^e1再进行模运算，势必导致变量范围溢出；进一步考虑，A^e1即e1个A相乘，假如每相乘一次做一次模运算，当然可以避免变量溢出，然而缺点是该运算相当耗时。终极方法应该是通过蒙哥马利快速幂模算法进行优化计算（没听说过的童鞋请自行百度）。

这里附上实现快速幂模算法的Quick_Mod函数，函数最后返回 x^n Mod N的值：

Quick_Mod(x, n, N) = 
{
      bin_n= binary(n);
      len= length(bin_n);
      result= 1;
      power_x= Mod(x, N);
      for(i= 1, len,
           if(bin_n[len+ 1 - i],
                 result*= power_x;
           );
           power_x= power_x^2;
      );
      return(lift(lift(result)));
}

注意将代码导入Pari时将代码转化成一行进行输入，譬如将上述代码去除回车在一行上进行表示如下：

Quick_Mod(x, n, N)= { bin_n =binary(n); len = length(bin_n); result = 1; power_x = Mod(x, N); for(i = 1,len,if(bin_n[len + 1 - i],result *= power_x; ); power_x = power_x^2; );return(lift(lift(result))); }

直接将上述函数代码输入Pari后即可进行调用。

答案如图五所示：

图五

所以得到明文A为416990899868399045262609236390743093230765763515005099059174。

相信通过以上的讲解小伙伴们对RSA算法的原理以及Pari的使用应该有了简单的认识，那就快动起手来试一试吧~