【正文】 法三 如果 mq 2? ，其中 m能被一個比較小的整數(shù) d整除，我們首先在有限域 )2)(( 11 dqqGF ? 上選擇橢圓曲線 E39。兒百年來，用這種方式解決了許多復(fù)雜的問題。接收者能驗證簽名，而任何其他人都不能偽造簽名。接收方在收到后， 對數(shù)字簽名和報文進(jìn)行一定的運算，通過判斷運算結(jié)果就可以確認(rèn)發(fā)送方 和報文的真實性。 （ 2）代理簽名的不可偽造性 由于只有 B 知道（ ? ， K），因為只有 B能生成有效的代理簽名，甚至 A 都不能偽造該代理簽名。 橢圓曲線數(shù)字簽名的計算機實現(xiàn) 橢圓曲線數(shù)字簽名方案的建立 A為簽名方，即為發(fā)送方， B為驗證方，即為接收方： (1)步驟一 用戶 A選定一個 Hash函數(shù)。下面給出了 ECDSA方案的簽名流程圖（圖 41）和驗證流程圖（圖 42）。目前采用最快的算法計算這兩類問題所需的時間復(fù)雜度 為： }))ln ( lnln)1(1( e x p { ppOO ? （ 41） 燕山大學(xué)本科生畢業(yè)設(shè)計（論文） 28 其中 P為模的大小。由于篇幅有限，這里只列出重要的參數(shù)和結(jié)果。 第 4 章 基于橢圓曲線的數(shù)字簽名 25 橢圓曲線數(shù)字簽名算法 Input：待簽名消息 m； Output：對待簽名消息 M的數(shù)字簽名 S為整數(shù)對 (r,s)； Actions： 選擇一 臨時 FCC密鑰對 (k,R)，其中 ),( RR yxR? 與域參數(shù) T相關(guān)；令 ifnxr R ，)(mod? r=0,return to step 1；計算待簽名的 hash值 H=Hash(M)；將 H換成整數(shù) e；計算： ))(m o d(1 nrdeks A?? ? ； If s=0,return to step 1。同時由于在簽名過程中 用到了各自的公鑰，很容易與他人的代理簽名區(qū)分開。全局參數(shù)組為（ q， FR， a， b， G， n， h）。當(dāng)雙方發(fā)生爭執(zhí)時，可以由一個公正的第三方出面解決爭端。 所謂數(shù)字簽名 ,是以電子化形式 ,使用密碼方法 ,在數(shù)字消息中嵌入一個秘密信息 ,以驗證這個秘密信息是否正確來達(dá)到識別的目的。在域 GF(q)上的嵌入 E，則 E即為所需的安全橢圓曲線。 圖 32 橢圓曲線圖象實例 橢圓曲線 上的離散對數(shù)問題 離散對數(shù)問題 1201是很多密碼體制的安全基礎(chǔ)，而橢圓曲線密碼體制的安全性也是基于橢圓曲線離散對數(shù)問題 (ECDI， P： Elliptic Curve Discrete Logarithm Problem ]16[ )。 SHA 算法操作 : Lqqq CVMDABC D ECVS U MCVIVCV ??? ? ；； ))(,(3210 其中： IV是初始化向量， qABCDE)( 是第 q個分組的最后一次循環(huán)體的輸出，L是報文的分組數(shù)目， 3232 2mod是SUM 的加法， MD是最終的散列值?？偟恼f來，其包含了四個循環(huán)的模塊，每個循環(huán)模塊由 20個處理步驟。填充串的長度滿足 :末尾分組剩余的剩余比特長度 +填充串比特長度 =51264=448，也就是在分組的最后，預(yù)留了 64bit填寫 消息長度。當(dāng)然也可以用到其他需要散列函數(shù)的場合。一般情況是 bn,所以稱 f為壓縮函數(shù)。 第 3 章 橢圓曲線密碼算法的研究 15 下面介紹的散列函數(shù)結(jié)構(gòu)是 Merkie提出的，如圖 31所示。散列函數(shù)是公開的，一般不涉及保密密鑰。散列函數(shù)是密碼學(xué)，也是認(rèn)證理論研究的主要內(nèi)容之一。另一方面，對 q1整數(shù)而言，q階有限域 GF(q)存在的充要條件是 q是某一素數(shù)的整次冪 (以下簡稱素數(shù)冪 )。 先證明第一條。 例如：在由集合 {1， 1}對于乘法運算所構(gòu)成的群中，群元一 1的階數(shù)為2。 燕山大學(xué)本科生畢業(yè)設(shè)計（論文） 12 例如：全體整數(shù)的集合在通常的加法運算下構(gòu)成一個阿貝爾交換群。若僅滿足 條件 (1)和 (2)，則被稱為半群 (Semigroup)；滿足條件 (1)， (2)和 (3)者，稱 么半群 (Monoid)、弱群或類群。在密碼學(xué)中，抽象代數(shù)也己經(jīng)扮演重要角色，如在橢圓曲線密碼體制中，群以及域上的多項式理論等都是其理論基礎(chǔ)。然而，如果一個消息想以密文的形式傳到接收者，我們應(yīng)該找到一個方法 安全傳輸密鑰。大多數(shù)公鑰密碼算法 都是基于以下三種數(shù)學(xué)難題之一的： 一是背包問題：給定一個互不相同的數(shù)組成的集合，要找出一個子集，其 和為 N。公鑰密碼算法具有如下特征： 加密密鑰與解密密鑰時本質(zhì)上不通的，也就是說如果僅僅知道密碼算法和加密密鑰，而要確定解密密鑰，在計算上是不可行的；大多數(shù)公鑰密碼算法的加密密鑰與解密密鑰具有互換的性質(zhì)。 公、密鑰對的用法是，當(dāng)發(fā)方向收方通信時發(fā)方用收方的公鑰對原文進(jìn) 行加密，收方收到發(fā)方的密文后，用自己的私鑰進(jìn)行解密，其中他人是燕山大學(xué)本科生畢業(yè)設(shè)計（論文） 8 無法解 密的，因為他人不擁有自己的私鑰，這就是用公鑰加密，私鑰解密用于通信 。 (3) 基 于橢圓曲線離散對數(shù)問題的：橢圓曲線密碼系統(tǒng)。明文、密文、密鑰空間分別表示全體 明文、全體密文、全體密鑰的集合；加密與解密算法通常是一些公式、法則或 程序，規(guī)定了明文與密文之間的數(shù)學(xué)變換規(guī)則 。偽裝 (變換 )之前的信息是原始信息，成為明文 (plaintext)； 偽裝之后的消息，看起來是一串無意義的亂碼，稱為密文 (cipher text)。網(wǎng)絡(luò)信息安全是密碼學(xué)的重要應(yīng)用領(lǐng)域， 公鑰密碼體制的主要應(yīng)用之一就是數(shù)字簽名。延遲體現(xiàn)在加密或簽名認(rèn)證的速度方面。 數(shù)字簽名技術(shù)選題依據(jù)和意義 信息時代雖然給我們帶來了無限商機與方便，但同時也充斥著隱患與危險。 (3) 要獲得同樣安全強度，比 RSA 用的參數(shù)規(guī)模小得多 [2]，開銷較少且速度快。同時應(yīng)用散列算法 (Hash)也是實現(xiàn)數(shù)字簽名的一種方法。 信息安全技術(shù)在信息化迅速發(fā)展的今天己進(jìn)入了高速發(fā)展的新時期，形成了密碼技術(shù)、可信計算技術(shù)、電磁輻射泄露防護(hù)技術(shù)、系統(tǒng)入侵檢測技術(shù)和計算機病毒檢測消除技術(shù)等多個安全防護(hù)技術(shù)門類。自從 Miller提出將橢圓曲線應(yīng)用于密碼算法以來，橢圓曲線密碼體制己得到了很大的發(fā)展，己經(jīng)成為密碼學(xué)的重要研究熱點之一。 自學(xué) MATLAB 仿真語言的一種版本。 燕山大學(xué) 畢業(yè)設(shè)計（論文） 基于橢圓曲線的數(shù)字簽名研究與仿真 畢業(yè)設(shè)計（論文）原創(chuàng)性聲明和使用授權(quán)說明 原創(chuàng)性聲明 本人鄭重承諾：所呈交的畢業(yè)設(shè)計（論文），是我個人在指導(dǎo)教師的指導(dǎo)下進(jìn)行的研究工作及取得的成果。 基 本 要 求 搜集、查閱資料，掌握數(shù)字簽名的產(chǎn)生、工作原理、各類典型算法的特點及其在保密通信領(lǐng)域的應(yīng)用。 指導(dǎo)教師：田澈 系級教單位審批： 摘要 I 摘 要 隨著信息技術(shù)的不斷發(fā)展和應(yīng)用，信息的安全性變得越來越重要，數(shù)字簽名技術(shù)是當(dāng)前網(wǎng)絡(luò)安全領(lǐng)域的研究熱點。信息系統(tǒng)的應(yīng)用，加速了社會自動化的進(jìn)程，減輕了日常繁雜的重復(fù)勞動，同時也提高了生產(chǎn)率，創(chuàng)造了經(jīng)濟效益。 1994年美國標(biāo)準(zhǔn)與技術(shù)協(xié)會公布了數(shù)字簽名標(biāo)準(zhǔn) (DSS)而使公鑰加密技術(shù)廣泛應(yīng)用。 (2) 橢圓曲線公鑰密碼系統(tǒng)中的主要計算量是計算 Q=kg，且 Q 很容易求出 [1],而知道 Q、 g ，求 k 十分困難。隨著網(wǎng)上交易的頻繁，這將成為今后研究的熱點。由于 ECC能實 AIR高的安全性，只需要較小的開銷和延遲，較小的開銷體現(xiàn)在如計算量、存儲量、帶寬、軟硬件實現(xiàn)的規(guī)模等 。第 2 章 密碼學(xué)基礎(chǔ)理論 及基本概念 5 第 2 章 密碼學(xué)基本理論及基本概念 密碼學(xué)是網(wǎng)絡(luò)信息安全的基礎(chǔ)，公鑰密碼體制是密碼學(xué)的只要組成部分， 數(shù)字簽名的基礎(chǔ)就是公鑰密碼體制。 密碼學(xué)的理論基礎(chǔ)是數(shù)學(xué)，其基本思想是隱藏、偽裝信息，使未經(jīng)授權(quán)者 不能得到消息的真正含義 ]8,4[ 。 那么一個密碼系統(tǒng)或稱其為密碼體制，是由明文空間、密文空間、密燕山大學(xué)本科生畢業(yè)設(shè)計（論文） 6 鑰空 間、加密算法與解密算法五個部分組成。 (2) 基于離散對數(shù)問題的： DSA和 EIGamal。因此，將這兩個質(zhì)數(shù)稱密鑰對，其中一個采用私密的安全介質(zhì) 保 密存儲起來，應(yīng)不對任何外人泄露，簡稱為“私鑰”；一個密鑰可以公開發(fā)表，用數(shù)字證書的方式發(fā)布在稱之為“上黃頁”的目錄服務(wù)器上，用 LDAP協(xié) 議進(jìn)行查詢，也可在網(wǎng)上請對方發(fā)送信息時主動將該公鑰證書傳送給對方，這 個密鑰稱之為“私鑰”。 公鑰密碼算法使用兩個密鑰，其中一個用于加密 (加密密鑰 )，另外一個用 于解密 (解密密鑰 )。 公鑰密碼體制的數(shù)學(xué)基礎(chǔ) 通觀公鑰密碼算法，它們的數(shù)學(xué)基礎(chǔ)是比較狹窄的。 燕山大學(xué)本科生畢業(yè)設(shè)計（論文） 10 對稱加密有速度上的優(yōu)點，用軟件實現(xiàn)，對稱密鑰比非對稱密鑰快1001000倍。 第 3 章 橢圓曲線密碼算法的研究 11 第 3 章 橢圓曲線密碼算法的研究 群（ Groups） 抽象代數(shù) ]11,10,9[ 不但是數(shù)學(xué)的一個重要分之，同時在其他學(xué)科如量子力學(xué)、結(jié)晶學(xué)、原子物理學(xué)等中都己經(jīng)稱為研究者的有力武器；群論因為是研究對稱性問題的基礎(chǔ)，例如其在物理學(xué)中在諸如時間和空間的對稱性研究、乃至超對稱性問題等研究中都有應(yīng)用。 上述四個條件是構(gòu)成群的充分必要條件，通常被稱為群的公理。 b為 a與 b的積，簡寫為 ab。顯然，對于有限群 G而言，其每一群元的階都是有 限正整數(shù)。 （ 3）存在 Gcba ?， ， 若 ab=ac，則 b=c；若 ab=cb，則 a=c。有限域 )( npGF的特征為 P，其階為域中元素的個數(shù)，即 np 。其運算結(jié)果就像數(shù)字式的指紋，即用一小段數(shù)據(jù)來識別大的數(shù)據(jù)對象。 消息 M的散列值 h，就像該消息的數(shù)字指紋，可以用來保證數(shù)據(jù)的完整性， 我們在前面稱其為數(shù)據(jù)摘要。一 般在迭代的最后一個分組中，還包含有消息的長度，從而在散列值中引入消息長度的影響。最后的鏈接變量就是散列值。 SHA 算法 安全散列算法 (SHA： Secure Hash Algorithm)是美國 NIST和 NSA共同設(shè)計的一個標(biāo)準(zhǔn)，用于作為數(shù)字簽名標(biāo)準(zhǔn) (DSS)的散列函數(shù)，產(chǎn)生數(shù)據(jù)摘要。所以要求填充，填充比特串為 100...0，即填充的最高位為 I，后續(xù)各位是 0。它的輸入是512bit的分組數(shù)據(jù)和上一此的輸出 160bit(在 A,B,C,D,E五個寄存器中 )；產(chǎn)生的輸出是 160bit(保存在 A,B,C,D,E五個寄存器中 )。 所有的 L個分組處理完畢之后，第 L階段產(chǎn)生的輸出便是最終的 160bit散列值。 橢圓曲線的圖象實例，如圖 32 所示。并計算其階，根據(jù)此值，利用 Weil定 理計算該曲線在其擴域 GF(q)上的階，若此階符合安全標(biāo)準(zhǔn)，我們再找曲線 E39。隨著信息時代的到來，電子商務(wù)、辦公自動化等數(shù)字化業(yè)務(wù)的興起，文件將不再是實實在在的物理實體，而是以電子形式進(jìn)行存儲和傳輸，傳統(tǒng)的手寫簽名和印章方式己經(jīng)很難再適用，需要一種能夠?qū)﹄娮游?件進(jìn)行認(rèn)證的新的手段。 (3)要求三 可仲裁性。 橢圓曲線代理簽名體制 主要參數(shù)的選擇 選取一個基域 qF ，一個定義在 qF 上的橢圓曲線 E 和 E 上一個為素數(shù)階p 的 G 點， G 可以公開。 （ 3）代理簽名的可區(qū)分性 代理簽名是由 (r， s， K)三部分組成，因此很容易將代理簽名和原始簽名區(qū)分開。 (2)步驟二 用戶 A建 立橢圓曲線域參數(shù) T=(p， a， b， Qn， h)，根據(jù)情況選擇適當(dāng)安全強 度的密鑰數(shù)據(jù)長度； (3)步驟三 用戶 B通過可靠的方式獲得 A所選擇的 Hash函數(shù)和建立的橢圓曲線域參數(shù) T。 圖 41 ECDSA 算法簽名流程圖 圖 42 ECDSA 算法驗證簽名流程圖 根據(jù)流程圖，我們以 NIST 推薦的橢圓曲線為例，編程實現(xiàn) ECDSA 的Y N N Y 計算 ),( 11 yxkG? 和 )(mHe? )(mod1 qexr ?? 輸出簽名 計算 )(m od ndrks ?? 計算 )(mod1 nexr ?? 判定 r=0 隨 機或者偽隨 機數(shù) k s=0 A 1,1 ??? nsr N Y N Y N 計算 ),( 11 yxrQsGX ??? 計算 )(mHe? 接受簽名 拒絕簽名 )(mod11 qexr ?? 根據(jù)接收到的（ m,r,s） X=0 Check rr?1 Y 第 4 章 基于橢圓曲線的數(shù)字簽名 27 簽名算法及驗證過程。對于橢圓曲線離散對數(shù)問題，雖然也可以使用對一般群都有效的 baby— step— gi— ant