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） 都是分组加密算法，它们很容易被描述，实现也很简单（典型的几行代码）。
; V# e' t/ J+ ?, c! ?" wTEA 算法最初是由剑桥计算机实验室的 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. 
   ; w- C6 p4 Q9 G, W0 c
2. void encrypt(unsigned long *v, unsigned long *k) {
   - S0 P( @& s9 |0 v
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 */
   
7.          sum += delta;
   # ~8 v! L  h: |& f! \  j% d
8.          y += ((z<<4) + a) ^ (z + sum) ^ ((z>>5) + b);
   
9.          z += ((y<<4) + c) ^ (y + sum) ^ ((y>>5) + d);/* end cycle */
   ' H& U( @! b, O- P$ \
10.      }
    
11.      v[0]=y;
    + L/ z$ b% y! k" p0 N
12.      v[1]=z;
    
13. }
      I, D0 b! [$ l  j' G6 c: u+ B
14.   
    
15. void decrypt(unsigned long *v, unsigned long *k) {
    7 b1 ~6 {7 T$ i; G
16.      unsigned long y=v[0], z=v[1], sum=0xC6EF3720, i; /* set up */
    & G- f; Y3 w4 v
17.      unsigned long delta=0x9e3779b9;                  /* a key schedule constant */
    - C7 |: m' l- a+ I( b) \
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 */
    + K! ?8 {* Y7 M( X9 V, W
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 */
    
23.      }
    
24.      v[0]=y;
    ! j4 [1 f5 E+ y0 X- p
25.      v[1]=z;
      R) o! {& _! O- I% w; U$ l
26. }
    ! x2 @9 Z* |% N1 l+ A8 ?1 [

复制代码

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

天云上人

#ifndef UTIL_H
#define UTIL_H

4 u6 y$ e0 Q% t$ i: {#include <string>
#include <cmath>
#include <cstdlib>

typedef unsigned char byte;
/ S5 U; f+ c+ utypedef unsigned long ulong;
& T4 Q% Z. G5 ]
% `4 J: F$ x; o$ d) ~. W/ a# Uinline double logbase(double base, double x) {
2 l+ S+ [& ?& l7 n* I2 m    return log(x)/log(base);
}

- W2 y5 K* b9 i- [1 \: A, R/*
*convert int to hex char.
- t+ b+ M9 R4 J( H9 h7 h( A*example:10 -> 'A',15 -> 'F'
*/
char intToHexChar(int x);
$ t3 U& Q" g5 O( H
# r7 x2 ]) [) t% e' x/*
# t  ?7 C3 {" F" x' f*convert hex char to int.
*example:'A' -> 10,'F' -> 15
*/
int hexCharToInt(char hex);

5 {5 Q2 m2 G" lusing std::string;
/*
*convert a byte array to hex string.
*hex string format example:"AF B0 80 7D"
* W9 k8 Y1 t$ i* K. J*/
string bytesToHexString(const byte *in, size_t size);
4 s7 O6 a* c' f3 m- {, p6 V
/*
; ^6 S' s; \* ~*convert a hex string to a byte array.
*hex string format example:"AF B0 80 7D"
% C7 j0 S# M3 C*/
; o  v; ?- I: G2 Ksize_t hexStringToBytes(const string &str, byte *out);
5 @% s) H3 c; x8 {) P
#endif/*UTIL_H*/

天云上人

#include "util.h"
9 A" `) B+ d% k7 V5 l) v#include <vector>

using namespace std;

char intToHexChar(int x) {
    static const char HEX[16] = {
% U8 Y- l- q6 {6 G        '0', '1', '2', '3',
        '4', '5', '6', '7',
. i0 o- {- X8 ?        '8', '9', 'A', 'B',
        'C', 'D', 'E', 'F'
3 P. Z3 o! i2 r" {4 B: `    };
6 w. t7 M$ |' [# \    return HEX[x];
}

int hexCharToInt(char hex) {
    hex = toupper(hex);
    if (isdigit(hex))
        return (hex - '0');
    if (isalpha(hex))
- u: q, r! w# T( B2 e" i        return (hex - 'A' + 10);
7 E+ M. A9 C( s    return 0;
}

+ N  L5 T. v2 L4 wstring bytesToHexString(const byte *in, size_t size) {
    string str;
$ z& \7 _. U# Z9 I$ C' t# z    for (size_t i = 0; i < size; ++i) {
* R* y; |: k3 ~  K" a        int t = in[i];
% Q8 x! M, B  j/ t% }# v        int a = t / 16;
        int b = t % 16;
$ R1 h% i1 F! ]8 e        str.append(1, intToHexChar(a));
* @5 M( o( ]. a& v2 n7 ]. M- G2 _# ~. x3 E        str.append(1, intToHexChar(b));
$ A/ Q- g% R4 N0 y; N        if (i != size - 1)
            str.append(1, ' ');
8 F6 c# k" @! m- f6 @8 T* J4 b    }
    return str;
}
+ t( Y4 C4 r) C2 Q5 H2 r
size_t hexStringToBytes(const string &str, byte *out) {

. g5 u7 p6 R% N- o. {    vector<string> vec;
    string::size_type currPos = 0, prevPos = 0;
    while ((currPos = str.find(' ', prevPos)) != string::npos) {
        string b(str.substr(prevPos, currPos - prevPos));
        vec.push_back(b);
        prevPos = currPos + 1;
) D& h, B# `) P. T    }
    if (prevPos < str.size()) {
        string b(str.substr(prevPos));
        vec.push_back(b);
$ s" _0 u" _! K4 |, @    }
    typedef vector<string>::size_type sz_type;
    sz_type size = vec.size();
/ ]3 ]$ b/ P- ?) \    for (sz_type i = 0; i < size; ++i) {
( v* M7 @  l* M* l3 ~6 {* R+ S: s        int a = hexCharToInt(vec[i][0]);
" k3 p: ^" S8 W! A6 U) A2 K& h/ I        int b = hexCharToInt(vec[i][1]);
5 P/ O. j0 H. B7 `        out[i] = a * 16 + b;
    }
    return size;
6 A+ @0 E% U+ q5 j: A}

天云上人

#ifndef TEA_H
6 V- J" b% I+ G: a& A% Q1 a4 I" y. [#define TEA_H
3 l/ s' }! q5 Q6 W4 G7 G; G
/*
*for htonl,htonl
*do remember link "ws2_32.lib"
*/
; O' Y# N4 R! l#include <winsock2.h>
#include "util.h"

1 o& R6 P5 \6 Q$ u1 d1 S* ]! L( Gclass TEA {
public:
    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);
" c  Z0 z  D+ w6 N    void decrypt(const byte *in, byte *out);
private:
    void encrypt(const ulong *in, ulong *out);
9 \# o6 M8 w+ Z! \6 V- z, d/ v, y    void decrypt(const ulong *in, ulong *out);
    ulong ntoh(ulong netlong) { return _isNetByte ? ntohl(netlong) : netlong; }
. a2 |  r- R7 N; Y    ulong hton(ulong hostlong) { return _isNetByte ? htonl(hostlong) : hostlong; }
1 ^2 t2 y4 X9 O8 W6 F# n: [private:
    int _round; //iteration round to encrypt or decrypt
    bool _isNetByte; //whether input bytes come from network
" }; Y0 e4 h* s2 j    byte _key[16]; //encrypt or decrypt key
& v" |) O2 M4 G. R};
4 `  y3 U" E9 j( D9 ]  p
#endif/*TEA_H*/

天云上人

1 #include "tea.h"
2 #include <cstring> //for memcpy,memset
' t$ G) s! g* f8 U7 t 3  
; [8 k7 `- q' M8 B# O6 X 4 using namespace std;
0 d( c5 |# ^7 u( A 5  
6 TEA::TEA(const byte *key, int round /*= 32*/, bool isNetByte /*= false*/)
7 :_round(round)
8 ,_isNetByte(isNetByte) {
9     if (key != 0)
10         memcpy(_key, key, 16);
11     else
+ K7 X5 Z5 [( ?/ d+ b- ]12         memset(_key, 0, 16);
% p% V9 r- ?* O13 }
0 R/ D8 _7 |( x* ~# `14  
15 TEA::TEA(const TEA &rhs)
16 :_round(rhs._round)
& V& E) S" P: a17 ,_isNetByte(rhs._isNetByte) {
& z; u, {+ u. j5 U18     memcpy(_key, rhs._key, 16);
19 }
20  
: w5 f7 r$ Z( F* b' l* p/ J4 p) s4 c21 TEA& TEA::operator=(const TEA &rhs) {
22     if (&rhs != this) {
7 g; }& ~0 v5 P0 Q, u  O) v23         _round = rhs._round;
24         _isNetByte = rhs._isNetByte;
25         memcpy(_key, rhs._key, 16);
# Z. h: g, X7 {4 c26     }
* F+ o5 z; P0 T  X$ V1 \" D27     return *this;
* d3 E0 {) X7 e1 Y: S6 x28 }
29  
9 u  }; p, X# h2 ?3 j# z30 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) {
35     decrypt((const ulong*)in, (ulong*)out);
36 }
+ b: Y0 A1 Z! c37  
: |! }) t* F3 \; R' d; I: ~) M38 void TEA::encrypt(const ulong *in, ulong *out) {
  }6 S8 b% M3 K- ~39  
, H9 Y( K: w* t40     ulong *k = (ulong*)_key;
. S5 Q3 h' C6 j3 J; ]41     register ulong y = ntoh(in[0]);
$ i3 h, ~0 |$ P* E6 K; Z' E42     register ulong z = ntoh(in[1]);
43     register ulong a = ntoh(k[0]);
44     register ulong b = ntoh(k[1]);
! o* [0 ~2 h' r  Q$ f( b45     register ulong c = ntoh(k[2]);
4 A7 z, c1 o, h! s46     register ulong d = ntoh(k[3]);
47     register ulong delta = 0x9E3779B9; /* (sqrt(5)-1)/2*2^32 */
48     register int round = _round;
49     register ulong sum = 0;
9 s' B; a: a6 v' C. }5 }50  
51     while (round--) {    /* basic cycle start */
( I% R  ?% B3 [- C/ ]52         sum += delta;
53         y += ((z << 4) + a) ^ (z + sum) ^ ((z >> 5) + b);
9 W0 W5 D& |( r$ Z- U3 l54         z += ((y << 4) + c) ^ (y + sum) ^ ((y >> 5) + d);
1 U' ]+ g% o" R8 R55     }    /* end cycle */
3 ?( q4 b; w, N( H1 ^56     out[0] = ntoh(y);
) v6 v0 c& k2 h. x- v  Z57     out[1] = ntoh(z);
9 J8 `# P9 ?& t% {58 }
" ?  P, l* I+ p59  
60 void TEA::decrypt(const ulong *in, ulong *out) {
6 f/ `, E. K: @# u61  
0 `$ D& R9 ~- {+ e' \1 v, Y62     ulong *k = (ulong*)_key;
- m# k8 M: @0 Y/ n# R0 y63     register ulong y = ntoh(in[0]);
2 f' q! }% Z4 s( b64     register ulong z = ntoh(in[1]);
0 e5 E) Z, H* |* A2 c+ p' h1 u4 O( M65     register ulong a = ntoh(k[0]);
+ k+ L- i; ?6 P7 O! d' P1 U/ |66     register ulong b = ntoh(k[1]);
67     register ulong c = ntoh(k[2]);
68     register ulong d = ntoh(k[3]);
69     register ulong delta = 0x9E3779B9; /* (sqrt(5)-1)/2*2^32 */
7 K, N* o' s( D7 _* [70     register int round = _round;
71     register ulong sum = 0;
- ^, a; l/ r2 G" R3 Y  W( W72  
73     if (round == 32)
74         sum = 0xC6EF3720; /* delta << 5*/
75     else if (round == 16)
76         sum = 0xE3779B90; /* delta << 4*/
77     else
* P# E% F) ?  e78         sum = delta << static_cast<int>(logbase(2, round));
, |2 g6 ]0 L- B; j6 _: f' X3 `/ W79  
80     while (round--) {    /* basic cycle start */
4 P7 y' K! J& L' m0 L2 R1 X( f7 p3 b81         z -= ((y << 4) + c) ^ (y + sum) ^ ((y >> 5) + d);
2 H4 H% N- S% D8 @3 a82         y -= ((z << 4) + a) ^ (z + sum) ^ ((z >> 5) + b);
83         sum -= delta;
84     }    /* end cycle */
85     out[0] = ntoh(y);
86     out[1] = ntoh(z);
87 }

- Y3 H  B. U2 v; R! `# W, |4 ?7 |+ a" O需要说明的是TEA的构造函数：
% K/ H: S! }8 j" W5 }& T) u) V  fTEA(const byte *key, int round = 32, bool isNetByte = false);
' j0 B4 [* j7 y: K& H1.key - 加密或解密用的128-bit(16byte)密钥。
1 C1 }; ^0 g1 H+ y: f2.round - 加密或解密的轮数，常用的有64，32，16。
# A9 g1 I( b/ c0 I3.isNetByte - 用来标记待处理的字节是不是来自网络，为true时在加密/解密前先要转换成本地字节，执行加密/解密，然后再转换回网络字节。偷偷告诉你，QQ就是这样做的！

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

天云上人

1 #include "tea.h"
2 #include "util.h"
3 #include <iostream>
( w1 S  z+ E! J: K( G: l) i' ~- l* ] 4  
5 using namespace std;
6  
7 int main() {
8  
! H- B5 Z( D9 U8 q, u  }3 F% D& b 9     const string plainStr("AD DE E2 DB B3 E2 DB B3");
3 \$ Z4 q' O: y8 Q9 u; {9 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;
$ j1 v* Q! q3 C. L9 e* E6 v% Q: r12     byte plain[SIZE_IN], crypt[SIZE_OUT], key[SIZE_KEY];
13  
! W6 |, \& w7 |+ q) W14     size_t size_in = hexStringToBytes(plainStr, plain);
15     size_t size_key = hexStringToBytes(keyStr, key);
16  
( `: u, a6 Z& ]. V# f7 N17     if (size_in != SIZE_IN || size_key != SIZE_KEY)
- F" _0 c5 J# f0 ~18         return -1;
9 b6 c3 d: p& i6 e' \: ]. h19  
20     cout << "Plain: " << bytesToHexString(plain, size_in) << endl;
21     cout << "Key  : " << bytesToHexString(key, size_key) << endl;
22  
, z% _, r. B+ e' n' _& x  o) h7 U23     TEA tea(key, 16, true);
( z: U3 q: b+ l! J% \6 s! E24     tea.encrypt(plain, crypt);
25     cout << "Crypt: " << bytesToHexString(crypt, SIZE_OUT) << endl;
, v6 E- C0 f2 K1 e  H, ~" I3 H/ \, K26  
( C( x7 l5 g, x  U) p6 I+ ~* p27     tea.decrypt(crypt, plain);
6 t( j# n0 c2 E) l5 O! N28     cout << "Plain: " << bytesToHexString(plain, SIZE_IN) << endl;
- l* \; ]2 i# b" \: X29     return 0;
30 }
: y4 l. [+ c. b% u
! j3 n- G5 W( `: H本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/sailing0123/archive/2008/04/28/2339231.aspx
运行结果：
Plain: AD DE E2 DB B3 E2 DB B3
0 b; @- g9 O0 |8 tKey  : 3A DA 75 21 DB E2 DB B3 11 B4 49 01 A5 C6 EA D4
( E) ], M4 d0 i9 ZCrypt: 3B 3B 4D 8C 24 3A FD F2
3 s2 r7 {) U6 b8 ZPlain: AD DE E2 DB B3 E2 DB B3