Encryption TEA, XTEA, XXTEA

The content of the article

• Description of the TEA encryption algorithm

  
  
  
  
  

• TEA implementation

  
  
  
  
  

• Eliminate critical TEA errors and get XTEA (Block TEA)

  
  
  
  
  

• XTEA implementation

  
  
  
  
  

• Better yet: XXTEA (Corrected Block TEA)

  
  
  
  
  

• Cryptanalysis of encryption algorithms

  
  
  
  
  

Introduction

Let's consider some definitions used in the article. There are two types of encryption: symmetric and asymmetric .

In symmetric encryption algorithms, the same key is used to encrypt data and to decode them. This key should be known only by the sender and the recipient, otherwise the data in the hands of attackers is essentially not encrypted. A person, knowing the key, who should not know, can decrypt the ciphertext and find out that you asked a friend to buy pasta in the store.

In asymmetric encryption algorithms, not one key is already used, but two: public and private . Data is encrypted with a public key, decrypted only with a private one. The public key can be distributed to everyone, but the private key must be kept secret.

TEA, XTEA, XXTEA . , , , .

, , .

.

TEA

TEA a.k.a. Tiny Encryption Algorithm -- . , , .

. 64 , 32 : . 64, . : 32 2 . -- . . :

-- , . ,

-- X Y ( )

-- - XOR

--

n- , : , :

:

:

:

, . :

TEA

, TEA . : David J. Wheeler Roger M. Needham. -- .

• k[0], k[1], k[2], k[3] -- ,

  
  
  
  
  

• v[0], v[1] -- ,

  
  
  
  
  

• encode -- (true), , (false),

  
  
  
  
  

void tea(long* v, long* k, bool encode) {
  unsigned long y = v[0];
  unsigned long z = v[1];
  unsigned long sum = 0;
  unsigned long delta = 0x9e3779b9;
  unsigned long n = 32;
  
  if(encode) {
    
    // encoding
  
    while(n-- > 0) {
      sum += delta;
      y += ((z << 4) + k[0]) ^ (z + sum) ^ ((z >> 5) + k[1]);
      z += ((y << 4) + k[2]) ^ (y + sum) ^ ((y >> 5) + k[3]);
    }
  
  } else {
    
    // decoding
  
    sum = delta << 5;
  
    while(n-- > 0) {
      z -= ((y << 4) + k[2]) ^ (y + sum) ^ ((y >> 5) + k[3]);
      y -= ((z << 4) + k[0]) ^ (z + sum) ^ ((z >> 5) + k[1]);
      sum -= delta;
    }
  }
  
  v[0] = y;
  v[1] = z;
  
  return;
}
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

XTEA

TEA , , XTEA.

XTEA a.k.a. eXtended TEA -- , TEA. David J. Wheeler Roger M. Needham. TEA, 64 . , TEA , . XTEA . ( 4).

. n- , :, :

:

:

:

:

XTEA

, David J. Wheeler Roger M. Needham . , ( ), .

• v -- 2

  
  
  
  
  

• k -- 4

  
  
  
  
  

• N -- ( 32)

  
  
  
  
  

• long -- 32

  
  
  
  
  

void xtea(long* v, long* k, long N) {
  unsigned long y = v[0];
  unsigned long z = v[1];
  unsigned long delta = 0x9e3779b9;
  
  if(N > 0) {
    
    // encoding
    
    unsigned long limit = delta * N;
    unsigned long sum = 0;
    
    while(sum != limit) {
      y += (z << 4 ^ z >> 5) + z ^ sum + k[sum & 3];
      sum += delta;
      z += (y << 4 ^ y >> 5) + y ^ sum + k[sum >> 11 & 3];
    }
    
  } else {
    
    // decoding
    
    unsigned long sum = delta * (-N);
    
    while (sum) {
      z -= (y << 4 ^ y >> 5) + y ^ sum + k[sum >> 11 & 3];
      sum -= delta;
      y -= (z << 4 ^ z >> 5) + z ^ sum + k[sum & 3];
    }
    
  }
  
  v[0] = y;
  v[1] = z;
  
  return;
}
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

XTEA : XTEA-1, XTEA-2, XTEA-3. . .

XXTEA

XXTEA a.k.a. Corrected Block TEA (.. XTEA Block TEA) -- , XTEA. , David J. Wheeler Roger M. Needham, . , , , :

• ,

  
  
  
  
  

• (, ), ,

  
  
  
  
  

• ,

  
  
  
  
  

• " ", ,

  
  
  
  
  

• , , 60 , , DES

  
  
  
  
  

, XXTEA . , , , , . . n- :

. , . ( ): . :

• 

  
  
  
  
  

• 

  
  
  
  
  

:

-:

XXTEA

, -- David J. Wheeler Roger M. Needham. .

• v -- 2

  
  
  
  
  

• k -- 4

  
  
  
  
  

• N --

  
  
  
  
  

• long -- 32

  
  
  
  
  

#define MX (z >> 5 ^ y << 2) + (y >> 3 ^ z << 4) ^ (sum ^ y) + (k[p & 3 ^ e] ^ z)

long xxtea(long* v, long * k, long N) {
  unsigned long z = v[N - 1];
  unsigned long y = v[0];
  unsigned long sum = 0;
  unsigned long e = 0;
  unsigned long delta = 0x9e3779b9;
  
  long m = 0;
  long p = 0;
  long q = 0;
  
  if(N > 1) {
    
    // encoding
    
    q = 6 + 52 / N;
    
    while(q-- > 0) {
      sum += delta;
      e = sum >> 2 & 3;
      for(p = 0; p < N - 1; p++) {
        y = v[p + 1];
        z = v[p] += MX;
      }
      y = v[0];
      z = v[N - 1] += MX;
    }
    
    return 0;
  } else if(N < -1) {
    
    // decoding
    
    N = -N;
    q = 6 + 52 / N;
    sum = q * delta;
    
    while(sum != 0) {
      e = sum >> 2 & 3;
      for(p = N - 1; p > 0; p--) {
        z = v[p - 1];
        y = v[p] -= MX;
      }
      z = v[N - 1];
      y = v[0] -= MX;
    }
    
    return 0;
  }
  
  return 1;
}
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

TEA, XTEA, XXTEA

TEA . 17 . " " TEA , ( ). : , .

XTEA, , , TEA. - ( XOR) XTEA , TEA. XTEA -- .

XXTEA . E. Yarrkov 2010 XXTEA . . 212 , 6 , . E. Yarrkov , .

• Roger M. Needham and David J. Wheeler: TEA, a Tiny Encryption Algorithm

  
  
  
  
  

• A. Roger M. Needham and David J. Wheeler: TEA extensions

  
  
  
  
  

• David J. Wheeler, Roger M. Needham: Correction to XTEA

  
  
  
  
  

• Elias Yarrkov: Cryptoanalysis of XXTEA