Latin squares and their applications in cryptography.pdf Подсчёт числа латинских квадратов порядка n - сложная комбинаторная задача,их точное число известно только для n от 1 до 11 [1].Латинские квадраты находят применение в комбинаторике, алгебре (изучение ла-тинских квадратов тесно связано с изучением квазигрупп), теории кодов, статистикеи многих других областях [2].Исследование выполнено при поддержке РФФИ (проекты 10-01-00424, 11-01-00997) и ФЦП«Научные и научно-педагогические кадры инновационной России» на 2009-2013 г. (гос. контракт02.740.11.0429).Впервые в криптографии латинский квадрат был применён в шифре И. Трите-мия [3]. Значение латинских квадратов для криптографии иллюстрирует теоремаШеннона, в соответствии с которой единственными совершенными шифрами являютсяшифры гаммирования, наложение гаммы в которых определяется латинским квадра-том [4]. Попытка обобщить подход Шеннона и ввести понятие «сильно совершенныйшифр» предпринята в [5].Краткий обзор результатов по применению латинских квадратов для построениясхем аутентификации, шифрования и однонаправленных функций содержится в [6].В ряду примеров применения латинских квадратов для построения поточных шиф-ров необходимо выделить предложенный в 2005 г. шифр Edon80 [7], который дошёл дотретьего тура конкурса ESTREAM. Разработчики шифра из 576 существующих латин-ских квадратов 4-го порядка тщательно выбрали 4, на основе которых в криптосхеместроится конвейер из 80 латинских квадратов, он используется для выработки гаммы.При разработке блочного шифра IDEA [8] авторы использовали три квазигруппы,соответствующие операциям сложения по модулю 2, сложения по модулю 216 и умно-жения по модулю 216 + 1. При этом высокие криптографические свойства шифра ониобосновали существованием единственной изотопии между двумя из используемыхквазигрупп.Латинские квадраты являются привлекательным средством для построения схемразделения секрета. Секретом является латинский квадрат, а все участники схемыполучают его частично заполненным (он называется частичным). Задача распозна-вания того, может ли частичный квадрат быть однозначно дополнен до латинского,NP-полна. Наряду с большим количеством латинских квадратов это обстоятельствои определяет стойкость схемы [9]. Предложенная схема может быть усовершенство-вана [10]. В свою очередь, на основе таких схем разделения секрета можно строить икриптографические хеш-функции [11]. Другой пример построения криптографическойхеш-функции на основе случайного латинского квадрата приведён в [12].Разработанное в 2008 г. для участия в конкурсе SHA-3 на новый американскийстандарт хеш-функции семейство Edon-R [13] не прошло во второй тур, но интереснотем, что в основе конструкции лежит построение и использование некоммутативнойнеассоциативной нелинейной квазигруппы.В [14] предложен протокол с нулевым разглашением. Каждый участник имеет от-крытый ключ, которым являются два эквивалентных латинских квадрата. Секретнымключом является изотопия между ними.В заключение отметим, что о растущем внимании к теме свидетельствует появле-ние обзоров [6, 15].

Скачать электронную версию публикации