【正文】 數(shù)字簽名體制 (Signature Algorithm System)是一個滿足下列條件的五元組 (M， S， K， SIG， VER)， 陜西理工學(xué)院畢業(yè)論文（設(shè)計(jì)） 第 24 頁。手工簽字的文件是不具備保密性的，文件一旦丟失，文件信息就極可能泄露。以上是簽名者不能抵賴，如果接收者確已收到對方的簽名報文，要防接收者的抵賴，在數(shù)字簽名體制中，要求接收者返回一個自己簽名的表示收到的報文，給對方或者是第三方，或者引入第三方機(jī)制，如此操作，雙方均不可抵賴。 (3)防重放：在數(shù)字簽名中，如果采用了對簽名報文添加流水號、時戳等技術(shù)，可以防止 重放攻擊。接收者使用發(fā)送者的公開密鑰對簽名報文進(jìn)行解密運(yùn)算，如其結(jié)果為明文，則簽名有效，證明對方身份是真實(shí)的。顯然要求各位保存好自己的私有密鑰，好象保存自己家門的鑰匙一樣。 數(shù)字簽名機(jī)制作為保障網(wǎng)絡(luò)信息安全的手段之一，可以解決偽造、抵賴、冒充和篡改問題 [8]。簽 名算法用于對消息產(chǎn)生數(shù)字簽名，它通常受一個簽名密鑰的控制，簽名算法或者簽名密鑰是保密的，有簽名者掌握；驗(yàn)證算法用于對消息的數(shù)字簽名進(jìn)行驗(yàn)證，根據(jù)簽名是否有效驗(yàn)證算法能夠給出該簽名為“真”或者“假”的結(jié)論。特殊數(shù)字簽名主要包括：盲簽名、雙重簽名、群簽名、門限簽名、代理簽名、門限代理簽名和不可否認(rèn)的門限代理簽名等簽名方案 [6]。 (4)按照數(shù)字簽名的實(shí)現(xiàn)分類：可分為直接和需仲裁的數(shù)字簽名。 (2)按照簽名用戶分類：可分為單個用戶簽名和多個用戶簽名方案 [5]。如果相同，則說明收到的信息是完整的，在傳輸過程中沒有被修改，否則說明信息被修改過，因此數(shù)字簽名能夠驗(yàn)證信息的完整性。 數(shù)字簽名 技術(shù)是將摘要信息用發(fā)送者的私鑰加密，與原文一起傳送給接收者。 20xx 年 4 月 1 日起開始施行的《中華人民共和國電子簽名法》中數(shù)字簽名的定義：“是指數(shù)據(jù)電文中以電子形式所含、所附用于識別簽名人身份并表明簽名人認(rèn)可其中內(nèi)容的數(shù)據(jù)。 陜西理工學(xué)院畢業(yè)論文（設(shè)計(jì)） 第 23 頁 共 41 頁 4 基 于 RSA 的數(shù)字簽名 數(shù)字簽名概述 1976年 Whittled Diffie 和 Maitin Hellman 最先提出數(shù)字簽名檔概念 [4]，目的是使簽名者對電子文件進(jìn)行簽名并且無法否認(rèn)，驗(yàn)證者無法篡改文件。密文通過傳輸?shù)綄Ψ剑邮艿矫芪恼呖梢杂盟借€通過解密公式 P = ci^d ( mod n )對密文進(jìn)行解密，然后在調(diào)用 hash 變換將 ASCII 碼轉(zhuǎn)換為英語傳輸內(nèi)容顯示出。因此，任何人都可對明文進(jìn)行加密，但只有授權(quán)用戶（知道 d）才可對密文解密。 將明文 P (假設(shè) P 是一個小于 r 的整數(shù) )加密為密文 C，計(jì)算方法為： C= mi^e ( mod n ) 隨機(jī)選取兩個素?cái)?shù) p 和 q 計(jì)算歐拉函數(shù) ( ) ( 1) * ( 1)n p q? ? ? ? 在 2 和 ()n? 之間隨機(jī)選擇一個和()n? 互素的加密密鑰 e 計(jì)算 *n p q? 已知 e 和 歐 拉 函 數(shù) ()n? ，利用1mod ( )ed n?? ，求出解密密鑰 d 得出：公鑰為 (, )ne ，私鑰為(, )nd 結(jié)束 開始 陜西理工學(xué)院畢業(yè)論文（設(shè)計(jì)） 第 18 頁 共 41 頁 N Y N Y Y N Y 圖 加密流程圖 （ 3） . 解密 經(jīng)過解密算法 moddm c n? ，將密文 c 回復(fù)為原來的明文 m 。 ③ 確定解密密鑰 d： d * e = 1 mod（ p 1） *（ q 1） 根據(jù) e、 p 和 q 可以容易地計(jì)算出 d。對應(yīng)的密文是： ci = mi^e ( mod n ) ( a ) 解密時作如下計(jì)算： mi = ci^d ( mod n ) ( b ) 算法流程 （ 1） . 產(chǎn)生密鑰 ① 任意選取兩個不同的大質(zhì)數(shù) p 和 q，計(jì)算乘積 n=p*q； ② 任意選取一個大整數(shù) e， e 與 (p1)*(q1)互素，整數(shù) e 用做加密密鑰。兩個素?cái)?shù) p和 q 不再需要，應(yīng)該丟棄，不要讓任何人知道。最后，利用 Euclid 算法計(jì)算解密密鑰 d, 滿足 e * d = 1 ( mod ( p 1 ) * ( q 1 ) ) 其中 n 和 d 也要互質(zhì)。計(jì)算： n = p * q 。據(jù)猜測，從一個密鑰和密文推斷出明文的難度等同于分解兩個大素?cái)?shù)的積。 RSA 的安全性依賴于大數(shù)分解。 ⑧ 退出。 ⑥ 轉(zhuǎn) (4) ,否則 n 可能不是素?cái)?shù) ,轉(zhuǎn) (8)。 ④ a ← a + 1。 陜西理工學(xué)院畢業(yè)論文（設(shè)計(jì)） 第 16 頁 共 41 頁 ② 分解 F ,使 F = ??rjjqj1? ,其中 qj ( j = 1,2,? ,r)為不同的素?cái)?shù) 。 則此算法的步驟如下 :, ① 分解 n 1,使 n 1= R 那么 n 的每一個素因子 p 都有 p=F *m + 1的形式 (m ? 1)。 (3). 素?cái)?shù)驗(yàn)證 采用 Pocklington定理對素?cái)?shù)進(jìn)行驗(yàn)證 ,基于 Pocklington定理的確定性素?cái)?shù)產(chǎn)生 方法 ,它需要已知 n 1的部分素因子。 ⑤ 返回 Z。 ③ 計(jì)算 Z← Mon(Z,1,n)。 所以模冪運(yùn)算 Z=am (mod n) 的計(jì)算步驟如下 : ① i← m 1。 ⑤ 返回 S 。 ③ 計(jì)算 S ← { T+[(Tmod R ) N’ mod R] N}/R 。 所以 S=Mon(A ,B ,N)=A*B*R1? mod N的計(jì)算步驟如下 : ① 計(jì)算 A’← AR mod N ,B’← B R mod N ,T← A’ B’ ?？梢钥闯?,Montgomery在算法中選取 0 T N R ,這樣 (T+MN)/R2N ,(T+MN)/R與 TR 1? mod N 也就至多相差一個 N ,只需一次額外的大數(shù)減法。 陜西理工學(xué)院畢業(yè)論文（設(shè)計(jì)） 第 15 頁 共 41 頁 上述理論中 ,T+MN =T+(TN’ kR)N =T(1+ N’ N)kRN = TR1? R kRN ,為 R的倍數(shù) ,所以 (T+MN)/R為整數(shù)。 (2). 采用 Montgomery 算法進(jìn)行優(yōu)化 MillerRabin算法最耗時的步驟是 (3)和 (6)的模冪運(yùn)算。若 n 是正整數(shù) ,選 k個小于 n 的正 整數(shù) ,以這 k 個數(shù)作為基用 MillerRabin算法進(jìn)行測試 ,若 n 是合數(shù) ,k 次測試全部通過的概率為 (1/4)k 。 MillerRabin算法并不是一個確定算法。否則轉(zhuǎn) (5)。否則轉(zhuǎn) (6)。 ④ 若 x=1或 x=n1,則 n 通過測試 ,轉(zhuǎn) (7)。 ② 隨機(jī)產(chǎn)生一個整數(shù) a(1an1)。 1兩個解。 MillerRabin算法的理論基礎(chǔ) :如果 n是一個奇素?cái)?shù) ,將 n1= 2r m ,r是非負(fù)整數(shù) ,m是正奇數(shù) , a 是和 n互素的任何整數(shù) ,那么 am ≡ 1(mod n)或者對某個 h(0? h? r1),等式 a w ≡ 1(mod n)成立 ,其中w =2h m 。 (1). Miller Rabin算法 MillerRabin算法是 Fermat算法的一 個變形改進(jìn) ,它的理論基礎(chǔ)是由 Fermat定理引申而來。檢測一個數(shù) n 是素?cái)?shù)的最確定的方法就是驗(yàn)證它不能被 2和 n 之間的任何數(shù)整除 ,但這種方法計(jì)算量太大 ,十分耗時 ,在實(shí)際中需要更有效的素性檢測方法。 素?cái)?shù)檢測 素性檢測就是判斷一個整數(shù)是否為素?cái)?shù)的準(zhǔn) 則。否則 ,i ← i+ 1,轉(zhuǎn) (4)。 (4) 當(dāng) i 53時 ,計(jì)算 y ← n (mod a[i])。 (2) 選取從 2 開始的一組個數(shù)約為 53個的素?cái)?shù) ,記為 a[i] 。這里采用大數(shù)除以小素?cái)?shù)過濾掉一部分合數(shù) ,選取 53個小素?cái)?shù)進(jìn)行對大數(shù)的過濾。所以文中的算法基于這個原理 ,預(yù)先對密鑰素?cái)?shù)進(jìn)行篩選 ,采用 Montgomery模乘算法優(yōu)化的概率性素?cái)?shù)產(chǎn)生方法 MillerRabin算法進(jìn)行檢測 ,最后用確定性素?cái)?shù)產(chǎn)生方法 Pocklington定理進(jìn)行驗(yàn)證。優(yōu)點(diǎn)在 于使用概率性素?cái)?shù)產(chǎn)生方法 ,產(chǎn)生的偽素?cái)?shù)速度很快 ,構(gòu)造的偽素?cái)?shù)無規(guī)律性。而概率性素?cái)?shù)產(chǎn)生方法的缺點(diǎn)在于它不能證明該數(shù)是素?cái)?shù) ,也就是說 ,產(chǎn)生的數(shù)只能是偽素?cái)?shù) ,為合數(shù)的可能性很小。產(chǎn)生素?cái)?shù)的方法可分為以下兩類 :確定性素?cái)?shù)的產(chǎn)生方法和概率性素?cái)?shù)的產(chǎn)生方法。根據(jù) Jcaobi符號容易推出 . 因此，只 要給定一個密文 C，不用通過解密密文就能有效的計(jì)算出結(jié)果，即反映了在 RSA密碼系統(tǒng)中，通過加密密文也會泄露一些有關(guān)的明文信息。 （ 3）由密文泄露明文相關(guān)的部分信息量 與其他一些密碼弱點(diǎn)一樣， RSA體制同樣存在將明文的部分信息由密文泄露出去的可能。除此之外，不同用戶選用的素?cái)?shù)也是不能相同的。而攻擊者截獲兩個密文后，可以通過使用擴(kuò) 展 陜西理工學(xué)院畢業(yè)論文（設(shè)計(jì)） 第 13 頁 共 41 頁 歐幾里得算法得到 r,s,使得 r. 1e +s. 2e =： 1C r . 2C s mod n=( 1m 1e )( 2m 2e )mod n= m 其中， 1m = 2m =m 為同一明文，表明即使 RSA密碼系統(tǒng)很安全，但攻擊者破獲 A發(fā)送的明文也是可能的。比如 :根據(jù) kC =RSA（ 1?km ） = 1?km e （ mod n），則有： 1C = 7123 =183（ mod187） 2C = 7183 =72（ mod187） 3C = 772 =30（ mod187） 4C = 730 =123（ mod187） 這時 4C = 1m ，對加密系統(tǒng)來說是不可靠的，必須加以克服。 （ 1）弱密鑰情形 類似其他密碼體制一樣， RSA體制也存在弱密鑰現(xiàn)象。在許多實(shí)際應(yīng)用中，人們總希望使用位數(shù)較短的密鑰 d，一是可降低解出或簽名的時間，二是能夠滿足計(jì)算能力低于主機(jī)的硬件芯片的需求，比如 IC卡 中的 CPU處理。因此 RSA的安全性是依賴于因數(shù)分解的困難性。 在 RSA算法中 ,若 n =p*q 被因數(shù)分解 ,則 RSA便被攻破。反過來，能攻破 RSA 系統(tǒng)，表明可以 分解 n 的因子，不過這不是絕對的。 安全性分析 如果說 RSA 體制的安全性等價于因子分解，那就是說，作為公鑰選擇的（ e,n）參數(shù)， n 是不能輕易被因子分解的，否則構(gòu)造單向函數(shù)的 T=Φ（ n） =(p1)(q1)就沒有秘密可言了。 ③ d 要大于 。經(jīng)驗(yàn)上 e 選 16位的素?cái)?shù)，這樣既可以有效地防止攻擊，又有較快的加、解密速度。 隨著計(jì)算機(jī)能力的不斷提高和分布式運(yùn)算的發(fā)展，沒有人敢斷言具體的安全密鑰長度。 ② p 和 q 之差要大，相差幾位以上； ③ p － 1 與 q － 1 的最大公因子要小； ④ p 和 q 要足夠大。 （ 1）算法模 n 的確定： RSA模數(shù) n =p*q是 RSA算法安全性的核心，如果模數(shù) n被分解，則 RSA公鑰密碼體制將立刻被攻破，所以選擇合適的 n是實(shí)現(xiàn) RSA 算法的重要環(huán)節(jié)。 參數(shù)分析 RSA 算法的安全性等價于分解 n 的困難性，但是在實(shí)際的應(yīng)用