日期：2022.11.1

本文介绍了RSA公钥加密体系以及复现常见的攻击手段。RSA公钥加密算法是基于大整数分解的困难问题建立的。本次实验的数据来源为首届全国高校密码数学挑战赛赛题三。采用Python编写程序。通过预处理截获数据，最终实现多种由于参数选取不当造成的攻击手段：因素碰撞、共模攻击、低加密指数广播攻击、费马分解攻击、pollard p-1分解法。

关键词：RSA算法，加密破解，因素碰撞、共模攻击、低加密指数广播攻击、费马分解攻击。

RSA公开密钥密码体制是一种使用不同的加密密钥与解密密钥，“由已知加密密钥推导出解密密钥在计算上是不可行的”密码体制。

在公开密钥密码体制中，加密密钥（即公开密钥）PK是公开信息，而解密密钥（即秘密密钥）SK是需要保密的。加密算法E和解密算法D也都是公开的。虽然解密密钥SK是由公开密钥PK决定的，但却不能根据PK计算出SK。

RSA算法的具体如下：

是一个任意的整数；所以，若知道e和，则很容易计算出d；

（4）公开整数n和e，秘密保存d；

（5）将明文m（m2.4因素碰撞

因数碰撞法指的是，如果参数选取不当, p或者q在多个rsa加密中使用多次，那么生成不同的n可能会有相同的因子，我们假设p相同,q不同，那么有:

很容易知道

这样很快就能将他们各自的私钥求解出来了。（寻找两个n的）

代码如下：

攻击结果为：

共模攻击指的是如果一条消息发送给不同的接收方，接收方的模数n相同, 公钥e不同，那么可以进行如下的攻击:

我们求解：

由扩展欧几里得算法我们可以很轻松的求出x和y

所以有：

所以将明文给求解出来了。

结果如下：

代码如下：

低加密指数广播攻击适合于n很大,e很小的情况，其适用的情况如下，当一条消息m发送给不同的接收者时，每个接收者的n都不同，但是加密的公钥都是相同的，我们假设公钥为3，那么有：

由中国剩余定理知道,我们是可以将m3算出来的，那么对其开立方就将明文给求出来了。

结果如下:

代码如下：

如果p 和q相差不大的话我们可以通过费马分解把p和q求出来，原理如下：

由于p与q相差不大，所以p-q相对于n和来说可以忽略不计，所以有:

通过不断尝试就可以把p和q给计算出来了。

代码如下：

结果如下：

如果p与q都不超过1020次方，若其中一个(p-1)或(q-1)的因子都很小的时候(在这里为了方便说明我们假设为(p-1))，可以如下操作:

选取一个整数k,使其满足(p-1)| k!，由费马小定理知道, a 与p 互素的时候有:

所以有

即

那么对于n 与必有公因数为p，这样就可以把n分解出来了。

我们直接计算 和 gcd（a-1，n）（n=pq）

但是对于k的选取还是有要求的，太小了(p-1)|k!不会成立，太大了花费时间会很多。

代码如下：

结果如下：

推荐常用分解网站factordb.com。3.总结

这次尝试第一届全国高校密码学挑战赛，目的为练习RSA算法常见漏洞的利用。学习了多种针对RSA的攻击方式，比如RSA共模攻击、pollard、低加密指数法、因数碰撞法、Fermat攻击等，了解了他们的原理，对RSA的结构和缺点有了更深入的了解。但是仍然存在一些尚未解决的问题，比如pollard p-q方法未能实现，有些赛题未解出等等。

参考链接