TEA，XTEA，XXTEA加密算法概要

字数统计: 2.1k字   |   阅读时长≈ 11分

记录一下TEA加密算法

TEA，XTEA，XXTEA加密算法概要

1. TEA

1.1 概要

在密码学中，微型加密算法（Tiny Encryption Algorithm，TEA）是一种易于描述和执行的块密码，通常只需要很少的代码就可实现。其设计者是剑桥大学计算机实验室的大卫·惠勒与罗杰·尼达姆。这项技术最初于1994年提交给鲁汶的快速软件加密的研讨会上，并在该研讨会上演讲中首次发表。

1.2 属性

待加密数据：64位，2个4字节无符号整数

密钥：128位，4个4字节的无符号整数

delta：通常为0x9e3779b9

轮数：建议为32次

TEA_InfoBox_Diagram

1.3 源码

1.3.1 C语言版本（原生）

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
#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]={1,2,3,4};
    // v为要加密的数据是两个32位无符号整数
    // k为加密解密密钥，为4个32位无符号整数，即密钥长度为128位
    printf("Before enc:  %#x %#x\n",v[0],v[1]);
    encrypt(v, k);
    printf("After  enc:  %#x %#x\n",v[0],v[1]);
    decrypt(v, k);
    printf("After  dec:  %#x %#x\n",v[0],v[1]);
    return 0;
}

1.3.2 Python版本（我自己改编的）

注：调用ctypes模块模拟C风格整数

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
from ctypes import *

def encrypt(v, k):
    v0 = c_uint32(v[0])
    v1 = c_uint32(v[1])
    summ = c_uint32(0)
    delta = 0x9e3779b9

    k0, k1, k2, k3 = c_uint32(k[0]), c_uint32(k[1]), c_uint32(k[2]), c_uint32(k[3])
    
    print("%#x %#x" % (v0.value, v1.value))
    print("%#x %#x %#x %#x" % (k0.value, k1.value, k2.value, k3.value))

    w = [0,0]
    for i in range(32):
        summ.value += delta
        v0.value += ((v1.value << 4) + k0.value) ^ (v1.value + summ.value) ^ ((v1.value >> 5) + k1.value)
        v1.value += ((v0.value << 4) + k2.value) ^ (v0.value + summ.value) ^ ((v0.value >> 5) + k3.value)
    w[0], w[1] = v0, v1
    return w

def decrypt(v, k):
    v0 = c_uint32(v[0])
    v1 = c_uint32(v[1])
    summ = c_uint32(0xC6EF3720)
    delta = 0x9e3779b9

    k0, k1, k2, k3 = c_uint32(k[0]), c_uint32(k[1]), c_uint32(k[2]), c_uint32(k[3])
    
    print("%#x %#x" % (v0.value, v1.value))
    print("%#x %#x %#x %#x" % (k0.value, k1.value, k2.value, k3.value))

    w = [0,0]
    for i in range(32):
        v1.value -= ((v0.value << 4) + k2.value) ^ (v0.value + summ.value) ^ ((v0.value >> 5) + k3.value)
        v0.value -= ((v1.value << 4) + k0.value) ^ (v1.value + summ.value) ^ ((v1.value >> 5) + k1.value)
        summ.value -= delta
    w[0], w[1] = v0, v1
    return w


v = [1,2]
k = [1,2,3,4]
ret = encrypt(v,k)
print("%#x %#x" % (ret[0].value, ret[1].value))
enc = [0xf99e87a6, 0xa5b88bf3]
dec = decrypt(enc,k)
print("%#x %#x" % (dec[0].value, dec[1].value))


1.4 CTF竞赛中的应用

1.4.1 出题方式

  1. 直接C语言算法
  2. 特殊：使用特殊大数计算函数（ADD，SUB，MUL，XOR，ROL，ROR等），模拟SSA风格的计算方式
  3. 改变加密轮数或delta的值，变体TEA
  4. delta的值不直接给，而是先拆成两个数字，然后在异或后得到delta，来防止被FindCrypt直接检测到

1.4.2 识别方式

  1. 简单的直接FindCrypt直接发现
  2. 识别特征值，4和5同时出现时要注意

2. XTEA

2.1 概要

升级版本的TEA算法

2.2 属性

待加密数据：64位，2个4字节无符号整数

密钥：128位，4个4字节的无符号整数

delta：通常为0x9e3779b9

2.3 源码

2.3.1 C语言

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
#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 encrypt(unsigned int num_rounds, uint32_t v[2], uint32_t key[4]){
    uint32_t v0=v[0], v1=v[1], sum=0, delta=0x9e3779b9;

    for(int 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]);
        //printf("%#x %#x\n",v0,v1);
    }
    v[0] = v0;
    v[1] = v1;
}


void decrypt(unsigned int num_rounds, uint32_t v[2], uint32_t key[4]){
    uint32_t v0=v[0], v1=v[1], delta=0x9e3779b9, sum=delta*num_rounds;
    for(int 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(void){
    uint32_t v[2]={1,2};
    uint32_t k[4]={1,2,3,4};
    unsigned int r=32;//num_rounds建议取值为32
    // v为要加密的数据是两个32位无符号整数
    // k为加密解密密钥，为4个32位无符号整数，即密钥长度为128位
    printf("%#x %#x\n",v[0],v[1]);
    encrypt(r, v, k);
    printf("%#x %#x\n",v[0],v[1]);
    decrypt(r, v, k);
    printf("%#x %#x\n",v[0],v[1]);
    return 0;
}

2.3.2 Python

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
import sys
import os
from ctypes import *

def encrypt(num_rounds, v, key):
    v0, v1 = c_uint32(v[0]), c_uint32(v[1])
    summ = c_uint32(0)
    delta = 0x9e3779b9

    #print("%#10x %#10x" % (v0.value, v1.value))
    #print("%#10x" % (summ.value))

    for i in range(num_rounds):
        v0.value += (((v1.value << 4) ^ (v1.value >> 5)) + v1.value) ^ (summ.value + key[summ.value & 3])
        summ.value += delta
        v1.value += (((v0.value << 4) ^ (v0.value >> 5)) + v0.value) ^ (summ.value + key[(summ.value>>11) & 3])
        #print("%#10x %#10x" % (v0.value, v1.value))
    w = [v0.value, v1.value]
    return w

def decrypt(num_rounds, v, key):
    v0, v1 = c_uint32(v[0]), c_uint32(v[1])
    delta = 0x9e3779b9
    summ = c_uint32(delta*num_rounds)

    print("%#10x %#10x" % (v0.value, v1.value))

    for i in range(num_rounds):
        v1.value -= (((v0.value << 4) ^ (v0.value >> 5)) + v0.value) ^ (summ.value + key[(summ.value>>11)&3])
        summ.value -= delta
        v0.value -= (((v1.value << 4) ^ (v1.value >> 5)) + v1.value) ^ (summ.value + key[summ.value & 3])

    w = [v0.value, v1.value]
    return w

v = [1,2]
k = [1,2,3,4]

ret = encrypt(32,v,k)
print("%#x %#x" % (ret[0], ret[1]))
enc = [0xf4420bdd, 0xd58bca18]
dec = decrypt(32,enc,k)
print("%#x %#x" % (dec[0], dec[1]))

3. XXTEA

3.1 概要

XXTEA是一个非平衡Feistel网络分组密码，在可变长度块上运行，这些块是32位大小的任意倍数（最小64位），使用128位密钥, 是目前TEA系列中最安全的算法，但性能较上两种有所降低。

3.2 属性

XXTEA

3.3 实现

3.3.1 C语言原生实现

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
#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;

    /* 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;
            }
            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("%#10x %#10x\n",v[0],v[1]);
    btea(v, n, k);
    printf("%#10x %#10x\n",v[0],v[1]);
    btea(v, -n, k);
    printf("%#10x %#10x\n",v[0],v[1]);
    return 0;
}

3.3.2 Python实现

可以考虑直接编译C文件后得到dll文件或者so等库文件，用ctypes加载后使用。

3.4 调用现成模块

GitHub上面有很多现成的XXTEA模块，可以直接使用。

3.4.1 Python

3.4.1.1 安装模块
1
pip install xxtea-py
3.4.1.2 使用

Python2:

1
2
3
4
5
6
import xxtea
text = "Hello World! 你好，中国！"
key = "1234567890"
encrypt_data = xxtea.encrypt(text, key)
decrypt_data = xxtea.decrypt(encrypt_data, key)
print(text == decrypt_data);

Python3:

1
2
3
4
5
6
import xxtea
text = "Hello World! 你好，中国！"
key = "1234567890"
encrypt_data = xxtea.encrypt(text, key)
decrypt_data = xxtea.decrypt_utf8(encrypt_data, key)
print(text == decrypt_data);

4. 参考资料

https://github.com/xxtea/xxtea-java

https://github.com/xxtea/xxtea-python

https://blog.csdn.net/MakerCloud/article/details/107454777

https://www.jianshu.com/p/4272e0805da3

https://zh.wikipedia.org/wiki/%E5%BE%AE%E5%9E%8B%E5%8A%A0%E5%AF%86%E7%AE%97%E6%B3%95

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia-plus根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

A junior undergraduate
studying in the college of cyber science and engineering
in Sichuan University
in Sichuan , China.
Pronouns:He/him.
A core member of 0x401 CTF team
majorly focus on Reverse Engineering chanllenges.