姓名：于川皓 學(xué)號：16140210089

轉(zhuǎn)載自：https://baike.baidu.com/item/RSA%E7%AE%97%E6%B3%95/263310?fromtitle=RSA%E5%8A%A0%E5%AF%86%E7%AE%97%E6%B3%95&fromid=9645994&fr=aladdin

【嵌牛導(dǎo)讀】：RSA公開密鑰密碼體制瑟捣。所謂的公開密鑰密碼體制就是使用不同的加密密鑰與解密密鑰牛哺，是一種“由已知加密密鑰推導(dǎo)出解密密鑰在計(jì)算上是不可行的”密碼體制奠支。

【嵌牛鼻子】：密碼學(xué)

【嵌牛提問】RSA算法的發(fā)展過程是什么樣子的？

【嵌牛正文】：RSA公開密鑰密碼體制石窑。所謂的公開密鑰密碼體制就是使用不同的加密密鑰與解密密鑰，是一種“由已知加密密鑰推導(dǎo)出解密密鑰在計(jì)算上是不可行的”密碼體制战授。

在公開密鑰密碼體制中囤攀，加密密鑰（即公開密鑰）PK是公開信息丈氓，而解密密鑰（即秘密密鑰）SK是需要保密的周循。加密算法E和解密算法D也都是公開的。雖然解密密鑰SK是由公開密鑰PK決定的万俗，但卻不能根據(jù)PK計(jì)算出SK湾笛。

正是基于這種理論，1978年出現(xiàn)了著名的RSA算法闰歪，它通常是先生成一對RSA 密鑰嚎研，其中之一是保密密鑰，由用戶保存课竣；另一個(gè)為公開密鑰嘉赎，可對外公開置媳，甚至可在網(wǎng)絡(luò)服務(wù)器中注冊于樟。為提高保密強(qiáng)度公条，RSA密鑰至少為500位長，一般推薦使用1024位迂曲。這就使加密的計(jì)算量很大靶橱。為減少計(jì)算量，在傳送信息時(shí)路捧，常采用傳統(tǒng)加密方法與公開密鑰加密方法相結(jié)合的方式关霸，即信息采用改進(jìn)的DES或IDEA對話密鑰加密，然后使用RSA密鑰加密對話密鑰和信息摘要杰扫。對方收到信息后队寇，用不同的密鑰解密并可核對信息摘要。

RSA算法是第一個(gè)能同時(shí)用于加密和數(shù)字簽名的算法章姓，也易于理解和操作佳遣。RSA是被研究得最廣泛的公鑰算法，從提出到現(xiàn)今的三十多年里凡伊，經(jīng)歷了各種攻擊的考驗(yàn)零渐，逐漸為人們接受，普遍認(rèn)為是目前最優(yōu)秀的公鑰方案之一系忙。

SET(Secure Electronic Transaction)協(xié)議中要求CA采用2048bits長的密鑰诵盼，其他實(shí)體使用1024比特的密鑰。RSA密鑰長度隨著保密級別提高银还，增加很快风宁。下表列出了對同一安全級別所對應(yīng)的密鑰長度。

保密級別

對稱密鑰長度（bit）

RSA密鑰長度（bit）

ECC密鑰長度（bit）

保密年限

80

80

1024

160

2010

112

112

2048

224

2030

128

128

3072

256

2040

192

192

7680

384

2080

256

256

15360

512

2120

這種算法1978年就出現(xiàn)了蛹疯，它是第一個(gè)既能用于數(shù)據(jù)加密也能用于數(shù)字簽名的算法杀糯。它易于理解和操作，也很流行苍苞。算法的名字以發(fā)明者的名字命名：Ron Rivest, Adi Shamir 和 Leonard Adleman固翰。早在1973年，英國國家通信總局的數(shù)學(xué)家Clifford Cocks就發(fā)現(xiàn)了類似的算法羹呵。但是他的發(fā)現(xiàn)被列為絕密骂际，直到1998年才公諸于世。

RSA算法是一種非對稱密碼算法冈欢，所謂非對稱歉铝，就是指該算法需要一對密鑰，使用其中一個(gè)加密凑耻，則需要用另一個(gè)才能解密太示。

RSA的算法涉及三個(gè)參數(shù)柠贤，n、e1类缤、e2臼勉。

其中，n是兩個(gè)大質(zhì)數(shù)p餐弱、q的積宴霸，n的二進(jìn)制表示時(shí)所占用的位數(shù)，就是所謂的密鑰長度膏蚓。

e1和e2是一對相關(guān)的值瓢谢，e1可以任意取，但要求e1與(p-1)*(q-1)互質(zhì)驮瞧；再選擇e2氓扛，要求(e2×e1)≡1(mod(p-1)×(q-1))。

（n论笔，e1),(n采郎，e2)就是密鑰對。其中(n翅楼，e1)為公鑰尉剩，(n，e2)為私鑰毅臊。

RSA加解密的算法完全相同理茎，設(shè)A為明文，B為密文管嬉，則：A≡B^e2( mod n)皂林；B≡A^e1 (mod n)；（公鑰加密體制中蚯撩，一般用公鑰加密础倍，私鑰解密）

e1和e2可以互換使用，即：

A≡B^e1 (mod n)胎挎；B≡A^e2( mod n);

安全性

編輯

RSA的安全性依賴于大數(shù)分解沟启，但是否等同于大數(shù)分解一直未能得到理論上的證明，因?yàn)闆]有證明破解RSA就一定需要作大數(shù)分解犹菇。假設(shè)存在一種無須分解大數(shù)的算法德迹，那它肯定可以修改成為大數(shù)分解算法。 RSA 的一些變種算法已被證明等價(jià)于大數(shù)分解揭芍。不管怎樣胳搞，分解n是最顯然的攻擊方法。人們已能分解多個(gè)十進(jìn)制位的大素?cái)?shù)。因此肌毅，模數(shù)n必須選大一些筷转，因具體適用情況而定。

實(shí)現(xiàn)細(xì)節(jié)

編輯

密鑰生成

首先要使用概率算法來驗(yàn)證隨機(jī)產(chǎn)生的大的整數(shù)是否質(zhì)數(shù)悬而，這樣的算法比較快而且可以消除掉大多數(shù)非質(zhì)數(shù)呜舒。假如有一個(gè)數(shù)通過了這個(gè)測試的話，那么要使用一個(gè)精確的測試來保證它的確是一個(gè)質(zhì)數(shù)摊滔。

除此之外這樣找到的p和q還要滿足一定的要求阴绢，首先它們不能太靠近店乐，此外p-1或q-1的因子不能太小艰躺，否則的話N也可以被很快地分解。

此外尋找質(zhì)數(shù)的算法不能給攻擊者任何信息眨八，這些質(zhì)數(shù)是怎樣找到的腺兴，尤其產(chǎn)生隨機(jī)數(shù)的軟件必須非常好。要求是隨機(jī)和不可預(yù)測廉侧。這兩個(gè)要求并不相同页响。一個(gè)隨機(jī)過程可能可以產(chǎn)生一個(gè)不相關(guān)的數(shù)的系列，但假如有人能夠預(yù)測出（或部分地預(yù)測出）這個(gè)系列的話段誊，那么它就已經(jīng)不可靠了闰蚕。比如有一些非常好的隨機(jī)數(shù)算法，但它們都已經(jīng)被發(fā)表连舍，因此它們不能被使用没陡，因?yàn)榧偃缫粋€(gè)攻擊者可以猜出p和q一半的位的話，那么他們就已經(jīng)可以輕而易舉地推算出另一半索赏。

此外密鑰d必須足夠大盼玄，1990年有人證明假如p大于q而小于2q（這是一個(gè)很經(jīng)常的情況）而，那么從N和e可以很有效地推算出d潜腻。此外e = 2永遠(yuǎn)不應(yīng)該被使用埃儿。[1]

運(yùn)算速度

由于進(jìn)行的都是大數(shù)計(jì)算，使得RSA最快的情況也比DES慢上好幾倍融涣，無論是軟件還是硬件實(shí)現(xiàn)童番。速度一直是RSA的缺陷。一般來說只用于少量數(shù)據(jù)加密威鹿。RSA的速度比對應(yīng)同樣安全級別的對稱密碼算法要慢1000倍左右剃斧。

比起DES和其它對稱算法來說，RSA要慢得多专普。實(shí)際上Bob一般使用一種對稱算法來加密他的信息悯衬，然后用RSA來加密他的比較短的對稱密碼，然后將用RSA加密的對稱密碼和用對稱算法加密的消息送給Alice。

這樣一來對隨機(jī)數(shù)的要求就更高了筋粗，尤其對產(chǎn)生對稱密碼的要求非常高策橘，因?yàn)榉駝t的話可以越過RSA來直接攻擊對稱密碼。

密鑰分配

和其它加密過程一樣娜亿，對RSA來說分配公鑰的過程是非常重要的丽已。分配公鑰的過程必須能夠抵擋一個(gè)從中取代的攻擊。假設(shè)Eve交給Bob一個(gè)公鑰买决，并使Bob相信這是Alice的公鑰沛婴，并且她可以截下Alice和Bob之間的信息傳遞，那么她可以將她自己的公鑰傳給Bob督赤，Bob以為這是Alice的公鑰嘁灯。Eve可以將所有Bob傳遞給Alice的消息截下來，將這個(gè)消息用她自己的密鑰解密躲舌，讀這個(gè)消息丑婿，然后將這個(gè)消息再用Alice的公鑰加密后傳給Alice。理論上Alice和Bob都不會(huì)發(fā)現(xiàn)Eve在偷聽他們的消息没卸。今天人們一般用數(shù)字認(rèn)證來防止這樣的攻擊羹奉。

時(shí)間攻擊

1995年有人提出了一種非常意想不到的攻擊方式：假如Eve對Alice的硬件有充分的了解，而且知道它對一些特定的消息加密時(shí)所需要的時(shí)間的話约计，那么她可以很快地推導(dǎo)出d诀拭。這種攻擊方式之所以會(huì)成立，主要是因?yàn)樵谶M(jìn)行加密時(shí)所進(jìn)行的模指數(shù)運(yùn)算是一個(gè)位元一個(gè)位元進(jìn)行的而位元為1所花的運(yùn)算比位元為0的運(yùn)算要多很多煤蚌，因此若能得到多組訊息與其加密時(shí)間蒿涎，就會(huì)有機(jī)會(huì)可以反推出私鑰的內(nèi)容悠反。[1]

模數(shù)攻擊

編輯

若系統(tǒng)中共有一個(gè)模數(shù)莉御，只是不同的人擁有不同的e和d且轨，系統(tǒng)將是危險(xiǎn)的。最普遍的情況是同一信息用不同的公鑰加密魄健，這些公鑰共模而且互質(zhì)赋铝，那么該信息無需私鑰就可得到恢復(fù)。設(shè)P為信息明文沽瘦，兩個(gè)加密密鑰為e1和e2革骨，公共模數(shù)是n，則：

C1 = P^e1mod n

C2 = P^e2 mod n

密碼分析者知道n析恋、e1良哲、e2、C1和C2助隧，就能得到P筑凫。

因?yàn)閑1和e2互質(zhì)，故用Euclidean算法能找到r和s，滿足：

r * e1 + s * e2 = 1

假設(shè)r為負(fù)數(shù)巍实，需再用Euclidean算法計(jì)算C1^(-1）滓技，則

（C1^(-1））^(-r) * C2^s = P mod n

另外，還有其它幾種利用公共模數(shù)攻擊的方法棚潦×钇總之，如果知道給定模數(shù)的一對e和d丸边，一是有利于攻擊者分解模數(shù)叠必，一是有利于攻擊者計(jì)算出其它成對的e’和d’，而無需分解模數(shù)妹窖。解決辦法只有一個(gè)纬朝，那就是不要共享模數(shù)n。

RSA的小指數(shù)攻擊嘱吗。有一種提高 RSA速度的建議是使公鑰e取較小的值玄组，這樣會(huì)使加密變得易于實(shí)現(xiàn)滔驾，速度有

所提高谒麦。但這樣做是不安全的，對付辦法就是e和d都取較大的值哆致。

RSA的邊信道攻擊

針對RSA的邊信道攻擊現(xiàn)今大多處于實(shí)驗(yàn)室階段绕德，邊信道攻擊并不是直接對RSA的算法本身進(jìn)行攻擊，而是針對計(jì)算RSA的設(shè)備的攻擊√В現(xiàn)今的邊信道攻擊一般是針對硬件實(shí)現(xiàn)RSA算法的芯片進(jìn)行的耻蛇。[2]

現(xiàn)國內(nèi)外防范公鑰密碼邊信道攻擊主要以犧牲效率為代價(jià)。公鑰密碼的實(shí)現(xiàn)效率一直是信息安全系統(tǒng)的應(yīng)用瓶頸胞此，進(jìn)一步損害算法效率臣咖，必將造成信息系統(tǒng)性能惡化。因此漱牵，尋找高效又抗功耗分析的公鑰算法實(shí)現(xiàn)途徑夺蛇，并結(jié)合其他層面抗攻擊手段，使密碼器件運(yùn)行效率酣胀、功耗刁赦、面積等綜合因素實(shí)現(xiàn)最優(yōu)化，無疑是極富挑戰(zhàn)性的課題闻镶，不僅對抗邊信道攻擊理論研究有重要價(jià)值甚脉，而且對廣泛應(yīng)用的智能卡（尤其是銀行卡、手機(jī)SIM或USIM卡）铆农、各種硬件密碼電子設(shè)備牺氨、有時(shí)也包括軟件實(shí)現(xiàn)的密碼算法的安全應(yīng)用無疑具有極大的現(xiàn)實(shí)意義。

邊信道攻擊以功耗分析和公鑰密碼為研究重點(diǎn)，在對各種類型猴凹、系列酝豪、型號、規(guī)模的基本電路運(yùn)行過程中的功耗軌跡進(jìn)行大量研究精堕、掌握其變化規(guī)律的基礎(chǔ)上孵淘，繼續(xù)研究電路工藝、結(jié)構(gòu)歹篓、算法瘫证、協(xié)議對功耗軌跡的影響，經(jīng)過一系列處理庄撮，從中提取出密鑰信息背捌。目標(biāo)是針對功耗分析攻擊機(jī)理，提出抗功耗分析的綜合優(yōu)化新方法洞斯，并盡量兼顧算法效率。

邊信道攻擊研究涉及密碼學(xué)烙如、信息論么抗、算法理論和噪聲理論，還涉及硬件電路設(shè)計(jì)亚铁、通信蝇刀、信號處理、統(tǒng)計(jì)分析徘溢、模式識別等諸多技術(shù)吞琐。

邊信道攻擊在若干關(guān)鍵問題研究上已取得了實(shí)質(zhì)性進(jìn)展。

目前國內(nèi)已經(jīng)有大學(xué)的研究者提出了公鑰密碼等功耗編碼的綜合優(yōu)化方法然爆，佐證了安全性和效率的可兼顧性站粟。截至目前，研究團(tuán)隊(duì)已針對著名公鑰密碼算法RSA的多種實(shí)現(xiàn)算法和方式成功實(shí)施了計(jì)時(shí)攻擊曾雕、簡單功耗和簡單差分功耗分析攻擊奴烙，實(shí)驗(yàn)驗(yàn)證了多種防御方法，包括 “等功耗編碼”方法的有效性翻默，并完成了大規(guī)模功耗分析自動(dòng)測試平臺的自主開發(fā)缸沃。

缺點(diǎn)

編輯

1）產(chǎn)生密鑰很麻煩，受到素?cái)?shù)產(chǎn)生技術(shù)的限制修械，因而難以做到一次一密趾牧。

2）安全性，RSA的安全性依賴于大數(shù)的因子分解肯污，但并沒有從理論上證明破譯RSA的難度與大數(shù)分解難度等價(jià)翘单，而且密碼學(xué)界多數(shù)人士傾向于因子分解不是NP問題《滞鳎現(xiàn)今，人們已能分解140多個(gè)十進(jìn)制位的大素?cái)?shù)哄芜，這就要求使用更長的密鑰貌亭，速度更慢；另外认臊，人們正在積極尋找攻擊RSA的方法圃庭，如選擇密文攻擊，一般攻擊者是將某一信息作一下偽裝（Blind）失晴，讓擁有私鑰的實(shí)體簽署剧腻。然后，經(jīng)過計(jì)算就可得到它所想要的信息涂屁。實(shí)際上书在，攻擊利用的都是同一個(gè)弱點(diǎn)，即存在這樣一個(gè)事實(shí)：乘冪保留了輸入的乘法結(jié)構(gòu)：

（XM)d = Xd *Md mod n

前面已經(jīng)提到拆又，這個(gè)固有的問題來自于公鑰密碼系統(tǒng)的最有用的特征--每個(gè)人都能使用公鑰儒旬。但從算法上無法解決這一問題，主要措施有兩條：一條是采用好的公鑰協(xié)議帖族，保證工作過程中實(shí)體不對其他實(shí)體任意產(chǎn)生的信息解密栈源，不對自己一無所知的信息簽名；另一條是決不對陌生人送來的隨機(jī)文檔簽名盟萨，簽名時(shí)首先使用One-Way Hash Function對文檔作HASH處理凉翻，或同時(shí)使用不同的簽名算法。除了利用公共模數(shù)捻激，人們還嘗試一些利用解密指數(shù)或φ（n）等等攻擊.

3）速度太慢，由于RSA 的分組長度太大前计，為保證安全性胞谭，n 至少也要 600 bits以上，使運(yùn)算代價(jià)很高男杈，尤其是速度較慢丈屹，較對稱密碼算法慢幾個(gè)數(shù)量級；且隨著大數(shù)分解技術(shù)的發(fā)展伶棒，這個(gè)長度還在增加旺垒，不利于數(shù)據(jù)格式的標(biāo)準(zhǔn)化。SET(Secure Electronic Transaction）協(xié)議中要求CA采用2048比特長的密鑰肤无，其他實(shí)體使用1024比特的密鑰先蒋。為了速度問題，人們廣泛使用單宛渐，公鑰密碼結(jié)合使用的方法竞漾，優(yōu)缺點(diǎn)互補(bǔ)：單鑰密碼加密速度快眯搭，人們用它來加密較長的文件，然后用RSA來給文件密鑰加密业岁，極好的解決了單鑰密碼的密鑰分發(fā)問題鳞仙。

攻擊進(jìn)度

編輯

針對RSA最流行的攻擊一般是基于大數(shù)因數(shù)分解。1999年笔时，RSA-155（512bits）被成功分解棍好，花了五個(gè)月時(shí)間（約8000 MIPS 年）和224 CPU hours 在一臺有3.2G中央內(nèi)存的Cray C916計(jì)算機(jī)上完成。

2002年允耿，RSA-158也被成功因數(shù)分解梳玫。

2009年12月12日，編號為 RSA-768 （768bits,232 digits）數(shù)也被成功分解右犹。

北京時(shí)間2013年2月15日上午消息提澎，據(jù)《紐約時(shí)報(bào)》周二報(bào)道，歐美數(shù)學(xué)家和密碼學(xué)家偶然發(fā)現(xiàn)念链，被全世界廣泛應(yīng)用的公鑰加密算法RSA存在漏洞盼忌。

他們發(fā)現(xiàn)，在700萬個(gè)實(shí)驗(yàn)樣本中有2.7萬個(gè)公鑰并不是按理論隨機(jī)產(chǎn)生的掂墓。也就是說谦纱，或許有人可以找出產(chǎn)生公鑰的秘密質(zhì)數(shù)。

該研究項(xiàng)目是由美國獨(dú)立密碼學(xué)家James P.Hughes和荷蘭數(shù)學(xué)家Arjen K. Lenstra牽頭的君编。他們的報(bào)告稱：“我們發(fā)現(xiàn)絕大多數(shù)公鑰都是按理論產(chǎn)生的跨嘉，但是每一千個(gè)公鑰中會(huì)有兩個(gè)存在安全隱患〕院伲”

報(bào)告稱祠乃，為防止有人利用該漏洞，有問題的公鑰已從公眾訪問的數(shù)據(jù)庫中移除兑燥。為確保系統(tǒng)的安全性亮瓷，網(wǎng)站需要在終端做出改變。

公式和定理

數(shù)和互為素?cái)?shù)

任何大于1的整數(shù)a能被因式分解為如下唯一形式：

a=p1p2…pl(p1,p2降瞳，…嘱支，pl為素?cái)?shù)）

二、模運(yùn)算

①{[a(mod n)]×[b(mod n)]}modn≡（a×b)(mod n)

②如果（a×b）=（a×c）（mod n),a與n互素挣饥，則

b=c(mod n)

三除师、費(fèi)馬定理

若p是素?cái)?shù)，a與p互素扔枫，則

a^(p-1）≡1 （mod p）

四汛聚、歐拉定理

歐拉函數(shù)φ（n）表示不大于n且與n互素的正整數(shù)的個(gè)數(shù)。

當(dāng)n是素?cái)?shù)茧吊，φ（n)=n-1贞岭。n=pq,p,q均為素?cái)?shù)時(shí)八毯，則φ（n)= φ（p）φ（q)=（p-1）（q-1）。

對于互素的a和n瞄桨，有a^φ（n)≡1(mod n)

如何利用計(jì)算機(jī)程序從公鑰e,以及φ（n）求得私鑰d?

問題可以化為求： e *x +φ（n）* y = 1 類型的方程话速，利用擴(kuò)展歐幾里得算法求解

c++實(shí)現(xiàn)

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18intinv(inte,intp)

{

intx1,x2,x3,y1,y2,y3;

intz1,z2,z3;

x1=1;x2=0;x3=p;

y1=0;y2=1;y3=e;

intq;

for(;;)

{

q=x3/y3;

z1=x1;z2=x2;z3=x3;

x1=y1;x2=y2;x3=y3;

y1=z1-y1*q;

y2=z2-y2*q;

y3=z3-y3*q;

if(y3==1)returny2>0?y2:y2+p;

}

}

Java實(shí)現(xiàn)詳細(xì)案例:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215importorg.apache.commons.codec.binary.Base64;

importjavax.crypto.Cipher;

importjava.security.*;

importjava.security.spec.PKCS8EncodedKeySpec;

importjava.security.spec.X509EncodedKeySpec;

importjava.util.HashMap;

importjava.util.Map;

/**

*?Created?by?humf.需要依賴?commons-codec?包

*/

publicclassRSACoder?{

publicstaticfinalString?KEY_ALGORITHM?="RSA";

publicstaticfinalString?SIGNATURE_ALGORITHM?="MD5withRSA";

privatestaticfinalString?PUBLIC_KEY?="RSAPublicKey";

privatestaticfinalString?PRIVATE_KEY?="RSAPrivateKey";

publicstaticbyte[]?decryptBASE64(String?key)?{

returnBase64.decodeBase64(key);

}

publicstaticString?encryptBASE64(byte[]?bytes)?{

returnBase64.encodeBase64String(bytes);

}

/**

*?用私鑰對信息生成數(shù)字簽名

*

*?@param?data???????加密數(shù)據(jù)

*?@param?privateKey?私鑰

*?@return

*?@throws?Exception

*/

publicstaticString?sign(byte[]?data,?String?privateKey)throwsException?{

//?解密由base64編碼的私鑰

byte[]?keyBytes?=?decryptBASE64(privateKey);

//?構(gòu)造PKCS8EncodedKeySpec對象

PKCS8EncodedKeySpec?pkcs8KeySpec?=newPKCS8EncodedKeySpec(keyBytes);

//?KEY_ALGORITHM?指定的加密算法

KeyFactory?keyFactory?=?KeyFactory.getInstance(KEY_ALGORITHM);

//?取私鑰匙對象

PrivateKey?priKey?=?keyFactory.generatePrivate(pkcs8KeySpec);

//?用私鑰對信息生成數(shù)字簽名

Signature?signature?=?Signature.getInstance(SIGNATURE_ALGORITHM);

signature.initSign(priKey);

signature.update(data);

returnencryptBASE64(signature.sign());

}

/**

*?校驗(yàn)數(shù)字簽名

*

*?@param?data??????加密數(shù)據(jù)

*?@param?publicKey?公鑰

*?@param?sign??????數(shù)字簽名

*?@return?校驗(yàn)成功返回true?失敗返回false

*?@throws?Exception

*/

publicstaticbooleanverify(byte[]?data,?String?publicKey,?String?sign)

throwsException?{

//?解密由base64編碼的公鑰

byte[]?keyBytes?=?decryptBASE64(publicKey);

//?構(gòu)造X509EncodedKeySpec對象

X509EncodedKeySpec?keySpec?=newX509EncodedKeySpec(keyBytes);

//?KEY_ALGORITHM?指定的加密算法

KeyFactory?keyFactory?=?KeyFactory.getInstance(KEY_ALGORITHM);

//?取公鑰匙對象

PublicKey?pubKey?=?keyFactory.generatePublic(keySpec);

Signature?signature?=?Signature.getInstance(SIGNATURE_ALGORITHM);

signature.initVerify(pubKey);

signature.update(data);

//?驗(yàn)證簽名是否正常

returnsignature.verify(decryptBASE64(sign));

}

publicstaticbyte[]?decryptByPrivateKey(byte[]?data,?String?key)throwsException{

//?對密鑰解密

byte[]?keyBytes?=?decryptBASE64(key);

//?取得私鑰

PKCS8EncodedKeySpec?pkcs8KeySpec?=newPKCS8EncodedKeySpec(keyBytes);

KeyFactory?keyFactory?=?KeyFactory.getInstance(KEY_ALGORITHM);

Key?privateKey?=?keyFactory.generatePrivate(pkcs8KeySpec);

//?對數(shù)據(jù)解密

Cipher?cipher?=?Cipher.getInstance(keyFactory.getAlgorithm());

cipher.init(Cipher.DECRYPT_MODE,?privateKey);

returncipher.doFinal(data);

}

/**

*?解密

*?用私鑰解密

*

*?@param?data

*?@param?key

*?@return

*?@throws?Exception

*/

publicstaticbyte[]?decryptByPrivateKey(String?data,?String?key)

throwsException?{

returndecryptByPrivateKey(decryptBASE64(data),key);

}

/**

*?解密

*?用公鑰解密

*

*?@param?data

*?@param?key

*?@return

*?@throws?Exception

*/

publicstaticbyte[]?decryptByPublicKey(byte[]?data,?String?key)

throwsException?{

//?對密鑰解密

byte[]?keyBytes?=?decryptBASE64(key);

//?取得公鑰

X509EncodedKeySpec?x509KeySpec?=newX509EncodedKeySpec(keyBytes);

KeyFactory?keyFactory?=?KeyFactory.getInstance(KEY_ALGORITHM);

Key?publicKey?=?keyFactory.generatePublic(x509KeySpec);

//?對數(shù)據(jù)解密

Cipher?cipher?=?Cipher.getInstance(keyFactory.getAlgorithm());

cipher.init(Cipher.DECRYPT_MODE,?publicKey);

returncipher.doFinal(data);

}

/**

*?加密

*?用公鑰加密

*

*?@param?data

*?@param?key

*?@return

*?@throws?Exception

*/

publicstaticbyte[]?encryptByPublicKey(String?data,?String?key)

throwsException?{

//?對公鑰解密

byte[]?keyBytes?=?decryptBASE64(key);

//?取得公鑰

X509EncodedKeySpec?x509KeySpec?=newX509EncodedKeySpec(keyBytes);

KeyFactory?keyFactory?=?KeyFactory.getInstance(KEY_ALGORITHM);

Key?publicKey?=?keyFactory.generatePublic(x509KeySpec);

//?對數(shù)據(jù)加密

Cipher?cipher?=?Cipher.getInstance(keyFactory.getAlgorithm());

cipher.init(Cipher.ENCRYPT_MODE,?publicKey);

returncipher.doFinal(data.getBytes());

}

/**

*?加密

*?用私鑰加密

*

*?@param?data

*?@param?key

*?@return

*?@throws?Exception

*/

publicstaticbyte[]?encryptByPrivateKey(byte[]?data,?String?key)

throwsException?{

//?對密鑰解密

byte[]?keyBytes?=?decryptBASE64(key);

//?取得私鑰

PKCS8EncodedKeySpec?pkcs8KeySpec?=newPKCS8EncodedKeySpec(keyBytes);

KeyFactory?keyFactory?=?KeyFactory.getInstance(KEY_ALGORITHM);

Key?privateKey?=?keyFactory.generatePrivate(pkcs8KeySpec);

//?對數(shù)據(jù)加密

Cipher?cipher?=?Cipher.getInstance(keyFactory.getAlgorithm());

cipher.init(Cipher.ENCRYPT_MODE,?privateKey);

returncipher.doFinal(data);

}

/**

*?取得私鑰

*

*?@param?keyMap

*?@return

*?@throws?Exception

*/

publicstaticString?getPrivateKey(Map?keyMap)

throwsException?{

Key?key?=?(Key)?keyMap.get(PRIVATE_KEY);

returnencryptBASE64(key.getEncoded());

}

/**

*?取得公鑰

*

*?@param?keyMap

*?@return

*?@throws?Exception

*/

publicstaticString?getPublicKey(Map?keyMap)

throwsException?{

Key?key?=?keyMap.get(PUBLIC_KEY);

returnencryptBASE64(key.getEncoded());

}

/**

*?初始化密鑰

*

*?@return

*?@throws?Exception

*/

publicstaticMap?initKey()throwsException?{

KeyPairGenerator?keyPairGen?=?KeyPairGenerator

.getInstance(KEY_ALGORITHM);

keyPairGen.initialize(1024);

KeyPair?keyPair?=?keyPairGen.generateKeyPair();

Map?keyMap?=newHashMap(2);

keyMap.put(PUBLIC_KEY,?keyPair.getPublic());//?公鑰

keyMap.put(PRIVATE_KEY,?keyPair.getPrivate());//?私鑰

returnkeyMap;

}

}

java實(shí)現(xiàn)

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29//例子為算47?*?x?+?30?*?y?==1?的解

publicclassExercise

{

publicstaticvoidmain(String[]?args)

{

int[]?p?=newint[2];

inta?=47;

intb?=30;

RSA(a,b,p);

System.out.print("p[0]?is:?"+?p[0]?+";p[1]?is："+?p[1]);//p1為私鑰

}

publicstaticint[]?RSA(inta,intb,int[]?p)//這里假設(shè)a?>?b

{

if(a%b?==1)

{

p[0]?=1;

p[1]?=?-(a?-1)?/?b;

returnp;

}

else

{

RSA(b,a?%?b,p);

intt?=?p[0];

p[0]?=?p[1];

p[1]?=?t?-?(a?/?b)?*?p[1];

returnp;

}

}

}