RSA密码算法是非对称密码算法的一种，其依靠的数学计算困难问题在于大素数的分解。也就是说把一个数分解成两个素数。比如35这个数，分解之后的结果是57；比如141，可以分解为1113。当这些数比较小的时候，我们几乎可以通过口算的方式来分解，当数比较大的时候，通过口算的方式就不可能了。当这些数再大一些的时候，通过计算机来分解也很困难，需要的时间很长。甚至需要几年、几十年直至几百年。几百年后，这些加密的数据应该没有什么意义了吧。
素数分解之常规暴力攻击
就是从从2开始直到n/2，，x为素数，用n除以x，如果可以整除，则说明n可以被分解。n越大，计算的时间越长。这种暴力攻击的方法，用在n较小的场景下。
素数分解之循环攻击法
- 循环攻击法
设攻击者已知某个密文，则攻击者可以计算
其中N是RSA公钥密码体制中的模数。
，因此经过有限步后，
必然再次出现。不妨设
。
2.推广的循环攻击法
攻击者先寻找满足的最小正整数
，
若，
，则
。
类似地，
若，
，则
。
两种情况下，N都可以被分解。
实际上，这种循环攻击法并不能对RSA的安全性构成威胁。若p和q是随机选择的具有相同比特长度的素数，则推广的循环攻击法获得成功的平均穷举次数至少为。相关文献证明了若p-1和q-1都有大素数因子，则上述循环攻击法很不容易成功。
举个例子
在RSA中，已知c=95，e=13，n=2537，求明文m。
我们先不考虑直接分解2537为两个素数，首先使用循环攻击法，对密文不断加密：
……
当计算结果和c相等时，。
N=2537
e=13
c=95
for i in range(1,N):
a=pow(c,pow(e,i),N)
if a == c :
print(i-1,pow(c,pow(e,i-1),N))
break
输出结果：
13 1520
接下来验证一下。
根据已知条件，，可知
，
。
如果，则
循环攻击法的计算量也很大，另外就是当N足够大时，循环到时，
也会很大，和暴力攻击相差无几。
