AES-GCM查表原理

内容来源论文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) · α· 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 · α⊕ X14 · H) · α8  

                          = X15 · H · α16 ⊕ X14 · H · α

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 可以通过查表得到,其中 X只有第1个字节不为0,其余120比特全为0,因此我们只需要遍历256种情况即可。16次查表操作均可以只使用1个表格,再通过移位实现。

2)Z ⊕ (Xi · H)对应的二进制比特串将不再是只有第1个字节不为0,重点求解 Z = Z · α8

Z = Z · α8

= Z · α · α7

= ((Z >> 1) ⊕ x127R) ·  α(其中,R = 0xe1000···0,高 8 比特为 e1,后 120 比特为全 0;x127R 表示若 Z 的第 127 比特为 0,则 x127R 为 0,否则为 R )

(Z' ⊕ x127R) ·  α(记 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 表的数量,只对 x0x1x2x预计算)· 16(每张表中  x0x1x2x 取值的情况)· 16(每个结果的字节数,为128比特)+ 1(R表的数量)· 16 (x127、x126、x125x124 共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' = 0x2460x7080= 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

上一篇:剑指offer63:数据流中的中位数


下一篇:bit操作 转