来源：刘教链
Source: The chain of Liu
1974年图灵奖(IT界的诺贝尔奖)获得者、《计算机程序设计艺术》(TAOCP)作者、美国计算机科学家、斯坦福大学退休教授高德纳(Donald Knuth, 1938-)在他出版于2000年的书《排序和搜索》中考证了“哈希”(hash)一词作为计算机术语的来历。“哈希”这个词在英文中的本意是“把东西切碎”、“把事情弄的一团糟”的意思。用到计算机的语境里，也是借用了这个词的本意，指把数据切碎、弄乱掉，乱到你根本无法恢复出原来的数据。就像把一本《红楼梦》撕成无数碎片，丢到火炉里一把火烧掉，从灰烬里捡回来几十个依稀可辨的字，把这几十个字拼凑起来，就是这本红楼梦的残片。就是上帝，恐怕也难以从这残片还原出原来那本《红楼梦》的全部内容。“哈希”则比这火炉有一个更优秀的特点，那就是对于同样的内容，每次焚毁后都会剩下同样的残片，仿佛时光倒流、事件重演一般。具有这种计算“哈希”功能的计算机函数就叫做“哈希函数”(hash function)，计算的结果就叫做“哈希值”(hash value)。据高德纳考证，美国IBM公司的图书馆和信息科学家汉斯·彼得·鲁恩(Hans Peter Luhn)在1953年的笔记中首次使用了“哈希函数”这个概念。这个词迅速流传开来，得到了广泛的使用。虽然直到70年代末，它才正式出现在学术刊物上。
The term “hash” was used as a computer term by the winner of the 1974 Turing Prize (Nobel Prize in the IT world), author of “TAOCP”, computer scientist in the United States, retired professor of Stanford University, Donald Knuth, 1938-), in his book “Standing and Search” published in 2000, to describe the word “hash” in English as the word “hashi.” The word “hashi” was meant to be “crushing things”, “making things a mess” in English. In the context of the computer, it was also used as the word “drawing and disassembling”, and it was impossible to restore the original data.
哈希，又叫做“摘要”，“散列”，或者“杂凑”。哈希不是一种信息压缩技术，虽然它也会大量丢弃数据，只产生一个固定长度的摘要。对照片或者音乐进行有损压缩，追求的是还原度和保真度；对数据做哈希计算，追求的结果恰恰相反。哈希也不是一种加密技术，虽然它的计算结果变得像密码一样无法理解。加密是为了解密，哈希则是为了无法解密。哈希也不是一种随机数计算技术，虽然它的计算结果看上去像随机数一样无规律可循。真随机数是非确定性的，每次计算结果都不同；哈希的结果虽然看似无章可循，但是只要输入的内容是相同的，结果必定相同。
Hashi, also known as “summary”, “cassette” or “comprehensive.” Hashi is not an information compression technique, although it can also discard data in large numbers, producing only a fixed-length summary. is damagingly compressed to photographs or music, seeking both restoration and authenticity; the data are calculated with the opposite result. Hashi is not an encoded technology, although it becomes as incomprehensible as a password. encryption is meant to declassify, while Hashi is not a random calculation technique. Hashi is not a random calculation technique, although it looks as irregular as random numbers. /b) The random numbers are irregular, and the results vary from time to time; while Hashi's results seem to be non-predictable, the results are necessarily the same, as long as the entries are identical.
密码学哈希函数(CHF, Cryptographic Hash Function)，则是一类具有独特性质的哈希函数。所有这些性质中，有三个性质是非常关键的：
CHF, Cryptopographic Hash Action, is a unique type of Hash function. Three of these properties are critical:
第一个性质就是，计算结果的分布非常稀疏，几乎不会出现两份不同的输入内容算出来同样的哈希值，这个性质叫做“免碰撞性”(collision-free)。
The first is that the distribution of the results of the calculations is very thin, and there are few different input elements to arrive at the same Hashi value, which is called "collision-free" .
第二个性质就是，计算结果毫无规律，你很难通过变换输入内容，然后对比内容及其哈希之间的规律，试图破译一个陌生哈希值的原始输入内容，这个性质叫做“隐藏性”(hiding)。
The second is the irregularity of the calculation, which makes it difficult for you to change the content and then compare it with the pattern between the content and the Hashi and try to decipher the original input of a strange Hashi value, which is called "hiding" .
第三个性质就是，给出一个指定的哈希值，找到一个输入内容，能够计算出这个哈希值的最有效方法，就是穷举尝试，又称作暴力破解，这个性质叫做“谜题友好性”(puzzle-friendly)。而密码学哈希函数的这三个特性，对于中本聪成功设计出比特币，起到了决定性的关键作用。
The third is to give a specified Hashi value, to find an input that will be the most effective way to calculate the Hashi value, namely, to try a lot, known as violence cracking, which is called "puzzle-friendly" . The cryptography of these three features of the Hashi function plays a decisive role in the successful design of Bitcoin by the middle-bone.
2004年、2005年，中国密码学家、中科院院士王小云教授和她的团队先后攻破了迄今仍在广泛使用的两个高度流行的哈希算法，一个叫做MD5，另一个叫做SHA-1。MD5是Message Digest 5(信息摘要算法第5版)的缩写。而SHA-1则是Secure Hash Algorithm 1(安全哈希算法第1版)的缩写。王小云团队对这两个哈希算法的破解都是完整版破解，均属世界首次，一时之间，举世瞩目。
In 2004, 2005, Chinese cryptographer, Professor Wang Xiaoyan of the Chinese Academy of Sciences and her team broke down two highly popular Hashi algorithms, one called MD5 and the other known as SHA-1. MD5 is the acronym of the message Digest 5 (version 5 of the information digest algorithm). And SHA-1 is the acronym of Secure Hash Algorithm 1 (version 1 of the security Hash algorithm). Wang Xiaoyun’s decomposition of the two Hashi algorithms was the first in the world and was the first in a time in the world.
为什么对这两次破解全球如此轰动？因为MD5和SHA-1这两个哈希算法的使用实在太广泛，广泛到即使在它们已经被完全攻破15年后的今天，仍然在被大量的软件、网站和系统使用着，上到政府网站，下到手机应用，这两个算法的身影无处不在。当我们注册网站或者登陆App输入密码时，常见的设计是，为了保护隐私数据，密码通常不应明文存储在数据库里，而应该存储其哈希值。但是，时至今日，大量网站系统仍然在使用MD5或SHA-1哈希算法。这无疑就是让我们的密码和隐私数据处于实质上的裸奔状态。大部分的用户，也许包括你，为了避免密码记忆之苦，又往往在不同的网站和App使用相同或者相近的密码。这样，当黑客攻破了安全最薄弱的一个网站，拿到了你的数据，破解了你的密码，就能用你的用户名和密码去登陆其他网站或App翻看你的更多隐私，甚至以你的名义对你的家人和朋友实施社会工程学攻击，骗取他们的信任，拿到更多的隐私信息，直至最终触及你以及你家人、朋友的财产和核心利益，并实施不法侵占或勒索。
Why is this so exciting for the world when we register websites or access App's passwords? The common design is that codes should not be stored explicitly in databases to protect privacy data, but should store their Hashi values. But, so far, a lot of web sites still use MD5 or SHA-1 Hashi algorithms, even 15 years after they have been completely breached. This is undoubtedly the virtual nudity of our passwords and privacy data. Most users, including you, may, in order to avoid the memory of passwords, often use the same or close combination of passwords on different websites and Apps to protect privacy data. So, when hackers break through one of the weakest web sites, get your data, break your passwords, and use your usernames and passwords to access other sites or App's personal information, and even to use your personal and personal knowledge of your personal interests, and to use your personal knowledge and your personal knowledge to steal it from you and your friends.
MD5算法的“碰撞攻击”(找到两个输入其哈希值相同)最佳破解记录是由谢涛(音, Tao Xie)等人于2013年3月25日发表；“原像攻击”(找到原输入)最佳破解记录是由佐佐木悠(Yu Sasaki)等人于2009年6月16日发表。而SHA-1算法的“碰撞攻击”最佳破解纪录是由盖坦·勒伦(Ga?tan Leurent）等人于2020年1月8日发表。SHA-1算法的“原像攻击”方法迄今尚未找到。
The best crack record of the MD5 algorithm's “collapse attack” (which found two of which entered the same Hashi value) was published by Xie Tao Xie et al. on 25 March 2013; the best crack record of the “original attack” (which found the original input) was published by Yu Sasaki et al. on 16 June 2009. The best crack record of the “collapse attack” of the SHA-1 algorithm was published by Gatán Leurent et al. on 8 January 2020. The “original attack” method of the SHA-1 algorithm has not yet been found.
MD5算法是由美国MIT大学教授、密码学家罗纳德·里维斯特(Ronald Rivest)在上世纪90年代前后所设计的一系列信息摘要算法的其中一个版本，其设计于1991年，并于1992年被IETF(国际互联网工程任务组)吸收为RFC(征集意见稿, Request For Comments)标准，编号1321，成为全世界互联网使用最多的加密算法之一。而作为美国政府1993年启动的“冠石项目”(capstone project)的一部分，SHA-1算法则是由NSA(美国国家安全局)主导设计的一系列安全哈希算法之一，是SHA-0的后继版本，在1995年由FIPS PUB 180-1号文件予以公布，同样的，在互联网领域，比如很多网站浏览器的加密证书中，有着极为广泛的应用。不知道如果没有王小云在中本聪开始着手设计比特币之前两三年发表论文，指出MD5和SHA-1算法已经不安全，中本聪会不会采用这两个算法中的某一个。以中本聪对密码学的敏感度，相信他应该不会。不过，历史从来不容假设。
The MD5 algorithm, one of the versions of a series of information digest algorithms designed by Ronald Riverst, a professor and cryptographer at the University of MIT, before and after the 1990s, was designed in 1991 and absorbed by the IETF (International Task Force on Internet Engineering) as a RFC standard, published in 1995 by FIPS PUB 180-1, and, similarly, in the Internet field, as in the cryptography of many web browsers, there is a very wide range of applications.
战国末期法家思想的集大成者韩非子(约公元前280年-公元前233年)在《韩非子·难一》中记载了一个“矛与盾”的小故事。故事说，有一个卖矛和盾的楚国人，一会儿叫卖自己的矛，说自己的矛是世界上最锋利的矛，什么盾都能刺破；一会儿又叫卖自己的盾，说自己的盾是世界上最坚固的盾，什么矛都挡得住。这时围观的群众里有人说，那你用你自己的矛，刺一刺你自己的盾，那又会怎么样呢？这个楚国人一时语塞，竟然一句话也答不上来。
Han Fiko, the author of the last era of French thought in the war, wrote a small story about spears and shields in "Kanfiko Koichi". The story says that there is a man who sells spears and shields, and says that his spears are the sharpest spears in the world, that any shield can be broken; and then he sells his shield, that his shield is the strongest shield in the world, that any spear can be blocked. Some in this crowd say, "What if you stab your shield with your own spear?" This man cannot say a word.
围绕哈希算法而展开的攻防较量就仿佛这矛与盾。今天道高一尺，却不知明天是否会有魔高一丈。攻守之道，往往都是攻方容易占据有利地位。正道的攻方，往往会收获比守方更大的荣誉；邪道的攻方，则直接从成功中获得巨大的利益。成功攻破MD5和SHA-1的王小云教授世界闻名，而这两个算法的设计者却鲜有人记得他们的名字。巨大的荣誉激励或物质激励推动着攻方不断的努力，攻守之势总归是一种不对称的、艰巨而长期的博弈。我们知道，也许今天所有已知的加密算法，在未来某一天都终将被破解，但我们不知道，这一天究竟何时到来。要让比特币系统能够安全运行100年、200年甚至更久(比特币挖矿结束时间大概到2140年左右，可见比特币的设计寿命至少也得一两百年往上)，中本聪不得不在今天做好充分的考虑和设计。
The battle against Hashi's algorithms is as if it were a spear and shield. Today, one foot tall, it is not clear whether there will be a magic tomorrow. It is often the way to do it. It is often the way to do it. It is the way to do it. The right way to do it is often to gain more honour than the right to do it; the way to do it is the way to do it is the way to do it; the way to do it, the way to do it, the way to do it, the way to do it, the way to do it, the way to do it, the way to do it, the way to do it, the way to do it, the way to do it, the way to do it, the way to do it, the way to do it, the way to do it, the way to do it, the way to do it, the way to do it. The way to do it, the way to do it, the way to do it, the way to do it, the way to do it, the way to do it.
2001年，NIST(美国国家标准局)公布了联邦标准FIPS PUB 180-2号草案。在该草案中，安全哈希算法SHA-2家族首次亮相，并于次年8月正式成为新的安全哈希标准。SHA-2家族包含了6个哈希函数，以其摘要长度(即计算出来的哈希值的长度)命名，比如SHA-256(摘要长度256比特)、SHA-512(摘要长度512比特)等。而其中的SHA-256算法，正是被中本聪选用，从而在比特币整个系统中几乎无处不在的哈希算法之一。
In 2001, NIST (National Standards Bureau of the United States) published draft federal standard FIPS PUB 180-2. In that draft, the SHA-2 family had its first appearance and formally became the new SHA-2 standard in August of the following year. The SHA-2 family included six Hashi functions named after its summary length (i.e. the length of the calculated Hashi value), such as SHA-256 (summary length 256 bits), SHA-512 (summary length 512 bits). The SHA-256 algorithm was one of the Hashi algorithms that had been chosen by Bint Bint, and was thus almost ubiquitous in the entire system of Bitcoin.
虽然SHA-256算法256比特的摘要长度只比SHA-1的160比特大了一倍，但是其安全性和破解难度却是天壤之别。对此，在2010年6月14日的一次论坛讨论中，中本聪专门就SHA-256的破解问题作出如下评价：
Although the SHA-256 bits summary is only twice as long as the 160 bits in SHA-1, its safety and difficulty of deciphering is quite different. In a forum discussion on 14 June 2010, China made the following assessment of the breakup of SHA-256:
“SHA-256非常强壮。它不像从MD5到SHA1的渐进式进步。它可以几十年屹立不倒，除非出现某种大规模突破性的攻击技术。
"SHA-256 is very strong. It's not like incremental progress from MD5 to SHA1. It can stand for decades unless there is some kind of massive breakthrough attack technique.
如果SHA-256被全面攻破，我想我们可以达成某种共识，锁定出问题之前的「诚实的」区块链，并从那个位置开始采用新的哈希函数。
If SHA-256 is completely breached, I think we can reach some kind of consensus, lock in the chain of "honest" blocks before the problem, and start with the new Hashi function from that position.
如果哈希攻破是逐渐发生的，我们有一个按部就班的方式过渡到新的哈希函数。(比特币)软件可以编写成从某个特定的区块号码开始采用新的哈希函数。每个人都需要在那个时间点升级。(比特币)软件可以把所有旧区块的新哈希值保存一下，如此可以确保对于旧区块的篡改——即便旧哈希值相同——也不会被接纳。”
If the Hash attack is gradual, we have a step-by-step transition to a new Hash function. (bitcoin) software can be written to start with a new Hash function from a given block number. Everyone needs to upgrade at that point in time. (bitcoin) software can save all the new Hash values of the old block, so that it can ensure that the tampering of the old block — even if it is the same — will not be accepted. ”
20世纪80年代，欧盟启动了“RACE(欧洲先进通信技术研发)计划”，并于1992年启动了“RIPE项目”。其中项目名“RIPE”的具体含义是“RACE完整性原语求值”(RACE Integrity Primitives Evaluation)。从这个名字我们就能读出“哈希”的味道，因为对给定内容求哈希值这一计算机指令(术语叫“原语”)正好可以用来验证内容的完整性，也就是没有被篡改。如果发生了篡改，即使再微小，也会导致哈希值的剧烈变化，从而很容易被发现。在“RIPE项目”的执行过程中，一个哈希算法被设计出来了，它的名字叫做RIPEMD(RIPE消息摘要, RIPE Message Digest)。
In the 1980s, the EU launched the RACE (European Advanced Communication Technology Research and Development) Project, and in 1992 it launched the RIPE Project. The specific meaning of the project's name, RIPE, is “RACE integrity for value”. From this name, we can read the taste of “Hashi” because the computer directive (the term “originally”) to give content is used to verify the integrity of the content, i.e., it has not been tampered with. If tampered with, even minorly, it could lead to a radical change in the Hashi value, so that it can be easily detected. In the course of the implementation of the RIPE project, a Hashi algorithm, called RIPEMD, is designed.
RIPEMD家族也有一系列所求摘要长度不等的哈希函数。其中摘要长度小于160比特的，被认为安全性不够，而摘要长度大于160比特的，其实际安全强度也就只有160比特，超出的部分只是为了凑够长度。所以，就余下一个RIPEMD-160不长不短刚刚好。根据我们对哈希算法命名的了解，RIPEMD-160计算出来的哈希值长度为160比特币，这个长度和SHA-1是一样的，都比SHA-256要短。中本聪说，“为了让比特币地址更短，它们是公钥的哈希，而不是(椭圆曲线电子签名算法的)公钥”。事实上，中本聪不是用了一个哈希函数，而是两个。他先对公钥做了SHA-256哈希，然后把结果又做了一次RIPEMD-160哈希，得到了比特币地址。这种双层哈希的设计，是中本聪的一个独特手法。在比特币区块挖矿中，也是这样的双层哈希结构，只不过换成了两层SHA-256。
The RIPEMD family also has a series of Hashi functions that vary in length. The summary length is less than 160 bits, which is considered to be inadequate for security, while the summary length is greater than 160 bits, and the actual security strength is only 160 bits, which is only enough. So, the rest of the RIPEMD-160 is just as long as it is long. According to our understanding of Hashi's naming, RIPEMD-160 calculates the Hashi value of 160 bits, which is the same length as SHA-1 and which is shorter than SHA-256. The middle hearing says, "To make the Bitcoin address shorter, they are Hashi's public key, rather than (the elliptical electronic signature algorithm) key." In fact, the middle being not a Hashi's function, but two. He first made a Sha-256, which is the same length as SHA-1, and then made another RIPMD-160, which has the bitcoin address.
中本聪没有解释过如此设计的原因。今天的我们已经知道，MD5、SHA-1、SHA-2这一系列的哈希算法，当然也就包括中本聪选用的SHA-256哈希算法，由于都使用了一种称之为“默克尔-丹加德”构造(Merkle–Damg?rd construction)的方法，而对一种称之为“长度扩展攻击”(length extension attack)的攻击方法敏感。通过使用这种攻击方法，攻击者可以在无需知道原文、只需知道原文长度的情况下，向原文后附加攻击文本并计算出正确的哈希值。今天我们能够查到的最早有关该攻击方法的文献，只能追溯到2012年。至于中本聪在2008年前后设计比特币时，是如何觉察到单层哈希可能会对某种特别的攻击方法敏感，从而在使用时小心翼翼的加了一层，形成双层哈希设计，我们就不得而知了。也许，他是受到了NIST(美国国家标准技术局)在2006年举办的哈希函数设计大赛的启发吗？
We already know today that MD5, SHA-1, SHA-2 is sensitive to the method of attack . By using this method of attack, the attacker can add the original version to the original version without having to know the length of the original text, and calculate the correct Hashi value. The earliest documentation we can find today on the method of attack can only go back to 2012.
2006年，NIST举办了一场后来旷日持久的哈希函数设计大赛，赛题是设计一种不使用“默克尔-丹加德”构造的崭新的哈希函数，称之为SHA-3。彼时，SHA-3的设计目标并非为了取代SHA-2，因为后者并未被攻破。但是因为MD5和SHA-1在2005年被王小云教授团队成功攻破了，NIST感觉需要未雨绸缪，于是希望提早着手，为SHA-2准备“备胎”。这个大赛，可以称之为SHA-2的“备胎计划”。
In 2006, NIST organized a later and protracted Hashi design competition on the design of a brand new Hashi function, known as SHA-3, which did not use the Merkel-Dangad structure. At the same time, SHA-3 was not designed to replace SHA-2, as the latter was not destroyed. But because MD5 and SHA-1 were successfully attacked by Professor Wang Xiaoyun's team in 2005, NIST felt that it needed to be proactive, so it wanted to start early and prepare a “preparation” for SHA-2. This competition, which could be called SHA-2, the “preparation plan”.
这个“备胎计划”的推进一波三折。2010年12月，一个称之为keccak-256的哈希函数最终胜出。NIST希望在标准化时对其设计进行微调和修订，却被2013年突发的“棱镜门”事件和斯诺登的“吹哨”打乱了节奏。公众失去了对NIST的信任，对NIST修订哈希函数的提案进行了强烈抵制。就这样一直僵持到2015年，NIST才最终完成了修订并发布了FIPS 202标准。另外一个由俄裔加拿大程序员维塔利克·布特林(Vitalik Buterin，人称“V神”，时年仅19岁)于2013年发起的知名公链项目，以太坊(Ethereum)，大量使用了keccak-256哈希函数，但是，他们使用的是重写的原始版keccak算法，而不是NIST的修订版算法。由于keccak算法没有使用“默克尔-丹加德”构造，而是使用了另外一种称之为“海绵构造”(sponge construction)的新方法，所以对“长度扩展攻击”免疫。也因为此，以太坊的地址就是单层哈希结构，只对公钥做了一次keccak-256哈希(并截取了后20位以缩短长度)。
In December 2010, a Hashi function called Keccak-256 was finally won. NIST, wishing to fine-tune and revise its design at the time of standardization, was outpaced by the sudden "Blackgate" incident in 2013 and the "blowing" of Snowden. The public lost confidence in NIST, strongly boycotting NIST's proposal to revise the Hashi function. The NIST finally completed the revision and release of the FIPS 202 standard until 2015. Another Russian Canadian programmer, Vitalik Buterin, called the "V God" when he was only 19 years old, used a large number of Keccak-256 Hashi functions , but used a new version of the KNCK medium, instead of NIST's revised version.
注册有任何问题请添加 微信：MVIP619 拉你进入群
打开微信扫一扫
添加客服
进入交流群
发表评论