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 所提供的獎金10000美金。如果成功分解RSA-2048,就能得到RSA Security 所提供的獎金200000美金,所以多研習密碼學,或許這些獎金會落入你的口袋。

參考資料:http://www.rsasecurity.com/rsalabs/challenges/factoring/numbers.html


Copyright ©昌爸工作坊 all rights reserved.