Re: [轉錄][資訊] 卡巴斯基發佈具危險性的新型勒索 …
※ 引述《mrgold29 (方方黃黃 伸縮自如)》之銘言：
引言恕刪
: 卡巴斯基實驗室成功的阻擋了以前 Gpcode 的變種，在仔細的分析這些加密過的檔案之後
: ，卡巴斯基病毒分析師即可破解私人金鑰。
: 卡巴斯基實驗室病毒分析師必須經過精密RSA演算來進行分析破解超過660位元的金鑰。要
: 完成這個工作，若採用一部 2.2 GHz的處理器的電腦則需花 30年的時間來破解一個660位
: 元的金鑰。而Gpcode的發起者已經花了兩年的時間加強這個病毒：從前的失誤已經被修復
: ，而金鑰也已經從原本的660位元加長至1024位元。
→
06/10 22:36,
06/10 22:36
我的研究領域不是密碼學，如有遺漏還望各位先進補完
如果病毒使用的是RSA-1024，而且它用的方法沒有任何漏洞的話
很遺憾的，幾乎不可能被破解，不管今天防毒軟體是是卡八弱盾還是江民金山
這已經是密碼學的問題了，RSA就我所知目前沒有找到有效的方法可以加速破解
因此剩下來的方法就是硬碰硬，用暴力法去解他的私鑰，除此之外別無他法
所以問題就回到了RSA究~竟~有多難用暴力法破解
我實在不想詳述RSA的演算法，簡單的說，目前要破解RSA就是必須做因式分解
沒人證明因式分解是求得私鑰的唯一方法，但是目前(至少公開的)已知只有這個方法最快
因式分解非常難，目前(至少公開的)已知方法中沒有夠快的方法
(用術語來說是沒有polynomial time的通用解，至於特殊解...我不知道有沒有囧)
如果你可以分解出RSA中用到的兩個大質數，你就破解它了
1024bits表示你選的兩個質數有1024的bits這麼大，這個數字用十進位法寫，有309個數字
這兩個數乘起來後要做因數分解，很困難
那麼有沒有人破解過1024 bits的因數分解呢？
就我所知最接近的是去年的307位數因式分解紀錄，這個數字是1023個bit
http://0rz.tw/064fw
1023bits，聽起來只差一個bit，但是很不幸的是"這是一個特殊解"
這表示這兩個質數有一些性質，可以比平常更快的被因式分解
為了算出這樣的一個特殊解，花掉了多少時間呢？11個月，但是他用的肯定不是PC
雖然他們也沒寫出他用了怎樣的配備，不過不是超級電腦就是叢集/網格之類的怪物
報導指出換算成一般電腦大約要100年
那麼最接近的"通解"，就是沒有投機取巧的因數分解又怎麼樣呢？
目前記錄是2005年，663bits，200位數的因式分解，花了18個月
換算成2.2 GHz Opteron的CPU，他們預估大概要跑55年
除非今天病毒使用的RSA演算法存在漏洞，否則被加密完的檔案
在沒有私鑰的情況下，幾乎不可能救的回來，因為暴力法太難算了
如果拿Earth Simulator / Blue Gene / Roadrunner之類的機器跑應該會快的多
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.136.8.4
※ 編輯: vintw 來自: 220.136.8.4 (06/11 00:58)
推
06/11 00:58, , 1F
06/11 00:58, 1F
推
06/11 08:36, , 2F
06/11 08:36, 2F
推
06/11 09:02, , 3F
06/11 09:02, 3F
→
06/11 09:02, , 4F
06/11 09:02, 4F
推
06/11 09:27, , 5F
06/11 09:27, 5F
推
06/11 17:02, , 6F
06/11 17:02, 6F
推
06/11 19:19, , 7F
06/11 19:19, 7F
→
06/12 07:39, , 8F
06/12 07:39, 8F
推
06/12 20:37, , 9F
06/12 20:37, 9F