XXTEA 加密算法的 PHP 实现

之前在应用中都在使用discuz里的加密解密方法 authcode (http://www.notech.net/?p=161) 这里介绍一下TEA加密的一个衍生版本XXTEA.   xxtea在在我的微博系统中有应用到 微型加密算法(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 字符集。 具体实现如下:

<?php
/*
 * xtea加密算法
 */

class XxTea {

  /**
    * 加密方法
    *
    * @param string $str    需要加密的内容
    * @param string $key    密钥
    * @param bool $toBase64  是否base64(最好true吧,比如cookie加密长度有限制的)
    * return string
    */
  public function encrypt($str, $key, $toBase64=true) {
    if ($str == "") {
      return "";
    }
    $v = $this->_str2long ( $str, true );
    $k = $this->_str2long ( $key, false );
    if (count ( $k ) < 4) {
      for($i = count ( $k ); $i < 4; $i ++) {
        $k [$i] = 0;
      }
    }
    $n = count ( $v ) - 1;

    $z = $v [$n];
    $y = $v [0];
    $delta = 0x9E3779B9;
    $q = floor ( 6 + 52 / ($n + 1) );
    $sum = 0;
    while ( 0 < $q -- ) {
      $sum = $this->_int32 ( $sum + $delta );
      $e = $sum >> 2 & 3;
      for($p = 0; $p < $n; $p ++) {
        $y = $v [$p + 1];
        $mx = $this->_int32 ( (($z >> 5 & 0x07ffffff) ^ $y << 2) + (($y >> 3 & 0x1fffffff) ^ $z << 4) ) ^ $this->_int32 ( ($sum ^ $y) + ($k [$p & 3 ^ $e] ^ $z) );
        $z = $v [$p] = $this->_int32 ( $v [$p] + $mx );
      }
      $y = $v [0];
      $mx = $this->_int32 ( (($z >> 5 & 0x07ffffff) ^ $y << 2) + (($y >> 3 & 0x1fffffff) ^ $z << 4) ) ^ $this->_int32 ( ($sum ^ $y) + ($k [$p & 3 ^ $e] ^ $z) );
      $z = $v [$n] = $this->_int32 ( $v [$n] + $mx );
    }
    if ($toBase64) {
      return base64_encode($this->_long2str ( $v, false ));
    }
    return $this->_long2str ( $v, false );
  }

  /**
    * 解密方法
    *
    * @param string $str    加密后的内容
    * @param string $key    密钥
    * @param bool $toBase64  
    * return string
    */
  public function decrypt($str, $key, $toBase64=true) {
    if ($str == "") {
      return "";
    }
    $toBase64 && $str = base64_decode($str);
    $v = $this->_str2long ( $str, false );
    $k = $this->_str2long ( $key, false );
    if (count ( $k ) < 4) {
      for($i = count ( $k ); $i < 4; $i ++) {
        $k [$i] = 0;
      }
    }
    $n = count ( $v ) - 1;

    $z = $v [$n];
    $y = $v [0];
    $delta = 0x9E3779B9;
    $q = floor ( 6 + 52 / ($n + 1) );
    $sum = $this->_int32 ( $q * $delta );
    while ( $sum != 0 ) {
      $e = $sum >> 2 & 3;
      for($p = $n; $p > 0; $p --) {
        $z = $v [$p - 1];
        $mx = $this->_int32 ( (($z >> 5 & 0x07ffffff) ^ $y << 2) + (($y >> 3 & 0x1fffffff) ^ $z << 4) ) ^ $this->_int32 ( ($sum ^ $y) + ($k [$p & 3 ^ $e] ^ $z) );
        $y = $v [$p] = $this->_int32 ( $v [$p] - $mx );
      }
      $z = $v [$n];
      $mx = $this->_int32 ( (($z >> 5 & 0x07ffffff) ^ $y << 2) + (($y >> 3 & 0x1fffffff) ^ $z << 4) ) ^ $this->_int32 ( ($sum ^ $y) + ($k [$p & 3 ^ $e] ^ $z) );
      $y = $v [0] = $this->_int32 ( $v [0] - $mx );
      $sum = $this->_int32 ( $sum - $delta );
    }
    return $this->_long2str ( $v, true );
  }

  /**
    * 长整型转为字符串
    *
    * @param long $v
    * @param boolean $w
    * @return string
    */
  private function _long2str($v, $w) {
    $len = count ( $v );
    $n = ($len - 1) << 2;
    if ($w) {
      $m = $v [$len - 1];
      if (($m < $n - 3) || ($m > $n))
        return false;
      $n = $m;
    }
    $s = array ();
    for($i = 0; $i < $len; $i ++) {
      $s [$i] = pack ( "V", $v [$i] );
    }
    if ($w) {
      return substr ( join ( '', $s ), 0, $n );
    } else {
      return join ( '', $s );
    }
  }

  /**
    * 字符串转为长整型
    *
    * @param string $s
    * @param boolean $w
    * @return Ambigous <multitype:, number>
    */
  private function _str2long($s, $w) {
    $v = unpack ( "V*", $s . str_repeat ( "\0", (4 - strlen ( $s ) % 4) & 3 ) );
    $v = array_values ( $v );
    if ($w) {
      $v [count ( $v )] = strlen ( $s );
    }
    return $v;
  }

  private function _int32($n) {
    while ( $n >= 2147483648 )
      $n -= 4294967296;
    while ( $n <= - 2147483649 )
      $n += 4294967296;
    return ( int ) $n;
  }
}

// 使用方式
$xxtea = new XxTea();
$string = 'hello leven';
$key = '123456';
$encode = $xxtea->encrypt($string,$key,true);
$decode = $xxtea->decrypt($encode,$key,true);
echo $encode;
echo "<br />";
echo $decode;