Hash Functions

 

Hash Functions: A Number Theory Perspective

Introduction

A hash function is a mathematical function that takes an input of arbitrary length and maps it to a fixed-size output, called a hash value or digest. Hash functions are fundamental in computer science and cryptography, playing a vital role in data integrity, authentication, digital signatures, and secure storage.

From a number theory viewpoint, hash functions rely heavily on modular arithmetic, prime numbers, finite fields, and algebraic structures, making them an interesting and practical application of abstract mathematics.

---

What Is a Hash Function?

Formally, a hash function is a function:

$$h : \{0,1\}^* \rightarrow \{0,1\}^n$$

that maps an input of any length to a fixed-length output of $n$ bits.

Key Characteristics

A good hash function should satisfy:

1. Determinism – The same input always produces the same output

2. Efficiency – The hash is computed quickly

3. Uniformity – Outputs are evenly distributed

4. Avalanche Effect – A small change in input produces a large change in output

---

Hash Functions and Number Theory

Hash functions are not random; they are carefully designed deterministic functions using mathematical operations such as:

• Modular arithmetic

• Large primes

• Bitwise operations

• Finite fields (Galois fields)

• Polynomial arithmetic

These ideas ensure diffusion, confusion, and collision resistance.

---

Simple Hashing Using Modular Arithmetic

A basic example (not cryptographically secure):

$$h(x) = x \bmod p$$

where $p$ is a prime.

Example

Let $p = 101$ and input:

$$x = 123456$$
$$h(x) = 123456 \bmod 101 = 34$$

🔴 This function is simple but not secure, because collisions are easy to find.

---

Hashing Strings: Polynomial Rolling Hash

A more refined mathematical approach is the polynomial hash, commonly used in algorithms.

$$h(s) = \sum_{i=0}^{n-1} s_i \cdot p^i \bmod m$$

where:

• $s_i$ is the numerical value of the $i$-th character

• $p$ is a small prime (e.g., 31)

• $m$ is a large prime

Example

For the string "abc":

$$h = 97\cdot31^0 + 98\cdot31^1 + 99\cdot31^2 \bmod m$$

Polynomial hashing is efficient and widely used in string matching algorithms.

---

Cryptographic Hash Functions

Cryptographic hash functions are designed to be secure against adversaries.

Essential Security Properties

1. Preimage Resistance
   Given $h(x)$, it is computationally infeasible to find $x$
   

2. Second Preimage Resistance
   Given $x$, it is hard to find $y \neq x$ such that $h(x) = h(y)$
   

3. Collision Resistance
   It is infeasible to find $x \neq y$ such that:

   $$h(x) = h(y)$$
   

---

Hash Functions and the Pigeonhole Principle

Since hash functions map infinite inputs to finite outputs:

$$|\text{Input space}| > |\text{Output space}|$$

➡️ Collisions must exist

The goal is to make finding collisions computationally infeasible, not impossible.

---

Popular Cryptographic Hash Functions

Hash Function	Output Size	Status
MD5	128 bits	Broken
SHA-1	160 bits	Broken
SHA-256	256 bits	Secure
SHA-3	256 bits	Secure

---

Role of Modular Arithmetic in SHA Algorithms

Modern hash functions like SHA-256 rely on:

• Modular addition modulo $2^{32}$
  

• Bit rotations and shifts

• Boolean functions

• Constants derived from prime numbers

📌 Example:

$$(a + b) \bmod 2^{32}$$

ensures controlled overflow and diffusion.

---

Hash Functions vs Encryption

Hash Function	Encryption
One-way	Two-way
No key required	Key required
Used for integrity	Used for confidentiality

---

Applications of Hash Functions

• Password storage (hashed + salted)

• Digital signatures

• Blockchain and cryptocurrencies

• Data integrity checks

• Hash tables and indexing

---

Why Hash Functions Matter in Number Theory

Hash functions provide a real-world application of:

• Modular arithmetic

• Prime numbers

• Finite fields

• Probability theory

• Computational hardness assumptions

They beautifully connect pure mathematics with practical computing.

---

Conclusion

Hash functions are a cornerstone of modern computing and cryptography. While they may appear as black-box algorithms, their foundations are deeply rooted in number theory and algebra. Understanding these mathematical principles allows students to appreciate both the power and limitations of hash-based systems.