XXTEA 加密算法的 JavaScript 和 PHP 實現(xiàn)

昵稱3884271 2015-01-16

展開全文

原創(chuàng)作品，轉(zhuǎn)載請注明出處。

微型加密算法（TEA）及其相關變種（XTEA，Block TEA，XXTEA）都是分組加密算法，它們很容易被描述，實現(xiàn)也很簡單（典型的幾行代碼）。

TEA 算法最初是由劍橋計算機實驗室的 David Wheeler 和 Roger Needham 在 1994 年設計的。該算法使用 128 位的密鑰為 64 位的信息塊進行加密，它需要進行 64 輪迭代，盡管作者認為 32 輪已經(jīng)足夠了。該算法使用了一個神秘常數(shù)δ作為倍數(shù)，它來源于黃金比率，以保證每一輪加密都不相同。但δ的精確值似乎并不重要，這里 TEA 把它定義為 δ=「(√5 - 1)2³¹」（也就是程序中的 0×9E3779B9）。

之后 TEA 算法被發(fā)現(xiàn)存在缺陷，作為回應，設計者提出了一個 TEA 的升級版本——XTEA（有時也被稱為“tean”）。XTEA 跟 TEA 使用了相同的簡單運算，但它采用了截然不同的順序，為了阻止密鑰表攻擊，四個子密鑰（在加密過程中，原 128 位的密鑰被拆分為 4 個 32 位的子密鑰）采用了一種不太正規(guī)的方式進行混合，但速度更慢了。

在跟描述 XTEA 算法的同一份報告中，還介紹了另外一種被稱為 Block TEA 算法的變種，它可以對 32 位大小任意倍數(shù)的變量塊進行操作。該算法將 XTEA 輪循函數(shù)依次應用于塊中的每個字，并且將它附加于它的鄰字。該操作重復多少輪依賴于塊的大小，但至少需要 6 輪。該方法的優(yōu)勢在于它無需操作模式（CBC，OFB，CFB 等），密鑰可直接用于信息。對于長的信息它可能比 XTEA 更有效率。

在 1998 年，Markku-Juhani Saarinen 給出了一個可有效攻擊 Block TEA 算法的代碼，但之后很快 David J. Wheeler 和 Roger M. Needham 就給出了 Block TEA 算法的修訂版，這個算法被稱為 XXTEA。XXTEA 使用跟 Block TEA 相似的結(jié)構(gòu)，但在處理塊中每個字時利用了相鄰字。它利用一個更復雜的 MX 函數(shù)代替了 XTEA 輪循函數(shù)，MX 使用 2 個輸入量。

XXTEA 算法很安全，而且非?？焖?，非常適合應用于 Web 開發(fā)中。但目前似乎很少有人將該算法用于實際開發(fā)中。甚至國內(nèi)尚無介紹該算法的文章（至少在 Google 上搜索不到這方面的中文文章，關于密碼學算法的書中也未見提及）。我在 Google 上搜索到了幾個國外的 XXTEA 算法的實現(xiàn)（見參考文獻），但基本上都是 JavaScript 的，但這些 JavaScript 實現(xiàn)也有一些問題，如果加密字符串長度不是 4 的整數(shù)倍，則這些實現(xiàn)的在加密后無法真正還原，還原以后的字符串實際上與原字符串不相等，而是后面多了一些 \0 的字符，或者少了一些 \0 的字符。

原因在于 XXTEA 算法只定義了如何對 32 位的信息塊數(shù)組（實際上是 32 位無符號整數(shù)數(shù)組）進行加密，而并沒有定義如何來將字符串編碼為這種數(shù)組。而現(xiàn)有的實現(xiàn)中在將字符串編碼為整數(shù)數(shù)組時，都丟失了字符串長度信息，因此還原出現(xiàn)了問題。另外單純的 JavaScript 是沒有意義的，因為單純的客戶端加密解密是不能有效保證信息的安全性的。因此我寫了這個 JavaScript 和 PHP 實現(xiàn)，這兩種實現(xiàn)在字符串編碼上采用的算法是一致的，因此 JavaScript 加密的內(nèi)容可以用 PHP 實現(xiàn)的解密算法進行解密，反之亦然。

注意：如果需要在 JavaScript 中加密解密帶有漢字的信息，在加密時，需要先將帶加密信息用 utf16to8 進行轉(zhuǎn)換，解密時，需要將解密后的內(nèi)容再用 utf8to16 還原。如果要在 PHP 和 JavaScript 之間傳遞帶有漢字的加密信息，原信息需要用 UTF-8 字符集。

2006年12月9日更新

當解密失敗時（如未使用正確的密鑰），可以返回 null（JavaScript）或 flase（PHP）。

2006年7月23日更新

修正了當密鑰不足 16 個字節(jié)時無法加密/解密的問題。

2006年6月27日更新

修正了大多數(shù) Linux 系統(tǒng)上 PHP 浮點數(shù)到整數(shù)轉(zhuǎn)化不正常引起的加密解密不正確的問題。（十分感謝 lynk 和 lishouming 二位的幫助和測試?。?/span>

2006年3月7日更新

修正了在 64 位機上不能正常工作的問題。（十分感謝大俠鼎力相助測試?。?/span>

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

JavaScript 實現(xiàn)代碼

xxtea.js

/* XXTEA encryption arithmetic library.
*
* Copyright (C) 2006 Ma Bingyao <andot@ujn.edu.cn>
* Version: 1.5
* LastModified: Dec 9, 2006
* This library is free. You can redistribute it and/or modify it.
*/
function long2str(v, w) {
var vl = v.length;
var n = (vl - 1) << 2;
if (w) {
var m = v[vl - 1];
if ((m < n - 3) || (m > n)) return null;
n = m;
}
for (var i = 0; i < vl; i++) {
v[i] = String.fromCharCode(v[i] & 0xff,
v[i] >>> 8 & 0xff,
v[i] >>> 16 & 0xff,
v[i] >>> 24 & 0xff);
}
if (w) {
return v.join('').substring(0, n);
}
else {
return v.join('');
}
}
function str2long(s, w) {
var len = s.length;
var v = [];
for (var i = 0; i < len; i += 4) {
v[i >> 2] = s.charCodeAt(i)
| s.charCodeAt(i + 1) << 8
| s.charCodeAt(i + 2) << 16
| s.charCodeAt(i + 3) << 24;
}
if (w) {
v[v.length] = len;
}
return v;
}
function xxtea_encrypt(str, key) {
if (str == "") {
return "";
}
var v = str2long(str, true);
var k = str2long(key, false);
if (k.length < 4) {
k.length = 4;
}
var n = v.length - 1;
var z = v[n], y = v[0], delta = 0x9E3779B9;
var mx, e, p, q = Math.floor(6 + 52 / (n + 1)), sum = 0;
while (0 < q--) {
sum = sum + delta & 0xffffffff;
e = sum >>> 2 & 3;
for (p = 0; p < n; p++) {
y = v[p + 1];
mx = (z >>> 5 ^ y << 2) + (y >>> 3 ^ z << 4) ^ (sum ^ y) + (k[p & 3 ^ e] ^ z);
z = v[p] = v[p] + mx & 0xffffffff;
}
y = v[0];
mx = (z >>> 5 ^ y << 2) + (y >>> 3 ^ z << 4) ^ (sum ^ y) + (k[p & 3 ^ e] ^ z);
z = v[n] = v[n] + mx & 0xffffffff;
}
return long2str(v, false);
}
function xxtea_decrypt(str, key) {
if (str == "") {
return "";
}
var v = str2long(str, false);
var k = str2long(key, false);
if (k.length < 4) {
k.length = 4;
}
var n = v.length - 1;
var z = v[n - 1], y = v[0], delta = 0x9E3779B9;
var mx, e, p, q = Math.floor(6 + 52 / (n + 1)), sum = q * delta & 0xffffffff;
while (sum != 0) {
e = sum >>> 2 & 3;
for (p = n; p > 0; p--) {
z = v[p - 1];
mx = (z >>> 5 ^ y << 2) + (y >>> 3 ^ z << 4) ^ (sum ^ y) + (k[p & 3 ^ e] ^ z);
y = v[p] = v[p] - mx & 0xffffffff;
}
z = v[n];
mx = (z >>> 5 ^ y << 2) + (y >>> 3 ^ z << 4) ^ (sum ^ y) + (k[p & 3 ^ e] ^ z);
y = v[0] = v[0] - mx & 0xffffffff;
sum = sum - delta & 0xffffffff;
}
return long2str(v, true);
}

PHP 實現(xiàn)代碼

xxtea.php

<?php
/* XXTEA encryption arithmetic library.
*
* Copyright (C) 2006 Ma Bingyao <andot@ujn.edu.cn>
* Version: 1.5
* LastModified: Dec 5, 2006
* This library is free. You can redistribute it and/or modify it.
*/
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);
}
}
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;
}
function int32($n) {
while ($n >= 2147483648) $n -= 4294967296;
while ($n <= -2147483649) $n += 4294967296;
return (int)$n;
}
function xxtea_encrypt($str, $key) {
if ($str == "") {
return "";
}
$v = str2long($str, true);
$k = 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 = int32($sum + $delta);
$e = $sum >> 2 & 3;
for ($p = 0; $p < $n; $p++) {
$y = $v[$p + 1];
$mx = int32((($z >> 5 & 0x07ffffff) ^ $y << 2) + (($y >> 3 & 0x1fffffff) ^ $z << 4)) ^ int32(($sum ^ $y) + ($k[$p & 3 ^ $e] ^ $z));
$z = $v[$p] = int32($v[$p] + $mx);
}
$y = $v[0];
$mx = int32((($z >> 5 & 0x07ffffff) ^ $y << 2) + (($y >> 3 & 0x1fffffff) ^ $z << 4)) ^ int32(($sum ^ $y) + ($k[$p & 3 ^ $e] ^ $z));
$z = $v[$n] = int32($v[$n] + $mx);
}
return long2str($v, false);
}
function xxtea_decrypt($str, $key) {
if ($str == "") {
return "";
}
$v = str2long($str, false);
$k = 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 = int32($q * $delta);
while ($sum != 0) {
$e = $sum >> 2 & 3;
for ($p = $n; $p > 0; $p--) {
$z = $v[$p - 1];
$mx = int32((($z >> 5 & 0x07ffffff) ^ $y << 2) + (($y >> 3 & 0x1fffffff) ^ $z << 4)) ^ int32(($sum ^ $y) + ($k[$p & 3 ^ $e] ^ $z));
$y = $v[$p] = int32($v[$p] - $mx);
}
$z = $v[$n];
$mx = int32((($z >> 5 & 0x07ffffff) ^ $y << 2) + (($y >> 3 & 0x1fffffff) ^ $z << 4)) ^ int32(($sum ^ $y) + ($k[$p & 3 ^ $e] ^ $z));
$y = $v[0] = int32($v[0] - $mx);
$sum = int32($sum - $delta);
}
return long2str($v, true);
}
?>