[轉錄]Re: [新聞] 美德數學家 發現超大質數
※ [本文轉錄自 Gossiping 看板]
作者: Freak1033 (金が信念! XD) 看板: Gossiping
標題: Re: [新聞] 美德數學家 發現超大質數
時間: Fri Sep 19 23:44:53 2008
※ 引述《ainor (><)》之銘言:
: http://www.csie.nctu.edu.tw/~rjchen/BigPrime.files/show.htm
: <恕刪>
: -----------------------------------------------------------------------------
: 隨便找都有資料
: 有沒有某些鄉民,自己無知算了,還怕別人不知道的八卦
: 還有沒有人要問算那麼大的要幹嘛?
請問您非常有知嗎? 這麼大脾氣就說別人無知?
我不認為會用 google 就有資格數落別人了. XD
我就直說了吧, 我在實驗室的主要研究領域就是密碼學與因數分解,
我可以斷言這麼大的質數在密碼學(至少在 RSA 上)沒有任何的實用價值,
而一堆人在產生這麼大的質數, 目的只是對純數學之神秘的探索而已.
為什麼說這麼大的質數在 RSA 上沒有任何實用價值呢? 起碼有以下原因:
1. 在 RSA 上面需要用的質數除了要夠大以外,
最重要的是要能夠兩個質數的乘積必須難以被它人分解.
而主題中所提到的質數其實是一個梅森質數,
它是一種具有特殊型狀的質數(二的冪次減一夠特別了吧?),
因此存在的候選並不多(事實上現在也才發現了 40 個梅森質數),
一下就會被猜中, 更糟的是它已經被公開出來了, 就等於沒有用了.
要是哪個傻子跟我說他的 RSA key 有 5 MB 那我一定馬上笑出來. A_A
2. 在實用上我們不會用到 Lucas-Lehmer test 來驗證質數,
就算我們要用大質數, 也只要用 Miller-Rabin test 就可以了.
這兩種測試的差別在於, Lucas-Lehmer test 能夠產生出一組 certificate,
藉由它你可以在很短的時間內驗證出該數 100% 是個質數.
而 Miller-Rabin test 則沒辦法產生出這種 certificate,
它是一種隨機演算法, 只能保證對於某個合數在隨機測試中,
有起碼 3/4 的機率它會被抓包出來是合數, 但是它沒辦法完全證明某個數是質數.
(note: 除非 generalized Riemann hypothesis 被證明為真)
在實務上, 其實我們不太需要那麼 100% 的證明,
我們只要多跑幾次 Miller-Rabin test, 而某個數沒有被抓包,
我們就可以相信它 99.999999% 是個質數, 那就夠用了. :p
所以我說原本新聞上所講的尋找質數多半只是對於數學神秘的探究,
而並非作為實際加密應用目的. :p
3. 用太大的 key 除了會降低破密速度以外, 同時也會讓正常的加解密變慢,
光是用 RSA-1024 來做加解密就得花上大約 0.1 sec 的時間,
而我們知道, 加解密的時間"至少"與 key 的長度成正比,
也就是說 RSA-43112609 起碼得花上一小時才能進行一次的加密. XD
而用這麼大的質數是否能帶來額外的安全性呢?
事實上是沒有, 目前地球上最快的因數分解實作剛好是我們的作品,
前日才剛投稿到 Eurocrypt. 我們估計出來,
目前實用上能夠破到最大的 RSA 大約是 RSA-768,
而這需要價值三百萬美元的機器與半年的計算時間.
以個人使用而言 RSA-1024 已經足夠安全,
而政府機關則是推薦使用 RSA-4096. (中華民國行政院的 key 便是 4096)
4. RSA 現在已經快要走到盡頭了, 自從 GNFS 發明之後,
為了達到足夠的安全性, 所採用的 key 必須越來越長,
使得加解密時間也越來越久.
現在密碼學界所注目的 PKI 已經漸漸轉移到 elliptic curve based system,
以及 multivariate quadratic system. 其中又以後者特別讓大家興奮,
因為一般的 MQ 問題已知是屬於 NP-hard 問題,
假使能夠產生某種 MQ trapdoor 使得產生出來的 key space 是所有的 MQ instance,
那麼除非能夠發現 P = NP 的演算法(which is believed not exist),
不然 MQ 的系統可以認為是安全的.
另外目前也尚未發現解 MQ 問題的量子演算法,
而質因數分解目前已知可用量子電腦破解,
只差技術上沒辦法造出足夠大的量子電腦.
---
感謝網友來信指正, 第三段的數據有修正.
--
「ふ…ふざけるな!そんあ短い咒文で、魔法を起動できるわけないだろうが!
お前わマウゼルの神に逆らう氣なのか?!傲慢な~」
「失禮致しました、誠實に全力でお相手致します。
第一戰術級‧軍用攻性魔法‧出よ、武雷神〈トール〉!」
〈スクラップド‧プリンセス〉
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.109.224.64
推
09/19 23:45,
09/19 23:45
→
09/19 23:45,
09/19 23:45
推
09/19 23:46,
09/19 23:46
→
09/19 23:46,
09/19 23:46
推
09/19 23:46,
09/19 23:46
推
09/19 23:47,
09/19 23:47
→
09/19 23:48,
09/19 23:48
推
09/19 23:51,
09/19 23:51
推
09/19 23:51,
09/19 23:51
推
09/19 23:51,
09/19 23:51
→
09/19 23:51,
09/19 23:51
推
09/19 23:51,
09/19 23:51
→
09/19 23:52,
09/19 23:52
推
09/19 23:52,
09/19 23:52
推
09/19 23:53,
09/19 23:53
推
09/19 23:53,
09/19 23:53
推
09/19 23:53,
09/19 23:53
→
09/19 23:53,
09/19 23:53
推
09/19 23:56,
09/19 23:56
推
09/19 23:56,
09/19 23:56
→
09/19 23:57,
09/19 23:57
推
09/19 23:58,
09/19 23:58
→
09/19 23:58,
09/19 23:58
推
09/20 00:00,
09/20 00:00
推
09/20 00:00,
09/20 00:00
推
09/20 00:00,
09/20 00:00
推
09/20 00:01,
09/20 00:01
推
09/20 00:02,
09/20 00:02
推
09/20 00:04,
09/20 00:04
→
09/20 00:04,
09/20 00:04
推
09/20 00:05,
09/20 00:05
→
09/20 00:05,
09/20 00:05
推
09/20 00:07,
09/20 00:07
→
09/20 00:08,
09/20 00:08
→
09/20 00:09,
09/20 00:09
推
09/20 00:11,
09/20 00:11
推
09/20 00:12,
09/20 00:12
推
09/20 00:13,
09/20 00:13
→
09/20 00:13,
09/20 00:13
→
09/20 00:13,
09/20 00:13
推
09/20 00:14,
09/20 00:14
→
09/20 00:15,
09/20 00:15
→
09/20 00:15,
09/20 00:15
→
09/20 00:15,
09/20 00:15
推
09/20 00:16,
09/20 00:16
→
09/20 00:16,
09/20 00:16
→
09/20 00:17,
09/20 00:17
→
09/20 00:20,
09/20 00:20
推
09/20 00:20,
09/20 00:20
→
09/20 00:21,
09/20 00:21
沒錯, 就是用橢圓曲線法來處理跑 1024-bits GNFS 之後生出來的那些"小"合數.
它們的範圍大約就是在 256-bits 上下.
我們這篇 paper 的主要價值在於使用 GPU 來計算,
我們都知道近代 GPU 的算術能力已經遠超過 CPU. :p
→
09/20 00:22,
09/20 00:22
→
09/20 00:23,
09/20 00:23
推
09/20 00:23,
09/20 00:23
→
09/20 00:23,
09/20 00:23
→
09/20 00:25,
09/20 00:25
※ 編輯: Freak1033 來自: 140.109.224.64 (09/20 00:26)
→
09/20 00:27,
09/20 00:27
推
09/20 00:41,
09/20 00:41
→
09/20 00:41,
09/20 00:41
推
09/20 00:43,
09/20 00:43
推
09/20 00:44,
09/20 00:44
→
09/20 00:46,
09/20 00:46
推
09/20 00:54,
09/20 00:54
推
09/20 00:54,
09/20 00:54
推
09/20 00:58,
09/20 00:58
推
09/20 00:59,
09/20 00:59
→
09/20 01:00,
09/20 01:00
→
09/20 01:01,
09/20 01:01
推
09/20 01:02,
09/20 01:02
→
09/20 01:24,
09/20 01:24
→
09/20 01:26,
09/20 01:26
推
09/20 01:47,
09/20 01:47
推
09/20 02:30,
09/20 02:30
→
09/20 02:38,
09/20 02:38
推
09/20 02:52,
09/20 02:52
推
09/20 02:53,
09/20 02:53
推
09/20 03:38,
09/20 03:38
推
09/20 03:38,
09/20 03:38
→
09/20 03:38,
09/20 03:38
推
09/20 03:42,
09/20 03:42
推
09/20 05:30,
09/20 05:30
推
09/20 09:39,
09/20 09:39
推
09/20 09:53,
09/20 09:53
→
09/20 10:37,
09/20 10:37
推
09/20 10:49,
09/20 10:49
推
09/20 12:34,
09/20 12:34
推
09/20 12:43,
09/20 12:43
推
09/20 13:43,
09/20 13:43
推
09/20 14:18,
09/20 14:18
推
09/20 16:15,
09/20 16:15
推
09/20 16:20,
09/20 16:20
推
09/20 16:23,
09/20 16:23
※ 編輯: Freak1033 來自: 140.109.224.64 (09/20 21:24)
推
09/20 21:44,
09/20 21:44
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 118.168.3.179
推
09/24 00:00, , 1F
09/24 00:00, 1F
推
09/24 00:01, , 2F
09/24 00:01, 2F
討論串 (同標題文章)
完整討論串 (本文為第 2 之 2 篇):