メインコンテンツまでスキップ

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を必要とします. そこではnonceを暗号化するためにAESが用いられ, 一意の (かつ秘密の) 128ビット列が得られますが, 論文が述べるとおり, "ここでAESに特別な意味はない. AESは, 任意のnonce集合から16バイト列への任意の鍵付き関数に置き換えてよい."

鍵の生成方法にかかわらず, 鍵は "r" と "s" と呼ばれる2部に分割されます. 組 (r,s) は一意でなければならず, 各呼び出しについて予測不可能でなければなりません (そのためもともとnonceを暗号化して得ていたのです). 一方 "r" は定数でも構いませんが, 使用する前に次のように修正する必要があります: ("r"は16オクテットのリトルエンディアン数として扱います):

  • r[3], r[7], r[11], r[15] は, 上位4ビットがクリアされていること, つまり16未満であることが求められます

  • r[4], r[8], r[12] は, 下位2ビットがクリアされていること, つまり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言語のビット単位AND代入演算子です.

"s" は予測不可能であるべきですが, "r" と "s" を毎回ともに一意に生成することは全く問題ありません. それぞれが128ビットであるため, 疑似乱数により生成することも (2.6節参照) 受け入れ可能です.

Poly1305への入力は次のとおりです:

  • 256ビットのワンタイム鍵

  • 任意の長さのメッセージ

出力は128ビットのタグです.

まず, "r" の値をクランプします.

次に, 定数素数 "P" を 2^130-5, すなわち 3fffffffffffffffffffffffffffffffb に設定します. また変数 "accumulator" (累算器) をゼロにします.

次に, メッセージを16バイトのブロックに分割します. 最後のブロックはそれより短い場合があります:

  • ブロックをリトルエンディアン数として読み取ります.

  • オクテット数を超える位置に1ビットを加えます. 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: 01:03:80:8a:fb:0d:b2:fd:4a:bf:f6:af:41:49:f5:1b

  • 128ビット数としての s: 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バイトのメッセージは3ブロックに分割されます. 以下の計算では, "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

に最終更新