GCMの認証コードの計算において、ガロア体 $GF(2^{128})$ におけるハッシュ鍵 $L$ とのかけ算が出てきます。
過去記事の補足で、一般的なかけ算のアルゴリズムを書きましたが、固定値と任意の値とのかけ算と考えて高速化することができます。ただし、大きなサイズのテーブルを作成するため、メモリ使用量とのトレードオフになります。
参考文書
[1] The Galois/Counter Mode of Operation (GCM)
https://csrc.nist.rip/groups/ST/toolkit/BCM/documents/proposedmodes/gcm/gcm-spec.pdf
4 Implementation
4.1 Software
[2]【過去記事】認証暗号化モードGCMの理論的なところの解説
https://qiita.com/shirokumaneko/items/5185373a9f0aebb16251
補足
ガロア体について
一番速い方法 (Simple table)
その代わり、メモリ使用量も最大です。
\begin{align}
a &= \sum_{i=0}^{127} a_i x^i \\
&= \sum_{i=0}^{15} \left(\sum_{j=0}^7 a_{ij}x^j \right) x^{8i} \\
&= \sum_{i=0}^{15} a^{(i)}x^{8i}
\end{align}
のようにおくと、
\begin{align}
L \cdot a = \sum_{i=0}^{15} (Lx^{8i})a^{(i)}
\end{align}
$a^{(i)} \in GF(2^8)$ であり、ビット列で考えると8ビット、0～255の値を取ります。
各 $i$ について、$a^{(i)} = 00000000 \cdots 11111111$ のすべての場合の $(Lx^{8i})a^{(i)}$ の値をあらかじめ計算しておきます。
M_i[n_{a^{(i)}}] = (Lx^{8i})a^{(i)}
ここで、$n_{a^{(i)}}$ は $a^{(i)}$ のビット列を8ビットの値とみなしたものです。
つまり、
\begin{align}
M_0[0] &= (Lx^0) \cdot 0 = 0 \\
M_0[1] &= (Lx^0) \cdot x^7 \\
M_0[2] &= (Lx^0) \cdot x^6 \\
&\ \ \ \ \ \vdots \\
M_{15}[255] &= (Lx^{120})(x^7 + \cdots + x + 1)
\end{align}
というような感じです。
こうすると、
L \cdot a = \sum_{i=0}^{15} M_i[n_{a^{(i)}}]
となります。
なお、GCMではビット順をリトルエンディアンとするため、1 = 0x01 = $x^7$, 128 = 0x80 = $x^0$ になります。
class GF2_128
{
public:
GF2_128(void);
GF2_128 multiply_L(void);
unsigned char coef[16];
};
GF2_128 M[16][256];
GF2_128 GF2_128::multiply_L(void)
{
GF2_128 a;
for (int i = 0; i < 16; i++)
{
a += M[i][this->coef[i]];
}
return a;
}
かけ算がないので、一見して速そうなのがわかると思います。
$i = 0,\cdots,15$ のそれぞれに256個の $GF(2^{128})$ なので、16×256×16 = 65536 = 64KBのテーブルになります。
なお、
\begin{align}
L \cdot a = \sum_{i=0}^{31} (Lx^{4i})a^{(i)}\ (a^{(i)} = \sum_{i=0}^3 a_{ij}x^j)
\end{align}
のように分割すると、$a^{(i)}$ は4ビット、0～15の値を取るので、32×16×16 = 8192 = 8KBになります。
そこそこ速い方法 (Shoup's table)
その分、メモリ使用量は小さいです。具体的には $M_0$ だけを使うので4KBです。
\begin{align}
L \cdot a &= L \cdot \sum_{i=0}^{15} a^{(i)} x^{8i} \\
&= \sum_{i=0}^{15} (La^{(i)}) \cdot x^{8i} \\
&= (((La^{(15)} \cdot x^8 + La^{(14)}) \cdot x^8 + La^{(13)}) \cdot x^8 + \cdots\ ) \cdot x^8 + La^{(0)} \\
\end{align}
$La^{(i)}$ はテーブル $M_0$ の値なので、
L \cdot a = (((M_0[n_{a^{(15)}}] \cdot x^8 + M_0[n_{a^{(14)}}]) \cdot x^8 + M_0[n_{a^{(13)}}]) \cdot x^8 + \cdots\ ) \cdot x^8 + M_0[n_{a^{(0)}}]
GF2_128 GF2_128::multiply_L(void)
{
GF2_128 a = GF2_128(M[0][this->coef[15]]);
for (int i = 15; i >= 1; i--)
{
a = a.multiply_x8();
a += M[0][this->coef[i-1]];
}
return a;
}
この方法は、メモリ使用量が少ない代わりに $x^8$ とのかけ算が必要になります。
テスト
過去記事で使用したハッシュ鍵を使い、GHASHの計算結果を確認します。
unsigned char L[16] =
{
0xB8, 0x3B, 0x53, 0x37, 0x08, 0xBF, 0x53, 0x5D, 0x0A, 0xA6, 0xE5, 0x29, 0x80, 0xD5, 0x3B, 0x78,
};
void GCM::GHASH(unsigned char *C, GF2_128& S, int blockNum)
{
S = GF2_128(); // S[0] = 0^{128}
for (int i = 0; i < blockNum; i++)
{
S += GF2_128(&C[16*i]); // S[i-1] + C[i]
S = S.multiply_L_simple(); // (S[i-1] + C[i])・L
// S = S.multiply_L_shoup();
}
}
TEST(GCM_AES128, Example2)
{
GCM gcm(K, IV);
memcpy(C, M, sizeof(M));
gcm.authenticated_encrypt(M, C, T, sizeof(M));
EXPECT_EQ(memcmp(S.coef, S_exp, 16), 0);
}
実行結果
simple,shoupとも
[==========] Running 1 test from 1 test case.
[----------] Global test environment set-up.
[----------] 1 test from GCM_AES128
[ RUN ] GCM_AES128.Example2
[ OK ] GCM_AES128.Example2 (0 ms)
[----------] 1 test from GCM_AES128 (1 ms total)[----------] Global test environment tear-down
[==========] 1 test from 1 test case ran. (4 ms total)
[ PASSED ] 1 test.
実行時間
Raspberry Pi 4で
g++ -O2
| テーブル | authenticated_encrypt | create |
|---|---|---|
| Simple (64KB) | 37.8 usec | 282.0 usec |
| Shoup (4KB) | 41.8 usec | 35.5 usec |
| なし | 114.0 usec |
int main(void)
{
GCM gcm(K, IV);
memcpy(C, M, sizeof(M));
struct timespec ts_start, ts_end;
clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &ts_start);
gcm.authenticated_encrypt(M, C, T, sizeof(M));
clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &ts_end);
printf("%d usec\n", (ts_end.tv_nsec - ts_start.tv_nsec) / 1000);
}
補足
テーブルの作成方法
$M_i$ の定義は
M_i[n_{a^{(i)}}] = (Lx^{8i})a^{(i)}
ですが、
\begin{align}
M_0[128] = L &\cdot x^{0} = L \\
M_0[64] = L &\cdot x\ \ = M_0[128] \cdot x \\
&\vdots \\
M_0[1] = L &\cdot x^7 = M_0[2] \cdot x \\
\end{align}
として $2^n$ 系列を先に求めてから
\begin{align}
&M_0[3] = L \cdot (x^{127} + x^{126}) = M_0[1] + M_0[2]
\end{align}
のようにして、すべての値を計算することができます。
M[0][128] = L;
for (int j = 64; j > 0; j /= 2)
{
M[0][j] = M[0][2*j].multiply_x(); // M_0[64], ..., M_0[1] = L・x^7
}
for (int j = 2; j <= 128; j *= 2)
{
for (int k = 1; k < j; k++)
{
M[0][j+k] = M[0][j] + M[0][k];
}
}
$x$ とのかけ算multiply_xは、過去記事で上げたGF2_128_multiply_xと同じです。
GF2_128 GF2_128::multiply_x(void)
{
GF2_128 a;
int i;
unsigned char a_127 = (this->coef[15] & 0x01);
// a >> 1
for (i = 15; i > 0; i--)
{
a.coef[i] = (this->coef[i] >> 1) | (this->coef[i - 1] << 7);
}
this->coef[0] = this->coef[0] >> 1;
if (a_127 == 1)
{
a.coef[0] ^= 0xe1; // 1 + x + x^2 + x^7
}
return a;
}
$M_1, \cdots, M_{15}$ は、出発点が $M_1[128] = L \cdot x^8, \cdots, M_{15}[128] = L \cdot x^{120}$ となる以外は、同じ手順で計算できます。
for (int i = 0; i < 16; i++)
{
M[i][128] = L;
for (int j = 0; j < i; j++)
{
M[i][128] = M[i][128].multiply_x8(); // M_i[128] = L・x^{8i}
}
}
$x^8$ とのかけ算は、$x$ とのかけ算を8回繰り返してもいいですが、これも高速化できます。
\begin{align}
a \cdot x^8 &= \sum_{i=0}^{15} a^{(i)} x^{8(i+1)} \\
&= \sum_{i=1}^{15} a^{(i-1)} x^{8i} + a^{(15)} x^{128} \\
&= \sum_{i=1}^{15} a^{(i-1)} x^{8i} + a^{(15)}(x^7 + x^2 + x + 1)
\end{align}
$x^7 + x^2 + x + 1$ とのかけ算をあらかじめ計算しておき、
R[n_{a^{(15)}}] = a^{(15)}(x^7 + x^2 + x + 1)
とすれば、
GF2_128 GF2_128::multiply_x8(void)
{
GF2_128 a;
for (int i = 15; i >= 1; i--)
{
a.coef[i] = this->coef[i-1]; // a^{(i-1)} x^{8i}
}
a += R[this->coef[15]]; // a^{(15)}(x^7 + x^2 + x + 1)
return a;
}
ここで、$a^{(15)} = \sum_{j=0}^7 a_j^{(15)} x^j$ なので、$a^{(15)}(x^7 + x^2 + x + 1)$ は128次以上の項を生じません。
つまり、単なるビットシフトになります。
R[n_{a^{(15)}}] = (a^{(15)} >> 7) \oplus (a^{(15)} >> 2) \oplus (a^{(15)} >> 1) \oplus a^{(15)}
最終的には、以下のようになります。
GF2_128 M[16][256];
GF2_128 R[256];
void table_create(GF2_128& L)
{
table_createR();
table_createM(L);
}
void table_createR(void)
{
for (int n = 0; n < 256; n++)
{
R[n].coef[0] = (n >> 7) ^ (n >> 2) ^ (n >> 1) ^ n;
R[n].coef[1] = ((n & 0x7f) << 1) ^ ((n & 0x03) << 6) ^ ((n & 0x01) << 7);
}
}
void table_createM(GF2_128& L)
{
for (int i = 0; i < 16; i++)
{
M[i][128] = L;
for (int j = 0; j < i; j++)
{
M[i][128] = M[i][128].multiply_x8(); // M_i[128] = L・x^{8i}
}
}
for (int i = 0; i < 16; i++)
{
for (int j = 64; j > 0; j /= 2)
{
M[i][j] = M[i][2*j].multiply_x();
}
for (int j = 2; j <= 128; j *= 2)
{
for (int k = 1; k < j; k++)
{
M[i][j+k] = M[i][j] + M[i][k];
}
}
}
}
$x^8$ の計算に必要なので、$R$ は $M_i$ よりも先に計算する必要があります。
なお、AESの秘密鍵 $K$ を交換すると $L = E_K(0)$ も変わるので、テーブルをつくり直す必要があります。