推 seagal:了解 十分感謝:) 08/25 22:53
※ 引述《seagal (會長繞跑了)》之銘言：
: 好的
: 我舉一個在他書上的例子
: 質數選擇: p=11, q=17
: 模數: r=187
n = r
: 歐拉函數: 160
: 公開指數: PK=13
e = PK
: 秘密指數: SK=37
d = SK
: 用明文2當例子 來做個加密
: 2^13 mod (187) = 151
: 151^13 mod (187) = 138
: 138^13 mod (187) = 117
: 117^13 mod (187) = 2
: 我們可以看到
: 在第四次重複做加密的時候
: 出現的密文也就是原先的明文
: 接下來如果我再做第五次加密
: 2^13 mod (187) = 151
: 這個結果很清楚的表示出與第一次加密重複
: 這很令我驚訝的是
: 完全不需要SK
: 只要利用PK
: 當我在第五次發現到151密文重複出現時
: 我就能夠知道第四次的密文2 也就是原先的明文
: 而作者做了一些數值分析
: 顯示出RSA演算法不僅有封閉性
: 而且還有週期性
嗯嗯
: 也就是上面的例子是以四的週期重複出現
: 而其他的明文也有許多會以四的週期重複出現
: 這本書的書名是 破譯RSA 全華科技圖書股份有限公司
: 是否照他書上形容的這種方法就可以算出明文
: 而繞過因數分解這種NPC的問題呢?
用這種方式的確可以解密, 不過要做 d 次
d 是任意小於 ψ(n) 且和 ψ(n) 互質的數, ed ≡ 1 mod ψ(n)
ψ(n) = (p-1)(q-1) 是非常大的數
e, d 也會是非常大的數(例如 2^256)
所以要用這種方式破解
還不如用暴力法解做因數分解還比較快
這例子是特殊情形, 而且 p 和 q 太小了, 因數分解一下就出來了,
如 shiuantzuo 所說, RSA 在 p 和 q 太小的情形是不安全的,
不過 RSA 的前提是 p 和 q 都要非常大,
所以這例子和真實情況有所出入..
當 e 和 d 非常大時, 通常週期也會非常大,
那種小周期現象幾乎不可能發生
所以那種破解法既不實際也 infeasible, 成功率趨近 0.
: ※ 引述《shiuantzuo (沒有下雨的日子)》之銘言：
: : SSL/TLS我不太熟
: : 但是我認為不太可能會是使用public key的方式去加解密
: : 畢竟有自己的public/private key的user比例實在太少了(如果是公開的網路環境)
: : 應該是連線建立前透過key establishment的方式產生share secret key
: : 再用此secret key去加解密
嗯嗯...
SSL/TLS 只有在前面一開始的 handshaking protocal 才使用 RSA
做 session key 的交換. 有了 session key 後面通訊的加解密都
是使用傳統加解密演算法(ex. 3-DES, RC5 等)
: : security有 數學上完全不可能被計算 和
: : 可計算但是所需資源太大,在現行機器上不可行 等幾種的強弱性
: : 這位作者的破解方法我沒看過(也許你可以大致解說示範一下)
: : RSA的安全性是在可計算但是現行機器不可行上面
: : 所以如果key length不夠長,RSA是不安全的
: : 這位作者的方法應該是用在較小的例子上
: : 現行RSA所使用的key length大都有足夠的長度
: : 所以安全性目前是還ok的
: : 請多指教,謝謝
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.115.205.19