柳州做网站人员,网站后台上传木马教程,生鲜电商网站建设策划书,做网站 页面自适应BijectiveHash#xff08;双射哈希#xff0c;即可逆哈希#xff09;的设计精髓在于它借鉴了现代密码学和高性能哈希函数中的核心思想#xff0c;但目标并非加密#xff0c;而是实现一种无冲突、可逆的置换#xff08;Permutation#xff09;。可逆哈希是什么#xff0…BijectiveHash双射哈希即可逆哈希的设计精髓在于它借鉴了现代密码学和高性能哈希函数中的核心思想但目标并非加密而是实现一种无冲突、可逆的置换Permutation。可逆哈希是什么用来做什么首先要明确它和我们通常说的用于哈希表或数据校验的哈希函数如 Hash64完全不同。普通哈希是多对一的输入空间远大于输出空间必然存在冲突多个不同输入产生相同输出并且是单向的不可逆。可逆哈希是一对一的输入和输出空间大小相同绝无冲突并且是双向的可逆的。它的主要用途是数据混淆Obfuscation或ID置换。比如你有一组从0开始连续的ID0, 1, 2, ...但你不想直接暴露它们希望把它们变成一组看起来毫无规律、随机分布的ID同时还能在需要时恢复成原始ID。这时可逆哈希就派上用场了。BijectiveHash2x64 设计精髓分析这个函数的设计巧妙地改编自 XXH3 哈希算法中处理小数据块的部分。XXH3为了达到雪崩效应混合极其充分而BijectiveHash则利用了这种充分混合的特性并确保每一步操作都是可逆的。我们来看它的核心代码hash.cc
// ... existing code ...
void BijectiveHash2x64(uint64_t in_high64, uint64_t in_low64, uint64_t seed,uint64_t* out_high64, uint64_t* out_low64) {// Adapted from XXH3_len_9to16_128bconst uint64_t bitflipl /*secret part*/ 0x59973f0033362349U - seed;const uint64_t bitfliph /*secret part*/ 0xc202797692d63d58U seed;Unsigned128 tmp128 Multiply64to128(in_low64 ^ in_high64 ^ bitflipl, 0x9E3779B185EBCA87U);uint64_t lo Lower64of128(tmp128);uint64_t hi Upper64of128(tmp128);lo 0x3c0000000000000U; // (len - 1) 54in_high64 ^ bitfliph;hi in_high64 (Lower32of64(in_high64) * uint64_t{0x85EBCA76});lo ^ EndianSwapValue(hi);tmp128 Multiply64to128(lo, 0xC2B2AE3D27D4EB4FU);lo Lower64of128(tmp128);hi Upper64of128(tmp128) (hi * 0xC2B2AE3D27D4EB4FU);*out_low64 XXH3_avalanche(lo);*out_high64 XXH3_avalanche(hi);
}
// ... existing code ...
设计精髓 1保证无信息丢失的操作要实现可逆最关键的一点是任何操作都不能丢失信息。Multiply64to128这是整个设计的核心。普通的64位乘法 uint64_t * uint64_t 的结果仍然是 uint64_t这会丢失高64位的信息导致不可逆。而 Multiply64to128 将两个64位整数相乘产生一个完整的128位结果Unsigned128完整保留了所有信息。这是可逆性的数学基础。XOR (^) 和加法 ()这些操作本身就是可逆的。a ^ b 可以通过再异或一次 b 恢复 a。a b 可以通过减去 b 恢复 a。设计精髓 2借鉴密码学的“混淆”与“扩散”为了让输出看起来随机它借鉴了密码学中的两个重要概念混淆Confusion让输入和输出之间的关系变得尽可能复杂。通过与seed相关的密钥bitflipl, bitfliph进行XOR操作。与大的素数0x9E3779B185EBCA87U 等相乘。扩散Diffusion让输入的任何一位微小变化都能影响到输出的多位雪崩效应。lo ^ EndianSwapValue(hi)这是一个类似Feistel网络的结构。它用一部分数据hi去改变另一部分数据lo然后再用改变后的lo去影响hi的计算。这种交叉影响能迅速地将输入的变化扩散到整个128位状态中。XXH3_avalanche最后调用XXH3的雪崩函数进行最终的、彻底的混合确保最终输出的随机性。设计精髓 3可逆的雪崩函数XXH3_avalanche 本身是一个单向函数但设计者巧妙地为它实现了一个逆函数 XXH3_unavalanche。
// ... existing code ...
inline uint64_t XXH3_avalanche(uint64_t h64) {h64 ^ h64 37;h64 * 0x165667919E3779F9U;h64 ^ h64 32;return h64;
}inline uint64_t XXH3_unavalanche(uint64_t h64) {h64 ^ h64 32;h64 * 0x8da8ee41d6df849U; // inverse of 0x165667919E3779F9Uh64 ^ h64 37;return h64;
}
// ... existing code ...
这里的关键是 0x8da8ee41d6df849U它是 0x165667919E3779F9U 在模 2^64 意义下的乘法逆元。这意味着 (a * b) * b_inverse a (mod 2^64)。通过找到这个逆元乘法步骤就变得可逆了。而XOR和移位操作的逆运算也相对直接。BijectiveUnhash2x64逆向工程的艺术逆向函数 BijectiveUnhash2x64 的实现完美展示了如何一步步“撤销”正向函数的操作。
// ... existing code ...
void BijectiveUnhash2x64(uint64_t in_high64, uint64_t in_low64, uint64_t seed,uint64_t* out_high64, uint64_t* out_low64) {// Inverted above (also consulting XXH3_len_9to16_128b)const uint64_t bitflipl /*secret part*/ 0x59973f0033362349U - seed;const uint64_t bitfliph /*secret part*/ 0xc202797692d63d58U seed;uint64_t lo XXH3_unavalanche(in_low64);uint64_t hi XXH3_unavalanche(in_high64);// ... a series of inverse multiplications, subtractions, and XORs ...// ... in the exact reverse order of the forward function ...*out_high64 hi;*out_low64 lo;
}
// ... existing code ...
它的每一步都精确地对应 BijectiveHash2x64 的逆操作并严格按照相反的顺序执行先用 XXH3_unavalanche 撤销雪崩混合。用乘法逆元撤销乘法。用减法撤销加法。用XOR撤销XOR。总结设计精髓以无损操作为基石使用扩展精度运算如64-128位乘法来确保计算过程不丢失任何信息这是可逆性的前提。借鉴密码学思想采用Feistel网络、密钥seed混淆、乘大素数等方式实现充分的混淆和扩散让输出看起来随机。依赖数论工具可逆性的实现严重依赖于数论特别是模乘法逆元的计算这是将单向乘法变为双向的关键。结构对称正向和逆向过程在结构上是完全对称的逆向过程是正向过程的完美“镜像”。通过学习这个设计我们可以看到一个看似简单的“可逆哈希”背后融合了计算机体系结构扩展精度乘法、密码学混淆扩散和数论模逆元的深刻原理是高性能计算和算法设计的典范。
