能力值:
( LV9,RANK:170 )
2 楼
谢谢了.一定细细bai读.
能力值:
(RANK:420 )
3 楼
拜讀倒不用,但歡迎一起交流及討論。
聽朋友說,看雪學院裏,牛人最多了。
隨便逛逛,都會撞到高手。
果然所言不假。
能力值:
( LV3,RANK:30 )
4 楼
向密码学高手致敬一下
能力值:
( LV15,RANK:670 )
5 楼
能不能附上简体一篇。。。
能力值:
(RANK:420 )
6 楼
晚一點,我把它轉成簡體看看。再 upload 上來給大家。
能力值:
(RANK: )
7 楼
看了你的文档, 我觉得有个问题:
Step 1: 计算 y 的值使得 m^y = 1 (mod p). <--- 这里的p应该是n(=p*q)吧? 如果知道p了还求什么....
这个计算有快速算法吗? 如果没有, 在 n 是一个大数(如1024位)时所需要的时间不会比最快的因数分解法少吧?
能力值:
( LV4,RANK:50 )
8 楼
应当是笔误 m^y = 1 (mod p)~~~~m^y = 1 (mod n )
也就是把因子分解问题转为求离散对数
能力值:
(RANK: )
9 楼
这好象有点南辕北辙了吧? 求离散对数同样是NP问题, 而且不见得比因子分解容易.
比如说同样是1024位的情况下, 求离散对数和因子分解, 哪个更容易?
能力值:
( LV4,RANK:50 )
10 楼
离散对数和因子分解目前还都是NP问题,
不过在不同的条件下两种方法各有特点,
有时两者也可结合起来用。
比如说:穷举64位的对数是很简单的,但穷举64位的因子却不容易。
能力值:
(RANK: )
11 楼
同意, 但要保证RSA的安全性, 至少得要1024位以上吧? 面对这样的大数, 把因子分解问题转为离散对数问题是不可取的.
BTW: 64位不用穷举都可以直接分解. 而且是秒杀.
能力值:
( 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即被分解。
能力值:
(RANK: )
13 楼
求教此公式来源?
按假设你只知道p+q是一个513位的数, 单变换低64位如何能逼近p+q?
能力值:
( LV4,RANK:50 )
14 楼
根据费马小定理
p+q是一个513位的数,假设 (当然现在找到的都不理想)用某些方去逼近,
这里说的是逼近,比如:第一次求出的x=p+q+2^200,第二次求出的x=p+q-2^190
.....第n次.....因为每次都有检查x的最后64位,所以在误差小于2^64时即可求出。
能力值:
(RANK: )
15 楼
一时没反应过来....
假设....
突然间我发现r大原文的立意是不去做因子分解, 而是把问题转移到求Φ(n), 然后根据e直接求出d而不需要理会p和q. 文章的第四部分只是举例评估可行性而已, 所以不关心也不需要关心大数情况下如何求y.
能力值:
( LV4,RANK:50 )
16 楼
嗯,只能假设
目前最快的因子分解法时间复杂度为O(exp{c(lnNlnlnN)^1/2}),其中c为常数
能力值:
(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 年(好像)的問題,在上世紀末時,解決了。
能力值:
(RANK:420 )
18 楼
突然间我发现r大原文的立意是不去做因子分解, 而是把问题转移到求Φ(n), 然后根据e直接求出d而不需要理会p和q. 文章的第四部分只是举例评估可行性而已, 所以不关心也不需要关心大数情况下如何求y.
恭喜您,終於開始理解一點的核心了。
能力值:
(RANK:420 )
19 楼
能力值:
( LV12,RANK:750 )
20 楼
谢谢,研究下
能力值:
( LV2,RANK:10 )
21 楼
很好的文章喔
能力值:
( LV2,RANK:10 )
22 楼
为什么都用繁体呢 看起来没费劲 用简体中文不好么/
能力值:
(RANK:420 )
23 楼
1)
很抱歉,我只看得懂繁體,電腦也是繁體的。
2)
如果您覺得麻煩,您可以轉換成簡體,謝謝。
能力值:
( LV5,RANK:60 )
24 楼
R大,我先下载回去研究一下,呵呵!
能力值:
( LV2,RANK:10 )
25 楼
发现来晚了,这么好的一篇文章。
我研究的就是RSA算法,多多学习。先下载了。