首页
社区
课程
招聘
[原创]RSA保护的程序 注册机制作思路总结
发表于: 2009-11-17 13:14 29754

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

2009-11-17 13:14
29754

【文章标题】: 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。
        伪码如下:
        


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

上传的附件:
收藏
免费 7
支持
分享
最新回复 (32)
雪    币: 276
活跃值: (34)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
2
暂时看不明白,先收藏。
2009-11-17 15:52
0
雪    币: 2575
活跃值: (502)
能力值: ( LV2,RANK:85 )
在线值:
发帖
回帖
粉丝
3
对RSA攻击比较感兴趣,目前RSA多少才算安全的?RSA512估计不行了吧
2009-11-17 16:50
0
雪    币: 2096
活跃值: (100)
能力值: (RANK:420 )
在线值:
发帖
回帖
粉丝
4
practical secure: 1024 bits.
real secure : 2048 bits be suggested.
2009-11-17 17:29
0
雪    币: 2096
活跃值: (100)
能力值: (RANK:420 )
在线值:
发帖
回帖
粉丝
5
在這篇論文 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 ,但也成功的達到目的。
上传的附件:
2009-11-17 17:45
0
雪    币: 362
活跃值: (25)
能力值: ( LV7,RANK:100 )
在线值:
发帖
回帖
粉丝
6
对低于 512 位才有效. 1024 位的算到头发都白了. 除非你有 n 台 PC,  用传说中的分布式解法还差不多.
2009-11-17 17:59
0
雪    币: 219
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
7
好文章 膜拜一下 谢谢楼主
2009-11-17 20:18
0
雪    币: 2096
活跃值: (100)
能力值: (RANK:420 )
在线值:
发帖
回帖
粉丝
8
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
上传的附件:
2009-11-18 01:48
0
雪    币: 37
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
9
呵呵,1024是可以搞定的。
2009-11-21 09:22
0
雪    币: 293
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
10
这帖子太好了!
2009-11-24 12:07
0
雪    币: 346
活跃值: (129)
能力值: ( LV6,RANK:90 )
在线值:
发帖
回帖
粉丝
11
好贴~ 认真看了一下 还需要慢慢消化
刚开始接触密码学 确实有点头疼 数学太差
2009-12-31 19:05
0
雪    币: 12
活跃值: (11)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
12
算法再安全,也要编码安全才有用
2010-1-2 10:16
0
雪    币: 48
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
13
请问 512 bits 的 n 分解大约需要多长时间呢?
穷举 d 的时候有没有什么加速的方法?记得以前听说过可以采取只计算密文的高位来加速,不过一直不知道如何实现~望指教~~~
目前来说我用过的方法还只有 patch……惭愧ing~
2010-1-4 18:09
0
雪    币: 230
活跃值: (728)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
14
个人感觉还不错 感谢分享
2010-1-4 18:10
0
雪    币: 547
活跃值: (2200)
能力值: ( LV7,RANK:100 )
在线值:
发帖
回帖
粉丝
15
太高深了睡不着觉时可以看看
2010-1-5 10:43
0
雪    币: 201
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
16
关注一下~有点高深,回头好好研究一下~
多谢分享~
2010-1-5 11:09
0
雪    币: 6
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
17
下来慢慢看,谢谢提供。
2010-1-5 20:39
0
雪    币: 421
活跃值: (83)
能力值: ( LV3,RANK:20 )
在线值:
发帖
回帖
粉丝
18
天狼星的六代东西貌似就是RSA 512,最近正在看如何替换这个大数。多谢这么好的资料
2010-4-18 00:05
0
雪    币: 19
活跃值: (13)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
19
好贴~ 认真看了一下 还需要慢慢消化
2010-5-20 09:54
0
雪    币: 204
活跃值: (84)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
20
好资料,睡不着时候看好
2010-8-8 16:52
0
雪    币: 232
活跃值: (25)
能力值: ( LV3,RANK:20 )
在线值:
发帖
回帖
粉丝
21
要找个很大的素数很难.....
2010-8-8 17:09
0
雪    币: 998
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
22
非常容易。基本每一本密码学书籍都讲了很多种找大素数方法。
2010-8-8 18:32
0
雪    币: 2325
活跃值: (2215)
能力值: (RANK:400 )
在线值:
发帖
回帖
粉丝
23
mark一下,精品文章啊。
2010-8-21 14:12
0
雪    币: 9
活跃值: (389)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
24
不错。好闻。学习了
2017-5-15 12:04
0
雪    币: 9
活跃值: (389)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
25
可否科普下签名加入验证的patch之类的
2017-5-15 12:05
0
游客
登录 | 注册 方可回帖
返回
//