At the technical exchange activity of the OK blockchain Engineering Institute, we invited Dr. Wu Yanbing from the cryptology research center of Tsinghua University to discuss and sort out some of the wonderful ideas for the readers. Hash function is a basic tool of cryptography. Hash function can be used in digital signature. We can know from the following introduction that digital signature uses elliptic curve and has high computational complexity. Before signing, we usually compress the file or information to be signed by hash function before signing. The hash function can also be used in the detection of data integrity. For example, we often see that when downloading software on the website, the hash value will be given next to it. This hash value is used to determine whether the file is complete and whether it has been tampered with by others during downloading.
We downloaded a file from the website. How can we judge whether the file we downloaded is complete? We can compare the value of the file after the hash function with that on the website to see whether it is the same. If it is the same, it means the file website; if it is different, it means it is not on the website or has been tampered with. The hash function can also be used in provably secure cryptosystems, which we will talk about later. Secondly, the hsah function can also detect whether the message is tampered with during transmission, and prevent forgery of electronic signature and message authentication code. As a security component, it designs a variety of cryptosystems and secure communication protocols, and is the core technology of bitcoin and blockchain.
Hash function, also known as hash function, hash function, digital fingerprint, etc., compresses arbitrarily long messages into a fixed length digest. As shown in the following figure, we can see that the hash function can compress files of any size into a 01 string of N bits, and N can be 128, 160, 192, 256, 384 or 512. We can see that the mathematical expression of the hash function is y = H (m), {0,1} * {0,1} n, H represents a hash function, M represents an input information, and Y is an output. We can see that the input of the hash function can be any number of bits, but the output is a fixed number of bits, which is n.
The hash table used in the computer is mainly used for storage and lookup, which is derived from the historical discussion of IBM in 1953. The hash function in cryptography is slightly different from the hash function used in computers. The hash function used in cryptography has specific security attributes. After that, we will introduce its security attributes in detail. The hash function we introduced earlier does not have a key and directly compresses messages. We can introduce a key into the hash function to make it a MAC algorithm that can authenticate. We can see that the following figure shows that the key and the message are used as the input of the hash function at the same time.
The MAC function has the functions of message integrity detection and identity authentication of both communication parties. Hash function is widely used in various Internet protocols, such as IPSec, SSL / TLS, SSH, SNMP, etc., as well as financial security: banks, electronic money, etc. Let's talk about the five security features of the hash function. First, the hash function has the security attribute of antigen like attack. Antigen image attack means that it is difficult to recover message M given any hash value y. Anti second image attack and collision resistance are similar. Anti second image attack means that it is difficult to calculate another message M2 so that h (M1) = H (M2) for a given message M1.
While anti-collision refers to finding that different messages (M1, M2) have the same fingerprint, that is, H (M1) = H (M2) is difficult. The difference between these two security attributes is that one is given M1, and the other is that M1 can choose by itself. Anti length extension attack refers to the calculation of H (mm & rsquo;) without knowing the length and H (m) of the message M It is difficult. Anti secondary collision attack: given a pair of collision messages m and M & rsquo;, For any message n, the messages Mn and M & rsquo; N also form a collision. My tutor Professor Wang Xiaoyun proposed an algorithm that can successfully break MD5 on crypto2004.
SHA-1 was proposed by NIST (National Institute of standards and Technology) in 1995, with an output length of 160 bits. SHA-2 was proposed by NIST in 2002, with an output length of 256384512 bits. Whirlpool was designed by Rijmen and others in 2000, with an output length of 512 bits. Keccak won the Sha-3 standard competition and became the Sha-3 standard algorithm. It was designed by Daemen and others in 2007, with an output length of 256384512 bits. The hash function also has an algorithm designed and implemented by the Chinese themselves. SM3 was designed by my tutor Academician Wang Xiaoyun in 2010, with an output length of 256 bits.
Secondly, Mr. Wang also broke SHA-1 and SHA-2. Mr. Wang's most recommended introductory book on cryptography is codebook. I mentioned MD5 by reading the art of deception. MD5 has been cracked by Chinese scientist Wang Xiaoyun. I learned about Mr. Wang. After that, I admired Mr. Wang and became her graduate student. Hash can be used in login authentication. The user provides the user name and password. The server looks up the user name in the database, obtains the salt value, calculates the hash (Salt + password) and compares it with the database. If it is the same, it passes the authentication. This can prevent the password from being directly stored in the database, and the hacker / administrator can directly view the user password.
The purpose of adding salt is to prevent two users with the same password from being directly viewed in the server. Hash can be used in key derivation. We can see that the random number generated by the U shield used by the bank is generated by the hash function. Secondly, hash function is also widely used in RFID, satellite communication and other cryptographic systems. Hash function is also used in digital signature. After learning the knowledge in the next section, we will know that the digital signature uses elliptic curve signature, which is very slow in calculation. The larger the amount of data to be signed, the slower the signature speed will be. Therefore, the general method is to hash compress the information to be signed before signing to obtain a very short bit string, and then perform signature operation.
Let's see the following figure is a model of financial security. Hash function is also well used in bitcoin and blockchain. Bitcoin mining is actually looking for a random number n, so that the first m bits of the hash value of the transaction information on N splicing are zero. The first m bits are zero, which represents the computational complexity of mining. If you want to find the hash value with the first 60 bits being zero, then the computational complexity is 260 operations. Electronic currency: an electronic signature that replaces money. The legitimacy of money can be verified by the user's public key (digital certificate). Wu Yanbing: Ph.D. in mathematics, Institute of advanced studies, Tsinghua University, under the guidance of Wang Xiaoyun, a famous Chinese cryptographer and academician of the Chinese Academy of Sciences.
Inventor of the Korean standard encryption algorithm lea and pop consensus algorithm.