TITLE  : Twofish加密算法详解
AUTHOR : lionel@nkbbs.org
BLOG   : http://lionel.blogchina.com
DATE   : 01/08/2005

CONTENT: 这几天分析一软件,发现其序列号用到了Twofish 加密算法,上网找了很久
         都没有找到相应的中文资料,于是决定等我研究明白之后写一篇文档,以便
         给今后需要使用Twofish 的人以参考,下面进入正题。

             首先介绍一下Twofish 的历史,如果您只想了解如何运用此算法,请直
         接跳到下一段。在1972到1974年中,National Bureau of Standards (现在
         更名为National Institute of Standards and Tecnology,缩写为NIST)首
         次公开征求一种标准的数据加密算法,结果产生了 DES ( Data Encryption
         Standard) 加密算法。但DES 的密钥长度对于现在计算机的运行速度来说,
         在某些高机密的场合显得有点不足,已经不再安全。所以1999年NIST决定采
         用一种更高标准的加密算法AES (Advanced Encryption Standard)来代替原
         来的DES。首先这种加密算法必须是块加密 (block cipher),因为块加密可
         以被用来对数据流进行加密,也可以被用来制造一些专用的数据加密设备。
         其次,这种加密算法必须使用更长的密钥,更大的加密块,更高的加密速度,
         更高的灵活性。Twofish 则是counterpane 公司向NIST提交的一种满足AES
         要求的加密算法。Twofish 采用128位数据块(128 bits block),128- 192-
         256-bit 可变长度密钥。Twofish 算法是进入NIST第二轮 5种加密算法中的
         一种。下面分步详细讲解如何使用Twofish 加密算法。

             现在网上能找到的大部分Twofish 的源程序都是外国人写的,还可以找
         到有一些 Twofish SDK。但它们普遍代码庞大,使用起来都不太方便,不如
         根据自己的需要,自己写一个代码。我写了一个可以用Twofish 进行加密解
         密的代码,才不过 400行,所以在看下面的文章之前,你首先要对自己有信
         心,因为其中用到了一些数学知识。你也可以参考Twofish 的官方文档:

         http://www.counterpane.com/twofish.html

         其中 paper-twofish-paper.pdf 有 68页,全英文,还不如看我这篇文章来
         的快,呵呵,不过你可以把它与本文互相参照着看。

             Twofish 加密算法的流程图如下:

         ┌───────────────────────────────┐
         │                          P (128 bits)                        │
         └┬───┬─────────────────────┬───┬┘
           │      │                                          │      │
           ⊙←K0  ⊙←K1      <- input whitening ->       K2→⊙  K3→⊙
           │      │                                          │      │
           │      │┌┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┐  │      │
           │      │┆F                                   ┆  │      │
           │      │┆┌┄┄┄┄┄┄┄┄┄┐              ┆  │   <<1│
           │      │┆┆g                 ┆       K(2r+8)┆  │      │
           │      │┆┆            ┌─┐┆            │┆  │      │
           │      │┆┆  ┌S-box0->│  │┆┌┄┄┄┐  │┆  │      │
           │      │┆┆  ├S-box1->│M │┆┆  PHT ┆  ↓┆  ↓      │
           ├───┼┼┼→│        │D ├┼┼→⊙┬┼→⊙┼→⊙      │
           │      │┆┆  ├S-box2->│S │┆┆  ↑│┆    ┆  │      │
           │      │┆┆  └S-box3->│  │┆┆  ││┆    ┆  │      │
           │      │┆┆            └─┘┆┆  ││┆    ┆  │      │
           │      │┆└┄┄┄┄┄┄┄┄┄┘┆  ││┆    ┆  │      │
           │      │┆┌┄┄┄┄┄┄┄┄┄┐┆  ││┆    ┆  │      │
           │      │┆┆g                 ┆┆  ││┆    ┆  │      │
           │      │┆┆            ┌─┐┆┆  ││┆    ┆  │      │
           │      │┆┆  ┌S-box0->│  │┆┆  ││┆    ┆  │      │
           │      │┆┆  ├S-box1->│M │┆┆  ││┆    ┆  │      ↓
           │   <<8├┼┼→│        │D ├┼┼─┴⊙┼→⊙┼─┼──→⊙
           │      │┆┆  ├S-box2->│S │┆┆      ┆  ↑┆  │      │
           │      │┆┆  └S-box3->│  │┆└┄┄┄┘  │┆  │      │
           │      │┆┆            └─┘┆            │┆  │      │
           │      │┆└┄┄┄┄┄┄┄┄┄┘       K(2r+9)┆  │      │
           │      │└┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┘  │>>1   │
           │      │                                          │      │
           │      └─────────┐    ┌────────┘      │
           │                           ╲  ╱                         │
           └─────────────┐ ╳ ┌────────────┘
                                        ╳  ╳
           ┌─────────────┘ ╳ └────────────┐
           │      ┌──────────┘└─────────┐      │

           ...     ...              15 more rounds             ...     ...

           │      └─────────┐    ┌────────┘      │
           │                           ╲  ╱                         │
           └─────────────┐ ╳ ┌────────────┘
                                        ╳  ╳
           ┌─────────────┘ ╳ └────────────┐
           │      ┌──────────┘└─────────┐      │
           ↓      ↓                                          ↓      ↓
           ⊙←K4  ⊙←K5      <- output whitening ->      K6→⊙  →K7⊙
           ↓      ↓                                          ↓      ↓
         ┌───────────────────────────────┐
         │                          C (128 bits)                        │
         └───────────────────────────────┘

             怎么样?看完之后有点晕了吧?里面有很多英文的术语,我不知道对应
         的中文怎么说,所以索性下面的术语就直接都用英文的好了。在讲解每一步
         具体如何计算之前我们先做一些准备工作,说明一下其中字母各代表什么。
         其中开始处 P(plain text)表示需要进行加密的 128-bit数据,也即16字节。
         然后将这16字节分为 4组,每组32-bit,即 4字节。在循环之前首先对这 4
         组数据分别用K0 K1 K2 K3进行异或操作,称之为input whitening,然后对
         异或后的数据分组进行计算。计算后将 1-3 2-4组的数据对换,如此循环15
         次,再 1-3 2-4对换一次。对这 4组数据分别用 K4 K5 K6 K7异或操作,称
         之为 output whitening。最后将这 4组数据组合成 16字节的数据,也就是
         最后的密文 C(cipher text),长度跟加密前的 P同样是128-bit。下面详细
         说明每一计算步骤。

         1.计算前的准备工作

             加密前的plain text是128 bits,也就是16 bytes。假设这16 bytes分
         别是p0, ... ,p15。用little-endian conversion (如果你不明白,可以参
         看我的blog中的的一篇相关文章),将p0, ... ,p15分为 4组:

             P(i) = ∑p(4i+j)2^(8j),其中i,j = 0, ... ,3

         2.Input whitening

             R(0,i) = P(i) xor K(i),其中i = 0, ... ,3

             这里的K(i)是跟据密钥算出来的32-bit数据,计算方法后面介绍。
         3.16次循环

             在16次循环的每一次中, 4组数据的前两组与当前循环次数通过 F进行
         计算,计算出 2组数据。第 3组数据与计算出的第 1组数据异或,然后向右
         循环移动一位。第 4组数据向左循环移动一位,然后异或计算出的第 2组数
         据。然后将 1-3 2-4组数据对换,作为下一轮计算的数据。程序表示如下:

             (F(r,0), F(r,1)) = F(R(r,0), R(r,1), r)
                     R(r+1,0) = ROR(R(r,2) xor F(r,0), 1)
                     R(r+1,1) = ROL(R(r,3), 1) xor F(r,1)
                     R(r+1,2) = R(r,0)
                     R(r+1,3) = R(r,1)

         4.Output whitening

             C(i) = R(16,(i+2) mod 4) xor K(i+4),其中i = 0, ... ,3

             这里的K(i+4)同样是根据密钥计算出来的32-bit数据,目前为止总共有

             K(i) i = 0, ... ,7

         5.计算后组成密文

             c(i) = [C(i/4) / 2^(8(i mod 4))] mod 2^8,其中i = 0, ... ,15

             这样,128-bit的C就计算出来了。
         前面的K(i)和函数 F还没有说明,下面先介绍函数 F。

         1. The Function F

             (F0, F1) = F(R0, R1, r)

             其中参数R0, R1是32-bit 数据,r表示当前循环的次数,T0,T1是计算
         出的结果,同样都是32-bit 的数据。

             T0 = g(R0)
             T1 = g(ROL(R1, 8))
             F0 = (T0 +  T1 + K(2r+8)) mod 2^32
             F1 = (T0 + 2T1 + K(2r+9)) mod 2^32

         其中后两步计算被称为 PHT(Pseudo-Hadamard Transforms)。
         这里K(i) i = 8, ... 39,加上前面的i = 0, ... ,7,所以总共有40个K

             K(i) i = 0, ... ,39

         我们仍然先不讲如何计算K,而先介绍函数 g。

         2. The Function g

             Z = g(X)

             函数 g是Twofish 算法的核心,也是比较难理解的一部分。其中参数 X
         与计算结果 Z都是32-bit的数据。

             x(i) = [X/2^(8i)] mod 2^8,其中i = 0, ... ,3
             y(i) = s(i)(x(i))        ,其中i = 0, ... ,3
             ┌  ┐  ┌   ┐  ┌  ┐
             │z0│  │   │  │y0│
             │z1│= │MDS│·│y1│
             │z2│  │   │  │y2│
             │z3│  │   │  │y3│
             └  ┘  └   ┘  └  ┘
             Z = ∑z(i)2^(8i),其中i = 0, ... ,3

             首先将32-bit的参数 X分为 4个字节x0, ... ,x4,然后每一个x(i) 分
         别进入自己的S-box,其中每一个S-box 都是8-bit输入, 8-bit输出。这样
         计算出来的 y(i)仍然是 8-bit,组成一个4 * 1的列向量,这个向量与定义
         在GF(2^8)上的4*4 MDS矩阵相乘,得到 4*1的列向量。最后将这个列向量中
         的四个元素组成32-bit数据 Z。其中 MDS矩阵为:

                   ┌           ┐
                   │01 EF 5B 5B│
             MDS = │5B EF EF 01│
                   │EF 5B 01 EF│
                   │EF 01 EF 5B│
                   └           ┘

         为了数据的计算,还必须明确定义GF,对于MDS 矩阵,GF的定义如下:

             GF(2^8) ≡ GF(2)(x)/v(x),其中v(x) = x^8 + x^6 + x^5 + x^3 + 1

         又不太明白了吧?上面不太容易理解的地方有两处,一个是 S-boxes,一个
         是在有限域GF上如何进行计算。对于前一个问题,我们将会在下面进行介绍,
         对于后一个问题,我将会专门写一篇在有限域上进行计算的文章,如果你感
         兴趣可以去我的blog。

             我们再总结一下吧,目前还有哪些问题没有解决:

             K(i),i = 0, ... ,39

             s(i)(),i = 0, ... ,3

         以上这两组数据都是通过密钥计算出来的 (key-dependent),所以下面我们
         该介绍一下密钥了。

         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继续讨论。