畢業(yè)論文有關(guān)HASH算法的外文文獻(xiàn)

1、廣東工業(yè)大學(xué)本科畢業(yè)設(shè)計(jì)（論文）外文參考文獻(xiàn)譯文及原文系 部計(jì)算機(jī)與藝術(shù)設(shè)計(jì)學(xué)部專 業(yè)信息工程年 級(jí)2006級(jí)班級(jí)名稱 06本信息工程3班學(xué) 號(hào)學(xué)生姓名指導(dǎo)教師2010年4月25日目錄 TOC o 1-5 h z HASH算法1通用Hash算法2Hash算法難度3 HYPERLINK l bookmark12 o Current Document HASH FUNCTIONS6 HYPERLINK l bookmark22 o Current Document commonly Used Hash Functions 7 HYPERLINK l bookmark25 o Current Doc

2、ument Difficulties withHash Functions 9Hash算法哈希算法(Hash functions)是密碼學(xué)主要的一部分。這是我們加密人員與泛濫的 破解技術(shù)抗?fàn)幍闹髁?，我們知道他們最不喜歡就是密碼圖形。一個(gè)hash算法提供了可變長(zhǎng)度的輸入字符串和固定長(zhǎng)度的結(jié)果。輸入的很簡(jiǎn)便就 是“hash”的意思，這個(gè)詞不是人名的縮寫。你可以用hash來(lái)輸入數(shù)據(jù)，固定長(zhǎng)度的 字符串允許我們使用hash值來(lái)引用實(shí)際字符串本身。因?yàn)閔ash算法使用長(zhǎng)的字符串，再變成一個(gè)短的。不可避免有2個(gè)字符串通過hash 算法會(huì)得出一樣的結(jié)果，這個(gè)在密碼學(xué)中叫“碰撞”。舉個(gè)你可以明白hash值的例

3、子， 假如Jon Callas和Jane Cannoy他們名字的hash值都是JC。碰撞是了解hash算法很 重要的部分，我們將會(huì)在比特(bit)的單位上有更多的介紹。盡管縮寫是一個(gè)很簡(jiǎn)單描述原文的方式，縮寫造成了密碼學(xué)目的的hash算法的錯(cuò) 誤。密碼學(xué)的hash算法。有很多用在加密技術(shù)中的屬性。很難逆向運(yùn)算hash算法。據(jù)hash知識(shí)，沒有一個(gè)好的辦法找到hash值對(duì)應(yīng)的那個(gè) 字符串。我們已經(jīng)知道了 hash算法會(huì)丟失數(shù)據(jù)，創(chuàng)造了一個(gè)簡(jiǎn)單的相對(duì)性。這個(gè)相同 的性質(zhì)也是名字縮寫的：除了 JC沒其它的信息，不能找出我的名字，是JonCallas？是 Jane Cannoy ？ 還是？一個(gè)hash

4、值，它應(yīng)該很難確定一個(gè)本來(lái)的字符串。這個(gè)性質(zhì)是縮寫遺漏(initials lack)?？纯s寫的時(shí)候如果知道名字的匹配是很簡(jiǎn)單的。在密碼學(xué)中，我們想找出源信 息和這個(gè)結(jié)果之間的聯(lián)系，他們之間的關(guān)系是盡可能不透明的。確定一個(gè)源字符串，我們根據(jù)這個(gè)字符串的hash值很難找出第二個(gè)字符串。很難有 效的改變字符串獲得一個(gè)碰撞。也很難改變“我同意支付100美元”到“我同意支付500 美元”而獲得碰撞。注意這2個(gè)字符串之間只有1位不同。也很難找出碰撞的2個(gè)字符串的hash值。這個(gè)算法在很多不同的事情上給了我們靈 活的想法，這里有一些例子：當(dāng)你在PGP軟件中輸入密碼的時(shí)候，我們使用hash算法來(lái)生成一個(gè)密鑰。

5、中間的過 程就是hash算法，通常一遍遍的使用來(lái)降低破解者的暴力破解的風(fēng)險(xiǎn)。PGP軟件的隨機(jī)數(shù)生成器在傳入數(shù)據(jù)后，會(huì)根據(jù)你鍵盤和鼠標(biāo)的移動(dòng)時(shí)時(shí)更新。這樣 使得觀察者不確定這個(gè)值，也沒有不變的隨機(jī)數(shù)字。我們使用hash算法消除觀察者的 數(shù)據(jù)中的不均勻性。隨機(jī)數(shù)生成器使用hash算法產(chǎn)生輸出值。這個(gè)過程PGP軟件也做了。文件完整性算法，使用hash算法可以很快的檢查文件。比如：你可以保留文件的hash 列表在你的電腦上。hash數(shù)據(jù)庫(kù)中的值也變了，你就看到計(jì)算機(jī)內(nèi)的文件變化了。軟件 分布系統(tǒng)站點(diǎn)通常有分布的復(fù)雜密碼系統(tǒng)使用hash算法創(chuàng)建數(shù)據(jù)完整性作為它的一個(gè)系統(tǒng)組件，我們稍后會(huì)了 解這個(gè)。注意幾

6、乎所有算法現(xiàn)在都在被廣泛使用，這有一個(gè)假設(shè)它們不會(huì)發(fā)生碰撞。如 果2個(gè)密鑰發(fā)生了 hash碰撞，任何一個(gè)密鑰都可以解密文件。如果2個(gè)軟件包有相同 的hash值時(shí)，一個(gè)肯定被誤認(rèn)為是另外一個(gè)。通用Hash算法表格1列出了一些hash算法的共同點(diǎn)，特別是PGP使用的。表格1：通用Hash算法名稱大小(Bits)描述MD5128MD5是hash系列算法中的最低標(biāo)準(zhǔn)，PGP軟件在PGP5.0 版本以前使用MD5的脆弱性在1996年第一次出現(xiàn)MD5 是MD4的改進(jìn)，PGP軟件小冉使用它的原因是它是第一 個(gè)被破解的通用hash算法SHA-1160SHA-1是MD5的改進(jìn)，由NIST設(shè)計(jì)，解決MD5的問題后

7、 被廣泛使用。RIPE-MD/160160RIPE-MD/160是一個(gè)和SHA-1差不多的Hash算法。設(shè)計(jì) RIPE-MD/160 為了改善超過 MD5。它被 Reseaux IPEurop eens(RIPE)組織設(shè)計(jì)，而小是美國(guó)NIST我們認(rèn)為它的 安全性和SHA-1差不多。SHA-256256SHA-256是美國(guó)NIST最新設(shè)計(jì)的新Hash算法。也屬于 “SH-2”的類型，它有和其它不同的內(nèi)部結(jié)構(gòu)，但和其 它hash算法的基本結(jié)構(gòu)都是一樣的。SHA-512512512這是“SH-2”算法的一種，和SHA-256差不多。SHA-384384SHA-384有比SHA-512更小的輸出。一般

8、不常用SHA-384 是因?yàn)槌舜笮∫酝鉀]有任何優(yōu)勢(shì)，如果我們需要比 SHA-256強(qiáng)度高的算法，我們會(huì)直接選SHA-512。同樣 SHA-224 是 SHA-256 縮小版。Hash算法難度目前(2006年中期),我們知道了 hash算法系列在使用上并不是很完美，他們中的 一些確實(shí)不完善。這個(gè)問題到2004年的夏天變的明朗了，中國(guó)山東大學(xué)王小云教授宣 布她和她的團(tuán)隊(duì)在一些hash算法中發(fā)現(xiàn)碰撞。這時(shí)RSA名字中的“S”的這個(gè)人Adi Shamir說，“上星期，我還認(rèn)為hash算法是我們認(rèn)為最好的部件?，F(xiàn)在則認(rèn)為它是我們 的部件中是最差的。”在2005年初，王小云的攻擊延伸到了第一次幸免的SH

9、A-1。我們?nèi)匀辉趹?yīng)對(duì)這個(gè)問題。他們中的所有都繞著hash碰撞，2個(gè)字符串生成了一 樣的hash值。一個(gè)數(shù)學(xué)的分支：組合數(shù)學(xué)(combinatorics)中的一個(gè)叫歸檔原理 (Pigeonhole Principled)的公理。最簡(jiǎn)單的歸檔原理的解釋是：如果你有13個(gè)鴿子而只有12個(gè)籠子，至少 有一個(gè)里面裝有2個(gè)鴿子。很顯然的，不是嗎？那就是為什么這是公理的原因！如果你應(yīng)用這個(gè)公理到hash算法，考慮16-bit的hash計(jì)算。再考慮整個(gè)16-bit 的字符。依照歸檔原理，至少有2個(gè)字符串會(huì)有一樣的hash。事實(shí)上，還有一大堆一樣 的例子。這個(gè)碰撞和鴿子匯集問題是一樣的。如果這個(gè)碰撞是均勻分布

10、的(這對(duì)hash算 法來(lái)說也正確)，一個(gè)hash值那會(huì)有256個(gè)碰撞，然后根據(jù)歸檔原理，至少1個(gè)hash 有至少有256個(gè)碰撞。找出一個(gè)碰撞應(yīng)該和猜一樣容易，但是有多難呢？回答這個(gè)問題又引發(fā)另外一個(gè)有 趣的數(shù)學(xué)問題叫生日問題。在談?wù)搮^(qū)塊大小的時(shí)候我們談到過的。和Alice有相同生日 的人的概率是1/365。但是如果你有一房子滿滿的人，和另外一個(gè)人生日發(fā)生碰撞的概 率有多大？特別的，有多少人機(jī)率均等也就是房間中有2個(gè)人的生日是一樣的呢？這個(gè)問題的一般回答和找出hash碰撞的是一樣的。我們認(rèn)為生日是比另外一個(gè)名 字縮寫問題更好的hash問題，但遠(yuǎn)遠(yuǎn)不完美。盡管如此，生日是一個(gè)公平的任意分布 的b。

11、對(duì)于生日來(lái)說，原來(lái)生日c碰撞的機(jī)率是大約23個(gè)人中的偶數(shù)。通常，機(jī)率是偶數(shù)的大約是選項(xiàng)數(shù)字的平方根。我確定你注意到我使用了一個(gè)很含糊的詞“大約”。這是因?yàn)榇鸢覆皇菧?zhǔn)確，只是 接近平方根。大概的說，碰撞的機(jī)率是：pro( pigeons, holes) = 1 -holes!(holes - pigeons )!* holes pigeons其中，Prob是機(jī)率的意思，只表示函數(shù)名，pigeons是鴿子，holes是籠子洞。Pigeons 和holes都是輸入變量的名字。省下你的數(shù)學(xué)運(yùn)算。如果你解決了鴿子數(shù)目的問題，結(jié)果的機(jī)率是一個(gè)洞的2個(gè)鴿子里 面每一個(gè)都有1的概率?？梢运愠黾s為1.2whol

12、es，對(duì)于我們使用的那個(gè)問題來(lái)說，我2們也可以認(rèn)為等于寸k。特別是當(dāng)我們?nèi)ヌ幚硪粋€(gè)非常大的數(shù)字的時(shí)候，這樣去推測(cè) 很方便，這個(gè)方法也是理論數(shù)學(xué)中被慣用的手法。n所以，如果我們有一個(gè)n-bit的hash算法，如果我們有22個(gè)字符串的碰撞的機(jī)率相等。 也就是說，160-bit的hash運(yùn)算只有80-bit的安全性。280是很大的一個(gè)數(shù)字。大約2 倍的阿伏伽德羅常數(shù)。阿伏伽德羅常數(shù)d是摩爾體積的分子數(shù)，或者用一個(gè)方便的東西 表示，就是一湯勺水中水分子的數(shù)目。那是個(gè)很大的數(shù)。王小云 帶著報(bào)告參加了 2004 年密碼界峰會(huì)，她震撼了密碼界。她沒有用一張紙來(lái)展示如何碰撞，她僅僅只用了他們 中的一部分。就像

13、你看到的，因?yàn)榕鲎埠茈y發(fā)現(xiàn)。僅僅有128-bit的hash算法中的一 部分中有碰撞，也就意味著碰撞已經(jīng)出現(xiàn)了。對(duì)于密碼分析學(xué)家的主要問題是“她知道 我們不能夠做什么？”6和月以后，她的技術(shù)擴(kuò)展到攻擊質(zhì)數(shù)的160-bit的hash算法。 這就是我們?cè)谧詈?年所總結(jié)的：王小云是最優(yōu)秀的密碼分析專家。她有著其它數(shù)學(xué)家沒有的基礎(chǔ)數(shù)學(xué)洞察力；她非常 迅速的成為世界上為數(shù)不多的、最優(yōu)秀的hash算法密碼分析專家。一些其它的理論工作不是去進(jìn)行應(yīng)用實(shí)際，而是更多的思考。有很多議案關(guān)于如何修改剩下的算法來(lái)抵抗王小云的攻擊。他們都非常棒，但是一個(gè) 明顯的問題是，“明年有什么攻擊，這個(gè)修正可以解決嗎？ ”當(dāng)然，這個(gè)

14、問題是不能回 答的。我們不可能反對(duì)未知的攻擊來(lái)保護(hù)我們的算法。無(wú)論如何，其中的很多議案確實(shí) 是解決的好辦法。一個(gè)簡(jiǎn)單的技術(shù)諸如當(dāng)進(jìn)行hash運(yùn)算時(shí)使用每雙字節(jié)（用AABBCC來(lái) 代替ABC），或者插入0比特在每4個(gè)字節(jié)后面，或者添加隨機(jī)數(shù)據(jù)在準(zhǔn)備hash運(yùn)算的 數(shù)據(jù)之前，用這些辦法解決了已知的問題。我們開始考慮一個(gè)如何設(shè)計(jì)一個(gè)好的hash算法的想法。在2005年10月，NIST主持 了一個(gè)關(guān)于hash算法的工作組。密碼專家開始考慮想出一個(gè)如何設(shè)計(jì)一個(gè)好的hash算 法的想法。第2個(gè)工作組在2006年8月開始計(jì)劃。同樣也有像AES相似的競(jìng)爭(zhēng)方式來(lái) 產(chǎn)生一個(gè)新的hash算法。工程師的觀點(diǎn)中也有一些

15、好的想法。在PGP團(tuán)隊(duì)中，我們已經(jīng)發(fā)揚(yáng)了首創(chuàng)精神。在PGP團(tuán)隊(duì)，我們開始轉(zhuǎn)移MD5到1997年的水平。PGP5.0開始從MD5向SHA-1發(fā)展， 保持MD5的唯一目的是為了向后兼容性。PGP8.0.3介紹了這個(gè)技術(shù)支持，也可以在閱讀 中找到，但是沒有SHA-256、SHA-384和SHA-512的算法PGP9.0開始從SHA-1向SHA-256 發(fā)展。Hash FunctionsHash functions are an important part of cryptography. They are the workhorses that we cryptographers use and

16、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 fixed-length output. That hash” of the input is a shortcut, not unlike a persons initials. You can refer to the input string by its h

17、ash. 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 string 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 crypto

18、grapher-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 functions, 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

19、function for cryptographic purposes. A cryptographic hash function has a number of other properties that make it useful cryptographically.It should be hard to reverse a hash function. Knowing the hh there should be no good way to find the input string that generated it. Given that (typically) hash f

20、unctions 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 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 i

21、s 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 and 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 s

22、hould 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 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 stri

23、ngs 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:Random number generators themselves often use hash functions to produce their output. The one in PGP software does.File integrity systems use ha

24、sh 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 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 distr

25、ibuted 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 integrity 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 w

26、ont 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 be mistaken for the other.Commonly Used Hash FunctionsNameSizeDescriptionMD5128biMD5 was the sole hash function that PGP software utsprior to PGP 5.0.

27、 Weaknesses in MD5 first showed uTable 1 lists some commonly used hash functions, especially the ones we presentlyuse in PGP software.3in 1996. MD5 is itself an improvement on MD4, whi was never used in PGP software and was the first common hash function to be fully broken.chSHA-1160bitsSHA-1 appear

28、ed in PGP 5.0, and also in OpenPGP.SHA-1 is an improvement on MD5 that was created b NIST to be wider and also to correct problems in MD)y5.RIPE-MD/160160bitsRIPE-MD/160is a hash function similar to SHA-1. RIPE-MD/160 was created to be an improvement ove MD5. However, it was created by the European

29、Reseaux IP Europdens (RIPE) organization rather than the US NIST. We expect it has similar security characteristics to SHA-1.jriSHA-256256bitsSHA-256 is one of a new family of hashes created by the US NIST that are collectively called the SIA-2” family. It has di erent internal structure, but comes

30、from the same basic construction as the other hash functions in this table.SHA-512512bitsThis is another member of the SHA2” family, alongwith SHA-256SHA-384384bitsSHA-384is a variant of SHA-512that has a smaller output. In general, SHA-384 is not used, because it h no advantages over SHA-512 except

31、 for the hash size runs at the same speed as SHA-512, so usually if we need something stronger than SHA-256, we go direct to SHA-512. There is also a SHA-224 which is a sim truncation of SHA-256.as.ItlyilarTablet Commonly Used Hash FunctionsDifficulties with Hash FunctionsPresently (mid-2006), we kn

32、ow the suite of hash functions we have been using is not perfect, and some of them are quite imperfect. These problems came to light in 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 algori

33、thm, said at the time, “Last week, I thought that hash functions were the component we understood best. Now I see that they are the component we understand least. In early 2005, Xiaoyungs attacks were extended to SHA-1, which had survived her first workWANG05.We are still coping with these problems,

34、 all of which revolve around hash function collisions, two strings producing the same hash value. One of the axioms of the branch 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

35、 pigeonholes, then at least one hole must contain at least two pigeons. Pretty obvious, isnt it? Thafs why its an axiom.If you apply this principle to hash functions, consider sixteen-byte hashes. Also consider the entire set of seventeen-byte strings. According to the Pigeonhole Principle, there ar

36、e 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 whole lot of them.The collisions are the equivalent of pigeons lumpingthemselves together. If the collisions are evenly distributed (and thus the hash function perfect), then

37、there will be 256 collisions per hash value, and according to the Pigeonhole Principle, there has to be at least one hash with at least 256 collisions.Finding a collision ought to be no better than guessing, but how hard is that? Answering thatquestion raises another interesting mathematical problem

38、 called The Birthday Problem, which we first saw when talking about block sizes. The probability that a given person has the same birthday as Alice is about 1/365 11. But if you have a room full of people, what is the chancethat there will be a collision on their birthday? Specifically, with how man

39、y people are there even odds that there will be two people in the room who share the same birthday?The general case answer 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

40、still nowhere near perfect. Nonetheless, birthdays are fairly randomly distribute12. For birthdays, it turns out that the 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 t

41、he weasel-word “about.” This is because the answer isnt exactly the square root, but close to it. In the general case, the chance of collisions ispro( pigeons, holes) = 1 -holes!(holes - pigeons )!* holes pigeonsnSo, if we have an n-bit hash function, there are even odds of a collision when we have

42、2 2 strings weve hashed. Thus, we say that a 160-bit hash function should have 80 bits of security. 280 is a very large number. Its about 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. If

43、s 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 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 e

44、ach of a handful of 128-bit hash functions means that something is up. For cryptographers, the main question was, “What does she know 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 thlast two years:Wan

45、g is an excellent cryptanalyst. She doesnt have any fundamental mathematical insights that other mathematicians dont have; shes merely the worlds best hash function cryptanalyst by leaps and bounds.Some other theoretical wor k that wasnt particularly practical is getting a lot of thought.For example

46、, 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 260 but you need to have messages6。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 impractical f