TEA加密算法的C/C++实现

血刀老祖

TEA(Tiny Encryption Algorithm) 是一种简单高效的加密算法，以加密解密速度快，实现简单著称。算法真的很简单，TEA算法每一次可以操作64-bit(8-byte)，采用128-bit(16-byte)作为key，算法采用迭代的形式，推荐的迭代轮数是64轮，最少32轮。目前我只知道QQ一直用的是16轮TEA。没什么好说的，先给出C语言的源代码(默认是32轮)：
, j3 p2 P3 y8 F  V微型加密算法（TEA）及其相关变种（XTEA，Block TEA，XXTEA） 都是分组加密算法，它们很容易被描述，实现也很简单（典型的几行代码）。
. K* }( u0 c. [/ YTEA 算法最初是由剑桥计算机实验室的 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 更有效率。
# Q" D' x; \2 o& p  e  P. m在 1998 年，Markku-Juhani Saarinen 给出了一个可有效攻击 Block TEA 算法的代码，但之后很快 David J. Wheeler 和 Roger M. Needham 就给出了 Block TEA 算法的修订版，这个算法被称为 XXTEA。XXTEA 使用跟 Block TEA 相似的结构，但在处理块中每个字时利用了相邻字。它利用一个更复杂的 MX 函数代替了 XTEA 轮循函数，MX 使用 2 个输入量。

天云上人

1. 
   - C5 \( C2 y& P1 k) m  n
2. void encrypt(unsigned long *v, unsigned long *k) {
   & q0 L" U! c4 l% i* |6 s- i1 v
3.      unsigned long y=v[0], z=v[1], sum=0, i;         /* set up */
     d# O( \( E: c0 a: o. P* u$ R0 O
4.      unsigned long delta=0x9e3779b9;                 /* a key schedule constant */
   
5.      unsigned long a=k[0], b=k[1], c=k[2], d=k[3];   /* cache key */
   
6.      for (i=0; i < 32; i++) {                        /* basic cycle start */
   
7.          sum += delta;
   7 F1 u( {0 F) S- V- k6 a
8.          y += ((z<<4) + a) ^ (z + sum) ^ ((z>>5) + b);
   
9.          z += ((y<<4) + c) ^ (y + sum) ^ ((y>>5) + d);/* end cycle */
   
10.      }
    
11.      v[0]=y;
    
12.      v[1]=z;
    
13. }
    2 ~; H& h2 L: ^
14.   
    
15. void decrypt(unsigned long *v, unsigned long *k) {
    0 n$ O) N+ m4 o
16.      unsigned long y=v[0], z=v[1], sum=0xC6EF3720, i; /* set up */
    ( Z1 f' @! ~% s6 Q! b  v
17.      unsigned long delta=0x9e3779b9;                  /* a key schedule constant */
    
18.      unsigned long a=k[0], b=k[1], c=k[2], d=k[3];    /* cache key */
    
19.      for(i=0; i<32; i++) {                            /* basic cycle start */
    
20.          z -= ((y<<4) + c) ^ (y + sum) ^ ((y>>5) + d);
      M5 M! `# `/ W) T1 t8 Y. z
21.          y -= ((z<<4) + a) ^ (z + sum) ^ ((z>>5) + b);
    
22.          sum -= delta;                                /* end cycle */
    ! s8 m4 R, J  K# w- o
23.      }
    
24.      v[0]=y;
    
25.      v[1]=z;
    
26. }
    

复制代码

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

天云上人

#ifndef UTIL_H
/ v: A  l, v: {  Q#define UTIL_H

#include <string>
; q: O8 }9 A5 `. i. P( g#include <cmath>
#include <cstdlib>
% ~4 k, f9 G! \6 f1 x( H
8 Z6 v! W. g* M/ Etypedef unsigned char byte;
1 {2 q/ X( [6 C- j0 otypedef unsigned long ulong;

! K% s8 H( r1 l, D3 p, @) cinline double logbase(double base, double x) {
6 E% B! ]# j2 `- y" N6 x' I+ l9 y# b    return log(x)/log(base);
}
. F5 p- K1 E/ O, p  E; B
9 J- `5 y0 h) Z! C5 m: n5 u) R/*
*convert int to hex char.
*example:10 -> 'A',15 -> 'F'
*/
6 P. |$ f" _9 ]& `char intToHexChar(int x);
) H. v8 r& a$ j+ H1 h" C6 j$ R- U
/*
*convert hex char to int.
# ~5 \: ]" D" |7 w! ?" {*example:'A' -> 10,'F' -> 15
. l, y1 l# B" a  k/ T& ]*/
0 v$ l5 I. Y& p, [int hexCharToInt(char hex);
' j, X' u  H- K/ @+ r6 e& r
using std::string;
. ~. @4 u% ~. s4 K% b/*
*convert a byte array to hex string.
# u% i+ a6 q- [5 a*hex string format example:"AF B0 80 7D"
*/
string bytesToHexString(const byte *in, size_t size);
! z. M, |. ?, V3 t3 n& }
* F0 @$ a6 D6 d( ~9 g7 V/*
) D% w: @2 r8 q: Y) J*convert a hex string to a byte array.
*hex string format example:"AF B0 80 7D"
2 d- B) F% ^/ q; Y  @) ^5 @$ ?*/
' C7 v. q2 ]+ F) fsize_t hexStringToBytes(const string &str, byte *out);
& T% R9 i7 z' s, y& e
#endif/*UTIL_H*/

天云上人

#include "util.h"
#include <vector>

using namespace std;
( b) |% _; B( V: y# `
char intToHexChar(int x) {
' o6 s  t% R% i% T    static const char HEX[16] = {
        '0', '1', '2', '3',
5 v% N+ z, V$ F0 m        '4', '5', '6', '7',
5 I; Y9 ?8 v2 Y- z6 M& e1 ^8 B        '8', '9', 'A', 'B',
        'C', 'D', 'E', 'F'
    };
    return HEX[x];
$ }7 d' I0 b& x8 M" F# K# C3 S}

int hexCharToInt(char hex) {
    hex = toupper(hex);
    if (isdigit(hex))
3 i$ G- J4 K+ b7 i        return (hex - '0');
1 @3 r0 S7 E) i0 y    if (isalpha(hex))
        return (hex - 'A' + 10);
! v1 [6 S# H5 n9 }$ z* l, z    return 0;
! V0 ?  w. U: v6 a1 W}

string bytesToHexString(const byte *in, size_t size) {
' I) R  G; T4 K' f) n    string str;
    for (size_t i = 0; i < size; ++i) {
8 V0 V2 o- H) K* X- G' _; A+ M        int t = in[i];
        int a = t / 16;
+ a( b! x2 C7 c2 ?# F( C        int b = t % 16;
' ]' f# _9 }, a& J3 B- M4 g# K        str.append(1, intToHexChar(a));
8 k7 y% G- \' x        str.append(1, intToHexChar(b));
        if (i != size - 1)
3 b. A% d, i2 a7 S. W2 v9 U            str.append(1, ' ');
    }
5 ]# g6 T0 U  x& W8 i    return str;
" z: X% z7 U$ o0 x2 M6 x5 x}

size_t hexStringToBytes(const string &str, byte *out) {
0 i% t4 Z6 q5 b( m% ~. G3 b
    vector<string> vec;
8 |9 q' u3 H. X3 W* [5 Z    string::size_type currPos = 0, prevPos = 0;
% R6 J( ^) }' {2 c' r    while ((currPos = str.find(' ', prevPos)) != string::npos) {
$ d8 p9 e- b0 I+ X        string b(str.substr(prevPos, currPos - prevPos));
        vec.push_back(b);
! }2 O+ N' l" @% X$ o        prevPos = currPos + 1;
    }
& ^9 J6 Q% Z, h/ D: ?    if (prevPos < str.size()) {
        string b(str.substr(prevPos));
% M7 `2 _$ W3 a6 |' {% e        vec.push_back(b);
    }
    typedef vector<string>::size_type sz_type;
    sz_type size = vec.size();
1 c1 D& y- o% u    for (sz_type i = 0; i < size; ++i) {
        int a = hexCharToInt(vec[i][0]);
1 Z+ f& P5 x/ [9 i3 J3 E9 @; z        int b = hexCharToInt(vec[i][1]);
! L9 S+ T* |$ e) \        out[i] = a * 16 + b;
% Y) S  ?# _5 Z/ n! _0 a    }
9 {$ Q& Z4 R' @; p: O  f! \! A    return size;
}

天云上人

#ifndef TEA_H
# w/ Z( ^) t( [& {- V#define TEA_H
, ]# G0 ]2 t9 Y2 K
& B" |! O0 v% G9 N$ O/*
6 Q% @2 t" A9 c*for htonl,htonl
3 t! \  V& Z0 G# V6 {+ _  E- ^4 n*do remember link "ws2_32.lib"
3 T7 ?6 o: m& j. r: h*/
( w5 n! n6 n3 b% w$ Y" M8 X#include <winsock2.h>
( ?! ]4 S: M$ [5 }  N#include "util.h"

" o% k( g- }6 d* i0 Vclass TEA {
public:
: J8 f5 r, |( t1 N    TEA(const byte *key, int round = 32, bool isNetByte = false);
* y( S) B5 T5 p2 l, E7 L    TEA(const TEA &rhs);
    TEA& operator=(const TEA &rhs);
    void encrypt(const byte *in, byte *out);
    void decrypt(const byte *in, byte *out);
private:
    void encrypt(const ulong *in, ulong *out);
' n' N. S2 ?3 q2 b    void decrypt(const ulong *in, ulong *out);
" _& G: z0 `" @% C1 h5 P8 L+ g    ulong ntoh(ulong netlong) { return _isNetByte ? ntohl(netlong) : netlong; }
/ b9 E& ~. a) H/ j    ulong hton(ulong hostlong) { return _isNetByte ? htonl(hostlong) : hostlong; }
private:
7 ?) P: ]. ^2 y% _8 j7 P    int _round; //iteration round to encrypt or decrypt
    bool _isNetByte; //whether input bytes come from network
% q2 R1 u' K( W  `6 W  L    byte _key[16]; //encrypt or decrypt key
, g  U( l0 L- b0 i1 ~1 E};
6 M- Z$ |8 i, {" H+ ~6 f1 w
7 z9 ^7 {# q/ C! M* x# G, l; }1 f4 g  T#endif/*TEA_H*/

天云上人

1 #include "tea.h"
2 #include <cstring> //for memcpy,memset
' S# m/ M, |5 @; |5 Y6 l 3  
4 using namespace std;
5 @( {5 g$ B% @" `0 I' G! X 5  
+ F0 J( X& j6 p( r8 e. t 6 TEA::TEA(const byte *key, int round /*= 32*/, bool isNetByte /*= false*/)
1 @' R, |7 D& q1 r+ {1 w0 ~ 7 :_round(round)
& c3 w1 U) y9 ? 8 ,_isNetByte(isNetByte) {
9     if (key != 0)
10         memcpy(_key, key, 16);
0 r, K$ E8 H- U11     else
12         memset(_key, 0, 16);
13 }
* ~0 H' B+ J8 q/ k$ V0 k14  
2 h0 |2 X9 I& k9 M$ k: c15 TEA::TEA(const TEA &rhs)
16 :_round(rhs._round)
17 ,_isNetByte(rhs._isNetByte) {
; d- j, `: _) c8 Q18     memcpy(_key, rhs._key, 16);
19 }
! D* z2 X1 I3 z! K- S8 T20  
" S+ V  Y0 H: Z4 @7 H: K; l7 E21 TEA& TEA::operator=(const TEA &rhs) {
22     if (&rhs != this) {
6 t0 |; J9 t) k, E; M8 t4 ~- O23         _round = rhs._round;
24         _isNetByte = rhs._isNetByte;
& D- F' O4 V5 q& @: D8 o! y25         memcpy(_key, rhs._key, 16);
26     }
27     return *this;
28 }
29  
30 void TEA::encrypt(const byte *in, byte *out) {
/ k5 z1 C) {+ b! q  ~31     encrypt((const ulong*)in, (ulong*)out);
/ n" H8 {$ v5 @) b+ J32 }
33  
5 d  w- p  h* N* i34 void TEA::decrypt(const byte *in, byte *out) {
35     decrypt((const ulong*)in, (ulong*)out);
36 }
37  
: i0 I3 w1 s+ J+ B" `9 J) B38 void TEA::encrypt(const ulong *in, ulong *out) {
39  
40     ulong *k = (ulong*)_key;
) m$ A: I& p! N% _; m1 O+ Q! q9 l( ]+ g41     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]);
6 l* }9 ~+ T1 r9 X4 G% \$ Y45     register ulong c = ntoh(k[2]);
46     register ulong d = ntoh(k[3]);
2 {4 m8 F' f  h9 n( O- w47     register ulong delta = 0x9E3779B9; /* (sqrt(5)-1)/2*2^32 */
48     register int round = _round;
49     register ulong sum = 0;
) Q7 N/ i5 k4 a4 _5 d& e50  
51     while (round--) {    /* basic cycle start */
52         sum += delta;
53         y += ((z << 4) + a) ^ (z + sum) ^ ((z >> 5) + b);
( ]. J; g% x' B/ y8 h% o54         z += ((y << 4) + c) ^ (y + sum) ^ ((y >> 5) + d);
2 F$ b0 e8 b& u! B' `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  
- b) z) b, _4 S2 |$ E62     ulong *k = (ulong*)_key;
0 J( E3 K5 c( X& Y1 \- j* u63     register ulong y = ntoh(in[0]);
. E, X2 U) q$ T5 k2 M7 U64     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]);
! p& [) N1 @+ \2 l3 x+ M: W$ F68     register ulong d = ntoh(k[3]);
69     register ulong delta = 0x9E3779B9; /* (sqrt(5)-1)/2*2^32 */
70     register int round = _round;
0 R( Y+ d8 i, F8 o71     register ulong sum = 0;
9 ]9 [& S+ W4 L4 M6 c72  
73     if (round == 32)
74         sum = 0xC6EF3720; /* delta << 5*/
75     else if (round == 16)
76         sum = 0xE3779B90; /* delta << 4*/
' m. f8 I. ^0 T" w+ S77     else
78         sum = delta << static_cast<int>(logbase(2, round));
79  
" C; [( R  ^" Q  n, v8 Y: A! k80     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);
4 w0 J/ _  q2 [$ v1 C3 ?& s  ~* |83         sum -= delta;
9 t5 E9 o! A9 k5 R9 q- u2 S8 G5 f84     }    /* end cycle */
8 ?( ~0 ?" T+ [85     out[0] = ntoh(y);
) e: n! {' a# @/ P+ @86     out[1] = ntoh(z);
87 }
) {, y# b$ `+ \! s& \* H) _
5 V/ Z; i7 s+ l1 i需要说明的是TEA的构造函数：
TEA(const byte *key, int round = 32, bool isNetByte = false);
1.key - 加密或解密用的128-bit(16byte)密钥。
; f! h! j! ~0 \2.round - 加密或解密的轮数，常用的有64，32，16。
) V( b% w# |6 G+ T3.isNetByte - 用来标记待处理的字节是不是来自网络，为true时在加密/解密前先要转换成本地字节，执行加密/解密，然后再转换回网络字节。偷偷告诉你，QQ就是这样做的！

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

天云上人

1 #include "tea.h"
2 #include "util.h"
3 #include <iostream>
. Z% B' U+ E  C) S9 Z% I8 o7 ] 4  
0 u) k( R" Q3 `3 K 5 using namespace std;
) g6 X9 A/ L7 [/ T: Q. | 6  
9 r. V- X+ F4 r8 G2 X 7 int main() {
3 M" n" Q3 |8 x7 E' O: N; ]' u 8  
9     const string plainStr("AD DE E2 DB B3 E2 DB B3");
5 X+ C& U3 ]9 H$ }7 u1 ~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;
1 h" ]& w) `/ S- D4 ?& j7 l3 o8 }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)
5 n+ B, P6 O, N0 q18         return -1;
19  
20     cout << "Plain: " << bytesToHexString(plain, size_in) << endl;
1 x. U% Y/ [- o/ I$ t4 k21     cout << "Key  : " << bytesToHexString(key, size_key) << endl;
: `$ d( d) J  Y22  
23     TEA tea(key, 16, true);
* R' o) g; j, Q3 V/ a! O# i5 H24     tea.encrypt(plain, crypt);
! c  @3 J* u7 b- v. l25     cout << "Crypt: " << bytesToHexString(crypt, SIZE_OUT) << endl;
: {/ s( V* ?$ E# |0 f) f/ A  x26  
# E  \* i% _! ]. |5 O27     tea.decrypt(crypt, plain);
28     cout << "Plain: " << bytesToHexString(plain, SIZE_IN) << endl;
; Z# m# @: _9 q6 X& a7 x0 A$ v  H% a; i29     return 0;
& A# H1 F3 M+ @$ Z; h30 }

& K  @  m. `/ E* `4 o本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/sailing0123/archive/2008/04/28/2339231.aspx
运行结果：
5 c9 j4 [7 L! D/ ]0 g& fPlain: AD DE E2 DB B3 E2 DB B3
8 f7 U# s0 Y0 u0 CKey  : 3A DA 75 21 DB E2 DB B3 11 B4 49 01 A5 C6 EA D4
0 q* ^# \. A+ D; q9 UCrypt: 3B 3B 4D 8C 24 3A FD F2
Plain: AD DE E2 DB B3 E2 DB B3