Articles

Twofish加密算法详解

几天分析一软件,发现其序列号用到了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的源程序都是外国人写的,还可以找到有一些TwofishSDK。 但它们普遍代码庞大,使用起来都不太方便,不如根据自己的需要,自己写一个代码。 我写了一个可以用Twofish进行加密解密的代码,才不过 400行,所以在看下面的文章之前,你首先要对自己有信心, 因为其中用到了一些数学知识。你也可以参考Twofish官方文档

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

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

怎么样?看完之后有点晕了吧?里面有很多英文的术语,我不知道对应的中文怎么说,所以索性下面的术语就直接都用英文的好了。在讲解每一步具体如何计算之前我们先做一些准备工作,说明一下其中字母各代表什么。其中开始处 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)上的44 MDS矩阵相乘,得到 41的列向量。最后将这个列向量中的四个元素组成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。