哈希与密码学：安全的数学

加密哈希函数的核心性质：雪崩效应（输入 1 bit 变化 → 输出 50% bit 变化）+ 抗原像 + 抗碰撞。

哈希函数的数学性质

package main

import (
    "crypto/hmac"
    "crypto/sha256"
    "fmt"
)

func main() {
    // SHA-256：雪崩效应演示
    h1 := sha256.Sum256([]byte("hello"))
    h2 := sha256.Sum256([]byte("hellp"))  // 只改了最后一个字母

    // 计算两个哈希有多少 bit 不同
    diff := 0
    for i := 0; i < 32; i++ {
        xor := h1[i] ^ h2[i]
        for xor != 0 {
            diff += int(xor & 1)
            xor >>= 1
        }
    }
    fmt.Printf("256 bits 中有 %d bits 不同（%.1f%%）\n", diff, float64(diff)/256*100)
    // 应该接近 50%

    // HMAC-SHA256：消息认证码
    key := []byte("secret-key")
    mac := hmac.New(sha256.New, key)
    mac.Write([]byte("payload data"))
    sig := mac.Sum(nil)
    fmt.Printf("HMAC: %x\n", sig)

    // 验证：使用 hmac.Equal 防止时序攻击
    mac2 := hmac.New(sha256.New, key)
    mac2.Write([]byte("payload data"))
    fmt.Println("验证通过:", hmac.Equal(sig, mac2.Sum(nil)))
}

密码存储：为什么需要慢哈希

存储密码不能用 SHA-256——现代 GPU 每秒能跑 10 亿次 SHA-256，暴力破解 8 位密码只需几分钟。bcrypt 和 argon2 通过可调节的计算代价，让每次哈希需要 100ms+，GPU 暴力破解变得不切实际。慢是安全特性，不是 bug。

package main

import (
    "fmt"
    "time"
    "crypto/sha256"
    "golang.org/x/crypto/bcrypt"
)

func main() {
    password := []byte("mypassword123")

    // SHA-256：极快（不适合密码）
    t1 := time.Now()
    for i := 0; i < 1_000_000; i++ {
        sha256.Sum256(password)
    }
    fmt.Printf("SHA-256 x 100万次: %v（约 %.0f ns/次）\n",
        time.Since(t1), float64(time.Since(t1).Nanoseconds())/1_000_000)

    // bcrypt：故意慢（cost=12 约 200ms）
    t2 := time.Now()
    hash, _ := bcrypt.GenerateFromPassword(password, 12)
    fmt.Printf("bcrypt cost=12: %v\n", time.Since(t2))

    // 验证密码
    err := bcrypt.CompareHashAndPassword(hash, password)
    fmt.Println("密码正确:", err == nil)
    err = bcrypt.CompareHashAndPassword(hash, []byte("wrong"))
    fmt.Println("错误密码:", err != nil)
}

哈希表的数学：装载因子与冲突

哈希表的负载因子 α = n/m（n 个键，m 个槽）决定了冲突概率。链式哈希的平均查找时间是 Θ(1 + α)，所以要控制 α < 0.75（Go 的 map 默认阈值）。哈希函数的关键要求是均匀分布——把键均匀散布到 m 个槽里。

package main

import "fmt"

// 多项式哈希（Polynomial Rolling Hash）
// 用于字符串哈希、Rabin-Karp 算法
func rollingHash(s string, base, mod int) int {
    h := 0
    for _, c := range s {
        h = (h*base + int(c)) % mod
    }
    return h
}

// Rabin-Karp 字符串搜索：O(n+m) 平均
func rabinKarp(text, pattern string) []int {
    n, m := len(text), len(pattern)
    if m > n { return nil }
    base, mod := 31, 1_000_000_007

    // 计算 base^(m-1) % mod
    pow := 1
    for i := 0; i < m-1; i++ { pow = pow * base % mod }

    pHash := rollingHash(pattern, base, mod)
    tHash := rollingHash(text[:m], base, mod)

    result := []int{}
    for i := 0; i <= n-m; i++ {
        if tHash == pHash && text[i:i+m] == pattern {
            result = append(result, i)
        }
        if i < n-m {
            tHash = (tHash - int(text[i])*pow%mod + mod) % mod
            tHash = (tHash*base + int(text[i+m])) % mod
        }
    }
    return result
}

func main() {
    positions := rabinKarp("hello world hello go", "hello")
    fmt.Println("找到 'hello' 在位置:", positions)  // [0 12]
}

密码学是数论和计算机科学的婚礼礼物——一边用数学证明安全，一边用工程实现保护。

— Bruce Schneier《应用密码学》