推 yalight:因數分解不是NPC ^^" 08/25 18:50
推 seagal:sorry 的確密碼學界多數人士傾向於因子分解不是NPC問題 08/25 21:18
好的
我舉一個在他書上的例子
質數選擇: p=11, q=17
模數: r=187
歐拉函數: 160
公開指數: PK=13
秘密指數: SK=37
用明文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的問題呢?
※ 引述《shiuantzuo (沒有下雨的日子)》之銘言：
: ※ 引述《seagal (會長繞跑了)》之銘言：
: : 大家好
: : 今天不小心在圖書館看到有關密碼學的書籍
: : 好奇之下翻了看看
: : 因為本身對密碼學完全沒有研究
: : 所以有以下疑問想請問各位版友
: : 1.請問SSL/TLS是否是應用公開密鑰的加密方式?也就是加密 解密使用不同的密鑰?
: : (哪裡有SSL/TLS的原理介紹呢?)
: SSL/TLS我不太熟
: 但是我認為不太可能會是使用public key的方式去加解密
: 畢竟有自己的public/private key的user比例實在太少了(如果是公開的網路環境)
: 應該是連線建立前透過key establishment的方式產生share secret key
: 再用此secret key去加解密
: : 2.我看一本破解RSA的書籍說
: : 基本上不需要使用因數分解的方法
: : 而他利用數值分析
: : 發現RSA演算法具有封閉性
: : 也就是重複使用PK對密文加密
: : 在幾個步驟之後
: : 密文就會轉換成明文
: : 他書上有列出詳細的數值分析過程
: : 我看的結果是 真的是幾個步驟就會成功了ㄝ
: : 我想請問這種破解法
: : 真的是可行的嘛?
: : 也就是是否在他提出的幾個特例中 才有這種現象
: : 如果PK的位元長度很長的話
: : 雖然有封閉性 但密文轉出明文可能會很複雜之類的
: : 而這位作者根據數值分析 就已經斷定RSA的密鑰是多餘的結論
: : 真的這麼神奇嘛?那RSA還有人敢用嘛?
: : 請大家幫我解答疑惑一下 謝謝
: security有 數學上完全不可能被計算 和
: 可計算但是所需資源太大,在現行機器上不可行 等幾種的強弱性
: 這位作者的破解方法我沒看過(也許你可以大致解說示範一下)
: RSA的安全性是在可計算但是現行機器不可行上面
: 所以如果key length不夠長,RSA是不安全的
: 這位作者的方法應該是用在較小的例子上
: 現行RSA所使用的key length大都有足夠的長度
: 所以安全性目前是還ok的
: 請多指教,謝謝
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.109.169.200