Tiny Encryption Algorithm (TEA) 微型加密演算法是劍橋大學電腦實驗室的 David Wheeler 與 Roger Needham 在 1994年於 Fast Software Encryption workshop 發表的加密演算法。因為該演算法速度快，很容易實作，也很容易設計電路，因此常常被使用。
這個演算法在內地的很有名氣，主要因為騰訊 QQ 大量使用了這個演算法，進行資料加密的工作。
tea.c
原本找到的文件，提供了一個 C 語言的版本。因為 TEA 是針對 byte array 進行加解密，實作時要注意，是使用哪一種 CPU，如果是 Intel CPU，都是 Little Endian 的 byte order。
#include <stdio.h>
#include <stdint.h>
void encipher(unsigned long *const v,unsigned long *const w,
const unsigned long *const k)
{
register unsigned long y=v[0], z=v[1], sum=0;
register unsigned long delta= 0x9E3779B9;
register unsigned long a=k[0], b=k[1], c=k[2], d=k[3];
register unsigned long n=32;
while(n-->0)
{
sum += delta;
y += (z << 4)+a ^ z+sum ^ (z >> 5)+b;
z += (y << 4)+c ^ y+sum ^ (y >> 5)+d;
}
w[0]=y; w[1]=z;
}
void decipher(unsigned long *const v,unsigned long *const w,
const unsigned long *const k)
{
register unsigned long y=v[0], z=v[1];
register unsigned long delta=0x9E3779B9;
register unsigned long sum= delta * 32;
register unsigned long a=k[0],b=k[1], c=k[2], d=k[3];
register unsigned long n=32;
/* sum = delta<<5, in general sum = delta * n */
while(n-->0)
{
z -= (y << 4)+c ^ y+sum ^ (y >> 5)+d;
y -= (z << 4)+a ^ z+sum ^ (z >> 5)+b;
sum -= delta;
}
w[0]=y; w[1]=z;
}
#define htonl(A) ((((unsigned long)(A) & 0xff000000) >> 24) | \
(((unsigned long)(A) & 0x00ff0000) >> 8) | \
(((unsigned long)(A) & 0x0000ff00) << 8) | \
(((unsigned long)(A) & 0x000000ff) << 24))
#define ntohl htonl
#define ENCRYPTED_VALUE_POSITION_IN_CONN_REQ 16
void printlong(unsigned long l) {
unsigned long nl = ntohl(l);
printf("%lX ", nl);
}
int main() {
unsigned long u_auth_key[4] = {0x11223344, 0x55667788, 0x99AABBCC, 0xDDEEFF00};
char random_num[8] = {0x72, 0x13, 0x8F, 0x90, 0x57, 0x68, 0x29, 0xaa };
unsigned long encrypted_num[2] = {0};
unsigned long * p_rand_num = (unsigned long *) random_num;
char xnl_conn_req[24] = {0};
// 由 big endiness 轉為 little
*p_rand_num = ntohl(*p_rand_num);
*( p_rand_num + 1) = ntohl(*(p_rand_num + 1));
encipher(p_rand_num, encrypted_num, u_auth_key);
// 由 little 轉為 big
encrypted_num[0] = htonl(encrypted_num[0]);
encrypted_num[1] = htonl(encrypted_num[1]);
// printf("%lx %lx\n", encrypted_num[0], encrypted_num[1]);
printlong(encrypted_num[0]);
printlong(encrypted_num[1]);
}但是編譯後發現，加密後的結果是錯誤的。原因在於 unsigned long 這個資料型別，因為該資料型別在 64位元 CPU 的機器上，資料長度超過 32 bits。解決方式是在編譯時，要加上 -m32 這個參數。
$ gcc -m32 tea.c
$ ./a.out
C5E65710 A9CA5E6Ftea2.c
在 TEA Wiki 也提供了一個 C 語言的加解密版本，可以注意到他使用了 uint32_t 這個資料型別，uint32_t 在 UNIX 系統上，是固定為 32-bit unsigned interger，不管 CPU 是 32bits 或是 64bits 都一樣，所以使用這個資料型別會比 long 來得好。
tea2.c
#include <stdio.h>
#include <stdint.h>
void encrypt(uint32_t* v, uint32_t key[4], uint32_t delta) {
uint32_t v0=v[0], v1=v[1], sum=0, i; // set up
// uint32_t delta=0x12345678; // a key schedule constant
for (i=0; i < 32; i++) {
sum += delta;
v0 += ((v1<<4) + key[0]) ^ (v1 + sum) ^ ((v1>>5) + key[1]);
v1 += ((v0<<4) + key[2]) ^ (v0 + sum) ^ ((v0>>5) + key[3]);
}
v[0]=v0; v[1]=v1;
}
void decrypt (uint32_t* v, uint32_t key[4], uint32_t delta) {
uint32_t v0=v[0], v1=v[1], i; // set up
// uint32_t sum=0x468ACF00;
// uint32_t delta=0x12345678; // a key schedule constant
uint32_t sum = delta * 32; // delta << 5
// printf("%X %X %X\n", v0, v1, sum);
for (i=0; i<32; i++) {
v1 -= ((v0<<4) + key[2]) ^ (v0 + sum) ^ ((v0>>5) + key[3]);
v0 -= ((v1<<4) + key[0]) ^ (v1 + sum) ^ ((v1>>5) + key[1]);
sum -= delta;
// printf("%X %X %X\n", v0, v1, sum);
}
v[0]=v0; v[1]=v1;
}
int main()
{
uint32_t v[] = {0x72138F90, 0x576829AA};
uint32_t key[4]={0x11223344, 0x55667788, 0x99AABBCC, 0xDDEEFF00};
uint32_t delta=0x9E3779B9;
printf("Original Values: ");
printf("%X %X\n", v[0], v[1]);
encrypt(v, key, delta);
printf("Encrypted : ");
printf("%X %X\n", v[0], v[1]);
decrypt(v, key, delta);
printf("Decrypted : ");
printf("%X %X\n", v[0], v[1]);
return 0;
}執行結果如下
$ gcc tea2.c
$ ./a.out
Original Values: 72138F90 576829AA
Encrypted : C5E65710 A9CA5E6F
Decrypted : 72138F90 576829AAtea.py
另外如果是 python，可以參考 C 語言的寫法，直接用 ctypes 進行開發。
tea.py
#!/usr/bin/env python
#-*- coding: utf-8 -*-
import sys
from ctypes import *
def encipher(v, k):
y = c_uint32(v[0])
z = c_uint32(v[1])
sum = c_uint32(0)
delta = c_uint32(0x9E3779B9).value
n = 32
w = [0,0]
while(n>0):
sum.value += delta
y.value += ( z.value << 4 ) + k[0] ^ z.value + sum.value ^ ( z.value >> 5 ) + k[1]
z.value += ( y.value << 4 ) + k[2] ^ y.value + sum.value ^ ( y.value >> 5 ) + k[3]
n -= 1
w[0] = y.value
w[1] = z.value
return w
def decipher(v, k):
y = c_uint32(v[0])
z = c_uint32(v[1])
delta = c_uint32(0x9E3779B9).value
sum = c_uint32(delta * 32)
n = 32
w = [0,0]
while(n>0):
z.value -= ( y.value << 4 ) + k[2] ^ y.value + sum.value ^ ( y.value >> 5 ) + k[3]
y.value -= ( z.value << 4 ) + k[0] ^ z.value + sum.value ^ ( z.value >> 5 ) + k[1]
sum.value -= delta
n -= 1
w[0] = y.value
w[1] = z.value
return w
if __name__ == "__main__":
key = [0x11223344, 0x55667788, 0x99AABBCC, 0xDDEEFF00]
v = [0x72138F90, 0x576829AA]
enc = encipher(v,key)
print "Original Values: " + ' '.join([format(i, 'x').upper() for i in v])
print "Encrypted: " + ' '.join([format(i, 'x').upper() for i in enc])
dec = decipher(enc,key)
print "Decrypted: " + ' '.join([format(i, 'x').upper() for i in dec])執行結果
$ python tea.py
Original Values: 72138F90 576829AA
Encrypted: C5E65710 A9CA5E6F
Decrypted: 72138F90 576829AATEA.java
這是 Java 語言的版本
public class TEA {
public static int[] encrypt(int[] block, int[] key) {
int i = block[0];
int j = block[1];
int sum = 0;
int delta = 0x9E3779B9;
for (int k = 0; k < 32; ++k) {
sum += delta;
i += (j << 4 & 0xfffffff0) + key[0] ^ j + sum ^ (j >> 5 & 0x7ffffff) + key[1];
j += (i << 4 & 0xfffffff0) + key[2] ^ i + sum ^ (i >> 5 & 0x7ffffff) + key[3];
}
block[0] = i;
block[1] = j;
return block;
}
public static int[] decrypt(int[] block, int[] key) {
int i = block[0];
int j = block[1];
int delta = 0x9E3779B9;
int sum = delta*32; // sum=468ACF00
// System.out.println("sum="+byteToUnsignedHex(sum));
// System.out.println("i, j, sum="+byteToUnsignedHex(i)+", "+byteToUnsignedHex(j)+", "+byteToUnsignedHex(sum));
for (int k = 0; k < 32; ++k) {
j -= (i << 4 & 0xfffffff0) + key[2] ^ i + sum ^ (i >> 5 & 0x7ffffff) + key[3];
i -= (j << 4 & 0xfffffff0) + key[0] ^ j + sum ^ (j >> 5 & 0x7ffffff) + key[1];
sum -= delta;
// System.out.println("i, j, sum="+byteToUnsignedHex(i)+", "+byteToUnsignedHex(j)+", "+byteToUnsignedHex(sum));
}
block[0] = i;
block[1] = j;
return block;
}
public static String byteToUnsignedHex(int i) {
String hex = Integer.toHexString(i).toUpperCase();
while(hex.length() < 8){
hex = "0" + hex;
}
return hex;
}
public static String intArrToHex(int[] arr) {
StringBuilder builder = new StringBuilder(arr.length * 8 + arr.length-1);
for (int b : arr) {
builder.append(byteToUnsignedHex(b));
builder.append(" ");
}
return builder.toString();
}
public static void main(String[] args){
int[] key = new int[]{0x11223344, 0x55667788, 0x99AABBCC, 0xDDEEFF00};
int[] data = new int[]{0x72138F90, 0x576829AA};
System.out.println("Original Values: "+intArrToHex(data));
int[] enc = TEA.encrypt(data, key);
System.out.println("Encrypted : "+intArrToHex(enc));
int[] dec = TEA.decrypt(enc, key);
System.out.println("Decrypted : "+intArrToHex(dec));
}
}執行結果
$ javac TEA.java
$ java TEA
Original Values: 72138F90 576829AA
Encrypted : C5E65710 A9CA5E6F
Decrypted : 72138F90 576829AAReferences
Java/J2ME implementation of the Tiny Encryption Algorithm
XXTEA encryption arithmetic library
沒有留言:
張貼留言