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） 都是分组加密算法，它们很容易被描述，实现也很简单（典型的几行代码）。
- Q$ L% T! U) ZTEA 算法最初是由剑桥计算机实验室的 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. 
   " C' N2 e5 {8 }& A$ @
2. void encrypt(unsigned long *v, unsigned long *k) {
   
3.      unsigned long y=v[0], z=v[1], sum=0, i;         /* set up */
   
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 */
   . K2 e2 h; [, v5 @4 C
6.      for (i=0; i < 32; i++) {                        /* basic cycle start */
   . V0 R9 v) w- C
7.          sum += delta;
   5 P$ }% Y( V$ e, B2 E  R7 z3 ]
8.          y += ((z<<4) + a) ^ (z + sum) ^ ((z>>5) + b);
   
9.          z += ((y<<4) + c) ^ (y + sum) ^ ((y>>5) + d);/* end cycle */
   
10.      }
    + Z5 ?* D' x1 F" s# ]
11.      v[0]=y;
    - |, O+ J- a. Q3 S
12.      v[1]=z;
    
13. }
    2 L6 i+ f/ Y- u/ j
14.   
    
15. void decrypt(unsigned long *v, unsigned long *k) {
    
16.      unsigned long y=v[0], z=v[1], sum=0xC6EF3720, i; /* set up */
    / \; z4 I% w$ f, C# Y0 @3 P
17.      unsigned long delta=0x9e3779b9;                  /* a key schedule constant */
    1 E/ F( R6 B& I' [
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);
    & f0 j, j. p; _0 Q; a
21.          y -= ((z<<4) + a) ^ (z + sum) ^ ((z>>5) + b);
    
22.          sum -= delta;                                /* end cycle */
    " i# D+ {: i4 T4 U$ `( a
23.      }
    
24.      v[0]=y;
    
25.      v[1]=z;
    + p& |+ ?/ D  M* N, G& ]' F; V
26. }
    0 {) T! h. M7 B% I0 l

复制代码

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

天云上人

#ifndef UTIL_H
# I9 _- p2 }8 a) d) f: Z4 [#define UTIL_H
7 L0 F+ G9 A% v- H1 u- v
: x. ?( R7 y. L9 C, l+ ]4 I#include <string>
#include <cmath>
# B! m8 E5 E0 `- x#include <cstdlib>
$ s8 }' A, E2 `4 x2 ]
% G3 G: a# R8 e3 L5 Htypedef unsigned char byte;
! h+ M$ b: v8 f0 ?typedef unsigned long ulong;
5 O6 `( n) ^6 E4 k
inline double logbase(double base, double x) {
$ G& Y/ g/ o3 H2 Z, N: I  [    return log(x)/log(base);
/ f- k. ]6 N: V4 b# h# d: C}
6 r& l7 O; c6 g( k
/*
+ q0 @8 L, I( y*convert int to hex char.
1 O/ F- L0 I+ i*example:10 -> 'A',15 -> 'F'
*/
char intToHexChar(int x);

/*
*convert hex char to int.
  u/ ]+ C. N& J5 y! ~* P) e*example:'A' -> 10,'F' -> 15
*/
int hexCharToInt(char hex);

( ~: n' q2 }' v) Y; }5 R  p: k) Nusing 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);

/*
4 V0 h" C5 V3 H- X1 L; s4 i+ W*convert a hex string to a byte array.
*hex string format example:"AF B0 80 7D"
7 K& h6 [9 N5 c& I! ?*/
size_t hexStringToBytes(const string &str, byte *out);

. ~8 D9 M" ?- I#endif/*UTIL_H*/

天云上人

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

) N0 ?( u2 I) L. C* d3 Q& o3 qusing namespace std;

char intToHexChar(int x) {
& r1 I, a; R+ y" L- i: C    static const char HEX[16] = {
* t: A) |, L9 ^) K        '0', '1', '2', '3',
        '4', '5', '6', '7',
        '8', '9', 'A', 'B',
4 K- l0 H- ~2 a  {% C2 A; R, E% X        'C', 'D', 'E', 'F'
5 ]7 _, u# _1 T* M5 y$ p; }    };
    return HEX[x];
}
& S1 o$ g: E9 y* P: c
int hexCharToInt(char hex) {
& X) I/ m1 n' t# k# Z    hex = toupper(hex);
    if (isdigit(hex))
        return (hex - '0');
4 i* o7 Z6 q4 s    if (isalpha(hex))
) A5 q" S9 \$ f        return (hex - 'A' + 10);
2 C3 F0 N; G6 z    return 0;
}

' Z& F. N/ V) }1 H9 c5 ^/ |+ [4 Nstring bytesToHexString(const byte *in, size_t size) {
+ P. ]9 ]3 ]4 H$ E    string str;
    for (size_t i = 0; i < size; ++i) {
        int t = in[i];
. _! J$ l7 [* f4 ~' _8 m        int a = t / 16;
        int b = t % 16;
        str.append(1, intToHexChar(a));
        str.append(1, intToHexChar(b));
        if (i != size - 1)
            str.append(1, ' ');
    }
    return str;
}

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) {
# s& P6 S$ Z- _# X        string b(str.substr(prevPos, currPos - prevPos));
; X) p% b2 C4 f" N% u' t9 y6 \        vec.push_back(b);
        prevPos = currPos + 1;
3 n, ^' {/ N6 j- L    }
    if (prevPos < str.size()) {
        string b(str.substr(prevPos));
0 Z- r, t. m6 g        vec.push_back(b);
    }
    typedef vector<string>::size_type sz_type;
    sz_type size = vec.size();
    for (sz_type i = 0; i < size; ++i) {
4 h( I8 i5 i) i  i, l2 |        int a = hexCharToInt(vec[i][0]);
; q/ L) C+ ?. C2 o+ r& }        int b = hexCharToInt(vec[i][1]);
        out[i] = a * 16 + b;
    }
4 f+ y  v, U; T! d* S( z4 ?9 ~    return size;
+ U6 Z0 H; X6 A* b}

天云上人

#ifndef TEA_H
8 Z1 q# U( [7 b" q  f#define TEA_H

# e# x, f7 ]( C+ ]# s: Z9 N4 C% p! d/*
$ E2 {0 P- h% D- L*for htonl,htonl
*do remember link "ws2_32.lib"
*/
! G  E# e! I$ S, M- }5 n7 p% ?#include <winsock2.h>
9 K, s2 I, k5 P1 }7 p' d#include "util.h"

" k; q' ?# G0 N4 e, Lclass TEA {
public:
0 b0 v' S+ ^% u* ?. e; a    TEA(const byte *key, int round = 32, bool isNetByte = false);
" k( P8 F$ a0 I0 T  _    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);
  }# s6 |( E1 z/ K, e& ~9 _    void decrypt(const ulong *in, ulong *out);
% I  O9 C0 p- A1 G' i! ~    ulong ntoh(ulong netlong) { return _isNetByte ? ntohl(netlong) : netlong; }
. p; q# J- V% {4 M+ P    ulong hton(ulong hostlong) { return _isNetByte ? htonl(hostlong) : hostlong; }
private:
    int _round; //iteration round to encrypt or decrypt
5 Z1 B! x9 i" R8 {    bool _isNetByte; //whether input bytes come from network
4 I! a% d- P, z    byte _key[16]; //encrypt or decrypt key
};
' X/ V) f! ~4 z+ _+ _1 ]. O; s$ K6 D6 L
1 N0 h7 s! m$ w: m' K4 K3 s1 I8 _#endif/*TEA_H*/

天云上人

1 #include "tea.h"
2 #include <cstring> //for memcpy,memset
3  
0 k5 ~9 Y( a* {) y# s 4 using namespace std;
5  
! o: \9 Z. N: J2 }% A" {) O 6 TEA::TEA(const byte *key, int round /*= 32*/, bool isNetByte /*= false*/)
: u/ {$ V+ p. K6 H4 \0 o5 {# w* z 7 :_round(round)
8 ,_isNetByte(isNetByte) {
9     if (key != 0)
10         memcpy(_key, key, 16);
11     else
8 S8 V8 f1 |- S3 k8 O12         memset(_key, 0, 16);
2 k, R% M/ [( D0 n3 e* v13 }
8 [  B6 W9 T5 R5 D0 f$ @2 G* d1 q14  
- y& P) R; @" N2 S' G15 TEA::TEA(const TEA &rhs)
  I. T7 O4 j7 \: y* i16 :_round(rhs._round)
& n% m/ A! a/ f. ?5 {17 ,_isNetByte(rhs._isNetByte) {
  G0 r$ o' u. ]  J4 Q7 l* Z5 [18     memcpy(_key, rhs._key, 16);
19 }
20  
21 TEA& TEA::operator=(const TEA &rhs) {
22     if (&rhs != this) {
; A) a8 A( A! p, Y$ `23         _round = rhs._round;
4 ]3 u( p, s2 n& {1 u24         _isNetByte = rhs._isNetByte;
7 Y9 O5 r/ v% X- @% o. I25         memcpy(_key, rhs._key, 16);
26     }
" D) M1 d# a5 m27     return *this;
28 }
% G2 w8 h- @/ Z29  
% n% E* ?, m" b30 void TEA::encrypt(const byte *in, byte *out) {
3 Q4 T: F! W7 _+ U! i9 T4 c, E1 A) ], b) z31     encrypt((const ulong*)in, (ulong*)out);
32 }
33  
34 void TEA::decrypt(const byte *in, byte *out) {
35     decrypt((const ulong*)in, (ulong*)out);
7 f/ J* g, w" y. Y36 }
  R" t: @: s0 O3 Z37  
38 void TEA::encrypt(const ulong *in, ulong *out) {
39  
40     ulong *k = (ulong*)_key;
41     register ulong y = ntoh(in[0]);
) e: ?- Y8 K7 s" K9 t# n6 l42     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]);
( T% d; {% l* s. y' Z0 r46     register ulong d = ntoh(k[3]);
47     register ulong delta = 0x9E3779B9; /* (sqrt(5)-1)/2*2^32 */
- Y& y; f$ W7 }( }1 c: f9 A. }2 ]48     register int round = _round;
49     register ulong sum = 0;
/ |8 N; r# L# r0 a. {: [' o! l4 w50  
! J2 p, y2 n# s5 a51     while (round--) {    /* basic cycle start */
; D! z# R* U' y52         sum += delta;
53         y += ((z << 4) + a) ^ (z + sum) ^ ((z >> 5) + b);
, X; n: x% `4 W$ [# f+ c2 Z. h54         z += ((y << 4) + c) ^ (y + sum) ^ ((y >> 5) + d);
55     }    /* end cycle */
56     out[0] = ntoh(y);
57     out[1] = ntoh(z);
58 }
/ M' U2 |: P, o5 q6 }0 s59  
60 void TEA::decrypt(const ulong *in, ulong *out) {
61  
62     ulong *k = (ulong*)_key;
) z8 z; U1 f3 F3 l0 W( _1 w63     register ulong y = ntoh(in[0]);
64     register ulong z = ntoh(in[1]);
' j5 \0 `" y7 R; E1 c6 R65     register ulong a = ntoh(k[0]);
66     register ulong b = ntoh(k[1]);
67     register ulong c = ntoh(k[2]);
0 E* [0 V7 o7 j9 b7 r- q# p68     register ulong d = ntoh(k[3]);
69     register ulong delta = 0x9E3779B9; /* (sqrt(5)-1)/2*2^32 */
70     register int round = _round;
' Y: n+ a6 ]' L: B2 o" j, o71     register ulong sum = 0;
72  
# C' r4 j1 Q  ?73     if (round == 32)
) n' n) [5 G$ V74         sum = 0xC6EF3720; /* delta << 5*/
, _& F3 e: q2 y" {8 O8 s5 h/ ?75     else if (round == 16)
76         sum = 0xE3779B90; /* delta << 4*/
# f/ g0 G. m& e5 p8 {9 _77     else
$ p: d$ ]  p. U# X6 r78         sum = delta << static_cast<int>(logbase(2, round));
, q6 E$ x. f2 n/ V* {79  
80     while (round--) {    /* basic cycle start */
0 I/ G4 y% N8 A+ g3 h9 c( g81         z -= ((y << 4) + c) ^ (y + sum) ^ ((y >> 5) + d);
8 @: N( Y7 _: x( ?82         y -= ((z << 4) + a) ^ (z + sum) ^ ((z >> 5) + b);
83         sum -= delta;
84     }    /* end cycle */
8 E/ e: O2 G' z  B7 V4 S85     out[0] = ntoh(y);
4 F% ~9 L: ~: ?1 `. x2 w9 T7 f86     out[1] = ntoh(z);
87 }
1 ~- H( j5 U8 [/ U; i* V7 W' I3 V
需要说明的是TEA的构造函数：
8 G; l& t/ z3 l0 ^: STEA(const byte *key, int round = 32, bool isNetByte = false);
1.key - 加密或解密用的128-bit(16byte)密钥。
) |% q3 S* _; W1 E5 b" ]& y! i7 k2.round - 加密或解密的轮数，常用的有64，32，16。
3.isNetByte - 用来标记待处理的字节是不是来自网络，为true时在加密/解密前先要转换成本地字节，执行加密/解密，然后再转换回网络字节。偷偷告诉你，QQ就是这样做的！

9 m9 f2 X+ w* u% k/ E- M& s! h最后当然少不了测试代码：

天云上人

1 #include "tea.h"
2 #include "util.h"
3 #include <iostream>
4  
5 using namespace std;
+ O/ f# {+ G- h 6  
8 W9 C4 V0 u8 ]2 J; g( c4 X 7 int main() {
8  
8 H2 `5 K  `1 ]- K7 C1 v 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");
" ~& l! ~2 N5 k. n6 A11     const int SIZE_IN = 8, SIZE_OUT = 8, SIZE_KEY = 16;
12     byte plain[SIZE_IN], crypt[SIZE_OUT], key[SIZE_KEY];
13  
6 u$ m! G0 [# b2 X1 ^( V14     size_t size_in = hexStringToBytes(plainStr, plain);
: S9 v! u. E+ d, i. _2 O5 n2 f  `15     size_t size_key = hexStringToBytes(keyStr, key);
16  
17     if (size_in != SIZE_IN || size_key != SIZE_KEY)
18         return -1;
* W9 }) p, P. A% w3 S- P19  
4 i5 f  c& v: B5 ?8 c# O20     cout << "Plain: " << bytesToHexString(plain, size_in) << endl;
21     cout << "Key  : " << bytesToHexString(key, size_key) << endl;
/ |+ H3 f; P$ E5 M22  
4 d- C+ \1 Y* K7 C, M23     TEA tea(key, 16, true);
24     tea.encrypt(plain, crypt);
! H  X5 t% N/ J25     cout << "Crypt: " << bytesToHexString(crypt, SIZE_OUT) << endl;
26  
27     tea.decrypt(crypt, plain);
28     cout << "Plain: " << bytesToHexString(plain, SIZE_IN) << endl;
! c% \9 a5 C# B% V  G1 p29     return 0;
30 }
* @$ v8 E. b+ O6 u8 y' O
本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/sailing0123/archive/2008/04/28/2339231.aspx
* @( u" S. N* o& f. U! d( Q0 V9 C运行结果：
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
+ r, A! B; v3 F8 tCrypt: 3B 3B 4D 8C 24 3A FD F2
+ B2 w) u* }* B9 ~3 IPlain: AD DE E2 DB B3 E2 DB B3