2018年8月27日

微型加密演算法 Tiny Encryption Algorithm (TEA)

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 A9CA5E6F

tea2.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 576829AA

tea.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 576829AA

TEA.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 576829AA

References

Tiny Encryption Algorithm

Java/J2ME implementation of the Tiny Encryption Algorithm

TEA、XTEA、XXTEA加密解密算法

介紹XXTEA加密算法

XXTEA encryption arithmetic library

TEA和QQTEA

TEA加密算法java版

一個長整數各自表述 (in 64-bit system)

Tiny-Encryption-Algorithm

TEA算法在QQ中的應用