Hash Functions (MD5, SHA)

Hash functions are essential tools in computer science and cryptography. They take an input of arbitrary size (a message, file, or data) and produce a fixed-size output, called a hash value or hash. This hash value serves as a unique "fingerprint" of the input data. Ideally, even a small change to the input should result in a drastically different hash value. MD5 (Message Digest Algorithm 5) and SHA (Secure Hash Algorithm) are two families of widely used hash functions.

Algorithm

Hash functions generally involve a series of operations on the input data, including:

Padding: The input data is padded to ensure its length is a multiple of a specific block size. This often involves appending a '1' bit, followed by a sequence of '0' bits, and then the original length of the message.
Initialization: A fixed-size buffer (or state) is initialized with specific constant values.
Processing in Blocks: The padded input is processed in fixed-size blocks. Each block is combined with the current state using a series of bitwise operations, modular arithmetic, and table lookups. These operations are designed to be highly nonlinear and produce a seemingly random output.
Finalization: After all blocks have been processed, the final state of the buffer is transformed to produce the hash value.

MD5 (Message Digest Algorithm 5)

MD5 produces a 128-bit hash value. It was designed by Ronald Rivest in 1991. While MD5 was widely used, it has been found to have security vulnerabilities (collision weaknesses) and is no longer recommended for cryptographic applications where collision resistance is crucial. However, it can still be used for checksums or non-cryptographic purposes.

SHA (Secure Hash Algorithm)

The SHA family includes several algorithms: SHA-0, SHA-1, SHA-2 (SHA-224, SHA-256, SHA-384, SHA-512), and SHA-3. SHA algorithms were developed by the National Security Agency (NSA) and published as U.S. Federal Information Processing Standards. SHA algorithms generally provide better security than MD5. SHA-256 and SHA-512 are commonly used in various security applications.

SHA-1 produces a 160-bit hash. It has also been found to have weaknesses and is generally being phased out.
SHA-256 produces a 256-bit hash.
SHA-512 produces a 512-bit hash.

Mathematics

Hash functions rely on a combination of mathematical operations to achieve their properties:

Bitwise Operations: These include AND (&), OR (|), XOR (^), and NOT (~). These operations are fast and introduce non-linearity.
Modular Arithmetic: Addition modulo $2^n$ is commonly used, where $n$ is the word size (e.g., 32 or 64 bits).
Circular Shifts (Rotations): Bits are shifted to the left or right, with the shifted-out bits re-inserted at the other end. This helps to spread the influence of each bit.
Boolean Functions: Complex Boolean functions are used to mix the bits in a non-linear way.
Padding: Ensures that messages of different lengths can be processed uniformly. Typically, the message is padded with a '1' bit, followed by zeros, and the original message length.
Initialization Vectors (IVs): The hash computation starts with specific initial values.

Key Properties of Hash Functions:

Preimage Resistance: Given a hash value $h$, it should be computationally infeasible to find any input $x$ such that $hash(x) = h$.
Second Preimage Resistance: Given an input $x$, it should be computationally infeasible to find any other input $y$ such that $hash(y) = hash(x)$.
Collision Resistance: It should be computationally infeasible to find any two distinct inputs $x$ and $y$ such that $hash(x) = hash(y)$.

Time and Memory Complexity

Time Complexity: The time complexity of hash functions like MD5 and SHA is typically linear with respect to the size of the input data. If the input data has length $n$, the hashing process takes $O(n)$ time. This is because the input is processed block by block, and the operations within each block take constant time.
Memory Complexity: The memory complexity is relatively low. Hash functions operate on fixed-size blocks and use a fixed-size internal state. The memory required is independent of the input size and is typically considered $O(1)$.

Problems and Code Examples

Hash functions are not typically used to solve standard algorithmic problems on platforms like Codeforces in the same way as sorting or searching algorithms. They are more relevant in security and data integrity contexts. However, we can illustrate their use with simple examples.

Problem 1: File Checksum (MD5)

Problem Statement: Calculate the MD5 hash of a given string. This can be used as a simple checksum to verify the integrity of a file (represented here as a string).

Input Example:


"Hello, world!"

Output Example:


b10a8db164e0754105b7a99be72e3fe5

C++ Code (MD5 - Simplified for demonstration. For robust MD5, use a library):


#include <iostream>
#include <string>
#include <iomanip>
#include <sstream>
#include <vector>
#include <algorithm>

//  Simplified MD5 for demonstration.  DO NOT USE THIS FOR SECURITY PURPOSES.
//  For real-world MD5, use a dedicated library (e.g., OpenSSL).
std::string simplifiedMD5(const std::string& message) {
    // 1. Padding (very simplified)
    std::string paddedMessage = message;
    while (paddedMessage.length() % 64 != 56) { // Pad to length % 64 == 56
        paddedMessage += '\0';
    }
    paddedMessage += '\x80'; // Append 10000000
    // Append original length (in bits, as 64-bit little-endian integer) - extremely simplified here
    std::string length_hex = "00000000000000" + std::to_string(message.size() * 8);
    paddedMessage += length_hex;


    // 2. Initialize variables (IV - Initialization Vector)
    unsigned int h0 = 0x67452301;
    unsigned int h1 = 0xEFCDAB89;
    unsigned int h2 = 0x98BADCFE;
    unsigned int h3 = 0x10325476;

    // 3. Process the message in 512-bit (64-byte) chunks.  Simplified to one chunk.
    std::vector<unsigned int> words(16, 0); // 16 32-bit words
    for (size_t i = 0; i < paddedMessage.length(); i+=4) {
      words[i/4] = (unsigned int)(paddedMessage[i]) |
                  ((unsigned int)(paddedMessage[i+1]) << 8) |
                  ((unsigned int)(paddedMessage[i+2]) << 16) |
                  ((unsigned int)(paddedMessage[i+3]) << 24);
    }
    // Dummy round
    unsigned int a = h0;
    unsigned int b = h1;
    unsigned int c = h2;
    unsigned int d = h3;

    // Very simplified round function
    for (int i = 0; i < 16; ++i) {
        unsigned int f, g;
        if (i < 4) {
            f = (b & c) | ((~b) & d);
            g = i;
        } else if (i < 8) {
            f = (b & d) | (c & (~d));
            g = (5*i + 1) % 16;
        } else if (i < 12) {
            f = b ^ c ^ d;
            g = (3*i + 5) % 16;
        } else {
            f = c ^ (b | (~d));
            g = (7*i) % 16;
        }

        unsigned int temp = d;
        d = c;
        c = b;
        b = b + ((a + f + 0xd76aa478 + words[g]) & 0xFFFFFFFF); // very simplified
        a = temp;
    }

    h0 = h0 + a;
    h1 = h1 + b;
    h2 = h2 + c;
    h3 = h3 + d;

    // 4.  Finalization (Produce the hash value)
    std::stringstream ss;
    ss << std::hex << std::setfill('0')
       << std::setw(8) << h0
       << std::setw(8) << h1
       << std::setw(8) << h2
       << std::setw(8) << h3;
    return ss.str();
}

int main() {
    std::string message = "Hello, world!";
    std::string md5_hash = simplifiedMD5(message);
    std::cout << md5_hash << std::endl;
    return 0;
}

Problem 2: SHA-256 Hashing

Problem Statement: Calculate the SHA-256 hash of a given string. Again, for demonstration and conceptual understanding. For real-world applications, use a robust library.

Input Example:


"This is a test string."

Output Example:


d14a028c2a3a2bc9476102bb288234c415a2b01f9cab3941508e50e837b56c26

C++ Code (SHA-256 - Simplified for demonstration. Use a library for real SHA-256):


#include <iostream>
#include <string>
#include <iomanip>
#include <sstream>
#include <vector>
#include <algorithm>

// Simplified SHA-256 for demonstration.  DO NOT USE THIS FOR SECURITY PURPOSES.
// For real-world SHA-256, use a dedicated library (e.g., OpenSSL).
std::string simplifiedSHA256(const std::string& message) {
    // 1. Padding (very simplified)
    std::string paddedMessage = message;
    while (paddedMessage.length() % 64 != 56) {
        paddedMessage += '\0';
    }
    paddedMessage += '\x80';
    std::string length_hex = "00000000000000" + std::to_string(message.size() * 8);
    paddedMessage += length_hex;

    // 2. Initialize variables (IV)
    unsigned int h0 = 0x6a09e667;
    unsigned int h1 = 0xbb67ae85;
    unsigned int h2 = 0x3c6ef372;
    unsigned int h3 = 0xa54ff53a;
    unsigned int h4 = 0x510e527f;
    unsigned int h5 = 0x9b05688c;
    unsigned int h6 = 0x1f83d9ab;
    unsigned int h7 = 0x5be0cd19;

    // 3. Process the message in 512-bit chunks.  Simplified to one chunk.
    std::vector<unsigned int> words(64, 0);
    for (size_t i = 0; i < paddedMessage.length(); i+=4) {
      words[i/4] = (unsigned int)(paddedMessage[i]) |
                  ((unsigned int)(paddedMessage[i+1]) << 8) |
                  ((unsigned int)(paddedMessage[i+2]) << 16) |
                  ((unsigned int)(paddedMessage[i+3]) << 24);
    }

    // Dummy round
    unsigned int a = h0;
    unsigned int b = h1;
    unsigned int c = h2;
    unsigned int d = h3;
    unsigned int e = h4;
    unsigned int f = h5;
    unsigned int g = h6;
    unsigned int h = h7;

    // Very simplified round
    for (int i = 0; i < 64; ++i) {
        unsigned int S1 = (e >> 6) ^ (e >> 11) ^ (e >> 25) ^ (e << 26) ^ (e << 21) ^ (e << 7);
        unsigned int ch = (e & f) ^ ((~e) & g);
        unsigned int temp1 = h + S1 + ch + 0x428a2f98 + words[i]; // Very simplified
        unsigned int S0 = (a >> 2) ^ (a >> 13) ^ (a >> 22) ^ (a << 30) ^ (a << 19) ^ (a << 10);
        unsigned int maj = (a & b) ^ (a & c) ^ (b & c);
        unsigned int temp2 = S0 + maj;

        h = g;
        g = f;
        f = e;
        e = d + temp1;
        d = c;
        c = b;
        b = a;
        a = temp1 + temp2;
    }

    h0 = h0 + a;
    h1 = h1 + b;
    h2 = h2 + c;
    h3 = h3 + d;
    h4 = h4 + e;
    h5 = h5 + f;
    h6 = h6 + g;
    h7 = h7 + h;

    // 4. Finalization
    std::stringstream ss;
    ss << std::hex << std::setfill('0')
       << std::setw(8) << h0
       << std::setw(8) << h1
       << std::setw(8) << h2
       << std::setw(8) << h3
       << std::setw(8) << h4
       << std::setw(8) << h5
       << std::setw(8) << h6
       << std::setw(8) << h7;
    return ss.str();
}

int main() {
    std::string message = "This is a test string.";
    std::string sha256_hash = simplifiedSHA256(message);
    std::cout << sha256_hash << std::endl;
    return 0;
}

Important Note: The C++ code provided for MD5 and SHA-256 is *highly* simplified for demonstration purposes. It is NOT suitable for any security-sensitive applications. For real-world use, you should use a well-established cryptographic library such as OpenSSL, which provides robust and secure implementations of these hash functions.

Ant In Loop

Sorting Algorithms

Searching Algorithms

Mathematical Algorithms

Graph Algorithms

Dynamic Programming

String Algorithms

Data Structure

Backtracking

Greedy Algorithms

Bit Manipulation

Geometry Algorithms

Advanced Techniques

Recurrence & Divide and Conquer

Cryptographic Algorithms

Core Problem Solving Skills