外文翻译hash算法大学论文.docx

外文翻译hash算法大学论文.docx

《外文翻译hash算法大学论文.docx》由会员分享，可在线阅读，更多相关《外文翻译hash算法大学论文.docx（12页珍藏版）》请在冰点文库上搜索。

外文翻译hash算法大学论文

广东工业大学

本科毕业设计（论文）

外文参考文献译文及原文

系部计算机与艺术设计学部

专业信息工程

年级2006级

班级名称06本信息工程3班

学号

学生姓名

指导教师

2010年4月25日

目录

Hash算法1

通用Hash算法2

Hash算法难度3

HashFunctions6

CommonlyUsedHashFunctions7

DifficultieswithHashFunctions9

Hash算法

哈希算法（Hashfunctions）是密码学主要的一部分。

这是我们加密人员与泛滥的破解技术抗争的主力，我们知道他们最不喜欢就是密码图形。

一个hash算法提供了可变长度的输入字符串和固定长度的结果。

输入的很简便就是“hash”的意思，这个词不是人名的缩写。

你可以用hash来输入数据，固定长度的字符串允许我们使用hash值来引用实际字符串本身。

因为hash算法使用长的字符串，再变成一个短的。

不可避免有2个字符串通过hash算法会得出一样的结果，这个在密码学中叫“碰撞”。

举个你可以明白hash值的例子，假如JonCallas和JaneCannoy他们名字的hash值都是JC。

碰撞是了解hash算法很重要的部分，我们将会在比特（bit）的单位上有更多的介绍。

尽管缩写是一个很简单描述原文的方式，缩写造成了密码学目的的hash算法的错误。

密码学的hash算法。

有很多用在加密技术中的属性。

●很难逆向运算hash算法。

据hash知识，没有一个好的办法找到hash值对应的那个字符串。

我们已经知道了hash算法会丢失数据，创造了一个简单的相对性。

这个相同的性质也是名字缩写的：

除了JC没其它的信息，不能找出我的名字，是JonCallas？

是JaneCannoy？

还是？

●一个hash值，它应该很难确定一个本来的字符串。

这个性质是缩写遗漏（initialslack）。

看缩写的时候如果知道名字的匹配是很简单的。

在密码学中，我们想找出源信息和这个结果之间的联系，他们之间的关系是尽可能不透明的。

●确定一个源字符串，我们根据这个字符串的hash值很难找出第二个字符串。

很难有效的改变字符串获得一个碰撞。

也很难改变“我同意支付100美元”到“我同意支付500美元”而获得碰撞。

注意这2个字符串之间只有1位不同。

●也很难找出碰撞的2个字符串的hash值。

这个算法在很多不同的事情上给了我们灵活的想法，这里有一些例子：

●当你在PGP软件中输入密码的时候，我们使用hash算法来生成一个密钥。

中间的过程就是hash算法，通常一遍遍的使用来降低破解者的暴力破解的风险。

●PGP软件的随机数生成器在传入数据后，会根据你键盘和鼠标的移动时时更新。

这样使得观察者不确定这个值，也没有不变的随机数字。

我们使用hash算法消除观察者的数据中的不均匀性。

●随机数生成器使用hash算法产生输出值。

这个过程PGP软件也做了。

●文件完整性算法，使用hash算法可以很快的检查文件。

比如：

你可以保留文件的hash列表在你的电脑上。

hash数据库中的值也变了，你就看到计算机内的文件变化了。

软件分布系统站点通常有分布的

●复杂密码系统使用hash算法创建数据完整性作为它的一个系统组件，我们稍后会了解这个。

注意几乎所有算法现在都在被广泛使用，这有一个假设它们不会发生碰撞。

如果2个密钥发生了hash碰撞，任何一个密钥都可以解密文件。

如果2个软件包有相同的hash值时，一个肯定被误认为是另外一个。

通用Hash算法

表格1列出了一些hash算法的共同点，特别是PGP使用的。

表格1：

通用Hash算法

名称

大小（Bits）

描述

MD5

128

MD5是hash系列算法中的最低标准，PGP软件在PGP5.0版本以前使用。

MD5的脆弱性在1996年第一次出现。

MD5是MD4的改进，PGP软件不再使用它的原因是它是第一个被破解的通用hash算法

SHA-1

160

SHA-1是MD5的改进，由NIST设计，解决MD5的问题后被广泛使用。

RIPE-MD/160

160

RIPE-MD/160是一个和SHA-1差不多的Hash算法。

设计RIPE-MD/160为了改善超过MD5。

它被ReseauxIPEuropéens（RIPE）组织设计，而不是美国NIST我们认为它的安全性和SHA-1差不多。

SHA-256

256

SHA-256是美国NIST最新设计的新Hash算法。

也属于“SH-2”的类型，它有和其它不同的内部结构，但和其它hash算法的基本结构都是一样的。

SHA-512

512

512这是“SH-2”算法的一种，和SHA-256差不多。

SHA-384

384

SHA-384有比SHA-512更小的输出。

一般不常用SHA-384是因为除了大小以外没有任何优势，如果我们需要比SHA-256强度高的算法，我们会直接选SHA-512。

同样SHA-224是SHA-256缩小版。

Hash算法难度

目前（2006年中期），我们知道了hash算法系列在使用上并不是很完美，他们中的一些确实不完善。

这个问题到2004年的夏天变的明朗了，中国山东大学王小云教授宣布她和她的团队在一些hash算法中发现碰撞。

这时RSA名字中的“S”的这个人AdiShamir说，“上星期，我还认为hash算法是我们认为最好的部件。

现在则认为它是我们的部件中是最差的。

”在2005年初，王小云的攻击延伸到了第一次幸免的SHA-1。

我们仍然在应对这个问题。

他们中的所有都绕着hash碰撞，2个字符串生成了一样的hash值。

一个数学的分支：

组合数学（combinatorics）中的一个叫归档原理（PigeonholePrinciple

d）的公理。

最简单的归档原理的解释是：

如果你有13个鸽子而只有12个笼子，至少有一个里面装有2个鸽子。

很显然的，不是吗？

那就是为什么这是公理的原因！

如果你应用这个公理到hash算法，考虑16-bit的hash计算。

再考虑整个16-bit的字符。

依照归档原理，至少有2个字符串会有一样的hash。

事实上，还有一大堆一样的例子。

这个碰撞和鸽子汇集问题是一样的。

如果这个碰撞是均匀分布的（这对hash算法来说也正确），一个hash值那会有256个碰撞，然后根据归档原理，至少1个hash有至少有256个碰撞。

找出一个碰撞应该和猜一样容易，但是有多难呢？

回答这个问题又引发另外一个有趣的数学问题叫生日问题。

在谈论区块大小的时候我们谈到过的。

和Alice有相同生日的人的概率是1/365。

但是如果你有一房子满满的人，和另外一个人生日发生碰撞的概率有多大？

特别的，有多少人机率均等也就是房间中有2个人的生日是一样的呢？

这个问题的一般回答和找出hash碰撞的是一样的。

我们认为生日是比另外一个名字缩写问题更好的hash问题，但远远不完美。

尽管如此，生日是一个公平的任意分布的b。

对于生日来说，原来生日c碰撞的机率是大约23个人中的偶数。

通常，机率是偶数的大约是选项数字的平方根。

我确定你注意到我使用了一个很含糊的词“大约”。

这是因为答案不是准确，只是接近平方根。

大概的说，碰撞的机率是:

其中，Prob是机率的意思，只表示函数名，pigeons是鸽子，holes是笼子洞。

Pigeons和holes都是输入变量的名字。

省下你的数学运算。

如果你解决了鸽子数目的问题，结果的机率是一个洞的2个鸽子里面每一个都有

的概率。

可以算出约为

，对于我们使用的那个问题来说，我们也可以认为等于

。

特别是当我们去处理一个非常大的数字的时候，这样去推测很方便，这个方法也是理论数学中被惯用的手法。

所以，如果我们有一个n-bit的hash算法，如果我们有

个字符串的碰撞的机率相等。

也就是说，160-bit的hash运算只有80-bit的安全性。

是很大的一个数字。

大约2倍的阿伏伽德罗常数。

阿伏伽德罗常数d是摩尔体积的分子数，或者用一个方便的东西表示，就是一汤勺水中水分子的数目。

那是个很大的数。

王小云带着报告参加了2004年密码界峰会，她震撼了密码界。

她没有用一张纸来展示如何碰撞，她仅仅只用了他们中的一部分。

就像你看到的，因为碰撞很难发现。

仅仅有128-bit的hash算法中的一部分中有碰撞，也就意味着碰撞已经出现了。

对于密码分析学家的主要问题是“她知道我们不能够做什么？

”6和月以后，她的技术扩展到攻击质数的160-bit的hash算法。

这就是我们在最后2年所总结的：

●王小云是最优秀的密码分析专家。

她有着其它数学家没有的基础数学洞察力；她非常迅速的成为世界上为数不多的、最优秀的hash算法密码分析专家。

●一些其它的理论工作不是去进行应用实际，而是更多的思考。

●有很多议案关于如何修改剩下的算法来抵抗王小云的攻击。

他们都非常棒，但是一个明显的问题是，“明年有什么攻击，这个修正可以解决吗？

”当然，这个问题是不能回答的。

我们不可能反对未知的攻击来保护我们的算法。

无论如何，其中的很多议案确实是解决的好办法。

一个简单的技术诸如当进行hash运算时使用每双字节（用AABBCC来代替ABC），或者插入0比特在每4个字节后面，或者添加随机数据在准备hash运算的数据之前，用这些办法解决了已知的问题。

●我们开始考虑一个如何设计一个好的hash算法的想法。

在2005年10月，NIST主持了一个关于hash算法的工作组。

密码专家开始考虑想出一个如何设计一个好的hash算法的想法。

第2个工作组在2006年8月开始计划。

同样也有像AES相似的竞争方式来产生一个新的hash算法。

●工程师的观点中也有一些好的想法。

在PGP团队中，我们已经发扬了首创精神。

在PGP团队，我们开始转移MD5到1997年的水平。

PGP5.0开始从MD5向SHA-1发展，保持MD5的唯一目的是为了向后兼容性。

PGP8.0.3介绍了这个技术支持，也可以在阅读中找到，但是没有SHA-256、SHA-384和SHA-512的算法。

PGP9.0开始从SHA-1向SHA-256发展。

HashFunctions

Hashfunctionsareanimportantpartofcryptography.Theyaretheworkhorsesthatwecryptographersuseandabuseforallsortsofthings,andyetweunderstandthemleastofallthecryptographicprimitives.

Ahashfunctiontakesavariable-lengthinputstringandcreatesafixed-lengthoutput.That“hash”oftheinputisashortcut,notunlikeaperson’sinitials.Youcanrefertotheinputstringbyitshash.Thefactthatitisafixed-lengthstringallowsustoeasilyusethehashvalueasareferrertotheactualstringitself.

Becauseahashfunctiontakesalongstringandreducesittoashortone,itisinevitablethattherewillbetwostringsthathashtothesamevalue,orcollideincryptographer-speak.Forexample,thenamesJonCallasandJaneCannoycollidewithinitialstothehashofJC.Collisionsareimportantintheunderstandingofhashfunctions,andwe’lltalkmoreabouttheminabit.

Althoughinitialsareaneasywaytodescribethebasicconcept,initialsmakeabadhashfunctionforcryptographicpurposes.Acryptographichashfunctionhasanumberofotherpropertiesthatmakeitusefulcryptographically.

•Itshouldbehardtoreverseahashfunction.Knowingthehash,thereshouldbenogoodwaytofindtheinputstringthatgeneratedit.Giventhat（typically）hashfunctionslosedata,thisisarelativelyeasypropertytocreate.Thesamepropertyisalsotrueforinitials:

knowingJCandnothingelse,thereisnogoodwaytogettomyname.

•Givenahashvalue,itshouldbehardtoidentifyapossiblesourcestring.Thispropertyisonethatinitialslack.Itisveryeasytolookatasetofinitialsandknowifanamematchesit.Withacryptographichashfunction,however,wewanttherelationshipbetweenasourceandaresulttobeasopaqueaspossible.

•Givenonesourcestring,itshouldbehardtofindasecondstringthatcollideswithitshash.Itshouldbeespeciallyhardtochangeastringusefullyandgetacollision.Inanextremecase,itshouldbehardtochange“Iagreetopay$100”to“Iagreetopay$500”andhavethatcollide.Notethatthedifferencebetweenthetwostringsisonlyasinglebit.

•Itshouldalsobehardtofindtwostringsthatcollideintheirhashvalues.Theserequirementsgiveusveryflexiblefunctionsthatareusedforlotsofdifferentthings.Herearesomeexamples:

•Randomnumbergeneratorsthemselvesoftenusehashfunctionstoproducetheiroutput.TheoneinPGPsoftwaredoes.

•Fileintegritysystemsusehashfunctionsasquickchecksonthefiles.Forexample,youcankeepalistofthehashesofthefilesonyourcomputer,andyoucanseeifthatfilehaschangedbycomparingthehashofthefileondisktotheoneinthedatabase.Softwaredistributionsitesalsooftenlistthehashvalueofthedistributedfilesothatpeoplewhowanttoseeiftheyhavetherightfilecancomputeandcomparehashes.

•Complexcryptographicsystemsthatcreatedataintegrityusehashfunctionsasacomponent.We’lltalkmoreaboutthemlater.Notethatforalmostalloftheseuses,there’sanassumptionthattherewon’tbecollisions.Iftwopassphrasescollideintheirhash,eithercandecryptafile.Iftwosoftwarepackageshashtothesamevalue,thenonecanbemistakenfortheother.

CommonlyUsedHashFunctions

Table1listssomecommonlyusedhashfunctions,especiallytheoneswepresentlyuseinPGPsoftware.

Name

Size

Description

MD5

128bits

MD5wasthesolehashfunctionthatPGPsoftwareusedpriortoPGP5.0.WeaknessesinMD5firstshowedupin1996.MD5isitselfanimprovementonMD4,whichwasneverusedinPGPsoftwareandwasthefirstcommonhashfunctiontobefullybroken.

SHA-1

160bits

SHA-1appearedinPGP5.0,andalsoinOpenPGP.SHA-1isanimprovementonMD5thatwascreatedbyNISTtobewiderandalsotocorrectproblemsinMD5.

RIPE-MD/160

160bits

RIPE-MD/160isahashfunctionsimilartoSHA-1.RIPE-MD/160wascreatedtobeanimprovementoverMD5.However,itwascreatedbytheEuropeanRéseauxIPEuropéens（RIPE）organizationratherthantheUSNIST.WeexpectithassimilarsecuritycharacteristicstoSHA-1.

SHA-256

256bits

SHA-256isoneofanewfamilyofhashescreatedbytheUSNISTthatarecollectivelycalledthe“SHA-2”family.Ithasdifferentinternalstructure,butcomesfromthesamebasicconstructionastheotherhashfunctionsinthistable.

SHA-512

512bits

Thisisanothermemberofthe“SHA-2”family,alongwithSHA-256

SHA-384

384bits

SHA-384isavariantofSHA-512thathasasmalleroutput.Ingeneral,SHA-384isnotused,becauseithasnoadvantagesoverSHA-512exceptforthehashsize.ItrunsatthesamespeedasSHA-512,sousuallyifweneedsomethingstrongerthanSHA-256,wegodirectlytoSHA-512.ThereisalsoaSHA-224whichisasimilartruncationofSHA-256.

Table1CommonlyUsedHashFunctions

DifficultieswithHashFunctions

Presently（mid-2006）,weknowthesuiteofhashfunctionswehavebeenusingisnotperfect,andsomeofthemarequiteimperfect.Theseproblemscametolightinthesummerof2004whenXiaoyungWangannouncedthatsheandherteamproducedcollisionsinanumberofhashfunctions[WANG04].AdiShamir,the“S”intheRSAalgorithm,saidatthetime,“Lastweek,Ithoughtthathashfunctionswerethecomponentweunderstoodbest.NowIseethattheyarethecomponentweunderstandleast.”Inearly2005,Xiaoyung’sattackswereextendedtoSHA-1,whichhadsurvivedherfirstwork[WANG05].

Wearestillcopingwiththeseproblems,allofwhichrevolvearoun