关于 protectz v1.53 RSA 算法的一点理解 (2千字)

RSA算法简述：
1、取两个素数p和q。
2、计算n=pq，f=(p-1)(q-1)。
3、随机选取整数e，满足条件gcd(e, f)=1，其中gcd为最大公约数。
4、计算d，使得乘积de对f求余的结果为1，即de和1对f同余。
上述只有e和n对外公开，用于加密。
加密过程（符号^表示乘幂，mod表示求余）：
    e为加密密钥，假定明文为m，则密文c = (m ^ e) mod n。
解密过程：
    d为解密密钥，则解密得到的明文m'= (c ^ d) mod n。
                       
                  --------摘自《论坛精华3》-------《Windows优化大师v2.9+的注册码加密算法》
                                                                written by dr0, 2000/08/22
===============================================================================================
  程序中明显的可以看出：e=7,n=0xbb=187=11*17
                  所以：p=11,q=17
                        n=p*q=11*17=187
                        f=(p-1)*(q-1)=160
                        gcd(e,f)=1
                又因为：(d*e)%f=1
                也就是：(d*7)%160=1
                  所以：(d*7)=a*160+1
                  假设：a=1
                    则：d=161/7=23
现在看看我们得到了什么：p=11, q=17, n=p*q=187, f=(p-1)*(q-1)=160, d=23, e=7
================================================================================================
程序中主要的计算过程是：
假设：已知0xi是一个两位的16进制数
  (1) 1*0xi==0xi
  (2) 如果 0xi*0xi>=0x8899  则取余--(0xi*0xi)%0x8899,余数参与下面计算
      否则用0xi*0xi参与下面计算
  (3) 如果 ((2)的结果*0xi)>=0x8899 则取余--((2)的结果*0xi)%0x8899,余数参与下面计算
      否则用(2)的结果*0xi)参与下面计算,以下同
  (4) 同上
  (5) 同上
  (6) 同上
  (7) 同上
  (8) 最后取余--(7)的结果%0xbb==A
   
其中A就是已知的密文，0xi就是我们要求的明文,上面那一段其实就是：A=(0xi^7) mod 0xbb
于是可以进行一下逆运算：0xi=(A^23) mod 0xbb
================================================================================================
本文是参考了“最弱智”大哥的keygen写成的，感谢！
          ,;~;,
                /\_
              (  /
              (()      //)
              | \\  ,,;;'\
          __ _(  )m=(lancelot(================--------
        /'  ' '()/~' '.(, |
      ,;(      )||    |  ~
    ,;' \    /-(.;,  )            兰斯洛特[CCG][FCG]
          ) /      ) /
        //        ||                      2001.09.26
        )_\        )_\
========================================================