BÃO NĂM NAY (2025) NHỚ MỘT VỤ LỤT NĂM XƯA (1971) VỚI TỔ TOÁN ĐẠI HỌC BÁCH KHOA HÀ NỘI…
HỌC SUỐT ĐỜI - LIFELONG LEARNING
COGITO ERGO SUM - Je pense, donc je suis - Tôi tư duy, vậy là tôi tồn tại! - RENÉ DESCARTES (Một Triết gia và Nhà Toán học Pháp)
Thứ Ba, 21 tháng 10, 2025
Thứ Hai, 18 tháng 9, 2023
HÀM BĂM - HASH FUNCTION
GIỚI THIỆU VỀ HÀM BĂM
Hàm băm thông dụng là một phép biến đổi một dãy "số" hoặc một dã "số và chữ cái" thành một số nguyên (khá bé):
H(k) = n
Biến đổi hàm băm là một đối một một chiều, nghĩa là nếu có k1 =/= k2 thì chắc chắn n1 =/n2 nhưng điều ngược lại không chắc đúng.
A Hash Function is a function that converts a given numeric or alphanumeric key to a small practical integer value. The mapped integer value is used as an index in the hash table. In simple terms, a hash function maps a significant number or string to a small integer that can be used as the index in the hash table.
The pair is of the form (key, value), where for a given key, one can find a value using some kind of a “function” that maps keys to values. The key for a given object can be calculated using a function called a hash function. For example, given an array A, if i is the key, then we can find the value by simply looking up A[i].
- Division Method.
- Mid Square Method.
- Folding Method.
- This method is quite good for any value of M.
- This method leads to poor performance since consecutive keys map to consecutive hash values in the hash table.
- Square the value of the key k i.e. k2
- The performance of this method is good as most or all digits of the key value contribute to the result. This is because all digits in the key contribute to generating the middle digits of the squared result.
- The size of the key is one of the limitations of this method, as the key is of big size then its square will double the number of digits.
- Divide the key-value k into a number of parts i.e. k1, k2, k3,….,kn, where each part has the same number of digits except for the last part that can have lesser digits than the other parts.
- Choose a constant value A such that 0 < A < 1.
- Multiply the key value with A.
- Extract the fractional part of kA.
- Multiply the result of the above step by the size of the hash table i.e. M.
MỘT SỐ HÀM BĂM THÔNG DỤNG
Commonly used hash functions
Hash functions are widely used in computer science and cryptography for a variety of purposes, including data integrity, digital signatures, password storage, and more.
There are many types of hash functions, each with its own strengths and weaknesses. Here are a few of the most common types:
1. SHA (Secure Hash Algorithm): SHA is a family of cryptographic hash functions designed by the National Security Agency (NSA) in the United States. The most widely used SHA algorithms are SHA-1, SHA-2, and SHA-3. Here’s a brief overview of each:
- SHA-1: SHA-1 is a 160-bit hash function that was widely used for digital signatures and other applications. However, it is no longer considered secure due to known vulnerabilities.
- SHA-2: SHA-2 is a family of hash functions that includes SHA-224, SHA-256, SHA-384, and SHA-512. These functions produce hash values of 224, 256, 384, and 512 bits, respectively. SHA-2 is widely used in security protocols such as SSL/TLS and is considered secure.
2. CRC (Cyclic Redundancy Check): CRC is a non-cryptographic hash function used primarily for error detection in data transmission. It is fast and efficient but is not suitable for security purposes. The basic idea behind CRC is to append a fixed-length check value, or checksum, to the end of a message. This checksum is calculated based on the contents of the message using a mathematical algorithm, and is then transmitted along with the message.
- SHA-3: SHA-3 is the latest member of the SHA family and was selected as the winner of the NIST hash function competition in 2012. It is designed to be faster and more secure than SHA-2 and produces hash values of 224, 256, 384, and 512 bits.
When the message is received, the receiver can recalculate the checksum using the same algorithm, and compare it with the checksum transmitted with the message. If the two checksums match, the receiver can be reasonably certain that the message was not corrupted during transmission.
The specific algorithm used for CRC depends on the application and the desired level of error detection. Some common CRC algorithms include CRC-16, CRC-32, and CRC-CCITT.
3. MurmurHash: MurmurHash is a fast and efficient non-cryptographic hash function designed for use in hash tables and other data structures. It is not suitable for security purposes as it is vulnerable to collision attacks.
4. BLAKE2: BLAKE2 is a cryptographic hash function designed to be fast and secure. It is an improvement over the popular SHA-3 algorithm and is widely used in applications that require high-speed hashing, such as cryptocurrency mining.
BLAKE2 is available in two versions: BLAKE2b and BLAKE2s. BLAKE2b is optimized for 64-bit platforms and produces hash values of up to 512 bits, while BLAKE2s is optimized for 8- to 32-bit platforms and produces hash values of up to 256 bits.
5. Argon2: Argon2 is a memory-hard password hashing function designed to be resistant to brute-force attacks. It is widely used for password storage and is recommended by the Password Hashing Competition. The main goal of Argon2 is to make it difficult for attackers to crack passwords by using techniques such as brute force attacks or dictionary attacks. It achieves this by using a computationally-intensive algorithm that makes it difficult for attackers to perform large numbers of password guesses in a short amount of time.
Argon2 has several key features that make it a strong choice for password hashing and key derivation:
- Resistance to parallel attacks: Argon2 is designed to be resistant to parallel attacks, meaning that it is difficult for attackers to use multiple processing units, such as GPUs or ASICs, to speed up password cracking.
- Memory-hardness: Argon2 is designed to be memory-hard, meaning that it requires a large amount of memory to compute the hash function. This makes it more difficult for attackers to use specialized hardware to crack passwords.
Resistance to side-channel attacks: Argon2 is designed to be resistant to side-channel attacks, such as timing attacks or power analysis attacks, that could be used to extract information about the password being hashed.
- Customizable: Argon2 is highly customizable, and allows users to adjust parameters such as the memory usage, the number of iterations, and the output length to meet their specific security requirements.
6. MD5 (Message Digest 5): MD5 is a widely-used cryptographic hash function that produces a 128-bit hash value. It is fast and efficient but is no longer recommended for security purposes due to known vulnerabilities. The basic idea behind MD5 is to take an input message of any length, and produce a fixed-length output, known as the hash value or message digest. This hash value is unique to the input message, and is generated using a mathematical algorithm that involves a series of logical operations, such as bitwise operations, modular arithmetic, and logical functions.
MD5 is widely used in a variety of applications, including digital signatures, password storage, and data integrity checks. However, it has been shown to have weaknesses that make it vulnerable to attacks. In particular, it is possible to generate two different messages with the same MD5 hash value, a vulnerability known as a collision attack.
There are many other types of hash functions, each with its own unique features and applications. The choice of hash function depends on the specific requirements of the application, such as speed, security, and memory usage.
Last Updated : 09 Mar, 2023
Thứ Tư, 7 tháng 6, 2023
THƯƠNG MẠI ĐIỆN TỬ TRONG THỜI ĐẠI SỐ