Twofish加密算法详解(下)

    3. The Key Schedual

             在这一部分，我们需要产生40 个与密钥相关的K(i)，和4个与密钥相关
         的，在函数 g中使用到的 S-box，也就是s(i)()。

             在Twofish 算法中，规定密钥的长度 N = 128, N = 192, N = 256三种。
         也就是说密钥的长度可以在128-bit ~ 256-bit之间变化。

             我们记 k = N / 64 (则k = 2, 3, 4)，那么密钥 M也就由 8k个字节组
         成。我们记这 8k个字节为：

             m0, ... ,m(8k-1)

         首先将这 8k 个字节转换成 2k 个 32-bit 的数据：

             M(i) = ∑m(4i+j)2^(8j)，其中j = 0, ... ,3，i = 0, ... ,2k-1

         然后由这 2k 个32-bit 数据构成两个 k维的向量：

             Me = (M0, M2, ... ,M(2k-2))
             Mo = (M1, M3, ... ,M(2k-1))

         下面再利用m(i)产生一个 k维的向量：

             ┌      ┐  ┌ ┐  ┌       ┐
             │s(i,0)│  │ │  │m(8i)  │
             │s(i,1)│= │R│·│m(8i+1)│
             │s(i,2)│  │S│  │ ......│
             │s(i,3)│  │ │  │m(8i+7)│
             └      ┘  └ ┘  └       ┘

         其中RS是定义在GF(2^8)的 4*8阶矩阵。记：

             S(i) = ∑s(i,j)2^(8j)，其中j = 0, ... ,3，i = 0, ... ,k-1

         这样就有产生了一个 k维向量：

             S = (S(k-1), S(k-2), ... ,S0)

         注意，这里 S是由S(i)反序组成的。对于RS矩阵，我们同样需要明确定义有
         限域GF(2^8)。在这里：

             GF(2^8) ≡ GF(2)[x]/w(x)，其中w(x) = x^8 + x^6 + x^3 + x^2 + 1

                  ┌                       ┐
                  │01 A4 55 87 5A 58 DB 9E│
             RS = │A4 56 82 F3 1E C6 68 E5│
                  │02 A1 FC C1 47 AE 3D 19│
                  │A4 55 87 5A 58 DB 9E 03│
                  └                       ┘

         这里定义的Me Mo S构成了 key schedual的基础。

         3.1 Additional Key Lengths

             这里介绍一下密钥长度的问题。密钥长度必须是小于256 bits的，如果
         密钥长度不足上面给丁的 N，那么在密钥后面补零，直到最接近的 N为止。
         例如密钥长度是80-bit，则在m0, ... ,m9后面加上：

             m(i) = 0，i = 10, ... ,15

         这样就构成了一个128-bit的密钥。

         3.2 The Function h

             你一定觉得奇怪，怎么突然有出来个 h函数，上面明明没有遇到啊？！
         呵呵，上面是没有遇到，不过下面就快用到了，而且这个函数很重要。

             Z = h(X, L)

         其中X, Z是32-bit的数据，L = L(L0, ... ,L(k-1))是一个 k维的向量。
         首先我们还是将X, L分成字节：

             l(i,j) = [L(i)/2^(8j)] mod 2^8    i = 0, ... ,k-1
               x(j) = [X/2^(8j)] mod 2^8       j = 0, ... ,3

         我们记：

             y(k,j) = x(j)                     j = 0, ... ,3

         如果：k == 4

             y(3,0) = q1[y(4,0)] xor l(3,0)
             y(3,1) = q0[y(4,1)] xor l(3,1)
             y(3,2) = q0[y(4,2)] xor l(3,2)
             y(3,3) = q1[y(4,3)] xor l(3,3)

         如果：k >= 3

             y(2,0) = q1[y(3,0)] xor l(2,0)
             y(2,1) = q1[y(3,1)] xor l(2,1)
             y(2,2) = q0[y(3,2)] xor l(2,2)
             y(2,3) = q0[y(3,3)] xor l(3,3)

         对于所有情况：

             y0 = q1[q0[q0[y(2,0)] xor l(1,0)] xor l(0,0)]
             y1 = q0[q0[q1[y(2,1)] xor l(1,1)] xor l(0,1)]
             y2 = q1[q1[q0[y(2,2)] xor l(1,2)] xor l(0,2)]
             y3 = q0[q1[q1[y(2,3)] xor l(1,3)] xor l(0,3)]

         也就是说，如果k==4，那么上面 3种情况都要做；如果k==3，那么只做后两
         种情况；如果k==2，则只计算最后这种情况。

             ┌  ┐  ┌   ┐  ┌  ┐
             │z0│  │   │  │y0│
             │z1│= │MDS│·│y1│
             │z2│  │   │  │y2│
             │z3│  │   │  │y3│
             └  ┘  └   ┘  └  ┘

              Z = ∑z(i)2^(8i)，其中i = 0, ... ,3

         最后的矩阵乘法同样遇到 MDS矩阵，GF(2^8)的定义跟前面一样。
         h 函数讲完了，但其中又多出来个q0 q1，它们同样是S-boxes，过一会我们
         再讲如何计算q0 q1，下面开始介绍如何计算S-boxes与K(i)。

         3.3 The Key-dependent S-boxes

             我们用下面的映射来定义 g中使用到的 4个S-boxes：

             g(X) = h(X, S)

             其中S 是上面计算出来的 k维向量。
             这样g 中出现的s(i)()就可以用h(X, S)来解决了。

         3.4 The Expanded Key Words K(i)

             下面介绍如何计算K(i)：

                   p = 2^24 + 2^16 + 2^8 + 2^0
                A(i) = h(2ip, Me)
                B(i) = ROL(h((2i+1)p, Mo), 8)
               K(2i) = (A(i) + B(i)) mod 2^32
             K(2i+1) = ROL((A(i) + 2B(i)) mod 2^32, 9)

             这里 i = 0, ... ,19

         3.5 The Permutations q0 and q1

             q0 q1是有256个元素的数组，数组中的元素是 8-bit的。它们的构成方

         法如下：

             a0, b0 = [x/16], x mod 16
                 a1 = a0 xor b0
                 b1 = a0 xor ROR(b0, 1) xor 8a0 mod 16
             a2, b2 = t0[a1], t1[b1]
                 a3 = a2 xor b2
                 b3 = a2 xor ROR(b2, 1) xor 8a2 mod 16
             a4, b4 = t2[a3], t3[b3]
                  y = 16b4 + a4

         这里a(i) b(i)都是4-bit的，其中的ROR运算也是4-bit的。这样利用上面的
         公式，就将一个16-bit的x 映射到一个16-bit的 y，我们把当x = i 的时候
         y的值定义为q[i]，这样当x = 0, ... 255时，也就求出了q[i]中的256个元
         素。对于q0 q1，上述公式中的t0 t1 t2 t3分别定义如下：

         对于q0：

             t0 = [8 1 7 D 6 F 3 2 0 B 5 9 E C A 4]
             t1 = [E C B 8 1 2 3 5 F 4 A 6 7 0 9 D]
             t2 = [B A 5 E 6 D 9 0 C 8 F 3 2 4 7 1]
             t3 = [D 7 F 4 1 2 6 E 9 B 3 0 8 5 C A]

         对于q1：

             t0 = [2 8 B D F 7 6 E 3 1 9 4 0 A C 5]
             t1 = [1 E 2 B 4 C 3 7 6 D A 5 F 9 0 8]
             t2 = [4 C 7 5 1 6 9 A 0 E D 8 2 B 3 F]
             t3 = [B 9 5 1 C 3 D E 6 4 7 F 2 0 8 A]

         这样，Twofish 算法的全部计算过程我就讲完了，其中说的不够详细的地方
         大家可以参看官方的文档，或者网上下载的源程序。这篇文章中有几处没有

         详细说明：

         1.如何根据定义g(X) = h(X, S)求出相应的S-boxes
         2.如何在有限域GF(2^8)上进行矩阵运算

             其实上面这两个问题都是关于有限域(finite field)的，如果直接按照
         定义去计算，运算过程十分复杂。但 MDS与 RS 矩阵都有各自的特点，所以
         在写程序的时候可以将运算化简。对于 Twofish算法中，有限域的更进一步
         讨论我将再专门写一篇文章，有兴趣的朋友可以关注一下我的blog。

             另外我要说是，在 Twofish算法中，可以使用几种加密模式，例如：

         ECB (electronic code book)
         CBC (cipher block chain)

         等等，如果我有精力继续写文档我会不定期的发布在我的blog上，最后再贴
         一下我的blog，算是一个小小的宣传，呵呵：

         http://lionel.blogchina.com

         欢迎大家去我的blog继续讨论