【文章內容簡介】 3）計算 s = k^1*(h(m)+x*r) mod q?則(r,s)為簽名人對m的簽名?3. 驗證過程（1）首先檢查r和s是否屬于[0,q],若不是,則 (r,s)不是簽名。（2）計算t= s^1mod q , r’=(g^h(m) t mod q (y^r*t mod q )mod p) mod q 。（3）比較r’= r 是否成立?若成立,則(r,s) 為合法簽名,則(r,s) 為簽名人對m的簽名 DSA的安全性DSA的安全性主要依賴于整數(shù)有限域離散對數(shù)難題。其安全性與RSA相比差不多，DSA的一個重要特點是兩個素數(shù)公開，這樣，當使用別人的P和Q是，即使不知道私鑰，你也能確認他們是否是隨機產生的，還是做了手腳的。RSA算法是做不到的。素數(shù)P必須足夠大，且p1至少包含一個大素數(shù)因子以抵抗Pohligamp。hellman算法的攻擊。M一般都應采用信息HASH的值。DSA安全性主要依賴于p和g，若選取不當則簽名容易偽造，應保證g對于p1的大素數(shù)因子不可約。DSA的一個主要特點是兩個素數(shù)公開，這樣，當使用別人的p和g，即使不知道私鑰，你也能確認他們是隨機產生的。[9] 橢圓曲線代理簽名體制橢圓曲線簽名算法ECDSA是基于橢圓曲線密碼體制(ECC)的數(shù)字簽名算法。DSA是美國國家標準局制定的數(shù)字簽名算法，他是建立在有限域乘法群上的。對于有限域上的橢圓曲線密碼系統(tǒng)，數(shù)字簽名標準建議采用橢圓曲線數(shù)字簽名算法ECDSA，下面給出該算法的過程。假設一組橢圓曲線的參數(shù)組為(q，F(xiàn)R，a，b，G，n，h)。其中q是域的階，F(xiàn)R指示域中元素的表示方法，a，b是兩個系數(shù)，G是基點，G的階為n，余因子h=E(Fq)／n，他是一個小的素數(shù)。1 ECDSA密鑰對生成過程（1）選擇一個隨機數(shù)d,d∈(1,n1)?（2）計算Q,Q=d*G?（3）那么公鑰為Q,私鑰為整數(shù)d?2 ECDSA簽名過程假設待簽名的消息為，m；（1）選擇一個隨機數(shù)k，k∈(1，n1)。（2）計算k*G=(x1,y1)。（3）計算r=x1 mod n；如果r=O，則返回到步驟(1)。（4）計算s=k^1(e+d*r) mod n，如果s=O，則返回到步驟(1)。（5）對消息的簽名為(r，s)，最后簽名者把消息m和簽名(r，s)發(fā)送給接收者。3 ECDSA密鑰對驗證過程獲得發(fā)送者的公鑰Q開始驗證： （1）檢查r，s，要求r，s∈(1，n1)。（2）計算e=SHA1(m)。（3）計算w=s1mod n。（4）計算u1=e*w mod n；u2=r*w mod n。（5）計算X=u1G+u2Q。（6）如果X=O，表示簽名無效；否則，X=(x1，y1)，計算v=x1 mod n。（7）如果v=r，表示簽名無效；否則表示簽名有效。[10]ECDSA在安全性方面的目標是能抵抗選擇明文（密文）攻擊。而攻擊A的攻擊者的目標是在截獲A的簽名后，可以生成對任何消息的合法簽名。盡管ECDSA的理論模型很堅固，但是人們仍研究很多措施以提高ECDSA的安全性。在ECDLP不可破解及哈希函數(shù)足夠強的前提下，DSA和ECDSA的一些變形已被證明可以抵抗現(xiàn)有的任何選擇明文（密文）攻擊。在橢圓曲線所在群是一般群并且哈希函數(shù)能夠抗碰撞攻擊的前提下，ECDSA本身的安全性已經得到證明。ECDSA可能面臨的攻擊：。ECDMA的優(yōu)點（1）安全性能高（2）計算機量小和計算機速度快（3）存儲空間占有量?。?）帶寬要求低。5 RSA算法及其數(shù)字簽名 RSA簡述RSA加密體制是一種公開的密碼體制。由于RSA算法很完善，即可用于數(shù)據加密，又可用于數(shù)字簽名，安全性良好，易于實現(xiàn)和理解，所以已經成為一種應用極廣的公匙密碼算法，目前，RSA在許多場合有廣泛的應用。RSA 公鑰密碼算法是迄今為止在理論上最為成熟、完善的公鑰密碼體制。 從提出到現(xiàn)在已經歷了各種攻擊的考驗，逐漸為人們接受，普遍認為是目前最優(yōu)秀的公鑰方案之一。它是第一個既能用于數(shù)據加密也能用于數(shù)字簽名和密鑰分配與管理的算法。它易于理解和操作，也很流行。因為它既可用于加密,又可用于簽名,并為用戶的公開密鑰簽發(fā)公鑰證書、發(fā)放證書、管理證書等,提高了服務質量，所以, RSA 公開密鑰密碼在當今的信息交換過程中已得到廣泛的應用和實踐，RSA 公鑰密碼體制在世界許多地方已經成為事實上的標準。該算法的加密密鑰和加密算法分開,使得密鑰分配更為方便。而且它特別符合計算機網絡環(huán)境。對于網上的大量用戶,可以將加密密鑰用電話簿的方式印出。如果某用戶想與另一用戶進行保密通信,只需從公鑰簿上查出對方的加密密鑰,用它對所傳送的信息加密發(fā)出即可。對方收到信息后,用僅為自己所知的解密密鑰將信息解密,了解明文的內容。[11]由此可看出,RSA 算法解決了大量網絡用戶密鑰管理的難題,這是公鑰密碼系統(tǒng)相對于對稱密碼系統(tǒng)最突出的優(yōu)點。RSA 是一個基于數(shù)論的非對稱密碼體制,是一種分組密碼體制，是一種基于因子分解的指數(shù)函數(shù)作為單向陷門函數(shù)的公鑰體制算法。它基礎是數(shù)論的歐拉定理,素數(shù)檢測,它的安全性是基于大數(shù)分解,后者在數(shù)學上是一個困難問題。 RSA 的安全性基于復雜性理論中的計算安全性, 依賴于大整數(shù)分解這一NP 難題。可靠性與所用密鑰的長度有很大關系, 假如有人找到一種很快的分解因子的算法, 即從一個公鑰中通過因數(shù)分解得到私鑰, 那么用RSA 加密的信息的可靠性肯定會極度下降。但由于其工作量巨大,按目前計算機的處理能力是不可能實現(xiàn)的。實踐證明,在當前的技術和方法下,密鑰不小于1 024 bit的RSA算法仍然是安全的。這充分說明RSA 系統(tǒng)具有良好的保密性能。因此,盡管先后出現(xiàn)了很多新的公鑰體制算法,但RSA仍然在不同應用領域占據了重要的位置。隨著計算機運算速度的提高以及因子分解算法的突破, RSA 的密鑰長度將越來越大, 其軟硬件實現(xiàn)速度將成為制約其使用的重要因素。 RSA加密的可行性雖然RSA加密運算的速度十分慢,但是在PC性能越來越好的今天,對于幾千字節(jié)的數(shù)據進行一次幾百位密鑰的RSA加密,所消耗的時間應該是可以接受的?下面結合大數(shù)運算程序的調試,從理論上簡單的分析消耗時間?在一臺普通配置的PC機上對一個整數(shù)進行冪模運算,因為公開密鑰的e通常取的較小,所以指數(shù)取一個小整數(shù),比如C353,模一個70字節(jié)長的整數(shù)(140位十六進制,大數(shù)單元以線性組方式實現(xiàn),對應到RSA算法中,這相當于約560bit的n),調試一個函數(shù)測試,按初等數(shù)論中的知識對程序進行算法優(yōu)化,最終在一臺配置為AMD Athron2800+,外頻333MHZ,物理內存512MB的PC上測試需要約45毫秒時間?如果按這種速度,逐字節(jié)對1KB的數(shù)據進行同樣的運算,所消耗的時間理論上為45毫秒的1024倍即約45秒?這個時間并不是非常長[12]?其實從一個簡單的角度來說,既然RSA用于數(shù)字簽名可行,那就完全可以用于同樣大小的普通文件?對于較大的文件,如果分成與數(shù)字簽名同樣大小的段(這里假設數(shù)字簽名較短,不分段一次計算加密完成),分開的各段逐一進行加密運算,那所需要的時間也只是按文件大小線性的增長?通常數(shù)字簽名為幾十字節(jié),加密運算并不需要很長的等待,這就說明對于幾百字節(jié)或一兩K字節(jié)大小的文件來說,如果進行RSA加密,并不會是非常漫長的工作?當然,如果文件更大,加密就顯得十分漫長了?比如按前面敘述的45毫秒大數(shù)運算程序推理,加密1M字節(jié)大小的文件需要約1天的時間?所以,要在普通PC用幾百位以上的長密鑰RSA加密文件,文件不能過大,一般可以接受的上限是幾KB?如果要在較短時間內加密大文件,需要縮短密鑰長度以減小運算量,這將帶來安全性隱患?[13] RSA算法的介紹 RSA系統(tǒng)由以下幾部分組成：（1）隨機選取的在素數(shù)P和Q，還有N ，其中N=P*Q ，P和Q保密，N公開。（2）任取Φ(n)=（P1）*(Q1)，其中 (n)表示比n小的素數(shù)的個數(shù)，任取2=e= (n),且(e, (n))=1,e為加密密鑰，公開。（3）計算d,使e*d=1(mod (n)),稱d為e對模 (n)的逆，其中d為解密秘鑰，保密。在RSA系統(tǒng)中，設m為明文，且明文塊的數(shù)值大于n,c為密文，則其加密和解密算法如為：加密算法 C=E(m)=m^e(mod n) 解密算法 m=D(c)=c^d(mod n) 在RSA系統(tǒng)中(e,n)構成加密秘鑰，即公鑰，(d,n) 構成解密秘鑰，即私鑰。 RSA中素數(shù)的選取在RSA中，因N=P*Q， 若P，Q被知道，即能將N因子分解，則由 Φ(n)=（P1）*(Q1)可以算出。由于e是公開密鑰，且解密秘鑰D關于E滿足 D*E=1 (mod Φ(n))則D也不難求得，這樣RSA系統(tǒng)便被完全攻破。 RSA中的素數(shù)都是上面位的十進制數(shù)，怎樣才能選擇好的P和Q，怎樣才能生成這樣的數(shù)，并且判斷它是否為素數(shù)，這是一個RSA系統(tǒng)關鍵的問題。針對素數(shù)P和Q的選擇，1978年Rivest等人在正式發(fā)表的RSA公開密鑰的論文中，就建議對素數(shù)P和Q的選擇應當滿足：（1）P、Q要足夠在，在長度上應相差幾位，且二者之差與P、Q位數(shù)相近；（2）P1與Q1的最大公約數(shù)GCD(P1,Q1)就盡量小；（3）P1與Q1均應至少含有一個大的素數(shù)因子。并把滿足這些條件的素數(shù)稱為安全素數(shù)。 RSA用到的公式和定理（1）數(shù)和互為素數(shù) 任何大于1的整數(shù)a能被因式分解為如下唯一形式： a=p1p2…pl(p1,p2,…,pl為素數(shù)) （2）模運算 ①{[a(modn)][b(mod n)]}modn≡(ab)(mod n) ②如果（ab）=（ac）(mod n),a與n互素，則 b=c(mod n) （3）費馬定理 若p是素數(shù)，a與p互素，則a ^(p1)=1 mod p （4）歐拉定理 歐拉函數(shù)φ(n)表示不大于n且與n互素的正整數(shù)的個數(shù)。當n是素數(shù), φ(n)=n1。n=p*q,p,q均為素數(shù)時,則φ(n)=φ(n)φ(n)=(p1)(q1)。 對于互素的a和n,有a^φ(n)=1(mod n) RSA安全性的分析在公布RSA算法之后，在使用RSA密碼體制和分析RSA算法發(fā)現(xiàn)了一系列的算法本身脆弱性及其存在的問題。 （1）RSA公鑰密碼體制在加密或解密中涉及大量的數(shù)值計算，其加密和解密的運算時間比較長，以致于實際使用RSA密碼體制無法應用到軟件產品，必須用超大規(guī)模集成電路的硬件產品。 （2）雖然提高N位數(shù)會大大提高RSA密碼體制的安全性，但其計算量呈指數(shù)增長，以致使其實現(xiàn)的難度增大，實用性降低。 （3）RSA公鑰密碼體制的算法完整性（指密鑰控制加密或解密變換的唯一性）和安全性（指密碼算法除密鑰本身外，不應該存在其它可破譯密碼體制的可能性）沿有等進一步完善。（4）RSA算法面臨著數(shù)學方法的進步和計算機技術飛躍發(fā)展帶來的破譯密碼能力日趨增強的嚴重挑戰(zhàn)。RSA公開密鑰密碼算法在信息交換過程中使用比較廣泛，安全性比較高。以當前的計算機水平，如選擇1024位長的密鑰（相當于300位十進制數(shù)字）就認為是無法攻破的。 RSA的攻擊RSA算法的安全性就是基于大整數(shù)的因子分解困難之上的，到目前其還是安全的，要分析RSA算法的安全性，我們從攻擊RSA的角度來審視。總的來分，RSA算法攻擊可以區(qū)分為三類：（1）蠻力攻擊：它通過實驗所用的可能私鑰，來達到目的。（2）數(shù)字攻擊：使用數(shù)學技巧，類似于分解N來達到目的。（3）時間攻擊：通過觀察解密算法運行的時間來達到目的。其中抵抗蠻力攻擊的方法，與其它加密系統(tǒng)是一致的，使用大的密鑰空間，是窮舉無能無力，因此E和D的位數(shù)越長則越安全，但是加解密速度會越慢，所以E和d位數(shù)的長度應與實際應用系統(tǒng)有綜合的權衡。（1）RSA的選擇密文攻擊RSA在選擇密文攻擊面前很脆弱。所謂密碼分析者并不知道解密的密鑰，但是給出任意的消息，密碼分析者可以將其加密，再解密。或者說，密碼分析者能獲得解密服務。設攻擊者為A，密文接受者為T，公鑰對為（e,n）,私鑰為d,T收到的密文為c，c對應的明文為m。現(xiàn)在A想知道m(xù) = c^d mod n，但是