外文文献及翻译 HASH算法

1、广东工业大学本科毕业设计（论文）外文参考文献译文及原文计算机与艺术设计学部信息工程2006 级班级名称06本信息工程3班学生姓名 指导教师2010年4月25日目录HASH算法通用hash算法 Hash算法难度.HASH FUNCTIONSCOMMONLY USED HASH FUNCTIONS . D IFFICULTIES WITH HASH FUNCTIONS79Hash 算法哈希算法（ Hash functions ）是密码学主要的一部分。这是我们加密人员与泛滥的 破解技术抗争的主力，我们知道他们最不喜欢就是密码图形。一个 hash 算法提供了可变长度的输入字符串和固定长度的结果。输入的

2、很简便就是“hash”的意思，这个词不是人名的缩写。你可以用hash来输入数据，固定长度的字符串允许我们使用 hash 值来引用实际字符串本身。因为hash算法使用长的字符串，再变成一个短的。不可避免有2个字符串通过hash 算法会得出一样的结果，这个在密码学中叫“碰撞”。举个你可以明白hash值的例子， 假如Jon Callas和Jane Cannoy他们名字的hash值都是JC。碰撞是了解hash算法很重要的部分，我们将会在比特（ bit ）的单位上有更多的介绍。尽管缩写是一个很简单描述原文的方式，缩写造成了密码学目的的 hash 算法的错 误。密码学的 hash 算法。有很多用在加密技术

3、中的属性。很难逆向运算 hash 算法。据 hash 知识，没有一个好的办法找到 hash 值对应的那个 字符串。我们已经知道了 hash 算法会丢失数据，创造了一个简单的相对性。这个相同 的性质也是名字缩写的：除了 JC没其它的信息，不能找出我的名字，是Jon Callas ?是Jane Cannoy? 还是？一个 hash 值，它应该很难确定一个本来的字符串。这个性质是缩写遗漏（ initials lack ）。看缩写的时候如果知道名字的匹配是很简单的。在密码学中，我们想找出源信 息和这个结果之间的联系，他们之间的关系是尽可能不透明的。确定一个源字符串，我们根据这个字符串的 hash 值很

4、难找出第二个字符串。很难有 效的改变字符串获得一个碰撞。 也很难改变“我同意支付 100 美元”到“我同意支付 500美元”而获得碰撞。注意这 2 个字符串之间只有 1 位不同。也很难找出碰撞的2个字符串的hash值。这个算法在很多不同的事情上给了我们灵 活的想法，这里有一些例子： 当你在PGP软件中输入密码的时候，我们使用 hash算法来生成一个密钥。中间的过 程就是 hash 算法，通常一遍遍的使用来降低破解者的暴力破解的风险。 PGP软件的随机数生成器在传入数据后，会根据你键盘和鼠标的移动时时更新。这样使得观察者不确定这个值，也没有不变的随机数字。我们使用hash算法消除观察者的数据中的

5、不均匀性。随机数生成器使用hash算法产生输出值。这个过程 PGP软件也做了。文件完整性算法，使用hash算法可以很快的检查文件。比如：你可以保留文件的hash列表在你的电脑上。hash数据库中的值也变了，你就看到计算机内的文件变化了。 软件分布系统站点通常有分布的复杂密码系统使用hash算法创建数据完整性作为它的一个系统组件，我们稍后会了 解这个。注意几乎所有算法现在都在被广泛使用，这有一个假设它们不会发生碰撞。如果2个密钥发生了 hash碰撞，任何一个密钥都可以解密文件。如果2个软件包有相同的hash值时，一个肯定被误认为是另外一个。通用Hash算法表格1列出了一些hash算法的共同点，特

6、别是PGP使用的。表格1：通用Hash算法名称大小(Bits)描述MD5128MD5是 hash系列算法中的最低标准，PGP软件在PGP5.0版本以前使用。MD5的脆弱性在1996年第一次出现。MD5是MD4的改进，PGP软件不再使用它的原因是它是第一个被破解的通用hash算法SHA-1160SHA-1是MD5的改进，由NIST设计，解决MD5的问题后被广泛使用。RIP E-MD/160160RIPE-MD/160是一个和SHA-1差不多的Hash算法。设计 RIPE-MD/160为了改善超过 MD5 它被 ReseauxIPEurop 国ns(RIPE)组织设计，而不是美国 NIST我们认为

7、它的 安全性和SHA-1差不多。SHA-256256SHA-256是美国NIST最新设计的新Hash算法。也属于“SH-2”的类型，它有和其它不同的内部结构，但和其 它hash算法的基本结构都是一样的。SHA-512512512这是“ SH-2”算法的一种，和 SHA-256差不多。SHA-384384SHA-384有比SHA-512更小的输出。一般不常用SHA-384 是因为除了大小以外没有任何优势，如果我们需要比SHA-256强度高的算法，我们会直接选 SHA-512同样SHA-224是 SHA-256缩小版。Hash算法难度目前（2006年中期），我们知道了 hash算法系列在使用上并不

8、是很完美，他们中的一些确实不完善。这个问题到 2004年的夏天变的明朗了，中国山东大学王小云教授宣布她和她的团队在一些 hash算法中发现碰撞。这时 RSA名字中的“ S”的这个人AdiSHA-1。Shamir说，“上星期，我还认为hash算法是我们认为最好的部件。现在则认为它是我们 的部件中是最差的。”在2005年初，王小云的攻击延伸到了第一次幸免的我们仍然在应对这个问题。他们中的所有都绕着hash碰撞，2个字符串生成了一样的hash值。一个数学的分支：组合数学（comb in atorics ）中的一个叫归档原理(Pigeon hole Principled）的公理。最简单的归档原理的解释

9、是：如果你有13个鸽子而只有12个笼子，至少有一个里面装有2个鸽子。很显然的，不是吗？那就是为什么这是公理的原因！还有一大堆一样如果你应用这个公理到hash算法，考虑16-bit的hash计算。再考虑整个16-bit 的字符。依照归档原理，至少有2个字符串会有一样的hash。事实上，（这对hash算至少 1个hash的例子。这个碰撞和鸽子汇集问题是一样的。如果这个碰撞是均匀分布的法来说也正确），一个hash值那会有256个碰撞，然后根据归档原理,有至少有256个碰撞。找出一个碰撞应该和猜一样容易， 但是有多难呢？回答这个问题又引发另外一个有趣的数学问题叫生日问题。在谈论区块大小的时候我们谈到过

10、的。和Alice有相同生日的人的概率是1/365。但是如果你有一房子满满的人，和另外一个人生日发生碰撞的概 率有多大？特别的，有多少人机率均等也就是房间中有2个人的生日是一样的呢？这个问题的一般回答和找出hash碰撞的是一样的。我们认为生日是比另外一个名字缩写问题更好的hash问题，但远远不完美。尽管如此，生日是一个公平的任意分布的b。对于生日来说，原来生日c碰撞的机率是大约23个人中的偶数。通常，机率是偶数的大约是选项数字的平方根。我确定你注意到我使用了一个很含糊的词“大约”。这是因为答案不是准确，只是接近平方根。大概的说，碰撞的机率是：holes!Pro（pjge。nsmes）亠而R站Fl

11、hok15其中，Prob是机率的意思，只表示函数名，pigeons是鸽子，holes是笼子洞。Pigeons 和holes都是输入变量的名字。省下你的数学运算。如果你解决了鸽子数目的问题，结果的机率是一个洞的2个鸽子里面每一个都有-的概率。可以算出约为1.2X Jholes，对于我们使用的那个问题来说，我2这样去推测们也可以认为等于Vhoies 0特别是当我们去处理一个非常大的数字的时候,很方便，这个方法也是理论数学中被惯用的手法。n所以，如果我们有一个n-bit的hash算法，如果我们有2个字符串的碰撞的机率相等。也就是说，160-bit的hash运算只有80-bit的安全性。280是很大的

12、一个数字。大约2倍的阿伏伽德罗常数。阿伏伽德罗常数 d是摩尔体积的分子数，或者用一个方便的东西 表示，就是一汤勺水中水分子的数目。那是个很大的数。王小云带着报告参加了 2004年密码界峰会，她震撼了密码界。她没有用一张纸来展示如何碰撞，她仅仅只用了他们 中的一部分。就像你看到的，因为碰撞很难发现。仅仅有128-bit的hash算法中的一部分中有碰撞，也就意味着碰撞已经出现了。对于密码分析学家的主要问题是“她知道 我们不能够做什么？” 6和月以后，她的技术扩展到攻击质数的 160-bit的hash算法。这就是我们在最后2年所总结的: 王小云是最优秀的密码分析专家。她有着其它数学家没有的基础数学洞

13、察力；她非常 迅速的成为世界上为数不多的、最优秀的 hash算法密码分析专家。 一些其它的理论工作不是去进行应用实际，而是更多的思考。有很多议案关于如何修改剩下的算法来抵抗王小云的攻击。他们都非常棒，但是一个 明显的问题是，“明年有什么攻击，这个修正可以解决吗？ ”当然，这个问题是不能回 答的。我们不可能反对未知的攻击来保护我们的算法。无论如何，其中的很多议案确实是解决的好办法。一个简单的技术诸如当进行hash运算时使用每双字节（用AABBC来 代替ABC,或者插入0比特在每4个字节后面，或者添加随机数据在准备 hash运算的数据之前，用这些办法解决了已知的问题。我们开始考虑一个如何设计一个好

14、的 hash算法的想法。在2005年10月，NIST主持了一个关于 hash 算法的工作组。 密码专家开始考虑想出一个如何设计一个好的 hash 算 法的想法。第2个工作组在2006年8月开始计划。同样也有像 AES相似的竞争方式来产生一个新的 hash 算法。工程师的观点中也有一些好的想法。在 PGF团队中，我们已经发扬了首创精神。在PGPffl队，我们开始转移MD5到1997年的水平。PGP5.0开始从MD5向SHA-1发展, 保持MD5勺唯一目的是为了向后兼容性。PGP8.0.3介绍了这个技术支持，也可以在阅读 中找到，但是没有SHA-256 SHA-384和 SHA-512的算法。PG

15、P9.0开始从SHA-1向SHA-256发展。Hash FunctionsHash functions are an important part of cryptography. They are the workhorses that wecryptographers use and abuse for all sorts of things, and yet we understand them least of allthe cryptographic primitives.Youcsaninriteiafelsr.to theA hash function takes a varia

16、ble-length input string and createsa fixed-length output.That “ hasohf”the input is a shortcut, not unlike a personinput string by its hash. The fact that it is a fixed-length string allows us to easily use thehash value as a referrer to the actual string itself.Because a hash function takes a long

17、string and reduces it to a short one, it is inevitablethat there will be two strings that hash to the same value, or collide in cryptographer-speak.ll talk moFor example, the names Jon Callas and Jane Cannoy collide with initials to the hash of JC.Collisions are important in the understanding of has

18、h functions, and wethem in a bit.Although initials are an easy way to describe the basic concept, initials make a bad hashfunction for cryptographic purposes. A cryptographic hash function has a number of otherproperties that make it useful cryptographically.? It should be hard to reverse a hash fun

19、ction. Knowing the h,atshere 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 to get to my na

20、me.?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 and a result to

21、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 esp ecially hard to cha nge a stri ng usefully and get a collisi on.In an extremecase, it should be hard to change“I agree to pay $100” to “I a$500” and have that c

22、ollide. Note that the differenee between the two strings is only a sin gle bit.?It should also be hard to find two stri ngs that collide in their hash values. These requireme nts give us very flexible fun cti ons that are used for lots of differe nt things.Here are some exa mp les: ? Random number g

23、eneratorsthemselvesoften use hash functions to produce their out put. The one in PGP software does.?File in tegrity systems use hash functions as quick checks on the fileFor exa mple.you can kee p a list of the hashes of the files on your compu ter, and you can see if that file has cha nged by compa

24、ring the hash of the file on disk to the one in the database.Software distributio n sites also ofte n 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.? Comp lex cryp togra phic systems that create data in tegrity u

25、se hash fun cti ons as a component.we lltalk more about them later. Note that for almost all of these uses, there as assumption that there won be collisions. If two passphrasescollide in their hash, either can decry pt a file. If two software p ackages hash to the same value, then one can be mistake

26、 n for the other.Commonly Used Hash FunctionsNameSizeDescri pti onMD5128biMD5 was the sole hash fun ctio n that PGP softwaretsprior to PGP 5.0. Weak nesses in MD5 ?rst showedTable 1 lists some common ly used hash functions, esp ecially the ones we p rese ntlyuse in PGP software.usedupSHA-1160bitsSHA

27、-1 app earedn PGP 5.0, and also in OpenPGPSHA-1 is an impro veme nt on MD5 that was createdbyNIST to be wider and also to correct p roblems in MD5.RIPE-MD/16160bitsRIP E-MD/160 is a hash fun ctio n similar to SHA-1.RIP E-MD/160 was created to be an imp roveme nt o、/erMD5. However, it was created by

28、the Euro pearReseaux IP Europe nai!(RI PE) orga ni zati on rather tha nthe US NIST. We expect it has similar securitycharacteristics to SHA-1.SHA-256256bitsSHA-256 is one of a new family of hashes created bythe US NIST that are collectively called theA-2”“SHfamily. It has di?ere nt in ternal structu

29、re,but comesfrom the same basic con struct ionas the other hashfun cti ons in this table.SHA-512SHA-384512bits384bitsThis is another member of the-2” “amHly, alonwith SHA-256SHA-384 is a varia nt of SHA-512 that has a smallerout pu t. I n gen eral, SHA-384 is not used, because ithasin 1996. MD5 is i

30、tself an imp roveme nt on MD4, which was n ever used in PGP software and was the ?rst com mon hash fun cti on to be fully broke n.ze. Itno adva ntages over SHA-512 exce pt for the hash s runs at the same sp eecbs SHA-512, so usually if we n eed somethi ng stron ger tha n SHA-256, we go directly to S

31、HA-512. There is also a SHA-224 which is a similar trun cation of SHA-256.Table1 Com mon ly Used Hash FunctionsDifficulties with Hash FunctionsPresently (mid-2006), we know the suite of hash functions we have been using is notperfect, and some of them are quite imperfect. These problems came to ligh

32、t in the summerof 2004 when Xiaoyung Wang announcedthat she and her team produced collisions in aS” in the RSA algorithm, said at the time, “Last weetkh,oIught that hash functions were the component we understood best. Now Inumber of hash functions W ANG04 . Adi Shamir, thesee that they are the comp

33、onent wuenderstand least. In ”early 2005, Xiaoyungs attacks wereextended to SHA-1, which had survived her first workWANG05.We are still coping with these problems, all of which revolve around hash functioncollisions, two strings producing the same hash value. One of the axioms of the branch ofmathem

34、atics called combinatorics is called the Pigeonhole Principle. At its simplest, thePigeonhole Principle states that if you have thirteen pigeons and only twelve pigeonholes, thenat least one hole must contain at least two pigeons. Pretty obvious, isnt it? Thataxiom.If you apply this principle to has

35、h functions, consider sixteen-byte hashes. Also considerthe entire set of seventeen-byte strings. According to the Pigeonhole Principle, there are going tobe 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

36、 are the equivalent of pigeons lumpingthemselves together. If the collisions are evenly distributed (and thus the hash functionperfect), then there will be 256 collisions per hash value, and according to the PigeonholePrinciple, there has to be at least one hash with at least 256 collisions.Finding

37、a collision ought to be no better than guessing, but how hard is that?Answering thatquestion raises another interesting mathematical problem called The Birthday Problem, whichwe first saw when talking about block sizes. The probability that a given person has the same 11birthday as Alice is about 1/

38、365 . But if you have a room full of people, what is the chancethat there will be a collisio n on their birthday? Sp ecifically, with how many people are there eve n odds that there will be two people in the room who share the same birthday?The gen eral case an swer to this questi on is the same as

39、finding collisi ons in a hash fun cti on.We can think of a birthday as yet ano ther hash fun cti on with p erha ps better prop erties tha n12 in itials, but still no where n ear p erfect. Non etheless, birthdays are fairly ran domly distributedFor birthdays, it turns out that the odds of a birthday

40、collisi on are eve n at about 23 peop le. In the gen eral case, the odds are eve n at about the square root of the nu mber of op ti ons.I m suryou noticed my use of the wease-word “ about. This is because the answerisn t exactly the square root, but close to it. In the general case, the chanee of co

41、llisions isholes!pro(pigeonsmes)亠(hoR药nSo, if we have an n-bit hash fun cti on, there are eve n odds of a collisio n whe n we have2stri ngs we ve hashed. Thus, we say that a 160hash function should have 80 bits of security.802 is a very large number. It about twice Avogadro sNumber, which is the num

42、ber of molecules in a mole, or to put it in convenient terms, the nu mber of molecules in a roun dedtables poon of water. Itnunabbig When Wang came to Cryp to 2004 with WANG04in hand, it shook cryptographers up. She didn have a paper that showed how to create collisi ons, she merely had a lot of the

43、m. As you can see, because collisi ons are supp osed to be hard to find, merely possessinga handful of collisions on each of a handful of 128-bit hash“ What doesfunctions mea ns that someth ing is up. For cryp togra phers, thea in questi on was, she know that we don SiX”months later, her techniques

44、werextended to attack the prime 160-bit hash fun ctio n.Here is a summary of what we ve learnast twthyears:? Wang is an excelle nt cryptan alyst. She does nt have any fun dame ntal mathematical insithat other mathematicia ns dont have; she s merely the world s best hash function cleaps and bounds.?

45、Some other theoretical work that wasn t 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 in106 160 602 work instead of 2 but you nee

46、d to have messages 2long to be able to do so. Before Wang showed flaws in how we were doing things, this was interesting but not practicaNl.ow some of us wonder if this impractical flaw is an indication of a structural problem. We don t knowye, t.? There are a number of proposals on how to modify ex

47、isting functions towithstand Wang sWhat new attack willattacks. They re all very good, but the obvious f-oollnowquestion is,happen next year, that this fix doesn tOafccournstef,otrh?is qu”estion is unanswerable.We just can t protect against unknown attacks. However, a number of these proposed solutions are practical to implement. Simple techniques like doubling every byte as you hash (instead of hashing ABC, hash AABBCC) or inserting a zero byte after every f