公開密鑰密碼系統

公開密鑰密碼系統是由R.Rivest、A.Shamir和L.Adleman於1977年提出的。RSA的 取名就是取自這三位發明者姓氏的第一個字母。

基本介紹

• 中文名：公開密鑰密碼系統
• 外文名：RSA
• 類別：計算機
• 時間：1977年

系統文字

後來，在1982年他們又創辦了以RSA命名的公司（RSA Data Security Inc.和RSA實驗室），該公司和實驗室在公開密鑰密碼系統的研發和商業套用推廣方面具有劃時代的意義，是全球公認的計算機網路安全的重要里程碑。與"公開密鑰密碼體制"相對應的是"傳統密碼體制",又稱"對稱密鑰密碼體制",其中用 於加密的密鑰與用於解密的密鑰完全一樣。

在對稱密鑰密碼體制中，加密運算與解密運算使用同樣的密鑰。通常，使用的加密算法 比較簡便高效，密鑰簡短，破譯極其困難。但是，在公開的計算機網路上安全地傳送和保管 密鑰是一個嚴峻的問題。1976年，Diffie和Hellman為解決密鑰管理問題，在他們的奠基性 的工作"密碼學的新方向"一文中，提出一種密鑰交換協定，允許在不安全的媒體上通訊雙方 交換信息，安全地達成一致的密鑰。在此新思想的基礎上，很快出現了"不對稱密鑰密碼體 制",即"公開密鑰密碼體制",其中加密密鑰不同於解密密鑰，加密密鑰公之於眾。

實例

工作原理

現在，用一個簡單的例子來說明RSA公開密鑰密碼系統的工作原理。

取兩個質數p=11,q=13,p和q的乘積為n=p×q=143，算出另一個數z=(p-1）×(q-1)=120；再選取一個與z=120互 質的數，例如e=7（稱為"公開指數")，對於這個e值，可以算出另一個值d=103（稱為"秘密指數 ")滿足e×d=1 mod z；其實7×103=721除以120確實餘1。（n,e）和（n,d）這兩組數分別為"公 開密鑰"和"秘密密鑰。"

構想張小姐需要傳送機密信息（明文，即未加密的報文）s=85給李先生，她已經從公開媒體或網站上得到了李先生的公開密鑰（n,e)=(143,7），於是她算出加密值

c=s【RUe】 mod n=85【RU7】 mod 143=123並傳送給李先生。

李先生在收到"密文"(即經加密的報文）其中c=123，他就可利用只有他自己知道的秘密密鑰（n,d)=(143,123）計算123123 mod 143,

得到的值就是明文（值）85，實現了解密。其中的計算用一般公式來表達，是

c【RUd】 mod n=(s【RUe】）【RUd】 mod n=s【RUed】 mod n

根據初等數論中的歐拉（Euler）定理，套用s【RUz】=1 mod n，所以

s【RUed】=s mod n

所以，李先生可以得到張小姐發給他的真正的信息s=85。

自然，我們要問，在李先生向公眾提供了公開密鑰，密文c又是通過公開的途徑傳送的，其安全性何在?

回答是肯定的！只有當n足夠大時，例如，有512比特，或1024比特甚至2048比特，n=p×q中的p和q的 位數差不多大小，任何人只知道公開密鑰（n,e），目前是無法算出秘密密鑰（n,d）的。其困難在於從乘積n難以找出它的兩個巨大的質數因子。

上面例子中的n=143，只是示意用的，用來說明RSA公開密鑰密碼系統的計算過程，從 143找出它的質數因子11和13是毫不困難的。對於巨大的質數p和q，計算乘積n=p×q非常簡便，而其逆運算卻是相當困難的事情。這是一種"單向性"。相應的函式稱為"單向函式"。任何單向函式都可以作為某一種公開密鑰密碼系統的基礎，而單向函式的安全性也就是這種公開密鑰密 碼系統的安全性。

公開密鑰密碼系統的一大優點是不僅可以用於信息的保密通訊，又可以用於信息傳送者的身份驗證（Authentication），或數字簽名（Digital Signature），我們仍用下例來示意說明。

李先生要向張小姐傳送信息m（表示他的身份，可以是他的身份證號碼，或其名字的漢字 的某一種編碼值），他必須讓張小姐確信該信息是真實的，是由李先生本人所發的。為此，他使用自己的秘密密鑰（n,d）計算

s=md mod n建立了一個"數字簽名",通過公開的通訊途徑發給張小姐。張小姐則使李先生的公開密鑰（n,e）對收到的s值進行計算

s【RUe】 mod n=(md)e mod n=m

這樣，她經過驗證，知道信息s確實代表了李先生的身份，只有他本人才能發出這一信息，因為只有他自己知道秘密密鑰（n,d），其他任何人即使知道李先生的公開密鑰（n,e），也無 法猜出或算出他的秘密密鑰來冒充他的"簽名"。

有兩類基本的加密算法可供對檔案加密者選擇：保密密鑰和公開/私有密鑰。在保密密鑰中，加密者和解密者使用相同的密鑰，被稱為對不對稱密鑰，這類算法有DES和IDEA。這種加密算法的問題是，用戶必須讓接收信息者知道自己所使用的密鑰，這個密鑰需要雙方共同保密，任何一方的失誤都會導致機密的泄露。而且在告訴收件人密鑰過程中，還需要的防止任何人發現或竊取密鑰，這個過程被稱為密鑰發布。有些認證系統在會話初期用明文傳送密鑰，這就存在密鑰被截獲的可能性。需要使用保密密鑰對加密密鑰的信息再加密。

另一類加密技術是公開/私有密鑰，與非對稱密鑰體制不同的是，它使用相互關聯的一對密鑰，一個是公開的密鑰，任何人都可以知道，另一個是私有密鑰（專一密鑰），只有擁有該對密鑰的人才有，其他人並沒有保管它。假如某甲發信給保存專一密鑰的乙方，乙接收到加密信息後，就用他自己保存的密鑰進行解密，而且只有乙方持有的私有密鑰可以解密。這種加密方式的好處顯而易見。密鑰只有一個人持有，也就更加容易進行保密，因為不需在網路上傳送私人密鑰，也就不用擔心別人在認證會話初期劫持密鑰。下面把公開/私有密

鑰技術總結為以下幾點

1、公開鑰/私有密鑰有兩個相互關聯的密鑰。

2、公開密鑰加密的檔案只有私有密鑰能解開。

3、私有密鑰加密的檔案只有公開密鑰能解開.這一特點被用於PGP（pretty good privacy）。