【文章內(nèi)容簡介】 NPC問題。 RSA的缺點(diǎn)主要有： A)產(chǎn)生密鑰很麻煩，受到素?cái)?shù)產(chǎn)生技術(shù)的限制，因而難以做到一次一密。 B)分組長度太大，為保證安全性， n 至少也要 600 bits。 RSA算法的時(shí)間復(fù)雜性取決于它所設(shè)計(jì)的幾個(gè)基本運(yùn)算的時(shí)間復(fù)雜性。密鑰生成過程時(shí)間主要是生成隨機(jī)素?cái)?shù)的時(shí)間及計(jì)算公鑰和私鑰的模乘法的時(shí)間。生成隨機(jī)素?cái)?shù)的時(shí)間在于完成對(duì)隨機(jī)大數(shù)的 Fermat測試的時(shí)間， Fermat測試的時(shí)間復(fù)雜度為 O((log2n)3)， n所測試的整數(shù)。模乘法的計(jì)算方法采取先計(jì)算兩個(gè)數(shù)的乘積，再取模 n，時(shí)間復(fù)雜性為 O((log2n)2)。 RSA加密解密計(jì)算的時(shí)間主要是模冪運(yùn)算的時(shí)間，即形式為 xc mod n的函數(shù)的運(yùn)算時(shí)間。模冪算法采取平方乘算法，設(shè) l是 c的長度，則計(jì)算 xc mod n至多需要 2l次模乘法，因?yàn)? 1?[log2n]+1,所以模冪運(yùn)算第 3 頁 共 23 頁 能 在時(shí)間 O((log2n)3)內(nèi)完成。因此， RSA的加密和解密均可在多項(xiàng)式時(shí)間內(nèi)完成。 RSA公開密鑰加密算法自 20世紀(jì) 70年代提出以來，已經(jīng)得到了廣泛認(rèn)可和應(yīng)用。發(fā)展至今，電子安全領(lǐng)域的各方面已經(jīng)形成了較為完備的國際規(guī)范。 RSA作為最重要的公開密鑰算法，在各領(lǐng)域的應(yīng)用數(shù)不勝數(shù)。 RSA在硬件方面，以技術(shù)成熟的 IC應(yīng)用于各種消費(fèi)類電子產(chǎn)品。 RSA在軟件方面的應(yīng)用，主要集中在Inter上、加密連接、數(shù)字簽名和數(shù)字證書的核心算法廣泛使用 RSA。 RSA 算法的實(shí)現(xiàn)原理 1) 隨機(jī)選擇兩個(gè)不同的素?cái)?shù) p和 q，它們的寬度是密鑰寬度的二分之一。 2) 計(jì)算出 p和 q的乘積 n 。 3) 在 2和 Φ(n) 之間隨機(jī)選擇一個(gè)數(shù) e , e 必須和 Φ(n) 互素，整數(shù) e用做加密密鑰（其中 Φ(n)=(p 1)*(q1)）。 4) 從公式 ed ≡ 1 mod Φ(n) 中求出解密密鑰 d 。 5) 得公鑰 （ e ， n ） , 私鑰 (d , n) 。 6) 公開公鑰，但不公開私鑰。 7) 將明文 P (假設(shè) P是一個(gè)小于 n的整數(shù) )加密為密文 C，計(jì)算方法為： C = P^e mod n。 8) 將密文 C解密為明文 P，計(jì)算方法為： P=C^d mod n。 然而只根據(jù) n和 e（不是 p和 q）要計(jì)算出 d是不可能的。因此，任何人都可對(duì)明文進(jìn)行加密，但只有授權(quán)用戶（知道 d）才可對(duì)密文解密 。 RSA數(shù)字簽名基本概念和 RSA 數(shù)字簽名算法的實(shí)現(xiàn)原理 RSA 數(shù)字簽名基本概念 RSA數(shù)字簽名體制使用了 RSA公開密鑰密碼 算法進(jìn)行數(shù)字簽名，鑒于 RSA算法在實(shí)踐中已經(jīng)被證明了的安全性， RSA數(shù)字簽名體制在許多安全標(biāo)準(zhǔn)中得以廣泛應(yīng)用。 ISO/IEC 9796和 ANSI 以及美國聯(lián)邦信息處理標(biāo)準(zhǔn) FIPS 1862已經(jīng)將 RSA作為推薦的數(shù)字簽名標(biāo)準(zhǔn) 算法之一。 RSA數(shù)字簽名算法，包括簽名算法和驗(yàn)證簽名算法。它是利用的 RSA算法的加密和解密算法的原理進(jìn)行的一種數(shù)字簽名，實(shí)際上是通過一個(gè)哈希函數(shù)來實(shí)現(xiàn)的（本設(shè)計(jì)是通過的 MD5算法）產(chǎn)生消息摘要 MD來實(shí)現(xiàn)的所需加密的對(duì)象。 數(shù)字簽名的特點(diǎn)是它代表了消息的特征，消息如 果發(fā)生改變，數(shù)字簽名的值也將發(fā)生改變，不同的消息將得到不同的數(shù)字簽名。安全的數(shù)字簽名使接收方可以得到保證：消息確實(shí)來自發(fā)送方。因?yàn)楹灻乃借€只有發(fā)送方自己保存，他人無法做一樣的數(shù)字簽名，如果第三方冒充發(fā)送方發(fā)出一個(gè)消息，而接收方在對(duì)數(shù)字簽名進(jìn)行解密時(shí)使用的是發(fā)送方的公開密鑰，只要第三方不知道發(fā)送方的私有第 4 頁 共 23 頁 密鑰，加密出來的數(shù)字簽名和經(jīng)過計(jì)算的數(shù)字簽名必然是不相同的，這就提供了一個(gè)安全的確認(rèn)發(fā)送方身份的方法，即數(shù)字簽名的真實(shí)性得到了保證。 數(shù)字簽名通過認(rèn)證技術(shù)來辨認(rèn)真?zhèn)?。認(rèn)證技術(shù)主要包括數(shù)字簽名認(rèn)證、身份認(rèn)證以及 公開密鑰證明等。數(shù)字簽名認(rèn)證機(jī)制提供了一種對(duì)數(shù)字簽名進(jìn)行鑒別的方法；身份認(rèn)證機(jī)制提供了辨別和確認(rèn)通信雙方真實(shí)身份的方法；公開密鑰證明機(jī)制則對(duì)密鑰進(jìn)行驗(yàn)證。網(wǎng)絡(luò)時(shí)代中，人們驗(yàn)證數(shù)字簽名來確定你正在和誰打交道，驗(yàn)證你的文件是否已被黑客篡改。數(shù)據(jù)的安全性和真實(shí)性已成為網(wǎng)絡(luò)安全中至關(guān)重要的一部分。 數(shù)字簽名類似手書簽名，它具有以 下的性質(zhì)： 1） 能夠驗(yàn)證簽名產(chǎn)生者的身份，以及產(chǎn)生簽名的日期和時(shí)間； 2） 能 用 于 證實(shí)被簽消息內(nèi)容； 3） 數(shù)字簽名可由第三方驗(yàn)證，從而能夠解決通信雙方的爭議。 為了實(shí)現(xiàn)數(shù)字簽名的以上性質(zhì)，它就 應(yīng)滿足下列要求： 1） 簽名是可信的：任何人都可以驗(yàn)證簽名的有效性； 2） 簽名是不可偽造的：除了合法的簽名者外，任何人偽造其簽名是困難的； 3） 簽名是不可復(fù)制的：對(duì)一個(gè)消息的簽名不能通過復(fù)制變?yōu)榱硪粋€(gè)消息的簽名。如果一個(gè)消息的簽名是從別處復(fù)制得到的，則任何人都可以發(fā)現(xiàn)消息與簽名之間的不一致性，從而可以拒絕簽名的消息； 4） 簽名的消息是不可改變的：經(jīng)簽名的消息不能篡改，一旦簽名的消息被篡改，任何人都可以發(fā)現(xiàn)消息與簽名之間的不一致性； 5） 簽名是不可抵賴的：簽名者事后不能否認(rèn)自己的簽名。可以由第三方或仲裁方來確認(rèn) 雙方的信息，以做出仲裁。 為了滿足數(shù)字簽名的這些要求，例如，通信雙方在發(fā)送消息時(shí)，既要防止接收方或其他第三方偽造，又要防止發(fā)送方因?qū)ψ约旱牟焕裾J(rèn)，也就是說，為了保證數(shù)字簽名的真實(shí)性。 數(shù)字簽名的原理是：（發(fā)送方和接收方根據(jù)要求各自產(chǎn)生自己的一對(duì)公鑰和私鑰） 1）被發(fā)送文件采用某種算法對(duì)原始消息進(jìn)行運(yùn)算，得到一個(gè)固定長度的數(shù)字串，稱為消息摘要（ MD），不同的消息得到的消息摘要各異，但是對(duì)相同的消息它的消息摘要卻是唯一的； 2）發(fā)送方生成消息的消息摘要，用自己的私鑰對(duì)摘要進(jìn)行加密來形成發(fā)送方的數(shù)字簽名； 3）這個(gè)數(shù)字簽名將作為消息的附件和消息一同用接收方的公鑰進(jìn)行加密，將加密后的密文一起發(fā)送給接收方； 第 5 頁 共 23 頁 4）接收方首先把接收到的密文用自己的私鑰解密，得到原始消息和數(shù)字簽名，再用發(fā)送方的公鑰解密數(shù)字簽名，隨后用同樣的算法計(jì)算出消息摘要； 5）如果計(jì)算出來的消息摘要和發(fā)送方發(fā)送給他的消息摘要（通過解密數(shù)字簽名得到的）是相同的，這樣接收方就能確認(rèn)數(shù)字簽名確實(shí)是發(fā)送方的，否則就認(rèn)為收到的消息是偽造的或是中途被篡改的。 數(shù)字簽名的原理圖如 21所示 A B 用 A的私鑰加密 用 B的公鑰 用 B的私鑰 用 A的公鑰解密 數(shù)字簽名 加密 解密 核實(shí)簽名 圖 21 數(shù)字簽名的原理 RSA 數(shù)字簽名算法的實(shí)現(xiàn)原理 RSA數(shù)字簽名算法分為以下兩個(gè)步驟： 1） 簽名算法（包括兩步：消息摘要計(jì)算， RSA加密） (1)消息摘要 MD的計(jì)算： 消息在簽名前首先通過 MD5計(jì)算，生成 128位的消息摘要 ； MD5函數(shù)是一種單向散列函數(shù)，它將任意長度的消息壓縮成 128位的消息摘要。應(yīng)用 MD5的單向性（即給定散列值 ,計(jì)算消息很難）和抗碰撞性 (即給定消息 M，要找到另一消息 M’并滿足兩者的散列值很難 )，可以實(shí)現(xiàn)信息的完整性檢驗(yàn)。另外該函數(shù)的設(shè)計(jì)不基于任何假設(shè)和密碼體制而直接構(gòu)造，執(zhí)行的速度快，是一種被廣泛認(rèn)可的單向散列算法。 (2)對(duì) MD作 RSA加密算法：采用簽名者的私鑰加密消息摘要，得到加密后的字符串即數(shù)字簽名； 2） 驗(yàn)證簽名算法 （ RSA解密、對(duì)消息摘要計(jì)算和比較） 驗(yàn)證簽名算法包 括兩步： RSA解密得簽名者的消息摘要，驗(yàn)證者對(duì)原消息計(jì)算摘要，比較兩個(gè)消息摘要。驗(yàn)證簽名的過程輸入為消息，簽名者的公鑰，簽名；輸出為驗(yàn)證的結(jié)果，即是否是正確的簽名。 (1)RSA解密： 簽名實(shí)際是加密的消息摘要，用以上所述的 RSA解密方法采用簽名者的公鑰對(duì)這個(gè)加密的消息摘要解密，解密的結(jié)果應(yīng)為 128位的消息摘要。 (2)消息摘要計(jì)算和比較： 驗(yàn)證者對(duì)消息用 MD5算法重新計(jì)算，得到驗(yàn)證者自己的消息摘要。驗(yàn)證者比較解密得到的消息摘要和自己的消息摘要，如果兩者相同，則驗(yàn)證成功，可以確認(rèn)消息的完整性及簽名確實(shí)為簽 名者的；否則，驗(yàn)證失敗，確認(rèn)簽名被冒充或是被篡改。 D E D E 第 6 頁 共 23 頁 MD5 算法的介紹 MD5 消息摘要算法 (RFC 1321)是由 Rivest(公開密鑰密碼 RSA 算法的設(shè)計(jì)者之一 )所設(shè)計(jì)的單 向散列函數(shù)， MD5 不基于任何假設(shè)和密碼體制，它采用了直接構(gòu)造的辦法，速度很快，非常實(shí)用。 MD5 算法的 典型應(yīng)用是對(duì)一段信息（ message）產(chǎn)生 信息摘要 (MD),以防止被篡改。比如，在 unix 下有很多軟件在下載的時(shí)候都有一個(gè)文件名相同，文件擴(kuò)展名為 .md5 的文件，在這個(gè)文件中通常只有一行文本，大致結(jié)構(gòu)如： md5 () = 0ca175b9c0f726a831d895