加密算法及實現

作者:fnlq 資料來源: http://www.encrypter.net/article/encrypt0005.htm 【聲明】 一．本文實用於初學者，目的在於幫助大家熟悉一些系統底層的知識。 二．本文只是為了讓廣大網友共同提高一些基礎知識，本人決無賣弄之意，只供需要這方面知識的讀者閱讀，如果你是高手，或者不需要這方面知識，請跳過。 三．本文是一篇翻譯文章，如有雷同，敬請諒解。 四．本文歡迎傳抄轉載，但是不要用於任何商業用途。請尊重作者勞動，也歡迎來信交流 fnlq@263.net ======================================================================= 【正文】 公開密鑰算法 隱秘密鑰算法 塊密碼模式 密文暗碼函數 隨機數字發生器 公開密鑰算法 公開密鑰算法使用不同的密鑰進行加密和解密運算，並且解密密鑰不能從加密密鑰變換獲得。公開密鑰算法通常都非常慢，因此公開密鑰算法很多時候被應用到加密一組由其他途徑產生的密鑰，並通過公眾網路進行傳送，然後接受方用私鑰解密後，在以後的對稱算法裡應用此傳送過來的密鑰。 RSA(Rivest-Shamir-Adelman)是使用最多的公開密鑰算法，能夠被應用在加密和數字簽名中。大家普遍接受當足夠長的密鑰被使用後，RSA是足夠安全的(512比特是不安全的，768比特是中等安全的，1024比特足夠保障一般的安全傳輸。) RSA的安全依賴於大整數因數分解的難度。因數分解的快速發展將導致RSA出現問題。不過，目前RSA是這個世界上最重要的公開密鑰算法。RSA的專利權將在今年失效(2000年)，並且將可以被自由使用。 Bruce Schneier有專門的論文討論使用RSA密鑰推薦的長度，按現狀而言，512比特是不足夠的，1024比特可以被認為是很安全的，如果使用2048比特，應該可以保障今後十年的安全。值得一提的是，RSA對於Chosen Plaintext attack非常脆弱，並且新近發展的Timing Attack能夠用來破解很多RSA的具體實現。如果對RSA進行正確的應用，可以締造一個很安全的系統，但是一定要注意避免上述這兩類攻擊。 很多RSA的實現可以被自由獲取，例如 PGP，SSH。 Diffie-hellman 是一個被普遍應用在密鑰交換的公開密鑰算法。當採用了足夠長度的密鑰和合適的發生因子時候，這個加密算法很安全。Diffie-hellman算法依賴於離散對數的困難度（這和大整數分解因數一樣，都非常困難）。 Diffie-hellman的專利權保護已經在1997年4月29日過期。 Diffie-hellman 算法對於強的素數和發生因子非常敏感，在Photuris草案裡推薦了一對可行的素數/發生因子。同樣，隱秘的指數的大小也對此算法的安全性非常重要。保守的建議生成長度是已建立的會話密鑰長度兩倍的隨機指數。 橢圓曲線公開密鑰密碼系統是逐漸浮出水面。這個方法非常緩慢，但是隨著計算機的發展，逐漸成為可行。他們被認為很安全，但是尚沒有經過類似RSA經歷過的詳細審查。 可以參考 IEEE P1363關於橢圓曲線密碼系統和相關模式的標準草案 DSS (Digital Signature Standard) 美國政府認可了一種只用於簽名的機制，它的設計想請並沒有被公布，但是很多人已經發覺其中很多潛在的問題(例如洩漏簽名中的隱藏數據，還有如果簽署兩個不同的消息採用同一個隨機數，將會洩漏隱秘密鑰)，美國政府已經對其進行了專利保護，使用這一算法將需要花費25美元以上給美國政府。幾乎沒有理由採用DSS，因為有更多更好的方法可以取代這一算法。 ElGamal公開密鑰密碼系統 LUC 是另一個公開密鑰的加密系統。 隱秘密鑰算法 （對稱密碼體制，又稱單鑰加密體制） DES (US Federal Data Encryption Standard) DES是最著名的採用對稱密碼體制的算法，作為美國政府的數據加密標準，其被應用到非常廣汎的範圍中。 IDEA (International Data Encryption Algorithm) 這是在瑞士蘇黎世開發的一種算法，這個算法被認為非常安全。這是目前世界上最好的公開的加密算法，這也是一種比較新的算法，在已經使用過的這些年裡，沒有關於這種算法的弱點的報告，盡管有無數人對其進行了分析和攻擊。 IDEA在美國和大多數歐洲國家得到專利保護。專利的持有者是Ascom-Tech，非商業性的IDEA的使用是免費的。要獲得IDEA的商業使用許可請和idea@ascom.ch 聯系 很多IDEA的實現可以被自由得獲得。例如 PGP SSH idea86 等 RC4 是RSA數據安全公司開發的一種密碼算法。它過去一直是商業機密，直到某個人在Usenet的新聞組貼了一個源代碼，聲稱等價於RC4算法。很明顯的是，這個被貼出的源代碼確實等價於RC4。這個算法非常快，但是破解這個算法也並不是非常簡單。因為其得快捷，很多應用都使用了這個算法。RC4本質上是一個偽隨機數生成器，並且生成算法的輸出與數據流進行異或運算。因此，非常重要的是，絕對不應當對兩個不同的數據流採用同一個RC4密鑰進行加密。 RC4算法可以從這裡獲得。 美國政府宣布40位密鑰RC4的應用可用於出口，如此短的密鑰可以被軍事情報、科研院所和業餘團體輕易破解。曾經有報道採用RC4-40的Netscape SSL被兩個獨立組織在幾天內破解。 SAFER 是J.L.Massey(同時也是IDEA的研究者之一)發明的一種算法。關於描述這種算法的論文已經公開，這種算法提供安全而又快捷的軟件實現甚至可以在8位處理器上實現。概算法目前有兩個變種，一個是64bits密鑰的算法，另一個是128位的密鑰算法。 暗碼變換的密碼函數 任何強加密的暗碼生成算法都可以轉換成密碼。有幾種可能採用的方式，通常的辦法是暗碼生成結果作為一個隨機數生成器，並且把生成的暗碼與數據進行異或運算加密。當所有的暗碼的字節都被使用以後，一個新的暗碼通過修改密鑰來獲得，並且重新進行暗碼計算。進行暗碼運算的數據必須還要包括一個密鑰，如前一次的暗碼，一個序列號，或者一個明文字符串等。 Enigma 這是德軍在二戰中使用的密碼系統，用現代的計算機可以輕而易舉地對付它。現代的應用不應該採用這類算法。類似的還有Vigenere等。 分塊加密模式 大多數經常使用的密碼算法(如DES,IDEA ,BlowFish)都是分塊加密的。這是指他們都採用一個固定長度的數據塊──通常是64比特──並且通過密鑰選擇移動到另一個64位的塊中。 如果同樣的塊通過同樣的密鑰進行加密，那麼結果的加密文本也將是相同的。這個加密模式被稱為ECB 電子代碼書。 這個信息對攻擊這很有用。 暗碼加密函數 MD5 (Message Digest Algorithm 5)是RSA數據安全公司開發的一種安全暗碼算法。可以用來把不同長度的數據塊進行暗碼運算成一個128位的數值。 MD5被廣汎使用，並且可以被認為是很安全。不過已經有能夠破解MD5的報道，據稱，一個價值幾百萬美元的計算機系統可以在幾周內尋找出已被暗碼處理的原文。 MD2 MD4都是舊的加密算法，現在不應該繼續使用了。其中Windows NT由於採用MD4，因此L0phtcrack等工具可以進行比較快地破解。 SHA (Secure Hash Algorithm) 這是一個美國政府公布的暗碼生成算法，可以對任意長度的數據運算生成一個160位的數值，很多人認為這個比較新的算法是一個好的算法。 fnlq 時間就是金錢---[ 發問前請先找找舊文章]

RSA算法

作者:fnlq 參考網頁:http://www.encrypter.net/article/encrypt0003.htm 【聲明】 一．本文實用於初學者，目的在於幫助大家熟悉一些系統底層的知識。 二．本文只是為了讓廣大網友共同提高一些基礎知識，本人決無賣弄之意，只供需要這方面知識的讀者閱讀，如果你是高手，或者不需要這方面知識，請跳過。 三．本文是一篇翻譯文章，如有雷同，敬請諒解。 四．本文歡迎傳抄轉載，但是不要用於任何商業用途。請尊重作者勞動，也歡迎來信交流 fnlq@263.net ======================================================================= 【正文】 最近大家經常在網路上討論security的問題有一個地方講起來非常頭大,就是網路竊聽的問題因為現今大部分的資料傳遞是使用明碼,所以,有心人只要組一台PC上網,就可以竊聽到許許多多有用的資訊,即使機器的su密碼也不能幸免所以,人們就想在資料上做加密解密的工作.在網路上所傳輸的都是經過加密之後資料,來防止第三者竊聽 其實,對資料作加密解密的工作並不困難,只要會寫程式的人就可以想出許許多多千奇百怪的方法.但問題是,如果這個演算法一但外流了,那這個方法就破功了.所傳的碼頓時之間成為明碼.所以,在一般公用的service,如telnet,ftp等,作者不可能使用自定的演算法作加密解密的工作. 現今,大家最常用的方法是DES演算法DES是一個公開的演算法,但它在加密解密的過程中需要一個key.解碼時如果key不對,那還是沒效.所以,只要key不要外流,即使傳輸過程中有人竊聽,也不怕資料曝光.但DES有個問題,因為加密解密需用同一個key,所以在傳輸時,要如何使雙方都使用同一個key?這個問題實在很頭大,因為如果不靠其它方法,比如你自己到對方耳邊親口告訴他,或是寄一封掛號信給對方等等.單靠網路的話,這個key是無法不被第三者所知.所以,像KERBEROS這類的安全系統(它也是使用DES演算法),就必須作一些人工設定(也就是有些動作不能透過網路設定)有個演算法,RSA,可以解決上述的問題它的做法大概如下:假設資料要由A機器傳至B機器,那,由B機器用亂數決定一個key,我們稱之為privatekey,這個key自始至終都只留在B機器裡不送出來然後,由這個privatekey計算出另一個key,我們稱之為publickey.這個publickey的特性是幾乎不可能反演算出privatekey來然後將這個publickey透過網路丟給A機器.A機器將資料用這個publickey編碼,這個編碼過的資料一定得使用privatekey才解得開然後A機器將編碼過的資料透過網路傳給B,B再用privatekey將資料解碼這時,如果有第三者竊聽資料時,他只得到B傳給A的publickey,以及A用這個publickey編碼後的資料沒有privatekey,第三者根本無法解碼所以這個方法確實能防止第三者的竊聽 它是第一個既能用於數據加密也能用於數字簽名的算法。它易於理解和操作，也很流行。算法的名字以發明者的名字命名：Ron Rivest, Adi Shamir 和Leonard Adleman。但RSA的安全性一直未能得到理論上的證明。它經歷了各種攻擊，至今未被完全攻破。 RSA的安全性依賴於大數分解。公鑰和私鑰都是兩個大素數（ 大於 100 個十進制位）的函數。據猜測，從一個密鑰和密文推斷出明文的難度等同於分解兩個大素數的積。 密鑰對的產生。選擇兩個大素數，p 和q 。計算： n = p * q 然後隨機選擇加密密鑰e，要求 e 和 ( p - 1 ) * ( q - 1 ) 互質。最後，利用 Euclid 算法計算解密密鑰d,滿足 e * d = 1 ( mod ( p - 1 ) * ( q - 1 ) ) 其中n和d也要互質。數e和 n是公鑰，d是私鑰。兩個素數p和q不再需要，應該丟棄，不要讓任何人知道。 加密信息 m（二進制表示）時，首先把m分成等長數據塊 m1 ,m2,..., mi ，塊長s ，其中 <= n, s 盡可能的 大。對應的密文是： ci = mi^e ( mod n ) ( a ) 解密時作如下計算： mi =ci^d ( mod n ) ( b ) RSA 可用於數字簽名，方案是用 ( a ) 式簽名， ( b )式驗證。具體操作時考慮到安全性和 m信息量較大等因素，一般是先作 HASH 運算。 RSA 的安全性。 RSA的安全性依賴於大數分解，但是否等同於大數分解一直未能得到理論上的證明，因為沒有證明破解 RSA就一定需要作大數分解。假設存在一種無須分解大數的算法，那它肯定可以修改成為大數分解算法。目前， RSA 的一些變種算法已被證明等價於大數分解。不管怎樣，分解n是最顯然的攻擊方法。現在，人們已能分解多個十進制位的大素數。因此，模數n 必須選大一些，因具體適用情況而定。 RSA的速度。 由於進行的都是大數計算，使得RSA最快的情況也比DES慢上倍，無論是軟件還是硬件實現。速度一直是RSA的缺陷。一般來說只用於少量數據加密。 RSA的選擇密文攻擊。 RSA在選擇密文攻擊面前很脆弱。一般攻擊者是將某一信息作一下偽裝( Blind)，讓擁 有私鑰的實體簽署。然後，經過計算就可得到它所想要的信息。實際上，攻擊利用的都是同一個弱點，即存在這樣一個事實：乘冪保留了輸入的乘法結構： ( XM )^d = X^d *M^d mod n 前面已經提到，這個固有的問題來自於公鑰密碼系統的最有用的特征--每個人都能使用公鑰。但從算法上無法解決這一問題，主要措施有兩條：一條是採用好的公鑰協議，保證工作過程中實體不對其他實體任意產生的信息解密，不對自己一無所知的信息簽名﹔另一條是決不對陌生人送來的隨機文檔簽名，簽名時首先使用One-Way HashFunction 對文檔作HASH處理，或同時使用不同的簽名算法。在中提到了幾種不同類型的攻擊方法。 RSA的公共模數攻擊。 若系統中共有一個模數，只是不同的人擁有不同的e和d，系統將是危險的。最普遍的情況是同一信息用不同的公鑰加密，這些公鑰共模而且互質，那末該信息無需私鑰就可得到恢復。設P為信息明文，兩個加密密鑰為e1和e2，公共模數是n，則： C1 = P^e1 mod n C2 = P^e2 mod n 密碼分析者知道n、e1、e2、C1和C2，就能得到P。 因為e1和e2互質，故用Euclidean算法能找到r和s，滿足： r * e1 s * e2 = 1 假設r為負數，需再用Euclidean算法計算C1^(-1)，則 ( C1^(-1) )^(-r) * C2^s = P mod n 另外，還有其它幾種利用公共模數攻擊的方法。總之，如果知道給定模數的一對e和d，一是有利於攻擊者分解模數，一是有利於攻擊者計算出其它成對的e’和d’，而無需分解模數。解決辦法只有一個，那就是不要共享模數n。 RSA的小指數攻擊。 有一種提高 RSA速度的建議是使公鑰e取較小的值，這樣會使加密變得易於實現，速度有所提高。但這樣作是不安全的，對付辦法就是e和d都取較大的值。 RSA算法是第一個能同時用於加密和數字簽名的算法，也易於理解和操作。RSA是被研究得最廣汎的公鑰算法，從提出到現在已近二十年，經歷了各種攻擊的考驗，逐漸為人們接受，普遍認為是目前最優秀的公鑰方案之一。RSA的安全性依賴於大數的因子分解，但並沒有從理論上證明破譯RSA的難度與大數分解難度等價。即RSA的重大缺陷是無法從理論上把握它的保密性能如何，而且密碼學界多數人士傾向於因子分解不是NPC問題。 RSA的缺點主要有：A)產生密鑰很麻煩，受到素數產生技術的限制，因而難以做到一次一密。B)分組長度太大，為保證安全性，n 至少也要 600 bits 以上，使運算代價很高，尤其是速度較慢，較對稱密碼算法慢幾個數量級﹔且隨著大數分解技術的發展，這個長度還在增加，不利於數據格式的標準化。目前，SET( Secure Electronic Transaction )協議中要求CA採用比特長的密鑰，其他實體使用比特的密鑰。 首先,找出三個數,其中p,q是兩個相異的質數,r是與(p-1)(q-1)互質的數這三個數便是privatekey 接著,找出m,使得rm==1mod(p-1)(q-1)這個m一定存在,因為r與(p-1)(q-1)互質,用輾轉相除法就可以得到了再來,計算n=pqm,n這兩個數便是publickey編碼過程是,若資料為a,將其看成是一個大整數,假設a=n的話,就將a表成s進位(s<=n,通常取s=2^t),則每一位數均小於n,然後分段編碼接下來,計算b==a^mmodn,(0<=b<證明> 因為rm==1mod(p-1)(q-1),所以rm=k(p-1)(q-1) 1,其中k是整數,因為在modulo中是preserve乘法的x==ymodzandu==vmodz=>xu==yvmodz), 所以,c==b^r==(a^m)^r==a^(rm)==a^(k(p-1)(q-1) 1)modpq 1.如果a不是p的倍數,也不是q的倍數時,則a^(p-1)==1modp(費馬小定理)=>a^(k(p-1)(q-1))==1modp,a^(q-1)==1modq(費馬小定理)=>a^(k(p-1)(q-1))==1modq 所以p,q均能整除a^(k(p-1)(q-1))-1=>pq|a^(k(p-1)(q-1))-1,即a^(k(p-1)(q-1))==1modpq =>c==a^(k(p-1)(q-1) 1)==amodpq 2.如果a是p的倍數,但不是q的倍數時,則a^(q-1)==1modq(費馬小定理) =>a^(k(p-1)(q-1))==1modq=>c==a^(k(p-1)(q-1) 1)==amodq=>q|c-a 因p|a =>c==a^(k(p-1)(q-1) 1)==0modp =>p|c-a所以,pq|c-a=>c==amodpq 3.如果a是q的倍數,但不是p的倍數時,證明同上 4.如果a同時是p和q的倍數時,則pq|a=>c==a^(k(p-1)(q-1) 1)==0modpq>pq|c-a =>c==amodpq Q.E.D. 這個定理說明a經過編碼為b再經過解碼為c時,a==cmodn(n=pq).... 但我們在做編碼解碼時,限制0<=a 時間就是金錢---[ 發問前請先找找舊文章]