RSA算法的一些猜想

RSA算法描述：
1）任意选定大素数p和q，计算n=p*q和r=(p-1)*(q-1)。
2）任意选定大整数e，使得(r,e)=1且1<e<r。
3）计算d，使得e*d=1 mod r，即d=e^-1 mod r。
4）公钥对(e,n),加密 c=m^e mod n。
5）私钥对(d,n),解密 m=c^d mod n。
注意：大数p、q、r在生成公钥对和私钥对后抛弃，私钥对要保密。

现在的问题是：已知 c=m^e mod n ，如何解密？

1）首先判断是否是标准RSA加密算法。
   分解n，看是否能够分解为两个素数的乘积。
   如果n能够分解为两个素数的乘积，计算r，看e是否满足1<e<r。
   如果是标准RSA加密算法，只要计算出d就可解密了。
   
2）如果n是素数，不能进行分解。
   可看成是RSA算法的特例，此时p=n,q=1,r=p-1,d=e^-1 mod p-1。
   
3）如果n可以分解为多个素数的乘积。
   可看成是RSA算法的推广形式。
   例如，若n=p*q*s*t,则r=(p-1)*(q-1)*(s-1)*(t-1),d=e^-1 mod r。
   
4）如果2和3中的e不满足(r,e)=1且1<e<r的条件。
   如果(r,e)!=1,则显然不存在d使得e*d=1 mod r，这里的方法都不适用。
   对于e>r,经试验上述1、2、3的方法往往还是可行的，不过需要证明。
   （在讲RSA算法时，有的书特意提到1<e<r这个条件，有的书根本没提，不知为何！个人暂时觉得这个条件有点多余。）

注意：n能分解的素数因子的个数越多，其分解的难度越低。如果位数相同，标准RSA算法中n的分解难度最大。
  
以上结论只经过粗略试验，未经严格证明，所以只是猜想。

现在来看最近的3个CrackMe。
对于Happytown CrackMe_0040，n是512位的大数，试了下，分解不出来，又按情况2验证了下，也不是素数，故放弃。
对于Happytown CrackMe_0035，n是素数，显然就是情况2，很简单。
对于Happytown CrackMe_0029，n可以分解为两个大素数，所以是情况1，应该按照标准RSA算法来处理。
只是由于后一个模n'=q刚好能够整除n，从而将问题简化为情况2。假若后一个模n'不能整除n，那么只能按照标准RSA算法来处理。

[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课