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

血刀老祖

TEA(Tiny Encryption Algorithm) 是一种简单高效的加密算法，以加密解密速度快，实现简单著称。算法真的很简单，TEA算法每一次可以操作64-bit(8-byte)，采用128-bit(16-byte)作为key，算法采用迭代的形式，推荐的迭代轮数是64轮，最少32轮。目前我只知道QQ一直用的是16轮TEA。没什么好说的，先给出C语言的源代码(默认是32轮)：
微型加密算法（TEA）及其相关变种（XTEA，Block TEA，XXTEA） 都是分组加密算法，它们很容易被描述，实现也很简单（典型的几行代码）。
4 O1 n- O3 n' t) p& MTEA 算法最初是由剑桥计算机实验室的 David Wheeler 和 Roger Needham 在 1994 年设计的。该算法使用 128 位的密钥为 64 位的信息块进行加密，它需要进行 64 轮迭代，尽管作者认为 32 轮已经足够了。该算法使用了一个神秘常数δ作为倍数，它来源于黄金比率，以保证每一轮加密都不相同。但δ的精确值似乎并不重要，这里 TEA 把它定义为 δ=「(√5 - 1)231」（也就是程序中的 0×9E3779B9）。
2 L4 s: V) U& X7 T" W5 q, P2 a2 p之后 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. 
   
2. void encrypt(unsigned long *v, unsigned long *k) {
   
3.      unsigned long y=v[0], z=v[1], sum=0, i;         /* set up */
   & e- l2 G7 Z- X% I) X
4.      unsigned long delta=0x9e3779b9;                 /* a key schedule constant */
   : K! b2 _- q7 X, F0 m$ m5 z- X- t
5.      unsigned long a=k[0], b=k[1], c=k[2], d=k[3];   /* cache key */
   ; K& X" T  q5 O
6.      for (i=0; i < 32; i++) {                        /* basic cycle start */
   
7.          sum += delta;
   
8.          y += ((z<<4) + a) ^ (z + sum) ^ ((z>>5) + b);
   / u: [/ L& S' e9 Q4 h& h  h
9.          z += ((y<<4) + c) ^ (y + sum) ^ ((y>>5) + d);/* end cycle */
   / f( C- i0 W% W( @% W# V0 Z, E- |
10.      }
    
11.      v[0]=y;
    7 ]' Z0 o- h' P/ F: m( Y+ x% H
12.      v[1]=z;
    
13. }
    . G$ a. Z% ^+ C; X: N- D( F
14.   
    * G, f# w3 D, ]1 k9 h+ v2 z
15. void decrypt(unsigned long *v, unsigned long *k) {
    2 \2 q$ F. i9 x9 A6 k% {2 P* O8 h. l
16.      unsigned long y=v[0], z=v[1], sum=0xC6EF3720, i; /* set up */
    ! n1 l) M" W6 U0 A4 m7 ^
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 */
    + h1 f3 |; g: h
19.      for(i=0; i<32; i++) {                            /* basic cycle start */
    
20.          z -= ((y<<4) + c) ^ (y + sum) ^ ((y>>5) + d);
    2 q" p. H9 d0 _1 ?& s; x- G
21.          y -= ((z<<4) + a) ^ (z + sum) ^ ((z>>5) + b);
    % W3 b$ F( K3 f' I9 d) Z
22.          sum -= delta;                                /* end cycle */
    1 u/ B4 ?$ o6 d) T4 `0 w
23.      }
    
24.      v[0]=y;
    
25.      v[1]=z;
    
26. }
    * r/ b; c" _8 N. L+ c

复制代码

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

天云上人

#ifndef UTIL_H
# B7 z3 t7 w9 w2 h#define UTIL_H
" y2 `1 b% D, O7 Q. j
#include <string>
) W) G' x/ X4 n; B! K8 n#include <cmath>
5 I9 ^+ t9 G1 I* h#include <cstdlib>
6 `3 m# h2 r0 q! l$ s2 `8 E
typedef unsigned char byte;
2 @. i, x, {: Ntypedef unsigned long ulong;

$ m. J3 E1 p9 ]" _, u6 }; |inline double logbase(double base, double x) {
1 w6 I3 g9 @' H: @. N; m    return log(x)/log(base);
5 g1 ?; ^- S9 l$ n2 E/ h  c/ l0 W+ Q}
! Z  J4 j3 `" _3 n6 Z
/*
) D$ c5 D8 h8 \) u9 S*convert int to hex char.
*example:10 -> 'A',15 -> 'F'
*/
; i% u8 X9 i2 ^) P+ t' r* Cchar intToHexChar(int x);

/*
; }* u2 n: k$ x8 V$ L*convert hex char to int.
*example:'A' -> 10,'F' -> 15
, x, L* D( w, i2 c) s3 Y# o*/
int hexCharToInt(char hex);

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

  B) L# L4 O: W$ u, w" @7 R  q/*
*convert a hex string to a byte array.
*hex string format example:"AF B0 80 7D"
% ?3 Z. B9 x* a9 p*/
size_t hexStringToBytes(const string &str, byte *out);

#endif/*UTIL_H*/

天云上人

#include "util.h"
#include <vector>
' X* C( b- i1 s9 `, b& P, F3 n
using namespace std;

4 }3 G4 n4 o0 t- k7 |: Bchar intToHexChar(int x) {
. X1 U7 Y8 `0 Y4 l    static const char HEX[16] = {
- o  A6 r6 M+ X# D( C4 ]; Y4 a5 \        '0', '1', '2', '3',
        '4', '5', '6', '7',
) _* L! t0 g* ~. ]! x8 m        '8', '9', 'A', 'B',
        'C', 'D', 'E', 'F'
( e/ e* u7 I- M, ~& k1 |    };
    return HEX[x];
}
% h7 W+ {% M$ j9 ]. K
int hexCharToInt(char hex) {
    hex = toupper(hex);
    if (isdigit(hex))
/ S- [8 v- N5 b2 T2 H4 z6 y        return (hex - '0');
1 d) k( Y& |3 S; }1 F$ ]    if (isalpha(hex))
9 h4 F0 k8 T0 A        return (hex - 'A' + 10);
* P) C1 W7 U2 h5 h6 e& y    return 0;
}

string bytesToHexString(const byte *in, size_t size) {
1 o  G' x) Z( g. u2 R/ I    string str;
- A6 c9 H' J3 q6 ~) n    for (size_t i = 0; i < size; ++i) {
* J/ t% ^' B( Y3 U# l        int t = in[i];
        int a = t / 16;
        int b = t % 16;
        str.append(1, intToHexChar(a));
        str.append(1, intToHexChar(b));
        if (i != size - 1)
9 h* @" l' S* D- E3 w" t            str.append(1, ' ');
' J+ v6 q$ z% B  }/ Y: L+ R    }
    return str;
}
9 K) c7 `; T" m3 V, I
, S$ H% c# h( R9 {4 x' {9 f1 Qsize_t hexStringToBytes(const string &str, byte *out) {
# C# n) Y3 z' K" ^; T2 o; E
: A. L* U) S9 l, G! i" M    vector<string> vec;
* L0 U; w7 O6 y8 D7 u) D9 Z    string::size_type currPos = 0, prevPos = 0;
    while ((currPos = str.find(' ', prevPos)) != string::npos) {
  _+ S; N/ \: E        string b(str.substr(prevPos, currPos - prevPos));
  h2 ^8 P2 L9 G9 o  J: e  Z2 t        vec.push_back(b);
        prevPos = currPos + 1;
    }
    if (prevPos < str.size()) {
        string b(str.substr(prevPos));
* p5 h) J* O' n) i. J        vec.push_back(b);
    }
    typedef vector<string>::size_type sz_type;
3 X& m/ a" o. ?  e# {, r5 D! F  s    sz_type size = vec.size();
8 h" V, F3 a/ ^; x5 V; ~    for (sz_type i = 0; i < size; ++i) {
        int a = hexCharToInt(vec[i][0]);
  ^/ X. l1 P! @8 _        int b = hexCharToInt(vec[i][1]);
. C  X5 K: o) U7 b& x        out[i] = a * 16 + b;
" q& w( z1 j5 r    }
9 ~% t6 a3 |8 T3 G, q    return size;
+ {) g4 l" I0 z; [, j2 T( ?" q}

天云上人

#ifndef TEA_H
8 Z# h. D" m9 }) w! `7 _3 k#define TEA_H
" T; Z) R" r9 |% J: ^; ?
# f7 s* w) H% h0 _/*
*for htonl,htonl
*do remember link "ws2_32.lib"
*/
* v0 m5 [( ?2 P9 c1 r) X#include <winsock2.h>
#include "util.h"
5 O+ I; |7 ]6 a) U2 A& r  u! J
# A6 b" l6 ]$ j  _; Q( Pclass TEA {
public:
    TEA(const byte *key, int round = 32, bool isNetByte = false);
    TEA(const TEA &rhs);
+ m$ C3 t" f5 m7 w% v    TEA& operator=(const TEA &rhs);
    void encrypt(const byte *in, byte *out);
    void decrypt(const byte *in, byte *out);
' t4 j9 n4 W; C$ I( o6 K) `2 s( S0 pprivate:
+ N7 F0 f$ t/ n' b6 u0 n% N    void encrypt(const ulong *in, ulong *out);
    void decrypt(const ulong *in, ulong *out);
; L. N7 s% d4 m) i    ulong ntoh(ulong netlong) { return _isNetByte ? ntohl(netlong) : netlong; }
, ]! l+ [  Y( n    ulong hton(ulong hostlong) { return _isNetByte ? htonl(hostlong) : hostlong; }
private:
    int _round; //iteration round to encrypt or decrypt
) G% a  D: b, K  H: m0 ^! A1 s    bool _isNetByte; //whether input bytes come from network
! Z% S' [7 t" n4 q1 S9 @    byte _key[16]; //encrypt or decrypt key
};

#endif/*TEA_H*/

天云上人

1 #include "tea.h"
2 #include <cstring> //for memcpy,memset
, c9 }% h6 s* c& S% h# E 3  
$ j4 l: z6 Z; }' a- z& {; a5 C 4 using namespace std;
5  
7 s7 b# ^7 N. P" S 6 TEA::TEA(const byte *key, int round /*= 32*/, bool isNetByte /*= false*/)
( F  B0 z" T* i+ \2 T/ P 7 :_round(round)
8 ,_isNetByte(isNetByte) {
9     if (key != 0)
7 U2 L6 K, _- {5 E' @8 K8 c10         memcpy(_key, key, 16);
11     else
12         memset(_key, 0, 16);
' L/ w; B$ s: Y7 R13 }
14  
' X. |5 d; r) m* u15 TEA::TEA(const TEA &rhs)
16 :_round(rhs._round)
# v$ F6 G- [. f, T9 k/ }17 ,_isNetByte(rhs._isNetByte) {
7 |' ]! x7 B- M+ _7 C" k$ V18     memcpy(_key, rhs._key, 16);
19 }
! v1 j8 B" q  P  Q) C& i+ w/ q20  
21 TEA& TEA::operator=(const TEA &rhs) {
22     if (&rhs != this) {
23         _round = rhs._round;
, l8 w4 l, }( o# W1 L9 n7 _# M24         _isNetByte = rhs._isNetByte;
/ {  |) o) Z8 P. s6 ~" n25         memcpy(_key, rhs._key, 16);
1 d  I7 s9 m" E26     }
% x: Q( E& {5 H+ v27     return *this;
28 }
29  
30 void TEA::encrypt(const byte *in, byte *out) {
( s. h) r. a+ X' q" s/ O8 n31     encrypt((const ulong*)in, (ulong*)out);
32 }
33  
0 }* ?3 I& _4 @8 z34 void TEA::decrypt(const byte *in, byte *out) {
  V1 q! B; ^8 h# B2 z35     decrypt((const ulong*)in, (ulong*)out);
36 }
37  
38 void TEA::encrypt(const ulong *in, ulong *out) {
+ {0 W% p' r% {1 Z) O9 p1 y39  
40     ulong *k = (ulong*)_key;
7 S: H- G: D) e' C41     register ulong y = ntoh(in[0]);
42     register ulong z = ntoh(in[1]);
$ Q" v) e* @6 s0 ~8 F! P- e& d3 e43     register ulong a = ntoh(k[0]);
44     register ulong b = ntoh(k[1]);
45     register ulong c = ntoh(k[2]);
+ x6 K+ C. b( w3 e46     register ulong d = ntoh(k[3]);
47     register ulong delta = 0x9E3779B9; /* (sqrt(5)-1)/2*2^32 */
/ v0 X7 B+ r/ L& e$ I7 Z48     register int round = _round;
49     register ulong sum = 0;
50  
51     while (round--) {    /* basic cycle start */
52         sum += delta;
, T  z" _) J. x) O% E; o; }5 k53         y += ((z << 4) + a) ^ (z + sum) ^ ((z >> 5) + b);
  k" q$ E# M, |" X+ s0 M% m$ K54         z += ((y << 4) + c) ^ (y + sum) ^ ((y >> 5) + d);
55     }    /* end cycle */
56     out[0] = ntoh(y);
4 `( [2 j4 s/ \" Z3 O2 G57     out[1] = ntoh(z);
58 }
: L) v3 D7 _" o4 `59  
60 void TEA::decrypt(const ulong *in, ulong *out) {
8 _5 w- ], l$ ^+ m" X' Q61  
62     ulong *k = (ulong*)_key;
+ E, E0 o/ l* n. n4 Q63     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]);
& M0 _$ I4 R; H2 Z8 i/ a67     register ulong c = ntoh(k[2]);
7 D0 U* |, J: g& s  u$ J! S68     register ulong d = ntoh(k[3]);
1 F5 k* d/ L6 x% w: ^9 K69     register ulong delta = 0x9E3779B9; /* (sqrt(5)-1)/2*2^32 */
70     register int round = _round;
/ T, \- M, B5 l: R  S& K9 R5 F* s1 L71     register ulong sum = 0;
72  
( x! H( T' y6 y7 b( Z4 a73     if (round == 32)
74         sum = 0xC6EF3720; /* delta << 5*/
75     else if (round == 16)
7 U2 F  C9 j/ Z$ e3 q- F76         sum = 0xE3779B90; /* delta << 4*/
5 F% @9 h# D0 g* z5 K77     else
+ q  y) l1 o; k4 }78         sum = delta << static_cast<int>(logbase(2, round));
$ E' V2 M, Y4 @+ L3 @79  
2 P. a9 B4 r* Y) H4 b7 d80     while (round--) {    /* basic cycle start */
! H8 [/ g" e" |( n81         z -= ((y << 4) + c) ^ (y + sum) ^ ((y >> 5) + d);
$ N* }$ E' e4 _7 c3 e1 y82         y -= ((z << 4) + a) ^ (z + sum) ^ ((z >> 5) + b);
7 D/ r" n! D5 ~/ F3 n83         sum -= delta;
6 N6 v$ |$ B. g* X0 W& C84     }    /* end cycle */
+ y3 P7 T1 {- p* z85     out[0] = ntoh(y);
86     out[1] = ntoh(z);
87 }
! s4 w& {( A! y
, Z# D- J& i3 r需要说明的是TEA的构造函数：
% b0 g' A; F2 H7 A2 zTEA(const byte *key, int round = 32, bool isNetByte = false);
; y$ g7 ^. U$ k7 f5 W# }; }# C1.key - 加密或解密用的128-bit(16byte)密钥。
2.round - 加密或解密的轮数，常用的有64，32，16。
3.isNetByte - 用来标记待处理的字节是不是来自网络，为true时在加密/解密前先要转换成本地字节，执行加密/解密，然后再转换回网络字节。偷偷告诉你，QQ就是这样做的！

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

天云上人

1 #include "tea.h"
2 #include "util.h"
2 D: x/ e  P( \: l 3 #include <iostream>
4  
5 using namespace std;
6  
; |( t6 t# ]4 r2 o. ^' n 7 int main() {
8  
9     const string plainStr("AD DE E2 DB B3 E2 DB B3");
. F5 C* ]$ K& H10     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;
) H$ R. r/ d' y' C* s# m0 a, t; i12     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  
2 L7 k8 O7 q" t; v17     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);
$ N$ F; n; x4 a1 Q! e24     tea.encrypt(plain, crypt);
3 g; c' k* B% G' G" ~2 ]: B25     cout << "Crypt: " << bytesToHexString(crypt, SIZE_OUT) << endl;
, s! ~3 J! ~  M. A26  
27     tea.decrypt(crypt, plain);
1 V$ _$ b1 m( U$ i8 N* T28     cout << "Plain: " << bytesToHexString(plain, SIZE_IN) << endl;
29     return 0;
+ d9 C+ ]. h3 i* R( j0 W30 }
' b. u: R) ~1 z" g
- H/ v3 j$ t: |3 o. |本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/sailing0123/archive/2008/04/28/2339231.aspx
运行结果：
" l$ @& k0 L* X1 L3 U7 lPlain: 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