Skip to content
Search

Hash function

lastmod 2025-01-15created 2016-08-227 edits

A hash function is an algorithm that maps data of arbitrary length to data of fixed length. The value obtained by a hash function is called a hash value, hash code, checksum, or hash. A hash function must operate deterministically, so if two hash values differ, the original data for those hash values must also differ. (The converse does not hold.) The quality of a hash function is determined by the probability of hash collisions over the input domain; the higher the probability of hash collisions, the harder it becomes to distinguish different data and the higher the cost of searching.

Hash functions are often divided into cryptographic hash functions (Cryptographic Hash Function) and non-cryptographic hash functions.

Cryptographic hash functions include MD5 and the SHA family of hash functions, while non-cryptographic hash functions include CRC32, among others.

Cryptographic hash functions must be secure against pre-image (pre-image), second pre-image (2nd preimage), and collision (collision) attacks, and are used for authentication. Cryptographic hash functions accept input of arbitrary length, but since length information is included during MD Strength Padding, there is a limit on the maximum length. For example, if the length information is written into the lower 8 bits during padding, the maximum hashable length is 0xFF, or 255 bytes. (The actual length information may differ depending on the padding scheme.)

Categories

What is a hash function?

A hash function H transforms a variable-size input m into a fixed-size string called the hash value h. Hash functions with this characteristic are used in a variety of general computations. When used in cryptography, however, hash functions generally have a few additional characteristics.

The basic requirements of a cryptographic hash function are as follows.

  • The input can be of any length.
  • The output has a fixed length.
  • H(x) is relatively easy to compute for any given x.
  • H(x) is one-way (one-way).
  • H(x) is collision-free (collision).

A hash function H is called one-way if it is hard to invert. Here, "hard to invert" means that, given a hash value h, it is computationally infeasible to find an x such that H(x)=h. If, for a given message x, it is computationally infeasible to find messages x, y such that H(x)=H(y), H is called a weakly collision-free hash function. A strongly collision-free hash function H is one for which it is computationally infeasible to find two messages x and y such that H(x)=H(y). A hash value concisely represents a long message or computerized document. It can be thought of as a message digest, like a "digital fingerprint" of a long document. Well-known examples of hash functions are MD2, MD5, and SHA. Perhaps the main role of cryptographic hash functions is in preparing digital signatures. Since hash functions are generally faster than digital signature algorithms, it is standard to compute the digital signature of a document by computing a signature on the document's hash value, which is small compared to the document itself. In addition, a digest can be made public without revealing the contents of the document it was derived from. This is important for digital timestamping. Here, by using a hash function, a document can be timestamped without revealing its contents to the timestamping service.

It is an algorithm that generates a message digest (message digest), a new compressed representation of a message, and is also called:

  • Cryptographic checksum (cryptographic checksum).
  • Cryptographic compression (cryptographic compression) algorithm.
  • Message digest (message digest).

Each has slight differences in meaning depending on the context of use, but they are almost the same as a hash function.

Hash collision (Hash collision)

In computer science, a hash collision is a situation in which a hash function produces the same output for two different inputs. Every hash function, however well designed, carries the potential for collisions. Hash collisions should occur relatively rarely or be relatively hard to find. In specific applications where the number of possible inputs is known in advance and is small, it is possible to create a perfect hash function that maps every input to a non-colliding output. However, most hash functions, including cryptographic hash functions, produce outputs in a fixed range from fairly long inputs. Therefore, since such designs accept a far larger range of inputs than the range of hash outputs, collisions always occur.

Double hashing (Double hashing)

Double hashing is a method for resolving hash collisions. A hash collision occurs when two different values have the same hash key. If colliding items are placed in other address spaces of the hash table instead of being managed separately, the question arises of where to place them. Double hashing hashes the value with a different hash function and adds that value to the current address to get a new address. Since the step size on collision then varies with the value, clustering at a single hash value is reduced. It also solves the problem where, with bad luck, collisions keep occurring and search takes a very long time.

See also

Favorite site

Guide

implementation

References

  1. Www.partow.net.zip ↩

author Zer0 sitemap