EEPW首頁 > 嵌入式系統(tǒng) > 設(shè)計(jì)應(yīng)用 > 非對稱密鑰RSA加密算法及其密鑰產(chǎn)生
(2):n = p * q 然后隨機(jī)選擇加密密鑰e,要求 e 和 ( p - 1 ) * ( q - 1 ) 互質(zhì)。
檢查兩數(shù)是否互質(zhì)的方法:檢查兩數(shù)的公約數(shù)以gcd是否為l,若是,則兩數(shù)互素。根據(jù)歐幾里德算法,如果a為n+c,則a和b的gCd等于b和C的gcd,即gcd(a,b)=gcdb(,c),因此,gdc(a,b)可用每次運(yùn)算的余數(shù)去除該運(yùn)
算的除數(shù)來計(jì)算,這樣可以逐漸減少參加運(yùn)算的操作數(shù)的數(shù)值,最后的非零余數(shù)即為公約。
如對40,31是否互素進(jìn)行判斷,即計(jì)算gcd(40,31)。
第一次運(yùn)算:40=31*l+9,即40/31的余數(shù)為9;
第二次運(yùn)算:31=9*3+4,即31/9的余數(shù)為4;
第三次運(yùn)算:9一*42+1,即9/4的余數(shù)為1。
因此,gcd(40,31)=1,40與31互素。
上述算法即使對根大的整數(shù),也只需要不多的步驟即可得到結(jié)果。
(3):利用歐幾里德定理計(jì)算解密密鑰d, 滿足
e * d = 1 ( mod ( p - 1 ) * ( q - 1 ) ) ,即ed的相乘值與( p - 1 ) * ( q - 1 ) 互質(zhì)。
其中n和d也要互質(zhì)。數(shù)e和n是公鑰,d是私鑰。兩個素?cái)?shù)p和q不再需要,與私鑰不同的是不僅需要保密,而且應(yīng)該丟棄,不要讓任何人知道。
編碼過程是,若資料為a,化為二進(jìn)制數(shù)表示,首先把m分成等長數(shù)據(jù)塊 m1 ,m2,..., mi ,塊長s,其中 2^s = n, s 盡可能的大。對應(yīng)的密文是:
ci = mi^e ( mod n ) -------------( a )
解密時作如下計(jì)算:
mi = ci^d ( mod n ) -------------( b )
RSA 可用于數(shù)字簽名,方案是用 ( a ) 式簽名, ( b )式驗(yàn)證。具體操作時考慮到安全性和 m信息量較大等因素,一般是先作 HASH 運(yùn)算。
二、RSA 的安全性
RSA的安全性依賴于大數(shù)分解,但是否等同于大數(shù)分解一直未能得到理論上的證明,因?yàn)闆]有證明破解 RSA就一定需要作大數(shù)分解。假設(shè)存在一種無須分解大數(shù)的算法,那它肯定可以修改成為大數(shù)分解算法。目前, RSA 的一些變種算法已被證明等價于大數(shù)分解。不管怎樣,分解n是最顯然的攻擊方法?,F(xiàn)在,人們已能分解多個十進(jìn)制位的大素?cái)?shù)。因此,模數(shù)n 必須選大一些,因具體適用情況而定。
三、RSA的速度
由于進(jìn)行的都是大數(shù)計(jì)算,使得RSA最快的情況也比DES慢上100倍,無論是軟件還是硬件實(shí)現(xiàn)。速度一直是RSA的缺陷。一般來說只用于少量數(shù)據(jù)加密。
評論