畢業(yè)論文 - 有關HASH算法的外文文獻

1、_大學本科畢業(yè)設計（論文）本科畢業(yè)設計（論文）外文參考文獻譯文及原文系 部 計算機與藝術設計學部 專 業(yè) 信息工程 年 級 2006 級 班級名稱 06 本信息工程 3 班 學 號 學生姓名 指導教師 2010 年 4 月 25 日目錄目錄HASHHASH 算法算法.1通用 HASH算法.2HASH算法難度.3HASH FUNCTIONS.6COMMONLY USED HASH FUNCTIONS.7DIFFICULTIES WITH HASH FUNCTIONS.9HashHash 算法算法哈希算法（Hash functions）是密碼學主要的一部分。這是我們加密人員與泛濫的破解技術抗爭的主

2、力，我們知道他們最不喜歡就是密碼圖形。一個 hash 算法提供了可變長度的輸入字符串和固定長度的結果。輸入的很簡便就是“hash”的意思，這個詞不是人名的縮寫。你可以用 hash 來輸入數據，固定長度的字符串允許我們使用 hash 值來引用實際字符串本身。因為 hash 算法使用長的字符串，再變成一個短的。不可避免有 2 個字符串通過hash 算法會得出一樣的結果，這個在密碼學中叫“碰撞” 。舉個你可以明白 hash 值的例子，假如 Jon Callas 和 Jane Cannoy 他們名字的 hash 值都是 JC。碰撞是了解 hash算法很重要的部分，我們將會在比特（bit）的單位上有更多

3、的介紹。盡管縮寫是一個很簡單描述原文的方式，縮寫造成了密碼學目的的 hash 算法的錯誤。密碼學的 hash 算法。有很多用在加密技術中的屬性。很難逆向運算 hash 算法。據 hash 知識，沒有一個好的辦法找到 hash 值對應的那個字符串。我們已經知道了 hash 算法會丟失數據，創(chuàng)造了一個簡單的相對性。這個相同的性質也是名字縮寫的：除了 JC 沒其它的信息，不能找出我的名字，是 JonCallas？是 Jane Cannoy？還是？一個 hash 值，它應該很難確定一個本來的字符串。這個性質是縮寫遺漏（initials lack） ?？纯s寫的時候如果知道名字的匹配是很簡單的。在密碼學中

4、，我們想找出源信息和這個結果之間的聯(lián)系，他們之間的關系是盡可能不透明的。確定一個源字符串，我們根據這個字符串的 hash 值很難找出第二個字符串。很難有效的改變字符串獲得一個碰撞。也很難改變“我同意支付 100 美元”到“我同意支付500 美元”而獲得碰撞。注意這 2 個字符串之間只有 1 位不同。也很難找出碰撞的 2 個字符串的 hash 值。這個算法在很多不同的事情上給了我們靈活的想法，這里有一些例子：當你在 PGP 軟件中輸入密碼的時候，我們使用 hash 算法來生成一個密鑰。中間的過程就是 hash 算法，通常一遍遍的使用來降低破解者的暴力破解的風險。PGP 軟件的隨機數生成器在傳入數

5、據后，會根據你鍵盤和鼠標的移動時時更新。這樣使得觀察者不確定這個值，也沒有不變的隨機數字。我們使用 hash 算法消除觀察者的數據中的不均勻性。隨機數生成器使用 hash 算法產生輸出值。這個過程 PGP 軟件也做了。文件完整性算法，使用 hash 算法可以很快的檢查文件。比如：你可以保留文件的hash 列表在你的電腦上。hash 數據庫中的值也變了，你就看到計算機內的文件變化了。軟件分布系統(tǒng)站點通常有分布的復雜密碼系統(tǒng)使用 hash 算法創(chuàng)建數據完整性作為它的一個系統(tǒng)組件，我們稍后會了解這個。注意幾乎所有算法現在都在被廣泛使用，這有一個假設它們不會發(fā)生碰撞。如果 2 個密鑰發(fā)生了 hash

6、碰撞，任何一個密鑰都可以解密文件。如果 2 個軟件包有相同的 hash 值時，一個肯定被誤認為是另外一個。通用通用 HashHash 算法算法表格 1 列出了一些 hash 算法的共同點，特別是 PGP 使用的。表格 1：通用 Hash 算法名稱大?。˙its）描述MD5128MD5 是 hash 系列算法中的最低標準，PGP 軟件在PGP5.0 版本以前使用。MD5 的脆弱性在 1996 年第一次出現。MD5 是 MD4 的改進，PGP 軟件不再使用它的原因是它是第一個被破解的通用 hash 算法SHA-1160SHA-1 是 MD5 的改進，由 NIST 設計，解決 MD5 的問題后被廣泛

7、使用。RIPE-MD/160160RIPE-MD/160 是一個和 SHA-1 差不多的 Hash 算法。設計 RIPE-MD/160 為了改善超過 MD5。它被 Reseaux IPEuropens(RIPE)組織設計，而不是美國 NIST 我們認為它的安全性和 SHA-1 差不多。SHA-256256SHA-256 是美國 NIST 最新設計的新 Hash 算法。也屬于“SH-2”的類型，它有和其它不同的內部結構，但和其它 hash 算法的基本結構都是一樣的。SHA-512512512 這是“SH-2”算法的一種，和 SHA-256 差不多。SHA-384384SHA-384 有比 SHA

8、-512 更小的輸出。一般不常用 SHA-384 是因為除了大小以外沒有任何優(yōu)勢，如果我們需要比 SHA-256 強度高的算法，我們會直接選 SHA-512。同樣 SHA-224 是 SHA-256 縮小版。HashHash 算法難度算法難度目前(2006 年中期)，我們知道了 hash 算法系列在使用上并不是很完美，他們中的一些確實不完善。這個問題到 2004 年的夏天變的明朗了，中國山東大學王小云教授宣布她和她的團隊在一些 hash 算法中發(fā)現碰撞。這時 RSA 名字中的“S”的這個人 Adi Shamir 說， “上星期，我還認為 hash 算法是我們認為最好的部件。現在則認為它是我們的

9、部件中是最差的。 ”在 2005 年初，王小云的攻擊延伸到了第一次幸免的 SHA-1。我們仍然在應對這個問題。他們中的所有都繞著 hash 碰撞，2 個字符串生成了一樣的 hash 值。一個數學的分支：組合數學（combinatorics）中的一個叫歸檔原理（Pigeonhole Principled）的公理。最簡單的歸檔原理的解釋是：如果你有 13 個鴿子而只有 12 個籠子，至少有一個里面裝有 2 個鴿子。很顯然的，不是嗎？那就是為什么這是公理的原因！如果你應用這個公理到 hash 算法，考慮 16-bit 的 hash 計算。再考慮整個 16-bit 的字符。依照歸檔原理，至少有 2 個

10、字符串會有一樣的 hash。事實上，還有一大堆一樣的例子。這個碰撞和鴿子匯集問題是一樣的。如果這個碰撞是均勻分布的(這對hash 算法來說也正確)，一個 hash 值那會有 256 個碰撞，然后根據歸檔原理，至少 1個 hash 有至少有 256 個碰撞。找出一個碰撞應該和猜一樣容易，但是有多難呢？回答這個問題又引發(fā)另外一個有趣的數學問題叫生日問題。在談論區(qū)塊大小的時候我們談到過的。和 Alice 有相同生日的人的概率是 1/365。但是如果你有一房子滿滿的人，和另外一個人生日發(fā)生碰撞的概率有多大？特別的，有多少人機率均等也就是房間中有 2 個人的生日是一樣的呢？這個問題的一般回答和找出 ha

11、sh 碰撞的是一樣的。我們認為生日是比另外一個名字縮寫問題更好的 hash 問題，但遠遠不完美。盡管如此，生日是一個公平的任意分布的 b。對于生日來說，原來生日 c 碰撞的機率是大約 23 個人中的偶數。通常，機率是偶數的大約是選項數字的平方根。我確定你注意到我使用了一個很含糊的詞“大約” 。這是因為答案不是準確，只是接近平方根。大概的說，碰撞的機率是:!(,)1()!*pigeonsholespro pigeons holesholespigeonsholes 其中，Prob 是機率的意思，只表示函數名，pigeons 是鴿子，holes 是籠子洞。Pigeons 和 holes 都是輸入變

12、量的名字。省下你的數學運算。如果你解決了鴿子數目的問題，結果的機率是一個洞的 2 個鴿子里面每一個都有的概率?？梢运愠黾s為，對于我們使用的那個問題來說，121.2holes我們也可以認為等于。特別是當我們去處理一個非常大的數字的時候，這樣去holes推測很方便，這個方法也是理論數學中被慣用的手法。所以，如果我們有一個 n-bit 的 hash 算法，如果我們有 個字符串的碰撞的機率相22n等。也就是說，160-bit 的 hash 運算只有 80-bit 的安全性。是很大的一個數字。802大約 2 倍的阿伏伽德羅常數。阿伏伽德羅常數 d 是摩爾體積的分子數，或者用一個方便的東西表示，就是一湯勺

13、水中水分子的數目。那是個很大的數。王小云 帶著報告參加了 2004 年密碼界峰會，她震撼了密碼界。她沒有用一張紙來展示如何碰撞，她僅僅只用了他們中的一部分。就像你看到的，因為碰撞很難發(fā)現。僅僅有 128-bit 的 hash算法中的一部分中有碰撞，也就意味著碰撞已經出現了。對于密碼分析學家的主要問題是“她知道我們不能夠做什么？”6 和月以后，她的技術擴展到攻擊質數的 160-bit的 hash 算法。這就是我們在最后 2 年所總結的：王小云是最優(yōu)秀的密碼分析專家。她有著其它數學家沒有的基礎數學洞察力；她非常迅速的成為世界上為數不多的、最優(yōu)秀的 hash 算法密碼分析專家。一些其它的理論工作不是

14、去進行應用實際，而是更多的思考。有很多議案關于如何修改剩下的算法來抵抗王小云的攻擊。他們都非常棒，但是一個明顯的問題是， “明年有什么攻擊，這個修正可以解決嗎？”當然，這個問題是不能回答的。我們不可能反對未知的攻擊來保護我們的算法。無論如何，其中的很多議案確實是解決的好辦法。一個簡單的技術諸如當進行 hash 運算時使用每雙字節(jié)(用AABBCC 來代替 ABC)，或者插入 0 比特在每 4 個字節(jié)后面，或者添加隨機數據在準備hash 運算的數據之前，用這些辦法解決了已知的問題。我們開始考慮一個如何設計一個好的 hash 算法的想法。在 2005 年 10 月，NIST 主持了一個關于 hash

15、 算法的工作組。密碼專家開始考慮想出一個如何設計一個好的 hash算法的想法。第 2 個工作組在 2006 年 8 月開始計劃。同樣也有像 AES 相似的競爭方式來產生一個新的 hash 算法。工程師的觀點中也有一些好的想法。在 PGP 團隊中，我們已經發(fā)揚了首創(chuàng)精神。在 PGP 團隊，我們開始轉移 MD5 到 1997 年的水平。PGP5.0 開始從 MD5 向 SHA-1 發(fā)展，保持 MD5 的唯一目的是為了向后兼容性。PGP8.0.3 介紹了這個技術支持，也可以在閱讀中找到，但是沒有 SHA-256、SHA-384 和 SHA-512 的算法。PGP9.0 開始從 SHA-1 向SHA-

16、256 發(fā)展。Hash Functions Hash functions are an important part of cryptography. They are the workhorses that we cryptographers use and abuse for all sorts of things, and yet we understand them least of all the cryptographic primitives. A hash function takes a variable-length input string and creates a f

17、ixed-length output. That “hash” of the input is a shortcut, not unlike a persons initials. You can refer to the input string by its hash. The fact that it is a fixed-length string allows us to easily use the hash value as a referrer to the actual string itself. Because a hash function takes a long s

18、tring and reduces it to a short one, it is inevitable that there will be two strings that hash to the same value, or collide in cryptographer-speak. For example, the names Jon Callas and Jane Cannoy collide with initials to the hash of JC. Collisions are important in the understanding of hash functi

19、ons, and well talk more about them in a bit. Although initials are an easy way to describe the basic concept, initials make a bad hash function for cryptographic purposes. A cryptographic hash function has a number of other properties that make it useful cryptographically. It should be hard to rever

20、se a hash function. Knowing the hash, there should be no good way to find the input string that generated it. Given that (typically) hash functions lose data, this is a relatively easy property to create. The same property is also true for initials: knowing JC and nothing else, there is no good way

21、to get to my name. Given a hash value, it should be hard to identify a possible source string. This property is one that initials lack. It is very easy to look at a set of initials and know if a name matches it. With a cryptographic hash function, however, we want the relationship between a source a

22、nd a result to be as opaque as possible. Given one source string, it should be hard to find a second string that collides with its hash. It should be especially hard to change a string usefully and get a collision. In an extreme case, it should be hard to change “I agree to pay $100” to “I agree to

23、pay $500” and have that collide. Note that the difference between the two strings is only a single bit. It should also be hard to find two strings that collide in their hash values. These requirements give us very flexible functions that are used for lots of different things. Here are some examples:

24、 Random number generators themselves often use hash functions to produce their output. The one in PGP software does. File integrity systems use hash functions as quick checks on the files. For example, you can keep a list of the hashes of the files on your computer, and you can see if that file has

25、changed by comparing the hash of the file on disk to the one in the database. Software distribution sites also often list the hash value of the distributed file so that people who want to see if they have the right file can compute and compare hashes. Complex cryptographic systems that create data i

26、ntegrity use hash functions as a component. Well talk more about them later. Note that for almost all of these uses, theres an assumption that there wont be collisions. If two passphrases collide in their hash, either can decrypt a file. If two software packages hash to the same value, then one can

27、be mistaken for the other. Commonly Used Hash Functions Table 1 lists some commonly used hash functions, especially the ones we presently use in PGP software. NameSize DescriptionMD5128biMD5 was the sole hash function that PGP software used tsprior to PGP 5.0. Weaknesses in MD5 first showed up in 19

28、96. MD5 is itself an improvement on MD4, which was never used in PGP software and was the first common hash function to be fully broken.SHA-1160bitsSHA-1 appeared in PGP 5.0, and also in OpenPGP. SHA-1 is an improvement on MD5 that was created by NIST to be wider and also to correct problems in MD5.

29、RIPE-MD/160160bitsRIPE-MD/160 is a hash function similar to SHA-1. RIPE-MD/160 was created to be an improvement over MD5. However, it was created by the European Rseaux IP Europens (RIPE) organization rather than the US NIST. We expect it has similar security characteristics to SHA-1.SHA-256256bitsS

30、HA-256 is one of a new family of hashes created by the US NIST that are collectively called the “SHA-2” family. It has different internal structure, but comes from the same basic construction as the other hash functions in this table.SHA-512512bitsThis is another member of the “SHA-2” family, along

31、with SHA-256SHA-384384bitsSHA-384 is a variant of SHA-512 that has a smaller output. In general, SHA-384 is not used, because it has no advantages over SHA-512 except for the hash size. It runs at the same speed as SHA-512, so usually if we need something stronger than SHA-256, we go directly to SHA

32、-512. There is also a SHA-224 which is a similar truncation of SHA-256.Table1 Commonly Used Hash FunctionsDifficulties with Hash Functions Presently (mid-2006), we know the suite of hash functions we have been using is not perfect, and some of them are quite imperfect. These problems came to light i

33、n the summer of 2004 when Xiaoyung Wang announced that she and her team produced collisions in a number of hash functions WANG04. Adi Shamir, the “S” in the RSA algorithm, said at the time, “Last week, I thought that hash functions were the component we understood best. Now I see that they are the c

34、omponent we understand least.” In early 2005, Xiaoyungs attacks were extended to SHA-1, which had survived her first work WANG05. We are still coping with these problems, all of which revolve around hash function collisions, two strings producing the same hash value. One of the axioms of the branch

35、of mathematics called combinatorics is called the Pigeonhole Principle. At its simplest, the Pigeonhole Principle states that if you have thirteen pigeons and only twelve pigeonholes, then at least one hole must contain at least two pigeons. Pretty obvious, isnt it? Thats why its an axiom. If you ap

36、ply this principle to hash functions, consider sixteen-byte hashes. Also consider the entire set of seventeen-byte strings. According to the Pigeonhole Principle, there are going to be at least two original strings that produce the same sixteen-byte hash. As a matter of fact, there have to be a whol

37、e lot of them. The collisions are the equivalent of pigeons lumping themselves together. If the collisions are evenly distributed (and thus the hash function perfect), then there will be 256 collisions per hash value, and according to the Pigeonhole Principle, there has to be at least one hash with

38、at least 256 collisions. Finding a collision ought to be no better than guessing, but how hard is that? Answering that question raises another interesting mathematical problem called The Birthday Problem, which we first saw when talking about block sizes. The probability that a given person has the

39、same birthday as Alice is about 1/365 11. But if you have a room full of people, what is the chance that there will be a collision on their birthday? Specifically, with how many people are there even odds that there will be two people in the room who share the same birthday? The general case answer

40、to this question is the same as finding collisions in a hash function. We can think of a birthday as yet another hash function with perhaps better properties than initials, but still nowhere near perfect. Nonetheless, birthdays are fairly randomly distributed12. For birthdays, it turns out that the

41、odds of a birthday collision are even at about 23 people. In the general case, the odds are even at about the square root of the number of options. Im sure you noticed my use of the weasel-word “about.” This is because the answer isnt exactly the square root, but close to it. In the general case, th

42、e chance of collisions is!(,)1()!*pigeonsholespro pigeons holesholespigeonsholes So, if we have an n-bit hash function, there are even odds of a collision when we have 22nstrings weve hashed. Thus, we say that a 160-bit hash function should have 80 bits of security. 280 is a very large number. Its a

43、bout twice Avogadros Number, which is the number of molecules in a mole, or to put it in convenient terms, the number of molecules in a rounded tablespoon of water. Its a big number. When Wang came to Crypto 2004 with WANG04 in hand, it shook cryptographers up. She didnt have a paper that showed how

44、 to create collisions, she merely had a lot of them. As you can see, because collisions are supposed to be hard to find, merely possessing a handful of collisions on each of a handful of 128-bit hash functions means that something is up. For cryptographers, the main question was, “What does she know

45、 that we dont?” Six months later, her techniques were extended to attack the prime 160-bit hash function. Here is a summary of what weve learned in the last two years: Wang is an excellent cryptanalyst. She doesnt have any fundamental mathematical insights that other mathematicians dont have; shes m

46、erely the worlds best hash function cryptanalyst by leaps and bounds. Some other theoretical work that wasnt particularly practical is getting a lot of thought. For example, a few months before WANG04, John Kelsey and Bruce Schneier showed in KSHASH04 that when looking for a SHA-1 collision of a given string, you could do it in 2106work instead of 2160 but you need to have messages 260 long to be able to do so. Before Wang showed flaws in how we were doing things, this was interesting but not practical. Now some of us wonder if this