快速且可移植的 DES 加密和解密

注意

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

des - 快速且可移植的 DES 加密和解密。

版权所有 © 1992 Dana L. How

本程序是自由软件；您可以根据自由软件基金会发布的 GNU 库通用公共许可证的条款重新分发和/或修改它；无论是许可证的第 2 版，还是（由您选择）任何后续版本。

本程序的发布希望它是有用的，但不作任何担保；甚至不包含对适销性或特定用途适用性的默示担保。有关更多详细信息，请参阅 GNU 库通用公共许可证。

您应该已经收到一份 GNU 库通用公共许可证的副本以及本程序；如果没有，请写信给自由软件基金会，地址为 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 创建）。后者以参数化的方式设置，因此它可以很容易地被追求最后微秒的速度恶魔黑客修改。你会发现检查一个特定的实现，然后再考虑这个实现，然后继续使用这个实现来处理公共抽象骨架，会更具启发性。

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

此代码（字节顺序无关）

  • 每次加密 30us（选项：64k 表，无 IP/FP）

  • 每次加密 33us（选项：64k 表，FIPS 标准位排序）

  • 每次加密 45us（选项：2k 表，无 IP/FP）

  • 每次加密 48us（选项：2k 表，FIPS 标准位排序）

  • 设置新密钥需要 275us（使用 1k 的密钥表）

    这具有我见过的最快的加密/解密例程。由于我感兴趣的是快速的 des 过滤器而不是 crypt(3) 和密码破解，所以我还没有真正费心去加速密钥设置例程。此外，我无意重新实现 mit kerberos des 库中的所有其他垃圾，所以我只提供了我的例程和一些小的存根接口，以便它们可以用作 mit 代码或以下任何 mit 兼容包的直接替代品。（请注意，由于缓存效应，上面的前两个计时变化很大）。

来自澳大利亚的 Kerberos des 替代品（版本 1.95）

  • 每次加密 53us（使用 2k 的表）

  • 设置新密钥需要 96us（使用 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 版本上的评论

  • 每次加密 68us（使用 2k 的表）

  • 设置新密钥需要 96us（使用 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 库

  • 每次加密 108us（使用 34k 的表）

  • 设置新密钥需要 134us（使用 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 代码（字节顺序相关）

  • 每次加密 165us（使用 6k 的表）

  • 设置新密钥需要 478us（使用 <1k 的密钥表）

    因此，尽管此代码中有注释，但仍有可能获得更快的代码和更小的表，以及使表与机器无关。（代码从 prep.ai.mit.edu 获取）

加州大学伯克利分校代码（取决于机器的字节序）

  • 每次加密 226us

  • 设置新密钥需要 10848us

    表大小不清楚，但它们看起来不是非常小（代码从 wuarchive.wustl.edu 获取）

动机和历史

不久前，我想要一些 des 例程，而 sun 的手册页上记录的例程要么不存在，要么转储核心。我听说过 kerberos，并且知道它使用 des，所以我认为我会使用它的例程。但是，一旦我得到了它并查看了代码，它真的引发了很多令人讨厌的地方 - 它太复杂了，代码的编写没有利用 IP、E 和 FP 等操作的规则结构（即作者在编码之前没有坐下来思考），它太慢了，作者试图通过添加更多语句来澄清代码，以使数据移动更一致，而不是简化其实现并减少所有数据移动（特别是他使用 L1、R1、L2、R2），而且它充满了针对特定机器的白痴调整，这些调整未能提供显著的加速，但确实使一切都变得模糊不清。因此，我从他的验证程序中获取了测试数据并重写了其他所有内容。

过了一段时间，我遇到了上面提到的很棒的 crypt(3) 包。这个人每次表查找计算 2 个 sbox 而不是 1 个（并且在此过程中使用更大的表）这一事实，鼓励我也这样做 - 这是一个微不足道的改变，我之前因表大小更大而感到害怕。在他的例子中，他没有意识到你不需要以两种形式保存工作数据，一种用于方便地使用一半的 sbox 进行索引，另一种用于方便地使用另一半；相反，你可以以第一半的形式保存它，并使用简单的旋转来获取另一半。这意味着我（几乎）有一半的数据操作和一半的表大小。公平地说，他可能在他的表中编码了一些特定于 crypt(3) 的内容 - 我没有检查。

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

移植说明

我不希望编写一个依赖于字节序和其他机器怪癖的庞大混乱的代码，并且这种代码必然会为不同的机器生成不同的代码和不同的查找表。例如，可以参考 Kerberos 代码，看看我不想做的事情；他们所有针对特定字节序的 优化 都使代码变得晦涩难懂，而且最终比一个更简单的、与机器无关的方法更慢。然而，总会有一些可移植性的考虑，我加入了一些选项来调整寄存器变量的数量。也许有些人仍然会认为结果是一团糟！

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

  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. 如果您的机器少于 12 个 32 位寄存器，我怀疑您的编译器会生成好的代码。

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

    由于我无法方便地对其进行测试，因此我没有提供我的硬塞 386 版本。请注意，对于此版本的 desCore，gcc 能够将所有内容放入寄存器中（！），并为 DesQuickCore... 例程生成大约 370 条指令！

编码注意事项

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

我假设使用常量比使用寄存器更昂贵

  1. 此外，我试图将较大的常量放入寄存器中。注册优先级如下

    • 任何大于 12 位的（对 RISC 和 CISC 不利）

    • 值大于 127 的（在 CISC 上不能使用 movq 或字节立即数）

    • 9-127（可能无法使用 CISC 移位立即数或 add/sub quick）

    • 1-8 从未注册，因为它们是最便宜的常量。

  2. 编译器可能太笨，无法意识到表和表 + 256 应该分配给不同的常量寄存器，而是重复地进行算术运算，因此我在可能且有帮助的情况下将它们分配给显式的 m 寄存器变量。

我假设索引比自动递增/递减更便宜或相等，其中索引是 7 位无符号或更小。对于 68k 和 vax，此假设被颠倒。

我假设可以从两个寄存器或一个寄存器和一个小的常量中廉价地形成地址。对于 68000，两个 寄存器 和一个 小 偏移形式很少使用。所有索引缩放都显式完成 - 没有 log2(sizeof) 的隐藏移位。

代码的编写方式是，即使是笨编译器也永远不需要超过一个隐藏的临时变量，从而增加了所有内容都适合寄存器的机会。如果您要重写任何内容，请记住这个更微妙的点。

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

特殊高效的数据格式

位在大多数情况下以此排列方式操作 (S7 S5 S3 S1)

003130292827xxxx242322212019xxxx161514131211xxxx080706050403xxxx

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

282726252423xxxx201918171615xxxx121110090807xxxx040302010031xxxx

最右边的两位通常被清除，因此较低的字节可以用作 sbox 映射表的索引。接下来的两个 x 位被设置为不同的值以访问表的不同部分。

如何使用例程

数据类型

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

指向 128 字节区域的指针，类型为 DesKeys，用于保存完整的 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 位，因为每个字节的最低两位未使用。请注意，这两位将被设置为魔法常量，从而加快某些机器上的加密/解密速度。是的，每个字节都控制特定迭代期间的特定 sbox。

您真的不应该直接使用 768 位格式；我应该提供一个例程，将 128 个 6 位字节（按 S-box 映射顺序或类似顺序指定）转换为适合您的正确格式。这将需要一些字节连接和旋转。

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 初始和最终置换；如果不是，则以非标准的位顺序加载和存储数据（FIPS w/o IP/FP）。

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 函数非常有用。