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

血刀老祖 · 发表于 2010-1-19 17:58:25

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）都是分组加密算法，它们很容易被描述，实现也很简单（典型的几行代码）。
TEA 算法最初是由剑桥计算机实验室的 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 个输入量。

天云上人 · 发表于 2010-1-19 19:47:00

8 n9 g6 k. i) ~# O: N5 v7 B
void encrypt(unsigned long *v, unsigned long *k) { % B; D3 Q% e ^" Z
unsigned long y=v[0], z=v[1], sum=0, i; /* set up */
' q4 y. h( h/ f5 `1 R
unsigned long delta=0x9e3779b9; /* a key schedule constant */ , N& ^- n8 m: r, O# |9 z) `
unsigned long a=k[0], b=k[1], c=k[2], d=k[3]; /* cache key */ J5 S7 n6 {3 c3 U" ~: h5 R
for (i=0; i < 32; i++) { /* basic cycle start */
9 s/ p, ~- i- m. I+ Q$ [# u
sum += delta;
1 a! P$ L" v$ \0 Z# C
y += ((z<<4) + a) ^ (z + sum) ^ ((z>>5) + b);
) [5 {& _ D0 G5 k# ?% P
z += ((y<<4) + c) ^ (y + sum) ^ ((y>>5) + d);/* end cycle */ 1 K# J N; e: ^- G
} - o, E+ m' B& l' u; x K4 ?& a7 L
v[0]=y;
; Z! V! R h$ c& q/ h) o5 Y) i3 y
v[1]=z;
$ |! V, }% x9 W% i& p
} 9 g! D! i# P6 U
+ _7 m2 h7 i- ?/ n* i( w- k
void decrypt(unsigned long *v, unsigned long *k) {
3 S# Q5 ^9 B& l. V6 b8 I
unsigned long y=v[0], z=v[1], sum=0xC6EF3720, i; /* set up */
. f( y, c) D% x4 k3 L. ~# L1 J8 w# T
unsigned long delta=0x9e3779b9; /* a key schedule constant */ . `& f. T( H9 @6 `. X2 _
unsigned long a=k[0], b=k[1], c=k[2], d=k[3]; /* cache key */
6 [6 a9 v7 j. X; r$ g. o' y
for(i=0; i<32; i++) { /* basic cycle start */
9 W. Z1 k. p4 |, Y$ J; Z' \
z -= ((y<<4) + c) ^ (y + sum) ^ ((y>>5) + d);
5 M8 g2 x R/ F2 x# B+ o
y -= ((z<<4) + a) ^ (z + sum) ^ ((z>>5) + b);
+ l% d6 @' B9 D" D
sum -= delta; /* end cycle */ # u O( t" Y$ f. I; G9 q# H# p
} # N7 V" s/ d C ^) `. y0 y: i) V
v[0]=y;
e" U( `* j; w$ j9 z& z
v[1]=z;
% c1 U. u' o- I8 {
}
2 m& d7 M* }$ E; w) j

复制代码

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

天云上人 · 发表于 2010-1-19 19:48:25

#ifndef UTIL_H
#define UTIL_H

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

typedef unsigned char byte;
typedef unsigned long ulong;

inline double logbase(double base, double x) {
return log(x)/log(base);
}

/*
*convert int to hex char.
*example:10 -> 'A',15 -> 'F'
*/
char intToHexChar(int x);

/*
*convert hex char to int.
*example:'A' -> 10,'F' -> 15
*/
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);

/*
*convert a hex string to a byte array.
*hex string format example:"AF B0 80 7D"
*/
size_t hexStringToBytes(const string &str, byte *out);

#endif/*UTIL_H*/

天云上人 · 发表于 2010-1-19 19:51:31

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

using namespace std;

char intToHexChar(int x) {
static const char HEX[16] = {
      '0', '1', '2', '3',
      '4', '5', '6', '7',
      '8', '9', 'A', 'B',
      'C', 'D', 'E', 'F'
};
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;
}

string bytesToHexString(const byte *in, size_t size) {
string str;
for (size_t i = 0; i < size; ++i) {
      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)
         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) {
      string b(str.substr(prevPos, currPos - prevPos));
      vec.push_back(b);
      prevPos = currPos + 1;
}
if (prevPos < str.size()) {
      string b(str.substr(prevPos));
      vec.push_back(b);
}
typedef vector<string>::size_type sz_type;
sz_type size = vec.size();
for (sz_type i = 0; i < size; ++i) {
      int a = hexCharToInt(vec[i][0]);
      int b = hexCharToInt(vec[i][1]);
      out[i] = a * 16 + b;
}
return size;
}

天云上人 · 发表于 2010-1-19 19:57:01

#ifndef TEA_H
#define TEA_H

/*
*for htonl,htonl
*do remember link "ws2_32.lib"
*/
#include <winsock2.h>
#include "util.h"

class 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);
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; }
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
byte _key[16]; //encrypt or decrypt key
};

#endif/*TEA_H*/

天云上人 · 发表于 2010-1-19 19:59:57

1 #include "tea.h"
2 #include <cstring> //for memcpy,memset
3
4 using namespace std;
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
12       memset(_key, 0, 16);
13 }
14
15 TEA::TEA(const TEA &rhs)
16 :_round(rhs._round)
17 ,_isNetByte(rhs._isNetByte) {
18    memcpy(_key, rhs._key, 16);
19 }
20
21 TEA& TEA::operator=(const TEA &rhs) {
22    if (&rhs != this) {
23       _round = rhs._round;
24       _isNetByte = rhs._isNetByte;
25       memcpy(_key, rhs._key, 16);
26    }
27    return *this;
28 }
29
30 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 }
37
38 void TEA::encrypt(const ulong *in, ulong *out) {
39
40    ulong *k = (ulong*)_key;
41    register ulong y = ntoh(in[0]);
42    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]);
47    register ulong delta = 0x9E3779B9; /* (sqrt(5)-1)/2*2^32 */
48    register int round = _round;
49    register ulong sum = 0;
50
51    while (round--) { /* basic cycle start */
52       sum += delta;
53       y += ((z << 4) + a) ^ (z + sum) ^ ((z >> 5) + b);
54       z += ((y << 4) + c) ^ (y + sum) ^ ((y >> 5) + d);
55    } /* end cycle */
56    out[0] = ntoh(y);
57    out[1] = ntoh(z);
58 }
59
60 void TEA::decrypt(const ulong *in, ulong *out) {
61
62    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]);
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 */
70    register int round = _round;
71    register ulong sum = 0;
72
73    if (round == 32)
74       sum = 0xC6EF3720; /* delta << 5*/
75    else if (round == 16)
76       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);
83       sum -= delta;
84    } /* end cycle */
85    out[0] = ntoh(y);
86    out[1] = ntoh(z);
87 }

需要说明的是TEA的构造函数：
TEA(const byte *key, int round = 32, bool isNetByte = false);
1.key - 加密或解密用的128-bit(16byte)密钥。
2.round - 加密或解密的轮数，常用的有64，32，16。
3.isNetByte - 用来标记待处理的字节是不是来自网络，为true时在加密/解密前先要转换成本地字节，执行加密/解密，然后再转换回网络字节。偷偷告诉你，QQ就是这样做的！

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

天云上人 · 发表于 2010-1-19 20:01:04

1 #include "tea.h"
2 #include "util.h"
3 #include <iostream>
4
5 using namespace std;
6
7 int main() {
8
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];
13
14    size_t size_in = hexStringToBytes(plainStr, plain);
15    size_t size_key = hexStringToBytes(keyStr, key);
16
17    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);
24    tea.encrypt(plain, crypt);
25    cout << "Crypt: " << bytesToHexString(crypt, SIZE_OUT) << endl;
26
27    tea.decrypt(crypt, plain);
28    cout << "Plain: " << bytesToHexString(plain, SIZE_IN) << endl;
29    return 0;
30 }

本文来自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

		自动登录	找回密码
密码			注册

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

unit.h

util.cpp

tea.h

tea.cpp

test.cpp