最近看到一些文章講密碼系統，說很多密碼系統都依賴大質數來建構
例如 RSA演算法 會用兩個質數p和q，兩個質數相乘得到的N，來N來當作系統運作時的參數，而要把N反向分解成p和q卻是很困難，有多困難也就決定了密碼的強度
高深的數學實在看不懂，不過把N反向分解成p和q倒是很有趣的問題，請問
. 一般所謂的128bits的密碼系統，N、p、q 的範圍大概是多大的數啊？
. 網路上已經有人發現很大的質數，把所有已經發現的質數都拿來除N，這樣也會很困難嗎？
. 如果發現方法可以很快的把N反向分解成p和q，經濟會不會崩潰啊？
請高手教一教
3Q
yinhell wrote:
N = 128bits 大約等於39 位數
p或q 其中一個不會超過18位數
那麼 N=64bits的話，p或q 其中一個不會超過9位數，是吧？
把所有9位數以下的質數都找出來，不知道需要多久的時間？ 大概有幾個質數？ 應該有人做過吧，現在電腦這麼發達
還有一點很納悶，既然加密的時候需要選一組p和q算出N，那表示 生成N的機構或者組織 知道所有的質數，那麼對他們來說，把N除以每個質數 算算看，要把N做因數分解應該不困難吧？
依NIST的規範 現行的N至少都要有2048位元以上
所以p,q至少都要有1024位元
數學上有所謂的"質數分佈定理"
可以大致算出某范圍內的質數總數
所以你只要看到那個公式
你就會知道在1024位元內的質數總數根本是天文數字的好幾次方
因為RSA的N是由p,q組成
而p,q是隨機所產生的2個大質數
綜合以上所說
除非有更好更新的質數分解演算法出現
可以將big-O降下來(以exponential成長)
否則以現今的能力無法分解這種N
但未來若量子電腦可以成功 那這種質因數分解的計算量就變成了polynomial型態
也因此RSA就不在是安全的拉...
ps.之前在RSA公司上有所謂的challenge
目前可看到的是分解7百多位元的N
可是這背後所需要付出的成本與時間都是難以想像的
內文搜尋
從 APP 打開
X