Cryptography
哈希函数
深入理解哈希函数的原理、算法和应用
哈希函数
哈希函数是密码学中的重要工具，它将任意长度的数据转换为固定长度的哈希值，具有单向性、抗碰撞性和雪崩效应等特性。
哈希函数的基本概念
哈希函数（Hash Function）是一种将任意长度的输入数据映射为固定长度输出的数学函数。
输入数据 → 哈希函数 → 哈希值（固定长度）哈希函数的特性
- 确定性：相同输入总是产生相同输出
- 单向性：无法从哈希值反推原始数据
- 抗碰撞性：很难找到两个不同的输入产生相同的哈希值
- 雪崩效应：输入的微小变化导致输出的巨大变化
经典哈希算法
1. MD5（Message Digest Algorithm 5）
// MD5 哈希函数（简化实现）
function md5(message) {
// MD5 使用 4 个 32 位寄存器
let a = 0x67452301;
let b = 0xEFCDAB89;
let c = 0x98BADCFE;
let d = 0x10325476;
// 消息填充
const paddedMessage = padMessage(message);
// 处理 512 位块
for (let i = 0; i < paddedMessage.length; i += 64) {
const block = paddedMessage.slice(i, i + 64);
processBlock(block, a, b, c, d);
}
return toHex(a) + toHex(b) + toHex(c) + toHex(d);
}
// 消息填充
function padMessage(message) {
const bitLength = message.length * 8;
let padded = message + String.fromCharCode(0x80);
// 填充到 448 位（mod 512）
while ((padded.length * 8) % 512 !== 448) {
padded += String.fromCharCode(0x00);
}
// 添加原始长度（64位）
padded += String.fromCharCode(bitLength & 0xFF);
for (let i = 1; i < 8; i++) {
padded += String.fromCharCode((bitLength >>> (i * 8)) & 0xFF);
}
return padded;
}
// 转换为十六进制
function toHex(num) {
return ('00000000' + num.toString(16)).slice(-8);
}注意：MD5 已被认为不安全，不推荐用于安全应用。
2. SHA-1（Secure Hash Algorithm 1）
// SHA-1 哈希函数（简化实现）
function sha1(message) {
// SHA-1 使用 5 个 32 位寄存器
let h0 = 0x67452301;
let h1 = 0xEFCDAB89;
let h2 = 0x98BADCFE;
let h3 = 0x10325476;
let h4 = 0xC3D2E1F0;
// 消息填充
const paddedMessage = padMessage(message);
// 处理 512 位块
for (let i = 0; i < paddedMessage.length; i += 64) {
const block = paddedMessage.slice(i, i + 64);
processBlock(block, h0, h1, h2, h3, h4);
}
return toHex(h0) + toHex(h1) + toHex(h2) + toHex(h3) + toHex(h4);
}注意：SHA-1 也已被认为不安全。
3. SHA-256（Secure Hash Algorithm 256）
// SHA-256 哈希函数（简化实现）
function sha256(message) {
// SHA-256 初始哈希值
const H = [
0x6a09e667, 0xbb67ae85, 0x3c6ef372, 0xa54ff53a,
0x510e527f, 0x9b05688c, 0x1f83d9ab, 0x5be0cd19
];
// SHA-256 常量
const K = [
0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5,
0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5,
// ... 更多常量
];
// 消息填充
const paddedMessage = padMessage(message);
// 处理 512 位块
for (let i = 0; i < paddedMessage.length; i += 64) {
const block = paddedMessage.slice(i, i + 64);
processBlock(block, H, K);
}
return H.map(h => toHex(h)).join('');
}
// 右旋转函数
function rightRotate(value, amount) {
return (value >>> amount) | (value << (32 - amount));
}
// SHA-256 压缩函数
function processBlock(block, H, K) {
// 准备消息调度
const W = new Array(64);
// 前16个字来自块
for (let i = 0; i < 16; i++) {
W[i] = (block[i * 4] << 24) | (block[i * 4 + 1] << 16) |
(block[i * 4 + 2] << 8) | block[i * 4 + 3];
}
// 扩展其余48个字
for (let i = 16; i < 64; i++) {
const s0 = rightRotate(W[i-15], 7) ^ rightRotate(W[i-15], 18) ^ (W[i-15] >>> 3);
const s1 = rightRotate(W[i-2], 17) ^ rightRotate(W[i-2], 19) ^ (W[i-2] >>> 10);
W[i] = (W[i-16] + s0 + W[i-7] + s1) >>> 0;
}
// 初始化工作变量
let a = H[0], b = H[1], c = H[2], d = H[3];
let e = H[4], f = H[5], g = H[6], h = H[7];
// 主循环
for (let i = 0; i < 64; i++) {
const S1 = rightRotate(e, 6) ^ rightRotate(e, 11) ^ rightRotate(e, 25);
const ch = (e & f) ^ (~e & g);
const temp1 = (h + S1 + ch + K[i] + W[i]) >>> 0;
const S0 = rightRotate(a, 2) ^ rightRotate(a, 13) ^ rightRotate(a, 22);
const maj = (a & b) ^ (a & c) ^ (b & c);
const temp2 = (S0 + maj) >>> 0;
h = g; g = f; f = e; e = (d + temp1) >>> 0;
d = c; c = b; b = a; a = (temp1 + temp2) >>> 0;
}
// 更新哈希值
H[0] = (H[0] + a) >>> 0; H[1] = (H[1] + b) >>> 0;
H[2] = (H[2] + c) >>> 0; H[3] = (H[3] + d) >>> 0;
H[4] = (H[4] + e) >>> 0; H[5] = (H[5] + f) >>> 0;
H[6] = (H[6] + g) >>> 0; H[7] = (H[7] + h) >>> 0;
}现代哈希算法
1. SHA-3（Keccak）
SHA-3 使用海绵结构（Sponge Construction），与 SHA-2 家族完全不同。
// SHA-3 海绵结构（简化版）
class Sponge {
constructor(rate, capacity) {
this.rate = rate;
this.capacity = capacity;
this.state = new Array(rate + capacity).fill(0);
}
// 吸收阶段
absorb(input) {
const paddedInput = this.pad(input);
for (let i = 0; i < paddedInput.length; i += this.rate) {
const block = paddedInput.slice(i, i + this.rate);
// XOR 块到状态
for (let j = 0; j < this.rate; j++) {
this.state[j] ^= block[j] || 0;
}
// 应用置换函数
this.permute();
}
}
// 挤压阶段
squeeze(length) {
const output = [];
while (output.length < length) {
// 输出状态的前 rate 位
for (let i = 0; i < this.rate && output.length < length; i++) {
output.push(this.state[i]);
}
// 应用置换函数
this.permute();
}
return output.slice(0, length);
}
// 置换函数（简化版）
permute() {
// 这里应该实现 Keccak-f 置换
// 简化处理，实际需要复杂的位操作
for (let i = 0; i < this.state.length; i++) {
this.state[i] = (this.state[i] * 7 + 13) % 256;
}
}
// 填充函数
pad(input) {
return input.concat([0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x80]);
}
}
// SHA-3-256 实现
function sha3_256(message) {
const sponge = new Sponge(1088, 512); // SHA-3-256 参数
sponge.absorb(message);
const hash = sponge.squeeze(32);
return hash.map(b => ('0' + b.toString(16)).slice(-2)).join('');
}2. BLAKE2
BLAKE2 是 BLAKE 的改进版本，速度更快，安全性更高。
// BLAKE2b 哈希函数（简化版）
function blake2b(message, key = '', outputLength = 64) {
// BLAKE2b 初始向量
const IV = [
0x6a09e667f3bcc908, 0xbb67ae8584caa73b,
0x3c6ef372fe94f82b, 0xa54ff53a5f1d36f1,
0x510e527fade682d1, 0x9b05688c2b3e6c1f,
0x1f83d9abfb41bd6b, 0x5be0cd19137e2179
];
// 初始化状态
const state = [...IV];
// XOR 密钥长度
state[0] ^= outputLength;
state[4] ^= key.length;
// 处理消息
const paddedMessage = padMessage(message);
for (let i = 0; i < paddedMessage.length; i += 128) {
const block = paddedMessage.slice(i, i + 128);
compress(block, state, false);
}
// 最终压缩
const finalBlock = new Array(128).fill(0);
compress(finalBlock, state, true);
// 返回哈希值
return state.slice(0, outputLength / 8)
.map(h => h.toString(16).padStart(16, '0'))
.join('');
}
// BLAKE2b 压缩函数（简化版）
function compress(block, state, final) {
// 这里应该实现完整的 BLAKE2b 压缩函数
// 包括 12 轮的 G 函数调用
// 简化处理
for (let i = 0; i < 8; i++) {
state[i] = (state[i] + block[i * 8]) >>> 0;
}
}哈希函数的应用
1. 密码存储
// 安全的密码哈希
class PasswordHasher {
constructor() {
this.saltLength = 32;
this.iterations = 100000;
}
// 哈希密码
hashPassword(password) {
const salt = crypto.randomBytes(this.saltLength);
const hash = this.pbkdf2(password, salt, this.iterations);
return {
hash: hash.toString('hex'),
salt: salt.toString('hex'),
iterations: this.iterations
};
}
// 验证密码
verifyPassword(password, storedHash, storedSalt, iterations) {
const salt = Buffer.from(storedSalt, 'hex');
const hash = this.pbkdf2(password, salt, iterations);
return crypto.timingSafeEqual(hash, Buffer.from(storedHash, 'hex'));
}
// PBKDF2 实现
pbkdf2(password, salt, iterations) {
let u = crypto.createHmac('sha256', password)
.update(salt)
.update(Buffer.from([0, 0, 0, 1]))
.digest();
let result = u;
for (let i = 1; i < iterations; i++) {
u = crypto.createHmac('sha256', password).update(u).digest();
for (let j = 0; j < result.length; j++) {
result[j] ^= u[j];
}
}
return result;
}
}
// 使用示例
const hasher = new PasswordHasher();
const password = "mySecurePassword123";
const hashed = hasher.hashPassword(password);
console.log(`哈希: ${hashed.hash}`);
console.log(`盐值: ${hashed.salt}`);
const isValid = hasher.verifyPassword(password, hashed.hash, hashed.salt, hashed.iterations);
console.log(`验证结果: ${isValid}`);2. 数字签名
// 数字签名系统
class DigitalSignature {
constructor() {
this.rsaKeys = generateRSAKeys();
}
// 签名消息
sign(message) {
// 1. 计算消息哈希
const hash = sha256(message);
// 2. 使用私钥签名哈希
const signature = rsaSign(hash, this.rsaKeys.privateKey);
return {
message: message,
signature: signature,
algorithm: 'RSA-SHA256'
};
}
// 验证签名
verify(signedMessage) {
// 1. 计算消息哈希
const hash = sha256(signedMessage.message);
// 2. 使用公钥验证签名
const decryptedHash = rsaVerify(signedMessage.signature, this.rsaKeys.publicKey);
// 3. 比较哈希值
return hash === decryptedHash;
}
}3. 区块链和默克尔树
// 默克尔树实现
class MerkleTree {
constructor(leaves) {
this.leaves = leaves.map(leaf => sha256(leaf));
this.tree = this.buildTree();
}
// 构建默克尔树
buildTree() {
let level = this.leaves;
const tree = [level];
while (level.length > 1) {
const nextLevel = [];
for (let i = 0; i < level.length; i += 2) {
const left = level[i];
const right = i + 1 < level.length ? level[i + 1] : left;
const parent = sha256(left + right);
nextLevel.push(parent);
}
level = nextLevel;
tree.push(level);
}
return tree;
}
// 获取根哈希
getRoot() {
return this.tree[this.tree.length - 1][0];
}
// 生成证明
generateProof(leafIndex) {
const proof = [];
let index = leafIndex;
for (let level = 0; level < this.tree.length - 1; level++) {
const isRightNode = index % 2 === 1;
const siblingIndex = isRightNode ? index - 1 : index + 1;
if (siblingIndex < this.tree[level].length) {
proof.push({
hash: this.tree[level][siblingIndex],
isRight: isRightNode
});
}
index = Math.floor(index / 2);
}
return proof;
}
// 验证证明
verifyProof(leaf, proof, root) {
let hash = sha256(leaf);
for (const proofElement of proof) {
if (proofElement.isRight) {
hash = sha256(hash + proofElement.hash);
} else {
hash = sha256(proofElement.hash + hash);
}
}
return hash === root;
}
}
// 使用示例
const data = ["block1", "block2", "block3", "block4"];
const merkleTree = new MerkleTree(data);
console.log(`根哈希: ${merkleTree.getRoot()}`);
const proof = merkleTree.generateProof(1);
const isValid = merkleTree.verifyProof("block2", proof, merkleTree.getRoot());
console.log(`证明验证: ${isValid}`);4. 文件完整性验证
// 文件哈希计算
class FileHasher {
constructor() {
this.chunkSize = 64 * 1024; // 64KB 块
}
// 计算文件哈希
async hashFile(file) {
const reader = new FileReader();
const chunks = [];
return new Promise((resolve, reject) => {
reader.onload = (e) => {
const arrayBuffer = e.target.result;
const hash = this.hashBuffer(arrayBuffer);
resolve(hash);
};
reader.onerror = reject;
reader.readAsArrayBuffer(file);
});
}
// 计算缓冲区哈希
hashBuffer(buffer) {
const uint8Array = new Uint8Array(buffer);
const hash = sha256(Array.from(uint8Array));
return hash;
}
// 分块计算大文件哈希
async hashLargeFile(file) {
const chunks = [];
let offset = 0;
while (offset < file.size) {
const chunk = file.slice(offset, offset + this.chunkSize);
const chunkHash = await this.hashFile(chunk);
chunks.push(chunkHash);
offset += this.chunkSize;
}
// 计算所有块哈希的哈希
return sha256(chunks.join(''));
}
}哈希函数的攻击
1. 碰撞攻击
// 生日攻击（简化版）
function birthdayAttack(hashFunction, hashLength) {
const hashSpace = Math.pow(2, hashLength);
const expectedCollision = Math.sqrt(Math.PI * hashSpace / 2);
console.log(`哈希空间大小: 2^${hashLength}`);
console.log(`预期碰撞点: ${expectedCollision}`);
return expectedCollision;
}
// 示例
birthdayAttack(sha256, 256);2. 彩虹表攻击
// 彩虹表生成（简化版）
class RainbowTable {
constructor() {
this.table = new Map();
}
// 生成彩虹表
generateTable(plaintexts, hashFunction) {
for (const plaintext of plaintexts) {
const hash = hashFunction(plaintext);
this.table.set(hash, plaintext);
}
}
// 查找哈希
lookup(hash) {
return this.table.get(hash);
}
}最佳实践
- 选择安全的算法：使用 SHA-256、SHA-3 或 BLAKE2
- 使用盐值：为密码哈希添加随机盐值
- 多次迭代：使用 PBKDF2、bcrypt 或 Argon2
- 验证完整性：使用 HMAC 进行消息认证
- 定期更新：关注算法安全性的最新研究
- 避免弱哈希：不使用 MD5、SHA-1 等已破解的算法
哈希函数是密码学的基础工具，理解其原理和应用对于构建安全的系统至关重要。