超空间优化代码

Question

有一些关键的独立算法 - 特别是与加密相关的算法，例如 AES、RSA、SHA1 等 - 您可以在互联网上免费找到它们的许多实现。

有些被编写为良好且可移植的干净 C。

有些被编写为快速 - 通常使用宏和显式展开。

据我所知，没有人试图变得特别小 - 所以我只能编写自己的 - 明确的 AES128 解密和 ARM THUMB2 的 SHA1。 （我已经通过使用 GCC 和 -Os 和 -mthumb 等编译我能找到的所有目标机器来进行验证）

我可以使用哪些模式和技巧来做到这一点？

是否有可以汇总代码的编译器/工具？

Answer 1

在优化空间（或速度）之前：现在编译器非常聪明，您是否尝试过，如果您告诉编译器优化空间，aes128 的正常可读实现是否足够小以满足您的需求？

去编写你自己的 aes128 版本也许是一件很好的教育事情，但你肯定会与 bug 作斗争，而密码学并不是那种凭空出现的琐碎的东西。错误或薄弱（由于实现中的一些错误）几乎是最糟糕的情况。

因为您的目标是 ARM，而 gcc 作为该平台的编译器非常常见：

-Os   Optimize for size.  

     -Os enables all -O2 optimizations that do not typically 
      increase code size. It also performs further optimizations
      designed to reduce code size.

Answer 2

这取决于您要优化的空间类型：代码或数据。常用的 AES128 本质上有三种变体，每种变体的预计算查找表空间量有所不同。

• 最快的版本使用 4k，排列为四个 32 位 x 256 条目查找表（通常称为 T 表）。如果您能负担得起那么多的数据空间，那么此版本中唯一的指令就是组合表结果的 EOR，这些指令将汇总成非常小的代码片段。
• 中间版本使用 8 位 x 256 条目查找表来对 SBox 进行编码。剩余指令需要实现移位行和混合列步骤，因此代码大小较大。
• 最小（数据大小）版本根本不使用任何查找表，但需要计算所有单独的 AES 字段操作，包括反转。即使您将域乘法和求逆都折叠到子例程中，这也会使用最多的指令。