介绍XXTEA加密算法

2013/02/20 15:01
阅读数 8.4K

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

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

其实,TEA跟我们的关系非常密切,因为QQ就是使用16轮迭代的TEA算法。

XXTEA是其最新的变种,于1998年提出。目前还没有人找到对其进行攻击的方法,是对前面一些变种的改进。XXTEA 算法很安全,而且非常快速,非常适合应用于 Web 开发中。

下面是作者给出的该算法的C实现:


#define MX (z>>5^y<<2) + (y>>3^z<<4)^(sum^y) + (k[p&3^e]^z);
 
 long btea(long* v, long n, long* k) {
   unsigned long z=v[n-1], y=v[0], sum=0, e, DELTA=0x9e3779b9;
   long p, q ;
   if (n > 1) {         
     q = 6 + 52/n;
     while (q-- > 0) {
       sum += DELTA;
       e = (sum >> 2) & 3;
       for (p=0; p<n-1; p++) y = v[p+1], z = v[p] += MX;
       y = v[0];
       z = v[n-1] += MX;
     }
     return 0 ;
   } else if (n < -1) { 
     n = -n;
     q = 6 + 52/n;
     sum = q*DELTA ;
     while (sum != 0) {
       e = (sum >> 2) & 3;
       for (p=n-1; p>0; p--) z = v[p-1], y = v[p] -= MX;
       z = v[n-1];
       y = v[0] -= MX;
       sum -= DELTA;
     }
     return 0;
   }
   return 1;
 }


瞧,短的惊人吧!

咱也搞不明白数学上的东西,有兴趣的话就去上面那个wikipedia里看吧。我这里就讲讲怎么用。

teab will encode or decode n words as a single block wheren> 1

  • v is the n word data vector
  • k is the 4 word key
  • n is negative for decoding
  • if n is zero result is 1 and no coding or decoding takes place, otherwise the result is zero
  • assumes 32 bit ‘long’ and same endian coding and decoding

这是wikipedia里的说明,讲得比较明白了。

最核心的是要明白:XXTEA算法使用128bit的密钥对以32bit为单位的信息块进行加密。

这段介绍里的'word’这个词让我很费了一番周折。我开始以为是“字”,也就是2byte,16bit。但是在我耗费了不少时间进行测试和实验后,可以确定,word在这里不是一个单位,大概是要翻译成“组元”之类的词,其实就是后面说的一个32bit的long类型。

搞清楚这个,别的就没什么了。刚才那段代码:

 long btea(long* v, long n, long* k)

v是要加密的组元的起始地址,以32bit为单位,这里用long来实现。

n是要加密的组元个数,正数是加密,负数是解密。

k是密钥的起始地址,长度为4个组元,4*32=128bit。

返回值为0或1(对应n=0,没有计算)。

加密的结果会直接写回到v中。

经过试验,我还有一点要补充的,XXTEA的计算是空间相关的,也就是说,在一个组元中,4个字节是不能断章取义的,即密文的一部分,并不能还原成明文的一部分。所以,当数据不能被4个字节整除时,要做好字节的填充和对其等辅助工作。

xxtea可逆加密算法PHP实现:

Class Xxtea {
	public function encrypt($s, $key) {
		return base64_encode(self :: xxtea_encrypt($s, $key));
	}
	public function decrypt($e, $key) {
		return self :: xxtea_decrypt(base64_decode($e), $key);
	}
	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);
		}
	}
	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;
	}
	private function xxtea_encrypt($str, $key) {
		if ($str == "") {
			return "";
		}
		$v = self :: str2long($str, true);
		$k = self :: 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 = self :: int32($sum + $delta);
			$e = $sum >> 2 & 3;
			for ($p = 0; $p < $n; $p++) {
				$y = $v[$p +1];
				$mx = self :: int32((($z >> 5 & 0x07ffffff) ^ $y << 2) + (($y >> 3 & 0x1fffffff) ^ $z << 4)) ^ self :: int32(($sum ^ $y) + ($k[$p & 3 ^ $e] ^ $z));
				$z = $v[$p] = self :: int32($v[$p] + $mx);
			}
			$y = $v[0];
			$mx = self :: int32((($z >> 5 & 0x07ffffff) ^ $y << 2) + (($y >> 3 & 0x1fffffff) ^ $z << 4)) ^ self :: int32(($sum ^ $y) + ($k[$p & 3 ^ $e] ^ $z));
			$z = $v[$n] = self :: int32($v[$n] + $mx);
		}
		return self :: long2str($v, false);
	}
	private function xxtea_decrypt($str, $key) {
		if ($str == "") {
			return "";
		}
		$v = self :: str2long($str, false);
		$k = self :: 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 = self :: int32($q * $delta);

		while ($sum != 0) {
			$e = $sum >> 2 & 3;
			for ($p = $n; $p > 0; $p--) {
				$z = $v[$p -1];
				$mx = self :: int32((($z >> 5 & 0x07ffffff) ^ $y << 2) + (($y >> 3 & 0x1fffffff) ^ $z << 4)) ^ self :: int32(($sum ^ $y) + ($k[$p & 3 ^ $e] ^ $z));
				$y = $v[$p] = self :: int32($v[$p] - $mx);
			}
			$z = $v[$n];
			$mx = self :: int32((($z >> 5 & 0x07ffffff) ^ $y << 2) + (($y >> 3 & 0x1fffffff) ^ $z << 4)) ^ self :: int32(($sum ^ $y) + ($k[$p & 3 ^ $e] ^ $z));
			$y = $v[0] = self :: int32($v[0] - $mx);
			$sum = self :: int32($sum - $delta);
		}
		return self :: long2str($v, true);
	}
}

使用方法:

加密:

Xxtea::encrypt(明文字符串, 密钥字符串);

解密:

Xxtea::decrypt(密文字符串, 密钥字符串);

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部