TEA加密算法的C/C++实现 - 数据结构/算法

TEA(Tiny Encryption Algorithm) 是一种简单高效的加密算法，以加密解密速度快，实现简单著称。算法真的很简单，TEA算法每一次可以操作64-bit(8-byte)，采用128-bit(16-byte)作为key，算法采用迭代的形式，推荐的迭代轮数是64轮，最少32轮。目前我只知道QQ一直用的是16轮TEA。没什么好说的，先给出C语言的源代码(默认是32轮)：

1 void encrypt(unsigned long *v, unsigned long *k) {
2     unsigned long y=v[0], z=v[1], sum=0, i;         /* set up */
3     unsigned long delta=0x9e3779b9;                 /* a key schedule constant */
4     unsigned long a=k[0], b=k[1], c=k[2], d=k[3];   /* cache key */
5     for (i=0; i < 32; i++) {                        /* basic cycle start */
6         sum += delta;
7         y += ((z<<4) + a) ^ (z + sum) ^ ((z>>5) + b);
8         z += ((y<<4) + c) ^ (y + sum) ^ ((y>>5) + d);/* end cycle */
9     }
10     v[0]=y;
11     v[1]=z;
12 }
13
14 void decrypt(unsigned long *v, unsigned long *k) {
15     unsigned long y=v[0], z=v[1], sum=0xC6EF3720, i; /* set up */
16     unsigned long delta=0x9e3779b9;                  /* a key schedule constant */
17     unsigned long a=k[0], b=k[1], c=k[2], d=k[3];    /* cache key */
18     for(i=0; i<32; i++) {                            /* basic cycle start */
19         z -= ((y<<4) + c) ^ (y + sum) ^ ((y>>5) + d);
20         y -= ((z<<4) + a) ^ (z + sum) ^ ((z>>5) + b);
21         sum -= delta;                                /* end cycle */
22     }
23     v[0]=y;
24     v[1]=z;
25 }

C语言写的用起来当然不方便，没关系，用C++封装以下就OK了：
util.h

1 #ifndef UTIL_H
2 #define UTIL_H
3
4 #include <string>
5 #include <cmath>
6 #include <cstdlib>
7
8 typedef unsigned char byte;
9 typedef unsigned long ulong;
10
11 inline double logbase(double base, double x) {
12 return log(x)/log(base);
13 }
14
15 /*
16 *convert int to hex char.
17 *example:10 -> 'A',15 -> 'F'
18 */
19 char intToHexChar(int x);
20
21 /*
22 *convert hex char to int.
23 *example:'A' -> 10,'F' -> 15
24 */
25 int hexCharToInt(char hex);
26
27 using std::string;
28 /*
29 *convert a byte array to hex string.
30 *hex string format example:"AF B0 80 7D"
31 */
32 string bytesToHexString(const byte *in, size_t size);
33
34 /*
35 *convert a hex string to a byte array.
36 *hex string format example:"AF B0 80 7D"
37 */
38 size_t hexStringToBytes(const string &str, byte *out);
39
40 #endif/*UTIL_H*/

util.cpp

1 #include "util.h"
2 #include <vector>
3
4 using namespace std;
5
6 char intToHexChar(int x) {
7     static const char HEX[16] = {
8         '0', '1', '2', '3',
9         '4', '5', '6', '7',
10         '8', '9', 'A', 'B',
11         'C', 'D', 'E', 'F'
12     };
13     return HEX[x];
14 }
15
16 int hexCharToInt(char hex) {
17     hex = toupper(hex);
18     if (isdigit(hex))
19         return (hex - '0');
20     if (isalpha(hex))
21         return (hex - 'A' + 10);
22     return 0;
23 }
24
25 string bytesToHexString(const byte *in, size_t size) {
26     string str;
27     for (size_t i = 0; i < size; ++i) {
28         int t = in[i];
29         int a = t / 16;
30         int b = t % 16;
31         str.append(1, intToHexChar(a));
32         str.append(1, intToHexChar(b));
33         if (i != size - 1)
34             str.append(1, ' ');
35     }
36     return str;
37 }
38
39 size_t hexStringToBytes(const string &str, byte *out) {
40
41     vector<string> vec;
42     string::size_type currPos = 0, prevPos = 0;
43     while ((currPos = str.find(' ', prevPos)) != string::npos) {
44         string b(str.substr(prevPos, currPos - prevPos));
45         vec.push_back(b);
46         prevPos = currPos + 1;
47     }
48     if (prevPos < str.size()) {
49         string b(str.substr(prevPos));
50         vec.push_back(b);
51     }
52     typedef vector<string>::size_type sz_type;
53     sz_type size = vec.size();
54     for (sz_type i = 0; i < size; ++i) {
55         int a = hexCharToInt(vec[i][0]);
56         int b = hexCharToInt(vec[i][1]);
57         out[i] = a * 16 + b;
58     }
59     return size;
60 }

tea.h

1 #ifndef TEA_H
2 #define TEA_H
3
4 /*
5 *for htonl,htonl
6 *do remember link "ws2_32.lib"
7 */
8 #include <winsock2.h>
9 #include "util.h"
10
11 class TEA {
12 public:
13     TEA(const byte *key, int round = 32, bool isNetByte = false);
14     TEA(const TEA &rhs);
15     TEA& operator=(const TEA &rhs);
16     void encrypt(const byte *in, byte *out);
17     void decrypt(const byte *in, byte *out);
18 private:
19     void encrypt(const ulong *in, ulong *out);
20     void decrypt(const ulong *in, ulong *out);
21     ulong ntoh(ulong netlong) { return _isNetByte ? ntohl(netlong) : netlong; }
22     ulong hton(ulong hostlong) { return _isNetByte ? htonl(hostlong) : hostlong; }
23 private:
24     int _round; //iteration round to encrypt or decrypt
25     bool _isNetByte; //whether input bytes come from network
26     byte _key[16]; //encrypt or decrypt key
27 };
28
29 #endif/*TEA_H*/

tea.cpp

1 #include "tea.h"
2 #include <cstring> //for memcpy,memset
3
4 using namespace std;
5
6 TEA::TEA(const byte *key, int round /*= 32*/, bool isNetByte /*= false*/)
7 :_round(round)
8 ,_isNetByte(isNetByte) {
9     if (key != 0)
10         memcpy(_key, key, 16);
11     else
12         memset(_key, 0, 16);
13 }
14
15 TEA::TEA(const TEA &rhs)
16 :_round(rhs._round)
17 ,_isNetByte(rhs._isNetByte) {
18     memcpy(_key, rhs._key, 16);
19 }
20
21 TEA& TEA::operator=(const TEA &rhs) {
22     if (&rhs != this) {
23         _round = rhs._round;
24         _isNetByte = rhs._isNetByte;
25         memcpy(_key, rhs._key, 16);
26     }
27     return *this;
28 }
29
30 void TEA::encrypt(const byte *in, byte *out) {
31     encrypt((const ulong*)in, (ulong*)out);
32 }
33
34 void TEA::decrypt(const byte *in, byte *out) {
35     decrypt((const ulong*)in, (ulong*)out);
36 }
37
38 void TEA::encrypt(const ulong *in, ulong *out) {
39
40     ulong *k = (ulong*)_key;
41     register ulong y = ntoh(in[0]);
42     register ulong z = ntoh(in[1]);
43     register ulong a = ntoh(k[0]);
44     register ulong b = ntoh(k[1]);
45     register ulong c = ntoh(k[2]);
46     register ulong d = ntoh(k[3]);
47     register ulong delta = 0x9E3779B9; /* (sqrt(5)-1)/2*2^32 */
48     register int round = _round;
49     register ulong sum = 0;
50
51     while (round--) {    /* basic cycle start */
52         sum += delta;
53         y += ((z << 4) + a) ^ (z + sum) ^ ((z >> 5) + b);
54         z += ((y << 4) + c) ^ (y + sum) ^ ((y >> 5) + d);
55     }    /* end cycle */
56     out[0] = ntoh(y);
57     out[1] = ntoh(z);
58 }
59
60 void TEA::decrypt(const ulong *in, ulong *out) {
61
62     ulong *k = (ulong*)_key;
63     register ulong y = ntoh(in[0]);
64     register ulong z = ntoh(in[1]);
65     register ulong a = ntoh(k[0]);
66     register ulong b = ntoh(k[1]);
67     register ulong c = ntoh(k[2]);
68     register ulong d = ntoh(k[3]);
69     register ulong delta = 0x9E3779B9; /* (sqrt(5)-1)/2*2^32 */
70     register int round = _round;
71     register ulong sum = 0;
72
73     if (round == 32)
74         sum = 0xC6EF3720; /* delta << 5*/
75     else if (round == 16)
76         sum = 0xE3779B90; /* delta << 4*/
77     else
78         sum = delta << static_cast<int>(logbase(2, round));
79
80     while (round--) {    /* basic cycle start */
81         z -= ((y << 4) + c) ^ (y + sum) ^ ((y >> 5) + d);
82         y -= ((z << 4) + a) ^ (z + sum) ^ ((z >> 5) + b);
83         sum -= delta;
84     }    /* end cycle */
85     out[0] = ntoh(y);
86     out[1] = ntoh(z);
87 }

需要说明的是TEA的构造函数：
TEA(const byte *key, int round = 32, bool isNetByte = false);
1.key - 加密或解密用的128-bit(16byte)密钥。
2.round - 加密或解密的轮数，常用的有64，32，16。
3.isNetByte - 用来标记待处理的字节是不是来自网络，为true时在加密/解密前先要转换成本地字节，执行加密/解密，然后再转换回网络字节。偷偷告诉你，QQ就是这样做的！

最后当然少不了测试代码：
test.cpp

1 #include "tea.h"
2 #include "util.h"
3 #include <iostream>
4
5 using namespace std;
6
7 int main() {
8
9     const string plainStr("AD DE E2 DB B3 E2 DB B3");
10     const string keyStr("3A DA 75 21 DB E2 DB B3 11 B4 49 01 A5 C6 EA D4");
11     const int SIZE_IN = 8, SIZE_OUT = 8, SIZE_KEY = 16;
12     byte plain[SIZE_IN], crypt[SIZE_OUT], key[SIZE_KEY];
13
14     size_t size_in = hexStringToBytes(plainStr, plain);
15     size_t size_key = hexStringToBytes(keyStr, key);
16
17     if (size_in != SIZE_IN || size_key != SIZE_KEY)
18         return -1;
19
20     cout << "Plain: " << bytesToHexString(plain, size_in) << endl;
21     cout << "Key  : " << bytesToHexString(key, size_key) << endl;
22
23     TEA tea(key, 16, true);
24     tea.encrypt(plain, crypt);
25     cout << "Crypt: " << bytesToHexString(crypt, SIZE_OUT) << endl;
26
27     tea.decrypt(crypt, plain);
28     cout << "Plain: " << bytesToHexString(plain, SIZE_IN) << endl;
29     return 0;
30 }

运行结果：
Plain: AD DE E2 DB B3 E2 DB B3
Key : 3A DA 75 21 DB E2 DB B3 11 B4 49 01 A5 C6 EA D4
Crypt: 3B 3B 4D 8C 24 3A FD F2
Plain: AD DE E2 DB B3 E2 DB B3

源代码下载：点击下载

在这里:http://www.coolcode.cn/?p=128
找到了TEA的详细点的介绍:

微型加密算法（TEA）及其相关变种（XTEA，Block TEA，XXTEA）都是分组加密算法，它们很容易被描述，实现也很简单（典型的几行代码）。

TEA 算法最初是由剑桥计算机实验室的 David Wheeler 和 Roger Needham 在 1994 年设计的。该算法使用 128 位的密钥为 64 位的信息块进行加密，它需要进行 64 轮迭代，尽管作者认为 32 轮已经足够了。该算法使用了一个神秘常数δ作为倍数，它来源于黄金比率，以保证每一轮加密都不相同。但δ的精确值似乎并不重要，这里 TEA 把它定义为 δ=「(√5 - 1)231」（也就是程序中的 0×9E3779B9）。

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

在跟描述 XTEA 算法的同一份报告中，还介绍了另外一种被称为 Block TEA 算法的变种，它可以对 32 位大小任意倍数的变量块进行操作。该算法将 XTEA 轮循函数依次应用于块中的每个字，并且将它附加于它的邻字。该操作重复多少轮依赖于块的大小，但至少需要 6 轮。该方法的优势在于它无需操作模式（CBC，OFB，CFB 等），密钥可直接用于信息。对于长的信息它可能比 XTEA 更有效率。

在 1998 年，Markku-Juhani Saarinen 给出了一个可有效攻击 Block TEA 算法的代码，但之后很快 David J. Wheeler 和 Roger M. Needham 就给出了 Block TEA 算法的修订版，这个算法被称为 XXTEA。XXTEA 使用跟 Block TEA 相似的结构，但在处理块中每个字时利用了相邻字。它利用一个更复杂的 MX 函数代替了 XTEA 轮循函数，MX 使用 2 个输入量。

转载:http://waitforlynn.spaces.live.com/blog/cns!F297AF6761A0D71!163.entry
(下面是TEA的汇编代码,感觉上面的C++语言还能优化下，可以使用汇编代码来写,所以先转载收藏下)

Tea加密算法的核心代码-Win32Asm原创
;---------------------------------
;Tea 加密算法
;Writer:Linfeng
;E-mail:foryouforhappy@gmail.com
;Date: 2007-1-21
   .386
   .model flat,stdcall
   option casemap:none
;---------------------------------
;include 定义
include   windows.inc
include   kernel32.inc
includelib  kernel32.lib
include   user32.inc
includelib  user32.lib
include   gdi32.inc
includelib  gdi32.lib
;---------------------------------
;equ 定义
DLG_Main  equ 101
Main_Ico                equ 103
Edt_Input               equ 1001
Edt_key                 equ 1002
Edt_EncryptionStr       equ 1004
Edt_IncryptionStr       equ 1005
Btn_Encryption          equ 1006h
Btn_Incryption          equ 1007h
IDC_STATIC              equ -1
;---------------------------------
;MACRO 宏定义
;---------------------------------
;data 数据段
  .data
hInstance dd ?
strCaption db '系统提示',0
strText  db '请输入轮数',0
strText1 db '请输入的密匙不正确!',0
FormatTea db '%08x%8x',0
TeaHex  db 17 dup(0)
Key  db 17 dup(0)
  .data?
SumStrLen dd ?      ;格式化后的串长度
lpSumStr dd ?      ;格式化后的串的指针
;---------------------------------
;code   代码段
    .code
;-----------------------------------
;格式化串
_FormatStrTea proc uses ebx edi esi _lpData
LOCAL @strLen

invoke lstrlen,_lpData                         ;取得字符串长度(byte)
mov @strLen,eax
shr eax,3     ;长度除8(byte)
inc eax
shl eax,3
mov SumStrLen,eax
invoke VirtualAlloc,NULL,SumStrLen,MEM_COMMIT,PAGE_EXECUTE_READWRITE
mov lpSumStr,eax
invoke RtlZeroMemory,lpSumStr,SumStrLen
mov esi,_lpData
mov edi,lpSumStr
mov ecx,@strLen
rep movsb
mov eax,lpSumStr
ret
_FormatStrTea  endp
;---------------------------------
;Tea Hex Tea加密算法
_EncryptionTea proc uses ebx edi esi _lpData,_keyStr  ;加密
LOCAL @v0,@v1
LOCAL @y,@z
LOCAL @Sum,@Delta
LOCAL @a_,@b_,@c_,@d_
LOCAL @_Count     ;轮数

mov @_Count,32                              ;32轮
mov @Sum,0                                 ;初始一些变量值
mov @Delta,9E3779B9h
       ;设置密匙
mov esi,_keyStr
mov edi,offset Key
mov ecx,16
rep movsb

mov edi,offset Key
mov eax,dword ptr [edi+0]
mov @a_,eax
mov eax,dword ptr [edi+4]
mov @b_,eax
mov eax,dword ptr [edi+8]
mov @c_,eax
mov eax,dword ptr [edi+12]
mov @d_,eax

invoke _FormatStrTea,_lpData

mov edi,lpSumStr
mov eax,dword ptr [edi+0]
mov @v0,eax
mov eax,dword ptr [edi+4]
mov @v1,eax

mov eax,@v0
mov @y,eax
mov eax,@v1
mov @z,eax

.while @_Count > 0
  mov eax,@Sum       ; Sum <- Sum + Delata
  add  eax,@Delta
  mov @Sum,eax

  ;----------------------------
  ;y <- y +(((z<<4)+a)^(z+Sum)^((z>>5)+b))
  mov eax,@z   ;  z << 4 --> eax
  shl eax,4
  add eax,@a_   ;  a + (z<<4) --> ebx

  mov ecx,@z   ;  ( z >> 5) + b --> ecx
  shr ecx,5
  add ecx,@b_

  mov ebx,@z   ;  z + sum
  add ebx,@Sum
  xor eax,ebx
  xor eax,ecx

  add eax,@y
  mov @y,eax

  ;------------------------------
  ;z <- z +(((y<<4)+c)^(y+Sum)^((y>>5)+d))
  mov eax,@y   ;(y << 4)+c --> eax
  shl eax,4
  add eax,@c_

  mov ebx,@y   ; y + sum --> ebx
  add ebx,@Sum

  mov ecx,@y   ; Sum ^ (y>>5) --> ecx
  shr ecx,5
  add ecx,@d_

  xor eax,ebx   ; eax+ebx+ecx+d+z --> z
  xor eax,ecx
  add eax,@z
  mov @z,eax

  dec @_Count
.endw
mov eax,@y
xchg al,ah
rol eax,16
xchg al,ah
mov @v0,eax

mov eax,@z
xchg al,ah
rol eax,16
xchg al,ah
mov @v1,eax

mov edi,lpSumStr
mov eax,@v0
mov dword ptr [edi+0],eax
mov eax,@v1
mov dword ptr [edi+4],eax

invoke wsprintf,offset TeaHex,offset FormatTea,@v0,@v1
ret
_EncryptionTea endp
;-----------------------------------
_DecryptionTea proc uses ebx edi esi _lpData  ;解密
LOCAL @v0,@v1
LOCAL @y,@z
LOCAL @Sum,@Delta
LOCAL @a_,@b_,@c_,@d_
LOCAL @_Count     ;轮数
mov @_Count,32                              ;32轮
mov @Sum,0c6ef3720h                                  ;初始一些变量值
mov @Delta,09e3779b9h

mov edi,offset Key
mov eax,dword ptr [edi+0]
mov @a_,eax
mov eax,dword ptr [edi+4]
mov @b_,eax
mov eax,dword ptr [edi+8]
mov @c_,eax
mov eax,dword ptr [edi+12]
mov @d_,eax

mov edi,_lpData
mov eax,dword ptr [edi+0]
xchg al,ah
rol eax,16
xchg al,ah
mov @v0,eax
mov eax,dword ptr [edi+4]
xchg  al,ah
rol eax,16
xchg al,ah
mov @v1,eax

mov eax,@v0
mov @y,eax
mov eax,@v1
mov @z,eax

.while @_Count > 0

  ;----------------------------
  ;z <- z - (((y<<4) + c)^(y + Sum)^((y>>5) + d))
  mov eax,@y   ;  (y << 4) + c--> eax
  shl eax,4
  add eax,@c_

  mov ebx,@y    ;  y + sum --> ebx
  add ebx,@Sum

  mov ecx,@y   ;  Sum ^ ( y >> 5) --> ecx
  shr ecx,5
  add ecx,@d_

  xor eax,ebx   ;  eax +ebx + ecx + d -->eax
  xor eax,ecx
  mov ebx,eax
  mov eax,@z
  sub eax,ebx

  mov @z,eax

  ;------------------------------
  ;y <- y - ((z<<4) + a)^(z + Sum)^((z>>5) + b))
  mov eax,@z   ;z << 4 --> eax
  shl eax,4
  add eax,@a_

  mov ebx,@z   ;z + Sum --> ebx
  add ebx,@Sum

  mov ecx,@z   ; (z>>5)+ b--> ecx
  shr ecx,5
  add ecx,@b_

  xor eax,ebx   ;y-(eax^ebx^ecx) --> ebx
  xor eax,ecx
  mov ebx,eax
  mov eax,@y
  sub eax,ebx

  mov @y,eax

  mov eax,@Sum                ;sum <-- sum - Delata
  sub eax,@Delta
  mov @Sum,eax

  dec @_Count
.endw

mov eax,@y
mov @v0,eax
mov eax,@z
mov @v1,eax

mov edi,lpSumStr
mov  eax,@v0
mov dword ptr [edi+0],eax
mov  eax,@v1
mov dword ptr [edi+4],eax

ret

_DecryptionTea endp

PS:错误处请大家批评

提提供给大家使用，原本想用Win32Asm写一个QQ登陆的,结果对协议分析那块不熟.
等掌握了再写咯~!

写的啥东西，拜托，自己写的代码测试两道行不？
源串还必须按你规定的格式，这就算了，我拿你的源串测试，结果确实和你的结果一样，我把你的源串稍微改动一下，加密出来的结果和前面一样，这也叫加密？？？