快速便携的 DES 加密与解密

注意

以下是来自 descore.shar 软件包的原始 README 文件，已转换为 ReST 格式。

des - 快速便携的 DES 加密与解密。

版权所有 © 1992 Dana L. How

本程序是自由软件；您可以在自由软件基金会发布的 GNU 宽通用公共许可证（GNU Library General Public License）的条款下重新分发和/或修改它；您可以选择许可证的第 2 版，或（根据您的选择）任何更高版本。

本程序是抱着将会有用的希望而发布的，但 不附带任何担保；不附带任何适销性或特定用途适用性的默示担保。更多详情请参阅 GNU 宽通用公共许可证。

您应该已经随本程序收到一份 GNU 宽通用公共许可证的副本；如果未收到，请致函自由软件基金会，地址：Free Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA。

作者地址：how@isl.stanford.edu

==>> 在解压/解包后进行编译，只需 make <<==

本软件包旨在实现以下目标

  1. 实现尽可能高的加密/解密性能。

  2. 可移植到任何具有 32 位无符号 C 类型且支持字节寻址的主机。

  3. 可即插即用地替代 KERBEROS 的底层例程。

此第二个版本包含了针对寄存器稀缺机器的多项性能增强。我与 Richard Outerbridge（71755.204@compuserve.com）的讨论促成了其中的一些增强。

为了更快地理解本软件包中的代码，请在着手研究 desCode.h 之前，先检查 desSmallFips.i（通过输入 make 生成）。后者以参数化方式设置，以便追求极致速度的黑客可以轻松修改它，以榨取最后一微秒的性能。您会发现检查一个具体的实现会更有启发性，然后在此基础上再转到通用的抽象骨架。

与我在 SPARCStation 1 上能编译的其他可用 DES 代码的性能比较 (cc -O4, gcc -O2)

此代码 (字节序无关)

  • 每次加密 30 微秒 (选项：64k 表，无 IP/FP)

  • 每次加密 33 微秒 (选项：64k 表，FIPS 标准位序)

  • 每次加密 45 微秒 (选项：2k 表，无 IP/FP)

  • 每次加密 48 微秒 (选项：2k 表，FIPS 标准位序)

  • 设置新密钥 275 微秒 (使用 1k 密钥表)

    这是我见过最快的加密/解密例程。由于我更关注快速的 DES 过滤器，而非 crypt(3) 和密码破解，因此我尚未真正着手加速密钥设置例程。此外，我对重新实现 MIT Kerberos DES 库中的所有其他无用功能不感兴趣，所以我只为我的例程提供了少量桩接口，以便它们可以作为 MIT 代码或下方任何兼容 MIT 的软件包的直接替代品使用。(请注意，上述前两个计时数据由于缓存效应而具有高度可变性)。

来自澳大利亚的 Kerberos DES 替代方案 (版本 1.95)

  • 每次加密 53 微秒 (使用 2k 表)

  • 设置新密钥 96 微秒 (使用 2.25k 密钥表)

    因此，尽管作者采纳了我向他提出的一些性能改进建议，但该软件包在 SPARC 和 68000 上的加密/解密速度仍然较慢。具体来说，根据编译器的不同，在 68020 上慢 19-40%，在 SPARC 上慢 11-35%。详细数据如下 (ALT_ECB 是 libdes 的一个变体)：

    编译器

    机器

    desCore libdes

    ALT_ECB 慢

    gcc 2.1 -O2

    Sun 3/110

    304 uS 369.5uS

    461.8uS 22%

    cc -O1

    Sun 3/110

    336 uS 436.6uS

    399.3uS 19%

    cc -O2

    Sun 3/110

    360 uS 532.4uS

    505.1uS 40%

    cc -O4

    Sun 3/110

    365 uS 532.3uS

    505.3uS 38%

    gcc 2.1 -O2

    Sun 4/50

    48 uS 53.4uS

    57.5uS 11%

    cc -O2

    Sun 4/50

    48 uS 64.6uS

    64.7uS 35%

    cc -O4

    Sun 4/50

    48 uS 64.7uS

    64.9uS 35%

    (我的时间测量不如他准确)。

我对 desCore 1.92 版本首次发布时的评论

  • 每次加密 68 微秒 (使用 2k 表)

  • 设置新密钥 96 微秒 (使用 2.25k 密钥表)

    这是一个非常不错的软件包，它实现了我在加密例程中所做的最重要的优化。它在常见的底层优化方面稍显不足，这就是为什么它慢 39%-106% 的原因。由于他关注快速的 crypt(3) 和密码破解应用，他也利用相同的想法来加速密钥设置例程，并取得了令人印象深刻的结果。(在某个时候我可能会在我的软件包中也这样做)。他还实现了 MIT DES 库的其余部分。

    (代码来源：eay@psych.psy.uq.oz.au，通过 comp.sources.misc)

来自丹麦的快速 crypt(3) 软件包

这里的 DES 例程嵌套在一个循环中以执行 crypt 函数，我不想将其剥离出来测量性能。他的代码需要 26 条 SPARC 指令来计算一次 DES 迭代；上面，Quick (64k) 需要 21 条，Small (2k) 需要 37 条。他声称使用了 280k 的表，但迭代计算似乎只使用了 128k。他的表和代码是机器无关的。

(代码来源：glad@daimi.aau.dk，通过 alt.sources 或 comp.sources.misc)

Kerberos DES 库的瑞典重新实现

  • 每次加密 108 微秒 (使用 34k 表)

  • 设置新密钥 134 微秒 (使用 32k 密钥表才能达到此速度！)

    所使用的表似乎与机器无关；他似乎包含了许多特殊情况代码，例如，当机器架构允许时，可以使用 long 加载代替 4 个 char 加载。

    (代码获取自 chalmers.se:pub/des)

来自英国的 crack 3.3c 软件包

如上文 crypt 所述，DES 例程嵌套在一个循环中。它也针对 crypt 进行了大量修改。他的迭代代码使用 16k 的表，并且看起来很慢。

(代码获取自 aem@aber.ac.uk，通过 alt.sources 或 comp.sources.misc)

高度优化 和调整过的 Kerberos/Athena 代码 (字节序相关)

  • 每次加密 165 微秒 (使用 6k 表)

  • 设置新密钥 478 微秒 (使用 <1k 密钥表)

    因此，尽管该代码中有这些注释，但仍然可以获得更快且更小的表，并使表与机器无关。(代码获取自 prep.ai.mit.edu)

加州大学伯克利分校代码 (取决于机器字节序)

  • 每次加密 226 微秒

  • 设置新密钥 10848 微秒

    表大小不清楚，但看起来不大 (代码获取自 wuarchive.wustl.edu)

动机与历史

一段时间前，我想要一些 DES 例程，但 Sun 手册页中记载的例程要么不存在，要么会产生核心转储。我听说过 Kerberos，并且知道它使用 DES，所以我想我会使用它的例程。但当我拿到它并查看代码时，它着实引发了我很多不满——它过于复杂，代码在编写时没有利用 IP、E 和 FP 等操作的常规结构（即作者在编码前没有坐下来思考），它慢得离谱，作者试图通过添加更多语句来使数据移动更 一致，而不是简化其实现并减少所有数据移动（特别是他对 L1、R1、L2、R2 的使用），并且充满了愚蠢的 调整，针对特定机器进行了调整，这些调整未能带来显著的速度提升，反而混淆了一切。因此，我从他的验证程序中获取了测试数据，并重写了其他所有内容。

不久之后，我偶然发现了上面提到的那个出色的 crypt(3) 软件包。他通过每次表查找计算 2 个 S 盒而不是 1 个（并且在此过程中使用了大得多的表）这一事实，鼓励我效仿——这只是一个微不足道的改变，但我曾因更大的表大小而望而却步。在他的例子中，他没有意识到你不需要将工作数据保持两种形式：一种用于索引一半 S 盒以便于使用，另一种用于另一半以便于使用；相反，你可以将其保持为前半部分的形式，然后使用简单的旋转来获取另一半。这意味着我的数据操作量和表大小（几乎）减半。不过公平地说，他可能在他的表中编码了与 crypt(3) 相关的一些特定内容——我没有检查。

我很高兴我以这种方式实现了它，因为这个 C 语言版本是可移植的（ifdef 是性能增强），而且它比为 SPARC 手写汇编的版本更快！

移植说明

我不想做的一件事就是编写一个庞大的混乱代码，它依赖于字节序和其他机器特性，并且必然为不同的机器生成不同的代码和不同的查找表。请参阅 Kerberos 代码，了解我不想做的事情的例子；他们所有针对字节序的 优化 混淆了代码，并且最终比更简单的机器无关方法更慢。然而，总会有一些可移植性方面的考虑，我提供了一些选项，用于不同数量的寄存器变量。也许有些人仍然会认为结果是一团糟！

  1. 我假设所有内容都是字节可寻址的，尽管我实际上不依赖于字节序，并且字节是 8 位。我假设字指针可以自由地转换为字符指针，反之亦然。请注意，99% 的 C 程序都做出了这些假设。如果最高位可能被设置，我总是使用无符号字符 (unsigned char)。

  2. 类型定义 word 表示一个 32 位无符号整型。如果 unsigned long 不是 32 位，请修改 desCore.h 中的类型定义。我假设在所有地方 sizeof(word) == 4。

我在围绕密钥迭代的数据加载和存储代码中没有进行字节序特定优化的（最坏情况）成本低于 12%。此外，还有一个额外的好处是输入和输出工作区域无需进行字对齐。

可选性能优化

  1. 您应该定义 i386, vax, mc68000, 或 sparc, 中的一个，选择最接近您机器能力的那个。请参阅 desCode.h 的开头，了解此选择的具体含义。请注意，如果您选择了错误的选项，DES 代码仍然可以工作；这些只是性能调整。

  2. 对于具有功能性 asm 关键字的用户：如果您的机器支持旋转指令，您应该更改 ROR 和 ROL 宏以使用机器旋转指令。这将为每次使用节省 2 条指令和一个临时变量，或者每次加密/解密节省大约 32 到 40 条指令。

    请注意，GCC 足够智能，可以将 ROL/R 宏转换为机器旋转指令！

这些优化都相当细致，但有了它们，您应该能够获得与汇编编码相当的性能，除非

  1. 由于 C 语言中缺少位旋转运算符，旋转必须从移位操作中合成。因此，如果您的机器有旋转指令，访问 asm 将加快速度，如上文 (3) 所述（如果您使用 GCC 则不需要）。

  2. 如果您的机器的 32 位寄存器少于 12 个，我怀疑您的编译器会生成好的代码。

    i386 尝试为 386 配置代码，只声明 3 个寄存器（似乎 GCC 可以使用 ebx、esi 和 edi 来保存寄存器变量）。然而，如果您喜欢汇编编程，386 确实有 7 个 32 位寄存器，如果您使用所有这些寄存器，并使用 scaled by 8 寻址模式以及位移和其他技巧，您可以为 DesQuickCore... 获得合理的例程，每个例程大约 250 条指令。对于 DesSmall...，重新排列 des_keymap 会有所帮助，即现在 S 盒编号是索引的高位部分，而 6 位数据是低位部分；交换这些会有帮助。

    由于我无法方便地测试它，因此我没有提供我的强制 386 版本。请注意，在 desCore 的这个版本中，GCC 能够将所有内容放入寄存器中（！），并为 DesQuickCore... 例程生成大约 370 条指令！

编码说明

加密/解密例程每个使用 6 个必要的寄存器变量，其中 4 个在内部迭代期间同时活跃使用。如果您没有 4 个寄存器变量，请换一台新机器。在某些配置中，最多还会使用 8 个寄存器来保存常量。

我假设使用常量比使用寄存器开销更大

  1. 此外，我尝试将较大的常量放入寄存器中。寄存器分配优先级如下：

    • 超过 12 位的任何值 (对 RISC 和 CISC 都不利)

    • 值大于 127 (无法在 CISC 上使用 movq 或字节立即数)

    • 9-127 (可能无法使用 CISC 移位立即数或快速加/减),

    • 1-8 从未被注册，因为它们是开销最低的常量。

  2. 编译器可能过于愚蠢，无法意识到 table 和 table+256 应该分配给不同的常量寄存器，而是重复进行算术运算，因此我尽可能且有益地将这些分配给显式的 m 寄存器变量。

我假设索引操作比自动增/减操作更便宜或等效，其中索引为 7 位无符号数或更小。对于 68k 和 VAX，这个假设是相反的。

我假设地址可以廉价地由两个寄存器，或由一个寄存器和一个小常量构成。对于 68000，两个寄存器和小偏移 形式很少使用。所有索引缩放都明确完成——没有通过 log2(sizeof) 进行隐藏移位。

代码的编写方式使得即使是愚蠢的编译器也绝不需要多于一个隐藏临时变量，从而增加了所有内容都能放入寄存器中的机会。如果您重写任何代码，请牢记这一更微妙的要点。

(实际上，现在有一些代码片段确实需要两个临时变量，但修复它要么会破坏宏的结构，要么需要声明另一个临时变量)。

特殊高效数据格式

大多数情况下，位按此排列进行操作 (S7 S5 S3 S1)

003130292827xxxx242322212019xxxx161514131211xxxx080706050403xxxx

(x 位仍然存在，我只是在强调 S 盒的位置)。在计算 S6 S4 S2 S0 时，位向左旋转 4 位。

282726252423xxxx201918171615xxxx121110090807xxxx040302010031xxxx

最右边的两位通常被清零，以便较低的字节可以用作 S 盒映射表的索引。接下来的两个 x 位被设置为各种值，以访问表的各个部分。

如何使用这些例程

数据类型

指向 DesData 类型 8 字节区域的指针，用于保存密钥和 DES 的输入/输出块。

指向 DesKeys 类型 128 字节区域的指针，用于保存完整的 768 位密钥。必须进行长字对齐。

DesQuickInit()

在使用任何名称中包含 Quick 的例程之前调用此函数。它会生成这些例程所需的特殊 64k 表。

DesQuickDone()

释放此表

DesMethod(m, k)

m 指向一个 128 字节块，k 指向一个 8 字节的 DES 密钥，该密钥必须具有奇校验（否则返回 -1）并且不能是（半）弱密钥（否则返回 -2）。通常 DesMethod() 返回 0。

m 从 k 填充，因此当使用 m 调用以下例程之一时，该例程将像使用密钥 k 的标准 DES 加密/解密一样运行。如果您使用 DesMethod，您将提供一个标准的 56 位密钥；但是，如果您自己填充 m，您将得到一个 768 位密钥——但它将不是标准的。它是 768 位而不是 1024 位，因为每个字节的最低两位未被使用。请注意，这两个位将被设置为魔术常量，这在某些机器上可以加快加密/解密速度。是的，每个字节在特定迭代期间控制一个特定的 S 盒。

您真的不应该直接使用 768 位格式；我应该提供一个例程，将 128 个 6 位字节（以 S 盒映射顺序或其他方式指定）转换为适合您的正确格式。这需要进行一些字节连接和旋转操作。

Des{Small|Quick}{Fips|Core}{Encrypt|Decrypt}(d, m, s)

将 s 处的 8 个字节进行 DES 运算，结果存入 d 处的 8 个字节中。 (d,s: char *)。

如上所述，使用 m 作为 768 位密钥。

Encrypt|Decrypt 的选择很明显。

Fips|Core 决定是否执行完全标准的 FIPS 初始置换和最终置换；如果不是，则数据以非标准位序加载和存储（不带 IP/FP 的 FIPS）。

Fips 会使 Quick 慢 10%，Small 慢 9%。

Small|Quick 决定您是使用常规例程还是占用额外 64k 内存的超快速例程。Small 比 Quick 慢 50%，但 Quick 需要 32 倍的内存。Quick 适用于只进行 DES 操作的程序，例如加密过滤器等。

在您的机器上编译

代码中没有机器依赖性（参见移植说明），除了 desTest.c 中的 now() 宏。所有生成的表都是机器无关的。您应该使用适合您的编译器的优化标志（最大优化）编辑 Makefile。

加速 Kerberos（和/或其 DES 库）

请注意，我已经在 desUtil.c 中通过 des_key_sched() 和 des_ecb_encrypt() 函数包含了 Kerberos 兼容接口。要将这些与 Kerberos 或 Kerberos 兼容代码一起使用，请在链接器命令行中将 desCore.a 放在 Kerberos 兼容库之前。您不需要 #include desCore.h；只需包含 Kerberos 库提供的头文件即可。

其他用途

desCode.h 中的宏对于在更复杂的加密例程中嵌入 DES 内联函数非常有用。