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

血刀老祖

TEA(Tiny Encryption Algorithm) 是一种简单高效的加密算法，以加密解密速度快，实现简单著称。算法真的很简单，TEA算法每一次可以操作64-bit(8-byte)，采用128-bit(16-byte)作为key，算法采用迭代的形式，推荐的迭代轮数是64轮，最少32轮。目前我只知道QQ一直用的是16轮TEA。没什么好说的，先给出C语言的源代码(默认是32轮)：
  e. h- I6 J+ [) q: X# y# ~( F微型加密算法（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 更有效率。
7 D( T# A2 o' z& L/ c在 1998 年，Markku-Juhani Saarinen 给出了一个可有效攻击 Block TEA 算法的代码，但之后很快 David J. Wheeler 和 Roger M. Needham 就给出了 Block TEA 算法的修订版，这个算法被称为 XXTEA。XXTEA 使用跟 Block TEA 相似的结构，但在处理块中每个字时利用了相邻字。它利用一个更复杂的 MX 函数代替了 XTEA 轮循函数，MX 使用 2 个输入量。

天云上人

1. 
   $ s6 i" @$ }7 W* k
2. void encrypt(unsigned long *v, unsigned long *k) {
   
3.      unsigned long y=v[0], z=v[1], sum=0, i;         /* set up */
   9 o/ K+ p' r6 Q6 r+ G
4.      unsigned long delta=0x9e3779b9;                 /* a key schedule constant */
   - b" ^" g7 f6 u0 B+ ?5 \' w: _
5.      unsigned long a=k[0], b=k[1], c=k[2], d=k[3];   /* cache key */
   . A) v+ \3 l' O* F3 Y% G8 U
6.      for (i=0; i < 32; i++) {                        /* basic cycle start */
   & L9 `6 G& ^* D4 L- z8 j% [
7.          sum += delta;
   
8.          y += ((z<<4) + a) ^ (z + sum) ^ ((z>>5) + b);
   
9.          z += ((y<<4) + c) ^ (y + sum) ^ ((y>>5) + d);/* end cycle */
   
10.      }
    5 p6 }9 o; R: y) l" ~1 m) `* y
11.      v[0]=y;
    
12.      v[1]=z;
    
13. }
    8 B! r' d9 l" v  Q/ \0 _8 R
14.   
    * e) Y5 q# P8 T4 E! k1 }3 r: f
15. void decrypt(unsigned long *v, unsigned long *k) {
    0 n& n  {$ Q1 P" T) {
16.      unsigned long y=v[0], z=v[1], sum=0xC6EF3720, i; /* set up */
    / E9 i. c3 q: U: k9 p* L3 n4 f" P
17.      unsigned long delta=0x9e3779b9;                  /* a key schedule constant */
    0 v8 B% T7 Q# j; J9 F, {
18.      unsigned long a=k[0], b=k[1], c=k[2], d=k[3];    /* cache key */
    7 o: Q% Z2 q% R6 K
19.      for(i=0; i<32; i++) {                            /* basic cycle start */
    + j& `: n; q& B* e$ m3 _
20.          z -= ((y<<4) + c) ^ (y + sum) ^ ((y>>5) + d);
    
21.          y -= ((z<<4) + a) ^ (z + sum) ^ ((z>>5) + b);
    
22.          sum -= delta;                                /* end cycle */
    2 f7 d0 S5 A5 R" w0 m
23.      }
    , ?; T# m+ w% ~# F% W0 }
24.      v[0]=y;
    
25.      v[1]=z;
    
26. }
    ( S- F5 T+ |3 \0 R. q

复制代码

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

天云上人

#ifndef UTIL_H
& O2 X, H  ~8 e( S% }' e; K( ~#define UTIL_H
4 L# t& E% v2 L/ `6 V
#include <string>
#include <cmath>
#include <cstdlib>
: l7 [$ U, }* ~
typedef unsigned char byte;
( X5 Z! f6 H4 ^) rtypedef unsigned long ulong;
- f" E: h! x" O; r- A! G& O) R
inline double logbase(double base, double x) {
6 n! H+ U# J8 C; f) c4 T: e5 R    return log(x)/log(base);
/ T$ \# G4 q7 F: N8 Y0 B7 J0 @}

/*
*convert int to hex char.
*example:10 -> 'A',15 -> 'F'
6 [* u8 i4 @) \0 B6 \3 J*/
! ^3 f9 s: @/ K/ M( n4 u) S' |+ Echar intToHexChar(int x);
0 k, Y) o  Y# W# W
/*
( m! L$ ?& P5 B*convert hex char to int.
8 m  V$ }6 v1 o  `2 J2 C' }  \- A*example:'A' -> 10,'F' -> 15
*/
int hexCharToInt(char hex);
9 _4 i2 I  z5 N  m6 K
using std::string;
/*
*convert a byte array to hex string.
*hex string format example:"AF B0 80 7D"
*/
string bytesToHexString(const byte *in, size_t size);

/*
7 W$ f2 w8 A. e5 C' q. }- ~*convert a hex string to a byte array.
: n, J- |: ^8 Y; ^& O7 u) ?( D*hex string format example:"AF B0 80 7D"
*/
5 F8 s+ i9 A( L8 @: Q, N& wsize_t hexStringToBytes(const string &str, byte *out);

! Q& u7 z5 Z% |#endif/*UTIL_H*/

天云上人

#include "util.h"
#include <vector>
& R) Y( L8 P7 ?7 ?1 b
using namespace std;
9 q; Y; y$ b, A' @
2 C' U; e% b: U$ q' r8 |- @char intToHexChar(int x) {
    static const char HEX[16] = {
        '0', '1', '2', '3',
6 D9 [% Y) M6 b- x- z. Y, K3 m        '4', '5', '6', '7',
+ Z0 ~* Q, O1 G  Q, `        '8', '9', 'A', 'B',
1 \* b3 P' j5 W# ^        'C', 'D', 'E', 'F'
7 N9 Q: ~# B0 J# l, O    };
! a" V& e) z; r2 |$ T    return HEX[x];
0 y! d+ K1 w: ^6 q* q  d) g8 G}
- n$ E& Z/ r8 ~9 F
int hexCharToInt(char hex) {
$ s: V* C9 Z' Z    hex = toupper(hex);
' b- u# \4 T& L    if (isdigit(hex))
        return (hex - '0');
    if (isalpha(hex))
        return (hex - 'A' + 10);
4 }4 K, o( |& \3 R    return 0;
}

string bytesToHexString(const byte *in, size_t size) {
    string str;
/ l+ h0 g, e# S# M  m/ r* b    for (size_t i = 0; i < size; ++i) {
        int t = in[i];
- |( `# F& e) e& y$ L' u        int a = t / 16;
% l: t. ]3 \$ z        int b = t % 16;
% K3 w8 `1 `2 U. |( n$ F        str.append(1, intToHexChar(a));
        str.append(1, intToHexChar(b));
+ w  X( R. U& [        if (i != size - 1)
3 z+ l' \) @* Y# n, p' C            str.append(1, ' ');
% W+ _, u4 a2 _' y7 {9 r    }
1 X  Q; g$ g/ e    return str;
& T# C# g$ j3 y- d6 _}

size_t hexStringToBytes(const string &str, byte *out) {
# z1 Q6 L- N7 ]0 H
    vector<string> vec;
    string::size_type currPos = 0, prevPos = 0;
. b- b7 q0 s; C' I' {! |8 R3 z    while ((currPos = str.find(' ', prevPos)) != string::npos) {
+ t# t6 c& a/ r' \% x% i        string b(str.substr(prevPos, currPos - prevPos));
* D2 I/ n- U) [+ `9 X1 n) v5 \/ ~        vec.push_back(b);
        prevPos = currPos + 1;
    }
2 F" R9 i9 S/ c7 k* S4 ?0 k    if (prevPos < str.size()) {
: m+ B, T. i1 M+ F/ ]+ h        string b(str.substr(prevPos));
        vec.push_back(b);
& n$ U7 |1 x1 G4 C& y8 t    }
    typedef vector<string>::size_type sz_type;
+ @$ y. k1 o8 {6 x% }- U    sz_type size = vec.size();
    for (sz_type i = 0; i < size; ++i) {
: @1 G$ Z$ |  S: o( z) _        int a = hexCharToInt(vec[i][0]);
' u4 H4 D& E0 h0 h% Y        int b = hexCharToInt(vec[i][1]);
        out[i] = a * 16 + b;
; }; p" @5 `5 `. b1 P  l0 ?4 I2 q/ c    }
    return size;
) G) g& e, |2 z7 m}

天云上人

#ifndef TEA_H
/ e8 }* m$ V0 W3 q6 |* p#define TEA_H

$ e* N. h2 V- J1 a9 T9 I/*
( F% B  z: _& I*for htonl,htonl
*do remember link "ws2_32.lib"
*/
8 B8 s5 Q+ C: m9 m8 X; }8 z#include <winsock2.h>
#include "util.h"

8 ]0 f5 l3 t5 r$ y; U/ Tclass TEA {
public:
3 [/ j9 j5 A/ _! f9 {8 X    TEA(const byte *key, int round = 32, bool isNetByte = false);
    TEA(const TEA &rhs);
3 o& i9 s: s6 n8 F7 ^    TEA& operator=(const TEA &rhs);
4 t5 y1 \5 K+ D& l$ N! q    void encrypt(const byte *in, byte *out);
  K, u! n" q6 A+ A, ~5 S3 j6 g/ M    void decrypt(const byte *in, byte *out);
private:
1 Y6 k4 i; ]$ A    void encrypt(const ulong *in, ulong *out);
    void decrypt(const ulong *in, ulong *out);
    ulong ntoh(ulong netlong) { return _isNetByte ? ntohl(netlong) : netlong; }
    ulong hton(ulong hostlong) { return _isNetByte ? htonl(hostlong) : hostlong; }
private:
    int _round; //iteration round to encrypt or decrypt
4 C; B& \2 v1 T0 I+ n( j    bool _isNetByte; //whether input bytes come from network
    byte _key[16]; //encrypt or decrypt key
};

#endif/*TEA_H*/

天云上人

1 #include "tea.h"
2 #include <cstring> //for memcpy,memset
3  
, i9 ]# K$ ^7 Z) g# u4 {9 j 4 using namespace std;
5  
3 L3 o6 H2 P& U% ? 6 TEA::TEA(const byte *key, int round /*= 32*/, bool isNetByte /*= false*/)
! q# M# Y* F0 [% S3 z% d 7 :_round(round)
$ J- k1 _$ o4 K7 ]. y4 k" g/ h' w5 } 8 ,_isNetByte(isNetByte) {
9     if (key != 0)
; M. e/ [+ B# R8 n/ ^, |/ Z10         memcpy(_key, key, 16);
11     else
! d1 _# w1 f* C2 ]2 l- d- ~12         memset(_key, 0, 16);
13 }
% i. y) t/ I/ ~1 r14  
15 TEA::TEA(const TEA &rhs)
16 :_round(rhs._round)
17 ,_isNetByte(rhs._isNetByte) {
18     memcpy(_key, rhs._key, 16);
2 \2 }7 }) A/ V( n7 x19 }
2 T' `& V/ w& s3 |% m& |5 ]20  
21 TEA& TEA::operator=(const TEA &rhs) {
22     if (&rhs != this) {
23         _round = rhs._round;
# k5 a/ s: |' Z24         _isNetByte = rhs._isNetByte;
- l# X$ g% _7 _, B* k, T25         memcpy(_key, rhs._key, 16);
26     }
27     return *this;
" W3 q: H+ i5 t. C  J28 }
29  
30 void TEA::encrypt(const byte *in, byte *out) {
31     encrypt((const ulong*)in, (ulong*)out);
7 X3 y- l/ U0 C5 m. q) Z32 }
33  
3 c& |+ {8 ?3 h4 X9 o34 void TEA::decrypt(const byte *in, byte *out) {
35     decrypt((const ulong*)in, (ulong*)out);
36 }
37  
9 c. P+ \: C( r; P, G38 void TEA::encrypt(const ulong *in, ulong *out) {
39  
40     ulong *k = (ulong*)_key;
8 v0 I% k) z4 `3 s7 T+ q41     register ulong y = ntoh(in[0]);
; f9 G: S5 \+ G  @* i+ R42     register ulong z = ntoh(in[1]);
( D8 g; {9 ^3 d+ y1 M43     register ulong a = ntoh(k[0]);
, t, e$ m' g/ z% X. W44     register ulong b = ntoh(k[1]);
45     register ulong c = ntoh(k[2]);
( u, b2 i8 f& Y7 N4 T' _46     register ulong d = ntoh(k[3]);
47     register ulong delta = 0x9E3779B9; /* (sqrt(5)-1)/2*2^32 */
  `) z; @: }! `$ v  @; q48     register int round = _round;
49     register ulong sum = 0;
50  
51     while (round--) {    /* basic cycle start */
- }' I4 j& Q  k) M- M  C52         sum += delta;
53         y += ((z << 4) + a) ^ (z + sum) ^ ((z >> 5) + b);
& I! L4 q3 W7 f3 _$ [7 I; L7 u54         z += ((y << 4) + c) ^ (y + sum) ^ ((y >> 5) + d);
55     }    /* end cycle */
7 O. o/ ]) G5 |# d- o3 U56     out[0] = ntoh(y);
57     out[1] = ntoh(z);
58 }
59  
60 void TEA::decrypt(const ulong *in, ulong *out) {
  M- T9 w: z2 E( U2 Y; h61  
3 B4 `9 m3 r5 n; Z62     ulong *k = (ulong*)_key;
63     register ulong y = ntoh(in[0]);
64     register ulong z = ntoh(in[1]);
0 v% B1 J- Q, h+ ^' `1 C4 X65     register ulong a = ntoh(k[0]);
66     register ulong b = ntoh(k[1]);
67     register ulong c = ntoh(k[2]);
5 h. _' L& E+ x9 c- O68     register ulong d = ntoh(k[3]);
69     register ulong delta = 0x9E3779B9; /* (sqrt(5)-1)/2*2^32 */
& c, M& \& U. W! \& c70     register int round = _round;
5 S2 q0 ~. I0 h0 d* g) J71     register ulong sum = 0;
72  
1 `. |/ l, T3 [/ U* C' X73     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  
3 p" m8 V/ g+ k1 Y80     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);
2 X  \# i9 |2 T  ]2 n1 t83         sum -= delta;
. {1 U0 j6 N* Y84     }    /* end cycle */
6 e7 D5 W" S, J& d8 n! [85     out[0] = ntoh(y);
86     out[1] = ntoh(z);
8 x# Z1 w7 t" p% e" _87 }

需要说明的是TEA的构造函数：
! B7 ^0 |0 r7 L& z$ v1 N9 [; ?" WTEA(const byte *key, int round = 32, bool isNetByte = false);
1.key - 加密或解密用的128-bit(16byte)密钥。
2.round - 加密或解密的轮数，常用的有64，32，16。
- }. T+ s3 _: \# Y3.isNetByte - 用来标记待处理的字节是不是来自网络，为true时在加密/解密前先要转换成本地字节，执行加密/解密，然后再转换回网络字节。偷偷告诉你，QQ就是这样做的！
! G+ `6 L% W. l
最后当然少不了测试代码：

天云上人

1 #include "tea.h"
2 #include "util.h"
3 #include <iostream>
4  
5 using namespace std;
) S( K) u7 e; w- A% F) V4 ?3 R 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  
9 }  I! g: x$ Z  Y2 t14     size_t size_in = hexStringToBytes(plainStr, plain);
* P1 m, d* w& r% i! T15     size_t size_key = hexStringToBytes(keyStr, key);
6 v  |9 q+ R' Y  X16  
17     if (size_in != SIZE_IN || size_key != SIZE_KEY)
3 c7 Z; g0 }: v  d5 i% S1 U18         return -1;
19  
$ M2 F; j' r5 ^+ E: N! |20     cout << "Plain: " << bytesToHexString(plain, size_in) << endl;
21     cout << "Key  : " << bytesToHexString(key, size_key) << endl;
22  
! J$ F2 w) v2 s$ J; O& Z8 {1 N( {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;
7 B/ J9 W8 z& }30 }
# q$ t7 i+ r* z  u( d7 f) v
本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/sailing0123/archive/2008/04/28/2339231.aspx
0 H- x$ X. \" ^, ]运行结果：
Plain: AD DE E2 DB B3 E2 DB B3
: {" J, F; d" _, a( c1 A2 K5 _/ {) UKey  : 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