RSA 原理簡介

  這基本上是嘴砲文章，主要介紹RSA 加密原理簡介。 有空希望能寫程式 Realize 他。

首先說說故事，密碼傳遞:
目標是Bob want to send some messages to Alice 透過一個public 的通道，簡單說就是廣播，所以所有public 的人都會知道這個訊息，要如何才能安穩地做到呢 ><
似乎是不可能的，
但在20 世紀末，有人想到一招式，簡單原理如下。
(1)bob 一開始先在他的訊息上裝上一道鎖，把這個鎖和物件寄出去，理論上沒有人有key 能打開，當然Alice 也不會有。
(2)但是很神奇的事情是，如果Alice 在這箱子上自己再設了一道鎖，然後傳給Bob.
(3)此時箱子上有兩道鎖，Bob 解開自己的鎖，此刻箱子上留有Alice 的鎖
(4) Alice 拿回箱子，解開自己的鎖。 大功告成，她可拿到東西啦。

幾個名詞:
Bob的鎖就叫做 公鑰public key
Alice的鎖就叫做 私鑰private key
目標就是Bob 要把訊息給Alice.

所以按照上述過程，這個作法是天衣無縫的，那要如何加密呢><(加密 就是 上鎖的意思)

以下簡介一些整數論:
首先

1. 質數Prime numbers: 就是那些只能寫成1*p=p*1 不能分解為兩個比p小的數字的乘積的數字:像是2,3,5,7,............歐幾里得說過: 質數有無限多><，要多大有多大，我覺得這是世界上第一件最重要的事情。
2. 任何一個大於1整數，都可以寫成唯一一組的質數乘積(up to 順序)。這也是幹話，91=7*13....
3. 目前，給定一個大整數，要分解是極困難的。這件事情目前是未定論，據說這件事應該是個NP problem (假定NP 不等於P)
4. 給一個a 是整數，跟N互質(兩者沒有共同因數)，必定存在一個數字k使得: a的k 次方 除上N 會剩下1。

上述證明需要用到一點group theory，且k有個最大值叫做，看以下記號(這句話需要修正，應該是，你計算 a 除上N, a^2 除上N,..........)最後會出現一個universal 的k(和a無關) 使得:a的k 次方 除上N 會剩下1。

為了解釋方便 ，讓

最後一個無聊素材，輾轉相除法，給兩個a, b 大於1整數，互質，存在x, y 是整數，使得ax-by=1。

開始了敘述如何產生密碼傳遞><



(1) Alice 選p, q兩個夠大質數，定義N=pq，可見N超大，而且難以分解，注意，此刻k=(p-1)(q-1)。
(2)Alice 選一個大正整數d 和 k 互質 (private key)，由輾轉相除法，存在一個e,X 整數，使得 de-kX=1
(3)Alice 把e 給bob, 當作bob的public key

現在準備完成: 假設Bob 要傳遞m 這個數字給Alice
第一步
(1) Bob 做 c=m^e ( mod N)  (意思就是m^e 除上N的餘數給Alice)
(2) Alice 把  c^d ( mod N) (意思就是c^d 除上N的餘數)

結論Alice 得到m:

證明如下 (簡單數學):

安全性:

這就是RSa加密，安全性在於N很難分解。首先要知道，e 跟N 都會在這過程中被竊取，不然Bob 就不知道他要做什麼數學操作。

假設有個黑暗力量，他想要破解這個密碼，那他需要知道啥? 他需要知道d，但是要得到d，
需要知道k，要知道k，需要分解N=pq, 因為k=(p-1)(q-1)。
如果黑暗力量知道了k，那他可以得到多組，X,d 滿足
de-kX=1。
裡面想必只有有限多個d，可以使得，這個m是有意義的。
所以就能夠破解這個傳遞。目前大家指望Shor's algorithm 某種量子演算法，能夠用來快速的分解N。

這個演算法細節非常複雜，
大家可以去看教科書...。
Shor's algorithm 維基連結
或看 Nielsen: 

Quantum Computation and Quantum Information