XXTEA 加密算法的概述及 Javascript 及 .net (C#) 实现

微型加密算法(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 和 C# 实现,这两种实现在字符串编码上采用的算法是一致的,因此 JavaScript 加密的内容可以用 C# 实现的解密算法进行解密,反之亦然。

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

JavaScript 版本的演示程序

/* xxtea.js
 *
 * Author:       Ma Bingyao <andot@ujn.edu.cn>
 * Copyright:    CoolCode.CN
 * Version:      1.2
 * LastModified: 2006-05-02
 * This library is free.  You can redistribute it and/or modify it.
 * http://www.coolcode.cn/?p=128
 */

function long2str(v, w) {
    var vl = v.length;
    var sl = v[vl – 1] & 0xffffffff;
    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, sl);
    }
    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);
    var n = v.length – 1;

    var z = v[n], y = v[0], delta = 0x9E3779B9;
    var mx, e, q = Math.floor(6 + 52 / (n + 1)), sum = 0;
    while (q– > 0) {
        sum = sum + delta & 0xffffffff;
        e = sum >>> 2 & 3;
        for (var 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);
    var n = v.length – 1;

    var z = v[n – 1], y = v[0], delta = 0x9E3779B9;
    var mx, e, q = Math.floor(6 + 52 / (n + 1)), sum = q * delta & 0xffffffff;
    while (sum != 0) {
        e = sum >>> 2 & 3;
        for (var 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);
}
/* xxtea.cs
 *
 * Author:       Ma Bingyao <andot@ujn.edu.cn>
 * Copyright:    CoolCode.CN
 * Version:      1.1
 * LastModified: 2006-05-05
 * This library is free.  You can redistribute it and/or modify it.
 * http://www.coolcode.cn/?p=163
 */

using System;

class XXTEA
{
    public static Byte[] Encrypt(Byte[] Data, Byte[] Key)
    {
        if (Data.Length == 0)
        {
            return Data;
        }
        return ToByteArray(Encrypt(ToUInt32Array(Data, true), ToUInt32Array(Key, false)), false);
    }
    public static Byte[] Decrypt(Byte[] Data, Byte[] Key)
    {
        if (Data.Length == 0)
        {
            return Data;
        }
        return ToByteArray(Decrypt(ToUInt32Array(Data, false), ToUInt32Array(Key, false)), true);
    }

    public static UInt32[] Encrypt(UInt32[] v, UInt32[] k)
    {
        Int32 n = v.Length – 1;
        if (n < 1)
        {
            return v;
        }
        if (k.Length < 4)
        {
            UInt32[] Key = new UInt32[4];
            k.CopyTo(Key, 0);
            k = Key;
        }
        UInt32 z = v[n], y = v[0], delta = 0x9E3779B9, sum = 0, e;
        Int32 p, q = 6 + 52 / (n + 1);
        while (q– > 0)
        {
            sum = unchecked(sum + delta);
            e = sum >> 2 & 3;
            for (p = 0; p < n; p++)
            {
                y = v[p + 1];
                z = unchecked(v[p] += (z >> 5 ^ y << 2) + (y >> 3 ^ z << 4) ^ (sum ^ y) + (k[p & 3 ^ e] ^ z));
            }
            y = v[0];
            z = unchecked(v[n] += (z >> 5 ^ y << 2) + (y >> 3 ^ z << 4) ^ (sum ^ y) + (k[p & 3 ^ e] ^ z));
        }
        return v;
    }
    public static UInt32[] Decrypt(UInt32[] v, UInt32[] k)
    {
        Int32 n = v.Length – 1;
        if (n < 1)
        {
            return v;
        }
        if (k.Length < 4)
        {
            UInt32[] Key = new UInt32[4];
            k.CopyTo(Key, 0);
            k = Key;
        }
        UInt32 z = v[n], y = v[0], delta = 0x9E3779B9, sum, e;
        Int32 p, q = 6 + 52 / (n + 1);
        sum = unchecked((UInt32)(q * delta));
        while (sum != 0)
        {
            e = sum >> 2 & 3;
            for (p = n; p > 0; p–)
            {
                z = v[p – 1];
                y = unchecked(v[p] -= (z >> 5 ^ y << 2) + (y >> 3 ^ z << 4) ^ (sum ^ y) + (k[p & 3 ^ e] ^ z));
            }
            z = v[n];
            y = unchecked(v[0] -= (z >> 5 ^ y << 2) + (y >> 3 ^ z << 4) ^ (sum ^ y) + (k[p & 3 ^ e] ^ z));
            sum = unchecked(sum – delta);
        }
        return v;
    }
    private static UInt32[] ToUInt32Array(Byte[] Data, Boolean IncludeLength)
    {
        Int32 n = (((Data.Length & 3) == 0) ? (Data.Length >> 2) : ((Data.Length >> 2) + 1));
        UInt32[] Result;
        if (IncludeLength)
        {
            Result = new UInt32[n + 1];
            Result[n] = (UInt32)Data.Length;
        }
        else
        {
            Result = new UInt32[n];
        }
        n = Data.Length;
        for (Int32 i = 0; i < n; i++)
        {
            Result[i >> 2] |= (UInt32)Data[i] << ((i & 3) << 3);
        }
        return Result;
    }
    private static Byte[] ToByteArray(UInt32[] Data, Boolean IncludeLength)
    {
        Int32 n;
        if (IncludeLength)
        {
            n = (Int32)Data[Data.Length – 1];
        }
        else
        {
            n = Data.Length << 2;
        }
        Byte[] Result = new Byte[n];
        for (Int32 i = 0; i < n; i++)
        {
            Result[i] = (Byte)(Data[i >> 2] >> ((i & 3) << 3));
        }
        return Result;
    }
}

 

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

JavaScript Implementation of Block TEA Tiny Encryption Algorithm

JavaScript Encryption Library

JavaScript Implementation of Block TEA Tiny Encryption Algorithm

TEA Encryption Algorithm (pascal)

 

本文来自CSDN博客,转载请标明出处:http://blog.csdn.net/thinmichael/archive/2006/05/23/751905.aspx

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注