1. はじめに
共通鍵暗号であるAESの、
なんかよさそうな方式にGCMというものがあります。
こいつの乗算だけを実装します。
最初に言っておきますが理論は説明しません、というかできません。
知らないし。
ここで説明するのは、どうやって実装するかです。
特にNISTが配布しているPDFの乗算の最適化を詳しく見ていきます。
あとで詳しく言いますが、先に言っておかないとがっかりする人がいるかもしれないので、
これだけは先行して書いておきます。
作成する乗算の方法は下記の通り。
- No tables
- Simple, 8-bit tables
- Simple, 4-bit tables
- Simple, 1-bit tables (PDFにないもの)
次のやつは作りません。
- Shoup’s, 8-bit tables
- Shoup’s, 4-bit tables
参考としてCommon Lispの完成品を下記にリンクしておきます。
AES, CCM, GCMが使えます。
https://github.com/nptcl/fixed/blob/main/aes/aes.lisp
1.1. 仕様書
まずは仕様書から。
たぶんこれが元だと思います。
- Recommendation for Block Cipher Modes of Operation: Galois/Counter Mode (GCM) and GMAC
https://nvlpubs.nist.gov/nistpubs/legacy/sp/nistspecialpublication800-38d.pdf
もう一つあり、こいつは何なんだ?
検索で出てくるけどNIST内でリンク張ってるところが見つからなかった。
- The Galois/Counter Mode of Operation (GCM)
https://csrc.nist.rip/groups/ST/toolkit/BCM/documents/proposedmodes/gcm/gcm-spec.pdf
この下の方のPDFが最高なんです。
実装するという視点で言わせてもらいますが、
上の方は参考程度で、
下の方を見ながら作った方がいいと思います。
下は、encrypt, ghash, decryptをそれぞれ
数式で表したものがあるのですが、
それがすごく良かったです。
乗算以外はその式だけで作れます。
むしろそこだけ見たほうがわかりやすいです。
乗算はどちらのPDFを見ても作れると思います。
おすすめは下の方のPDFです。
さらに下のPDFは、乗算の最適化まで言及されています。
そいつをちゃんとやろう、というのがここでの目的です。
2. ガロア体の演算
ガロア体とは有限体の事だそうです。
GCMではの有限体を扱うようで、
と書くそうです。
GCMではない、素のAESではが使われていたのを覚えています。
楕円曲線ではさんざん素数の有限体をやってきました。
しかし今回はであり、
素数ではないので楕円曲線の時とはだいぶ事情が違います。
単にでひたすら割ってやるだけではダメみたいです。
これに気が付くのに時間がかかってしまった。
まず普通の値と、ガロア体の値の対応を考えます。
どちらも128bitの整数を扱いますが、
ビットのオーダーが逆転します。
普通の整数の最下位1bitは、ガロア体では最上位1bitになります。
なんでこんなことになるのかは知りませんが、
実装するならちゃんと覚えておかなければいけません。
覚えておいてほしいので詳しく書きます。
普通の値の、9
を二進数で表してみます。
00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00001001
ちょっと長いですね。
扱う整数が128bitなので、こんなに長くなるわけです。
書きたくないので次のように省略します。
00000000 ... 00001001
左が上位ビットで、右が下位ビットです。
しかし、ガロア体の演算を行う際には逆転するので、
左が下位ビットになります。
これを覚えておいてください。
↓ ガロア体での最下位ビット 00000000 ... 00001001 ↑ 普通の値の最下位ビット
変数に値が整数が入っているとして、
ガロア体での
番目のビットを
と記載します。
このとき、は整数の最上位ビットであることに注意してください。
つまり、値が9の場合はです。
これも気が付くまで全然意味が分からなかった。
整数は128bitなので、が最下位ビットになります。
つまり、値が9の場合はです。
ではガロア体に話を進めます。
ガロア体で使う演算は二種類。
加算と乗算です。
加算は単純なXORです。
普通の加算と違い、繰上りを考慮する必要がありません。
これは通常の加算よりだいぶ楽ですね。
XORは⊕と表します。
つまり、と
の加算は、
です。
乗算はかなり面倒です。
乗算はと表すことにします。
乗算の実装は、2進数のひっ算で計算すると思ってください。
ひっ算に必要な処理は、加算とシフトです。
シフトとはひっ算を進めていくうえで、
足す数の位を上げていく処理です。
このシフトを行った際に128bitを超えた場合は、
ガロア体特有の方法で値を修正する必要があります。
普通に考えれば128bitと128bitの乗算結果は256bit以下ですが、
今はガロア体ですので何とかして128bitに納めなければならないわけです。
素数のガロア体だったら乗算を求めた後に余りを求めればいいだけですが、
今回は素数ではないので簡単にはいきません。
単純に128bit切り捨てではだめです。
これが面倒、というか難しいわけです。
ここまでわかれば乗算のコードを理解できると思います。
3. 乗算コードの説明
乗算の実装を示します。
Z ← 0, V ← X for i = 0 to 127 do if Yのi番目のビット = 1 then Z ← ZとVの加算 end if V ← Vの2倍 end for return Z
このコードは、乗算を行うための汎用的なコードです。
ただの整数だろうがガロア体だろうが、これを行うと乗算できます。
やっていることはただの2進数のひっ算です。
のビットを一つずつ見ていき、
ビットが立っていたら結果に
をシフトした値を加算します。
順番に見ていきます。
for
の中の加算の部分を取り上げます。
if Yのi番目のビット = 1 then Z ← ZとVの加算 end if
先にの
番目のビットを
と表すと書きました。
ということで、次のように書き直します。
if Yi = 1 then Z ← ZとVの加算 end if
for
文の最初はi=0
ですが、は
に格納されている整数の
最上位ビットであることに注意してください。
何度も書いていますが、ガロア体の演算ではビットの順番が逆転します。
Y0
は、実際の値Y
の最上位ビットです。
Y127
は、実際の値Y
の最下位ビットです。
コードの内容は、ビットが立っていたら
に
を加算するという内容です。
はビットの位置に応じて、
をシフトした内容です。
と
の加算は、単純なXORですので、
とても簡単に書き直すことができます。
if Yi = 1 then Z ← Z ⊕ V end if
この加算(XOR)は通常の加算とは異なり繰り上げがありませんので、
128bitを超えることがありません。
これで加算の部分は完了です。
問題は次の文です。
V ← Vの2倍
ここはちゃんと理解してください。
PDFには次のように記載されています。
if V127 = 0 then V ← rightshift(V) else V ← rightshift(V) ⊕ R end if
まず最初のV127
というのは、
のことで、
ガロア体の演算における
の最上位ビットを表します。
つまり、格納されている整数の最下位ビットです。
最上位だの最下位だの、紛らわしいです。
そもそも何をしようとしているのかを説明します。
ここでは、を2倍するためにシフトしています。
普通のプログラミングであれば左に1つシフトすることで2倍にすることができますが、
今はガロア体での演算のために右にシフトしています。
自分はこれに気が付くのに時間がかかってしまいました。
なんで右にシフトしてるの?ってずっと思ってた。
もしシフトして128bitを超えるような場合には、
ガロア体では単純に切り捨てることができないんです。
そこで、シフトで切り捨てられるビットをあらかじめ判定しておいて、
もしそれが1であったときは、
いきなり出てきたという定数のXORを取ります。
が何者かというと次の通り。
0xE1
を120bit分だけ左にシフトしてください。
これはガロア体での話ではなく、
0xE1
に対して普通にを乗算してくださいという意味です。
そういう定数のXORを取ることで、
はみ出したのビットを何とかしてくれるんだそうです。
どうしてそうなるかはPDFに説明がありますのでご確認ください。
私にはわかりません。
これらを全部まとめると、
PDFに記載されているコードになります。
次のコードは引用です。
Z ← 0, V ← X for i = 0 to 127 do if Yi = 1 then Z ← Z ⊕ V end if if V127 = 0 then V ← rightshift(V) else V ← rightshift(V) ⊕ R end if end for return Z
これが完成形です。
上記のコードをそのまま実装すれば正しく動きます。
を2倍することろに関してはもう少し説明が必要です。
2倍するという演算を、次のように表すことができるとのこと。
との乗算の内容は、先ほど提示したコードにある通り、
右にシフトしてあふれた場合は
でXORを取るというものです。
このは、あとでいっぱい使うので覚えておいてください。
コードも次のように書き直せます。
Z ← 0, V ← X for i = 0 to 127 do if Yi = 1 then Z ← Z ⊕ V end if V ← V ⋅ P end for return Z
乗算を計算するコードにの乗算が現れて混乱しますが、
別に再起呼び出しをするのではなく、
が単純に2倍を表すと考えていいと思います。
は複数回乗算できることを覚えておきましょう。
例えば倍するときは次のようになります。
4. 配列を用いた実装
乗算は、工夫をすることで早く実行できます。
まずは乗算がどこで使われるか見ていきましょう。
AES-GCMでは、GHASHを算出するときに使用されます。
PDFのGHASHの算出式を見てもらえばわかるのですが、
乗算はすべて次のような形になっています。
カッコの中はいろいろだったので省略しました。
ここでのポイントは、必ず右が「」になっていることです。
乗算の片方はで固定なのです。
はAESの鍵を設定さえすれば求めることができるので、
encrypt/decryptを行う前に
を用いて最適化の準備をすることができます。
入力をとし、固定値
との乗算
を求めることを考えます。
その時に用いる最適化用の配列をとします。
配列にアクセスするための引数を「添字」と呼びます。
例えば、と表したとき、
が添字です。
4.1. 添字8bitの配列
添字8bitの配列とは、つまり要素数が256個の配列のことです。
こちらを用いて最適化することを考えていきましょう。
まずはと乗算したい入力
を1byteごとに分割します。
128bit=16byteなので、16個に分割することができます。
例えば次のような値であったとします。
X = 0xFFEEDDCCBBAA99887766554433221100
これを16個に分けます。
FF EE DD CC BB AA 99 88 77 66 55 44 33 22 11 00
これらは、あらかじめ用意しておいた16個の
配列の要素を参照するのに使います。
と
の乗算の結果を、次のように表します。
いま、の各要素を
だの
だの定数を直打ちしていますが、
そうではなく変数
を1byteずつ分割した内容を
とします。
このとき乗算は次のように表せます。
配列さえあれば、
乗算が求まるということです。
こんなことをして何がうれしいのかというと、
乗算をおよそ16回のXORで求めることができるので低コストなのです。
代償もあります。
データの容量、そして初期値の計算です。
いまは一つの配列の要素数は256個であり、
その中に128bitのデータが格納され、
その配列が16個あるという状況です。
事前に256 [個] × 16 [byte] × 16 [個] = 65536 [byte]の容量が必要になります。
さらにが決まった後で、
16個の配列を最初に計算しなければなりません。
そのコストは、256 [個] × 16 [個] = 4096 [個]分です。
4.2. 添字4bitの配列
4bitの配列を作ることを考えます。
8bitに比べると次の特徴があります。
- 配列のサイズが小さい(ひとつあたり256個ではなく16個)
- 初期値の設定が早い
- 乗算の算出速度が遅い
いいところも悪いところあります。
まずはを4bitごとに分割します。
128bitなので、32個に分割することができます。
例えば次のように分割したとします。
F F E E ... 1 1 0 0
32個は多いので省略しました。
を4bitずつ分割した内容を
とします。
また、配列をとします。
このとき乗算は次のように表せます。
8bitのときは15回のXORで計算できましたが、
4bitのときは31回になっており、
およそ2倍のコストとなっています。
しかしその分スペースは小さくなります。
配列の要素数は16個であり、
その中に128bitのデータが格納され、
その配列が32個あります。
32 [個] × 16 [byte] × 16 [個] = 8192 [byte]の容量が必要になります。
さらにが決まった後で、
16個の配列を事前に計算しなければなりません。
そのコストは、32 [個] × 16 [個] = 512 [個]分です。
4.3. 添字1bitの配列
こちらはPDFにはないものですが、
とても簡単に実装できますし、
配列を用いない場合よりも効率が良くなります。
スペースは2048 [byte]必要になります。
初期値の計算は128個分。
乗算の演算はおよそ128回です。
乗算を求めるコードは配列を用いないときと似ていますが、
さらに単純になっています。
Z ← 0 for i = 0 to 127 do if Xi = 1 then Z ← Z ⊕ M[i] end if end for return Z
個人的には手軽でいいのではないかと思います。
合わせて見ていきます。
5. 配列の作り方
配列とそれに続く
なのですが、
作成方法があんまり詳しく乗ってないので苦労しました。
今回の投稿の主な目的は、この配列を作成する方法を示すことです。
5.1. 添字8bit配列の作り方
添字8bitの配列を作成しましょう。
値をもとに、
を作成します。
各配列の要素数は、添字8bitということなので256個です。
まずは添字のbitがたった1つの場合の値を算出します。
値は128bitなので128通りありますが、
最初の配列分の8個を見ていきましょう。
具体的に書くと次の8通り。
10000000 添字128のとき 01000000 添字64のとき 00100000 添字32のとき 00010000 添字16のとき 00001000 添字8のとき 00000100 添字4のとき 00000010 添字2のとき 00000001 添字1のとき
これらの配列の値は、
の値をシフトしていくだけです。
- 添字
10000000
は、 - 添字
01000000
は、 - 添字
00100000
は、 - 添字
00010000
は、 ...
- 添字
00000001
は、
なので、
直前に算出した値を使うことができます。
では、次にbitがたくさんある場合を考えます。
例として24
を考えましょう。
24
の2進数表記は次のようになります。
00011000 24
つまりは、8
と16
の加算です。
00010000 16のとき 00001000 8のとき ---------------- 00011000 24
値の求め方は簡単であり、8と16のそれぞれの配列の値を足すだけです。
つまり、
右辺の2つの値はすでに算出していますので、
配列に格納されています。
すでに算出した値を用いて、
必要な値を全部求めることができます。
では、他の配列も合わせて見ていきます。
128bitを8bitに分割するので、配列は全部で16個。
配列をとします。
まずは、すべての配列において、bitが1つの場合を先行して求めてしまいます。
の内容は下記の通り。
10000000
は、01000000
は、00100000
は、00010000
は、...
00000001
は、
続いての配列を作成します。
内容はの続きです。
10000000
は、01000000
は、00100000
は、00010000
は、...
00000001
は、
最初にの値を参照している点に注意してください。
実装では直前に算出した値をでシフトして求めてください。
最後はこんな感じ。
10000000
は、01000000
は、00100000
は、00010000
は、...
00000001
は、
これで、bitが1つだけ立っている128個の要素は算出できました。
こちらを算出するコードですが、
PDFにAlgorithm 3として記載があります。
しかしこれがよくわからなかった。
PDFを参考に似たようなコードを作ってみます。
M0[128] = H for i = 1 to 128 - 1 do j ← trunc(i / 8) k ← i % 8 H ← H ⋅ P Mj[1 << (8 - k - 1)] ← H end for
いくつかの命令を勝手に自作してしまいました。
trunc
は、小数点を切り捨てる命令です。
i % 8
は、i
を8
で割ったあまりです。
1 << n
という部分は1
をn
bit分左にシフトするという意味です。
他の要素はbitの組み合わせで全部出します。
まずは最初のを完成させてみましょう。
i ← 2 while i < 256 do for j = 1 to i − 1 do M0[i + j] = M0[i] ⊕ M0[j] end for i ← 2 * i end while
同じように、ほかの配列も作成できます。
しかし上記のコードを配列ごとに分ける必要はないので、
まとめてやってしまいましょう。
次のように書き換えます。
i ← 2 while i < 256 do for j = 1 to i − 1 do for k = 0 to 16 - 1 do Mk[i + j] ← Mk[i] ⊕ Mk[j] end for end for i ← 2 * i end while
以上により、添字0以外はすべて完了です。
最後の値は下記の通り。
00000000
は、
コードは次の通り。
for k = 0 to 16 - 1 do Mk[0] ← 0 end for
完成です!
5.2. 添字4bit配列の作り方
添字4bitの配列を作成しましょう。
128bitを4bitに分割するので、配列は全部で32個。
配列をとします。
まずは、すべての配列において、bitが1つの場合を先行して求めてしまいます。
1000
は、0100
は、0010
は、0001
は、
1000
は、0100
は、0010
は、0001
は、
以降省略
求め方は8bitの時とほぼ同じです。
実装を示します。
M0[8] = H for i = 1 to 128 - 1 do j ← trunc(i / 4) k ← i % 4 H ← H ⋅ P Mj[1 << (4 - k - 1)] ← H end for
他の部分を求めます。
i ← 2 while i < 16 do for j = 1 to i − 1 do for k = 0 to 32 - 1 do Mk[i + j] ← Mk[i] ⊕ Mk[j] end for end for i ← 2 * i end while
最後は0です。
for k = 0 to 32 - 1 do Mk[0] ← 0 end for
5.3. 添字1bit配列の作り方
こちらは8bit, 4bitと同じ内容ではあるものの、
素直に1bitの配列を作るわけではありません。
そんなことしても、どう考えても扱いづらいですから。
代わりに128bit分の、128個の配列を作ります。
各要素には、をシフトした値を入れます。
つまりは次のようになります。
0
は、1
は、2
は、3
は、...
127
は、
いくつか注意点があります。
まず、他とは違い、配列はひとつだけです。
添字0の値は、0ではなくです。
コードは簡単です。
for i = 0 to 128 - 1 do M[i] ← H H ← H ⋅ P end for
6. 乗算の算出
では実際に算出していきましょう。
6.1. 添字8bit配列の乗算の算出
算出していきたいわけですが、
まず入力を8bitに分割する必要があります。
これはプログラミング言語によって
実装方法が異なるのではないでしょうか。
疑似コードで無理やり作ってみます。
for i = 0 to 16 - 1 do r[i] ← (X >> (i * 8)) % 0x0100 end for
X >> n
という部分はX
をn
bit分右にシフトするという意味です。
入力の代わりに、求めた配列
r
を使い、乗算を計算します。
Z ← 0 for i = 0 to 16 - 1 do k ← r[16 - i - 1] Z ← Z ⊕ Mi[k] end for return Z
以上で、が求まりました。
6.2. 添字4bit配列の乗算の算出
さっそくコードを示します。
for i = 0 to 32 - 1 do r[i] ← (X >> (i * 4)) % 0x10 end for Z ← 0 for i = 0 to 32 - 1 do k ← r[32 - i - 1] Z ← Z ⊕ Mi[k] end for return Z
6.3. 添字1bit配列の乗算の算出
こちらはすでに作成済みです。
同じものを下記に示します。
Z ← 0 for i = 0 to 127 do if Xi = 1 then Z ← Z ⊕ M[i] end if end for return Z
7. 乗算の速度
次の表は、AES-GCMのencrypt/decryptの実行結果です。
Common Lispでテストを行いました。
GHASHだけの計測ではないので注意してください。
Type | Size [byte] | Time [sec] | process [cycle] | cons [byte] |
---|---|---|---|---|
table0 | 0 | 33.7 | 111 G | 14.7 M |
table1 | 2048 | 27.2 | 89.7 G | 6.68 M |
table4 | 8192 | 25.0 | 82.6 G | 5.38 M |
table8 | 65536 | 24.3 | 80.5 G | 4.67 M |
Typeに対して、下記のコストを出しました。
- Sizeは配列のサイズをbyteで表したものです。
- Timeは、あるテストプログラムの実行時間(秒)です。
- processはCPUの命令回数です。
- consはLisp特有の値であり、実行時に生成されたconsの総数です。
上記の表でわかることは、配列を使ったコードは
ちゃんと速度において改善されているということです。
これはAES-GCMのencrypt/decryptすべての実行結果ですが、
GHASHだけのものがgcm-spec.pdfにありますので見てみましょう。
- The Galois/Counter Mode of Operation (GCM)
https://csrc.nist.rip/groups/ST/toolkit/BCM/documents/proposedmodes/gcm/gcm-spec.pdf
Table 1
Method | Storage requirement | Throughput (cycles per byte) |
---|---|---|
No tables | 16 bytes/key | 119 |
Simple, 4-bit tables | 8,192 bytes/key | 17.3 |
Simple, 8-bit tables | 65,535 bytes/key | 13.1 |
この表を見ますと、いわゆるtable0とtable4のコストが119と17.3になっており、
差がとても大きいことがわかります。
配列を使った方が大幅に早いということになります。
この手の最適化はメモリと速度のトレードオフになると思いますが、
それにしても何らかの表を使った方がいいみたいです。
テストに使ったコードは下記の通り。
(defpackage work (:use common-lisp aes)) (in-package work) (defconstant +size+ (* 10 1024 1024)) (defun make-vector8 (size) (make-array size :element-type '(unsigned-byte 8))) (defun integer-big-vector (v size) (let ((a (make-array size :element-type '(unsigned-byte 8)))) (dotimes (i size) (let ((k (- size i 1))) (setf (aref a i) (ldb (byte 8 (* k 8)) v)))) a)) (defun main () (let* ((x (make-vector8 +size+)) (g (make-aes-gcm-128)) (key (aes-gcm-key g)) (nonce (aes-gcm-nonce g)) a b) (dotimes (i 32) (setf (aref key i) (random #x0100))) (dotimes (i 12) (setf (aref nonce i) (random #x0100))) (dotimes (i +size+) (setf (aref x i) (random #x0100))) (multiple-value-bind (y a) (aes-gcm-encrypt g x) (multiple-value-bind (z b) (aes-gcm-decrypt g y) (unless (equalp a b) (format t "tab error, ~S /= ~S.~%" a b)) (unless (equalp x z) (format t "decode error.~%")))))) (let ((aes::*aes-gcm-mode* 'aes::table8)) (time (main)))