TEA家族详解
TEA
TEA 的全称是“Tiny Encryption Algorithm”，1994年由英国剑桥大学的David j.wheeler发明的一种微型分组加密算法。该算法实现非常简单，通常只需要很精简的十几行代码，它的分组长度为 64 bit，密钥长度为 128 bit，采用 32 轮的 Feistel 结构。
算法原理
TEA 算法比较简单，没有子密钥生成算法，每一轮的 Feistel 结构也简单明了，采用的 ARX 计算也非常简单，值得注意的是 TEA 算法中有一个源于黄金分割比的魔数 0x9E3779B9，故不多分析，直接上 C 语言实现代码：
#include <stdint.h>
void encrypt (uint32_t v[2], const uint32_t k[4]) {
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[2], const uint32_t k[4]) {
uint32_t v0=v[0], v1=v[1], sum=0xC6EF3720, i; /* set up; sum is (delta << 5) & 0xFFFFFFFF */
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;
}
XTEA
XTEA 算法是 TEA 算法的改进版本，主要修改了 Feistel 结构中的 ARX 计算和密钥的使用顺序，由于改变不大，故不多解释，直接上源码：
#include <stdint.h>
/* take 64 bits of data in v[0] and v[1] and 128 bits of key[0] - key[3] */
void encrypt(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 decrypt(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;
}
XXTEA
XXTEA 算法为前两代 TEA 家族算法的改进型，拥有更复杂的非平衡 feistel 结构，更灵活的加密块大小（至少为 64 bit）。源码如下：
#include <stdint.h>
#define DELTA 0x9e3779b9
#define MX (((z>>5^y<<2) + (y>>3^z<<4)) ^ ((sum^y) + (key[(p&3)^e] ^ z)))
void xxtea(uint32_t *v, int n, uint32_t const key[4]) {
uint32_t y, z, sum;
unsigned p, rounds, e;
if (n > 1) { /* Encrypt Part */
rounds = 6 + 52/n; /* calculate rounds */
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) { /* Decrypt 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);
}
}
是不是看起来和前两代差距很大，感觉像一个全新的算法。上面那个源码之所以看起来变化很大，主要是为了满足可变加密块大小做出的改变。如果将加密块大小固定为熟悉的 64 bit，上面的算法可以简化为：
#include <stdint.h>
void encrypt (uint32_t v[2], const uint32_t k[4]) {
uint32_t v0=v[0], v1=v[1], sum=0, i, e; /* set up */
uint32_t delta=0x9E3779B9; /* a key schedule constant */
for (i=0; i<32; i++) { /* basic cycle start */
sum += delta;
e = (sum >> 2) & 3;
v0 += (((v1>>5 ^ v1<<2) + (v1>>3 ^ v1<<4)) ^ ((sum ^ v1) + (k[e] ^ v1)));
v1 += (((v0>>5 ^ v0<<2) + (v0>>3 ^ v0<<4)) ^ ((sum ^ v0) + (k[e^1] ^ v0)));
} /* end cycle */
v[0]=v0; v[1]=v1;
}
void decrypt (uint32_t v[2], const uint32_t k[4]) {
uint32_t v0=v[0], v1=v[1], sum=0xC6EF3720, i, e; /* set up; sum is (delta << 5) & 0xFFFFFFFF */
uint32_t delta=0x9E3779B9; /* a key schedule constant */
for (i=0; i<32; i++) { /* basic cycle start */
e = (sum >> 2) & 3;
v1 -= (((v0>>5 ^ v0<<2) + (v0>>3 ^ v0<<4)) ^ ((sum ^ v0) + (k[e^1] ^ v0)));
v0 -= (((v1>>5 ^ v1<<2) + (v1>>3 ^ v1<<4)) ^ ((sum ^ v1) + (k[e] ^ v1)));
sum -= delta;
} /* end cycle */
v[0]=v0; v[1]=v1;
}
这个看着是不是顺眼多了。顺便附上正确性验证代码：
nt main(int argc, char** argv)
{
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]);
xxtea(v, n, k);
printf("加密后的数据：%u %u\n",v[0],v[1]);
xxtea(v, -n, k);
printf("解密后的数据：%u %u\n",v[0],v[1]);
encrypt(v, k);
printf("加密后的数据：%u %u\n",v[0],v[1]);
decrypt(v, k);
printf("解密后的数据：%u %u\n",v[0],v[1]);
return 0;
}