Light-industry-up.ru

Экосистема промышленности

XXTEA

28-06-2023

XXTEA
Создатель:

Дэвид Вилер
Создан:

1998 г.
Опубликован:

1998 г.
Размер ключа:

128 бит
Размер блока:

64 бит и более
Число раундов:

зависит от размера блока 52 + 6 * кол-во 32-разрядных чисел в блоке
6-32 полных циклов
Тип:

Сеть Фейстеля


XXTEA — расширение шифроалгоритма XTEA, опубликованное в 1998 году. Исправлена уязвимость в алгоритме, найденная Markuu-Juhani Saarinen. Отличительной особенностью алгоритма является также возможность зашифровки блоков любого кратного 32 битам размера (минимальный размер 64 бита), в то время как другие алгоритмы данного семейства TEA, XTEA, XTEA-3, Raiden и RTEA используют блоки фиксированного размера, равного двум или четырем 32-х битным числам.

Т.к. это блочный шифроалгоритм, где длина блока 64-бит, а длина данных может быть не кратна 64-битам, значения всех байтов дополняющих блок до кратности в 64-бит устанавливается в 0x01 .

Содержание

Пример реализации

  #define MX  ( (((z>>5)^(y<<2))+((y>>3)^(z<<4)))^((sum^y)+(k[(p&3)^e]^z)) )
 
  long btea(long* v, long n, long* k) {
    unsigned long z /* = v[n-1] */, y=v[0], sum=0, e, DELTA=0x9e3779b9;
    long p, q ;
    if (n > 1) {          /* Coding Part */
      z=v[n-1];           /* Moved z=v[n-1] to here, else segmentation fault in decode when n < 0 */
      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 Part */
      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;
        sum -= DELTA;
      }
      return 0;
    }
    return 1;
  }

Пример реализации на PHP

 function long2str($v, $w) {  
     $len = count($v);  
     $n = ($len - 1) << 2;  
     if ($w) {  
         $m = $v[$len - 1];  
         if (($m < $n - 3) || ($m > $n)) return false;  
         $n = $m;  
     }  
     $s = array();  
     for ($i = 0; $i < $len; $i++) {  
         $s[$i] = pack("V", $v[$i]);  
     }  
     if ($w) {  
         return substr(join('', $s), 0, $n);  
     } else {  
         return join('', $s);  
     }  
 }  
 
 // Старая реализация!  
 //function str2long($s, $w) {  
 //    $v = unpack("V*", $s. str_repeat("\0", (4 - strlen($s) % 4) & 3));  
 //    $v = array_values($v);  
 //    if ($w) {  
 //        $v[count($v)] = strlen($s);  
 //    }  
 //    return $v;  
 //}  
 
function str2long($s, $w) {     
    $str_len = mb_strlen($s, '8bit'); // подсчет количества байт(!) в строке. Актуально для многобайтных строк (например UTF-8)
 
    $v = unpack("V*", $s. str_repeat("\0", (4 - $str_len % 4) & 3));
    $v = array_values($v);
    if ($w) {
        // $v[count($v)] = strlen($s);
        $v[] = $str_len;
    }
    return $v;
}
 
 
 function int32($n) {  
     while ($n >= 2147483648) $n -= 4294967296;  
     while ($n <= -2147483649) $n += 4294967296;  
     return (int)$n;  
 }  
 
 function xxtea_encrypt($str, $key) {
     $key = md5(md5($key).strrev($key));
     if ($str == "") {  
         return "";  
     }  
     $v = str2long($str, true);  
     $k = str2long($key, false);  
     if (count($k) < 4) {  
         for ($i = count($k); $i < 4; $i++) {  
             $k[$i] = 0;  
         }  
     }  
     $n = count($v) - 1;  
 
     $z = $v[$n];  
     $y = $v[0];  
     $delta = 0x9E3779B9;  
     $q = floor(6 + 52 / ($n + 1));  
     $sum = 0;  
     while (0 < $q--) {  
         $sum = int32($sum + $delta);  
         $e = $sum >> 2 & 3;  
         for ($p = 0; $p < $n; $p++) {  
             $y = $v[$p + 1];  
             $mx = int32((($z >> 5 & 0x07ffffff) ^ $y << 2) + (($y >> 3 & 0x1fffffff) ^ $z << 4)) ^ int32(($sum ^ $y) + ($k[$p & 3 ^ $e] ^ $z));  
             $z = $v[$p] = int32($v[$p] + $mx);  
         }  
         $y = $v[0];  
         $mx = int32((($z >> 5 & 0x07ffffff) ^ $y << 2) + (($y >> 3 & 0x1fffffff) ^ $z << 4)) ^ int32(($sum ^ $y) + ($k[$p & 3 ^ $e] ^ $z));  
         $z = $v[$n] = int32($v[$n] + $mx);  
     }  
     return long2str($v, false);  
 }  
 
 function xxtea_decrypt($str, $key) {
     $key = md5(md5($key).strrev($key));  
     if ($str == "") {  
         return "";  
     }  
     $v = str2long($str, false);  
     $k = str2long($key, false);  
     if (count($k) < 4) {  
         for ($i = count($k); $i < 4; $i++) {  
             $k[$i] = 0;  
         }  
     }  
     $n = count($v) - 1;  
 
     $z = $v[$n];  
     $y = $v[0];  
     $delta = 0x9E3779B9;  
     $q = floor(6 + 52 / ($n + 1));  
     $sum = int32($q * $delta);  
     while ($sum != 0) {  
         $e = $sum >> 2 & 3;  
         for ($p = $n; $p > 0; $p--) {  
             $z = $v[$p - 1];  
             $mx = int32((($z >> 5 & 0x07ffffff) ^ $y << 2) + (($y >> 3 & 0x1fffffff) ^ $z << 4)) ^ int32(($sum ^ $y) + ($k[$p & 3 ^ $e] ^ $z));  
             $y = $v[$p] = int32($v[$p] - $mx);  
         }  
         $z = $v[$n];  
         $mx = int32((($z >> 5 & 0x07ffffff) ^ $y << 2) + (($y >> 3 & 0x1fffffff) ^ $z << 4)) ^ int32(($sum ^ $y) + ($k[$p & 3 ^ $e] ^ $z));  
         $y = $v[0] = int32($v[0] - $mx);  
         $sum = int32($sum - $delta);  
     }  
     return long2str($v, true);  
 }

Безопасность

Существует эффективная дифференциальная атака на XXTEA и все шифры с аналогичной, опубликованная Elias Yarrkov. Впрочем, практическая эффективность атаки пока не доказана однозначно. [1]

Примечания

  1. Исходная статья с реализацией атаки на XXTEA и примером кода

Ссылки

  • David J. Wheeler and Roger M. Needham. «Correction to xtea.» Technical report, Computer Laboratory, University of Cambridge, October 1998 (PDF).
  • Roger M. Needham and David J. Wheeler. «Tea extensions.» Technical report, Computer Laboratory, University of Cambridge, October 1997 (PDF).

XXTEA.

© 2014–2023 light-industry-up.ru, Россия, Краснодар, ул. Листопадная 53, +7 (861) 501-67-06