65.9K
CodeProject 正在变化。 阅读更多。
Home

《编译器》：8051 的 AES-128 密码，汇编实现

CPallini
starIconstarIconstarIconstarIconstarIcon

5.00/5 (6投票s)

2019年11月12日

CPOL

8分钟阅读

viewsIcon

10616

downloadIcon

491

为 8051 微控制器实现的 AES-128 密码算法的汇编实现

Code successfully executed

图片 0：代码在 MCU 8051 IDE 模拟器中成功运行

引言

本文描述了我使用 8051 微控制器的汇编语言实现的 AES-128 加密算法。

背景

最近（别问我为什么），我对 8051 微控制器产生了兴趣。

正如您可能已经知道的，8051 是一款 CISC、8 位 MCU，内存资源稀少（内部 RAM 只有 128 字节！详情请参见专门的 Wikipedia 页面[^]）。

我实现了 AES-128 密码算法，以便熟悉其指令集并“感受 CISC 的魅力”（我习惯于 RISC 设备）。

以下文档是我的背景资料，也可能对您有所帮助。

这是 AES 算法的描述。它写得非常好（非常！）：我建议大家看看这份精彩的文档。

这是编程 8051 汇编的“参考”。您可以在网上找到其 PDF 文件（我不提供链接，因为我无法找到其官方存储库）。

  1. FIPS 197，高级加密标准 (AES) - NIST 页面
  2. (Intel) MCS@51 微控制器系列用户手册

此外，我使用了 MCU 8051 IDE（参见 MCU 8051 IDE - Wikipedia[^]）来编辑、编译（即从汇编生成机器码）和运行代码（通过内置的模拟器）。

同样，这样的 IDE 是一款出色的软件（向Martin Ošmera 致敬）。不过，它只在 Linux OS 上运行。我强烈建议 Windows 用户弄一个 Linux 盒子（例如，虚拟机）来使用它。

Using the Code

您需要使用 cipher 例程，它只有一个参数，即明文（16 字节）数组的地址，存储在 dpl 寄存器中，而加密密钥则硬编码在闪存中（当然，您可以更改这种行为）。

该例程会就地产生输出（即用相应的密文替换明文数组的内容）。

提供的项目（如图 0 所示）使用了与 NIST 文档的“附录 B – 密码示例”中相同的输入（和密钥），幸运的是，产生了相同的输出。

实现细节

伪代码

实现的原点是 NIST 文档 [1] 中提供的伪代码，针对 AES-128 进行了专门化并稍作重新排列。

KeyExpansion(byte key[16], word w[44])
  //...
end

Cipher(byte in[16], byte out[16], word w[44])
  begin
  byte state[4,4]
  state = in
  AddRoundKey(state, w[0, 3])
  for round = 1 step 1 to 10
    SubBytes(state)
    ShiftRows(state)
    if round < 10 then
      MixColumns(state)
    end if
    AddRoundKey(state, w[round*4, round*4 +3])
  end for
  out = state
end
代码 0：原始算法伪代码

不幸的是，由于扩展密钥的内存需求（w[44] 数组，长 176 字节，参见 [1] 中第 5.2 节：“密钥扩展”），这种伪代码无法直接在 8051 MCU 上实现。

为了克服这一障碍，密钥扩展步骤是在逐轮直接在 Cipher 代码中执行的：使用前一轮密钥计算“轮密钥”。

这样，密钥扩展的内存需求就减少到 32 字节。

修改后的伪代码如下。

byte prevkey[16]
byte roundkey[16]

InitKey()
  // initialize roundkey with key
  // ..
end

NextKey(byte round)
  // computes roundkey using prevkey and round variable
  // ..
end
	
Cipher(byte in[16])
  begin
  InitKey()
  AddRoundKey(in, roundkey)
  for round = 1 step 1 to 10
    SubBytes(in)
    ShiftRows(in)
    if round < 10 then
      MixColumns(in)
    end if
    NextKey(round)
    AddRoundKey(in, roundkey)
  end for
end
代码 1：“修改后”的伪代码

其中

  • InitKey 和 NextKey 组合例程取代了 KeyExpansion 步骤。
  • 密码是就地进行的（移除了 state 和 out 变量）。
  • 显示了对外部 roundkey 和 prevkey（由 NextKey 使用）数组的显式依赖。

实际的 8051 汇编代码

代码由以下部分组成：

  • 常量表
  • 保留的 RAM
  • XTIME 宏
  • 主例程 (cipher)
  • 子例程

下面将详细介绍每个组件。

常量表

该算法需要一些常量表，即 sbox 和 rcon。

此外，明文块和用户提供的加密密钥数组需要存储在持久内存中，以提供相应的 RAM 变量的至少初始化代码。

总而言之，我们有：

数组 大小（字节） 备注
sbox 256 替换矩阵，参见文档 [1] 的“5.1.1 SubBytes()Transformation”。
rcon 11 轮常量，用于密钥扩展步骤，参见 [1] 的“5.2 密钥扩展”。
input 16 算法输入数据（明文）
cipherkey 16 用户提供的 128 位加密密钥
表 1：存储在闪存中的常量数组

注意：我使用了“数组”而不是“表”来描述常量。这更能反映实现的角度：“列”和“行”操作在代码中被展平为它们的数组等价物（代码注释引用了原始算法术语）。

所有数组都是从可用 C 实现中找到的相应数组自动生成的。

值使用 db 汇编指令存储在闪存中（有关详细信息，请参阅 MCU 51 IDE 文档），如下面的图所示。

Constant table definitions in the MCU 8051 IDE

图片 1：MCU 8051 IDE 中的常量表定义

保留的 RAM

算法实现使用了一些 MCU 内部 RAM，即：

所有可用的 8051 通用寄存器（r0、…、r7、a、…），但 dpl 除外（它被保留）。

以下内存块：

  • 16 字节，从 0x70 开始，用于存储当前轮密钥
  • 16 字节，从 0x60 开始，用于存储上一轮密钥
  • 1 字节，在地址 0x5F，用于保存当前轮号

这样，算法消费者还可以使用相当大的 RAM（63 字节！）。

堆栈既用于隐式地存储子例程调用中的返回地址，也用于显式地（通过 push/pop 指令）保存 dpl 寄存器的值。

XTIME 宏

XTIME 实现算法 xtime 操作，即在伽罗瓦域 GN(2^8) 中乘以 x（参见 [1] 的“4.2.1 Multiplication by x”）。

该宏在 mix_columns 子例程中使用了多次（8 次）。

它解决为左移和条件 XOR（如果其操作数原始值具有位 7 设置，则与 0x1B 进行 XOR）。

The XTIME macro

图片 2：XTIME 汇编宏

（图片 2 有一个小谎言，您可以在提供的源代码中看到实际的宏定义。）

注意

  • 寄存器 a 同时用作参数和结果。
  • 由于 8051 MCU 不提供移位指令，
    add a, a
    被用来代替。如果 a 寄存器原始值的位 7 设置，它会设置进位，因此代码在“进位清除”条件下跳过 XOR。
  • 使用宏而不是子例程，因为在如此少量的代码上，调用/返回开销会很高。

主例程 (Cipher)

概念上，cipher 例程精确地遵循“修改后”的伪代码（代码 1），并且实现也反映了这一点，因此它会解析为对各种辅助例程的调用，例如：

Sample subroutine call in cipher code

图片 3：cipher 代码中的示例子例程调用

在其启动代码和遍历各个轮的循环内部。

AddRoundKey 和 SubBytes 操作是例外：没有子例程用于它们，它们的代码直接包含在 cipher 例程中。

在下面的图中，SubBytes 代码被报告为访问闪存常量的示例。

The assembly code corresponding to SubBytes operation

图片 4：SubBytes 操作对应的汇编代码

具体来说，“替换值”rcon[state[k]] 是这样获得的：

  1. 将 state[k] 移入寄存器 a
  2. 将 rcon 的地址移入 dptr 寄存器
  3. 使用 movc 指令将闪存地址 (a+dptr) 的值移入寄存器 a。

子例程

辅助例程是：

  • init_key
  • next_key
  • shift_rows
  • mix_columns

init_key 子例程

init_key 子例程只是将用户提供的密钥（闪存中的 cipherkey）复制到 roundkey 数组中，所以没什么好写的。

next_key 子例程

next_key 子例程更复杂。它必须使用当前轮密钥和下一轮的编号作为输入，来生成下一轮加密的密钥。

它开始将 rndkey 数组的内容复制到 prvkey 中。

然后它初始化临时变量 temp（即 r4,..r7 寄存器），并开始计算 w4[nround*4]，忠实地遵循 [1] 中描述的操作，即：

temp = rotw(w3)
temp = subword(temp)
temp ^= rcon[nround]
w[nround*4] = temp ^ w[(nround-1)*4]
代码 2：用于计算 w4[round*4] 的步骤

之后，它计算其他（更简单的）值。

w[nround*4+1] = w[nround*4] ^ w[(nround-1)*4+1]
w[nround*4+2] = w[nround*4+1] ^ w[(nround-1)*4+2]
w[nround*4+3] = w[nround*4+2] ^ w[(nround-1)*4+3]
代码 3：next key 的其他组件要简单得多

您可以很容易地按照上述步骤在 next_key 源代码中进行，因为它们都已注释。

例如：

The temp ^= rcon[nround] step

图片 5：temp ^= rcon[nround] 步骤

shift_rows 子例程

这是对文档 [1]“5.1.2 ShiftRows() Transformation”的直接实现。同样，您可以按照它进行，这要归功于注释。我认为棘手之处在于：

  • 跟踪当前行和列索引
  • 在使用 subb 指令之前注意清除进位标志

mix_columns 子例程

这也是对文档 [1]（“5.1.3 MixColumns() Transformation”）中相应操作的直接实现。

它开始将列分量复制到临时变量（r4,..r7）中，然后应用 [1] 中描述的步骤，即通过加法运算符（XOR）和乘法运算符（xtime）对列分量本身进行线性组合。

Excerpt of the mix_columns subroutine

图片 6：mix_columns 子例程的摘录

init_key 和 next_key 以增量方式、逐轮实现 KeyExpansion 操作，而 shift_rows 和 mix_columns 分别提供文档 [1] 中“5.1.2 ShiftRows() Transformation”和“5.1.3 MixColumns() Transformation”中描述的功能。

关注点

免责声明

这是我的第一个 8051 汇编程序，代码没有针对 NIST 向量进行完全测试。这是一个看似成功的实验，仅此而已。如果您打算使用它，我强烈建议您根据向量进行充分测试。

学到的东西

在 8051 上实现 AES-128 产生了双重效果：

  • 让我欣赏 AES 加密算法的细节。
  • 让我熟悉了 8051 的指令集和架构。

一些数字

代码内存使用，约 16%

完整的密码代码（包括常量表）长 668 字节（闪存为 4096 字节）。

内部 RAM 使用，约 38%（不包括堆栈）

实现使用了 49 字节用于增量密钥扩展和临时变量。

执行时间：14.162 毫秒（根据模拟器）

这大致相当于加密一个 16 字节块的 10^4 条指令（这显然是此实现的一个薄弱环节）。

下一步该做什么？

当然是解密实现。

历史

  • 2019 年 11 月 11 日 - 首次发布
© . All rights reserved.