RSA加密演算法

你認為分解兩個不同巨大質數的乘積很容易嗎?

西元1997，三位美國麻省理工學院的學者李瓦士（Rivest）、夏米爾（Shamir）、以及艾道曼（Adleman）率先公開RSA加密演算法並取得專利權，此演算法是最先進及最方便的加密方法，它在電子商務交易中扮演了相當重要的角色，目前有很多的數位消費性產品，例如視訊轉換器與智慧卡，都是利用了RSA加密來傳遞訊息，RSA就是取用三位學者名字的開頭字母來命名的。

RSA加密演算法是一種特殊的非對稱密碼法，利用兩個質數作為加密與解密的兩個鑰匙(key)。這兩個鑰匙分別稱為公開鑰匙 (public key) 和私人鑰匙 (private key 或是 secret key)，鑰匙的長度約在 40 個位元到 1024 位元。公開鑰匙作為加密，只有使用私人鑰匙才能解密，解密者只要不洩露私人鑰匙，別人就算有公開鑰匙，也是很難推演算出來私人鑰匙，就算是利用反向工程來解密也不是一件簡單的事，所以 RSA 算是一種十分安全的加密與解密演算法。

如果你想和別人祕密通訊，那麼你可以先選定兩個非常巨大的質數P1、P2作為私人鑰匙（(private key，解密用的），然後將 P1× P2 的乘積作為加密用的公開鑰匙 (public key)，你可以把公開鑰匙 (public key)公佈在名片上或在網路上。那麼，別人要傳一封密函給你，他必需要先得到你的公開鑰匙 (public key)，按照一個約定的方法將信件加密後送出。你在收到密函後，再用你的私人鑰匙(private key)就可以解出密函原文。

或許你會懷疑它真的安全嗎?當然計算兩個質數乘積在快速運算電腦的協助下，就算質數很巨大，也不會是很困難的事。但是要將一個巨大的數分解成兩個質數的乘積，儘管用最快速的超級電腦運算，也需要很長久的時間。所以 RSA 密碼法在目前雖然稱不上絕對安全，但算是夠安全了。

為了檢測 RSA 技術的安全性，一家專門研究RSA 技術的公司 RSA Security 提出了 8 個巨大合數讓數學家作質因數分解。這些合數都是由兩個巨大的質數相乘積，要分解它們並不一件簡易的事。RSA-576 是 8 個合成數中最小的一個，其餘 7 個合成數的位數分別有 193 ～617 個。RSA-576 是指這個合成數寫成二進位時有 576 個位。其他七個巨大的合成數分別是RSA-640、RSA-704、RSA-768、RSA-896、RSA-1024、RSA-1536、RSA-2048。

RSA-576=1881 9881292060 7963838697 2394616504 3980716356 3379417382 7007633564 2298885971 5234665485 3190606065 0474304531 7388011303 3967161996 9232120573 4031879550 6569962213 0516875930 7650257059，它總共有174位數。在2003年12月3日，一個德國機構成功的將它分解成3980750 8642406493 7397125500 5503864911 9906436234 2526708406 3851895759 4638895726 1768583317 和 4727721 4610743530 2536223071 9730482246 3291469530 2097116459 8521711305 2071125636 3590397527，並獲得RSA Security 所提供的獎金１００００美金。如果成功分解RSA-2048，就能得到RSA Security 所提供的獎金２０００００美金，所以多研習密碼學，或許這些獎金會落入你的口袋。

參考資料：ｈttp://www.rsasecurity.com/rsalabs/challenges/factoring/numbers.html