何謂 RSA 加密演算法?

RSA 是一種非對稱的加密演算法，非對稱是因為它利用了兩把不同的鑰匙，一把叫公開金鑰，另一把叫私密金鑰，這跟我們一般認知鑰匙不太一樣，大家家裡面的大門鎖門跟開門都用同一把鑰匙吧！這沒問題，就如 AES、DES 這種對稱的加密演算法也是都使用同一把鑰匙加密及解密，那 RSA 為什麼要用兩把鑰匙呢? 它一把用來鎖門，另一把是用來開門的，交換也是可以，只要鎖門跟開門用不同把就可以了，喔，這麼麻煩，為什麼呢?

主要為了確保網路上的資料安全，網路上會有三個很重要的需求：

1. 保密性:大家在網路上傳資料一定要保密，這是基本上需要的。
2. 真實需求性:也就是說當你收到一筆資料後，你怎麼能確定資料是正確的?中間沒有被別人篡改過?也就是要避免其他人”假傳聖旨”。
3. 不可否認性:這個特性就是指類似虛擬印章的意思，這份文件只要經過你簽名蓋章之後，你就不可以否認耍賴，當然這要有一個很好的機制才能讓人心服口服。

RSA 很厲害的就是說它都符合以上這三個要求，為什麼會符合我們先不管，我先來說明 RSA 的演算法，這個演算法簡單講就是使用了一個很神奇的數學特性來完成，而且很神奇地剛好都符合以上三個需求，你一定要了解這個數學特性是什麼，才能進一步知道為什麼這樣就會達到加密需求、真實需求、不可否性需求。

這個數學特性就是說
1.有兩個質數很大的質數 p 跟 q，計算得到 n=pq。
2.接著 z=(p-1)(q-1)。
3.接著我們要試著找一個數字 e，e 要比 n 小，而且 e 要跟 z 互為質數。
4.再來要找出另一個數字 d，它要滿足 ed-1 恰好可以被 z 整除，意指沒有餘數，另一個說法就是說 ed mod z =1(mod是取餘數的意思)，換句話說，已知 e，我們選擇 d，使用得當 ed 除以 z 時得到餘數 1。

已經亂掉了對不對? 好複雜呀，e 跟 d 的數字的確不好找，這裡舉2個符合的例子，你自己套用驗證看看:
p=3, q=5, n=pq=15, z=(p-1)(q-1)=8, e=3, d=3
p=5, q=7, n=pq=35, z=(p-1)(q-1)=24, e=5, d=29

不過如果你已經找到這些資料，底下就會有一個很神奇的數學特性了，假設 m 是原文(plaintext)，我們使用了e,n 這一組數字來加密，得到經過加密過的密文(ciphertext) c
m^e mod n = c

收到密文 c 之後我們再使用 d,n 這一組數字做解密，咦，很神奇地，它會回到到原來原文了

c^d mod n = m

所以任何資料可以使用 e,n 這組數字加密，使用 d,n 這組數字解密，角色對調也可以，使用 d,n 這組數字加密，使用 e,n 這組數字解密也是OK，所以 (e,n) 與 (d,n) 就很像兩把鑰匙，一把開，另一把就是關，我們通常定義其中一把鑰匙為公閞金鑰，另一把就是私密金鑰，公開金鑰是公開的，任何人都可以拿得到你的公開金鑰，但是私密金鑰是自己要保存好的，今天某人要傳送一串資料給你，例如”I love you”，但他不想讓其他人看到，這時候他可以拿你的公開金鑰加密過再傳送給你，當你接收到之後再使用你的私密金鑰打開來看，就算在傳送過程中如果被駭客擷取到了，駭客沒有你的私密金鑰也打不開資料，所以使用你的公開金鑰加密過的資料，全世界唯一只有你自己能解密，這樣就巧妙地達到安全加密的效果了。

好，但是你有沒有想過，公開金鑰是每個人都可以拿到的，那有沒有辦法由公開金鑰來計算出你的私密金鑰是什麼? 也就是說有沒有可能從已知 e,n 這組數字，算出 d,n 這組數字呢? 答案是可以的!從 n 的質因數分解開始找。

哇，那不是白幹了Orz….，並不會，因為質因數分解對電腦的計算上來講很複雜，也就是要花很久的時間來做，就算是超級電腦來跑也要跑個一兩年，況且 p,q 是一個夠大的質數，這個加密結果並不是算不出來，而要花很長的時間，等到跑出結果來時已經過了時效性了

基本上上面已經提到了第一個需求，保密的需求，那第二個需求是真實的需求，如何來確定原文是由某個人發給你的，而不是假傳聖旨呢? 當某人要傳”I love you”給你時，他要先將”I love you”先用自己的私密金鑰加密，外面那層再用你的公開金鑰加密，也就是加密了兩次，就像包裹一樣包了兩層，當你收到包裹後最外面那層是他用你的公開金鑰加密的嘛，所以你就用自己的私密金鑰解密打開來，接下來你就要拿對方的公開金鑰打開裡面這層，因為他第一層是使用他的私密金鑰加密的嘛，如果打得開的話就表示，保證確認是對方加密的，這樣就能確認跟你說”I love you”的這個人的身份是確定的。

接下來第三個需求是不可否認性的需求，也就是我們要講的數位簽章，由數位簽章可以來辦認這份文件確實是由你簽署的，你不能耍賴，例如有一份公文，當然這份文件是公開的不需要保密，你把這份公文用自己的私密金鑰加密過，公佈出來，其他人想看這份公文就拿你的公開金鑰去打開它，如果打得開那就表示這文件保證是由你加密，同時代表了你有簽名蓋章的意思，但是通常不把全部的內文都加密，這樣會太浪費資源，因為內文有可能幾百頁資料，全部都加密會耗掉太多資源，所以一般原文加密前會先做個雜湊運算 (hashing)，不管多長多短的內文都會 hashing 成一個固定長度的文件，我們稱為摘要，你只要加密摘要就好了，節省時間，傳的時候把原文的內文以及加密過後的摘要一起送給對方，對方收到兩樣東西1.原文的內文 2.加密過後的搞要，對方這時候就要來驗證確認身份跟內容，首先它把原文的內文也做一次 hashing，就如同之前你在傳送前做的那件事一樣，它會得到摘要，好，這個摘要先擺著，第二步再拿收到的第二樣東西-加密過的摘要，用對方的公開金鑰去解開它，解得開表示確認了身份，解開的摘要再跟剛剛我們之前自己做 hashing 的摘要一比對，比對如果都一樣，那我們也可以確定原文的內文傳送過程中沒有被篡改，這樣就能達成不可否認性的特性了。