› 看板 NTUE-CS98 關於我們 聯絡資訊
作者aeolus1215 (663jI )
看板NTUE-CS98
標題[轉錄]Re: [新聞] 美德數學家 發現超大質數
時間Mon Sep 22 03:43:37 2008
※ [本文轉錄自 Gossiping 看板] 作者: flamesky (豬也會跑哦) 看板: Gossiping 標題: Re: [新聞] 美德數學家 發現超大質數 時間: Fri Sep 19 22:32:33 2008 ※ 引述《ainor (><)》之銘言： : http://www.csie.nctu.edu.tw/~rjchen/BigPrime.files/show.htm : 公鑰密碼系統需要大質數 : 自從1976年Diffie和Hellman提出公鑰密碼系統(public-key cryptosystem)的觀念 : 之後，許多演算法例如Diffie-Hellman密鑰交換(1976)、RSA加密(1978)、ElGamal數位簽 : 章(1985)紛紛提出，應用在包括資料加密以及數位簽章等實際用途上。這些公鑰密碼系統 : 都有一個共通點：需要大質數來建構其系統；RSA演算法需要兩個質數p和q相乘得到的N來 : 當作系統運作時的參數，Diffie-Hellman演算法以及數位簽章標準(DSS)則需要質數p來構 : 成一個有限體(finite field) Zp以供系統運作。更重要的是，這些公鑰密碼系統的「安 : 全強度」往往取決於所選擇的質數大小以及強弱(這裡的強弱是指有些質數具有較弱的性 : 質，例如，如果p-1的質因數都太小，就容易被攻擊者用特殊的攻擊法攻擊)；對RSA演算 : 法來說，其強度決定於「大數分解」的困難度，至於對Diffie-Hellman演算法及DSS而言 : ，其強度則決定於Zp上的離散對數問題的困難度。因此，如何找到一個大的質數來構成我 : 們所需要的安全公鑰密碼系統，就成為一個重要的研究課題。 : ----------------------------------------------------------------------------- : 隨便找都有資料 : 有沒有某些鄉民，自己無知算了，還怕別人不知道的八卦 : 還有沒有人要問算那麼大的要幹嘛？ 看到這裡，我也說說加密算法相關的東西， 說到加密算法，就不得不提到信息論裡面一個叫信息量的東西， 對于網絡應用，有些是保証信息量的算法，有些卻是損失的， 對于這些算法，各位可以將其看成一個函數f， 作用在一些信息X上，即f(X) 以下講一些加密的一些概念， 首先談談無損的加密（其實無損壓縮什麼的也可以套用） 還是用f舉例： 信息 加密算法 密文 f X--------------->f(X) <-------------- F 如果我們可以找到一個f的反函數F，使得F(f(X))=X 那麼這種算法對于X是對稱或者可逆的,這是一個無損的算法。 因為f(X)中包含X的全部信息，只要通過F，就可以還原X 一下講傳輸信息的雙方稱為Alice和Bob 所以： 加密算法舉例： 將英文字母a,b,c,d...z 對應 01,02,03,04....26這種做法記做f 如： Alice 傳abc給Bob,那她可以用f作用：f(abc)=010203, Bob受到之後，用F（f的反函數和f作用正好相反）作用于密文F(010203)=abc 這種算法其優勢是通信雙方都可以使用同一套固定的系統進行大量數據傳送， 典型的應用就是莫爾斯碼，當然實際算法沒那麼簡單，這種算法叫對稱加密 但是有個很大的缺陷，這個方法必須Alice偷偷告訴Bob他要用哪個F解密， 不然： Alice:Bob你用F解密（大聲） Bob：原來我是用F哦 謎之音：原來她的密文可以用F解密哦。。 Alice:密文發送中 Bob：解密中 謎之音：偷看中。。。 這裡的問題就在于：網絡是個公共空間，一個人發的信息大家都能聽見。 如何能在公共空間裡沒有私下交流的情況下把東西傳給對方呢。 這裡，數學家們想了個辦法： 通信分兩步： 1.Bob自己找一對f和F，然後 Bob:Alice你用f加密哦（大聲） Alice:哦，用f 謎之音：用f，（筆記ing） 2.Alice將f(abc)=010203發給Bob Bob:偷偷用F一下，F(010203)=abc,收到 謎之音：靠腰，010203，這是什麼，（傻眼中） 即原來的過程變為 Alice| Public | Bob 1. abc |<--f------| F，f | | 2.f,abc|--f(abc)->|F,f |F(f(abc))=abc 好了，這下安全了吧 謎之音：媽搭媽搭！ 既然f是a變01，b變02，那麼反過來就行嘍，010203->abc 這裡的問題就是，知道f，反過來求F太容易了， 但是聰明的數學家知道，數學裡，很多可逆的算子反過來求並不容易： 比如說質數分解的問題，p，q兩個質數乘起來為n容易，但想知道n是哪幾個 質數的積就很困難了。（這種例子在數學中大量存在，如指數對數，微分積分，不贅述） 于是出現很多天才的加密算法，如前所說的RSA算法即以大質數分解為基礎 還有ECC橢圓曲線算法（Matrix裡面一堆綠字在閃的就是這種，因為涉及到大量的 代數幾何的專業知識，就不講了，有興趣可以去google） 這裡在只有一方知道密鑰(F),大家知道公鑰（f）的過程，叫非對稱加密 ------------------------------ 那麼，這下安全了吧，NO！ 謎之音:大絕來了！ 因為Bob找Alice需要出示暗號──密碼，証明自己是Bob（因為在網路上誰也不認識） 但是密碼明顯不能公開傳播，于是就使用加密算法 設Bob密碼aaa Alice發了一個公鑰g給Bob讓Bob加密 （比如g是換成數字後數位顛倒下z->62,a->10) Alice:這是g，密碼呢？ Bob：g(aaa)=101010.（以下大聲）101010,公鑰f Alice：G（101010）=aaa，的確是Bob,他的公鑰是f Alice:加密數據發送中 謎之音：偷聽到101010 。。。 深夜，Bob夢遊不在線 謎之音：Alice，我是Bob，這是g(aaa)=101010，公鑰f'，快點把東西加密發給我 Alice:G(101010)=aaa,他是Bob，換了個公鑰叫f'，無所謂，密碼對了，發資料 密之音：收到，解密中（注意，這個f'不是上次那個f了） 會出現這種情況因為Alice往往要服務很多人，並不會把Bob的f一直記得 而Bob也會在每次通訊時選個新的f,F,這就為有人冒名提供了便利。 ------------------------ 于是Bob的大絕來了， Bob：先用自己的密鑰F加密aaa=F(aaa), 再用Alice的公鑰g加密F(aaa)得到g(F(aaa)), 發送給Alice的是：（大聲）g(F(aaa))和自己公鑰f Alice：用自己密鑰G作用密文：G(g(F(aaa)))=F(aaa), 用Bob的公鑰作用：f（F(aaa))=aaa,的確是Bob 迷之音:故技重施:g(F(aaa))和自己公鑰f' Alice：G（g(F(aaa)))=F(aaa),f'(F(aaa))=$%^@# 。。。（幹，你騙鬼哦） 而一般情況下，這個密碼是和要傳輸的文件一起放在一個包裡發的， 而且密碼一般是從文件生成的，一般是用來加密文件用的，不然 謎之音：我是Alice，這事我的g' Bob：g'(F(aaa))，公鑰f 謎之Alice:行啦，這是你要的東西 f(G'(...）) Bob：F(f(G'(...)))=G'(...), g'G'(...)=... ... Bob：幹，中毒了，這不是我要的東西 還有一種可能：終極大絕來了 Alice手下小弟：對不起，其實，我是個臥底 （偷看屏幕）原來Bob的密碼是aaa啊，回家偷上Bob的MSN -------------------------- 于是要講到會損失信息量的算法，一般計算機裡叫Hash算法， 就是會丟失信息的不可逆算法 最直接的例子就是求余數 如求被7除的余數記為h， 原文為9，加密：h（9)=2, 那麼h(?)=2（2？9？16？23?...） 同樣的原文加密可能會一樣，但是大家注意一點， 對于身份的驗証，我只需要知道Yes or No,不需要像傳文件一點不能錯 其實就想大家算加法驗算一樣，算算最後一位數字對不對就差不多了 這裡依靠的是概率，當h是某一個很大的質數求mod時，那麼在固定范圍類 的兩個數余數會同樣的概率就大大減小了 大名鼎鼎的MD5算法就是基于這個原理， 各位在輸入MSN密碼時，其實服務器只知道你的密碼的MD5值， 並不能看到你的密碼，如果帳戶名和MD5值符合就算登錄 其實不同密碼同一MD5值可能一樣，但是那樣的概率，大概地球人沒人 用100個ID都碰不上一樣的。 同樣的，文件也可以用MD5加密， 對于上面文件傳輸中出錯的可能， 對于每傳輸一個文件，就用這種算法把文件算出一個值做密碼然後加密傳輸， 這樣保証了文件在傳輸過程中不會出錯，而且在發送文件時也進行加密 保証了不會有人冒充發送文件 寫了這麼多，因為本人非IT相關系科，講的不好希望大家能看懂， 其實無損有損壓縮有很多方法，比如傅裡葉變換(jpg圖片,mp3)這些 數學的應用其實在生活中還是蠻多的，只是平時我們沒有感覺到而已 -- 單身男人的三不原則 不主動，不拒絕，不負責 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 116.235.217.205
推 seymour72325:你....你....說的是中文嗎Q___Q? 09/19 22:33
推 ec75123:推 09/19 22:34
推 startlequiet:看了有點暈 轉信箱慢慢研究 09/19 22:34
→ GunsNRoses:我END 09/19 22:34
推 temuro:wow ... 雖然我很認真的想要去理解，卻真的不懂… 09/19 22:36
→ jock78:文組霧撒撒 09/19 22:36
推 kidkuang:講得不錯ㄚ 概論齁~~ 09/19 22:36
推 a28829424:太有道理了 (假裝完全看懂) 09/19 22:36
推 widec:太精彩了!!!真是好文!!!!(快稱讚 不然人家就知道我看不懂 09/19 22:36
推 TroyLee:為啥總是喜歡用 Alice 和 Bob ? 09/19 22:37
推 dosser:阿鬼!你還是說中文吧... 09/19 22:37
推 startlequiet:這一篇文章值 1000 銀 認真程度值得再推 09/19 22:37
推 tasogare:好帖我頂!!!!! 09/19 22:37
推 ispy03532003:對不起 我看不懂 Orz... 09/19 22:37
→ TroyLee:這不難理解吧 @@a 09/19 22:38
推 aceliang:...看沒有耶... 09/19 22:38
推 timking:有知識沒八卦..... (拉板凳) 09/19 22:39
→ ZMittermeyer:不難理解...基本數學用語而已　看仔細點吧@@ 09/19 22:39
推 tenshoufly:大概了解...不過也不算很懂果然學物理跟學數學還是有差 09/19 22:39
推 ss60115:借轉 3q 09/19 22:39
推 vi000246:專業給推　等等再看 09/19 22:40
推 Gooooooogle:太精彩了!!(快稱讚 不然人家就知道我看不懂 09/19 22:40
推 ttpshb03:我真的看無耶- - 認真文給你推一個 09/19 22:40
推 wolfer:看八卦長知識~ 09/19 22:40
※ 編輯: flamesky 來自: 116.235.217.205 (09/19 22:42)
→ jock78:阿鬼我再這,讓專業的來 09/19 22:41
推 chungsen:這就是實際上在用的密碼學啊... 09/19 22:41
→ TiaraWei:1000銀...真的是自己打的 09/19 22:42
推 arsonlolita:快點推不然被笑看不懂 09/19 22:42
推 ErinChu:專業不推會對不起良心 09/19 22:42
噓 TsengWeichen:支那人來亂了 大家快噓 這文跟三鹿一樣有毒 09/19 22:43
推 pilipilifans:推~雖然我不懂 09/19 22:44
推 probsk:看BBS記得先掃毒啊 09/19 22:44
推 knetlalala:上海人 難怪遣詞用字有點不太習慣@@" 09/19 22:44
推 wallace79:呃…我竟然看的懂，學生時代有學過 09/19 22:45
推 IMISSA:推 後面就看不懂了QQ 09/19 22:45
推 windward:資工的有修密碼學應該都有教 09/19 22:45
推 lilicoco520:推一個 辛苦了 讓我想起上學期期中考( ￣ c￣)y▂ξ 09/19 22:45
推 kcyy:JPG不是用離散餘弦轉換嘛?可能我記錯吧... 09/19 22:45
→ gain:趕快推不然別人以為我們看不懂 09/19 22:46
推 Cathay:哦～原來如此呀（快推裝懂） 09/19 22:46
推 Doub1eK:我數學系又修過密碼學 看到後半段也有點看不懂〒△〒 09/19 22:46
推 CYNDl:我看得懂喔 專業專業 推推 09/19 22:47
→ Doub1eK:我太混了 Orz 09/19 22:47
→ flamesky:樓上，是我記錯，JPG用的是DCT，因為我不是專業學這個的 09/19 22:48
推 ariesgolem:推你一下 雖然不知道你再寫三小朋友 09/19 22:48
→ zvx1232003:你在幹嘛? 09/19 22:48
推 tarinmind:1000銀 09/19 22:49
→ flamesky:我就是學數學的，業余時間會看看IT類的東西 09/19 22:49
推 DWR:用語還好阿，看起來也沒有很對岸化 09/19 22:50
推 Pash77:寫得不錯~ 淺顯易懂 09/19 22:50
推 SepHiRoS:推一個 支那也是會po專業文的 09/19 22:51
推 knetlalala:可是我看到一半就覺得是大陸人寫的耶@@ 09/19 22:51
推 ILoveRiva:我認為新趨勢是找新的function，也就是新的演算法 09/19 22:51
推 shy723:END 09/19 22:51
噓 bloodycross:紅的明顯..http://tinyurl.com/46sxnk MD5可碰撞 09/19 22:51
→ DWR:傳輸信息 傅裡葉 大概這個比較明顯XD 09/19 22:52
→ bloodycross:原PO的MD5解釋有誤 09/19 22:52
→ flamesky:恩，很明顯吧，因為兩岸口頭還好，專業用語差蠻多的 09/19 22:52
→ ILoveRiva:Input:X output:F(X) 有沒有更屌的F 找出來 是美俄趨勢 09/19 22:52
推 zsh:解釋的還滿淺的 09/19 22:53
推 etfofts:太用心了 不推不行 09/19 22:53
推 ping0519:推 ~ 09/19 22:53
推 nosod:看不太懂 09/19 22:54
→ flamesky:回b大，這則新聞我也看過，不過這是知道MD5情況下構造的 09/19 22:55
推 smileofblue:快推 不然別人以為你看不懂 09/19 22:55
推 invigorator:一篇專業文 巴死多少不懂裝懂的白目 09/19 22:56
推 freewash:那這樣這篇是業餘文囉！ 09/19 22:56
推 qq2107:阿這不就只是普通的密碼學而已..... 09/19 22:56
→ flamesky:這個用來對付刻意制造的沖突的確無效，本來這就是用概率 09/19 22:56
推 souening:嗯 這樣說蠻合理的 我也這麼認!! 09/19 22:57
→ flamesky:的算法，如果刻意為之肯定會有碰的，只是方法比較復雜 09/19 22:57
→ momogo11:ORZ......... 09/19 22:57
推 ILoveRiva:高中一年級 第零章 就在講 邏輯 真值表 跟這個函數群 09/19 22:58
→ ILoveRiva:高三 理科數學 有更深入的探討 有認真念高中的 就看得懂 09/19 22:58
推 xxx22088:感覺已經很深入淺出了　但是跟我還是很遙遠～ 09/19 22:59
推 jock78:媽,我考上大學居然看不懂 09/19 23:00
→ abian:不懂 囧 09/19 23:00
→ jock78:IL想戰就說嘛(~^O^~) 09/19 23:01
→ abian:不過推一個..@@ 09/19 23:01
推 timmerix:推 每天都在接觸 看得懂 09/19 23:02
推 st60213:可是我高中念社會組耶 高三沒念理科數學 (我承認我不認真) 09/19 23:02
→ jock78:阿扁推祖國人 09/19 23:02
→ timmerix:我這學期密碼學等於修完了XDD 09/19 23:02
推 ilikethee:好艱深的八卦XD 09/19 23:02
推 ttuenzo:我竟然看得懂...還好我有修過資訊安全= =" 09/19 23:04
推 superbabaya:我只知道九淺一伸....... 09/19 23:04
推 realestate:有看有推 雖然說深入簡出 可是還是看得頭昏腦脹 09/19 23:05
推 jackloutter:不錯 推 09/19 23:05
推 keepoo:加密這種東西其實是很弔詭的　XD 09/19 23:06
推 weinine32:寫得滿精采的，多謝分享，不過有點看不懂，所以每個MSN 09/19 23:06
推 buthow:Is it good to drink ? 09/19 23:07
→ weinine32:都放要除數(7)，然後傳送 密碼除以7的值給 SERVICE? 09/19 23:07
推 jokker:推 09/19 23:08
推 mayloveonly:趕快推免得人家以為我看不懂 09/19 23:08
→ weinine32:那骸客入侵用戶端的電腦找出MSN的除數7 一樣可以破解阿 09/19 23:09
→ flamesky:w大，原理類似，但不是用7，“除”出來的東西還蠻長的 09/19 23:10
推 atana:快推~ 免得有人說鄉民都看不懂 09/19 23:10
推 kcyy:嗯~離散餘弦轉換就是DCT~大學沒修工數還要寫這個程式~昏頭了 09/19 23:10
推 sttp:專業文!! 09/19 23:11
→ flamesky:MD5算法是公開算法，但是求解是比較困難的 09/19 23:11
推 doit1911:專業文!!!! 大學裡有教!!!!!!!!!!!!! 09/19 23:13
→ flamesky:就好像你知道三角函數，但是給你一個數反求符合其的某一 09/19 23:13
推 ePaper:看不懂 囧 09/19 23:13
→ flamesky:角度不是很容易的，如 sin(?)=0.3這種問題 09/19 23:14
推 ETTom:看到就頭昏了...囧rz 09/19 23:17
推 ILoveRiva:原PO只是在講基本的函數跟反函數的應用而已... 09/19 23:17
→ ILoveRiva:講錯 不是反函數 是 Input process output 三者關系 09/19 23:18
推 akanokuruma:看懂七成 大概上都是密鑰的觀念 這對於讀資訊的學生 09/19 23:18
→ akanokuruma:來說算是入門 09/19 23:18
推 CREA:快推 不然人家會以為我們看不懂 09/19 23:18
→ timmerix:原PO可否順便說明下DES加密？ 09/19 23:18
推 weinine32:喔看懂了謝謝 09/19 23:19
推 WhoopsNow:看不懂但推認真文 09/19 23:27
推 erc:推 09/19 23:28
推 SHANGOYANYI:資安概論? 09/19 23:34
→ flamesky:因為非工程專業，不懂DES加密，google了一下，看了下原理 09/19 23:34
→ flamesky:其實本質上就是一個多層加密算法f1(f2(f3(..f16(X)))) 09/19 23:36
→ flamesky:而解密則使用f16(f15(..f1(Y)），是個對稱算法 09/19 23:38
推 DTapir:我竟然看的懂耶～你好利害 09/19 23:38
→ flamesky:即加解密用同一套密鑰 09/19 23:39
推 xinu:工程專業也不一定有修資訊安全啊(推眼鏡) 09/19 23:40
推 Bluecold:哎呀 所以這篇文章要用什麼解密法解密? 09/20 00:01
推 JSD:耶~~從頭到尾看懂了(~^O^~) 09/20 00:01
→ JSD:PTT的密碼在主機那邊也再加密過了~一樣的道理吧~ 09/20 00:02
推 INSISTBELIEF:= =+為什麼人名跟我密碼學的書是一樣的..你照抄的吧 09/20 00:16
推 EVA01:很好, 我數字科目被當都是真的..Y 09/20 00:24
推 secretbear:喔喔喔 （三洨） 09/20 00:26
推 vovzz:高手.... 09/20 00:27
→ flamesky:Alice和Bob這是國際慣例好像，我之前有挺過一個量子計算 09/20 00:27
推 easy618:推 看某 09/20 00:28
→ gdgy:就好像影象處理都是用那位 play boy 女郎 09/20 00:29
→ flamesky:方面的講座，那個人也用Alice和Bob 09/20 00:29
推 devilangel:還不錯阿 解釋的很生動 推一下~ 09/20 00:33
推 yamigo:科科又是 alice 跟 bob 的故事 , 密碼學看多了 =..= 09/20 00:36
推 mmeow: 為什麼要用 "于" 害我以為大陸人寫的 09/20 00:37
噓 imprezasti:阿不就照抄密碼學課本 09/20 00:39
→ flamesky:我就是大陸鄉民啊XD 09/20 00:41
→ flamesky:i大，我只是在學校一次在教室睡覺聽到這門課講這個，就記 09/20 00:42
推 wackyjazz:推傅立葉轉換 09/20 00:43
→ flamesky:下了，因為我沒上過密碼學，倒是上過infromation theory 09/20 00:43
→ flamesky: or 09/20 00:45
→ Waleela:阿鬼 09/20 01:39
推 romo:認真推一個 講的淺顯 09/20 01:41
推 lamontlui:哭哭 旁聽就這麼強 09/20 01:44
推 SMARTSMART:順便一提 adversary常用Eva或是Oscar 別我為啥XD 09/20 01:58
推 anbr:看完好睏.. 09/20 02:14
推 ccbbaa:幫推一個~~~ 09/20 02:37
推 eggbird:看到想睡覺...專業推~ 09/20 02:43
推 ticketwoon:推 09/20 02:45
推 Gokinyou:認真就要給推啊。 09/20 02:51
推 jimmyhero:艾莉絲跟包柏....PAPER上常常用到= = 09/20 02:57
→ jimmyhero:就是電腦算相乘很簡單 但是要拆解一個大數字很難.... 09/20 02:59
推 moo1211:實用 09/20 03:03
推 leinru:快笑不然別人以為我看不懂 09/20 03:09
推 warlocks:看八卦 長知識 09/20 03:10
噓 ethanjava: 不少錯誤和誤解 還有這裡是台灣... 09/20 03:20
推 anitai:酷耶 推 09/20 05:56
推 hisehise9707:一大早看到這篇精神都來了@@ 09/20 08:17
推 show172:. 09/20 11:32
推 Yie:前半段不錯，後面就看不太懂了。 09/20 12:29
推 abc0:給你推 09/20 12:32
推 palpi:這裡是台灣 所以? 09/20 14:12
推 spittz:看...看不懂... 09/20 14:13
推 andotsubasa:跨隴謀.. 09/20 14:30
推 ymcg:有笑有推.... 咦，不是笑話喔？ 09/20 17:16
推 s60984:Good 09/20 18:43
推 iamgyfan:幹我以後一定要修這門課 09/20 23:07
推 loopuntil:這念資訊又修過密碼學的的應該都看得懂吧... 09/20 23:13
推 s4511981:推認真（茶） 09/21 00:54
推 sheepmaymay:END... 09/21 01:18
推 Bigcookie2:!!!!看不懂!!!!但是一定要推專業 09/21 01:20
推 DeathDeath:明明這篇根本就沒有什麼艱深字彙 還寫的很完整 09/21 10:05
→ DeathDeath:不知道end和酸的人的心態是什麼 09/21 10:05
→ DeathDeath:有學過國中函數反函數的觀念就可以看懂這篇文章了 09/21 10:06
→ DeathDeath:另外 很佩服原po認真解說 在數字板寫認真文需要勇氣 09/21 10:09
推 newest:死死耶XD 09/21 13:56
推 DeathDeath:loll 09/21 21:38
推 MrBaa:請問 您是說中文嘛@@?? 09/22 00:09
推 aeolus1215:借轉 09/22 03:43
--
→ whsfun:挨呀 畢竟那天只撐了30秒... 210.66.228.20 08/14
推 Calaglin:30秒(抖) 218.171.171.3 08/14
→ annaheart:吼～都只有你自己盡興而已～ 219.81.207.254 08/14
-- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 59.105.220.111
推 cair:jpg沒有用到FT是用離散餘弦轉換 09/22 08:13
推 cair:密碼學的部分則是大致都對 09/22 08:14
→ wayne750213:end 09/22 18:08