wutenan 's blog

先介紹幾個名詞
明文：也就是一般文字，沒有加上密碼，像是「今天晚上吃什麼」「this is a book」等等，一看就知道在說什麼的東西，如果是以英文書寫，習慣全以小寫書寫。
密文：經過加密的文字，像是「rup 1wu0 1j031g;41t 1gk65ai71」「WKLV LV D ERRN」，如果是以英文書寫，習慣全以大寫書寫。
鑰匙：特定演算法加密的細節參數，像第2句的鑰匙是3
以上3個名詞是密碼學中最常用到的常見名詞

加密解密過程
加密時，除了我們要加密的文字(即明文)，還鑰匙以及一個演算法
解密時也是一樣，除了所拿到的密文，我們需要同一個演算法以及鑰匙
這邊就用上面的明文「This is a book」以及鑰匙「3」做為範例
第1步，寫下明文「This is a book」
第2步，選擇一個演算法及一個鑰匙，這邊演算法選擇的是最基本的凱撒挪移法[*1]及鑰匙3
第3步，開始加密，t在英文中排序20，20+3=23變為W，h=8，8+3=11變為K
第4步，密文完成「WKLV LV D ERRN」，傳送給對方吧
第5步，對方收到密文，使用鑰匙跟演算法做逆演算，W=23-3 =20得到t，K=11-3=8得到h，以此類推，得到明文「this is a book」
以上5步為加密解密大致上的過程，名詞介紹的第1個範例「今天晚上吃什麼」就是一個「沒有鑰匙」、演算法為「舊注音」的加密解密，有興趣的人自己試一下就知道了

*1所謂的凱撒挪移法，就是先把英文寫成1-26的數字，然後鑰匙就代表著移動幾位，key=3，則a變D，key=6，則a變G，鑰匙的大小為25(也就是頂多a變Z，最多25種變法)

問題來了，只要有做傳送的動作，就會有被攔截的可能，我們就假設別人一定會攔到我們的密文吧，而攔到密文的同時，演算法其實八九不離十的也很容易猜中，因此演算法就假定為公開、每個人都知道使用的演算法是哪一種，剩下的，鑰匙就是解不解得開這則密文的關鍵，我們只能祈禱他不會猜到鑰匙。

鑰匙
鑰匙既然這麼重要，一定要慎選，像剛剛的凱撒挪移法，只有少少的25組鑰匙，根本用不到電腦，畫張字母表，25組鑰匙都硬猜，用手算都不超過30分鐘就能破解。若是我們改用替代演算法，那就有25!(約為4x10^26)組的鑰匙能用，就算1秒算1組，也要4x10^26秒，即起碼10^19年才能全部猜完。

鑰匙這麼重要，還有一項重點，那就是應該要怎麼傳送呢？密文用傳的，鑰匙也要用傳的，密文我們不怕攔截，鑰匙怕，因為當鑰匙被攔截下來，不用猜，直接就可以打開，鑰匙要怎麼傳呢？

以前，不是每件訊息都要加密時，大可以兩個人相約1個月見面一次，一次就給1個月份的鑰匙，或是給多久的鑰匙，當時要加密的訊息只有軍事訊息(所以才會有獵風行動，尼可拉斯凱吉演的電影，內容就是保護密碼員，自行參考)，大可以這麼做，但是到了現代，每天都在網購每天都在傳些不想讓別人知道的訊息，鑰匙怎麼發…每天為了換鑰匙就夠你累死，若是請第3者負責傳送鑰匙，難保不會像密文一樣被攔截，或是第3者自己把鑰匙偷走等等的問題，所幸，1974年，衛德費迪菲及馬丁黑爾曼想出了解決的辦法。

對稱鑰匙
講到這邊，先重頭整理一次
為什麼需要加密？
如果A跟B兩個人，嘴對耳講著敲敲話，那就不用這麼麻煩，不需要演算法也不用鑰匙更不用加什麼密，我們就是假定A跟B兩個人隔著距離，一定要透過第3者去傳話，但是又怕第3者知道他們的密秘，所以想將他們的訊息加密，明文加密成為密文安全了，但是鑰匙也是要透過第3者傳遞，那不又回到原點了嗎？

迪菲跟黑爾曼提出的方式如下
第1步，A將文件放在箱子裡面，然後箱子裡面放了一把A鑰匙，並且在箱子外面鎖上了A鎖，把箱子交出去
傳送，由於箱子上了A鎖，所以第3者只能乖乖傳給B，沒有辦法知道裡面的文件寫些什麼
第2步，B拿到箱子，B打不開，不過沒關係，B在箱子外鎖上B鎖，再回傳給A
傳送，箱子上有AB兩鎖，第3者一樣打不過，乖乖傳送
第3步，A拿到箱子，把A鎖打開，箱子外面還是有B鎖，傳給B
傳送，箱子上有B鎖，第3者打不開
第4步，B拿到箱子，把B鎖打開，他可以得到文件以及A鑰匙！
A跟B在第3者負責傳送下，安全的把文件傳送給對方！
如此一來，第3者及其他人得到密文想解密，只能靠著猜鑰匙而已。

以下實作一次對稱鑰匙
演算法採單向函數，因為單向函數較難回推，就像黃顏料+藍顏料會變綠顏料，但是卻很難從綠顏料推回黃跟藍顏料，而模算術是一個充滿單向函數的數學領域。

使用Y^x %P這個演算法
Y和P可以給別人知道沒有關係，就用Y=7 P=11
所以公式為7^x % 11
第1步，甲挑一個數字3(稱為A)，乙挑一個數字6(稱為B)，這個數字只有自己知道，不會讓對方、第3者知道
第2步，各自套入公式，7^3 % 11 = 343%11=2(稱a)，7^6%11 = 117649%11=4(稱b)
第3步，把這個算出來的數給對方，就算第3者知道也沒關係
第4步，甲使用b^A % 11 算出結果 4^3 %11=64%11=9
        乙使用a^B% 11 算出結果 2^6 %11=64%11=9
Key！兩個人都產生同樣一個數字9，這就是鑰匙！
而第3者，就算知道了a、b、7^x%11這些東西，依然不知道密碼為何，只能靠著一組一組慢慢猜。

以上，對稱鑰匙的講解，是告訴大家，這麼個傳鑰匙，除非是被猜中鑰匙，否則傳送的過程是安全的，但是這個樣子傳送，還是挺累人的，要來回個3次才能完成一次傳送，沒關係，1977年，Rivest、Shamir、Adleman三個人解決這個問題。

公開鑰匙(非對稱鑰匙)
何為公開、非對稱鑰匙？
先問，上面所有內容所提到的，何謂對稱鑰匙？
像甲跟乙皆使用9當做鑰匙，鑰匙是一樣的，不管加密解密都用一樣的鑰匙，這就叫做對稱鑰匙。
回到第一個問題就很好解釋了，加密解密鑰匙不一樣，就是非對稱鑰匙，而且加密鑰匙還公開給所有人知道，所以又叫做公開鑰匙。

在非對稱鑰匙中，加密的鑰匙可以發給任何人，每一個人要傳給你訊息，都可以取得你的加密鑰匙，然後使用這把鑰匙將訊息給加密起來，但是解密鑰匙只有你自己才有，任何人加密的文件都只有你能夠開啟，B要傳訊息給A，B用A加密鑰匙把訊息加密好，一但加完密，就連寫訊息的B都解不開，只有A能夠將訊息打開，要這麼做就必須找一個單向函數，而且只有在特殊條件下，才能逆向求出原值，這邊找到一個最重要的數-質數。

所謂質數，即是只能被自己跟1整除，3是質數，7是質數。

我們取兩個質數p及q算出他的乘積N，這個N便是加密的鑰匙，可以給任何人知道，p跟q就是我們的解密鑰匙，我們以p=18,313、q=22,307為例，p * q = 408,508,091=N，我們大可以告訴任何人408,508,091這個數字，任何人加密都用這個數字加密，但是我們並沒有公佈p跟q兩個數字，要解密時，其他人很難從N去回推p跟q兩個數字，要推回算到18,313這個數字，從1開始往上算，最精簡的算法也要算到2000個質數才能求出p。

當然，用電腦算，很快就能算出來了，但是當鑰匙(p及q)夠大的時候，電腦是攻不破的，事實上，現在的使用慣例是，公開鑰匙N值必須大到全球電腦聯合起來都需要比宇宙壽命長的時間才能破解。

常用的演算法：
公開鑰匙密碼系統(Public Key Cryptosystem)：RSA、Diffie-Hellman、ElGamal、橢圓曲線密碼、DSA及Fortezza
對稱鑰匙密碼系統(Symmetric Key Cryptosystem)：DES、Triple DES、AES、RC2、RC4、IDEA
單向散列函數：MD5及SHA。

電腦破解
前面講解許多演算法、鑰匙概念，一再再強調著「除非被猜中，不然不會被破解」的原因跟理論，但是究竟密碼會不會被猜中呢？人腦算不出來，那電腦呢？

MIPS(one-Million-instruction-per-second)一秒執行百萬次指令
1MIPS的電腦，一年約可以執行3*10^13次指令，也就是運算的次數
舉幾台電腦：
100MHz Pentium = 50MIPS
1GHz Pentium = 500MIPS
Intel core 2 extreme QX6700 3.33GHz = 61119MIPS
Core2這CPU是2006年底intel出版極殺的一顆CPU

「MIPS-年」指電腦執行3x10^13次指令所需要的年數時間

以1GHz(500MIPS)破5000MIPS-年的鑰匙，需要(5000*3*10^13)/500 = 10*3*10^13 = 10年

RSA 512位元=8400MIPS-年
RSA 768位元=5*10^7MIPS-年
簡單說，用Core2去破RSA512位元，只需要0.137年，但是Core2去破RSA768位元，需要818年
1024以上位元的就不再多提了，而電腦做cluster去拼解密的狀況也不去做計算

基本上理論上目前來說，就算電腦去爆破都還算是安全的，因為就算別人硬幹出你的鑰匙了，也許重要期限早已經過了。

結論
在沒有中木馬沒有側錄的情形下，基本上理論上網路加密算是安全的，但是誰敢100%保證呢？所有邏輯性的編碼都是有機會突破的，只是解出來，也許人都死了，或是事情也不重要了，秘密不機密了，就像，誰敢保證總統府一定安全？誰敢保證銀行一定安全？也是有人開汽油炸彈車去撞總統府，也是有人去搶銀行把錢偷走…

參考文獻
[1]碼書The Code Book，Simon Singh註，劉燕芬譯，2000年譯本，臺灣商務印書館
[2]密碼學-加密演算法，鄧安文編著，2004年，全華科技