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

血刀老祖

TEA(Tiny Encryption Algorithm) 是一种简单高效的加密算法，以加密解密速度快，实现简单著称。算法真的很简单，TEA算法每一次可以操作64-bit(8-byte)，采用128-bit(16-byte)作为key，算法采用迭代的形式，推荐的迭代轮数是64轮，最少32轮。目前我只知道QQ一直用的是16轮TEA。没什么好说的，先给出C语言的源代码(默认是32轮)：
! x) w# Q! X8 ?5 L* M微型加密算法（TEA）及其相关变种（XTEA，Block TEA，XXTEA） 都是分组加密算法，它们很容易被描述，实现也很简单（典型的几行代码）。
TEA 算法最初是由剑桥计算机实验室的 David Wheeler 和 Roger Needham 在 1994 年设计的。该算法使用 128 位的密钥为 64 位的信息块进行加密，它需要进行 64 轮迭代，尽管作者认为 32 轮已经足够了。该算法使用了一个神秘常数δ作为倍数，它来源于黄金比率，以保证每一轮加密都不相同。但δ的精确值似乎并不重要，这里 TEA 把它定义为 δ=「(√5 - 1)231」（也就是程序中的 0×9E3779B9）。
. p' b- _$ L% v  x7 s' O5 o2 I( P之后 TEA 算法被发现存在缺陷，作为回应，设计者提出了一个 TEA 的升级版本——XTEA（有时也被称为“tean”）。XTEA 跟 TEA 使用了相同的简单运算，但它采用了截然不同的顺序，为了阻止密钥表攻击，四个子密钥（在加密过程中，原 128 位的密钥被拆分为 4 个 32 位的子密钥）采用了一种不太正规的方式进行混合，但速度更慢了。
+ A  i5 e6 n3 X在跟描述 XTEA 算法的同一份报告中，还介绍了另外一种被称为 Block TEA 算法的变种，它可以对 32 位大小任意倍数的变量块进行操作。该算法将 XTEA 轮循函数依次应用于块中的每个字，并且将它附加于它的邻字。该操作重复多少轮依赖于块的大小，但至少需要 6 轮。该方法的优势在于它无需操作模式（CBC，OFB，CFB 等），密钥可直接用于信息。对于长的信息它可能比 XTEA 更有效率。
6 Y# p6 R/ J" t. X$ Z- c+ F- t在 1998 年，Markku-Juhani Saarinen 给出了一个可有效攻击 Block TEA 算法的代码，但之后很快 David J. Wheeler 和 Roger M. Needham 就给出了 Block TEA 算法的修订版，这个算法被称为 XXTEA。XXTEA 使用跟 Block TEA 相似的结构，但在处理块中每个字时利用了相邻字。它利用一个更复杂的 MX 函数代替了 XTEA 轮循函数，MX 使用 2 个输入量。

天云上人

1. 
     N2 d( \# H2 @( G9 [) T
2. void encrypt(unsigned long *v, unsigned long *k) {
   . Z, A( }- ^  g' V2 ^
3.      unsigned long y=v[0], z=v[1], sum=0, i;         /* set up */
   
4.      unsigned long delta=0x9e3779b9;                 /* a key schedule constant */
   1 X; P: q. u( g% ^- z
5.      unsigned long a=k[0], b=k[1], c=k[2], d=k[3];   /* cache key */
   % X* W' Y7 k" j# d, k- p- M+ {
6.      for (i=0; i < 32; i++) {                        /* basic cycle start */
   - m7 d) e1 X# i4 v& c
7.          sum += delta;
   , M$ O" N3 x; y- }
8.          y += ((z<<4) + a) ^ (z + sum) ^ ((z>>5) + b);
   + k& ^* b% ~' L# P# Y2 L3 `
9.          z += ((y<<4) + c) ^ (y + sum) ^ ((y>>5) + d);/* end cycle */
   ; ~, l' i6 c0 z) u% @
10.      }
    
11.      v[0]=y;
    2 h2 p9 P/ Z8 M
12.      v[1]=z;
    , u8 n& z2 {$ r0 f( c
13. }
    - C' k4 G3 U! Y; S+ V4 J$ H
14.   
    ; Z% ?+ g% z" ]/ J$ V. a" r+ t/ M
15. void decrypt(unsigned long *v, unsigned long *k) {
    3 A) G5 E% q) |
16.      unsigned long y=v[0], z=v[1], sum=0xC6EF3720, i; /* set up */
    
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 */
    ! J0 J7 ?) o; o/ w3 h* o
19.      for(i=0; i<32; i++) {                            /* basic cycle start */
    $ W' d) o/ r. s  p3 y5 x
20.          z -= ((y<<4) + c) ^ (y + sum) ^ ((y>>5) + d);
    
21.          y -= ((z<<4) + a) ^ (z + sum) ^ ((z>>5) + b);
    9 U5 p/ k$ b7 P( \5 R! a; g4 }
22.          sum -= delta;                                /* end cycle */
    5 V/ z" O; U- h' Q
23.      }
    
24.      v[0]=y;
    
25.      v[1]=z;
    
26. }
    

复制代码

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

天云上人

#ifndef UTIL_H
. Q4 C1 E' j8 ?+ M) w4 T. h7 `#define UTIL_H

#include <string>
#include <cmath>
#include <cstdlib>

typedef unsigned char byte;
typedef unsigned long ulong;
- @" S+ F/ @0 g% L
! `; d8 `( u" O8 V# x: a8 Xinline double logbase(double base, double x) {
- E  F1 P3 L8 V! G/ w$ m    return log(x)/log(base);
" `! b' ]: l& m- g) f}

" p0 S; f2 \5 q. f) K/*
*convert int to hex char.
*example:10 -> 'A',15 -> 'F'
*/
char intToHexChar(int x);
/ c3 f. J7 i* T' D# y0 T
/*
*convert hex char to int.
*example:'A' -> 10,'F' -> 15
- t6 I  T3 F) }2 ]3 S  k# h*/
7 r# @  A! D' E  J+ Xint hexCharToInt(char hex);
( z5 c7 J$ a2 p0 f; r
* l/ F6 I+ G/ _4 {using std::string;
0 `1 i3 W7 h7 x5 T/*
  }9 K& k( o* m*convert a byte array to hex string.
+ C+ c. x: }" G$ `*hex string format example:"AF B0 80 7D"
*/
string bytesToHexString(const byte *in, size_t size);

' O' b7 j" W/ V/*
; ^- B' G) Z  D! ^1 ?- ~*convert a hex string to a byte array.
*hex string format example:"AF B0 80 7D"
*/
# P4 n1 e- s- B2 Bsize_t hexStringToBytes(const string &str, byte *out);
9 k; f5 C& }* g7 w5 a, I9 u
* n8 k$ l& e) E7 ?#endif/*UTIL_H*/

天云上人

#include "util.h"
#include <vector>
6 }: c( }% P0 M/ p0 ]4 H$ B
/ K( ?) S1 T6 C/ i9 }; w/ Nusing namespace std;

char intToHexChar(int x) {
    static const char HEX[16] = {
+ P3 h: b, D+ s- O" Z  p9 H& a        '0', '1', '2', '3',
        '4', '5', '6', '7',
        '8', '9', 'A', 'B',
+ N9 [. b& Y4 x0 j; i5 L9 ~        'C', 'D', 'E', 'F'
! g6 G0 T# E" O( g0 A# D, p4 m    };
' \' @4 Y) {" H    return HEX[x];
}

int hexCharToInt(char hex) {
    hex = toupper(hex);
    if (isdigit(hex))
        return (hex - '0');
    if (isalpha(hex))
        return (hex - 'A' + 10);
    return 0;
( }% o8 X3 h0 V5 u, v}
; R/ @1 b9 E. k! I; Z" \( a
0 g: N  t7 x" q) rstring bytesToHexString(const byte *in, size_t size) {
) G% k  o" j0 g( Y; o( O    string str;
    for (size_t i = 0; i < size; ++i) {
1 v5 J  }( @8 L; `' [' }8 z        int t = in[i];
# n2 E  b* k; C* B, E- y8 b        int a = t / 16;
; N1 s8 g- K' S* M8 F        int b = t % 16;
        str.append(1, intToHexChar(a));
) s3 H- v( m  x+ W        str.append(1, intToHexChar(b));
        if (i != size - 1)
            str.append(1, ' ');
    }
    return str;
}

size_t hexStringToBytes(const string &str, byte *out) {
  O6 H/ k9 W/ L/ y' v
    vector<string> vec;
( Z( O$ k- E8 a; k    string::size_type currPos = 0, prevPos = 0;
    while ((currPos = str.find(' ', prevPos)) != string::npos) {
        string b(str.substr(prevPos, currPos - prevPos));
: ^: l) O6 m& A0 \' @4 U        vec.push_back(b);
        prevPos = currPos + 1;
3 b! E9 ?) u% R4 j: I/ E    }
    if (prevPos < str.size()) {
1 r9 _3 b! F2 k; j  t+ B! a        string b(str.substr(prevPos));
        vec.push_back(b);
    }
    typedef vector<string>::size_type sz_type;
4 ]/ }" D5 a4 c: F* A) j( J! u( v0 s    sz_type size = vec.size();
8 t  A: C, p( t6 _  g7 e5 A, n    for (sz_type i = 0; i < size; ++i) {
) j5 G) |  y/ ?8 Y        int a = hexCharToInt(vec[i][0]);
        int b = hexCharToInt(vec[i][1]);
        out[i] = a * 16 + b;
    }
' z5 X  J9 M  x4 Z    return size;
6 \3 l8 {8 _4 J1 L}

天云上人

#ifndef TEA_H
4 {, S$ @( T0 n- h" ]5 @5 h+ N9 M#define TEA_H
3 C4 g  `! w3 G0 a4 I
/*
*for htonl,htonl
% n/ d3 F. R" j, P1 a*do remember link "ws2_32.lib"
/ s4 R" C" y; `2 j  g*/
#include <winsock2.h>
#include "util.h"

4 Y5 W9 M+ J* O& S7 qclass TEA {
public:
    TEA(const byte *key, int round = 32, bool isNetByte = false);
' }# k' d/ T8 Y2 [9 S4 {9 g    TEA(const TEA &rhs);
    TEA& operator=(const TEA &rhs);
& ^! G. f& Y+ k# J  v, o    void encrypt(const byte *in, byte *out);
    void decrypt(const byte *in, byte *out);
private:
    void encrypt(const ulong *in, ulong *out);
    void decrypt(const ulong *in, ulong *out);
    ulong ntoh(ulong netlong) { return _isNetByte ? ntohl(netlong) : netlong; }
: [( F0 }/ ~+ z$ q; a# v: S    ulong hton(ulong hostlong) { return _isNetByte ? htonl(hostlong) : hostlong; }
private:
* @  j4 R$ [5 n1 \$ W/ v    int _round; //iteration round to encrypt or decrypt
    bool _isNetByte; //whether input bytes come from network
( a$ m1 B+ _% w1 `0 B! z- f    byte _key[16]; //encrypt or decrypt key
" n& X2 g$ e% q+ G5 F0 v7 B};

#endif/*TEA_H*/

天云上人

1 #include "tea.h"
2 #include <cstring> //for memcpy,memset
3  
' z2 \: A  F( B1 W$ d. ?& | 4 using namespace std;
5  
6 TEA::TEA(const byte *key, int round /*= 32*/, bool isNetByte /*= false*/)
7 :_round(round)
8 |& w3 v1 F2 g 8 ,_isNetByte(isNetByte) {
& w# D! b! x3 b0 M  d4 N3 [ 9     if (key != 0)
' C. @$ m" `& M4 R10         memcpy(_key, key, 16);
11     else
12         memset(_key, 0, 16);
13 }
14  
15 TEA::TEA(const TEA &rhs)
; M5 z+ m7 q! ]$ u& t* \7 f& Y16 :_round(rhs._round)
17 ,_isNetByte(rhs._isNetByte) {
, i, ]6 ~  m; ^+ z) Q18     memcpy(_key, rhs._key, 16);
$ M" \" G! N- ~; ]( Q1 H19 }
5 F2 ?# [! D; {% N8 ]7 I20  
* C8 ]) ?; o- J21 TEA& TEA::operator=(const TEA &rhs) {
: m/ Q$ A2 k* m22     if (&rhs != this) {
23         _round = rhs._round;
+ u- S+ M: X3 N& f* U24         _isNetByte = rhs._isNetByte;
25         memcpy(_key, rhs._key, 16);
26     }
27     return *this;
28 }
29  
30 void TEA::encrypt(const byte *in, byte *out) {
- s" l) N1 F. [5 S# s31     encrypt((const ulong*)in, (ulong*)out);
32 }
5 t" [" J2 W" M: c3 }33  
34 void TEA::decrypt(const byte *in, byte *out) {
35     decrypt((const ulong*)in, (ulong*)out);
: ?- x0 H+ N% ?" I" {36 }
- z7 a- k2 N) q; h/ O# t37  
9 X' X( x) [" C2 c& A$ m38 void TEA::encrypt(const ulong *in, ulong *out) {
; n& U" D5 J. c) |39  
; B' P! N1 X3 N. G40     ulong *k = (ulong*)_key;
41     register ulong y = ntoh(in[0]);
42     register ulong z = ntoh(in[1]);
" Q; e2 D) _9 j3 ~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]);
47     register ulong delta = 0x9E3779B9; /* (sqrt(5)-1)/2*2^32 */
48     register int round = _round;
49     register ulong sum = 0;
! L' A" \8 c2 ^2 X2 V50  
; @0 t9 D9 d$ P% H+ M% N51     while (round--) {    /* basic cycle start */
, u3 K$ ]4 c+ j/ P6 H52         sum += delta;
53         y += ((z << 4) + a) ^ (z + sum) ^ ((z >> 5) + b);
54         z += ((y << 4) + c) ^ (y + sum) ^ ((y >> 5) + d);
7 _/ E+ n# D9 t+ T0 w55     }    /* end cycle */
56     out[0] = ntoh(y);
) N% B. ^9 i0 n, r3 j# _) A57     out[1] = ntoh(z);
& z0 G8 w: H' V3 _, [58 }
59  
; w; e. h( @. E* b4 y60 void TEA::decrypt(const ulong *in, ulong *out) {
8 M9 S0 A  j! g8 s0 y  _61  
62     ulong *k = (ulong*)_key;
: r0 A8 e% ^9 B) U  h1 q' L63     register ulong y = ntoh(in[0]);
64     register ulong z = ntoh(in[1]);
65     register ulong a = ntoh(k[0]);
1 `5 U( X& k1 G& [  o- D7 {; }66     register ulong b = ntoh(k[1]);
) K6 R! n  _1 M" f67     register ulong c = ntoh(k[2]);
  z1 K- M' g- P: [) i68     register ulong d = ntoh(k[3]);
! `( R  e$ g  t5 m6 t* H' d69     register ulong delta = 0x9E3779B9; /* (sqrt(5)-1)/2*2^32 */
70     register int round = _round;
71     register ulong sum = 0;
72  
1 V1 `' M+ |2 K8 R3 T73     if (round == 32)
6 I: h$ G0 e. K/ V74         sum = 0xC6EF3720; /* delta << 5*/
* S3 T, ]& P+ O7 }75     else if (round == 16)
. b4 c' [3 @+ j5 A2 o& |( X. R% ]9 j76         sum = 0xE3779B90; /* delta << 4*/
77     else
78         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);
) S) w/ c9 u8 L( Y6 y6 n83         sum -= delta;
9 |/ C& F- S+ n. R84     }    /* end cycle */
- m. Y. \/ M  `+ I2 \1 G85     out[0] = ntoh(y);
9 J5 [! r, C: G8 I9 g' v: M2 R& A86     out[1] = ntoh(z);
% w* B# q6 z! b2 F% X7 s2 G! P) c87 }
0 W5 ?  P- A! ]0 b
需要说明的是TEA的构造函数：
; n) J3 R9 W2 Y( qTEA(const byte *key, int round = 32, bool isNetByte = false);
& O# S: I6 |$ q* L3 r1.key - 加密或解密用的128-bit(16byte)密钥。
2.round - 加密或解密的轮数，常用的有64，32，16。
3.isNetByte - 用来标记待处理的字节是不是来自网络，为true时在加密/解密前先要转换成本地字节，执行加密/解密，然后再转换回网络字节。偷偷告诉你，QQ就是这样做的！

- q* {0 U9 S6 H- x/ Z% `最后当然少不了测试代码：

天云上人

1 #include "tea.h"
2 #include "util.h"
3 #include <iostream>
4  
5 using namespace std;
& N$ |3 w; c4 |# k2 p- ]* h+ o' {# L 6  
7 int main() {
' R; K. V$ U& D! {$ n5 X 8  
. i  H6 p0 V! X. T5 T 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");
11     const int SIZE_IN = 8, SIZE_OUT = 8, SIZE_KEY = 16;
12     byte plain[SIZE_IN], crypt[SIZE_OUT], key[SIZE_KEY];
, B/ @# `- C" ^7 s7 M; g: E2 S' ^! T13  
' G/ e; I* s: K! v. z14     size_t size_in = hexStringToBytes(plainStr, plain);
+ S4 J: y; a6 s; `  n15     size_t size_key = hexStringToBytes(keyStr, key);
4 A5 O8 j) j' i; |; d% |2 X16  
" ]$ [0 x; @! X. J; x- ?0 t17     if (size_in != SIZE_IN || size_key != SIZE_KEY)
) W9 M9 p5 @- [+ u5 M! s) z18         return -1;
( u% i' J( J, F/ A19  
20     cout << "Plain: " << bytesToHexString(plain, size_in) << endl;
* C+ U$ f4 Q; D2 u% T21     cout << "Key  : " << bytesToHexString(key, size_key) << endl;
7 ^0 \9 _$ z7 F$ o5 W22  
' x7 ~) x! `9 H& H23     TEA tea(key, 16, true);
+ B4 ?2 ?( u2 C4 a24     tea.encrypt(plain, crypt);
' G) s; V+ C- [: m" \25     cout << "Crypt: " << bytesToHexString(crypt, SIZE_OUT) << endl;
26  
27     tea.decrypt(crypt, plain);
28     cout << "Plain: " << bytesToHexString(plain, SIZE_IN) << endl;
7 h6 U; b( \) L. q29     return 0;
! P8 V  ^1 @" ^' j+ B30 }

0 h6 M$ j; \2 u% L- o9 n本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/sailing0123/archive/2008/04/28/2339231.aspx
运行结果：
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
Crypt: 3B 3B 4D 8C 24 3A FD F2
Plain: AD DE E2 DB B3 E2 DB B3