最近看到一些文章講密碼系統，說很多密碼系統都依賴大質數來建構
例如 RSA演算法 會用兩個質數p和q，兩個質數相乘得到的N，來N來當作系統運作時的參數，而要把N反向分解成p和q卻是很困難，有多困難也就決定了密碼的強度
高深的數學實在看不懂，不過把N反向分解成p和q倒是很有趣的問題，請問
. 一般所謂的128bits的密碼系統，N、p、q 的範圍大概是多大的數啊？
. 網路上已經有人發現很大的質數，把所有已經發現的質數都拿來除N，這樣也會很困難嗎？
. 如果發現方法可以很快的把N反向分解成p和q，經濟會不會崩潰啊？
請高手教一教
3Q
個人積分：50分
文章編號：14605344
個人積分：16分
文章編號：14606365
個人積分：510分
文章編號：14652097
個人積分：0分
文章編號：14652211
個人積分：111分
文章編號：14652222
個人積分：510分
文章編號：14653690
個人積分：16分
文章編號：14657924
依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
可是這背後所需要付出的成本與時間都是難以想像的
個人積分：12分
文章編號：14660274
個人積分：510分
文章編號：14682270
關閉廣告