| 查看: 615 | 回复: 1 | |||
| 当前主题已经存档。 | |||
sdlj8051金虫 (著名写手)
|
[交流]
[转贴]Twofish加密算法详解
|
||
|
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的基础。 [ Last edited by sdlj8051 on 2006-10-6 at 12:45 ] |
回复此楼» 猜你喜欢
求调剂一志愿武汉理工大学材料工程（085601）
已经有7人回复
-
一志愿C9材料与化工专业总分300求调剂
已经有4人回复
-
321求调剂
已经有4人回复
-
307求调剂
已经有4人回复
-
293求调剂
已经有6人回复
-
085602 289分求调剂
已经有3人回复
-
一志愿北京化工大学材料与化工 264分各科过A区国家线
已经有3人回复
-
277分求调剂，跨调材料
已经有3人回复
-
材料292调剂
已经有6人回复
-
材料与化工考研调剂
已经有6人回复
sdlj8051
金虫 (著名写手)
- 应助: 0 (幼儿园)
- 贵宾: 0.1
- 金币: 1149.8
- 红花: 3
- 帖子: 2254
- 在线: 18.1小时
- 虫号: 71297
- 注册: 2005-05-30
- 专业: 电路与系统
|
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，这样当x = 0, ... 255时，也就求出了q中的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 矩阵都有各自的特点，所以 在写程序的时候可以将运算化简。 |
2楼2006-08-23 15:46:57
