TEA、XTEA、XXTEA加解密

算法简介

TEA(Tiny Encryption Algorithm) 是一种简单高效的分组加密算法，以加密解密速度快，实现简单著称，因为其以异或和模加运算为基础，这两种运算计算机实现的效率很高。TEA算法每一次可以操作64-bit(8-byte)，采用128-bit(16-byte)作为key，算法采用迭代的形式，推荐的迭代轮数是64轮，最少32轮。

​ 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 个输入量。

TEA加密算法

​ TEA的分组长度为64位，密钥长度为128位，采用Feistel网络，建议32次循环加密即64轮。Feistel网络是一种分组密码常用的结构，其特点为明文分为等长两组，每一轮只加密一半，其安全性与密钥长度、分组长度、轮函数复杂度等有关。使用Feistel网络的密码算法，解密与加密流程类似，通常解密只需要用加密使用的硬件或者软件进行适当修改即可，提高效率降低成本。其结构如下所示：

​ TEA的加密流程图解：

​ 加解密C实现：

#include <stdio.h>
void encrypt(unsigned int* v, unsigned int* key) {
  unsigned int l = v[0], r = v[1], sum = 0, delta = 0x9e3779b9;
  for (size_t i = 0; i < 32; i++) {
    sum += delta;
    l += ((r << 4) + key[0]) ^ (r + sum) ^ ((r >> 5) + key[1]);
    r += ((l << 4) + key[2]) ^ (l + sum) ^ ((l >> 5) + key[3]);
  }
  v[0] = l;
  v[1] = r;
}
 
void decrypt(unsigned int* v, unsigned int* key) {
  unsigned int l = v[0], r = v[1], sum = 0, delta = 0x9e3779b9;
  sum = delta *32;
  for (size_t i = 0; i < 32; i++) {
    r -= ((l << 4) + key[2]) ^ (l + sum) ^ ((l >> 5) + key[3]);
    l -= ((r << 4) + key[0]) ^ (r + sum) ^ ((r >> 5) + key[1]);
    sum -= delta;
  }
  v[0] = l;
  v[1] = r;
}
//注意，这种写法是把两轮加密合为一轮来写的，所以写法与des有些不同
int main(int argc, char const *argv[])
{
    //test
    unsigned int v[2]={1,2},key[4]={1,2,3,4};
    printf("%u,%u\n",v[0],v[1]);
    encrypt(v,key);
    printf("%u,%u\n",v[0],v[1]);
    decrypt(v,key);
    printf("%u,%u\n",v[0],v[1]);
    return 0;
} 

XTEA加密算法

​ XTEA是TEA的扩展，同样是一个64位块的Feistel密码，使用128位密钥，建议64轮。

​ 加密流程图解：

​ 加解密C实现：

#include <stdio.h>
void encrypt(unsigned int* v, unsigned int* key) {
  unsigned int l = v[0], r = v[1], sum = 0, delta = 0x9e3779b9;
  for (size_t i = 0; i < 32; i++) {
    l += (((r << 4) ^ (r >> 5)) + r) ^ (sum + key[sum & 3]);
    sum += delta;
    r += (((l << 4) ^ (l >> 5)) + l) ^ (sum + key[(sum >> 11) & 3]);
  }
  v[0] = l;
  v[1] = r;
}
 
void decrypt(unsigned int* v, unsigned int* key) {
  unsigned int l = v[0], r = v[1], sum = 0, delta = 0x9e3779b9;
  sum = delta * 32;
  for (size_t i = 0; i < 32; i++) {
    r -= (((l << 4) ^ (l >> 5)) + l) ^ (sum + key[(sum >> 11) & 3]);
    sum -= delta;
    l -= (((r << 4) ^ (r >> 5)) + r) ^ (sum + key[sum & 3]);
  }
  v[0] = l;
  v[1] = r;
}
 
int main(int argc, char const *argv[])
{
    //test
    unsigned int v[2]={1,2},key[4]={1,2,3,4};
    printf("%u,%u\n",v[0],v[1]);
    encrypt(v,key);
    printf("%u,%u\n",v[0],v[1]);
    decrypt(v,key);
    printf("%u,%u\n",v[0],v[1]);
    return 0;
}

XXTEA加密算法

​ XXTEA是一个非平衡Feistel网络分组密码，在可变长度块上运行，这些块是32位大小的任意倍数（最小64位），使用128位密钥。

​ 加密流程图解：

​ 加解密C实现：

#include <stdio.h> 
#include <stdint.h> 
#define DELTA 0x9e3779b9 
#define MX (((z>>5^y<<2) + (y>>3^z<<4)) ^ ((sum^y) + (key[(p&3)^e] ^ z))) 
 
void btea(uint32_t *v, int n, uint32_t const key[4]) 
{ 
    uint32_t y, z, sum; 
    unsigned p, rounds, e; 
    if (n > 1)            /* Coding Part */ 
    { 
        rounds = 6 + 52/n; 
        sum = 0; 
        z = v[n-1]; 
        do 
        { 
            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; 
        } 
        while (--rounds); 
    } 
    else if (n < -1)      /* Decoding Part */ 
    { 
        n = -n; 
        rounds = 6 + 52/n; 
        sum = rounds*DELTA; 
        y = v[0]; 
        do 
        { 
            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; 
        } 
        while (--rounds); 
    } 
} 
 
 
int main() 
{ 
    uint32_t v[2]= {1,2}; 
    uint32_t const k[4]= {2,2,3,4}; 
    int n= 2; //n的绝对值表示v的长度，取正表示加密，取负表示解密 
    // v为要加密的数据是两个32位无符号整数 
    // k为加密解密密钥，为4个32位无符号整数，即密钥长度为128位 
    printf("加密前原始数据：%u %u\n",v[0],v[1]); 
    btea(v, n, k); 
    printf("加密后的数据：%u %u\n",v[0],v[1]); 
    btea(v, -n, k); 
    printf("解密后的数据：%u %u\n",v[0],v[1]); 
    return 0; 
}