内容来源论文The Galois/Counter Mode of Operation(GCM),本文主要根据第4.1章软件实现进行原理推导。
问题:已知 f = 1 + α + α2 + α7 + α128 求 H · X,其中X、H都是128位的比特串
一、查表1
The operation H ·X is linear in the bits of X, over the field GF(2). This property can be exploited tomakeefficient table-driven implementations,in which tables computedforaparticular valueof H can be used to multiply H byan arbitrary elementX. The simplest method computes Z = X·H as
Z = M0[byte(X, 0)] ⊕ M1[byte(X, 1)] ⊕ ... ⊕ M15[byte(X, 15)]
解释:实际上就是将 X 拆分成16个独立的操作进行查表。
X · H = (x0 + x1α + x2α2 + x3α3 + ···· + x126α126 + x127α127) · H
= (x0 + x1α + x2α2 + x3α3 + ···· + x7α7 + 0α8 + ··· + 0α127) · H +
(0 + 0α + ···· + 0α7 + x8α8 + x9α9 + ··· + x15α15 + 0α16 + ··· + 0α127) · H +
··· +
(0 + 0α + ···· + 0α119 + x120α120 + x121α121 + ··· + x127α127) · H -- 公式1
这样就可以转化为16次乘法 + 16次加法操作,对于每个乘法操作,由于只有1个字节不为0,所以我们可以预先遍历256种取值,对于每一个取值 x,计算 x · H。当后续需要时直接查表即可,因此可以转化为16次查表 + 16次加法操作。具体可以再配制密钥完成后,先计算出H,再进行预计算。
所需要的空间:16(表的数量)· 256(每张表中元素的个数)· 16(每个元素的字节数,为128比特) = 24·28·24 = 64KBytes。
另外一种方法可以按照 4比特 拆分,因此一共需要32次查表 + 32次加法。
所需要的空间:32(表的数量)· 16(每张表中元素的个数)· 16(每个元素的字节数,为128比特) = 25·24·24 = 8KBytes。
二、查表2
1、With a small increase in the amount of computation, we can reduce the storage requirements considerably, as describedby Shoup[9].We can use only the table M0 defined above to multiply an arbitrary element X ∈ GF(2128) by H as follows.Wefirstexpresstheproductas
X · H = (x0 + x1α + x2α2 + x3α3 + ···· + x126α126 + x127α127) · H
= (x0 + x1α + x2α2 + x3α3 + ···· + x7α7 + 0α8 + ··· + 0α127) · H +
(0 + 0α + ···· + 0α7 + x8α8 + x9α9 + ··· + x15α15 + 0α16 + ··· + 0α127) · H +
··· +
(0 + 0α + ···· + 0α119 + x120α120 + x121α121 + ··· + x127α127) · H
= (x0 + x1α + x2α2 + x3α3 + ···· + x7α7 + 0α8 + ··· + 0α127) · H +
(0 + 0α + ···· + 0α7 + x8α0 + x9α1 + ··· + x15α7 + 0α16 + ··· + 0α127) · α8 · H +
··· +
(0 + 0α + ···· + 0α119 + x120α0 + x121α1 + ··· + x127α7) · α120 · H -- 公式2
论文中转换后的算法如下
算法1
Z = 0
for i = 15 to 1 do
Z = Z ⊕ (Xi · H)
Z = Z · α8
end for
Z = Z ⊕ (X0 · H)
return Z
2、解释:这里算法中的Xi分别对应16个字节(等价于xi*8+0xi*8+1xi*8+2xi*8+3xi*8+4xi*8+5xi*8+6xi*8+7)。
论文中对算法1进行了解释,但期初看起来可能比较费解。这里我们详细计算验证算法的等价性。
i = 15结束后:Z = X15 · H · α8
i = 14结束后:Z = (X15 · H · α8 ⊕ X14 · H) · α8
= X15 · H · α16 ⊕ X14 · H · α8
i = 13结束后:Z = (X15 · H · α16 ⊕ X14 · H · α8 ⊕ X13 · H) · α8
= X15 · H · α24 ⊕ X14 · H · α16 ⊕ X13 · H · α8
···
i = 1结束后:Z = X15 · H · α120 ⊕ X14 · H · α112 ⊕ X13 · H · α104 ⊕ ··· ⊕ X2 · H · α16 ⊕ X1 · H · α8
算法结束后:Z = X15 · H · α120 ⊕ X14 · H · α112 ⊕ X13 · H · α104 ⊕ ··· ⊕ X2 · H · α16 ⊕ X1 · H · α8 ⊕ X0 · H -- 公式3
以比特串的形式表示,我们可以发现公式3和公式2是等价的,因此可以证明算法1是正确的。
3、算法1的求解
1)Xi · H 可以通过查表得到,其中 Xi 只有第1个字节不为0,其余120比特全为0,因此我们只需要遍历256种情况即可。16次查表操作均可以只使用1个表格,再通过移位实现。
2)Z ⊕ (Xi · H)对应的二进制比特串将不再是只有第1个字节不为0,重点求解 Z = Z · α8
Z = Z · α8
= Z · α · α7
= ((Z >> 1) ⊕ x127R) · α7 (其中,R = 0xe1000···0,高 8 比特为 e1,后 120 比特为全 0;x127R 表示若 Z 的第 127 比特为 0,则 x127R 为 0,否则为 R )
= (Z' ⊕ x127R) · α7 (记 Z' 表示 Z 右移 1 位)
= (Z' ⊕ x127R) · α · α6
= ((Z' ⊕ x127R)' ⊕ x127R) · α6
= ((Z'' ⊕ x127R' ⊕ x126R) · α6
= ((Z''' ⊕ x127R'' ⊕ x126R' ⊕ x125R) · α5
···
= Z'''''''' ⊕ x127R''''''' ⊕ x126R'''''' ⊕ x125R'''''⊕ ···⊕ x120R -- 公式4
其中 Z'''''''' 可以直接通过循环右移 8 比特得到;对于x127R''''''' ⊕ x126R'''''' ⊕ x125R'''''⊕ ···⊕ x120R,由于 R 本身是常量,因此我们可以遍历 x127、x126、 x125 、···、 x120 共256种取值进行预计算,最终通过查表得到实际结果。
所需要的空间:1(Xi · H 表的数量,只对第1个字节预计算)· 256(每张表中 Xi 取值的情况)· 16(每个结果的字节数,为128比特)+ 1(R表的数量)· 256 (x127、x126、 x125 、···、 x120 256种取值)+ 2(由于R只有最高8比特非0,最多右移8次,因此只需要16比特即可表示) = 4KBytes + 512 Bytes。
同理,若按照 4比特 拆分,所需要的空间:1(Xi · H 表的数量,只对 x0x1x2x3 预计算)· 16(每张表中 x0x1x2x3 取值的情况)· 16(每个结果的字节数,为128比特)+ 1(R表的数量)· 16 (x127、x126、x125、x124 共16种取值)+ 2(由于R只有最高8比特非0,最多右移8次,因此只需要16比特即可表示) = 256Bytes + 32 Bytes。
4)这里给出按照 4比特 拆分时,R表的构造方法。8 比特拆分的计算方法同理
根据公式4,可以容易的推导出
Z = Z · α4
= Z'''' ⊕ x127R''' ⊕ x126R'' ⊕ x125R'⊕ ···⊕ x124R -- 公式5
x124 x125 x126 x127 结果
0 0 0 0 0
0 0 0 1 R''' = 0xe1 >> 3 = 0x1c20
0 0 1 0 R'' = 0xe1 >> 2 = 0x3840
0 0 1 1 R''' ⊕ R'' = 0x1c20 ⊕ 0x3840 = 0x2460
0 1 0 0 R' = 0xe1 >> 1 = 0x7080
0 1 0 1 R''' ⊕ R' = 0x1c20 ⊕ 0x7080 = 0x6ca0
0 1 1 0 R'' ⊕ R' = 0x3840 ⊕ 0x7080 = 0x48c0
0 1 1 1 R''' ⊕ R'' ⊕ R' = 0x2460 ⊕ 0x7080= 0x54e0
1 0 0 0 R = 0xe100
1 0 0 1 R''' ⊕ R = 0x1c20 ⊕ 0xe100 = 0xfd20
1 0 1 0 R'' ⊕ R = 0x3840 ⊕ 0xe100 = 0xd940
1 0 1 1 R''' ⊕ R'' ⊕ R= 0x2460 ⊕ 0xe100 = 0xc560
1 1 0 0 R' ⊕ R = 0x7080 ⊕ 0xe100 = 0x9180
1 1 0 1 R''' ⊕ R' ⊕ R = 0x6ca0 ⊕ 0xe100 = 0x8da0
1 1 1 0 R''⊕ R' ⊕ R = 0x48c0 ⊕ 0xe100 = 0xa9c0
1 1 1 1 R''' ⊕ R'' ⊕ R' ⊕ R = 0x54e0 ⊕ 0xe100 = 0xb5e0