rsa公鑰密碼系統(tǒng)new

《rsa公鑰密碼系統(tǒng)new》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、RSA公鑰密碼系統(tǒng)徐厚駿[摘要]RSA加密算法是由Rivest、Shamir和Adleman提出的基于素?cái)?shù)理論的密碼系統(tǒng)，是第一個(gè)較為成功的公鑰密碼系統(tǒng)，也是目前應(yīng)用比較廣泛的公鑰密碼系統(tǒng)，本文較詳細(xì)地給出了RSA公鑰密碼系統(tǒng)的證明，同時(shí)給出了操作方法和安全性說(shuō)明。[關(guān)鍵詞]數(shù)據(jù)通訊信息加密公鑰密碼系統(tǒng)RSA加密算法⒈前言我國(guó)的因特網(wǎng)(Internet)現(xiàn)已經(jīng)發(fā)展到商業(yè)網(wǎng)，E-Mail已廣為應(yīng)用，另外還有三金工程，各部門、各行業(yè)、各省市的行業(yè)網(wǎng)、地區(qū)網(wǎng)的建成，數(shù)據(jù)傳輸比當(dāng)年CHINAPAC網(wǎng)的應(yīng)用更為普遍。金融、商業(yè)、政府等的通信對(duì)保密的要求愈來(lái)愈高，從而激起了對(duì)數(shù)據(jù)通訊中的

2、信息加密研究的熱情。從商業(yè)角度來(lái)說(shuō)，DES是一個(gè)很好的加密算法，而為了提高安全性和避開傳遞密鑰的麻煩，人們廣泛地使用臨時(shí)隨機(jī)密鑰，這需要用RSA算法對(duì)其密鑰加密。RSA公鑰密碼系統(tǒng)由于加密密鑰公開，為信息加密帶來(lái)了極大的方便，更由于RSA加密算法可以方便地實(shí)現(xiàn)數(shù)字簽名，在網(wǎng)絡(luò)通信高度發(fā)達(dá)的今天，意義更加顯得突出。自1994年四季度起，我國(guó)CHINAPAC網(wǎng)加大了宣傳力度并實(shí)行了一系列優(yōu)惠措施。1995年．使用E-Mail的用戶迅速增加．?dāng)?shù)據(jù)通訊中的信息加密開始在我國(guó)民間受到重視。由于DES數(shù)據(jù)加密標(biāo)準(zhǔn)算法較早傳人我國(guó)，相對(duì)來(lái)說(shuō)掌握此項(xiàng)技術(shù)的人也較多．所以相當(dāng)多的用戶使用了DE

3、S算法。但是DES算法的密鑰只有2^56≈7.21e16。顯然有些不足，所以DES算法的可靠性一直受到廣泛關(guān)注。1995年，129位十進(jìn)制數(shù)RSA129在1993年被成功破譯的信息傳來(lái)后，人們根據(jù)運(yùn)算工作量估算，對(duì)當(dāng)前速度最快的計(jì)算機(jī)，窮舉搜索這7.21e16個(gè)密鑰大概只需要幾天或十幾天的時(shí)間。又考慮到美國(guó)已經(jīng)提出了第三方保管密鑰的加密標(biāo)準(zhǔn)(TheEscrowEncryptionStandard簡(jiǎn)稱為‘EES’)采用80bit密鑰稱作SKIPJACK的加密算法，歐洲提出了128bit密鑰處理64bit數(shù)據(jù)塊的加密算法稱作國(guó)際數(shù)據(jù)加密算法(TheInternotionalDat

4、aEncryptionAlgorithm簡(jiǎn)稱為‘IDEA’)。另外，使用三個(gè)不同密鑰的三重DES加密算法也在使用，因此出現(xiàn)了完善現(xiàn)有加密算法以適應(yīng)Internet和E-Mail的要求。經(jīng)過(guò)充分比較，認(rèn)識(shí)到把公鑰密碼技術(shù)和密鑰密碼技術(shù)相結(jié)合，可以獲得安全性和高性能的結(jié)合。為此選擇了使用臨時(shí)隨機(jī)密鑰的DES算法加密信息，再使用RSA算法對(duì)DES密鑰進(jìn)行數(shù)字簽名和加密，為了避免冒充，數(shù)字簽名是必須的。因此，解決RSA算法的關(guān)鍵問(wèn)題成為這一工作成功的保證。筆者在實(shí)施過(guò)程中對(duì)其有了一個(gè)較全面的了解，現(xiàn)介紹如下。⒉必要的數(shù)論知識(shí)2．1因子分解素?cái)?shù)：只能被1和該數(shù)自身除盡的整數(shù)。合數(shù)：不是

5、l且非素?cái)?shù)的整數(shù)。最大公因子：若a能除盡b且a也能除盡c，即a是b和c的公因子，若b和c的每個(gè)公因子都能除盡a，則a是b和c的最大公因子，表示為：a=gcd{b，c}定義：若gcd{a，b}=士1。則稱a和b互素。定理l：每一個(gè)正合數(shù)都可表示為正素?cái)?shù)的乘積，且當(dāng)不考慮乘積的順序時(shí)，表示方法是唯一的。素?cái)?shù)的個(gè)數(shù)是無(wú)限的，不大于正整數(shù)N的素?cái)?shù)個(gè)數(shù)P，有比較精確的近似式如下：1PLi(N)=?Li(N)2其中xdtLi(x)=∫ln(t)2展開式為：23(ln(x))(ln(x))Li(x)=ln(ln(x))+ln(x)+++…2×2!3×3!2．2同余模運(yùn)算：b=mod(a，m

6、)，表示a除以m的余數(shù)為b。定義：若mod(a，m)=mod(b，m)，則可寫作a＝km十b，k為一整數(shù)，我們稱a和b模m同余，記作：a≡b(modulom〕其中m稱為這個(gè)同余式的模。定理2：模m的同余關(guān)系滿足(1)自反性：即a≡a(modulom)；(2)對(duì)稱性：即若a≡b(modulom)，則b≡a(modulom)；(3)傳遞性：即若a≡b(modulom)，且b≡c(modulom)，則a≡c(modulom)。定理3：若a≡b(modulom)且c≡d(modulom)，則(1)a±c≡b±d(modulom)；(2)a×c≡b×d(modulom)。定理4：若a×

7、c≡b×c(modulom)且d=gcd{c，m}，則a≡b(modulom/d)。2．3同余類Euler函數(shù)：在0、l、2、……m-1這m個(gè)數(shù)中，和m互素的數(shù)的個(gè)數(shù)稱為數(shù)m的Euler函數(shù)，表示為Φ(m)。每個(gè)整數(shù)，總是與0、1、2……m-1這m個(gè)數(shù)中的一個(gè)數(shù)r模m同余，且僅和這一個(gè)數(shù)模m同余，所有模m和r(0<=r<=m-1)同余的整數(shù)，組成一個(gè)“同余類”，用[r]表示。如果r與模數(shù)m互素，則同余類[r]中的每個(gè)數(shù)都與m互素，稱作同余類[r]與模數(shù)m互素。所以模數(shù)m的Euler函數(shù)Φ(m)即代表了和