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

血刀老祖

TEA(Tiny Encryption Algorithm) 是一种简单高效的加密算法，以加密解密速度快，实现简单著称。算法真的很简单，TEA算法每一次可以操作64-bit(8-byte)，采用128-bit(16-byte)作为key，算法采用迭代的形式，推荐的迭代轮数是64轮，最少32轮。目前我只知道QQ一直用的是16轮TEA。没什么好说的，先给出C语言的源代码(默认是32轮)：
  n, ^1 L# ^' B  r! e微型加密算法（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 个输入量。

天云上人

1. 
   ! l; {3 P$ B' z+ z/ S+ Z) H
2. void encrypt(unsigned long *v, unsigned long *k) {
   
3.      unsigned long y=v[0], z=v[1], sum=0, i;         /* set up */
   1 p6 m" K1 a; u/ F5 L8 F5 Q
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 */
   ; |& m( [6 m: E% p& E
6.      for (i=0; i < 32; i++) {                        /* basic cycle start */
   
7.          sum += delta;
   
8.          y += ((z<<4) + a) ^ (z + sum) ^ ((z>>5) + b);
   ' ~+ h% D& i6 Y) R" d3 }2 O
9.          z += ((y<<4) + c) ^ (y + sum) ^ ((y>>5) + d);/* end cycle */
   ! ?2 v4 z, \2 p' ]9 Q
10.      }
    
11.      v[0]=y;
    2 w2 ]8 T9 B# Y" c3 W
12.      v[1]=z;
    
13. }
    
14.   
    ( N! o9 B' s2 N" ?
15. void decrypt(unsigned long *v, unsigned long *k) {
    3 j1 \5 s6 H4 C9 Q0 l  o
16.      unsigned long y=v[0], z=v[1], sum=0xC6EF3720, i; /* set up */
    % @$ [( f2 z! I! h0 Z! p
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 */
    % n( }  y2 i. i3 ~
19.      for(i=0; i<32; i++) {                            /* basic cycle start */
    ; K8 r6 {! N" a4 `# o; S
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 */
    . R# R' l4 C5 P8 u
23.      }
    $ r( |& u2 w9 X0 j4 f: ]- q5 @
24.      v[0]=y;
    
25.      v[1]=z;
    2 t3 \% r6 q$ W2 h
26. }
    ( E9 S: c2 ?6 m0 T9 k; b

复制代码

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

天云上人

#ifndef UTIL_H
3 o! w5 ?" ~, f- j/ s#define UTIL_H

) ]2 G& p- A8 E1 |4 |% M4 x#include <string>
#include <cmath>
#include <cstdlib>

typedef unsigned char byte;
/ y# @9 I+ [1 R' q& _/ {typedef unsigned long ulong;
/ E: [* A' F- D1 V7 E
inline double logbase(double base, double x) {
6 z3 g8 _: ~2 I% [    return log(x)/log(base);
}

' d6 o) R3 u( U; x6 r: ^4 J& S/*
*convert int to hex char.
% B$ S, j  J# c  ]*example:10 -> 'A',15 -> 'F'
*/
( b$ p+ V0 d4 K( A" \char intToHexChar(int x);

: |/ i7 V' [0 Y0 M% V4 ^1 _( t8 m" N/*
*convert hex char to int.
*example:'A' -> 10,'F' -> 15
*/
6 R/ j9 N1 P* Z. zint hexCharToInt(char hex);
" r8 ^5 m% i5 H& x. Z! z
using std::string;
% ^5 z. N8 h( v9 S5 S/*
2 b  R$ ^0 c7 X*convert a byte array to hex string.
*hex string format example:"AF B0 80 7D"
; I# G4 I, o/ M*/
9 M3 g; V" i' J. n  ]" S$ x8 ]  T4 G5 Pstring bytesToHexString(const byte *in, size_t size);
$ ~/ I- z" n5 _$ I
/*
*convert a hex string to a byte array.
7 g# M1 s" _- r4 G9 w: I: T*hex string format example:"AF B0 80 7D"
*/
& F0 w0 `% l. hsize_t hexStringToBytes(const string &str, byte *out);

& V$ C$ ?- x. B. g1 G#endif/*UTIL_H*/

天云上人

#include "util.h"
9 D) \) K9 Y1 u, O% m#include <vector>
- s  _8 i: U# O% d. ~
using namespace std;
" A. y( c$ o" u: i
! ]8 l, A) T% a4 {char intToHexChar(int x) {
    static const char HEX[16] = {
$ o! D, G  v; v0 |4 P( O0 ^        '0', '1', '2', '3',
        '4', '5', '6', '7',
        '8', '9', 'A', 'B',
        'C', 'D', 'E', 'F'
/ Q9 U% z8 I7 I& X) Z    };
7 d$ d! f& c3 ~6 `# r2 V/ H    return HEX[x];
4 `; v- k2 B, }6 `- g3 |}

! V4 I6 m3 v4 e. @) H  Tint hexCharToInt(char hex) {
    hex = toupper(hex);
! z+ J; F, p7 |2 a' t    if (isdigit(hex))
: N0 y! |& k) S1 y: [* y        return (hex - '0');
    if (isalpha(hex))
) H( z# A- D/ B8 o3 D        return (hex - 'A' + 10);
    return 0;
  A8 m' a8 t9 ~7 A# a1 F}
: G- m* b+ |/ P. @$ U
string bytesToHexString(const byte *in, size_t size) {
    string str;
' ?# c  ~/ t5 Q$ W' Z& m5 v# I    for (size_t i = 0; i < size; ++i) {
* [' z4 a0 E- R" ^        int t = in[i];
        int a = t / 16;
9 S8 ^" O2 i* e0 u        int b = t % 16;
# q: k( F; V& |6 k1 C; P7 Y        str.append(1, intToHexChar(a));
        str.append(1, intToHexChar(b));
        if (i != size - 1)
            str.append(1, ' ');
    }
: |, o3 S! |( Y5 J& ~    return str;
, ]5 J6 c' C2 a. e4 H8 y+ z}
& e* C# n! a( g! f3 {% K; @! z) z+ K
1 S7 M3 M% j: h" ]* ]size_t hexStringToBytes(const string &str, byte *out) {

    vector<string> vec;
    string::size_type currPos = 0, prevPos = 0;
    while ((currPos = str.find(' ', prevPos)) != string::npos) {
0 n: R. {8 L+ x1 F* V5 p3 V; f; S        string b(str.substr(prevPos, currPos - prevPos));
        vec.push_back(b);
3 L* T( [8 d$ U9 H  ~# C8 G, ]8 W        prevPos = currPos + 1;
7 m9 V" W/ j" i" ]    }
: a2 m% _+ a- P    if (prevPos < str.size()) {
        string b(str.substr(prevPos));
        vec.push_back(b);
    }
. U9 L% }- r& C: J( q. S8 r3 X    typedef vector<string>::size_type sz_type;
    sz_type size = vec.size();
/ [/ o- ]9 G! ~/ `8 H$ F    for (sz_type i = 0; i < size; ++i) {
) f, c6 |# [: I" K        int a = hexCharToInt(vec[i][0]);
        int b = hexCharToInt(vec[i][1]);
        out[i] = a * 16 + b;
    }
    return size;
2 s0 S+ ^+ ?; @( a) K}

天云上人

#ifndef TEA_H
#define TEA_H

8 N% v7 a7 G! ^9 {; d$ Q7 Z/*
: \/ ?( j4 u' v$ W0 |  Q- O$ o*for htonl,htonl
*do remember link "ws2_32.lib"
*/
3 C" k, z) q$ d) A8 C6 i. {#include <winsock2.h>
#include "util.h"
# z, j+ K3 X6 n6 I# ^
class TEA {
public:
, ]# W4 {, W, ?4 W+ R, Y- ~    TEA(const byte *key, int round = 32, bool isNetByte = false);
' |* k: s0 S: J7 b    TEA(const TEA &rhs);
" p0 A9 R  _2 H    TEA& operator=(const TEA &rhs);
    void encrypt(const byte *in, byte *out);
. l' U, x& f# u/ v, R    void decrypt(const byte *in, byte *out);
$ a5 O3 i% \7 i. P- S' c7 n1 s% Z' lprivate:
    void encrypt(const ulong *in, ulong *out);
1 Y3 a; N5 X/ U    void decrypt(const ulong *in, ulong *out);
& E: C2 M6 y1 u1 q# `* a    ulong ntoh(ulong netlong) { return _isNetByte ? ntohl(netlong) : netlong; }
9 s+ D) H2 ]& X% a% Q( N. F    ulong hton(ulong hostlong) { return _isNetByte ? htonl(hostlong) : hostlong; }
private:
    int _round; //iteration round to encrypt or decrypt
    bool _isNetByte; //whether input bytes come from network
    byte _key[16]; //encrypt or decrypt key
$ t; k: |. g" D. S5 C0 I$ A  o* L};

#endif/*TEA_H*/

天云上人

1 #include "tea.h"
2 #include <cstring> //for memcpy,memset
3  
4 using namespace std;
5  
. X+ x" |! G* U  I2 g/ N/ d# w 6 TEA::TEA(const byte *key, int round /*= 32*/, bool isNetByte /*= false*/)
7 :_round(round)
8 ,_isNetByte(isNetByte) {
" b; r9 U1 W; ^, Q2 {% f 9     if (key != 0)
. }/ F9 [' F8 t4 [/ \1 o( Y: p9 N10         memcpy(_key, key, 16);
2 q4 }: }- U+ S- p; q4 e3 m11     else
- D) J- z) [) n- P5 c12         memset(_key, 0, 16);
  ~  Z* X9 a! m) c/ e" }4 }13 }
4 d- Y' }5 l/ [- U! ]14  
5 B2 x: b) V$ F, w" v# A15 TEA::TEA(const TEA &rhs)
5 B5 |6 M" N) n$ H5 B6 l, ?! q3 _16 :_round(rhs._round)
. [+ _8 o3 D& a17 ,_isNetByte(rhs._isNetByte) {
) k# G* i& r4 S) D8 Q18     memcpy(_key, rhs._key, 16);
  {5 U3 f. m0 l' D6 [  P19 }
9 z5 t9 v7 Q! J9 d$ d20  
21 TEA& TEA::operator=(const TEA &rhs) {
22     if (&rhs != this) {
23         _round = rhs._round;
) C! e5 o5 Q# b24         _isNetByte = rhs._isNetByte;
25         memcpy(_key, rhs._key, 16);
26     }
$ a) ~0 q* Y+ f( W27     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) {
# Y6 Y) V- E1 [) H: K6 j35     decrypt((const ulong*)in, (ulong*)out);
36 }
37  
3 n& E! Z3 V# U8 B# ~38 void TEA::encrypt(const ulong *in, ulong *out) {
39  
1 {2 i4 C# n7 ]( ^. B40     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]);
' _# Z8 W3 ~9 p* C45     register ulong c = ntoh(k[2]);
- {" Y9 A* i* {' f46     register ulong d = ntoh(k[3]);
47     register ulong delta = 0x9E3779B9; /* (sqrt(5)-1)/2*2^32 */
) ?, e) t' \2 h' E6 M) {; t1 I48     register int round = _round;
49     register ulong sum = 0;
1 z7 J+ N, }5 r, p9 A1 p2 J/ t50  
51     while (round--) {    /* basic cycle start */
6 O( z  l* Q: K52         sum += delta;
- S% [5 o) z- F4 k53         y += ((z << 4) + a) ^ (z + sum) ^ ((z >> 5) + b);
54         z += ((y << 4) + c) ^ (y + sum) ^ ((y >> 5) + d);
6 m/ ~' c4 B& O" Y# |9 G& L" K% G55     }    /* end cycle */
% d+ S; K# B' f% }. S3 R& B, j56     out[0] = ntoh(y);
57     out[1] = ntoh(z);
58 }
59  
1 m/ M+ U( {+ P$ j! n. q60 void TEA::decrypt(const ulong *in, ulong *out) {
6 C8 R* R* b' P5 ^" m61  
8 i& u, A8 O. |- B1 x3 H62     ulong *k = (ulong*)_key;
+ U6 u! J) n4 @) F2 R4 S2 ]63     register ulong y = ntoh(in[0]);
+ y6 J2 }0 I4 W* y) ?( Z, l2 C) q64     register ulong z = ntoh(in[1]);
65     register ulong a = ntoh(k[0]);
66     register ulong b = ntoh(k[1]);
9 W' Y5 a4 }" i67     register ulong c = ntoh(k[2]);
68     register ulong d = ntoh(k[3]);
" C- q0 v4 }& s/ K" C. G  M* I69     register ulong delta = 0x9E3779B9; /* (sqrt(5)-1)/2*2^32 */
70     register int round = _round;
' [  c: w4 j3 m0 l71     register ulong sum = 0;
72  
8 U- b  q) {3 D% A. F& I) Q: i/ q7 t73     if (round == 32)
* c6 G" f; ~* v; w  z74         sum = 0xC6EF3720; /* delta << 5*/
  ~6 i: ^; z; K% A75     else if (round == 16)
76         sum = 0xE3779B90; /* delta << 4*/
77     else
78         sum = delta << static_cast<int>(logbase(2, round));
$ R" f/ Y9 m0 x6 S79  
80     while (round--) {    /* basic cycle start */
81         z -= ((y << 4) + c) ^ (y + sum) ^ ((y >> 5) + d);
: B* P- g0 }( D2 Y3 Z4 O82         y -= ((z << 4) + a) ^ (z + sum) ^ ((z >> 5) + b);
83         sum -= delta;
84     }    /* end cycle */
. U5 z/ `. `4 X* F# O5 r' H" g85     out[0] = ntoh(y);
86     out[1] = ntoh(z);
87 }

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

( w' X) ?1 ~+ W最后当然少不了测试代码：

天云上人

1 #include "tea.h"
8 B( J0 c) f' P5 F% g! g 2 #include "util.h"
3 #include <iostream>
  i0 O- c9 W" d; N 4  
: j+ b+ j  X9 Z# F8 |) A; i3 n 5 using namespace std;
6  
# \, ~" f) V& _% f# G% h6 B, Z 7 int main() {
8  
4 X6 ?, w* J# A: m+ E 9     const string plainStr("AD DE E2 DB B3 E2 DB B3");
4 O2 q+ ?& w# H10     const string keyStr("3A DA 75 21 DB E2 DB B3 11 B4 49 01 A5 C6 EA D4");
$ _& E6 X' R, q& W, n% _11     const int SIZE_IN = 8, SIZE_OUT = 8, SIZE_KEY = 16;
  G0 W. \6 G4 H; {" B- ]12     byte plain[SIZE_IN], crypt[SIZE_OUT], key[SIZE_KEY];
13  
0 Z/ B7 O2 f- K+ ]& X( L0 x14     size_t size_in = hexStringToBytes(plainStr, plain);
15     size_t size_key = hexStringToBytes(keyStr, key);
16  
9 S2 J+ z' `+ [17     if (size_in != SIZE_IN || size_key != SIZE_KEY)
18         return -1;
19  
' x+ x- r6 J* D20     cout << "Plain: " << bytesToHexString(plain, size_in) << endl;
3 ?! r) X( z0 q21     cout << "Key  : " << bytesToHexString(key, size_key) << endl;
+ Q+ }: t1 {( U. Z! p2 j22  
23     TEA tea(key, 16, true);
24     tea.encrypt(plain, crypt);
7 G1 @# {$ x) \25     cout << "Crypt: " << bytesToHexString(crypt, SIZE_OUT) << endl;
26  
5 D% ?; K7 y. j27     tea.decrypt(crypt, plain);
! C, O( ~% b3 l7 o" V& l28     cout << "Plain: " << bytesToHexString(plain, SIZE_IN) << endl;
; R. J6 t4 d1 `+ @8 A29     return 0;
1 Y5 \9 O" E1 `% c: x( K30 }
" f0 Y4 k* F$ ]7 M% i
本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/sailing0123/archive/2008/04/28/2339231.aspx
运行结果：
' L3 T4 X; R9 c% N" P* H3 U, P) MPlain: 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