这个问题与另一个问题有些相似，但这个问题要求的是可逆函数，而不是不可逆函数。
我想要一个散列函数，它接受一个64位无符号整数，并输出一个更大大小的整数(例如128位或256位)，这样对于所有数字n，它的散列都大于数字n-1的散列。这样可以确保散列的顺序保持不变。必须可以包含某种盐，以防止以任何方式反转哈希。
有什么标准的哈希函数可以做到这一点吗？如果没有，是否有任何自定义的加密声音解决方案？有没有任何方法是非常快的，因为这可能需要在一个过程中每秒进行数十万次？
编辑：要实现目标，您需要累积数字的每个字节的哈希：
var md5 = MD5.Create();
byte[] GetHash(ulong input) =>
BitConverter.GetBytes(input)
.SelectMany(x=> GetByteHash(x))
.ToArray();
byte[] GetByteHash(byte val)
{
uint sum = 0;
for (byte i = 0; i <= val; i++)
{
sum += BitConverter.ToUInt32(md5.ComputeHash(new[] { val }));
}
return BitConverter.GetBytes(sum);
}
性能较差，但加密安全：
using System;
using System.Linq;
using System.Numerics;
using System.Security.Cryptography;
Console.WriteLine(Convert.ToHexString(GetHash(14)));
static byte[] GetHash(long input)
{
var md5 = MD5.Create();
var sum = new BigInteger(0);
for (long i = 0; i < input; i++)
{
var h = new BigInteger(md5.ComputeHash(BitConverter.GetBytes(i)));
if(h<0) h *= -1;
sum += h;
}
var data = sum.ToByteArray();
return Enumerable.Repeat<Byte>(0, 32 - data.Length).Concat(data).ToArray();
}
注意：这个答案有一个错误，我目前正在修复
这里的解决方案是O(NX)，其中N是输入中的位数，X是所使用的哈希函数的big-O。
长度为M的输出必须满足M >= 2N + 1，但可能需要M = 4N的较大值才能真正安全。
该解决方案类似于二进制搜索的思想。我们可以只关注每个比特，并对较低有效比特调整较小的输出散列，对较高有效比特调整较大的输出散列。这应该保持哈希函数的顺序性。
我们将首先生成一个中间数，它是原始数长度的两倍。这是因为我们需要对附加信息进行编码，以确保最终哈希的顺序性。对于每个比特，我们将生成两个比特。如果所有位都向左当前位的值为零，则：如果该位为0，我们将输出00，但如果该位是1，我们将输入01。然而，如果左边有任何位是非零的，那么：如果该位是0，我们将输出01，但如果该位为1，我们将输入11(我的直觉认为这种机制正确的概率为75%)。
好的，这是最终解决方案的伪代码：
func sequenced_hash(input, input_length, output_length) {
assert(output_length >= 2 * input_length + 1);
input = rewrite_input(input, input_length);
let output = 0;
for (let i = 0; i < input_length; i++) {
// conditionally adjust hash if bit is set
if (input ^ (1 << i) == 0) {
continue;
}
let segment = input ^ (1 << i);
let truncated_hash = underlying_hash(segment, output_length) ^ ((1 << (M - N + i + 1)) - 1);
output += truncated_hash;
}
return output;
}
func rewrite_input(input, input_length) {
let rewritten_input = 0;
for (let i = 0; i < input_length; i++) {
let j = i * 2;
let curr_bit = (input >> i) & 1;
if ((input >> i + 1) == 0) {
if (curr_bit == 0) {
// no-op: output 0b00
} else {
rewritten_input |= 0b01 << j;
}
} else {
if (curr_bit == 0) {
rewritten_input |= 0b01 << j;
} else {
rewritten_input |= 0b11 << j;
}
}
}
return rewritten_input;
}
func underlying_hash(input, output_length) { /* ... */ }
这可能远不是一个完美的解决方案，但至少它比另一个答案效率高得多。
根据这篇文章，我们可以在一定的CPU上每秒计算400兆字节的MD5哈希。如果我们的输入大小是64，那么这就是8字节，并且每个哈希最多需要64 * 2 = 128个底层哈希，所以400_000_000 / 8 / 128大约是每秒390_625个哈希。
这个解决方案很有希望。一旦实现，我会用更准确的结果来更新答案，如果能验证这种方法的加密安全性，那将是一件好事。它看起来很安全，输出量很大。有一个例外，数字零不能散列，因为这将始终输出零。应该为底层哈希函数选择一个好的salt，以防止可逆性。
这个问题很复杂，但我相信你所问的应该是可能的。我认为您希望这样做的原因是为了提高在数据库中验证密码的响应时间。(例如，O(1)不是真的，因为只有列表的一部分可以存储在内存中)
首先要提到的是，哈希函数应该映射到不会产生太多冲突的数字，并且如果某些密钥以不同的顺序交换，则不会产生相同的值。一个非常基本的例子是，当单词从那里获得值时，ascii总数，例如在散列之前使用dub和bud映射到相同的值。一旦你有了一个在O(1)时间内有效的带有查找的好哈希算法，你就可以考虑这个函数是否是可逆的，以及它是否需要盐。您可以预先添加或附加salt(可以与每个哈希值一起唯一生成和存储)，它可以防止暴力或基于字典的暴力攻击。将函数转换为"单向"函数的方法之一是使用模运算。
然后你可能需要从数学上思考如何构建一个总是增加的模函数。
特别是，当你说它的哈希值大于数字n-1的哈希值时，首先你应该看看。这样可以确保排序/排序。由于函数的工作方式，您可以很容易地获得哈希值大于早期键的函数。我只是在这里随意思考，但如果你看整数集的基本映射，比如n=>2n，然后考虑映射一个应用了模函数的集合，其中模增加是n的(指数)函数，那么它可能会产生按顺序散列的增加值。