[轉錄]Re: [新聞] 美德數學家 發現超大質數
※ [本文轉錄自 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
推
09/19 22:33,
09/19 22:33
推
09/19 22:34,
09/19 22:34
推
09/19 22:34,
09/19 22:34
→
09/19 22:34,
09/19 22:34
推
09/19 22:36,
09/19 22:36
→
09/19 22:36,
09/19 22:36
推
09/19 22:36,
09/19 22:36
推
09/19 22:36,
09/19 22:36
推
09/19 22:36,
09/19 22:36
推
09/19 22:37,
09/19 22:37
推
09/19 22:37,
09/19 22:37
推
09/19 22:37,
09/19 22:37
推
09/19 22:37,
09/19 22:37
推
09/19 22:37,
09/19 22:37
→
09/19 22:38,
09/19 22:38
推
09/19 22:38,
09/19 22:38
推
09/19 22:39,
09/19 22:39
→
09/19 22:39,
09/19 22:39
推
09/19 22:39,
09/19 22:39
推
09/19 22:39,
09/19 22:39
推
09/19 22:40,
09/19 22:40
推
09/19 22:40,
09/19 22:40
推
09/19 22:40,
09/19 22:40
推
09/19 22:40,
09/19 22:40
※ 編輯: flamesky 來自: 116.235.217.205 (09/19 22:42)
→
09/19 22:41,
09/19 22:41
推
09/19 22:41,
09/19 22:41
→
09/19 22:42,
09/19 22:42
推
09/19 22:42,
09/19 22:42
推
09/19 22:42,
09/19 22:42
噓
09/19 22:43,
09/19 22:43
推
09/19 22:44,
09/19 22:44
推
09/19 22:44,
09/19 22:44
推
09/19 22:44,
09/19 22:44
推
09/19 22:45,
09/19 22:45
推
09/19 22:45,
09/19 22:45
推
09/19 22:45,
09/19 22:45
推
09/19 22:45,
09/19 22:45
推
09/19 22:45,
09/19 22:45
還有 109 則推文
推
09/20 02:43,
09/20 02:43
推
09/20 02:45,
09/20 02:45
推
09/20 02:51,
09/20 02:51
推
09/20 02:57,
09/20 02:57
→
09/20 02:59,
09/20 02:59
推
09/20 03:03,
09/20 03:03
推
09/20 03:09,
09/20 03:09
推
09/20 03:10,
09/20 03:10
噓
09/20 03:20,
09/20 03:20
推
09/20 05:56,
09/20 05:56
推
09/20 08:17,
09/20 08:17
推
09/20 11:32,
09/20 11:32
推
09/20 12:29,
09/20 12:29
推
09/20 12:32,
09/20 12:32
推
09/20 14:12,
09/20 14:12
推
09/20 14:13,
09/20 14:13
推
09/20 14:30,
09/20 14:30
推
09/20 17:16,
09/20 17:16
推
09/20 18:43,
09/20 18:43
推
09/20 23:07,
09/20 23:07
推
09/20 23:13,
09/20 23:13
推
09/21 00:54,
09/21 00:54
推
09/21 01:18,
09/21 01:18
推
09/21 01:20,
09/21 01:20
推
09/21 10:05,
09/21 10:05
→
09/21 10:05,
09/21 10:05
→
09/21 10:06,
09/21 10:06
→
09/21 10:09,
09/21 10:09
推
09/21 13:56,
09/21 13:56
推
09/21 21:38,
09/21 21:38
推
09/22 00:09,
09/22 00:09
推
09/22 03:43,
09/22 03:43
--
→
210.66.228.20 08/14,
210.66.228.20 08/14
推
218.171.171.3 08/14,
218.171.171.3 08/14
→
219.81.207.254 08/14,
219.81.207.254 08/14
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 59.105.220.111
推
09/22 08:13, , 1F
09/22 08:13, 1F
推
09/22 08:14, , 2F
09/22 08:14, 2F
→
09/22 18:08, , 3F
09/22 18:08, 3F
討論串 (同標題文章)
完整討論串 (本文為第 1 之 2 篇)：