作品集錦

RSA 是一種採用公鑰方式同時提供亂碼及數位簽章的安全機制，是由
Ron Rivest, Adi Shamir 和 Leonard Adleman 於1977年發展出來，RSA 即是
這三個發明人名字的縮寫

先取兩個大質數 p 和 q，求其乘積為 n，n 稱為其模數
再任選一個小於 n 且和 (p-1)(q-1) 互質的數字 e
再找一個數字 d， d 必須使 (ed-1) 與 (p-1)(q-1) 互質
e 稱為公開數 (public exponents) ，d 稱為私有數 (private exponents)
而 (n, e) 稱為公鑰， ( n, d) 稱為私鑰，產生公鑰及私鑰後，
p, q 兩數可以與私鑰一起保存或是銷毀 目前要想從公鑰 (n, e) 求得私鑰的 d 值是困難的， 然而只要能將 n 分解出 p 和 q 就可以得到私鑰中的 d ， 因此 RSA 的安全性是建立在"質數分解是困難的"的前提之上， 簡易質數分解法的發現將破解 RSA 的安全性(詳見FAQ 3-1-3及2-3-3)， 接著是 RSA 如何應用在亂碼及數位簽章作業上(實際應用時會有些許差異，請參考 FAQ 3-1-7 及 3-1-8 )：

假設 m 是 Alice 要給 Bob 的資料，Alice 用下列公式進行亂碼作業， c = m^e mod n，
其中 c 是亂碼後的資料， e 和 n 是 Bob 的公鑰，等資料到了 Bob 手中，
Bob 的解碼公式為：m = c^d mod n， 藉著 e 和 d 的關係可以讓 Bob 正確地求得原始訊息 m　
也因為 d 只有 Bob 知道，所以只有 Bob 可以解出正確的原始訊息

假設 m 是 Alice 要給 Bob 的資料，Bob 希望能確定 m 在傳送過程中沒被修改
而且必須有方法可以證明是 Alice 本人發的訊息，Alice 就用下列公式產生數位簽章 s ，
s = m^d mod n，其中 d 和 n 是 Alice 的私鑰， Alice 必須將 m 和 s 一起送出給 Bob，
Bob 收到後驗證數位簽章公式如下： m = s^e mod n，其中 e 和 n 是 Alice 的公鑰 不論要亂碼或身分認證都不需要將私鑰給別人，每個人唯一要用到的是別人的 公鑰或是自己的私鑰，每個人可以發送出亂碼過的訊息或是驗證被簽章過的訊 息，但只有擁有正確私鑰的人可以對訊息解碼或進行數位簽章