比特切片如何更快？

#1 楼

比特切片技术是一种计算方法，它可以进行以下操作：

简化为具有单个比特输出（通常为NOR，XOR等类似OR AND NAND NXOR的基本运算（称为Gates），通常进一步限制为两个输入） ），而不是对跨越几个位的字或整数进行操作。
并行执行，并发实例（在单个CPU上）与某种寄存器类型的位一样多，同时对所有寄存器同时执行NOR，XOR ..

执行1会产生大量的门：两个$ n $位字的XOR需要$ n $门。对于$ n> 1 $，其加法运算$ 2 ^ n $需要$ 5n-6 $门； AES子字节中的每个8位S-box查找大约需要128个门。另一方面，旋转时，任意位改组，选择或扩展都不需要门。
做2实现每条指令$ w $门操作$ w $位寄存器，并且大多数加速（如果有的话）都来自于并行化$ w $（注意：有效的$ w $不能大于同时执行的计算数量）。越来越多的嵌入式CPU支持$ w = 32 = 2 ^ 5 $，带有AVX指令的CPU甚至支持$ w = 256 = 2 ^ 8 $。最重要的是，位片化代码不受与缓存相关的辅助通道（包括定时）的影响。另外，它是非常线性的，这使得对数据访问的高效调度变得更加容易，并且没有分支延迟。
在位切片的不利方面：最重要的是，同时执行$ w $操作并不匹配所有工作负载！对于单个大文件和块密码的常见操作模式，只有CTR（或有缺陷的ECB）才完全可用（CBC和CFB仅可用于解密，OFB不可用）。而且，代码很大并且相对复杂。从普通参数转换为位片形式的参数（并返回结果）需要位转换，这会增加一些开销。正常情况下，很多中间结果或状态数据适合寄存器或L1缓存。
原则上，对多个实例执行的任何加密计算都可以按位分割。但是，许多没有位分片地本机处理的操作不太可能获得任何速度优势。这包括任何太简单的事情（如提议的XOR），或到门的转换效率极低的事情（如模块化乘法，或查找大型任意固定表，或相当大的动态表），或执行流程有太多路径的地方。有关更详细的分类，请参阅Ilmari Karonen的答案。再一次，我们需要能够并行进行多个计算！
由Eli Biham的A快速新DES率先提出的，其中比特切片可以带来速度优势的真实密码的原型示例是（3）DES。

我可以构造出比DES更简单的任何东西来证明比特切片的好处远非现实生活；因此，我以具有预计算子项的（单个）DES的纯软件实现为例，它在CPU上具有十几个通用128位寄存器，128位（缓存）内存访问权，用于128个块的加密（1024个任意字节；我忽略了CTR模式下可能的优化）。
传统的（非位分段）实现是：

每个$ w $块

将每个初始置换（IP，位换位）将输入块转换为两个32位半L和R
对于$ r $从1到16的轮次

加载48位子键将$ r $放入寄存器K
中，将S-box $ s $从8转换为1

进行适当旋转的副本或R
与K
保留其中的低6位
将其用作加载$ s $ th S表的索引，该表由$ 64 = 2 ^ 6 $个值组成，每个值32位（实现S-box和排列P，因此输出较宽）;该步骤通常会控制成本，并且可能是与目标缓存相关的辅助通道
将X移至L
，将下一个S盒的K向右移6位


交换R和L


按照IP-1将两个32位半R和L转换成输出块




S-box循环通常是展开的（以及回合循环的至少两个连续执行，这使得交换基本上是免费的），因此成本由编号的步骤决定。我们可以抑制8个步骤1和6中的1个。因此，成本的一个很好的近似值（现在忽略IP和IP-1）是$ w $乘以16倍：9个内存负载（其中8个已​​索引）和大约38个其他简单操作。
按位排列的DES抑制了外部块循环，在每一步中以$ w = 128 $ -bit的操作来替换它，以操作依赖于块的数据：

转换128个输入块（每个64位）转换为64个存储字（每个128位），每个存储字保存一个块中相同等级的所有位（位换位）
用于将$ r $从1循环到16
< br将用于循环$ r $的48位子密钥装入S-box $ s $的寄存器K
，从8到1

6个输入位j中的每个输入位S-box $ s $
a）将K的最右位复制到128位宽的寄存器Tj
b）加载保持状态适当位的128位存储字
c）将X异或到Tj
d）对S盒$ s $
的4个输出位中的每个位右移K
a）将输出位（对于所有128个块同时计算）作为T1..T6的布尔函数，到128位寄存器X
b）将保持状态适当位的128位存储字加载
c）与X进行异或运算d）将其存储为保存状态的相应位的128位存储字




将64个存储字（每个128位）转换为128个输出块（每个64位）以形成结果（位转换与第一个相反）

我们将展开循环（如果我们要为子键以外的其他加载/存储使用固定地址，则需要两个版本，具体取决于$ r $是奇数还是偶数）。独立地：我们可以使用在步骤1a中加载的6个值中的2个值可用于下一个（或/和最后一个）S-box，从而减少步骤1b中的有效加载次数，而只需几个额外的寄存器。 />在步骤2a中，将S-box替换为布尔运算。使用马修·关（Matthew Kwan）在减少Bitslice DES的门数（ePrint 2000/051）中得出的表达式，每个S-box的平均成本下降到51个布尔运算，其代价是需要一些临时寄存器，并且有些不期望的突发次数。存储在第2d步。
因此，成本的一个很好的近似值（忽略初始和最终转换）是16倍：65个内存负载和32个内存写操作（没有索引），以及大约440个其他操作。因此，如果我们忽略初始和最终换位的成本，则DES将成为速度方面的赢家，即使广泛操作的成本要比狭窄操作的成本高一些：每轮内存访问从$ 9w = 1152 $减少到$ 97 $；其他操作，从$ 38w = 4864 $到$ 440 $。十倍的改进（对于$ w = 128 = 2 ^ 7 $）超过了换位的额外成本（无论如何，这比$ w $乘以IP和IP-1的成本要适度高：最后，相同数量的数据转置）。通过仔细的编码，包括$ w = 32 = 2 ^ 5 $的位片DES可能会更快。

#2 楼

寄存器中位切片或SIMD的基本思想包括两个部分：用单位逻辑运算（AND，OR，XOR，NOT等）表达密码。 ），就好像您是在硬件中实现它一样，并且


使用CPU上的按位运算并行地针对多个密码实例执行这些操作。


也就是说，在按位分割的实现中，没有一个变量存储例如32位数字，而是有一个变量存储数字的最低位（或者$ n $数字，其中$ n $是CPU可以在寄存器中存储的位数），另一个变量是存储该数字的第二低位，依此类推。
显然，计算所有位-逐位（通常）比仅以普通方式计算事物要慢得多。但是使用$ n $位处理器，按位分片的实现可以并行运行最多$ n $个密码实例（例如，加密最多$ n $个数据块）。因此，只要将位片化的实现运行单个密码实例的速度减慢不超过$ n $倍，您就可以最终获得吞吐量的净收益。
那么哪种类型的操作在位片化中效果很好，



位移位，旋转和其他位置换在按位切片的实现中变得微不足道，因为它们仅与重新标记变量相对应。因此，在按位划分的实现中，这样的操作实际上根本不需要时间。由于加密代码往往会大量使用此类操作，因此，仅此一项就可以成为位切片的巨大胜利。
（但是，这仅适用于恒定的位移位。如果移位量取决于要处理的数据，则对其进行位切片变得更加困难。）


诸如XOR之类的按位逻辑运算趋于接近收支平衡点。如果您有两组32位数字，每组32位，并且想对它们进行异或运算，则按数字或逐位进行操作并不重要-您需要做的是两种方式都可以进行32个异或运算。
当然，如果您的CPU具有64位或128位寄存器（例如，任何具有SSE的现代x86 CPU都具有），那么您可以执行64位或128位切片32位XOR，仍仅使用32个XOR指令。因此，仅由于额外的并行性，位切片仍可能胜出XOR。



还可以使用按位逻辑运算来实现加法和减法，本质上是通过实现加法器电路来实现的。这需要每位最多五个指令（两个XOR，两个AND和一个OR / XOR）来实现一个完整的加法器，尽管有时可以根据可用的指令减少它（例如，三输入XOR和多数指令可以允许在每位两个指令中实现一个完整的加法器）以及将用于什么结果（例如，如果可以使用进位保存加法）。因此，尽管上面提到的增加的并行性仍可以弥补这一点，但在位分片的实现中加法和减法的效率往往较低。


更复杂的算术，例如乘法和除法，可以原则上也可以使用位分片来实现，但是结果代码可能非常慢且复杂。幸运的是，这些运算很少用在密码中（尽管有时需要使用公钥加密）。
但是，值得注意的是，由于没有进位，（二进制）Galois字段乘法比普通乘法更容易位切片。 。同样，乘以常数（无论是普通的还是在Galois字段中）都可以分解为移位（自​​由！）和加法（或XOR）的组合，从而很容易进行位分片。


出于显而易见的原因，通常很难对表进行位片分割。但是，如果查找表又小又固定，就像许多密码中的S盒一样，则可以用计算相同结果并对其进行位片化的逻辑电路来代替它。例如，Eli Biham就是通过这种方式在最初的1997年比特化DES实现中处理S-box的。通常，经过优化的硬件S-box实现通常可以直接转换为按位分割的软件实现。因此，任何可以在硬件中有效实施的密码（通常是常见的设计准则）通常也可以进行位片分割。


条件代码（例如if语句）也相当很难进行位片分割，尽管有一些方法可以通过掩盖来模拟它。例如，诸如x = (condition ? a : b)之类的条件表达式可以改写为x = (a & mask) | (b & ~mask)，其中如果mask为true，则condition设置为全1，否则设置为全零，然后进行位分割。


比特切片的优点是，比特切片的代码倾向于在流水线密集的现代CPU上很好地运行，因为它倾向于流水线停顿的风险较低，并且有大量机会优化指令重新排序。基本上，在普通的加密代码中，如果您计算出以下内容：

w = x + (y XOR z)

，那么XOR计算必须在加法开始之前完成，以防止操作并行执行。然而，在按位划分的实现中，我们可以首先计算XOR的低阶位，然后移至高阶位，这样，当我们开始进行加法运算时，我们首先需要的低阶位将有足够的时间准备。
如果我们愿意，我们也可以将XOR和加法计算交织在一起（或只是让编译器为我们完成），仅在需要加法时才及时计算XOR位以准备就绪。通过让处理器在等待进位准备就绪时计算XOR，可以减少添加代码中发生停顿的可能性，并且还可以改善寄存器和/或缓存的局部性。
如上所述，在消除条件的情况下，位片化代码往往不会遭受分支错误预测的困扰。方便地，这也倾向于使其能够抵抗定时攻击，从而更加安全。
总而言之，比特切片也有其缺点。一种是，在并行处理$ n $个密码实例时，您需要存储$ n $个密码状态副本。因此，尽管在传统的实现中，您可能可以将完整状态填充到CPU寄存器中，或者至少在L1高速缓存中，但位片化的实现将占用更多的空间，因此最终可能会将一些数据推送到速度较慢的缓存中，甚至是未缓存的RAM。
有时，通过在密码实例之间共享数据可以部分缓解此问题，例如用相同的密钥加密多个数据块时。而且，（由程序员或由编译器）巧妙的指令重新排序可以改善高速缓存的局部性，例如在其他位上执行相同操作之前，通过对数据的低位位计算多个操作（从而将变量存储在寄存器或快速缓存中）保持不变。通常，按位加密的实现比不按位加密的实现更可能具有较差的缓存局部性。
此外，有些算法只是不能很好地对位进行切片。 RC4流密码是一个著名的例子，它似乎几乎被设计用来挫败任何比特切片工作：


它具有很大的内部状态（每个密码实例258×8 = 2064位），其中大多数不能在实例之间共享，因此按位分割的实现需要大量内存。


该状态包含一个不断变化的8位查找表。由于查找表不是固定的，因此无法用逻辑电路（例如DES或AES中的S盒）替换。


状态更改只有4个字节每次迭代，但实际上更改的字节之一实际上是伪随机选择的。并行运行许多RC4实例将意味着，在每次迭代中，状态的许多位将在某些实例中发生变化（但很少在一个以上）。


实际上，我有时候，我想知道RC4或其他类似算法是否可能在像scrypt的构造中作为故意不可并行化且对硬件不友好的组件有用。

#3 楼

位分片是一种允许将多个指令/数据点编码到单个寄存器中的技术。

想法是在单个寄存器中编码几个按位运算。因此，通过将数据填充到SIMD寄存器中并并行执行，可以减少操作总数，而不是依次执行32个按位或运算。

所以您将更改

POR EAX, ECX // Compares A with B

转换为

OR XMM0, XMM1 // makes up to 32 such comparisons if you have AVX extensions.

现在不利之处这是您必须将数据转换为simd操作所需的格式，以便您的结果将成为易于使用的值块。基本上，您必须“切片”：

A1-A2-A3-A4 OR B-1-B2-B3-B4 

进入：

A1-D1 OR B1-E1 = C1-F1

这不是免费的。但是，在许多情况下，如果进行仔细的优化，则可以显着提高速度。作为一项额外的好处，此技术可用于避免在某些情况下进行表查找（https://eprint.iacr.org/2015/727.pdf），有助于增强针对缓存定时攻击的实现。

之所以该技术非常适合于加密，是因为加密技术经常使用重复的按位运算，可以通过这种方式轻松地将其并行化。其他人则正确地将您指向原始文件，以获取有关此内容的实施详细信息：

http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr- get.cgi / 1997 / CS / CS0891.pdf

是一个很好的起点。我将引用原始论文的话，其中总结了在64位计算机上使用SIMD进行DES的一些特殊优势：

”八个S-Box可以并行应用，因此流水线可以在没有流水线停顿的情况下使用它。”

他继续说，但是我还没有发现这种纸的格式并不讨厌复制和粘贴。阅读整篇文章，简短扼要。