Т-функция

Т-функция VEST-4 с последующим транспозиционным слоем

В криптографии Т -функция — это биективное отображение, которое обновляет каждый бит состояния способом , который можно описать как $x_{i}'=x_{i}+f(x_{0},\cdots ,x_{i-1})$или, проще говоря, функция обновления, в которой каждый бит состояния обновляется линейной комбинацией того же бита и функцией подмножества его менее значимых битов. Если каждый менее значимый бит включен в обновление каждого бита состояния, такая Т-функция называется треугольной . Благодаря своей биективности (отсутствие коллизий и, следовательно, отсутствие потерь энтропии) независимо от используемых логических функций и независимо от выбора входных данных (пока все они поступают с одной стороны выходного бита), Т-функции сейчас широко используются в криптография для создания блочных шифров , потоковых шифров , PRNG и хеш-функций . Т-функции были впервые предложены в 2002 году А. Климовым и А. Шамиром в статье «Новый класс обратимых отображений». Такие шифры, как TSC-1 , TSC-3 , TSC-4 , ABC , Мир-1 и VEST, построены с использованием различных типов Т-функций.

Поскольку арифметические операции, такие как сложение , вычитание и умножение, также являются Т-функциями (треугольными Т-функциями), можно создавать эффективные с точки зрения программного обеспечения словные Т-функции путем объединения побитовой логики с арифметическими операциями. Еще одним важным свойством Т-функций, основанных на арифметических операциях, является предсказуемость их периода , что весьма привлекательно для криптографов. Хотя треугольные Т-функции по своей природе уязвимы для атак типа «угадай и определи», хорошо выбранные побитовые транспозиции между раундами могут нейтрализовать этот дисбаланс. В программно-эффективных шифрах это можно сделать путем чередования арифметических операций с операциями перестановки байтов и, в небольшой степени, с побитового вращения операциями . Однако треугольные Т-функции остаются крайне неэффективными в аппаратном обеспечении.

Т-функции не имеют никаких ограничений на типы и ширину функций обновления, используемых для каждого бита. Последующее транспонирование выходных битов и итерация Т-функции также не влияют на биективность. Эта свобода позволяет разработчику выбирать функции обновления или S-блоки , которые удовлетворяют всем остальным криптографическим критериям, и даже выбирать произвольные или зависящие от ключа функции обновления (см. семейный ключ ).

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

Ссылки

• Климов, Александр; Шамир, Ади (2002). «Новый класс обратимых отображений» (PDF) . Криптографическое оборудование и встраиваемые системы — CHES 2002 . Конспекты лекций по информатике. Том. 2523. Шпрингер-Верлаг . стр. 470–483. дои : 10.1007/3-540-36400-5_34 . ISBN  978-3-540-00409-7 . S2CID   29129205 .
• Климов, Александр; Шамир, Ади (2003). «Криптографические приложения Т-функций». Избранные области криптографии . Конспекты лекций по информатике. Том. 3006. Шпрингер-Верлаг. стр. 248–261. дои : 10.1007/978-3-540-24654-1_18 . ISBN  978-3-540-21370-3 . S2CID   30281166 .
• Климов, Александр; Шамир, Ади (2004). «Новые криптографические примитивы на основе многословных Т-функций». Быстрое программное шифрование . Конспекты лекций по информатике. Том. 3017. Шпрингер-Верлаг. стр. 1–15. дои : 10.1007/978-3-540-25937-4_1 . ISBN  978-3-540-22171-5 .
• Даум, Магнус (2005). «Узкие Т-функции». Быстрое программное шифрование . Конспекты лекций по информатике. Том. 3557. Шпрингер-Верлаг. стр. 50–67. дои : 10.1007/11502760_4 . ISBN  978-3-540-26541-2 .
• Хун, Джин; Ли, Дон Хун; Ём, Ёнджин; Хан, Дэван (2005). «Новый класс Т-функций одного цикла». Быстрое программное шифрование . Конспекты лекций по информатике. Том. 3557. Шпрингер-Верлаг. стр. 68–82. дои : 10.1007/11502760_5 . ISBN  978-3-540-26541-2 .
• Климов, Александр; Шамир, Ади (2005). «Новые применения Т-функций в блочных шифрах и хеш-функциях». Быстрое программное шифрование . Конспекты лекций по информатике. Том. 3557. Шпрингер-Верлаг. стр. 18–31. дои : 10.1007/11502760_2 . ISBN  978-3-540-26541-2 .