首页
论坛
课程
招聘
[原创]RSA保护的程序 注册机制作思路总结
2009-11-17 13:14 27383

[原创]RSA保护的程序 注册机制作思路总结

2009-11-17 13:14
27383
【文章标题】: 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

2022 KCTF春季赛【最佳人气奖】火热评选中!快来投票吧~

上传的附件:
收藏
点赞0
打赏
分享
最新回复 (32)
雪    币: 276
活跃值: 活跃值 (21)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
kwzlj 活跃值 2009-11-17 15:52
2
0
暂时看不明白,先收藏。
雪    币: 162
活跃值: 活跃值 (65)
能力值: ( LV5,RANK:65 )
在线值:
发帖
回帖
粉丝
wyfe 活跃值 2009-11-17 16:50
3
0
对RSA攻击比较感兴趣,目前RSA多少才算安全的?RSA512估计不行了吧
雪    币: 1806
活跃值: 活跃值 (39)
能力值: (RANK:420 )
在线值:
发帖
回帖
粉丝
rockinuk 活跃值 8 2009-11-17 17:29
4
0
practical secure: 1024 bits.
real secure : 2048 bits be suggested.
雪    币: 1806
活跃值: 活跃值 (39)
能力值: (RANK:420 )
在线值:
发帖
回帖
粉丝
rockinuk 活跃值 8 2009-11-17 17:45
5
0
在這篇論文 D. Boneh and G. Durfee. Cryptanalysis of RSA with private key d less than N^0.292. IEEE Transactions on Information Theory, 46(4):1339. 1349, July 2000. 有完整介紹。若有興趣,在密碼版可以找到這篇 paper,或是我可以直接提供。

.....已知 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 就不好说了:)
.....

這是個移花接木法,雖然沒有真正分解 RSA 的模數 n ,但也成功的達到目的。
上传的附件:
雪    币: 335
活跃值: 活跃值 (10)
能力值: ( LV7,RANK:100 )
在线值:
发帖
回帖
粉丝
人很老实 活跃值 2 2009-11-17 17:59
6
0
对低于 512 位才有效. 1024 位的算到头发都白了. 除非你有 n 台 PC,  用传说中的分布式解法还差不多.
雪    币: 219
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
lankiny 活跃值 2009-11-17 20:18
7
0
好文章 膜拜一下 谢谢楼主
雪    币: 1806
活跃值: 活跃值 (39)
能力值: (RANK:420 )
在线值:
发帖
回帖
粉丝
rockinuk 活跃值 8 2009-11-18 01:48
8
0
Special-Purpose Hardware in Cryptanalysis --- The Case of 1,024-Bit RSA
PUBLISHED BY THE IEEE COMPUTER SOCIETY ■ 1540-7993/07/$25.00 © 2007 IEEE ■ IEEE SECURITY & PRIVACY 63
上传的附件:
雪    币: 37
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
VC菜鸟 活跃值 2009-11-21 09:22
9
0
呵呵,1024是可以搞定的。
雪    币: 293
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
onbadday 活跃值 2009-11-24 12:07
10
0
这帖子太好了!
雪    币: 340
活跃值: 活跃值 (80)
能力值: ( LV6,RANK:90 )
在线值:
发帖
回帖
粉丝
毁灭 活跃值 2 2009-12-31 19:05
11
0
好贴~ 认真看了一下 还需要慢慢消化
刚开始接触密码学 确实有点头疼 数学太差
雪    币: 12
活跃值: 活跃值 (11)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
kryso 活跃值 2010-1-2 10:16
12
0
算法再安全,也要编码安全才有用
雪    币: 48
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
OildFish 活跃值 2010-1-4 18:09
13
0
请问 512 bits 的 n 分解大约需要多长时间呢?
穷举 d 的时候有没有什么加速的方法?记得以前听说过可以采取只计算密文的高位来加速,不过一直不知道如何实现~望指教~~~
目前来说我用过的方法还只有 patch……惭愧ing~
雪    币: 230
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
沙漠猎人 活跃值 2010-1-4 18:10
14
0
个人感觉还不错 感谢分享
雪    币: 15
活跃值: 活跃值 (651)
能力值: ( LV6,RANK:90 )
在线值:
发帖
回帖
粉丝
sungy 活跃值 1 2010-1-5 10:43
15
0
太高深了睡不着觉时可以看看
雪    币: 201
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
snowfoxzx 活跃值 2010-1-5 11:09
16
0
关注一下~有点高深,回头好好研究一下~
多谢分享~
雪    币: 6
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
ofxmzyo 活跃值 2010-1-5 20:39
17
0
下来慢慢看,谢谢提供。
雪    币: 412
活跃值: 活跃值 (66)
能力值: ( LV3,RANK:20 )
在线值:
发帖
回帖
粉丝
大头和尚 活跃值 2010-4-18 00:05
18
0
天狼星的六代东西貌似就是RSA 512,最近正在看如何替换这个大数。多谢这么好的资料
雪    币: 19
活跃值: 活跃值 (12)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
纠结 活跃值 2010-5-20 09:54
19
0
好贴~ 认真看了一下 还需要慢慢消化
雪    币: 204
活跃值: 活跃值 (42)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
daidaihu 活跃值 2010-8-8 16:52
20
0
好资料,睡不着时候看好
雪    币: 226
活跃值: 活跃值 (10)
能力值: ( LV3,RANK:20 )
在线值:
发帖
回帖
粉丝
warcraft 活跃值 2010-8-8 17:09
21
0
要找个很大的素数很难.....
雪    币: 998
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
programfan 活跃值 2010-8-8 18:32
22
0
非常容易。基本每一本密码学书籍都讲了很多种找大素数方法。
雪    币: 1006
活跃值: 活跃值 (756)
能力值: (RANK:400 )
在线值:
发帖
回帖
粉丝
莫灰灰 活跃值 9 2010-8-21 14:12
23
0
mark一下,精品文章啊。
雪    币: 12
活跃值: 活跃值 (106)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
杨开银 活跃值 2017-5-15 12:04
24
0
不错。好闻。学习了
雪    币: 12
活跃值: 活跃值 (106)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
杨开银 活跃值 2017-5-15 12:05
25
0
可否科普下签名加入验证的patch之类的
游客
登录 | 注册 方可回帖
返回