六个月前，我想用一些不同的架构创建最好的伪随机数生成器（PRNG）。我认为开始会很容易，并且随着您的工作，任务将逐渐变得更加复杂。我想如果我能足够快地学习所有内容以应付最困难的事情。令我惊讶的是，复杂度并没有线性增加。卡方字节测试证明非常困难！后来，通过顽固的测试同样困难。我发布了当前结果以了解还有哪些其他问题在等待着我。但是，那时PractRand测试失败。然后，通过BigCrush测试非常困难。然后，通过PractRand时很难传输32 TB的数据。速度已经成为问题。创建每秒产生10兆字节的设计还远远不够，因为通过PractRand需要一个月的时间。但是我必须承认，以每秒千兆字节的速度通过此测试非常困难。当您上升到这样的高度时，您想知道是否可以到达帕累托边界。您要创建世界上最快的PRNG，它将通过最复杂的统计测试。我成功了。在上一篇文章中，我谈到了我学到的实现目标的知识。在这里，我将告诉您最终的架构是如何工作的。目的
让我们从显而易见的开始：速度取决于平台。我专注于针对现代x86-64架构（Intel和AMD处理器）进行优化。为了比较性能，使用了经典的cpb指标：这是在生成一个字节上花费的处理器周期数。在所有密码工作中都会计算并比较此指标。软件或硬件领域的cpb稍低可以确保在竞争中获胜或在世界各地的网站上使用。要改善cpb，您可以：- 以相同的工作量生成更多字节，
- 或者做更少的工作来生成相同数量的字节，
- 或并行工作。
我们将完成上述所有操作。根据第一点，我们需要在每次迭代中产生更多的位。我担心他们会告诉我：“如果不给出32位数字，那么这不是PRSP”，或者与64位数字相同。或者：“ PRNG仅应用于x86-64体系结构”，就像禁止使用POPCNT之类的指令或％xmm7之类的寄存器一样。但是，PRNG是工程技术：生成器已经尝试了数十年，以将所有可能的东西从处理器中挤出来！当ROL出现时，他们开始依赖他。随着64位处理器的出现，他们开始依赖％rax。当然，在ARM上，此类算法的运行速度可能较慢（尽管这还有待观察），但是，甚至在Android在2019年开始要求64位支持之前，仍在积极使用64位PRN！即，该领域与硬件一起发展。如今，由于AVX2而已，英特尔和AMD处理器已经支持256位操作。 RC4产生1个字节，drand48一次可以产生4个字节，pcg64-8个字节，现在我们可以立即产生32个字节。8字节可以是64位数字，并且大多数编程语言都具有内置类型。但是很少有语言提供16个字节的类型（一个明显的例外是C中的__uint128_t）。更少的语言具有32个字节的类型（内部除外）。因此，我们可以告别PRNG函数的常规原型（例如来自Vigny HWD基准测试的示例）：static uint64_t next(void);
相反，您可以使生成器填充缓冲区（例如，来自我的基准测试的示例）：void prng_gen(prng_state *s, __uint64_t buf[], __uint64_t size);
该解决方案的缺点是什么？如果生成器一次生成32个字节，则您需要使用方提供一个32的倍数的数组（理想情况下，对齐到32个字节）。尽管您可以不用它，但是我们只会填充缓冲区。我们将从其中删除未使用的数据，并根据需要再次填充。延迟变得不可预测：某些调用只会读取缓冲区。但平均而言，一切都会相同。现在，我们生成更多字节，完成相同的工作量。我们如何并行化它？并行性
处理器在所有级别都提供了一套令人难以置信的并行化工具。首先，这些是SIMD指令（单指令，多数据）。例如，AVX2同时执行四个64位加法或八个32位加法，等等。它已经在密码学中使用了大约十五年。并发提供了ChaCha20令人难以置信的性能。不使用AESNI的最重要的原语使用它。例如，NORX和Gimli在设计时考虑了并行性。最近，非密码PRNG社区对此主题的兴趣也有所增加。特别是，没有为SIMD设计的现有原语可以作为创建非常快的PRN的基础。当Sebastiano Vigna 在Julia标准库中推广其xoshiro256 ++架构时，他发现，如果在所有PRNR中同时执行每个操作，则可以非常快速地串联八个竞争的，初始化方式不同的PRNG实例的结果。SIMD只是处理器中并行化的级别之一。我建议阅读有关该主题的上一篇文章，以便有更好的主意，但我会给出一些解释。处理器管线允许在不同阶段处理几条指令。如果您很好地组织了它们的执行顺序以减少阶段之间的依赖性，则可以加快指令的处理速度。超标量执行使您可以同时处理指令的计算部分。但是为此，它们不应具有读写依赖性。您可以通过在读取前进行长时间记录来调整体系结构，以减少停机风险。非凡执行使处理器可以按顺序执行指令，而不必按顺序执行，即使先前的指令尚未准备好也可以执行。但是为此，应该没有读写依赖性。现在我们进行实施！建筑
考虑一种称为Semi-SHISHUA的方案。阅读时，这种名称的来源将逐渐变得明显。该方案如下所示：逐行考虑其。typedef struct prng_state {
__m256i state[2];
__m256i output;
__m256i counter;
} prng_state;
状态分为两部分，分别放在AVX2寄存器（256位）中。为了提高速度，我们将结果保持在靠近状态本身的位置，但它不是状态的一部分。我们还有一个64位计数器。为了简化计算，它也是一个AVX2寄存器。事实是AVX2具有一个小功能：普通寄存器（％rax等）无法通过MOV直接传输到SIMD，它们必须通过RAM（通常是通过堆栈），这增加了延迟，并花费了两个处理器指令（MOV在堆栈上，VMOV在堆栈上）。现在让我们看一下一代。让我们从加载开始，然后遍历缓冲区，并在每次迭代时用32个字节填充它。inline void prng_gen(prng_state *s, __uint64_t buf[], __uint64_t size) {
__m256i s0 = s->state[0], counter = s->counter,
s1 = s->state[1], o = s->output;
for (__uint64_t i = 0; i < size; i += 4) {
_mm256_storeu_si256((__m256i*)&buf[i], o);
// …
}
s->state[0] = s0; s->counter = counter;
s->state[1] = s1; s->output = o;
}
由于该函数是内联函数，因此在启动时立即填充缓冲区使处理器可以通过特殊的执行机制立即执行指令。在循环内部，我们快速执行三个状态操作：- SHI英尺
- 舒 ffle
- 一个 DD
因此，名字叫SHISHUA！一，换班
u0 = _mm256_srli_epi64(s0, 1); u1 = _mm256_srli_epi64(s1, 3);
不幸的是，AVX2不支持转速。但是我想将64位数字中一个位置的位与另一位置的位混合！而转变是实现这一目标的最佳方法。我们将移位一个奇数，以便每一位将访问所有64位位置，而不是其中一半。在移位期间，位丢失，这导致从我们的状态中删除信息。这很不好，您需要将损失降到最低。最小的奇数是1和3，我们将使用不同的移位值来增加两个部分之间的差异。这将有助于降低其自相关的相似性。我们将向右移动，因为最右边的位在加法期间具有最低的扩散：例如，A + B中的最低有效位只是最低有效位A和B的XOR。搅拌
t0 = _mm256_permutevar8x32_epi32(s0, shu0); t1 = _mm256_permutevar8x32_epi32(s1, shu1);
我们将使用32位混合，因为与我们在各处使用的64位操作（违反了64位对齐方式）相比，它提供的粒度不同。它也可以是跨通道操作：如果其他混洗从左开始，则可以在左128位之内移动位；如果从右开始，则可以在右128位之内移动。混合常数：__m256i shu0 = _mm256_set_epi32(4, 3, 2, 1, 0, 7, 6, 5),
shu1 = _mm256_set_epi32(2, 1, 0, 7, 6, 5, 4, 3);
为了使混合真正改善结果，我们将64位加法的弱（低分散）32位部分移到强位置，以便下一个加法丰富它们。64位块的低端32位部分永远不会移到与高阶部分相同的64位块中。因此，两个部分不保留在同一块内，这改善了混合。最后，每个32位部分都经过一个圆的所有位置：从A到B，从B到C，...从H到A。您可能已经注意到，考虑到所有这些要求的最简单的混合是两个256位周转率（分别向右旋转96位和160位）。加成
让我们从两个临时变量（移位和混合）中添加64位块。s0 = _mm256_add_epi64(t0, u0); s1 = _mm256_add_epi64(t1, u1);
加法是分散的主要来源：在此操作中，位组合为分布在64位位置的XOR和AND表达式的不可约组合。在状态内存储加法结果将永久保留这种分散。输出功能
我们从哪里获得输出？很简单：我们创建的结构允许我们生成状态s0和s1的两个独立部分，它们不会以任何方式相互影响。对它们应用XOR并获得完全随机的结果。为了加强应用XOR的数据之间的独立性，我们得出了部分结果：一种状态的转移部分和另一种状态的混合部分。o = _mm256_xor_si256(u0, t1);
这类似于减少超标量处理器中指令之间的读写依赖性，就像u0和t1准备好读取到s0和s1一样。现在讨论柜台。我们在周期开始时对其进行处理。首先，更改状态，然后增加计数器值：s1 = _mm256_add_epi64(s1, counter);
counter = _mm256_add_epi64(counter, increment);
为什么我们首先更改状态，然后更新计数器？ s1较早可用，这减少了后续读取它的指令在处理器管线中停止的可能性。同样，此序列有助于避免读写计数器的直接依赖性。我们将计数器应用于s1，而不是s0，因为它们都会影响输出，但是s1由于移位而丢失更多位，因此它有助于移位后“站起来”。计数器可能不会记录PractRand测试。其唯一目的是将下限设置为2 69PRNG周期中的字节数= 512 EB，只有在经过一千年的工作之后，才以10吉比特/秒的速度开始重复该周期。在未来的几个世纪中，实际应用不太可能太慢。增量：__m256i increment = _mm256_set_epi64x(1, 3, 5, 7);
选择奇数作为增量，因为只有基本的互质数覆盖了有限域GF（2 64）的整个周期，并且所有的奇数都是2的互质。换句话说，如果您以从0到4，在4之后返回0，我们得到序列0-2-0-2 -...，它将永远不会导致1或3。奇数增量遍历所有整数。对于所有处于状态的64位数字，我们将使用不同的奇数，这将进一步分隔它们并稍微增加混合。我选择了最小的奇数，所以它们看起来并不神奇。这就是状态转换和输出功能的工作方式。如何初始化它们？初始化
我们使用十六进制数Φ初始化状态，十六进制数Φ是最接近分数的无理数。static __uint64_t phi[8] = {
0x9E3779B97F4A7C15, 0xF39CC0605CEDC834, 0x1082276BF3A27251, 0xF86C6A11D0C18E95,
0x2767F0B153D27B7F, 0x0347045B5BF1827F, 0x01886F0928403002, 0xC1D64BA40F335E36,
};
取一个256位种子。这通常在密码学中完成，并且不会损害非密码PRNG的工作：prng_state prng_init(SEEDTYPE seed[4]) {
prng_state s;
// …
return s;
}
我们不想使用该初始数字来重新定义状态的整个部分（s0或s1），我们只需要影响一半即可。这样，我们将避免使用衰减的初始数，因为它会偶然或有意引起已知的弱初始状态。由于我们不更改每个状态的一半，因此我们保留对128个状态位的控制。这样的熵足以启动并维持强势地位。s.state[0] = _mm256_set_epi64x(phi[3], phi[2] ^ seed[1], phi[1], phi[0] ^ seed[0]);
s.state[1] = _mm256_set_epi64x(phi[7], phi[6] ^ seed[3], phi[5], phi[4] ^ seed[2]);
然后，我们按ROUNDS以下顺序多次重复（）：- 运行
STEPSSHISHUA迭代的步骤（）。 - 我们将状态的一部分分配给另一状态，将另一部分分配给输出。
for (char i = 0; i < ROUNDS; i++) {
prng_gen(&s, buf, 4 * STEPS);
s.state[0] = s.state[1];
s.state[1] = s.output;
}
分配输出结果会增加状态分散。在初始化期间，其他工作和状态关联无关紧要，因为这一系列操作仅执行一次。我们只对初始化期间的分散感兴趣。在评估了对初始值相关性的影响之后，我选择了STEPS2 作为值，选择ROUNDS10 作为10。我通过计算PractRand中PRNG质量控制工具产生的“异常”和“可疑”异常来计算相关性。性能
由于以下几个原因，很难测量速度：- 时钟测量可能不够准确。
- , , - , -, .
- , . .
- : , .
我使用RDTSC处理器指令，该指令可计算周期数。为了使任何人都能重现我的结果，我使用了基于云的虚拟机。与本地测试相比，这不会改变基准测试结果的水平。此外，您不必购买与我相同的计算机。最后，在许多情况下，PRNG在云中启动。我选择了Google Cloud Platform N2（英特尔处理器）和N2D（AMD处理器）。 GCP的优势在于它们为服务器提供了两家制造商的处理器。在本文中，我们将重点介绍英特尔，但对于AMD，结果将保持不变。为了更深入地研究该主题，让我们首先摆脱旧的RC4密码生成器。无法并行化工作，我得到了7.5 cpb（每个生成字节的周期）。现在，让我们运行一个非常流行且快速的MCG：通过BigCrush测试的最简单的Lehmer128 PRNG显示为0.5 cpb。哇，太好了！然后，我们将运行用于快速哈希表的最新开发-wyrand。0.41 cpb，好一点！一些PRSP不能通过32 TB的PractRand测试，但是它们可以非常快速地工作。Xoshiro256 +仅达到512 MB，但显示出非常高的速度：0.34 cpb。RomuTrio的另一个最新开发。她声称自己是世界上最快的PRNG- 0.31 cpb。好的，足够了。SHISHIA的半身显示了什么？0.14厘泊。速度是RomuTrio的两倍。凉。现在测试密码生成器ChaCha8。他达到了... 0.12 cpb。哦。SIMD是真正的魔术！对于密码界来说，这并不是什么特别的惊喜。ChaCha8非常容易并行化。这只是一个散布状态下的杂乱无章的计数器。还记得朱莉亚语言团队是如何尝试结合Vigny架构的几个实例来创建基于SIMD的快速PRNG的吗？让我们看看使用这种技术的结果（8个Xoshiro256 +）。0.09厘泊！从技术上讲，我的笔记本电脑可能会影响结果。我不确定Julia团队的开发为何比GCP中的ChaCha8快，但是在本地测试时却慢。在我的机器上，半SHISHUA的运行速度快于Julia团队的开发速度，但慢于ChaCha8。必须击败所有竞争对手。您可能已经在问为什么我们调用了SHISHUA生成器的先前版本？因为事实证明，如果运行两个半SHISHUA副本，则速度很容易翻倍。类似于Julia命令的想法，我们分别初始化了两个PRNG（四个256位状态的块），并交替提供其工作的输出。但是，如果我们建立更多状态，那么我们可以生成更多数据，将四个状态成对组合：o0 = _mm256_xor_si256(u0, t1);
o1 = _mm256_xor_si256(u2, t3);
o2 = _mm256_xor_si256(s0, s3);
o3 = _mm256_xor_si256(s2, s1);
因此我们得到了SHISHUA，其速度为0.06 cpb。这是通过32 TB的PractRand测试的世界上最快的竞争对手的两倍。结果在图表上。我相信这一发展具有竞争力。在笔记本电脑上，它的运行速度甚至更快-0.03 cpb，但我将坚持有关基准测试的原则。希望我的发电机能够再呆几周，成为世界上最快的发电机（请这样做）。质量
生成器诚实地通过了BigCrush和32 TB的PractRand测试。而全部归功于四个输出流。体系结构的缺点包括其不可逆性。这可以通过使用s0 = [a, b]和降低为4位状态来看出s1 = [c, d]。有了转变，我们得到了[0, a]和[0, d]，并且有了搅拌，[b, c]还有[d, a]。新s0等于[b, c] + [0, a] = [b⊕(a∧c), a⊕c]，但s1等于[d, a] + [0, c] = [d⊕(a∧c), a⊕c]。如果a = ¬c，那么，a⊕c = 1和a∧c = 0因此，s0 = [b, 1]和s1 = [d, 1]。也就是说，我们得到的两个组合a并c，这给了我们同样的最终状态。在我们的情况下，这不是问题，因为64位计数器也是状态的一部分。原来最小周期是2 71字节（每个状态转换128字节），速度为10吉字节/秒。将持续七千年。这平衡了丢失状态。此外，即使不可逆，状态之间的平均过渡期也为2 ^（（256 +1）÷2）。这样得出的平均周期为2135字节（速度为10吉字节/秒。它将比宇宙存在的时间长一万亿倍）。尽管我认为中间周期被高估了，因为它们并没有告诉我们有关发电机质量的任何信息。以下是基准测试结果：- 性能：在一个生成的字节上花费的处理器周期数。在云计算机N2 GCP和N2D（AMD）上收到的顺序是相同的。
- 质量：发生器未通过PractRand测试的级别。如果没有失败，则显示一个>符号。如果结果没有得到证实，则会出现一个问号。
- 种子编号的相关性：具有八个种子编号分别为 0、1、2、4、8、16、32、64的流的交替字节的PractRand遍历。我们将PractRand与双卷积和高级测试一起使用。
进一步
尽管在我们看来，不可逆性没有问题，但我们仍然可以改善SHISHUA。我认为理想的PRNG具有以下特性：- , 21024. 10 /. 10282 , . «» ( ). , . , 128- NEON ARM? , , .
- . , SHISHUA XOR . , .
- , 2128 ( ). SHISHUA, , . , ( ) (, , . 2).
- 状态初始化具有完美的分散性：初始编号的所有位以相同的概率影响状态的所有位。我想找出有关SHISHUA的信息。
阻碍PRNG和加密技术整体发展的问题之一是缺少更好的通用工具。我需要一个可以立即为我提供准确测量结果的工具，以便可以即时比较不同的体系结构。与以前相比，PractRand很棒。- 它不允许评估高质量的生成器，因此无法将它们相互比较。我们必须说：“嗯，在32 TB之后，它们没有异常……”
- 运行它需要数周时间...
我希望情况将很快得到改善。