首页
社区
课程
招聘
[分享]植基於RSA加密演算法頻率特性之研究
发表于: 2009-5-4 22:07 18987

[分享]植基於RSA加密演算法頻率特性之研究

2009-5-4 22:07
18987
收藏
免费 7
支持
分享
最新回复 (37)
雪    币: 413
活跃值: (637)
能力值: ( LV9,RANK:170 )
在线值:
发帖
回帖
粉丝
2
谢谢了.一定细细bai读.
2009-5-5 09:35
0
雪    币: 2096
活跃值: (100)
能力值: (RANK:420 )
在线值:
发帖
回帖
粉丝
3
拜讀倒不用,但歡迎一起交流及討論。
聽朋友說,看雪學院裏,牛人最多了。
隨便逛逛,都會撞到高手。
果然所言不假。
2009-5-5 15:13
0
雪    币: 1844
活跃值: (35)
能力值: ( LV3,RANK:30 )
在线值:
发帖
回帖
粉丝
4
向密码学高手致敬一下
2009-5-10 09:45
0
雪    币: 1708
活跃值: (586)
能力值: ( LV15,RANK:670 )
在线值:
发帖
回帖
粉丝
5
能不能附上简体一篇。。。
2009-5-10 10:05
0
雪    币: 2096
活跃值: (100)
能力值: (RANK:420 )
在线值:
发帖
回帖
粉丝
6
晚一點,我把它轉成簡體看看。再 upload 上來給大家。
2009-5-10 14:18
0
雪    币:
能力值: (RANK: )
在线值:
发帖
回帖
粉丝
7
看了你的文档, 我觉得有个问题:
Step 1: 计算 y 的值使得 m^y = 1 (mod p).  <--- 这里的p应该是n(=p*q)吧? 如果知道p了还求什么....
这个计算有快速算法吗? 如果没有, 在 n 是一个大数(如1024位)时所需要的时间不会比最快的因数分解法少吧?
2009-5-11 20:45
0
雪    币: 1022
活跃值: (31)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
8
应当是笔误 m^y = 1 (mod p)~~~~m^y = 1 (mod n)
也就是把因子分解问题转为求离散对数
2009-5-11 20:56
0
雪    币:
能力值: (RANK: )
在线值:
发帖
回帖
粉丝
9
这好象有点南辕北辙了吧? 求离散对数同样是NP问题, 而且不见得比因子分解容易.
比如说同样是1024位的情况下, 求离散对数和因子分解, 哪个更容易?
2009-5-11 21:29
0
雪    币: 1022
活跃值: (31)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
10
离散对数和因子分解目前还都是NP问题,
不过在不同的条件下两种方法各有特点,
有时两者也可结合起来用。
比如说:穷举64位的对数是很简单的,但穷举64位的因子却不容易。
2009-5-11 21:44
0
雪    币:
能力值: (RANK: )
在线值:
发帖
回帖
粉丝
11
同意, 但要保证RSA的安全性, 至少得要1024位以上吧? 面对这样的大数, 把因子分解问题转为离散对数问题是不可取的.
BTW: 64位不用穷举都可以直接分解. 而且是秒杀.
2009-5-11 21:51
0
雪    币: 1022
活跃值: (31)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
12
设n是1024位的,p,q都是512位的,
假设通过某些方法逼近x-->p+q,
2^(p+q-1)mod =2^n mod n
每次检查x的最后64位(穷举对数的最后64位)p+q-2^64<=x<=p+q+2^64
则p+q即被求出,n即被分解。
2009-5-11 22:04
0
雪    币:
能力值: (RANK: )
在线值:
发帖
回帖
粉丝
13
求教此公式来源?


按假设你只知道p+q是一个513位的数, 单变换低64位如何能逼近p+q?
2009-5-11 22:13
0
雪    币: 1022
活跃值: (31)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
14
根据费马小定理
p+q是一个513位的数,假设(当然现在找到的都不理想)用某些方去逼近,
这里说的是逼近,比如:第一次求出的x=p+q+2^200,第二次求出的x=p+q-2^190
.....第n次.....因为每次都有检查x的最后64位,所以在误差小于2^64时即可求出。
2009-5-11 22:24
0
雪    币:
能力值: (RANK: )
在线值:
发帖
回帖
粉丝
15
一时没反应过来....


假设....

突然间我发现r大原文的立意是不去做因子分解, 而是把问题转移到求Φ(n), 然后根据e直接求出d而不需要理会p和q. 文章的第四部分只是举例评估可行性而已, 所以不关心也不需要关心大数情况下如何求y.
2009-5-11 22:41
0
雪    币: 1022
活跃值: (31)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
16
嗯,只能假设
目前最快的因子分解法时间复杂度为O(exp{c(lnNlnlnN)^1/2}),其中c为常数
2009-5-11 23:16
0
雪    币: 2096
活跃值: (100)
能力值: (RANK:420 )
在线值:
发帖
回帖
粉丝
17


1) 筆誤,謝謝指正。
正確應該是 m^y = 1 (mod n).

2) 这个计算有快速算法吗?
老實說,我也不知道。

3)如果没有, 在 n 是一个大数(如1024位)时所需要的时间不会比最快的因数分解法少吧?
你的觀點完全正確。
就我所知道的,是沒有√n 那樣分解的快,這是肯定的。


在這篇文章裏,真正想表示的重點有機個:

A)
從 Table 1 及 Table 2 可以知道,只要用 public key 連續加密,最後會回到原點,因此,可以知道 RSA 是一個封閉空間的 cryptosystem。因此, secret key 是冗餘的。

B)
大家都知道,cracking RSA 都是用super computer 來運作,如果我們沒有 super computer 呢,那怎麼辦?
所以,這個算法(algorithm),透過 mini computer or micro computer 上,也可以實現。
最重要的事是,這是另一種方法,以往大家所不知道的新方法。
好不好用,實不實用,可不可以用,沒也有人知道 。

C)
如原作者劉尊全教授所說的,大家對 Cracking RSA 的印象,不外乎就是「因數分解法」,所以大家自然而然的就接受 or 公認 要 breaking RSA 只有「因數分解法」,是不是還有其他的方法?
我想專門研究 RSA 的人,也在努力中。

Ps. 當初也沒人想到要解 Fermat Last Theorem 要用到 Elliptic Curve 的知識,也沒人知道這個沉寂了350 年(好像)的問題,在上世紀末時,解決了。
2009-5-12 00:12
0
雪    币: 2096
活跃值: (100)
能力值: (RANK:420 )
在线值:
发帖
回帖
粉丝
18
突然间我发现r大原文的立意是不去做因子分解, 而是把问题转移到求Φ(n), 然后根据e直接求出d而不需要理会p和q. 文章的第四部分只是举例评估可行性而已, 所以不关心也不需要关心大数情况下如何求y.

恭喜您,終於開始理解一點的核心了。
2009-5-12 00:19
0
雪    币: 2096
活跃值: (100)
能力值: (RANK:420 )
在线值:
发帖
回帖
粉丝
19


附上簡體版,請查收。
上传的附件:
2009-5-12 05:54
0
雪    币: 1233
活跃值: (907)
能力值: ( LV12,RANK:750 )
在线值:
发帖
回帖
粉丝
20
谢谢,研究下
2009-5-12 07:47
0
雪    币: 86
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
21
很好的文章喔
2009-5-12 08:33
0
雪    币: 203
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
22
为什么都用繁体呢 看起来没费劲 用简体中文不好么/
2009-5-17 02:22
0
雪    币: 2096
活跃值: (100)
能力值: (RANK:420 )
在线值:
发帖
回帖
粉丝
23
1)
很抱歉,我只看得懂繁體,電腦也是繁體的。

2)
如果您覺得麻煩,您可以轉換成簡體,謝謝。
2009-5-17 03:24
0
雪    币: 304
活跃值: (10)
能力值: ( LV5,RANK:60 )
在线值:
发帖
回帖
粉丝
24
R大,我先下载回去研究一下,呵呵!
2009-5-21 20:10
0
雪    币: 21
活跃值: (26)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
25
发现来晚了,这么好的一篇文章。
我研究的就是RSA算法,多多学习。先下载了。
2009-10-13 18:23
0
游客
登录 | 注册 方可回帖
返回
//