生成(非常)大的非重复整数序列,无需预先混洗

背景

我有一个简单的媒体客户端/服务器,我写了,我想产生一个非显而易见的时间价值,我发送每个命令从客户端到服务器。 时间戳会有相当的数据(纳秒分辨率,即使由于现代操作系统中定时器采样的限制,它不是真正准确的),等等。

我试图做的(在Linux上,C语言)是生成一个n位值的序列(让我们假设数据现在存储在128位的int数组元素中),没有重叠/碰撞值。 然后我将一个伪随机的128位值/数字作为“salt”,将其应用于时间戳,然后开始向服务器发送命令,递增预先腌制/预先哈希的值。

时间戳大小的原因是因为时间戳可能需要适应非常长的时间。


我怎么能用一个初始的盐值来完成这个序列(不碰撞)呢? 听起来和我的目标一致的最好的方法是从这篇文章中注意到 :

如果选项1对您来说不够“随机”,则使用全局(32位)计数器的CRC-32哈希值。 在N位整数和它们的CRC-N之间存在1对1的映射(双射),所以唯一性仍将得到保证。

但是,我不知道:

  • 如果可以(有效地)扩展到128位数据。
  • 如果某种加法/乘法的盐值为序列提供初始种子,将会扰乱它或引入冲突。

跟进

我意识到我可以使用来自libssl或类似的128位随机哈希,但我希望使用相同的盐值的远程服务器能够将散列的时间戳转换回它们的真实值。

谢谢。

Solutions Collecting From Web of "生成(非常)大的非重复整数序列,无需预先混洗"

你可以使用线性同余发生器 。 使用正确的参数,保证产生具有全周期(即没有碰撞)的非重复序列[唯一]序列。

这是random(3)TYPE_0模式下使用的。 我适应了一个完整的unsigned int范围和种子可以是任何unsigned int (见我下面的示例代码)。

我相信它可以扩展到64或128位。 我会看看: https : //en.wikipedia.org/wiki/Linear_congruential_generator ,看看有关参数的约束,以防止碰撞和良好的随机性。

按照wiki页的指导原则,你可以产生一个可以取任何 128位的值作为种子,直到所有可能的128位的数字都被生成为止。

您可能需要编写一个程序来生成合适的参数对,然后测试它们的“最佳”随机性。 这将是一次性的操作。

一旦你得到了他们,只需将这些参数插入到您的实际应用程序中的等式中。


以下是我在寻找类似的东西时玩过的一些代码:

 // _prngstd -- get random number static inline u32 _prngstd(prng_p prng) { long rhs; u32 lhs; // NOTE: random is faster and has a _long_ period, but it _only_ produces // positive integers but jrand48 produces positive _and_ negative #if 0 rhs = jrand48(btc->btc_seed); lhs = rhs; #endif // this has collisions #if 0 rhs = rand(); PRNG_FLIP; #endif // this has collisions because it defaults to TYPE_3 #if 0 rhs = random(); PRNG_FLIP; #endif // this is random in TYPE_0 (linear congruential) mode #if 0 prng->prng_state = ((prng->prng_state * 1103515245) + 12345) & 0x7fffffff; rhs = prng->prng_state; PRNG_FLIP; #endif // this is random in TYPE_0 (linear congruential) mode with the mask // removed to get full range numbers // this does _not_ produce overlaps #if 1 prng->prng_state = ((prng->prng_state * 1103515245) + 12345); rhs = prng->prng_state; lhs = rhs; #endif return lhs; } 

简短的答案是加密。 用一组128位的值将它们送入AES并获得一组不同的128位值。 由于加密是可逆的,输出保证唯一的唯一输入与一个固定的密钥。

加密是输入值到输出值的可逆的一对一映射,每个集合是另一个的完全排列。

既然你大概不会重复你的输入,那么ECB模式可能就足够了,除非你想要更高的安全性。 如果使用相同的输入重复使用ECB模式,这种情况在这里看起来并不是这样。

对于短于128位的输入,然后使用固定的填充方法使它们长度合适。 只要输入的唯一性不受影响,填充就可以合理灵活。 零填充,在任何一端(或在内部字段的开始)可能就足够了。

我不知道你的详细要求,所以随时修改我的建议。

在线性同余发生器和加密函数之间的某处,可以将线性计数转换为可通过的伪随机数。

如果您碰巧有128位整数类型(例如,为64位目标构建GCC中的__int128 ),或者愿意手动实现如此长的乘法,那么您可以扩展SplitMix64中使用的构造 。 我做了一个相当肤浅的搜索,并提出了以下参数:

 uint128_t mix(uint128_t x) { uint128_t m0 = (uint128_t)0xecfb1b9bc1f0564f << 64 | 0xc68dd22b9302d18d; uint128_t m1 = (uint128_t)0x4a4cf0348b717188 << 64 | 0xe2aead7d60f8a0df; x ^= x >> 59; x *= m0; x ^= x >> 60; x *= m1; x ^= x >> 84; return x; } 

和它的逆向:

 uint128_t unmix(uint128_t x) { uint128_t im0 = (uint128_t)0x367ce11aef44b547 << 64 | 0x424b0c012b51d945; uint128_t im1 = (uint128_t)0xef0323293e8f059d << 64 | 0x351690f213b31b1f; x ^= x >> 84; x *= im1; x ^= x >> 60 ^ x >> (2 * 60); x *= im0; x ^= x >> 59 ^ x >> (2 * 59); return x; } 

我不确定你是否想要一个随机序列,或者混淆一个任意时间戳的方式(因为你说你想解码这些值,它们必须比一个线性计数器更有趣),但是一个只是从另一个足够:

 uint128_t encode(uint128_t time, uint128_t salt) { return mix((time + 1) * salt); } uint128_t generate(uint128_t salt) { static uint128_t t = 0; return encode(t++, salt); } static uint128_t inv(uint128_t d) { uint128_t i = d; while (i * d != 1) { i *= 2 - i * d; } return i; } uint128_t decode(uint128_t etime, uint128_t salt) { return unmix(etime) * inv(salt) - 1; } 

请注意, salt选择2 127个非重复的128位值序列之一(因为salt必须是奇数,所以我们丢失一位),但是有(2 128 )! 可能已经产生的序列。 在其他地方,我正在扩展参数化,以便可以访问更多的这些序列,但是我开始用上述方法来增加序列的随机性,以隐藏参数可能选择不那么随机的任何问题但可证明不同的)序列。

显然uint128_t不是一个标准类型,所以我的答案不是C,但是可以使用一个bignumber库或一个编译器扩展来进行算术运算。 为了清楚起见,我依赖于编译器扩展。 所有的操作都依赖于类C的无符号溢出行为(取任意精度结果的低位)。