tea系列加密算法学习笔记概述tea算法xtea算法xxtea算法总结

125 阅读 0 评论 83 点赞

我是靠谱客的博主想人陪黑夜，这篇文章主要介绍tea系列加密算法学习笔记概述tea算法xtea算法xxtea算法总结，现在分享给大家，希望可以做个参考。

tea系列加密算法

概述
tea算法
xtea算法
xxtea算法
总结

概述

最近在做ctf逆向的题目中多次遇到了该算法，因此打算重写一篇完整的博客来详细学习下该算法。
TEA（Tiny Encryption Algorithm），是一种分组加密算法，实现过程比较简单，从其名字也能看出这是一种微型的加密算法，效率极高。该系列一共有三种算法，tea --> xtea --> xxtea，从右往左依次是前面的升级版。此系列算法都使用了一个神秘常数作为倍数，源于黄金比率，程序中一般写作0x9E3779B9。但有时该常数会以减法的形式出现，-0x61C88647=0x9E3779B9，因此出现了0x61C88647该常数时也应当注意。
下面会依次介绍三种算法的官方c语言实现，代码中均使用64bit(8byte)的明文作为加密数据，采用128bit(16byte)的值作为key，算法采用迭代的形式，推荐的迭代轮数是64轮，最少32轮，这里采用32轮。当然在实际题目中可能会对算法轮次等做一些魔改，不过问题不大，按照已经学习过的算法思路去理解也能很快写出求解算法。
PS：这里是python实现该三种算法的链接 – python实现tea/xtea/xxtea加密算法。

tea算法

实现代码如下，主体逻辑是用异或实现的，加密和解密是两个逆向操作，相关细节我已经标注在代码中了。值得说明一下的就是，加密算法中主体变量都是用32位无符号整型实现的，这意味其实算法运行过程中肯定是有溢出的，但是只保留低32位。

复制代码

#include <stdio.h>
#include <stdint.h>

void encrypt (uint32_t* v, uint32_t* k) {
    uint32_t sum = 0;  // 注意sum也是32位无符号整型
    uint32_t v0 = v[0], v1 = v[1];
    uint32_t delta = 0x9e3779b9;
    uint32_t k0 = k[0], k1 = k[1], k2 = k[2], k3 = k[3];

for (int i=0; i<32; i++) {
        sum += delta;
        v0 += ((v1<<4) + k0) ^ (v1 + sum) ^ ((v1>>5) + k1);
        v1 += ((v0<<4) + k2) ^ (v0 + sum) ^ ((v0>>5) + k3);
    }

v[0]=v0; 
    v[1]=v1;
}

void decrypt (uint32_t* v, uint32_t* k) {
    uint32_t v0 = v[0], v1 = v[1];
    uint32_t delta = 0x9e3779b9;
    uint32_t sum = delta * 32;
    uint32_t k0 = k[0], k1 = k[1], k2 = k[2], k3 = k[3];

for (int i=0; i<32; i++) {
        v1 -= ((v0<<4) + k2) ^ (v0 + sum) ^ ((v0>>5) + k3);
        v0 -= ((v1<<4) + k0) ^ (v1 + sum) ^ ((v1>>5) + k1);
        sum -= delta;
    }

v[0]=v0; 
    v[1]=v1;
}

// test
int main()
{
    // 两个32位无符号整数，即待加密的64bit明文数据
    uint32_t v[2] = {0x12345678, 0x78563412};
    // 四个32位无符号整数，即128bit的key
    uint32_t k[4]= {0x1, 0x2, 0x3, 0x4};

printf("Data is : %x %xn", v[0], v[1]);
    encrypt(v, k);
    printf("Encrypted data is : %x %xn", v[0], v[1]);
    decrypt(v, k);
    printf("Decrypted data is : %x %xn", v[0], v[1]);

return 0;
}
/*
Data is : 12345678 78563412
Encrypted data is : 9a65a69a 67ed00f6
Decrypted data is : 12345678 78563412
*/

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
#include <stdio.h>
#include <stdint.h>


void encrypt (uint32_t* v, uint32_t* k) {
    uint32_t sum = 0;  // 注意sum也是32位无符号整型
    uint32_t v0 = v[0], v1 = v[1];
    uint32_t delta = 0x9e3779b9;
    uint32_t k0 = k[0], k1 = k[1], k2 = k[2], k3 = k[3];

    for (int i=0; i<32; i++) {
        sum += delta;
        v0 += ((v1<<4) + k0) ^ (v1 + sum) ^ ((v1>>5) + k1);
        v1 += ((v0<<4) + k2) ^ (v0 + sum) ^ ((v0>>5) + k3);
    }

    v[0]=v0; 
    v[1]=v1;
}

void decrypt (uint32_t* v, uint32_t* k) {
    uint32_t v0 = v[0], v1 = v[1];
    uint32_t delta = 0x9e3779b9;
    uint32_t sum = delta * 32;
    uint32_t k0 = k[0], k1 = k[1], k2 = k[2], k3 = k[3];

    for (int i=0; i<32; i++) {
        v1 -= ((v0<<4) + k2) ^ (v0 + sum) ^ ((v0>>5) + k3);
        v0 -= ((v1<<4) + k0) ^ (v1 + sum) ^ ((v1>>5) + k1);
        sum -= delta;
    }

    v[0]=v0; 
    v[1]=v1;
}

// test
int main()
{
    // 两个32位无符号整数，即待加密的64bit明文数据
    uint32_t v[2] = {0x12345678, 0x78563412};
    // 四个32位无符号整数，即128bit的key
    uint32_t k[4]= {0x1, 0x2, 0x3, 0x4};

    printf("Data is : %x %xn", v[0], v[1]);
    encrypt(v, k);
    printf("Encrypted data is : %x %xn", v[0], v[1]);
    decrypt(v, k);
    printf("Decrypted data is : %x %xn", v[0], v[1]);

    return 0;
}
/*
Data is : 12345678 78563412
Encrypted data is : 9a65a69a 67ed00f6
Decrypted data is : 12345678 78563412
*/

xtea算法

实现代码如下，xtea是tea的升级版，可以看到变量类型处理和tea一样，主要是加密逻辑有所变化，对每轮加密的key的选择也有所变化。

复制代码

#include <stdio.h>
#include <stdint.h>

void encrypt(uint32_t* v, uint32_t* key) {
    uint32_t v0 = v[0], v1 = v[1];
    uint32_t sum = 0, delta = 0x9E3779B9;

for (int i=0; i<32; 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(uint32_t* v, uint32_t* key) {
    uint32_t v0 = v[0], v1 = v[1];
    uint32_t delta = 0x9E3779B9;
    uint32_t sum = delta * 32;

for (int i=0; i<32; 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;
}

printf("Data is : %x %xn", v[0], v[1]);
    encrypt(v, k);
    printf("Encrypted data is : %x %xn", v[0], v[1]);
    decrypt(v, k);
    printf("Decrypted data is : %x %xn", v[0], v[1]);

return 0;
}
/*
Data is : 12345678 78563412
Encrypted data is : ae685ec7 59af4238
Decrypted data is : 12345678 78563412
*/

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
#include <stdio.h>
#include <stdint.h>


void encrypt(uint32_t* v, uint32_t* key) {
    uint32_t v0 = v[0], v1 = v[1];
    uint32_t sum = 0, delta = 0x9E3779B9;

    for (int i=0; i<32; 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(uint32_t* v, uint32_t* key) {
    uint32_t v0 = v[0], v1 = v[1];
    uint32_t delta = 0x9E3779B9;
    uint32_t sum = delta * 32;

    for (int i=0; i<32; 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;
}

// test
int main()
{
    // 两个32位无符号整数，即待加密的64bit明文数据
    uint32_t v[2] = {0x12345678, 0x78563412};
    // 四个32位无符号整数，即128bit的key
    uint32_t k[4]= {0x1, 0x2, 0x3, 0x4};

    printf("Data is : %x %xn", v[0], v[1]);
    encrypt(v, k);
    printf("Encrypted data is : %x %xn", v[0], v[1]);
    decrypt(v, k);
    printf("Decrypted data is : %x %xn", v[0], v[1]);

    return 0;
}
/*
Data is : 12345678 78563412
Encrypted data is : ae685ec7 59af4238
Decrypted data is : 12345678 78563412
*/

xxtea算法

实现代码如下，xxtea是xtea算法的升级版，可以看到其实现过程比前两种算法要略显复杂些，加密的明文数据可以不再是64bit（两个32位无符号整数），并且其加密轮数是由n即待加密数据个数决定的。

复制代码

#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 xxtea(uint32_t* v, int n, uint32_t* key)
{
    uint32_t y, z, sum;
    unsigned p, rounds, e;

if (n > 1)             // encrypt
    {
        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)      // decrypt
    {
        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);
    }
}

// test
int main()
{
    // 两个32位无符号整数，即待加密的64bit明文数据
    uint32_t v[2] = {0x12345678, 0x78563412};
    // 四个32位无符号整数，即128bit的key
    uint32_t k[4]= {0x1, 0x2, 0x3, 0x4};
    //n的绝对值表示v的长度，取正表示加密，取负表示解密
    int n = 2;

printf("Data is : %x %xn", v[0], v[1]);
    xxtea(v, n, k);
    printf("Encrypted data is : %x %xn", v[0], v[1]);
    xxtea(v, -n, k);
    printf("Decrypted data is : %x %xn", v[0], v[1]);

return 0;
}
/*
Data is : 12345678 78563412
Encrypted data is : ef86c2bb 25f31b5e
Decrypted data is : 12345678 78563412
*/

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#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 xxtea(uint32_t* v, int n, uint32_t* key)
{
    uint32_t y, z, sum;
    unsigned p, rounds, e;

    if (n > 1)             // encrypt
    {
        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)      // decrypt
    {
        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);
    }
}

// test
int main()
{
    // 两个32位无符号整数，即待加密的64bit明文数据
    uint32_t v[2] = {0x12345678, 0x78563412};
    // 四个32位无符号整数，即128bit的key
    uint32_t k[4]= {0x1, 0x2, 0x3, 0x4};
    //n的绝对值表示v的长度，取正表示加密，取负表示解密
    int n = 2;

    printf("Data is : %x %xn", v[0], v[1]);
    xxtea(v, n, k);
    printf("Encrypted data is : %x %xn", v[0], v[1]);
    xxtea(v, -n, k);
    printf("Decrypted data is : %x %xn", v[0], v[1]);

    return 0;
}
/*
Data is : 12345678 78563412
Encrypted data is : ef86c2bb 25f31b5e
Decrypted data is : 12345678 78563412
*/