生成（非常）大的不重复整数序列而无需预先洗牌

Question

背景

我编写了一个简单的媒体客户端/服务器，并希望为每个从客户端发送到服务器的命令生成一个非显而易见的时间值。这些时间戳将包含大量数据（纳秒分辨率，即使它不是真正准确的，由于现代操作系统中计时器采样的限制等），等等。

我在尝试做的事情（在Linux中，使用C语言）是生成一个n位值的一对一序列（暂且假设数据现在存储在128位的整数数组元素中），没有重叠/冲突值。然后，我将以伪随机的128位值/数字作为“盐”，将其应用于时间戳，然后开始向服务器发送命令，递增预先加盐/哈希的值。

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

---

问题

如何使用初始盐值实现这种（非冲突）序列？ 最符合我的目标的最佳方法来自这篇文章，其中指出：

如果选项1对您来说不够“随机”，请使用该全局（32位）计数器的CRC-32哈希。N位整数与其CRC-N之间存在一对一映射（双射），因此仍将保证唯一性。

但是，我不知道：

• 是否可以（有效地）将其扩展到128位数据。
• 如果添加/乘以盐值来为序列提供初始种子是否会破坏它或引入冲突。

---

后续步骤

我意识到我可以使用libssl或类似的东西中的128位随机哈希，但我希望远程服务器能够使用相同的盐值将哈希时间戳转换回其真实值。

谢谢。

- Cloud

---

关于序列：Xorshift128是一个快速的128位伪随机数生成器，其周期为2¹²⁸-1。也就是说，给定任何非零的128位数字，它都会产生另一个非零的128位数字；该序列经过所有128位无符号整数，除了零。所有周期为(2ⁿ)-1的n位PRNG都具有这样的特征，不仅仅是线性同余式。 - Nominal Animal

将您的程序未来化，直到宇宙热寂。我喜欢它。 - 2501

是的，您可以将CRC扩展到128位，并且您可以在维基百科的LFSR页面上找到其系数，但是对于它所实现的功能，有更有效的操作。是的，您可以将您的盐添加或乘以（如果它是奇数）到任何等效函数中，而不会引入冲突（mod 2 ** 128）。只要两个函数都是1:1，链接它们的结果也必须是1:1。我有这样一个函数的想法，但我必须将我的搜索工具扩展到128位，以找到它的良好参数。 - sh1

我不确定我看到了重点。当然，任何旧的128位LFSR都可以，但我认为除了浪费处理器时间之外，这没有任何意义。为什么不直接明文发送呢？如果您需要出于某种原因隐藏它，则需要真正的加密； LFSR根本不提供任何安全性。 - Lee Daniel Crocker

Answer 1

你可以使用线性同余发生器。通过正确的参数，它保证能够生成不重复、有完整周期（即没有碰撞）的序列。

这就是 random(3) 在 TYPE_0 模式下使用的方法。我将其改编成了一个完整的 unsigned int 范围，并且种子可以是任何 unsigned int（请参见下面的示例代码）。

我相信它可以扩展到 64 或 128 位。我会看一下：https://en.wikipedia.org/wiki/Linear_congruential_generator，以了解关于防止碰撞和好的随机性参数的限制。

遵循维基页面的指导方针，您可以生成一个可以接受任何 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;
}

- Craig Estey

---

两个答案都很好(+1)，但是这个更符合我的需求。谢谢大家！ - Cloud

不用谢！顺便说一下，我手头有这段代码，因为我在写这篇文章：https://dev59.com/J5nga4cB1Zd3GeqPTRb2 但是，我陷入了编写一次性参数生成程序的泥潭。它可以使用大量CPU和更多内存，并导致我的系统频繁地交换。我需要重新设计。所以，暂时搁置了。 - Craig Estey

你给我发了一条关于vim/checkpatch问题和我的建议的评论，但是后来这个问题被删除了。你还需要帮助吗[并会重新发布]，还是已经解决了？ - Craig Estey

Answer 2

简短回答是加密。将一组128位的值输入到AES中，并获得不同的一组128位的输出值。由于加密是可逆的，因此使用固定密钥的唯一输入保证了唯一的输出。

加密是输入值与输出值之间可逆的一对一映射，每个集合都是另一个集合的全排列。

由于您很可能不会重复输入，因此ECB模式可能足够，除非您需要更高的安全度。如果反复使用相同的输入，则ECB模式易受攻击，但在这种情况下似乎不是这种情况。

对于长度小于128位的输入，则使用固定填充方法使其达到正确的长度。只要不影响输入的唯一性，填充可以相对灵活。零填充（在内部字段的开头或任意一端）可能已经足够。

我不知道您的详细要求，因此请随意修改我的建议。

- rossum

Answer 3

在线性同余生成器和加密函数之间，有一种哈希函数可以将线性计数转换为可接受的伪随机数。

如果您恰好有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语言，但您可以使用大数字库或编译器扩展使算术运算工作。为了清晰起见，我依赖于编译器扩展。所有操作都依赖于类似于C语言的无符号溢出行为（取任意精度结果的低位）。

- sh1