TEA Series

描述

TEA

TEA (Tiny Encryption Algorithm) 是一种块加密的对称加密算法

TEA使用一个128位(16字节)的密钥对64位(8字节)的明文进行分组运算, 明文被分成2个32位的分组( $L_0$, $L_1$), 密钥被分为4个32位的分组 ($K_0$, $K_1$, $K_2$, $K_3$). 加密涉及两轮的重复应用, 定义第$i$轮与第$i+1$轮运算如下:

$$\begin{array}{rl}& L_{i+1}=L_i+F(R_i,K_0,K_1,{\delta }_i)\\ & R_{i+1}=R_i+F(L_{i+1},K_2,K_3,{\delta }_i)\end{array}$$

这里$F$定义:

$$F(M,K_j,K_k,{\delta }_i)=((M\ll 4)\oplus K_j)\oplus ((M\gg 5)\oplus K_k)\oplus (M+{\delta }_i)$$

其中${\delta }_i$是一个预定义的常量序列, 一般使用

$${\delta }_i=(0x9e3779b9\times i)mod0xffffffff$$

这里的 $0x9e3779b9$ 其实在数学上等于 $\frac{\sqrt{5}-1}{2}\times 2^{32}$

XTEA

XTEA (eXtended TEA) 是 TEA的升级版

XTEA也使用一个128位(16字节)的密钥对64位(8字节)的明文进行分组运算, 明文被分成2个32位的分组( $L_0$, $L_1$), 密钥被分为4个32位的分组 ($K_0$, $K_1$, $K_2$, $K_3$), 不过加密的的轮函数变了:

$$\begin{array}{rl}& L_{i+1}=L_i+F(R_i,Sum,K[Sum\&3])\\ & Sum=Sum+\delta \\ & R_{i+1}=R_i+F(L_{i+1},Sum,K[(Sum\gg 11)\&3])\end{array}$$

此时$F$为:

$$F(M,Sum,K)=(((M\ll 4)\oplus (M\gg 5))+M)\oplus (Sum+K)$$

$\delta$也一般使用$0x9e3779b9$

XXTEA (BTEA)

XXTEA (Corrected Block TEA) , 其特点是运行在可变长度的块上, 这些块大小为32位的任意倍数(最小64位), 密钥仍然是128位, 被分为4个32位的分组. 对于较长的消息, XXTEA可能比XTEA更高效.

XXTEA 的轮数由数据长度决定 $rounds=6+52/n$, $n$为待加密数据的长度

初始情况下, sum的值为0, z的值为待加密数据的最后一个字节, 在每一轮中进行如下操作

sum += delta;

e = (sum >> 2) & 3;
for r = 0 to datalen do
	y = data[(r + 1) % data];
	data[r] += MX(z, y, key, r, e, sum)

sum = sum.wrapping_add(DELTA);
let e = (sum >> 2) & 3;
for r in 0..block.len() {
	// round
	let y = block[(r + 1) % block.len()]; // right neighbour
	block[r] = block[r].wrapping_add(mx(z, y, key, r, e as usize, sum));
	z = block[r];
}

$\delta$一般是$0x9e3779b9$, 其中$MX$的定义为:

$$MX(z,y,key,r,e,sum)=(((z\gg 5)\oplus (y\ll 2))+((y\gg 3)\oplus (z\ll 4)))\oplus ((sum\oplus y)+(key[(r\oplus e)\&3]\oplus z))$$

其结构是

$$(PartA+PartB)\oplus (PartC+PartD)$$

$PartA=(z\gg 5)\oplus (y\ll 2)$

$PartB=(y\gg 3)\oplus (z\ll 4)$

$PartC=sum\oplus y$,

$PartD=key[(r\oplus e)\&3]\oplus z$,

这里给出2个实现

fn mx(z: u32, y: u32, key: &[u32], r: usize, e: usize, sum: u32) -> u32 {
    let term1 = ((z >> 5) ^ (y << 2)).wrapping_add((y >> 3) ^ (z << 4));
	let term2 = (sum ^ y).wrapping_add(key[(r ^ e) & 3] ^ z);
	
	term1 ^ term2
}

def mx(z, y, key, r, e, sum) -> int:
	part1 = (z >> 5) ^ (y << 2)
	part2 = (y >> 3) ^ (z << 4)
	part3 = sum ^ y
	part4 = key[(e ^ r) & 3] ^ z
	
	return (part1 + part2) ^ (part3 + part4)

实现

TEA

• rust

use std::mem;
const DELTA: u32 = 0x9E3779B9;
 
fn signed_tea(data: u32, key1: u32, key2: u32, delta: u32) -> u32 {
    let p1 = data.wrapping_shl(4).wrapping_add(key1);
    let p2 = data.wrapping_shr(5).wrapping_add(key2);
    let p3 = data.wrapping_add(delta);
    p1 ^ p2 ^ p3
}
 
fn encrypt_block(data: u64, key: [u32; 4], rounds: usize) -> u64 {
    let [mut v0, mut v1] = unsafe { mem::transmute::<u64, [u32; 2]>(data) };
    for i in 1..=rounds {
        v0 = v0.wrapping_add(signed_tea(v1, key[0], key[1], DELTA.wrapping_mul(i as u32)));
        v1 = v1.wrapping_add(signed_tea(v0, key[2], key[3], DELTA.wrapping_mul(i as u32)));
    }
    unsafe { mem::transmute::<[u32; 2], u64>([v0, v1]) }
}
 
fn decrypt_block(data: u64, key: [u32; 4], rounds: usize) -> u64 {
    let [mut v0, mut v1] = unsafe { mem::transmute::<u64, [u32; 2]>(data) };
    for i in (1..=rounds).rev() {
        v1 = v1.wrapping_sub(signed_tea(v0, key[2], key[3], DELTA.wrapping_mul(i as u32)));
        v0 = v0.wrapping_sub(signed_tea(v1, key[0], key[1], DELTA.wrapping_mul(i as u32)));
    }
    unsafe { mem::transmute::<[u32; 2], u64>([v0, v1]) }
}

XTEA

• rust

use std::mem;
const DELTA: u32 = 0x9E3779B9;
fn encrypt_block(data: u64, key: [u32; 4], rounds: usize) -> u64 {
    let [mut v0, mut v1] = unsafe { mem::transmute::<u64, [u32; 2]>(data) };
    let mut sum: u32 = 0;
    for _ in 0..rounds {
        v0 = v0.wrapping_add(
            (v1.wrapping_shl(4) ^ v1.wrapping_shr(5)).wrapping_add(v1)
                ^ sum.wrapping_add(key[sum as usize & 3]),
        );
        sum = sum.wrapping_add(DELTA);
        v1 = v1.wrapping_add(
            (v0.wrapping_shl(4) ^ v0.wrapping_shr(5)).wrapping_add(v0)
                ^ sum.wrapping_add(key[(sum as usize >> 11) & 3]),
        );
    }
    unsafe { mem::transmute::<[u32; 2], u64>([v0, v1]) }
}
 
fn decrypt_block(data: u64, key: [u32; 4], rounds: usize) -> u64 {
    let [mut v0, mut v1] = unsafe { mem::transmute::<u64, [u32; 2]>(data) };
    let mut sum: u32 = DELTA.wrapping_mul(rounds as u32);
    for _ in 0..rounds {
        v1 = v1.wrapping_sub(
            (v0.wrapping_shl(4) ^ v0.wrapping_shr(5)).wrapping_add(v0)
                ^ sum.wrapping_add(key[(sum as usize >> 11) & 3]),
        );
        sum = sum.wrapping_sub(DELTA);
        v0 = v0.wrapping_sub(
            (v1.wrapping_shl(4) ^ v1.wrapping_shr(5)).wrapping_add(v1)
                ^ sum.wrapping_add(key[sum as usize & 3]),
        );
    }
    unsafe { mem::transmute::<[u32; 2], u64>([v0, v1]) }
}

XXTEA

• rust

use std::slice;
const DELTA: u32 = 0x9E3779B9;
fn mx(z: u32, y: u32, key: &[u32], r: usize, e: usize, sum: u32) -> u32 {
    (((z >> 5) ^ (y << 2)).wrapping_add((y >> 3) ^ (z << 4)))
        ^ ((sum ^ y).wrapping_add(key[(r ^ e) & 3] ^ z))
}
 
fn as_u32_slice(x: &[u8]) -> &[u32] {
    unsafe { slice::from_raw_parts(x.as_ptr() as *const u32, x.len() / 4) }
}
 
fn as_u32_slice_mut(x: &mut [u8]) -> &mut [u32] {
    unsafe { slice::from_raw_parts_mut(x.as_mut_ptr() as *mut u32, x.len() / 4) }
}
 
pub fn encrypt(block: &mut [u8], key: &[u8]) {
    assert!(key.len() == 16);
    assert!((block.len() & 3) == 0);
 
    let key = as_u32_slice(key);
    let block = as_u32_slice_mut(block);
 
    let rounds = 6 + 52 / block.len();
    let n = block.len() - 1;
 
    let mut sum = 0u32;
    let mut z = block[n]; // left neighbour for the first round
    for _ in 0..rounds {
        // cycle
        sum = sum.wrapping_add(DELTA);
        let e = (sum >> 2) & 3;
        for r in 0..block.len() {
            // round
            let y = block[(r + 1) % block.len()]; // right neighbour
            block[r] = block[r].wrapping_add(mx(z, y, key, r, e as usize, sum));
            z = block[r];
        }
    }
}
 
pub fn decrypt(block: &mut [u8], key: &[u8]) {
    assert!(key.len() == 16);
    assert!((block.len() & 3) == 0);
 
    let key = as_u32_slice(key);
    let block = as_u32_slice_mut(block);
 
    let rounds = 6 + 52 / block.len();
 
    let mut sum = (rounds as u32).wrapping_mul(DELTA);
    let mut y = block[0];
    for _ in 0..rounds {
        // cycle
        let e = (sum >> 2) & 3;
        for r in (0..block.len()).rev() {
            // round
            let z = block[(r + block.len() - 1) % block.len()];
            block[r] = block[r].wrapping_sub(mx(z, y, key, r, e as usize, sum));
            y = block[r];
        }
        sum = sum.wrapping_sub(DELTA);
    }
}