Tea系列算法学习

介绍

​ TEA算法是由剑桥大学计算机实验室的 David Wheeler和Roger Needham于1994年发明。 它是一种分组密码算法，其明文密文块为64比特，密钥长度为128比特。TEA算法利用不断增加的Delta(黄金分割率)值作为变化，使得每轮的加密是不同，该加密算法的迭代次数可以改变，建议的迭代次数为32轮。 （取自百度百科）

Tea算法

​ Tea算法是此系列算法中最早出现的算法之后的xtea和xxtea都是从此算法改进出来的，所以此算法的学习应该是此系列当中最简单的。

​ Tea算法使用了64位的明文分组和128位的密钥，也就是8字节的明文和16字节的密钥。通常我们见到的Tea加密算法都是加密32轮（ctf中的通常），David Wheeler和Roger Needham在设计此算法的时候是要进行64轮的迭代加密，但是大多数人都认为32位已经足够了，至于为什么，还需要等本人研究明白了再进行跟新补充。

​ 算法中使用了一个常数δ作为倍数确保每一次迭代加密都不一样，其实是不是这个常数都可以进行加密解密，但是要保证加解密使用的常数一致，否则将无法解密。

img

我之前一直没有弄明白这个图是个什么意思，查百度得出的下面的解释

田字格就是代表的加法。
圆的田字格代表的异或。

流程图分析

这张图应该从上向下看。

第一步：将8字节的密文分为4字节的两组，这里称左边的为v0，又边的是v1。

1732526073434.png

第二步：先处理了v1，有三个并列的操作：1、将v1左移四位然后与K[0]相加（这里的k是密钥）。2、将v1与常熟δ相加。3、将v1右移五位与k[1]相加。然后三个操作的值进行异或得出的结果与v0相加。

img

第三步：将处理后的v0，v1进行继续操作

img

第四步：将v0进行三个并列的操作：1、将v0左移四位然后与K[2]相加（这里的k是密钥）。2、将v0与常数δ相加。3、将v0右移五位与k[3]相加。然后三个操作的值进行异或得出的结果与v1相加。

img

第五步：进入下一次的迭代。

TEA加解密代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#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 %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;
}

我发现认真学了一下，tea好像也没什么东西，继续学xtea吧

xTea算法

xTea算法是Tea算法的一个升级，增加了运算的次数，和运算方法组合和顺序，增加了一点点理解的难度。鄙人不善言辞长话短说，短话不说，没话偏要说，那么直接从流程图分析吧。

流程图分析

先从总体来看，确实是比Tea算法多了几个步骤，but还是好理解的。

img

第一步：将8字节的密文分为4字节的两组，这里称左边的为v0，又边的是v1。

img

第二步：先处理了v1，有二个并列的操作：1、将v1左移4位。2、将v1右移5位。然后这两步的结果异或后与原始v1相加。

img

第三步，这里有个对key值选择的操作，sum&3作为索引选取对应的key，此key和δ相加然后与第二步的结果异或得出的结果与v0相加。

img

第四步，v0，v1位置交换再进行一次加密，然后下一次迭代。

XTEA加解密代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#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 %u\n",v[0],v[1]);
    encipher(r, v, k);
    printf("加密后的数据：%u %u\n",v[0],v[1]);
    decipher(r, v, k);
    printf("解密后的数据：%u %u\n",v[0],v[1]);
    return 0;
}

有点东西但不多，继续来学xxtea

xxTea算法

xxtea看起来长的就没有他的两个哥哥规矩。

特点：原字符串长度可以不是4的倍数了 。这个特点看起来就不是这么规矩。

此图需要结合代码去理解，因为硬看是看不懂的 [/乐]

img 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#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)))
//一个混淆操作，根据密码学的扩散原理，让算法更安全，同时也是xxtea的特征之一 
void xxtea(uint32_t *v, int n, uint32_t const key[4]){
    uint32_t y, z, sum;
    unsigned p, rounds, e;
    //n是明文长度，sum对应图中的D，p对应图中的密钥下标索引，e是图中的D>>2

    /* Coding Part */
    if (n > 1) {
        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;//本质上还是双整形加密,用v[p]和v[p+1]对v[p]加密
                /*
                v[p] += MX;
                z = v[p];
                */
            }
            y = v[0];
            z = v[n-1] += MX;//一轮加密的最后用v[n-1]和v[0]对v[n-1]加密
        }
        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("%#10x %#10x\n",v[0],v[1]);
    xxtea(v, n, k);//n>0为加密
    printf("%#10x %#10x\n",v[0],v[1]);
    xxtea(v, -n, k);//n<0为解密
    printf("%#10x %#10x\n",v[0],v[1]);
    return 0;
}

PS：也不知道是哪个神仙发明的算法，自学起来如此晦涩难懂。

参考链接

TEA加密算法_百度百科

TEA/XTEA/XXTEA系列算法 - zpchcbd - 博客园

[TEA XTEA XXTEA 学习笔记 | EPs1l0h’s Castle](https://eps1l0h.github.io/2021/11/04/TEA XTEA XXTEA 学习笔记/#XXTEA加密算法)