XXTEA 加密算法的 JavaScript 和 PHP 实现

原创作品,转载请注明出处。

微型加密算法(TEA)及其相关变种(XTEA,Block TEA,XXTEA) 都是分组加密算法,它们很容易被描述,实现也很简单(典型的几行代码)。

TEA 算法最初是由剑桥计算机实验室的 David Wheeler 和 Roger Needham 在 1994 年设计的。该算法使用 128 位的密钥为 64 位的信息块进行加密,它需要进行 64 轮迭代,尽管作者认为 32 轮已经足够了。该算法使用了一个神秘常数δ作为倍数,它来源于黄金比率,以保证每一轮加密都不相同。但δ的精确值似乎并不重要,这里 TEA 把它定义为 δ=「(√5 - 1)231」(也就是程序中的 0×9E3779B9)。

之后 TEA 算法被发现存在缺陷,作为回应,设计者提出了一个 TEA 的升级版本——XTEA(有时也被称为“tean”)。XTEA 跟 TEA 使用了相同的简单运算,但它采用了截然不同的顺序,为了阻止密钥表攻击,四个子密钥(在加密过程中,原 128 位的密钥被拆分为 4 个 32 位的子密钥)采用了一种不太正规的方式进行混合,但速度更慢了。

在跟描述 XTEA 算法的同一份报告中,还介绍了另外一种被称为 Block TEA 算法的变种,它可以对 32 位大小任意倍数的变量块进行操作。该算法将 XTEA 轮循函数依次应用于块中的每个字,并且将它附加于它的邻字。该操作重复多少轮依赖于块的大小,但至少需要 6 轮。该方法的优势在于它无需操作模式(CBC,OFB,CFB 等),密钥可直接用于信息。对于长的信息它可能比 XTEA 更有效率。

在 1998 年,Markku-Juhani Saarinen 给出了一个可有效攻击 Block TEA 算法的代码,但之后很快 David J. Wheeler 和 Roger M. Needham 就给出了 Block TEA 算法的修订版,这个算法被称为 XXTEA。XXTEA 使用跟 Block TEA 相似的结构,但在处理块中每个字时利用了相邻字。它利用一个更复杂的 MX 函数代替了 XTEA 轮循函数,MX 使用 2 个输入量。

XXTEA 算法很安全,而且非常快速,非常适合应用于 Web 开发中。但目前似乎很少有人将该算法用于实际开发中。甚至国内尚无介绍该算法的文章(至少在 Google 上搜索不到这方面的中文文章,关于密码学算法的书中也未见提及)。我在 Google 上搜索到了几个国外的 XXTEA 算法的实现(见参考文献),但基本上都是 JavaScript 的,但这些 JavaScript 实现也有一些问题,如果加密字符串长度不是 4 的整数倍,则这些实现的在加密后无法真正还原,还原以后的字符串实际上与原字符串不相等,而是后面多了一些 \0 的字符,或者少了一些 \0 的字符。

原因在于 XXTEA 算法只定义了如何对 32 位的信息块数组(实际上是 32 位无符号整数数组)进行加密,而并没有定义如何来将字符串编码为这种数组。而现有的实现中在将字符串编码为整数数组时,都丢失了字符串长度信息,因此还原出现了问题。另外单纯的 JavaScript 是没有意义的,因为单纯的客户端加密解密是不能有效保证信息的安全性的。因此我写了这个 JavaScript 和 PHP 实现,这两种实现在字符串编码上采用的算法是一致的,因此 JavaScript 加密的内容可以用 PHP 实现的解密算法进行解密,反之亦然。

注意:如果需要在 JavaScript 中加密解密带有汉字的信息, 在加密时,需要先将带加密信息用 utf16to8 进行转换,解密时,需要将解密后的内容再用 utf8to16 还原。如果要在 PHP 和 JavaScript 之间传递带有汉字的加密信息,原信息需要用 UTF-8 字符集。

2006年12月9日 更新

当解密失败时(如未使用正确的密钥),可以返回 null(JavaScript) 或 flase(PHP)。

2006年7月23日 更新

修正了当密钥不足 16 个字节时无法加密/解密的问题。

2006年6月27日 更新

修正了大多数 Linux 系统上 PHP 浮点数到整数转化不正常引起的加密解密不正确的问题。(十分感谢 lynk 和 lishouming 二位的帮助和测试!)

2006年3月7日 更新

修正了在 64 位机上不能正常工作的问题。(十分感谢 大侠鼎力相助测试!)

JavaScript 版本的演示程序:http://test.coolcode.cn/xxtea/

JavaScript 实现代码

xxtea.js
  1. /* XXTEA encryption arithmetic library.
  2. *
  3. * Copyright (C) 2006 Ma Bingyao <andot@ujn.edu.cn>
  4. * Version:      1.5
  5. * LastModified: Dec 9, 2006
  6. * This library is free.  You can redistribute it and/or modify it.
  7. */
  8.  
  9. function long2str(v, w) {
  10.     var vl = v.length;
  11.     var n = (vl - 1) << 2;
  12.     if (w) {
  13.         var m = v[vl - 1];
  14.         if ((m < n - 3) || (m > n)) return null;
  15.         n = m;
  16.     }
  17.     for (var i = 0; i < vl; i++) {
  18.         v[i] = String.fromCharCode(v[i] & 0xff,
  19.                                    v[i] >>> 8 & 0xff,
  20.                                    v[i] >>> 16 & 0xff,
  21.                                    v[i] >>> 24 & 0xff);
  22.     }
  23.     if (w) {
  24.         return v.join('').substring(0, n);
  25.     }
  26.     else {
  27.         return v.join('');
  28.     }
  29. }
  30.  
  31. function str2long(s, w) {
  32.     var len = s.length;
  33.     var v = [];
  34.     for (var i = 0; i < len; i += 4) {
  35.         v[i >> 2] = s.charCodeAt(i)
  36.                   | s.charCodeAt(i + 1) << 8
  37.                   | s.charCodeAt(i + 2) << 16
  38.                   | s.charCodeAt(i + 3) << 24;
  39.     }
  40.     if (w) {
  41.         v[v.length] = len;
  42.     }
  43.     return v;
  44. }
  45.  
  46. function xxtea_encrypt(str, key) {
  47.     if (str == "") {
  48.         return "";
  49.     }
  50.     var v = str2long(str, true);
  51.     var k = str2long(key, false);
  52.     if (k.length < 4) {
  53.         k.length = 4;
  54.     }
  55.     var n = v.length - 1;
  56.  
  57.     var z = v[n], y = v[0], delta = 0x9E3779B9;
  58.     var mx, e, p, q = Math.floor(6 + 52 / (n + 1)), sum = 0;
  59.     while (0 < q--) {
  60.         sum = sum + delta & 0xffffffff;
  61.         e = sum >>> 2 & 3;
  62.         for (p = 0; p < n; p++) {
  63.             y = v[p + 1];
  64.             mx = (z >>> 5 ^ y << 2) + (y >>> 3 ^ z << 4) ^ (sum ^ y) + (k[p & 3 ^ e] ^ z);
  65.             z = v[p] = v[p] + mx & 0xffffffff;
  66.         }
  67.         y = v[0];
  68.         mx = (z >>> 5 ^ y << 2) + (y >>> 3 ^ z << 4) ^ (sum ^ y) + (k[p & 3 ^ e] ^ z);
  69.         z = v[n] = v[n] + mx & 0xffffffff;
  70.     }
  71.  
  72.     return long2str(v, false);
  73. }
  74.  
  75. function xxtea_decrypt(str, key) {
  76.     if (str == "") {
  77.         return "";
  78.     }
  79.     var v = str2long(str, false);
  80.     var k = str2long(key, false);
  81.     if (k.length < 4) {
  82.         k.length = 4;
  83.     }
  84.     var n = v.length - 1;
  85.  
  86.     var z = v[n - 1], y = v[0], delta = 0x9E3779B9;
  87.     var mx, e, p, q = Math.floor(6 + 52 / (n + 1)), sum = q * delta & 0xffffffff;
  88.     while (sum != 0) {
  89.         e = sum >>> 2 & 3;
  90.         for (p = n; p > 0; p--) {
  91.             z = v[p - 1];
  92.             mx = (z >>> 5 ^ y << 2) + (y >>> 3 ^ z << 4) ^ (sum ^ y) + (k[p & 3 ^ e] ^ z);
  93.             y = v[p] = v[p] - mx & 0xffffffff;
  94.         }
  95.         z = v[n];
  96.         mx = (z >>> 5 ^ y << 2) + (y >>> 3 ^ z << 4) ^ (sum ^ y) + (k[p & 3 ^ e] ^ z);
  97.         y = v[0] = v[0] - mx & 0xffffffff;
  98.         sum = sum - delta & 0xffffffff;
  99.     }
  100.  
  101.     return long2str(v, true);
  102. }

PHP 实现代码

xxtea.php
  1. <?php
  2. /* XXTEA encryption arithmetic library.
  3. *
  4. * Copyright (C) 2006 Ma Bingyao <andot@ujn.edu.cn>
  5. * Version:      1.5
  6. * LastModified: Dec 5, 2006
  7. * This library is free.  You can redistribute it and/or modify it.
  8. */
  9.  
  10. function long2str($v, $w) {
  11.     $len = count($v);
  12.     $n = ($len - 1) << 2;
  13.     if ($w) {
  14.         $m = $v[$len - 1];
  15.         if (($m < $n - 3) || ($m > $n)) return false;
  16.         $n = $m;
  17.     }
  18.     $s = array();
  19.     for ($i = 0; $i < $len; $i++) {
  20.         $s[$i] = pack("V", $v[$i]);
  21.     }
  22.     if ($w) {
  23.         return substr(join('', $s), 0, $n);
  24.     }
  25.     else {
  26.         return join('', $s);
  27.     }
  28. }
  29.  
  30. function str2long($s, $w) {
  31.     $v = unpack("V*", $s. str_repeat("\0", (4 - strlen($s) % 4) & 3));
  32.     $v = array_values($v);
  33.     if ($w) {
  34.         $v[count($v)] = strlen($s);
  35.     }
  36.     return $v;
  37. }
  38.  
  39. function int32($n) {
  40.     while ($n >= 2147483648) $n -= 4294967296;
  41.     while ($n <= -2147483649) $n += 4294967296;
  42.     return (int)$n;
  43. }
  44.  
  45. function xxtea_encrypt($str, $key) {
  46.     if ($str == "") {
  47.         return "";
  48.     }
  49.     $v = str2long($str, true);
  50.     $k = str2long($key, false);
  51.     if (count($k) < 4) {
  52.         for ($i = count($k); $i < 4; $i++) {
  53.             $k[$i] = 0;
  54.         }
  55.     }
  56.     $n = count($v) - 1;
  57.  
  58.     $z = $v[$n];
  59.     $y = $v[0];
  60.     $delta = 0x9E3779B9;
  61.     $q = floor(6 + 52 / ($n + 1));
  62.     $sum = 0;
  63.     while (0 < $q--) {
  64.         $sum = int32($sum + $delta);
  65.         $e = $sum >> 2 & 3;
  66.         for ($p = 0; $p < $n; $p++) {
  67.             $y = $v[$p + 1];
  68.             $mx = int32((($z >> 5 & 0x07ffffff) ^ $y << 2) + (($y >> 3 & 0x1fffffff) ^ $z << 4)) ^ int32(($sum ^ $y) + ($k[$p & 3 ^ $e] ^ $z));
  69.             $z = $v[$p] = int32($v[$p] + $mx);
  70.         }
  71.         $y = $v[0];
  72.         $mx = int32((($z >> 5 & 0x07ffffff) ^ $y << 2) + (($y >> 3 & 0x1fffffff) ^ $z << 4)) ^ int32(($sum ^ $y) + ($k[$p & 3 ^ $e] ^ $z));
  73.         $z = $v[$n] = int32($v[$n] + $mx);
  74.     }
  75.     return long2str($v, false);
  76. }
  77.  
  78. function xxtea_decrypt($str, $key) {
  79.     if ($str == "") {
  80.         return "";
  81.     }
  82.     $v = str2long($str, false);
  83.     $k = str2long($key, false);
  84.     if (count($k) < 4) {
  85.         for ($i = count($k); $i < 4; $i++) {
  86.             $k[$i] = 0;
  87.         }
  88.     }
  89.     $n = count($v) - 1;
  90.  
  91.     $z = $v[$n];
  92.     $y = $v[0];
  93.     $delta = 0x9E3779B9;
  94.     $q = floor(6 + 52 / ($n + 1));
  95.     $sum = int32($q * $delta);
  96.     while ($sum != 0) {
  97.         $e = $sum >> 2 & 3;
  98.         for ($p = $n; $p > 0; $p--) {
  99.             $z = $v[$p - 1];
  100.             $mx = int32((($z >> 5 & 0x07ffffff) ^ $y << 2) + (($y >> 3 & 0x1fffffff) ^ $z << 4)) ^ int32(($sum ^ $y) + ($k[$p & 3 ^ $e] ^ $z));
  101.             $y = $v[$p] = int32($v[$p] - $mx);
  102.         }
  103.         $z = $v[$n];
  104.         $mx = int32((($z >> 5 & 0x07ffffff) ^ $y << 2) + (($y >> 3 & 0x1fffffff) ^ $z << 4)) ^ int32(($sum ^ $y) + ($k[$p & 3 ^ $e] ^ $z));
  105.         $y = $v[0] = int32($v[0] - $mx);
  106.         $sum = int32($sum - $delta);
  107.     }
  108.     return long2str($v, true);
  109. }
  110. ?>

原创作品,转载请注明出处。

参考文献

Correction to xtea David J. Wheeler Roger M. Needham Computer Laboratory Cambridge University England October 1998

Tinyness: An Overview of TEA and Related Ciphers

JavaScript Encryption Library

JavaScript Implementation of Block TEA Tiny Encryption Algorithm

TEA Encryption Algorithm (pascal)

标签: PHP, JavaScript, Cryptology

« 上一篇 | 下一篇 »

只显示10条记录相关文章

6 条回复至 "XXTEA 加密算法的 JavaScript 和 PHP 实现" 的评论

博主,希望你抽时间看下这个。JS加密,PHP解密,这个很实用的,以后随着互联网的发展,这个是很需要的。我试过用你所说的http://www.phprpc.org/zh_CN/download/ 东西,但没有成功,依然是各自能解密各自的加密。

由 我的青春 于 2013-01-14 17:38:39 提交#1

博主,你能不能帮忙测试一下,我怎么试JS中的解密到PHP中就是无法解密。而且我也用了你说的PHPRPC里面的文件。

还希望指教一下。

我的青春 于 2013-01-05 20:48:26 提交#2

明天先用gbk试下,不晓得JS杂弄成utf-8东西的。

我的青春 于 2013-01-04 23:24:30 提交#3

javascript 下需要先把 string 变成 utf8 编码的字节 string,参见http://www.phprpc.org/zh_CN/download/ 里面 PHPRPC for javascript中的实现。

andot 于 2013-01-04 21:59:00 提交#4

博主,你好

目前我完全copy你的代码,在utf-8环境中测试,都是只能解密各自的加密,并不能出现JS加密,PHP解密。

真诚的希望得到博主的帮助。

谢谢!

由 我的青春 于 2012-12-30 20:41:45 提交#5

博主,请问这个解密还有更新吗???似乎是2006的东西。可有新稳定版本????有在项目中实施吗???

我的青春 于 2012-12-19 21:52:19 提交#6


发表评论

评论 (必须):