适合单片机的加密算法之 TEA，XTEA，XXTEA！！！

TEA

TEA 的全称为"Tiny Encryption Algorithm" 是1994年由英国剑桥大学的David j.wheeler发明的。

TEA算法是一种微型加密算法。

在安全学领域，TEA 是一种分组加密算法，它的实现非常简单，通常只需要很精短的几行代码。

TEA算法使用64位的明文分组和128位的密钥，它使用Feistel分组加密框架，需要进行64轮迭代，但是作者认为32轮已经足够了，所以32轮迭代加密后最后得到的密文就是64位。

简单的说就是，TEA加密解密是以原文以8字节（64位bit）为一组，密钥16字节（128位bit）为一组，该算法加密轮次可变，作者建议为32轮，因为被加密的明文为64位，所以最终加密的结果也是64位。

该算法使用了一个神秘常数δ作为倍数，它来源于黄金比率，以保证每一轮加密都不相同。但δ的精确值似乎并不重要，这里TEA把它定义为 δ=「(√5 - 1)231」，这个δ对应的数指就是0×9E3779B9，所以这个值在TEA加密或者解密中会有用到。

从图解中可以看到运算有加法运算，位运算，异或运算。

流程1：

1、首先TEA加密解密是以原文的8字节为输入，图中所示，从两边各自传入4字节。

2、右边传入的4个字节，这里将这4个字节称呼为M，M进行了三个部分的操作，M左移4位与密钥[0]相加，M右移5位与密钥[1]相加，M与δ相加，最后这三个算出的值再异或，我们称呼 F(M)。

3、左边传入的4个字节，这里将这4个字节称呼为N，N=N+F(M)。

流程2：

接着就到了下面这个部分，这里的话M和N交换了位置。

2、右边传入的4个字节，N进行了三个部分的操作，N左移4位与密钥[2]相加，N右移5位与密钥[3]相加，N与δ相加，最后这三个算出的值再异或，这里也记为 F(N)吧。

3、左边传入的4个字节，M=M+F(N)。

4、此时拿到的M和N就是加密过后的M和N。

下面是实现的代码：

#include <stdio.h>
#include <stdint.h>
//加密函数
void encrypt (uint32_t* v, uint32_t* k) 
{
    uint32_t v0=v[0], v1=v[1], sum=0, i;           /* set up */
    uint32_t delta=0x9e3779b9;                     /* a key schedule constant */
    uint32_t k0=k[0], k1=k[1], k2=k[2], k3=k[3];   /* cache key */
    for (i=0; i < 32; i++) {                       /* basic cycle start */
        sum += delta;
        v0 += ((v1<<4) + k0) ^ (v1 + sum) ^ ((v1>>5) + k1);
        v1 += ((v0<<4) + k2) ^ (v0 + sum) ^ ((v0>>5) + k3);
    }                                              /* end cycle */
    v[0]=v0; v[1]=v1;
}
//解密函数
void decrypt (uint32_t* v, uint32_t* k)
{
    uint32_t v0=v[0], v1=v[1], sum=0xC6EF3720, i;  /* set up */
    uint32_t delta=0x9e3779b9;                     /* a key schedule constant */
    uint32_t k0=k[0], k1=k[1], k2=k[2], k3=k[3];   /* cache key */
    for (i=0; i<32; i++) {                         /* basic cycle start */
        v1 -= ((v0<<4) + k2) ^ (v0 + sum) ^ ((v0>>5) + k3);
        v0 -= ((v1<<4) + k0) ^ (v1 + sum) ^ ((v1>>5) + k1);
        sum -= delta;
    }                                              /* end cycle */
    v[0]=v0; v[1]=v1;}
int main()
{ 
   uint32_t v[2]={1,2},k[4]={2,2,3,4};
    // v为要加密的数据是两个32位无符号整数
    // k为加密解密密钥，为4个32位无符号整数，即密钥长度为128位
    printf("加密前原始数据：%u %un",v[0],v[1]);
    encrypt(v, k);
    printf("加密后的数据：%u %un",v[0],v[1]);
    decrypt(v, k);
    printf("解密后的数据：%u %un",v[0],v[1]);
    return 0;
}

重点：这个加密算法有个比较明显的特征，那就是其中的一个δ，这个数值是固定的，因此他特别容易被反编译软件识别，因此，我们可以对 TEA 做一些魔改，比如改成 0x12345678。另外，我们还可以对迭代次数做修改，比如腾讯就使用了 16 次迭代的方式。

TEA 看起来很美，但它有致命缺陷：

❌ 1. 等价密钥（Equivalent Keys）

128 bit 密钥中存在 2³² 组不同密钥 → 完全相同的加密效果，这在密码学上是不可接受的！

❌ 2. 密钥混合方式太简单

每一轮用的 k[0]~k[3] 是固定的攻击者可以利用这一点构造相关密钥攻击

XTEA

XTEA算法也被称作为Corrected Block TEA

XTEA是TEA的升级版，增加了更多的密钥表，移位和异或操作等等，设计者是Roger Needham, David Wheeler

之后 TEA 算法被发现存在缺陷，作为回应，设计者提出了一个 TEA 的升级版本——XTEA（有时也被称为"tean"）。XTEA 跟 TEA 使用了相同的简单运算，但它采用了截然不同的顺序，为了阻止密钥表攻击，四个子密钥（在加密过程中，原 128 位的密钥被拆分为 4 个 32 位的子密钥）采用了一种不太正规的方式进行混合，因此速度更慢了。

从程序中看具体的差别：

#include <stdio.h>
#include <stdint.h>
/* take 64 bits of data in v[0] and v[1] and 128 bits of key[0] - key[3] */
void encipher(unsigned int num_rounds, uint32_t v[2], uint32_t const key[4]) 
{    unsigned int i;    uint32_t v0=v[0], v1=v[1], sum=0, delta=0x9E3779B9;
    for (i=0; i < num_rounds; i++) {
        v0 += (((v1 << 4) ^ (v1 >> 5)) + v1) ^ (sum + key[sum & 3]);
        sum += delta;
        v1 += (((v0 << 4) ^ (v0 >> 5)) + v0) ^ (sum + key[(sum>>11) & 3]);
    }
    v[0]=v0; v[1]=v1;
}
void decipher(unsigned int num_rounds, uint32_t v[2], uint32_t const key[4]) 
{ 
   unsigned int i;    uint32_t v0=v[0], v1=v[1], delta=0x9E3779B9, sum=delta*num_rounds;
    for (i=0; i < num_rounds; i++) { 
       v1 -= (((v0 << 4) ^ (v0 >> 5)) + v0) ^ (sum + key[(sum>>11) & 3]);
        sum -= delta;
        v0 -= (((v1 << 4) ^ (v1 >> 5)) + v1) ^ (sum + key[sum & 3]);
    }
    v[0]=v0; v[1]=v1;
}
int main(){
    uint32_t v[2]={1,2};
    uint32_t const k[4]={2,2,3,4};
    unsigned int r=32;//num_rounds建议取值为32    // v为要加密的数据是两个32位无符号整数    
// k为加密解密密钥，为4个32位无符号整数，即密钥长度为128位
    printf("加密前原始数据：%u %un",v[0],v[1]);
    encipher(r, v, k);
    printf("加密后的数据：%u %un",v[0],v[1]);
    decipher(r, v, k);
    printf("解密后的数据：%u %un",v[0],v[1]);
    return 0;
}

从代码中可以看出，这里的 KEY 每次迭代都不同了，因为 sum 参与到了 Key 的查表。也就是每次迭代使用的 KEY 的顺序被打乱了。

到这里你会发现：

TEA / XTEA 只能加密 64 bit，也就是固定的 8 字节加密。

对数据流、结构化数据并不友好，不够 8 字节的还需要补充好。

于是有了 XXTEA（又叫 Block TEA）。

XXTEA

特点：原字符串长度可以不是4的倍数了。

首先：把数据看成一个 uint32_t 数组

其次，每一轮：

当前元素与前后元素相互搅拌

类似“环形依赖”

最后，使用同样的 delta 常数

且看代码：

#include <stdio.h>
#include <stdint.h>
#define DELTA 0x9e3779b9
static inline uint32_t xxtea_mx(uint32_t z,uint32_t y,uint32_t sum,uint32_t key)
{    
   return ((z >> 5 ^ y << 2) + (y >> 3 ^ z << 4))^ ((sum ^ y) + (key ^ z));
}
void btea(uint32_t *v, int n, const uint32_t key[4])
{    
   uint32_t y, z, sum;    unsigned p, rounds, e;
    if (n > 1)  /* 加密 */    
       {
        rounds = 6 + 52 / n;
        sum = 0;
        z = v[n - 1];
        do{
            sum += DELTA;
            e = (sum >> 2) & 3;
            for (p = 0; p < (unsigned)(n - 1); p++)
            {
                y = v[p + 1];
                z = v[p] += xxtea_mx(z, y, sum, key[(p & 3) ^ e]);
            }
            y = v[0];
            z = v[n - 1] += xxtea_mx(z, y, sum, key[(p & 3) ^ e]);
        }while (--rounds);
    }else if (n < -1) /* 解密 */    
     {
        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] -= xxtea_mx(z, y, sum, key[(p & 3) ^ e]);
            }
            z = v[n - 1];
            y = v[0] -= xxtea_mx(z, y, sum, key[(p & 3) ^ e]);
            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 %un",v[0],v[1]);
    btea(v, n, k);
    printf("加密后的数据：%u %un",v[0],v[1]);
    btea(v, -n, k);
    printf("解密后的数据：%u %un",v[0],v[1]);
    return 0;}