TEA

TEA
Создатель	Дэвид Уилер и Роджер Нидхэм
Создан	1994 г.
Опубликован	1994 г.
Размер ключа	128 бит
Размер блока	64 бит
Число раундов	32
Тип	Сеть Фейстеля

В криптографии,Tiny Encryption Algorithm (TEA) — блочный алгоритм шифрования типа «Сеть Фейстеля». Алгоритм был разработан на факультете компьютерных наук Кембриджского университета Дэвидом Уилером (David Wheeler) и Роджером Нидхэмом (Roger Needham) и впервые представлен в 1994 году на симпозиуме по быстрым алгоритмам шифрования в Лёвене (Бельгия).

Шифр не патентован, широко используется в ряде криптографических приложений и широком спектре аппаратного обеспечения благодаря крайне низким требованиям к памяти и простоте реализации. Алгоритм имеет как программную реализацию на разных языках программирования, так и аппаратную реализацию на интегральных схемах типа FPGA.

Свойства

Алгоритм шифрования TEA основан на битовых операциях с 64-битным блоком, имеет 128-битный ключ шифрования. Стандартное количество раундов сети Фейстеля равно 64 (32 цикла), однако для достижения наилучшей производительности или шифрования, число циклов можно варьировать от 8 (16 раундов) до 64 (128 раундов). Сеть Фейстеля несимметрична из-за использования в качестве операции наложения сложения по модулю 32.

Достоинствами шифра являются его простота в реализации, небольшой размер кода и довольно высокая скорость выполнения, а также возможность оптимизации выполнения на стандартных 32-битных процессорах, так как в качестве основных операций используются операции исключающего «ИЛИ» (XOR), побитового сдвига и сложения по модулю 2³². Поскольку алгоритм не использует таблиц подстановки и раундовая функция довольно проста, алгоритму требуется не менее 16 циклов (32 раундов) для достижения эффективной диффузии, хотя полная диффузия достигается уже за 6 циклов (12 раундов).

Алгоритм имеет отличную устойчивость к линейному криптоанализу и довольно хорошую к дифференциальному криптоанализу. Главным недостатком этого алгоритма шифрования является его уязвимость к атакам по ключу (англ. Related-key attack). Из-за простого расписания ключей каждый ключ имеет 3 эквивалентных ключа. Это означает, что эффективная длина ключа составляет всего 126 бит, поэтому данный алгоритм не следует использовать в качестве хэш-функции.

Описание алгоритма

Исходный текст разбивается на блоки по 64 бита каждый. 128-битный ключ К делится на четыре 32-битных подключа K[0], K[1], K[2] и K[3]. На этом подготовительный процесс заканчивается, после чего каждый 64-битный блок шифруется на протяжении 32 циклов (64 раундов) по нижеприведённому алгоритму.

Предположим, что на вход n-го раунда (для 1 ≤ n ≤ 64) поступают правая и левая часть (L_n, R_n), тогда на выходе n-го раунда будут левая и правая части (L_n+1, R_n+1), которые вычисляются по следующим правилам:

L_n+1 = R_n.

Если n = 2 * i - 1 для 1 ≤ i ≤ 32 (нечётные раунды), то R_n+1 = L_n $\boxplus$ ( { [ R_n $\ll$ 4 ] $\boxplus$ K[0] } $\oplus$ { R_n $\boxplus$ i * δ } $\oplus$ { [ R_n $\gg$ 5 ] $\boxplus$ K[1] } )

Если n = 2 * i для 1 ≤ i ≤ 32 (чётные раунды), то R_n+1 = L_n $\boxplus$ ( { [ R_n $\ll$ 4 ] $\boxplus$ K[2] } $\oplus$ { R_n $\boxplus$ i * δ } $\oplus$ { [ R_n $\gg$ 5 ] $\boxplus$ K[3] } )

Где

• X $\boxplus$ Y – операция сложения чисел X и Y по модулю 2³².
• X $\oplus$ Y – побитовое исключающее «ИЛИ» (XOR) чисел X и Y, которое в языке программирования Си обозначается как X ^ Y
• X $\ll$ Y и X $\gg$ Y - операции побитового сдвига числа X на Y бит влево и вправо соответственно.
• Константа δ была выведена из Золотого сечения δ = 2654435769 = 9E3779B9_h. В каждом раунде константа умножается на номер цикла i. Это было сделано для предотвращения простых атак, основанных на симметрии раундов.

Также очевидно, что в алгоритме шифрования TEA нет как такового алгоритма расписания ключей. Вместо этого в нечётных раундах используются подключи К[0] и К[1], в нечётных – К[2] и К[3].

Ниже приведены примеры процедур шифрования и расшифрования на языке программирования Си.

Реализация

Реализация на языке программирования Си (адаптированный вариант кода, представленного в статье Дэвида Уилера и Роджера Нидхэма) функций шифрования и расшифрования с использованием алгоритма TEA:

#include <stdint.h>

void encrypt (uint32_t* v, uint32_t* k) {
    uint32_t v0=v[0], v1=v[1], sum=0, i;           /* set up */
    uint32_t delta=0x9e3779b9;                     /* a key schedule constant */
    uint32_t k0=k[0], k1=k[1], k2=k[2], k3=k[3];   /* cache key */
    for (i=0; i < 32; i++) {                       /* basic cycle start */
        sum += delta;
        v0 += ((v1<<4) + k0) ^ (v1 + sum) ^ ((v1>>5) + k1);
        v1 += ((v0<<4) + k2) ^ (v0 + sum) ^ ((v0>>5) + k3);
    }                                              /* end cycle */
    v[0]=v0; v[1]=v1;
}

void decrypt (uint32_t* v, uint32_t* k) {
    uint32_t v0=v[0], v1=v[1], sum=0xC6EF3720, i;       /* set up */
    uint32_t delta=0x9e3779b9;                          /* a key schedule constant */
    uint32_t k0=k[0], k1=k[1], k2=k[2], k3=k[3];        /* cache key */
    for (i=0; i<32; i++) {                              /* basic cycle start */
        v1 -= ((v0<<4) + k2) ^ (v0 + sum) ^ ((v0>>5) + k3);
        v0 -= ((v1<<4) + k0) ^ (v1 + sum) ^ ((v1>>5) + k1);
        sum -= delta;                                   
    }                                                   /* end cycle */
    v[0]=v0; v[1]=v1;
}

Комментарии:

• v — исходный текст состоящий из двух частей по 32 бита
• k — ключ состоящий из четырёх 32-битных частей

Изменения по сравнению с оригинальным кодом:

• используется тип uint32_t вследствие того, что он всегда имеет размер 32 бита в отличие от long (присутствующий в оригинальном коде), который может содержать 64 бита (например в некоторых 64 битных системах)
• исходный код не использует тип const
• в исходном коде опущены избыточные скобки в выражениях для v0 и v1, в данной модификации они оставлены для большей наглядности

Варианты алгоритма

Выявление ряда серьезных уязвимостей и слабых мест в исходном алгоритме TEA привело к скорому созданию его расширения — XTEA, который затем был так же исправлен и получил название XXTEA. Существует так же альтернативная модификация алгоритма TEA, получившая наименование RTEA. С использованием механизмов генетического программирования был создан алгоритм Raiden, призванный устранить уязвимости шифра TEA. Существует так же шифр GTEA, частично основанный на принципах TEA, имеющий 128-битный блок и использующий таблицы подстановки. В то же время, авторы алгоритма TEA на своей официальной странице обращают внимание на то, что в реальных условиях практического использования алгоритм TEA все еще остается довольно надежным и все найденные уязвимости, как правило, не являются критичными, к примеру, при передаче данных в реальном времени.

См. также

• XTEA

• XXTEA

• RTEA

• GTEA

• Блочный шифр

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