跳到主要内容

2.5 The Poly1305 Algorithm (Poly1305 算法)

2.5 The Poly1305 Algorithm (Poly1305 算法)​

Poly1305 是由 D. J. Bernstein 设计的一次性认证器 (one-time authenticator). Poly1305 接收一个 32 字节的一次性密钥和一条消息, 并产生一个 16 字节的标签 (tag). 该标签用于认证消息.

原始论文 ([Poly1305]) 的标题是 "The Poly1305-AES message-authentication code", 其中的 MAC 函数需要一个 128 位的 AES 密钥, 一个 128 位的 "附加密钥 (additional key)", 以及一个 128 位的 (非机密) nonce. 文中使用 AES 来加密 nonce, 从而获得唯一的 (且机密的) 128 位串, 但正如论文所述, "此处并无任何针对 AES 的特殊之处. 可以将 AES 替换为从任意 nonce 集合到 16 字节串的任意带密钥函数."

无论密钥如何生成, 密钥都会被划分为两部分, 称为 "r" 和 "s". 数对 (r,s) 应当唯一, 且对每次调用而言必须是不可预测的 (这也就是最初通过对 nonce 加密来获得它的原因), 而 "r" 可以为常量, 但在使用前需要按下述方式修改: ("r" 被视为一个 16 字节的小端序数):

  • r[3], r[7], r[11] 和 r[15] 必须将其高四位清零 (即数值小于 16)

  • r[4], r[8] 和 r[12] 必须将其低两位清零 (即能被 4 整除)

下列示例代码将 "r" 钳制 (clamp) 为符合要求的取值:

/*
Adapted from poly1305aes_test_clamp.c version 20050207
D. J. Bernstein
Public domain.
*/

#include "poly1305aes_test.h"

void poly1305aes_test_clamp(unsigned char r[16])
{
  r[3] &= 15;
  r[7] &= 15;
  r[11] &= 15;
  r[15] &= 15;
  r[4] &= 252;
  r[8] &= 252;
  r[12] &= 252;
}

其中 "&=" 是 C 语言的按位与赋值运算符.

"s" 应当是不可预测的, 但每次同时唯一地生成 "r" 与 "s" 完全可以接受. 由于二者各为 128 位, 对它们进行伪随机生成 (见第 2.6 节) 也是可以接受的.

Poly1305 的输入为:

  • 一个 256 位的一次性密钥

  • 任意长度的消息

输出是一个 128 位的标签.

首先, 对 "r" 的值进行钳制.

接着, 将常量素数 "P" 设为 2^130-5: 3fffffffffffffffffffffffffffffffb. 同时将变量 "accumulator" (累加器) 置为零.

接着, 将消息划分为 16 字节的块. 最后一个块可能更短:

  • 将该块按小端序读成一个数.

  • 在八位字节数量之外再追加一位. 对 16 字节块而言, 这等价于在该数上加上 2^128. 对较短的块, 附加位可以对应 2^120, 2^112, 或任意能被 8 整除的 2 的幂, 一直到 2^8.

  • 若该块不是 17 字节长 (即最后一个块), 则用零填充. 若将各块视为数值, 则此步骤没有实质影响.

  • 将此数加到累加器上.

  • 乘以 "r".

  • 将累加器设为结果对 p 取模. 概括而言: Acc = ((Acc+block)*r) % p.

最后, 将密钥 "s" 的值加到累加器上, 并以小端序序列化最低 128 位以形成标签.

2.5.1 The Poly1305 Algorithms in Pseudocode (伪代码中的 Poly1305 算法)​

clamp(r): r &= 0x0ffffffc0ffffffc0ffffffc0fffffff
poly1305_mac(msg, key):
   r = le_bytes_to_num(key[0..15])
   clamp(r)
   s = le_bytes_to_num(key[16..31])
   a = 0  /* a is the accumulator */
   p = (1<<130)-5
   for i=1 upto ceil(msg length in bytes / 16)
      n = le_bytes_to_num(msg[((i-1)*16)..(i*16)] | [0x01])
      a += n
      a = (r * a) % p
      end
   a += s
   return num_to_16_le_bytes(a)
   end

2.5.2 Poly1305 Example and Test Vector (Poly1305 示例与测试向量)​

在本例中, 我们将不采用 AES 生成一次性密钥, 而假定已获得下列密钥素材:

  • 密钥素材 (Key Material): 85:d6:be:78:57:55:6d:33:7f:44:52:fe:42:d5:06:a8:01:03:80:8a:fb:0d:b2:fd:4a:bf:f6:af:41:49:f5:1b

  • s 作为八位字节串 (octet string): 01:03:80:8a:fb:0d:b2:fd:4a:bf:f6:af:41:49:f5:1b

  • s 作为 128 位数: 1bf54941aff6bf4afdb20dfb8a800301

  • 钳制前的 r: 85:d6:be:78:57:55:6d:33:7f:44:52:fe:42:d5:06:a8

  • 钳制后的 r 作为数值: 806d5400e52447c036d555408bed685

对于消息, 我们使用一段短文本:

待认证的消息 (Message to be Authenticated):

000  43 72 79 70 74 6f 67 72 61 70 68 69 63 20 46 6f  Cryptographic Fo
016  72 75 6d 20 52 65 73 65 61 72 63 68 20 47 72 6f  rum Research Gro
032  75 70                                            up

由于 Poly1305 按 16 字节块工作, 这条 34 字节的消息被分为三块. 下列计算中, "Acc" 表示累加器, "Block" 表示当前块:

块 #1

Acc = 00
Block = 6f4620636968706172676f7470797243
Block with 0x01 byte = 016f4620636968706172676f7470797243
Acc + block = 016f4620636968706172676f7470797243
(Acc+Block) * r =
     b83fe991ca66800489155dcd69e8426ba2779453994ac90ed284034da565ecf
Acc = ((Acc+Block)*r) % P = 2c88c77849d64ae9147ddeb88e69c83fc

块 #2

Acc = 2c88c77849d64ae9147ddeb88e69c83fc
Block = 6f7247206863726165736552206d7572
Block with 0x01 byte = 016f7247206863726165736552206d7572
Acc + block = 437febea505c820f2ad5150db0709f96e
(Acc+Block) * r =
     21dcc992d0c659ba4036f65bb7f88562ae59b32c2b3b8f7efc8b00f78e548a26
Acc = ((Acc+Block)*r) % P = 2d8adaf23b0337fa7cccfb4ea344b30de

最后一块

Acc = 2d8adaf23b0337fa7cccfb4ea344b30de
Block = 7075
Block with 0x01 byte = 017075
Acc + block = 2d8adaf23b0337fa7cccfb4ea344ca153
(Acc + Block) * r =
     16d8e08a0f3fe1de4fe4a15486aca7a270a29f1e6c849221e4a6798b8e45321f
((Acc + Block) * r) % P = 28d31b7caff946c77c8844335369d03a7

加上 s 后得到下列数, 再将其序列化即得标签:

Acc + s = 2a927010caf8b2bc2c6365130c11d06a8

标签 (Tag): a8:06:1d:c1:30:51:36:c6:c2:2b:8b:af:0c:01:27:a9

最后于 更新