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

血刀老祖

TEA(Tiny Encryption Algorithm) 是一种简单高效的加密算法，以加密解密速度快，实现简单著称。算法真的很简单，TEA算法每一次可以操作64-bit(8-byte)，采用128-bit(16-byte)作为key，算法采用迭代的形式，推荐的迭代轮数是64轮，最少32轮。目前我只知道QQ一直用的是16轮TEA。没什么好说的，先给出C语言的源代码(默认是32轮)：
0 T1 E% k- A# A" {微型加密算法（TEA）及其相关变种（XTEA，Block TEA，XXTEA） 都是分组加密算法，它们很容易被描述，实现也很简单（典型的几行代码）。
TEA 算法最初是由剑桥计算机实验室的 David Wheeler 和 Roger Needham 在 1994 年设计的。该算法使用 128 位的密钥为 64 位的信息块进行加密，它需要进行 64 轮迭代，尽管作者认为 32 轮已经足够了。该算法使用了一个神秘常数δ作为倍数，它来源于黄金比率，以保证每一轮加密都不相同。但δ的精确值似乎并不重要，这里 TEA 把它定义为 δ=「(√5 - 1)231」（也就是程序中的 0×9E3779B9）。
2 _$ ?9 M7 a% h" _; q9 s- a0 V& @之后 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. 
   3 H4 E- I& B% v9 X/ e
2. void encrypt(unsigned long *v, unsigned long *k) {
   / q# Q$ {, I$ i  ~# N  c: `
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 */
   
6.      for (i=0; i < 32; i++) {                        /* basic cycle start */
   2 R4 y- A; t$ H  e. Y
7.          sum += delta;
   
8.          y += ((z<<4) + a) ^ (z + sum) ^ ((z>>5) + b);
   1 s2 I0 {" g+ @/ Z3 s
9.          z += ((y<<4) + c) ^ (y + sum) ^ ((y>>5) + d);/* end cycle */
   - w  U+ x8 m: K& J5 B
10.      }
    
11.      v[0]=y;
    
12.      v[1]=z;
    
13. }
    
14.   
    
15. void decrypt(unsigned long *v, unsigned long *k) {
    1 @: k; @! e4 x; U
16.      unsigned long y=v[0], z=v[1], sum=0xC6EF3720, i; /* set up */
    # f6 y/ {" j1 W1 n" z/ d9 w2 z
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 */
    ( _+ ?4 X& k( L1 K  \7 s
20.          z -= ((y<<4) + c) ^ (y + sum) ^ ((y>>5) + d);
    . L% l5 e( d8 f2 y  l9 t
21.          y -= ((z<<4) + a) ^ (z + sum) ^ ((z>>5) + b);
    
22.          sum -= delta;                                /* end cycle */
    4 d% F9 z1 S0 {# E
23.      }
    
24.      v[0]=y;
    
25.      v[1]=z;
    
26. }
    ; \$ _- v( t& n" S, P6 o% D

复制代码

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

天云上人

#ifndef UTIL_H
#define UTIL_H

#include <string>
#include <cmath>
+ x8 K: I7 E' T8 M* N#include <cstdlib>

typedef unsigned char byte;
typedef unsigned long ulong;
* z6 R+ j7 ?& O* b% _
inline double logbase(double base, double x) {
    return log(x)/log(base);
% w$ D8 o! A- W9 d, \8 {; O}

2 c2 Z& @& Y" s5 i/*
*convert int to hex char.
*example:10 -> 'A',15 -> 'F'
' n2 ^0 [  ^- f# b*/
char intToHexChar(int x);

/*
) x& G" v; s' Z/ ]*convert hex char to int.
*example:'A' -> 10,'F' -> 15
*/
int hexCharToInt(char hex);

% F' r% m% {  a+ _6 C! t$ @" nusing std::string;
- T0 _( O) U6 W# t% h  n) d/*
*convert a byte array to hex string.
" {& W  }* Q8 ]! a  C*hex string format example:"AF B0 80 7D"
0 c$ o: z- B5 m) ~2 \1 f*/
string bytesToHexString(const byte *in, size_t size);
+ ?, \. \5 y& F" f0 \
/*
( |; l$ D. u+ N3 _) p1 i6 T*convert a hex string to a byte array.
) a) Q3 S4 K1 x2 b*hex string format example:"AF B0 80 7D"
*/
4 D& `" n1 k+ q$ W$ \size_t hexStringToBytes(const string &str, byte *out);
1 e  ]8 q4 T7 b/ u/ f" ^4 u8 n
#endif/*UTIL_H*/

天云上人

#include "util.h"
' R/ z0 {* o& _! f3 q: H/ b- R#include <vector>

using namespace std;
# Y+ L7 N: ^! q/ s" Q/ |6 C0 j; H
char intToHexChar(int x) {
  G8 }2 {$ p7 {& s% d# {! K% |    static const char HEX[16] = {
$ a' m# ^6 J9 U        '0', '1', '2', '3',
        '4', '5', '6', '7',
8 w8 U7 P% W( B7 E6 V        '8', '9', 'A', 'B',
        'C', 'D', 'E', 'F'
    };
/ M- f1 x% q+ U* j5 J8 P% C    return HEX[x];
3 q9 N* Q5 \9 {3 J. s}

int hexCharToInt(char hex) {
    hex = toupper(hex);
    if (isdigit(hex))
( O# G6 ]- T; s# d9 {& D" w0 o        return (hex - '0');
+ l2 g% s* {' t% ]% z* K    if (isalpha(hex))
) X/ h8 e$ m5 @/ @. i2 \        return (hex - 'A' + 10);
3 s0 _1 b) l1 R) \5 T/ b    return 0;
}

2 b, Y% L% r' W( B$ _! A8 ^7 e6 cstring bytesToHexString(const byte *in, size_t size) {
    string str;
    for (size_t i = 0; i < size; ++i) {
7 T4 l3 ?* E6 T5 F- D# T7 ]        int t = in[i];
        int a = t / 16;
        int b = t % 16;
( M8 k7 K- D' k+ @  C( {        str.append(1, intToHexChar(a));
        str.append(1, intToHexChar(b));
        if (i != size - 1)
            str.append(1, ' ');
# A+ n$ @5 w: n! w' @1 h1 A    }
2 i: J, O* w- H  E! D    return str;
}

. l. n, G( o' j7 r$ Y6 K  ?) v9 {size_t hexStringToBytes(const string &str, byte *out) {
# \- Z1 F  o, h9 L
    vector<string> vec;
1 S" O+ B* V8 g+ I* \& A' B    string::size_type currPos = 0, prevPos = 0;
2 r; b' V8 ]3 o4 W5 F    while ((currPos = str.find(' ', prevPos)) != string::npos) {
8 A3 f8 \5 G) k        string b(str.substr(prevPos, currPos - prevPos));
) N+ r* Q' ?! A  |8 y7 T1 j        vec.push_back(b);
        prevPos = currPos + 1;
2 [! B3 v( U$ Q! u/ @    }
+ B9 J+ W% }, r4 o/ P    if (prevPos < str.size()) {
        string b(str.substr(prevPos));
6 ]8 R  a, q5 L5 V6 A3 R/ v4 f        vec.push_back(b);
    }
9 C3 g- d9 S  g4 T    typedef vector<string>::size_type sz_type;
    sz_type size = vec.size();
5 P3 ]+ O5 @. {& l! z5 z3 X+ K3 w    for (sz_type i = 0; i < size; ++i) {
        int a = hexCharToInt(vec[i][0]);
) v: {, K; T2 U- Z3 s7 b/ E        int b = hexCharToInt(vec[i][1]);
        out[i] = a * 16 + b;
    }
    return size;
}

天云上人

#ifndef TEA_H
#define TEA_H
, Q- k3 b+ x: O
0 a4 Y5 g0 l7 ]3 O1 \7 x/*
2 G( j( c5 I- e' e; H2 K8 W7 A*for htonl,htonl
" w) D& E2 z" l, x+ D+ g*do remember link "ws2_32.lib"
*/
#include <winsock2.h>
#include "util.h"

class TEA {
7 E5 \. w' f( |- bpublic:
0 H. u' w/ {; F# X) w) y5 }    TEA(const byte *key, int round = 32, bool isNetByte = false);
    TEA(const TEA &rhs);
    TEA& operator=(const TEA &rhs);
    void encrypt(const byte *in, byte *out);
    void decrypt(const byte *in, byte *out);
6 A4 `6 L( q) x3 C4 Jprivate:
* E1 i  u& d: w* {    void encrypt(const ulong *in, ulong *out);
    void decrypt(const ulong *in, ulong *out);
    ulong ntoh(ulong netlong) { return _isNetByte ? ntohl(netlong) : netlong; }
0 @* ~# N6 @8 m( K- |4 Y" @    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
4 K/ r2 O2 _, Q; w6 ~/ P! Y, m$ i    byte _key[16]; //encrypt or decrypt key
4 |) W7 Y  g/ Y! G, B& l' i1 \/ m};

#endif/*TEA_H*/

天云上人

1 #include "tea.h"
/ c7 I; M& B, M7 f 2 #include <cstring> //for memcpy,memset
8 n8 e, A* B# O3 Z) |1 P+ \7 @: @ 3  
; h9 Z5 R8 v, f* ~& n$ k4 B 4 using namespace std;
5  
( z2 a: ^8 C% v0 T" A7 {. x 6 TEA::TEA(const byte *key, int round /*= 32*/, bool isNetByte /*= false*/)
- R+ D1 C0 Z$ t; G5 ?0 R% F 7 :_round(round)
8 ,_isNetByte(isNetByte) {
9     if (key != 0)
10         memcpy(_key, key, 16);
3 D$ a( F" m) G- r11     else
8 s  M" E, ^2 J12         memset(_key, 0, 16);
13 }
14  
/ j+ K' P. C2 U8 g8 H6 ^/ V15 TEA::TEA(const TEA &rhs)
1 l6 f- N3 s* Y8 i16 :_round(rhs._round)
2 U8 F; P9 y$ V: I6 S) Z17 ,_isNetByte(rhs._isNetByte) {
18     memcpy(_key, rhs._key, 16);
  `1 `3 v: c* @6 S8 I19 }
: h, E" \5 d' y20  
1 Q9 V0 _: E0 D( Z' |21 TEA& TEA::operator=(const TEA &rhs) {
5 s- n! r0 h* \- i3 B1 a* Y22     if (&rhs != this) {
) a9 u0 v" }+ K' ~- s23         _round = rhs._round;
24         _isNetByte = rhs._isNetByte;
25         memcpy(_key, rhs._key, 16);
26     }
( x# U. e9 A) F27     return *this;
: ~. M! A4 B2 r+ u0 N! e5 a28 }
29  
- ~& l! K5 v+ \30 void TEA::encrypt(const byte *in, byte *out) {
- Y8 |+ A- L7 |3 s' p/ c31     encrypt((const ulong*)in, (ulong*)out);
32 }
& C7 r5 O& V2 {- R' I33  
3 V9 Y3 C2 I6 h7 L! u34 void TEA::decrypt(const byte *in, byte *out) {
35     decrypt((const ulong*)in, (ulong*)out);
, v- u# \' l+ H* `9 k; P5 u36 }
37  
8 W9 ~# ?7 Z/ o38 void TEA::encrypt(const ulong *in, ulong *out) {
- k7 {* i7 m2 K$ V1 c+ X39  
40     ulong *k = (ulong*)_key;
41     register ulong y = ntoh(in[0]);
, [6 ^" Y: l, R, D, q) H42     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]);
46     register ulong d = ntoh(k[3]);
" q. j8 t! z/ h) h& Q47     register ulong delta = 0x9E3779B9; /* (sqrt(5)-1)/2*2^32 */
" ]4 H+ g: s9 I. V/ x48     register int round = _round;
49     register ulong sum = 0;
4 W) U$ o# G4 Q; B0 l; i50  
51     while (round--) {    /* basic cycle start */
52         sum += delta;
53         y += ((z << 4) + a) ^ (z + sum) ^ ((z >> 5) + b);
  z5 }% ^6 n- [/ b) w- \54         z += ((y << 4) + c) ^ (y + sum) ^ ((y >> 5) + d);
55     }    /* end cycle */
+ X* o% A2 O: o) P56     out[0] = ntoh(y);
57     out[1] = ntoh(z);
7 \2 h& ^8 }2 L1 Q; n+ V+ q" f58 }
' G  j9 y* r  }) X: r( x0 @/ w# R59  
60 void TEA::decrypt(const ulong *in, ulong *out) {
1 [  G. e- U/ F4 ]61  
; o% B, r1 o* w: r2 r& g62     ulong *k = (ulong*)_key;
63     register ulong y = ntoh(in[0]);
64     register ulong z = ntoh(in[1]);
65     register ulong a = ntoh(k[0]);
3 K# g  R5 v# R" ^: I1 l66     register ulong b = ntoh(k[1]);
67     register ulong c = ntoh(k[2]);
' \, L! y: s( F/ q4 o68     register ulong d = ntoh(k[3]);
: m' p6 T4 S  X8 Y$ H+ L& j, B69     register ulong delta = 0x9E3779B9; /* (sqrt(5)-1)/2*2^32 */
70     register int round = _round;
71     register ulong sum = 0;
9 Z# u! ^! }0 o2 o4 n72  
73     if (round == 32)
0 Q; a2 W6 L1 t- J3 Q* f: O74         sum = 0xC6EF3720; /* delta << 5*/
2 m% H- i, c' \& e7 n9 x8 c5 e75     else if (round == 16)
76         sum = 0xE3779B90; /* delta << 4*/
" o* P5 a( H! k5 S+ w- @$ ?2 T77     else
" M9 Z7 r' d: S* m2 S" p78         sum = delta << static_cast<int>(logbase(2, round));
79  
80     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);
! Z+ G2 [* F5 A% x0 v  D- Q  |3 q83         sum -= delta;
84     }    /* end cycle */
85     out[0] = ntoh(y);
+ c' A" R+ @1 u- T$ O$ [86     out[1] = ntoh(z);
87 }

. E% Y: `* w& D8 d# p需要说明的是TEA的构造函数：
/ [7 j7 Z4 t' h2 ~TEA(const byte *key, int round = 32, bool isNetByte = false);
( O# H( J9 a/ t1.key - 加密或解密用的128-bit(16byte)密钥。
5 ?' B4 ]( b: }! V2.round - 加密或解密的轮数，常用的有64，32，16。
3.isNetByte - 用来标记待处理的字节是不是来自网络，为true时在加密/解密前先要转换成本地字节，执行加密/解密，然后再转换回网络字节。偷偷告诉你，QQ就是这样做的！

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

天云上人

1 #include "tea.h"
2 #include "util.h"
3 #include <iostream>
% V6 o) z. Z7 E" {* _ 4  
5 using namespace std;
& s* P& N  y* J 6  
. n# j& p3 d+ y" h9 t 7 int main() {
8  
3 |  @7 j% q& W+ j) s# `* ~ 9     const string plainStr("AD DE E2 DB B3 E2 DB B3");
/ V- g* o- N3 U0 w10     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];
+ k: C2 _: z( }9 J9 \: b13  
14     size_t size_in = hexStringToBytes(plainStr, plain);
# n3 F9 t& E1 Z$ d15     size_t size_key = hexStringToBytes(keyStr, key);
16  
17     if (size_in != SIZE_IN || size_key != SIZE_KEY)
18         return -1;
19  
6 g) M% x6 t) _4 ]20     cout << "Plain: " << bytesToHexString(plain, size_in) << endl;
21     cout << "Key  : " << bytesToHexString(key, size_key) << endl;
2 Y* z. e; Y. Z3 d0 }2 k22  
23     TEA tea(key, 16, true);
24     tea.encrypt(plain, crypt);
, J) d* }. ~0 B% ^; A. z( S25     cout << "Crypt: " << bytesToHexString(crypt, SIZE_OUT) << endl;
26  
6 I( G! h* Y. v) m; r27     tea.decrypt(crypt, plain);
- `! f' L/ Y8 c- ^  I8 A, p1 `28     cout << "Plain: " << bytesToHexString(plain, SIZE_IN) << endl;
7 b" j2 _0 I$ ^' X. O29     return 0;
: K& B$ C2 a( Q' n5 ~( Z30 }

本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/sailing0123/archive/2008/04/28/2339231.aspx
运行结果：
3 U* D! W! {7 e! ~' N! L' MPlain: AD DE E2 DB B3 E2 DB B3
1 o2 _1 t, A# {4 H. K" X! f! g* M5 QKey  : 3A DA 75 21 DB E2 DB B3 11 B4 49 01 A5 C6 EA D4
# L, D$ l6 L/ p9 k1 z- D' d; y2 dCrypt: 3B 3B 4D 8C 24 3A FD F2
2 Z4 Y' o- o+ y- ?+ B* P* RPlain: AD DE E2 DB B3 E2 DB B3