【文章內容簡介】 對q1整數(shù)而言，q階有限域GF(q)存在的充要條件是q是某一素數(shù)的整次冪(以下簡稱素數(shù)冪)。設有限域GF(q)上的多項式為： ,用表示系數(shù)取自域GF(p)的一切多項式的集合。中的任何多項式不一定有乘法逆元，所以只能組成一個有單位元的無零因子環(huán)，這與整數(shù)環(huán)Z完全相似。與Z環(huán)上的素數(shù)相對應，在域上有既約多項式。設f(x)是次數(shù)大于0的多項式，若除了常數(shù)、常數(shù)與本身的乘積以外，不能再被域GF(p)上的其他多項式除盡，則稱f(x)為域GF(p)上的既約多項式。所以，一個常數(shù)總是多項式的因子，f(x)是否既約與討論的域有很大關系。散列(Hash)函數(shù)，又稱為哈希函數(shù)、雜湊函數(shù)。其運算結果就像數(shù)字式的指紋，即用一小段數(shù)據(jù)來識別大的數(shù)據(jù)對象。散列函數(shù)是密碼學，也是認證理論研究的主要內容之一。數(shù)據(jù)完整性服務確保：接收到的信息如同發(fā)送的消息一樣，其在傳輸過程中沒有被攻擊或者插入、篡改、重排等。破壞數(shù)據(jù)完整性是一種主動攻擊；而加密可以保護信息的機密性，是為了抵御被動攻擊。散列函數(shù)是目前保護數(shù)據(jù)完整性的主要技術手段。常見的散列函數(shù)攻擊方法有：生日攻擊、中途相遇攻擊和窮舉攻擊等。一個安全的散列函數(shù)應該對這些已知的攻擊法有很好的抗攻擊性。 散列函數(shù)原理散列函數(shù)H(M)，就是把任意長度的消息M，通過函數(shù)H，將其變換為一個固定長度的散列值h: h=H(M)。消息M的散列值h，就像該消息的數(shù)字指紋，可以用來保證數(shù)據(jù)的完整性，我們在前面稱其為數(shù)據(jù)摘要。散列函數(shù)是公開的，一般不涉及保密密鑰。少量有密鑰的散列函數(shù)，可以作為計算消息的認證碼等其他用途，因其有密鑰而具有一定的身份鑒別功能。目前我們指的散列函數(shù)都是單向散列函數(shù)h=H(M)，即函數(shù)H是單向函數(shù)。它有弱單向散列函數(shù)和強單向散列函數(shù)之分。單向散列函數(shù)是建立在壓縮函數(shù)(pression function)的想法之上的：給一個輸入n位長消息，得到一個較短的散列值。單向散列函數(shù)的性質：（1）函數(shù)H適用于任何大小的數(shù)據(jù)分組；（2）函數(shù)H產生一定長度輸出；（3）對于任何數(shù)據(jù)M，計算H(M)是容易實現(xiàn)的；（4）對于任何給定的散列值h，要計算出M使H(M)=h，這在計算上是不可行的；（5）對于任意給定的數(shù)據(jù)x，要計算出另外一個數(shù)據(jù)Y，使H(x)=H(y),這在計算上是不可行的；（6）要尋找任何一對數(shù)據(jù)(x，y)，使H(x)=H(y)，這在計算上也是不可行的；其中前面3個性質是散列函數(shù)應用于報文(數(shù)據(jù))鑒別的基本要求；性質4是單向函數(shù)性質；性質5也可稱其為弱抗沖突(weak collision resistance)，就是在給定x之后，考察與本特定的x相沖突的情況:性質6也可稱其為強抗沖突(strong collision resistance)，是考察任意兩個元素x，y相沖突的情況。 散列函數(shù)的一般結構散列函數(shù)是建立在壓縮函數(shù)的基礎之上的，它通過對消息分組的反復迭代壓縮，生成一個長度固定的散列值。一般在迭代的最后一個分組中，還包含有消息的長度，從而在散列值中引入消息長度的影響。下面介紹的散列函數(shù)結構是Merkie提出的，如圖31所示。本結構符合大多數(shù)散列函數(shù)的結構，如MD5，SHA1，RIPEMD160等。它接受一個消息，并把消息分為L個分組，每個分組長度為b比特。如果最后一個分組長度不足b比特，可以強制將其填充為長b比特；并且包含消息a的總長度值，從上面講述可知，添加消息的總長度值，可以提高散列函數(shù)的安全強度。由圖31可知，散列函數(shù)重復使用相同的壓縮函數(shù)f重復處理分組。f有兩個輸入:一個是前一步的n比特輸出，稱為鏈接變量；另一個是b比特的分組數(shù)據(jù)Y。在算法開始時，鏈接變量是一個初始化向量IV。最后的鏈接變量就是散列值。一般情況是bn,所以稱f為壓縮函數(shù)。（注釋） bnnfbnfbnn…f圖31 散列函數(shù)總體結構可以把散列函數(shù)總結如下： （31）其中散列函數(shù)的輸出是如果壓縮函數(shù)是抗沖突的，那么迭代函數(shù)的合成值也是抗沖突的，也就是說散列函數(shù)也是抗沖突的。所以設計安全的散列函數(shù)的關鍵就是設計安全的、抗沖突的壓縮函數(shù)。散列函數(shù)的密碼分析的著重點在于壓縮函數(shù)f的內部結構，并基于這種嘗試來尋找對f單次運行后就能產生沖突的高效技術?？偟恼f來，任何散列函數(shù)必定存在沖突，因為將長度至少等于分組長度b的數(shù)據(jù)映射為長度n的散列值，其中bn，所以沖突是肯定存在的。而需要做的是要把尋找沖突在計算上變?yōu)椴豢赡堋?SHA算法安全散列算法(SHA：Secure Hash Algorithm)是美國NIST和NSA共同設計的一個標準，用于作為數(shù)字簽名標準(DSS)的散列函數(shù)，產生數(shù)據(jù)摘要。當然也可以用到其他需要散列函數(shù)的場合。該算法于1993年公布為聯(lián)邦信息處理標準FIPS PUB 180。于1995年又頒布了一個修訂版FIPS PUB 1801，常記作SHA1。SHA的要求是消息長度小于bit,輸出的散列值長度為160bit，分組長度是512bit。 .Rivest教授設計的MD4算法原理，并模仿了該算法。下面介紹一下該算法的主要步驟。(1)附加填充比特 對于末尾分組，要求其是512bit長度，并且包含64bit的消息長度值。所以要求填充，填充比特串為100...0，即填充的最高位為I，后續(xù)各位是0。填充串的長度滿足:末尾分組剩余的剩余比特長度+填充串比特長度=51264=448，也就是在分組的最后，預留了64bit填寫消息長度。此外，如果消息的最后分組剛好512bit，此時由于需要加入64bit的消息長度，所以還是要再新增加一個分組，前面填充100...0共448bit；如果消息最后分組數(shù)據(jù)長度大于448bit，此時用100...0填滿512bit，再新增加一個分組；在新分組前面填充000...0共448bit，最后填寫消息長度。(2)附加長度值 由上面一步知道，末尾分組在最后64bit還沒有填寫，它就是用來填寫消息長度的，所以要求消息長度小于比特。填寫的64bit長度被看作無符號整數(shù)，高字節(jié)優(yōu)先。(3)設置初始化向量 壓縮函數(shù)f產生160bit的結果，可以用五個32bit的緩存寄存器A,B,C,D,E來保存這些中間結果和最終結果。初始化向量IV也裝入這五個機器存，它們的值是:A=67452301，B=EFCDAB89，C=98BADCFE，D=10325476，E=C3D2EIF0。(4)處理報文分組 處理一個512bit的報文分組比較復雜。它的輸入是512bit的分組數(shù)據(jù)和上一此的輸出160bit(在A,B,C,D,E五個寄存器中)；產生的輸出是160bit(保存在A,B,C,D,E五個寄存器中)?？偟恼f來，其包含了四個循環(huán)的模塊，每個循環(huán)模塊由20個處理步驟。四個循環(huán)體的結構是相似的，但是使用不同的原始邏輯，創(chuàng)門分別是fl,f2 ,S ,f4 。每一個循環(huán)模塊的輸入是:A,B,C,D,E五個寄存器共160bit。從當前512bit分組數(shù)據(jù)產生的20個32bit字W[i,i+ 19]。每一個循環(huán)模塊的輸出是160bit,也保存在A,B,CD,E五個寄存器中。每一個循環(huán)模塊還使用一個常數(shù)值K，其中四個模塊分別使用。其實是次方取整，，是次方取整。所有的L個分組處理完畢之后，第L階段產生的輸出便是最終的160bit散列值。SHA 算法操作:其中：IV是初始化向量，是第q個分組的最后一次循環(huán)體的輸出，L是報文的分組數(shù)目，的加法，MD是最終的散列值。 橢圓曲線的數(shù)學定義橢圓曲線的研究來源于橢圓積分： （32）這里的E(x)是x的三次多項式或四次多項式。這樣的積分不能用初等函數(shù)來表示，為此引進了所謂橢圓函數(shù)。所謂橢圓曲線是指由Weierstrass方程描述: （33）所確定的曲線，是該方程的解及無窮遠點0的集合，其中，F(xiàn)可以是有理數(shù)域、復數(shù)域、還可以為有限域G(p)（素數(shù)p3）或橢圓曲線通常用E表示，若令，代入（33）得 （34） 當時整理得： （35）定義如下參數(shù)：其中為Weierstrass方程的判別式，當滿足時，該橢圓曲線為非奇異曲線，即滿足曲線上任意一點的偏導數(shù)不能同時為0，也就是曲線上的任意一點都有切線存在，則上面的實數(shù)點可以構成加法群，而當=0時，此時第3章 橢圓曲線密碼算法的研究的橢圓曲線上的點就不宜構造群。因為若=0，方程就存在兩相等的根，也就是有兩個相重合的曲線點，求這兩點之間的加之和就是一個困難，一般情況下要去除重根的點，才可能構成群，在密碼學中一般不使用此種情形。設K是一個域(可以是有理數(shù)域、實數(shù)域或者有限域)，和，分別為其代數(shù)閉域和乘法群，橢圓曲線E(K)定義為上滿足Weierstrass方程的點加上所謂的無窮遠點的集合。 , 其中。橢圓曲線的圖象實例，如圖32所示。圖32 橢圓曲線圖象實例 橢圓曲線上的離散對數(shù)問題離散對數(shù)問題1201是很多密碼體制的安全基礎，而橢圓曲線密碼體制的安全性也是基于橢圓曲線離散對數(shù)問題(ECDI，P：Elliptic Curve Discrete Logarithm Problem)。根據(jù)前面介紹的橢圓曲線加法運算，假設橢圓曲線E上有點P，Q有：kP=Q，此時ECDLP就可以描述為:已知E上的點P，Q，求k使kP=Q，顯然E上不是任意兩個點都有離散對數(shù)解k的。在實際的密碼系統(tǒng)中的Fp，模p可以達到上百比特，要計算k是非常困難的。 有限域上安全橢圓曲線的選取安全橢圓曲線的選取需要滿足前面所描述的安全準則，下面基于這些準則，來介紹選取安全橢圓曲線的方法。獲取安全的橢圓曲線主要有以下四種辦法:(1)方法一 有限域GF(q)上隨機生成一橢圓曲線，直接計算其階，判斷階是否為大素數(shù)或含大素數(shù)因子，若是即確定，否則繼續(xù)選取曲線，直至符合條件。(2)方法二 取具有一定特殊性橢圓曲線的系數(shù)，計算該橢圓曲線的階，對該階進行判斷，直至找到所需要的安全曲線。(3)方法三 如果，其中m能被一個比較小的整數(shù)d整除，我們首先在有限域上選擇橢圓曲線E39。并計算其階，根據(jù)此值，利用Weil定理計算該曲線在其擴域GF(q)上的階，若此階符合安全標準，我們再找曲線E39。在域GF(q)上的嵌入E，則E即為所需的安全橢圓曲線。(4)方法四 首先給出具有安全條件的曲線階，然后構造具有此階的橢圓曲線。第4章 基于橢圓曲線的數(shù)字簽名第4章 基于橢圓曲線數(shù)字簽名的實現(xiàn) 數(shù)字簽名數(shù)字簽名能夠實現(xiàn)電子文檔的辨認和驗證。數(shù)字簽名是傳統(tǒng)文件手寫簽名的模擬，能夠實現(xiàn)用戶對電子形式存放的消息認證。數(shù)字簽名的目的是什么呢?簽名者要留下證據(jù)來證明他辦了這件事，所謂“白紙黑字”，親手寫下的名字就是一個最好的依據(jù)。在政治、軍事、外交等活動中簽署文件，商業(yè)活動中鑒定契約、合同，以及日常生活中寫信等，都是采用手寫簽名或蓋印章的方式來起到認證和鑒別的作用。兒百年來，用這種方式解決了許多復雜的問題。隨著信息時代的到來，電子商務、辦公自動化等數(shù)字化業(yè)務的興起，文件將不再是實實在在的物理實體，而是以電子形式進行存儲和傳輸，傳統(tǒng)的手寫簽名和印章方式己經很難再適用，需要一種能夠對電子文件進行認證的新的手段。所謂數(shù)字簽名,是以電子化形式,使用密碼方法,在數(shù)字消息中嵌入一個秘密信息,以驗證這個秘密信息是否正確來達到識別的目的。它的實質是一種密碼變換。數(shù)字簽名是認證理論和密碼學研究的一個新課題,現(xiàn)在己經是網絡安全中最流行的一個話題。數(shù)字簽名，要能起到認證和識別的目的，至少要達到以下要求:(1)要求一 不可否認性。簽名者事后不能否認自己的簽名。(2)要求二 可驗證性。接收者能驗證簽名，而任何其他人都不能偽造簽名。(3)要求三 可仲裁性。當雙方發(fā)生爭執(zhí)時，可以由一個公正的第三方出面解決爭端。數(shù)字簽名方案一般包括三個過程:系統(tǒng)的初始化過程、簽名產生過程和簽名驗證過程。在系統(tǒng)的初始化過程中要產生的數(shù)字簽名方案中用到的一切參數(shù)，有公開的，也有秘密的。在簽名產生的過程中用戶利用給定的算法對消息產生簽名，這種簽名過程可以公開，也可以不公開。在簽名驗證過程中，驗證者利用公開驗證算法對給定簽名的消息進行驗證，得出簽名的有效性。數(shù)字簽名一般的工作流程是：信息的發(fā)送方首先通過運行一個哈希函結論數(shù)(hash function)，對要發(fā)送的報文生成消息摘要，然后用自己的私鑰對這個消息摘要生成數(shù)字簽名，將這個數(shù)字簽名和報文一起發(fā)送給接收方。接收方在收到后，對數(shù)字簽名和報文進行一定的運算，通過判斷運算結果就可以確認發(fā)送方和報文的真實性。 橢圓曲線代理簽名體制 主要參數(shù)的選擇選取一個基域，一個定義在上的橢圓曲線E和E上一個為素數(shù)階p的G點，G可以公開。全局參數(shù)組為（q，F(xiàn)R，a，b，G，n，h）。 密鑰的生成（1）步驟一 選擇一個隨即整數(shù)；（2）步驟二 計算，若的橫坐標為0，則返回（1）；（3）步驟三 實體的公鑰為，私鑰為；這里，記原始簽名A和代理簽名B的公鑰和私鑰對為，其中。 代理簽名協(xié)議（1） 委托過程步驟一：A隨即選取一個整數(shù)；步驟二：計算步驟三：A計算；第4章 基于橢圓曲線的數(shù)字簽名步驟四：B驗證等式步驟五：B計算（2） 簽名過程步驟一：B隨即選取一個整數(shù)；步驟二：計算；步驟三：B計算；步驟四：計算，如果s=0，則返回（*）；式中（r,s,K）就是B對消息m的簽名。（3） 簽名過程計算；若X=0，則拒絕這個簽名；否則計算，當且僅當時接受這個簽名。其正確性可由下面算式證明：