信息科學(xué)與工程學(xué)院網(wǎng)絡(luò)信息安全論文課程網(wǎng)絡(luò)信息安全課題：RSA數(shù)字簽名姓名：學(xué)號：專業(yè)：年級：指導(dǎo)教師：年月日-年月日引言自20世紀(jì)40年代計(jì)算機(jī)在美國誕生以來，計(jì)算機(jī)應(yīng)用已逐漸在社會的各個(gè)領(lǐng)域中普及。20世紀(jì)80年代中期，隨著計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)的成熟，計(jì)算機(jī)網(wǎng)絡(luò)應(yīng)用迅速普及。伴隨著我國國名經(jīng)濟(jì)信息化進(jìn)程的推進(jìn)和信息技術(shù)的普及，我國各行各業(yè)對計(jì)算機(jī)網(wǎng)絡(luò)的依賴程度越來越高，這種高度依賴使社會變得十分“脆弱”，一旦計(jì)算機(jī)網(wǎng)絡(luò)受到攻擊，不能正常工作，就會使整個(gè)社會陷入危機(jī)。所以信息與信息安全管理，已經(jīng)成為社會公共安全工作的重要組成部分。信息安全的基礎(chǔ)就是密碼理論，信息安全的基密性、完整性和抗否性都依賴于密碼算法。密碼學(xué)主要研究兩個(gè)方面：密碼編碼學(xué)和密碼分析學(xué)。密碼編碼學(xué)主要研究對信息進(jìn)行交換，以保護(hù)信息在信道的傳遞過程中不被他人竊取、解密和利用的方法，而密碼分析學(xué)則與密碼編碼學(xué)相反，它主要研究如何分析和破譯密碼。兩者之間既相互對立又相互促進(jìn)。密碼體制的分類有很多，其中一種是根據(jù)加密算法和解密算法所使用的密鑰是否相同，可以將密碼體制分為對稱密鑰密碼體制（單鑰密碼體制）和非對稱密鑰密碼體制（公鑰密碼體制），這兩種密碼體制各有自己的長處和短處，因此現(xiàn)在采用了兩種的混合體。公鑰密碼體制的特點(diǎn)是：接收方B產(chǎn)生一對密鑰（PK和ＳＫ）；ＰＫ公開，ＳＫ保密；從ＰＫ推出ＳＫ是很困難的；Ａ、Ｂ雙方通信時(shí)，Ａ通過任何途徑取得Ｂ的公鑰，用Ｂ的公鑰加密信息，加密后的信息可通過任何不安全信道發(fā)送。Ｂ收到密文信息后，用自己私鑰解密恢復(fù)出明文。公鑰密碼體制已成為確保信息的安全性的關(guān)鍵技術(shù)。RSA公鑰密碼體制到目前為止還是一種被認(rèn)可為安全的體制。RSA公鑰加密算法是第一個(gè)既能用于數(shù)據(jù)加密也能用于數(shù)字簽名的算法。它易于理解和操作，也十分流行。隨著越來越多的商業(yè)應(yīng)用和標(biāo)準(zhǔn)化工作，RSA已經(jīng)成為最具代表性的公鑰加密技術(shù)。VISA、MasterCard、IBM、Microsoft等公司協(xié)力制定的安全電子交易標(biāo)準(zhǔn)（SecureElectronicTransactions，SET）就采用了標(biāo)準(zhǔn)RSA算法，這使得RSA在我們的生活中幾乎無處不在。網(wǎng)上交易加密連接、網(wǎng)上銀行身份驗(yàn)證、各種信用卡使用的數(shù)字證書、智能移動(dòng)和存儲卡的驗(yàn)證功能芯片等，大多數(shù)使用RSA技術(shù)。一．公鑰密碼體制公鑰密碼算法的最大特點(diǎn)是采用兩個(gè)相關(guān)密鑰將加密和解密能力分開，其中一個(gè)密鑰是公開的，即公開密鑰，用于加密；另一個(gè)為用戶專用，因而是保密的，稱為秘密密鑰，用于解密。因此公鑰密碼體制又被稱為雙密鑰密碼體制。算法有以下的重要性：已知密碼算法和加密密鑰，求解密密鑰在計(jì)算上是不可行的。公鑰密鑰算法應(yīng)滿足以下要求：（1）接受方B產(chǎn)生密鑰對（公開密鑰PKB，和秘密鑰SKB）在計(jì)算上是容易的。（2）發(fā)送方A用接受方的公開密鑰對消息m進(jìn)行加密以產(chǎn)生密文c，獲取c在計(jì)算上是容易的。（3）接受方B用自己的秘密密鑰對c解密，在計(jì)算上也是容易的。（4）攻擊者由B的公開鑰PKB求秘密鑰SKB在計(jì)算上是不可行的。（5）攻擊者由密文c和B公開的密鑰PKB恢復(fù)明文m在計(jì)算上是不可行的。（6）加密解密的次序可以更換。二.數(shù)字簽名的基本原理政治,軍事，外交等領(lǐng)域的文件，命令和條約，商業(yè)中的契約，以及個(gè)人之間的書信等，傳統(tǒng)上都采用手寫或印章，以便在法律上能認(rèn)證、核準(zhǔn)和生效。隨著計(jì)算機(jī)通信的發(fā)展，人們希望通過電子設(shè)備實(shí)現(xiàn)快速、遠(yuǎn)距離的交易，數(shù)字簽名便應(yīng)運(yùn)而生，并開始用于商業(yè)通信系統(tǒng)，如電子郵遞、電子轉(zhuǎn)帳和辦公自動(dòng)化等系統(tǒng)中。數(shù)字簽名也是一種認(rèn)證機(jī)制，它是公鑰密碼學(xué)發(fā)展過程中的一個(gè)重要組成部分，是公鑰密碼算法的典型應(yīng)用。數(shù)字簽名的應(yīng)用過程是，數(shù)據(jù)源發(fā)送方使用自己的私鑰對數(shù)據(jù)校驗(yàn)和或其他與數(shù)據(jù)內(nèi)容有關(guān)的信息進(jìn)行處理，完成對數(shù)據(jù)的合法“簽名”，數(shù)據(jù)接收方則利用發(fā)送方的公鑰來驗(yàn)證收到的消息上的“數(shù)字簽名”，以確認(rèn)簽名的合法性。類似手寫簽名，數(shù)字簽名也應(yīng)該滿足一下要求：收方能夠確認(rèn)或證實(shí)發(fā)方的簽名，但不能偽造。發(fā)方發(fā)出簽名的消息送收方之后，就不能再否認(rèn)他所簽發(fā)的消息。收方對已收到的簽名消息不能否認(rèn)，即收到認(rèn)證。第三者可以確認(rèn)收發(fā)雙方之間的消息傳送，但不能偽造者以過程。1.數(shù)字簽名與手寫簽名的區(qū)別數(shù)字簽名與手寫簽名的區(qū)別在于:手寫簽名是模擬的,且因人而異;數(shù)字簽名是0和1的數(shù)字串,因消息而異。數(shù)字簽民與消息認(rèn)證的區(qū)別在于：消息認(rèn)證使收方能驗(yàn)證消息發(fā)送者及所發(fā)的消息內(nèi)容是否被篡改過。當(dāng)收發(fā)者之間沒有利害沖突時(shí)，這對于防止第三者的破壞來說是足夠了。但當(dāng)收者和發(fā)者之間有利害沖突時(shí)，單純用消息認(rèn)證技術(shù)就無法解決他們之間的糾紛，此時(shí)需要借助數(shù)字簽名技術(shù)。為了實(shí)現(xiàn)簽名的目的，發(fā)方需向收方提供足夠的非保密信息，以便使其能驗(yàn)證消息的簽名，但又不泄露用于生產(chǎn)簽名的機(jī)密信息，以防止他人偽造簽名。因此，簽名者和證實(shí)者可公用的信息不能太多。任何一種產(chǎn)生簽名的算法或函數(shù)都應(yīng)當(dāng)提供這兩種信息，而且從公開的信息很難推測出用于產(chǎn)生簽名的機(jī)密信息。另外，任何一種數(shù)字簽名的實(shí)現(xiàn)都有賴于精心設(shè)計(jì)的通信協(xié)議。2.數(shù)字簽名的分類數(shù)字簽名有兩種：一種是對整個(gè)消息的簽名，一種是對壓縮消息的簽名，它們都是附加被簽名信息之后或某一種特定位置上的一段簽名圖樣。若按明、密紋的對應(yīng)關(guān)系劃分，每一種又可以分為兩個(gè)子類：一類是數(shù)字性確定簽名，其明文與密文一一對應(yīng)，它對特定消息的簽名不變化（使用簽名者的密鑰簽名），如RSA、ElGamal等簽名；另類是隨機(jī)化的或概率式數(shù)字簽名，它對同一消息的簽名是隨機(jī)變化的，取決于簽名算法中隨機(jī)參數(shù)和取值。一個(gè)簽名體制一般包含有兩個(gè)組成部分，即簽名算法和驗(yàn)證算法。對M消息的簽名可以簡寫為Sig（M）=s（有時(shí)為了說明密鑰K在簽名中的作用，也可以將簽名寫為Sig（M，k），而對s的證實(shí)簡記為Ver（s）={真，偽}={1，0}。簽名算法或簽名密鑰是秘密的，只有簽名人掌握。證實(shí)算法應(yīng)當(dāng)公開，以便于他們進(jìn)行驗(yàn)證。一個(gè)簽名體制可以由量（M，S，K，V）表示，其中M為明文空間，S是簽名的集合，K是密鑰空間，V是證實(shí)函數(shù)的值域，由真，偽構(gòu)成。對于每一k∈K，有一簽名算法，易于計(jì)算s=Sig（k,m）∈S。利用公開的證實(shí)算法：Ver（s，m）∈{真，偽}可以驗(yàn)證簽名的真?zhèn)巍Ｋ鼈儗γ恳籱∈M,真簽名Sig(k,m)∈S為M到S的映射.易于驗(yàn)證S是否為M的簽名.Ver(s,m)=真,當(dāng)Sig(s,m)滿足驗(yàn)證方程.Ver(s,m)=偽,當(dāng)Sig(s,m)不滿足驗(yàn)證方程.三.RSA密碼算法1.RSA（Rivest-Shamir-Adelman）加密體制是一種公開的密碼體制。RSA公匙密碼體制是又R.L.Rivest，A.Shamir和L.Adelman于1978年提出的。由于RSA算法很完善，即可用于數(shù)據(jù)加密，又可用于數(shù)字簽名，安全性良好，易于實(shí)現(xiàn)和理解，所以已經(jīng)成為一種應(yīng)用極廣的公匙密碼算法，它是基于數(shù)論的非對稱(公開鑰)密碼體制。目前，RSA在許多場合有廣泛的應(yīng)用。2.RSA運(yùn)用的數(shù)論基礎(chǔ)：2.1產(chǎn)生素?cái)?shù)（1）反素?cái)?shù)n必不能被2-（實(shí)際上一個(gè)數(shù)最大公約數(shù)小于或等于）之間所有素?cái)?shù)的整數(shù)。（2）除2以外所有素?cái)?shù)為奇數(shù)，有素?cái)?shù)的定義來決定算法2.2求最大公約數(shù)設(shè)b，c為整數(shù)b>0，c>0,b>c，c的最大公約數(shù)記作gcd（b，c）可以利用歐幾里得算法：每次余數(shù)為除數(shù)除以上一次的除數(shù)直到余數(shù)為0為止，則上次的余數(shù)為最大公約數(shù)，可以現(xiàn)設(shè)b為上次的除數(shù)，c為余數(shù)，按歐幾里得算法求出gcd（b，c）。2.3互素互素：如果gcd（a，b）=1，則成a與b互素。例如21與50。同余：如果a（modn）=b(modn),則策劃能夠兩整數(shù)a和b模n同余。也就是n能整除（a-b），即n|(a-b).同余的性質(zhì)：n|(a-b),→a≡bmodn(amodn)=(bmodn),→a≡bmodna≡bmodn,→b≡amodna≡bmodn,b≡cmodn,→a≡cmodn這里要解釋一下，≡是數(shù)論中表示同余的符號。公式中，≡符號的左邊必須和符號右邊同余，也就是兩邊模運(yùn)算結(jié)果相同。2.4加法逆、乘法逆加法逆：對于加法+，若x+y≡0modn，則y為x的模n加法逆元，也稱y為-x。當(dāng)x，y∈Z（Z表示模n完全剩余系），有唯一的加法逆元。乘法逆元：對于乘法×，若xy≡1modn，則y為x的模n乘法逆元，也稱y為x的倒數(shù)，記為1/x，或者x^-1。對于乘法，不一定有逆元。設(shè)a∈Z，gcd（a，n）=1，則a在Z中有乘法逆元。2.5歐拉函數(shù)設(shè)n為一個(gè)正整數(shù)，小于n且與n互素的正整數(shù)的個(gè)數(shù)為n的歐拉函數(shù)，記為∮（n）。定理：若n是兩個(gè)互素的整數(shù)p和q的乘積，則∮（n）=∮（p）∮（q）。若p和q為不同的素?cái)?shù)，則∮（n）=∮（p）∮（q）=（p-1）（q-1）。歐拉定理：若a和n互素，則a^∮(n)≡1modn,所以a的逆元為a^(∮(n)-1)。3.RSA公鑰密碼方案建立一個(gè)RSA密碼體制的過程如下：（1）用戶選擇一對不同的大素?cái)?shù)p和q，將p和q保密。（2）令n=pq，用戶公布n。∮（n）=（p-1）（q-1），此外∮（n）是歐拉函數(shù)，保密。（3）選取正整數(shù)d，使其滿足gcd（d，∮（n））=1，將d保密。（4）最后根據(jù)公式：ed≡1（mod∮（n）），計(jì)算e并公開。公開密鑰：k1=（n，e）私有密鑰：k2=（p，q，d）RSA是一種發(fā)分組密碼系統(tǒng)，加密時(shí)首先將明文表示成從0到n-1之間的整數(shù)。如果明文太長，可將其變成為n進(jìn)制的形式，即令M=M0+M1n+M2n^1+……+Msn^s然后分別加密（M0，M1，……，Ms）。加密算法：C=E（M）≡M^e(modn)解密算法：D（C）=C^d(modn)3．實(shí)例描述通過一個(gè)簡單的例子來理解RSA的工作原理。為了便于計(jì)算。在以下實(shí)例中只選取小數(shù)值的素?cái)?shù)p,q,以及e，假設(shè)用戶A需要將明文“key”通過RSA加密后傳遞給用戶B，過程如下：3.1設(shè)計(jì)公私密鑰(e,n)和(d,n)

令p=3，q=11，得出n=p×q=3×11=33；f(n)=(p-1)(q-1)=2×10=20；取e=3，（3與20互質(zhì)）則e×d≡1modf(n)，即3×d≡1mod20。

d怎樣取值呢？可以用試算的辦法來尋找。試算結(jié)果見下表：

通過試算我們找到，當(dāng)d=7時(shí)，e×d≡1modf(n)同余等式成立。因此，可令d=7。從而我們可以設(shè)計(jì)出一對公私密鑰，加密密鑰（公鑰）為：KU=(e,n)=(3,33)，解密密鑰（私鑰）為：KR=(d,n)=(7,33)。3.2英文數(shù)字化將明文信息數(shù)字化，并將每塊兩個(gè)數(shù)字分組。假定明文英文字母編碼表為按字母順序排列數(shù)值，即：

則得到分組后的key的明文信息為：11，05，25。

3.3明文加密

用戶加密密鑰(3,33)將數(shù)字化明文分組信息加密成密文。由C≡M^e(modn)得C1≡M1^e(modn)=11^3(mod33)=11C2≡M2^e(modn)=05^3(mod33)=26C3≡M3^e(modn)=25^3(mod33)=16

因此，得到相應(yīng)的密文信息為：11，26，16。

3.4密文解密

用戶B收到密文，若將其解密，只需要計(jì)算M≡C^d(modn)，即：

M1≡C1^d(modn)=11^7(mod33)=11M2≡C2^d(modn)=26^7(mod33)=05M3≡C3^d(modn)=16^7(mod33)=25

用戶B得到明文信息為：11，05，25。根據(jù)上面的編碼表將其轉(zhuǎn)換為英文，我們又得到了恢復(fù)后的原文“key”。四．基于RSA算法的數(shù)字簽名技術(shù)1．RSA密碼體制的簽名實(shí)現(xiàn)圖：其中SKA表示A自己的密鑰。PKA為A自己公開的密鑰。A用自己的密鑰SKA對姚發(fā)送的信息m加密，得到加密文c，將c發(fā)往B，B用A公用的密鑰PKA對c解密。因?yàn)閺膍到c是經(jīng)過A的秘密鑰SKA加密，只有A才能做到。因此c可作為A對m的數(shù)字簽名。另一方面，任何人只要得不到A的秘密鑰SKA，就不能篡改m，所以以上過程獲得了對消息來源和消息完整性的認(rèn)證。以上認(rèn)證過程中，由于信息是有發(fā)送者自己的密鑰加密的，所以不能被別人篡改，但是卻會導(dǎo)致信息被竊聽。所以我們使用雙重加密、解密。首先發(fā)送者對信息使用密鑰加密，用于提供數(shù)字簽名，然后又使用接受端產(chǎn)生的公開密鑰加密，解密的時(shí)候是逆過程，先用接受方自己的密鑰解密，然后用發(fā)送放的公開密鑰解密。2．RSA簽名安全參數(shù)：令n=pq，p和q是大素?cái)?shù)，選e并計(jì)算出d，使得ed=1mod（p-1）（q-1），公開n和e，將p、q和d保密，則所有的RSA參數(shù)為k=（n，p，q，e，d）。數(shù)字簽名：對消息M∈Z定義S=Sig（M）=M^dmodn為對M的簽名。簽名驗(yàn)證：對給定的M、S可按下式驗(yàn)證：設(shè)M’=S^emodn,如果M'=M，則簽名為真；否則，不接受簽名。顯然，由于只有簽名者知道d，由RSA體制可知，其他人不能偽造簽名，但容易證實(shí)所給（M，S）對是不是消息M和相應(yīng)的簽名所構(gòu)成的合法對。RSA體制的安全性依靠于n=pq分解的復(fù)雜性。3.基于RSA密鑰算法的數(shù)字簽名實(shí)例舉例發(fā)送端輸入明文m=2，令p=3，q=11，求其簽名以及驗(yàn)證過程。n=pq=11*3=33；Z={0，1，……，32}∮（n）=（p-1）（q-1）=（11-1）（3-1）=20；取e=3，gcd（d，∮（n））=gcd（3，20）=1；e