【文章标题】: RSA保护的程序注册机制作思路总结
【文章作者】: FishSeeWater
【作者声明】: 前几天分析了一个RSA保护的软件,把与RSA相关的部分知识整理一下,以做备忘,
                    本想与软件分析一起发了,但感觉还是分离出来比较清晰,失误之处敬请诸位大侠赐教!
--------------------------------------------------------------------------------
【详细过程】
  预备知识:
  (一)RSA密码学的介绍:
      这种算法1978年就出现了,它是第一个既能用于数据加密也能用于数字签名的算法。它易于理解和操作,也很流行。
  算法的名字以发明者的名字命名:Ron Rivest, AdiShamir 和Leonard Adleman。
    RSA算法是一种非对称密码算法,所谓非对称,就是指该算法需要一对密钥,使用其中一个加密,则需要用另一个
  才能解密。
    RSA的算法涉及三个参数,n、e、d。
    其中,n是两个大质数p、q的积。n的二进制表示时所占用的位数,就是所谓的密钥长度。
    e和d是一对相关的值,e可以任意取,但要求满足e<(p-1)*(q-1)并具 e与(p-1)*(q-1)互质(就是最大公约数为1);
  再选择d,要求(d*e)mod((p-1)*(q-1))=1。
    (n及e),(n及d)就是密钥对。
    RSA加解密的算法完全相同,设M为明文,c为密文,则:
       加密:C=M^e mod n; 
       解密:m=c^d mod n;

    注:上面两式中的e和d可以互换。  
      n d两个数构成公钥,可以告诉别人;
      n e两个数构成私钥,e自己保留,不让任何人知道。
      给别人发送的信息使用私钥e加密,只要别人能用公钥d解开就证明信息是由你发送的,构成了签名机制,起验证身份的作用。
  别人给你发送信息时使用d加密,这样只有拥有e的你能够对其解密,起到数据保密的作用。  
  整理一下:
   为实现RSA的加解密
   最终目标:找三个参数 n,e,d
     1、n = p*q (p,q 是两个质数)
     2、 
        1)、φ(N)=(p-1)*(q-1)
        2)、取任何一个数e,要求满足e<φ(N)并且e与φ(N)互质
     3、(d*e) modφ(N)=1 

  
  (二)采用RSA算法保护软件的攻击方法
      1、分解RSA三个参数中的 n (使用前提条件:n的位数小于512的时候可行):
  如果n位数太大,一般分解是很困难的。一旦分解成功,就可以通过d与分解的质数求出e。求e方法见后。
      2、RSA小指数攻击法(使用前提条件:知道了 n、d,并且 e 较小):
          RSA加密方法为保证安全性,n 至少也要 600 bits 以上,使运算代价很高,尤其是速度较慢,有一种提高RSA
      速度的建议是使公钥e取较小的值,这样会使加密变得易于实现,速度有所提高。但也降低了加密的安全性。
      例如:
          如果加密时选用一个小e,而将 d,n发送给对方进行解密,如果对方想获取e,就可以用穷举方法小e。
        伪码如下:
        

代码:
        //m 为密文(任意数就可),d,n已知,穷举小e(本方法由lingyu指导,感谢:))。
        temp = m^d % n;
        c=1;
        while(true)
        {
         c = temp*c % n;
         i++;
         if (c==m) break;
        }
        printf("find e is :%d",i);
        
        在加密方案设计中,对付办法就是e和d都取较大的值。
  
      3、RSA其它攻击方法略(我也不知道了:))。
  
      4、Patch 软件中的 n ,d 方法(使用前提条件:无。 注意事项:如果软件有自校验要去掉):
  基本思路:
  用RSAtool工具生成一组 n1,e1,d1,然后用n1,d1  替换掉软件中的n,d,这样我们就可以用n,e 生成注册码给软件使用了。
    此方法有一个弊端就是要Patch的数据量往往很大,容易出错,通常我们用下面的方法来Patch。
  
      5、Patch 软件中的 n 方法(使用前提条件:无。 注意事项:如果软件有自校验要去掉(本方法由lingyu指导,感谢:))):
        方法(1):完全替换 n
  基本思路:
      要做注册机我们需要 n,e,d, 通过分析软件已知 n,d了,还需要一个e ,我们可以通过工具生成一组位数相同的 n1,e1,d1,
  用 n1 替换 n。
      现在的问题来了: 
  //===============
  注册机根据用户硬件指纹正向生成注册码的过程:
        Lic = SN1^e mod n            //SN1 代表硬件指纹等信息, lic 为经过加密后的密文。
  软件中逆向验证过程:
        SN= Lic^d mod n
      cmp(SN,SN1)     

  //===============
  如果我们Patch N为n1
  //===============
  那  正向生成注册码的过程:
      Lic = SN1^ e mod n1          //SN1 代表硬件指纹等信息, lic 为经过加密后的密文。但我们还是没有e,怎么生成Lic呢?
  逆向验证过程:
       SN= Lic^ d mod n1    //这样能解密也不可能成功!
      cmp(SN,SN1)        
 
  //======================
  我们需要用 d ,n1(我们生成的) 来求出一个新的 e1 来,这样我们才能:
  //===============
  正向生成注册码的过程:
      Lic = SN1^ e1 mod  n1        
  逆向验证过程:
      SN = Lic^ d mod n1    
      cmp(SN,SN1)      
   
  //======================
      已知 d,n1(我们生成的或者说是可分解的)求 e1还记得 (一)RSA密码学的简单介绍 中的第3条求d的方法
  (d*e) modφ(N)=1吗?对,我们还需要一个φ(N),这个φ(N)我们是可以通过p,q求出的。
      至此,我们可以通过 用 n1 替换 n的方法来做注册机了,这个方法相比于方法3,要patch的数据量就小了很多了。
  但同样,追求完美无止境,有没有更小的数据改动量呢?请继续向下看:

      方法(2):patch  n 
      为了软件改动的最小化,最好 我们的 n1 与软件中的n 尽可能的接近。
      比如:软件中的n是112233445566,最好我们的n1是112233445565。那好,我们现在就用分析一下这个方法。
   基本思路:
      我们先来看一下方法的可行性:
      n,d,e 这三个参数主要的精力是想要得到一个可用的e1,而 e1可能过公式ed≡1 mod φ(N) 得到,也就是说,如果
  我们得到了φ(N)就可以算出e1,而φ(N)就是素数之积,哈哈,可行,关键是要能分解N。虽然分解n的成功概率比较低,
  但分解改动后的n 就不好说了:)
      步骤:
      1)、用RSATool工具“RSA-Tool 2 by tE!”尝试分解改动后的n会得到一系列质数"PRIME FACTOR1 ..N"
          (这一步要多尝试,一个不行就下一个,如果可分解,很快就会出结果的。)
      2)、求φ(N)=(PRIME FACTOR1-1)( PRIME FACTOR2-1)…( PRIME FACTORn-1)
      3)、求e1,公式:ed≡1 mod φ(N),这一步用大数计算器“Big Integer Calculator v1.13”的"Ans =Y/X MO&D Z"
          功能进行。其中 Y=1,X=d,Z=φ(N)。
      好了,现在n1,d,e1 都有了,patch 软件中的n 后,就可以用e1写注册机了。而且软件的中的代码改动量小到极限。
  


   将用到的两个工具一并传上来备用:)
--------------------------------------------------------------------------------
【版权声明】: 本文原创于看雪技术论坛, 转载请注明作者并保持文章的完整, 谢谢!

                                                       2009年11月17日 13:02:06
上传的附件 RSA-Tool 2 by tE!.zip
Big Integer Calculator v1.13.zip