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では $2^{128}$ の有限体を扱うようで、 $GF(2^{128})$ と書くそうです。
GCMではない、素のAESでは $GF(2^{8})$ が使われていたのを覚えています。
楕円曲線ではさんざん素数 $p$ の有限体をやってきました。
しかし今回は $2^{128}$ であり、素数ではないので楕円曲線の時とはだいぶ事情が違います。
単に $2^{128}$ でひたすら割ってやるだけではダメみたいです。
これに気が付くのに時間がかかってしまった。

まず普通の値と、ガロア体の値の対応を考えます。
どちらも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
                    ↑　普通の値の最下位ビット

変数 $Y$ に値が整数が入っているとして、ガロア体での $i$ 番目のビットを $Y_{i}$ と記載します。
このとき、 $Y_{0}$ は整数の最上位ビットであることに注意してください。
つまり、値が9の場合は $Y_{0}=0$ です。
これも気が付くまで全然意味が分からなかった。
整数は128bitなので、 $Y_{127}$ が最下位ビットになります。
つまり、値が9の場合は $Y_{127}=1$ です。

ではガロア体に話を進めます。
ガロア体で使う演算は二種類。
加算と乗算です。

加算は単純なXORです。
普通の加算と違い、繰上りを考慮する必要がありません。
これは通常の加算よりだいぶ楽ですね。
XORは⊕と表します。
つまり、 $X$ と $Y$ の加算は、 $X \oplus Y$ です。

乗算はかなり面倒です。
乗算は $X \cdot Y$ と表すことにします。
乗算の実装は、2進数のひっ算で計算すると思ってください。
ひっ算に必要な処理は、加算とシフトです。
シフトとはひっ算を進めていくうえで、足す数の位を上げていく処理です。
このシフトを行った際に128bitを超えた場合は、ガロア体特有の方法で値を修正する必要があります。
普通に考えれば128bitと128bitの乗算結果は256bit以下ですが、今はガロア体ですので何とかして128bitに納めなければならないわけです。
素数のガロア体だったら乗算を求めた後に余りを求めればいいだけですが、今回は素数ではないので簡単にはいきません。
単純に128bit切り捨てではだめです。
これが面倒、というか難しいわけです。

ここまでわかれば乗算のコードを理解できると思います。

3. 乗算コードの説明

乗算 $Z = X \cdot Y$ の実装を示します。

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進数のひっ算です。
$Y$ のビットを一つずつ見ていき、ビットが立っていたら結果に $X$ をシフトした値を加算します。

順番に見ていきます。
forの中の加算の部分を取り上げます。

if Yのi番目のビット = 1 then
  Z ← ZとVの加算
end if

先に $Y$ の $i$ 番目のビットを $Y_{i}$ と表すと書きました。
ということで、次のように書き直します。

if Yi = 1 then
  Z ← ZとVの加算
end if

for文の最初はi=0ですが、 $Y_{0}$ は $Y$ に格納されている整数の最上位ビットであることに注意してください。
何度も書いていますが、ガロア体の演算ではビットの順番が逆転します。
Y0は、実際の値Yの最上位ビットです。
Y127は、実際の値Yの最下位ビットです。

コードの内容は、ビットが立っていたら $Z$ に $V$ を加算するという内容です。
$V$ はビットの位置に応じて、 $X$ をシフトした内容です。
$Z$ と $V$ の加算は、単純な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というのは、 $V_{127}$ のことで、ガロア体の演算における $V$ の最上位ビットを表します。
つまり、格納されている整数の最下位ビットです。
最上位だの最下位だの、紛らわしいです。
そもそも何をしようとしているのかを説明します。

ここでは、 $V$ を2倍するためにシフトしています。
普通のプログラミングであれば左に1つシフトすることで2倍にすることができますが、今はガロア体での演算のために右にシフトしています。
自分はこれに気が付くのに時間がかかってしまいました。
なんで右にシフトしてるの？ってずっと思ってた。

もしシフトして128bitを超えるような場合には、ガロア体では単純に切り捨てることができないんです。
そこで、シフトで切り捨てられるビットをあらかじめ判定しておいて、もしそれが1であったときは、いきなり出てきた $R$ という定数のXORを取ります。
$R$ が何者かというと次の通り。

$\displaystyle R = 11100001 \| 0^{120}$

0xE1を120bit分だけ左にシフトしてください。
これはガロア体での話ではなく、 0xE1に対して普通に $2^{120}$ を乗算してくださいという意味です。
そういう定数のXORを取ることで、はみ出した $V_{128}=1$ のビットを何とかしてくれるんだそうです。
どうしてそうなるかは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

これが完成形です。
上記のコードをそのまま実装すれば正しく動きます。

$V$ を2倍することろに関してはもう少し説明が必要です。
2倍するという演算を、次のように表すことができるとのこと。

$\displaystyle V \leftarrow V \cdot P$

$P$ との乗算の内容は、先ほど提示したコードにある通り、右にシフトしてあふれた場合は $R$ でXORを取るというものです。
この $P$ は、あとでいっぱい使うので覚えておいてください。

コードも次のように書き直せます。

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

乗算を計算するコードに $P$ の乗算が現れて混乱しますが、別に再起呼び出しをするのではなく、 $P$ が単純に2倍を表すと考えていいと思います。

$P$ は複数回乗算できることを覚えておきましょう。
例えば $2^{8}$ 倍するときは次のようになります。

$\displaystyle V \leftarrow V \cdot P^{8}$

4. 配列を用いた実装

乗算は、工夫をすることで早く実行できます。
まずは乗算がどこで使われるか見ていきましょう。
AES-GCMでは、GHASHを算出するときに使用されます。
PDFのGHASHの算出式を見てもらえばわかるのですが、乗算はすべて次のような形になっています。

$\displaystyle X_{i} = (...) \cdot H$

カッコの中はいろいろだったので省略しました。
ここでのポイントは、必ず右が「 $\cdot H$ 」になっていることです。
乗算の片方は $H$ で固定なのです。
$H$ はAESの鍵を設定さえすれば求めることができるので、 encrypt/decryptを行う前に $H$ を用いて最適化の準備をすることができます。

入力を $X$ とし、固定値 $H$ との乗算 $X \cdot H$ を求めることを考えます。
その時に用いる最適化用の配列を $M$ とします。
配列にアクセスするための引数を「添字」と呼びます。
例えば、 $M \lbrack 123 \rbrack$ と表したとき、 $123$ が添字です。

4.1. 添字8bitの配列

添字8bitの配列とは、つまり要素数が256個の配列のことです。
こちらを用いて最適化することを考えていきましょう。

まずは $H$ と乗算したい入力 $X$ を1byteごとに分割します。
128bit=16byteなので、16個に分割することができます。
例えば次のような値であったとします。

X = 0xFFEEDDCCBBAA99887766554433221100

これを16個に分けます。

FF EE DD CC BB AA 99 88 77 66 55 44 33 22 11 00

これらは、あらかじめ用意しておいた16個の配列 $M_{0}, ..., M_{15}$ の要素を参照するのに使います。
$X$ と $H$ の乗算の結果を、次のように表します。

$\displaystyle X \cdot H = M_{0} \lbrack FF \rbrack \oplus M_{1} \lbrack EE \rbrack \oplus ... \oplus M_{15} \lbrack 00 \rbrack$

いま、 $X$ の各要素を $FF$ だの $EE$ だの定数を直打ちしていますが、そうではなく変数 $X$ を1byteずつ分割した内容を $x_{0} \ x_{1} \ ... \ x_{15}$ とします。
このとき乗算は次のように表せます。

$\displaystyle X \cdot H = \bigoplus_{i=0}^{15} M_{i} \lbrack x_{i} \rbrack$

配列 $M_{0}, ..., M_{15}$ さえあれば、乗算が求まるということです。
こんなことをして何がうれしいのかというと、乗算をおよそ16回のXORで求めることができるので低コストなのです。

代償もあります。
データの容量、そして初期値の計算です。いまは一つの配列 $M_{0}$ の要素数は256個であり、その中に128bitのデータが格納され、その配列が16個あるという状況です。
事前に256 [個] × 16 [byte] × 16 [個] = 65536 [byte]の容量が必要になります。
さらに $H$ が決まった後で、 16個の配列を最初に計算しなければなりません。
そのコストは、256 [個] × 16 [個] = 4096 [個]分です。

4.2. 添字4bitの配列

4bitの配列を作ることを考えます。
8bitに比べると次の特徴があります。

配列のサイズが小さい（ひとつあたり256個ではなく16個）
初期値の設定が早い
乗算の算出速度が遅い

いいところも悪いところあります。

まずは $X$ を4bitごとに分割します。
128bitなので、32個に分割することができます。
例えば次のように分割したとします。

F F E E ... 1 1 0 0

32個は多いので省略しました。
$X$ を4bitずつ分割した内容を $x_{0} \ x_{1} \ ... \ x_{31}$ とします。
また、配列を $M_{0}, ..., M_{31}$ とします。
このとき乗算は次のように表せます。

$\displaystyle X \cdot H = \bigoplus_{i=0}^{31} M_{i} \lbrack x_{i} \rbrack$

8bitのときは15回のXORで計算できましたが、 4bitのときは31回になっており、およそ2倍のコストとなっています。
しかしその分スペースは小さくなります。

配列 $M_{0}$ の要素数は16個であり、その中に128bitのデータが格納され、その配列が32個あります。
32 [個] × 16 [byte] × 16 [個] = 8192 [byte]の容量が必要になります。
さらに $H$ が決まった後で、 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. 配列の作り方

配列 $M_{0}$ とそれに続く $M_{n}$ なのですが、作成方法があんまり詳しく乗ってないので苦労しました。
今回の投稿の主な目的は、この配列を作成する方法を示すことです。

5.1. 添字8bit配列の作り方

添字8bitの配列を作成しましょう。
値 $H$ をもとに、 $M_{0}, ..., M_{15}$ を作成します。
各配列の要素数は、添字8bitということなので256個です。

まずは添字のbitがたった1つの場合の値を算出します。
値は128bitなので128通りありますが、最初の配列 $M_{0}$ 分の8個を見ていきましょう。
具体的に書くと次の8通り。

10000000  添字128のとき
01000000  添字64のとき
00100000  添字32のとき
00010000  添字16のとき
00001000  添字8のとき
00000100  添字4のとき
00000010  添字2のとき
00000001  添字1のとき

これらの配列 $M_{0}$ の値は、 $H$ の値をシフトしていくだけです。

添字10000000は、 $H$
添字01000000は、 $H \cdot P$
添字00100000は、 $H \cdot P^{2}$
添字00010000は、 $H \cdot P^{3}$
...
添字00000001は、 $H \cdot P^{7}$

$H \cdot P^{2} = (H \cdot P) \cdot P$ なので、直前に算出した値を使うことができます。

では、次にbitがたくさんある場合を考えます。
例として24を考えましょう。 24の2進数表記は次のようになります。

00011000  24

つまりは、8と16の加算です。

00010000  16のとき
00001000  8のとき
----------------
00011000  24

値の求め方は簡単であり、8と16のそれぞれの配列の値を足すだけです。
つまり、

$\displaystyle H \cdot P^{24} = (H \cdot P^{16}) \oplus (H \cdot P^{8})$

右辺の2つの値はすでに算出していますので、配列に格納されています。
すでに算出した値を用いて、必要な値を全部求めることができます。

では、他の配列も合わせて見ていきます。
128bitを8bitに分割するので、配列は全部で16個。
配列を $M_0, M_1, ..., M_{15}$ とします。
まずは、すべての配列において、bitが1つの場合を先行して求めてしまいます。

$M_{0}$ の内容は下記の通り。

- 10000000は、 $H$
- 01000000は、 $H \cdot P = M_0 \lbrack 128 \rbrack \cdot P$
- 00100000は、 $H \cdot P^{2} = M_0 \lbrack 64 \rbrack \cdot P$
- 00010000は、 $H \cdot P^{3} = M_0 \lbrack 32 \rbrack \cdot P$
- ...
- 00000001は、 $H \cdot P^{7} = M_0 \lbrack 2 \rbrack \cdot P$

続いて $M_{1}$ の配列を作成します。
内容は $M_{0}$ の続きです。

- 10000000は、 $H \cdot P^{8} = M_{0} \lbrack 1 \rbrack \cdot P$
- 01000000は、 $H \cdot P^{9} = M_{1} \lbrack 128 \rbrack \cdot P$
- 00100000は、 $H \cdot P^{10} = M_{1} \lbrack 64 \rbrack \cdot P$
- 00010000は、 $H \cdot P^{11} = M_{1} \lbrack 32 \rbrack \cdot P$
- ...
- 00000001は、 $H \cdot P^{15} = M_{1} \lbrack 2 \rbrack \cdot P$

最初に $M_{0}$ の値を参照している点に注意してください。
実装では直前に算出した値を $P$ でシフトして求めてください。
最後はこんな感じ。

- 10000000は、 $H \cdot P^{120} = M_{14} \lbrack 1 \rbrack \cdot P$
- 01000000は、 $H \cdot P^{121} = M_{15} \lbrack 128 \rbrack \cdot P$
- 00100000は、 $H \cdot P^{122} = M_{15} \lbrack 64 \rbrack \cdot P$
- 00010000は、 $H \cdot P^{123} = M_{15} \lbrack 32 \rbrack \cdot P$
- ...
- 00000001は、 $H \cdot P^{127} = M_{15} \lbrack 2 \rbrack \cdot P$

これで、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をnbit分左にシフトするという意味です。

他の要素はbitの組み合わせで全部出します。
まずは最初の $M_{0}$ を完成させてみましょう。

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は、 $0$

コードは次の通り。

for k = 0 to 16 - 1 do
  Mk[0] ← 0
end for

完成です！

5.2. 添字4bit配列の作り方

添字4bitの配列を作成しましょう。
128bitを4bitに分割するので、配列は全部で32個。
配列を $M_{0}, M_{1}, ..., M_{31}$ とします。
まずは、すべての配列において、bitが1つの場合を先行して求めてしまいます。

$M_{0}$
- 1000は、 $H$
- 0100は、 $H \cdot P = M_0 \lbrack 8 \rbrack \cdot P$
- 0010は、 $H \cdot P^{2} = M_0 \lbrack 4 \rbrack \cdot P$
- 0001は、 $H \cdot P^{3} = M_0 \lbrack 2 \rbrack \cdot P$
$M_{1}$
- 1000は、 $H \cdot P^{4} = M_{0} \lbrack 1 \rbrack \cdot P$
- 0100は、 $H \cdot P^{5} = M_{1} \lbrack 8 \rbrack \cdot P$
- 0010は、 $H \cdot P^{6} = M_{1} \lbrack 4 \rbrack \cdot P$
- 0001は、 $H \cdot P^{7} = M_{1} \lbrack 2 \rbrack \cdot P$
以降省略

求め方は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個の配列を作ります。
各要素には、 $H$ をシフトした値を入れます。
つまりは次のようになります。

- 0は、 $H$
- 1は、 $H \cdot P = M \lbrack 0 \rbrack \cdot P$
- 2は、 $H \cdot P^{2} = M \lbrack 1 \rbrack \cdot P$
- 3は、 $H \cdot P^{3} = M \lbrack 2 \rbrack \cdot P$
- ...
- 127は、 $H \cdot P^{127} = M \lbrack 126 \rbrack \cdot P$

いくつか注意点があります。
まず、他とは違い、配列は $M$ ひとつだけです。
添字0の値は、0ではなく $H$ です。
コードは簡単です。

for i = 0 to 128 - 1 do
  M[i] ← H
  H ← H ⋅ P
end for

6. 乗算の算出

では実際に算出していきましょう。

6.1. 添字8bit配列の乗算の算出

算出していきたいわけですが、まず入力 $X$ を8bitに分割する必要があります。
これはプログラミング言語によって実装方法が異なるのではないでしょうか。
疑似コードで無理やり作ってみます。

for i = 0 to 16 - 1 do
  r[i] ← (X >> (i * 8)) % 0x0100
end for

X >> nという部分はXをnbit分右にシフトするという意味です。
入力 $X$ の代わりに、求めた配列rを使い、乗算を計算します。

Z ← 0
for i = 0 to 16 - 1 do
  k ← r[16 - i - 1]
  Z ← Z ⊕ Mi[k]
end for
return Z

以上で、 $X \cdot H$ が求まりました。

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の総数です。

上記の表でわかることは、配列 $M$ を使ったコードはちゃんと速度において改善されているということです。
これは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)))

nptclのブログ

Common Lisp処理系nptの開発メモです。https://github.com/nptcl/npt

AES-GCMの乗算を実装する