ЛАТИНСКИЕ КВАДРАТЫ И ИХ ПРИМЕНЕНИЕ В КРИПТОГРАФИИ

Самым первым упоминанием о латинских квадратах можно считать «Шамс аль Маариф» -  текст от 1200 года, написанный Ахмадом Аль-Буни.

Название «латинские» - квадраты получили благодаря математику Леонарду Эйлеру, который использовал для их записи символы латинского алфавита. Сейчас для этого чаще используют какой-либо набор натуральных чисел, но название уже прижилось.

Жак Озанам в 1725 году в своем сборнике задач более подробно описал латинские квадраты, а также впервые показал латинский квадрат не как отдельный объект, а в отношении с другим латинским квадратом, точнее с ортогональным ему. Его известная задача на эту тему звучит так:

Имеется 16 игральных карт. Тузы, короли, дамы и валеты всех 4-х мастей. Их надо разместить в виде квадрата так, чтобы в каждых строке и столбце карты всех достоинств и мастей встречались только один раз.

Задача в общем случае имеет 6912 вариантов решения. Однако, если ввести тоже условие для диагоналей квадрата, то количество решений сократится в шесть раз.

Отметим, что многие подходы и методы изучения латинских квадратов дошли до нас из работ Эйлера. Также существенный вклад внести труды Артура Кэли, в которых он привел формулу для количества латинских прямоугольников из двух строк. Похожую формулу, но для латинских прямоугольников из трех строк вывели лишь в 1953 году.

Латинским прямоугольником называется матрица m × n, в которой символы из некоторого набора M или натуральные числа от 1 до n в каждой строке образуют перестановку, а в каждом столбце все элементы разные.

Очевидно, что при m = n, латинский прямоугольник становится квадратом, при этом n называют его порядком.

Рисунок 1. Латинский прямоугольник(слева), латинский квадрат(справа)

Далее будем рассматривать только латинские квадраты, потому что именно они используются при кодировании информации.

Пара таких квадратов может быть изотопной, если один из этой пары можно получить из другого путем композиции из перестановок строк и столбцов и замены элементов множества M элементами из симметрической группы S_n.

Это отношение можно также охарактеризовать как эквивалентное, поэтому все множество латинских квадратов делится на отдельные изотопные классы, которые не пересекаются. Количество изотопных(эквивалентных) латинских квадратов, которые можно получить из одного равно (n!)³ .

Два латинских квадрата могут быть ортогональными. Это означает, что для квадратов L и K , все их упорядоченные пары (l_ij,k_ij) отличны друг от друга.

Рисунок 2. Ортогональные латинские квадраты

Такие квадраты подробно изучал Эйлер, который доказал их существование для всех порядков, отличных от 2 и 6. У него не получилось найти их для порядка 6, а также 10, и в связи с этим он предположил, что не существует пар ортогональных квадратов для n = 4r + 2. Эта гипотеза подтвердилась для n = 6, но в общем случае она оказалась неверна. Это было доказано с помощью ЭВМ в 60-х годах XX века путем нахождения ортогональной пары латинских квадратов для n = 22 и 10.

В этом разделе также стоит упомянуть о частичных латинских квадратах. Это такой квадрат, в котором каждый элемент множества M в каждой строке и в каждом столбце попадается только один раз.

У частичного квадрата существует свое критическое множество. Удаление какого-либо элемента из этого множества приведет к тому, что однозначно восстановить исходный квадрат становится невозможным.

Известна мощность этого множества для небольших порядков. Для n = 1 это 0, для 2—1, 3—3, 4—7, 5—11, 6—18.

Впервые латинскими квадратами для кодирования воспользовались в шифре Тритемия. Это относительно простой метод шифрования, основанный на замещении информационного символа на бессмысленный, если не знать алгоритм расшифровки. Является усовершенствованным шифром Цезаря. Для этого шифра была построена таблица (соответствующая таблице Кэли группы (Z₂₆, +)) Эта таблица использовалась для полиалфавитного шифрования. То есть первая буква открытого текста шифруется первым алфавитом (первой строкой таблицы), вторая — вторым и т. д.

Спустя время, Дж. Белазо добавил в шифр пароль, тем самым усовершенствовав его. Также это позволило, при совмещении с Л. Б. Альберти, который задействовал произвольный алфавит, создать новый эффективный шифр, который оказал серьезное влияние на дальнейшее развитие криптографии.

1 Протокол с нулевым разглашением секрета

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

Имеет несколько типовых шагов:

1. Фиксатор генерируется в виде разового отрытого ключа для пользователей, доказывающих свою подлинность;

2. Для проверяющего случайным образом генерируется запрос;

3. Ответ на запрос вычисляется по специальному алгоритму.

Этот протокол можно преобразовать в схему электронно цифровой подписи, что еще раз доказывает его стойкость.

В данном шифре используются свойства изотопных латинских квадратов. Для каждого участника а есть открытый ключ. Как раз в качестве ключа и используется пара изотопных латинских квадрата L_a и L^!_a. Отношение изотопии между ними и сеть секретный ключ. Для аутентификации пользователь, который подтверждает свою подлинность многократно, случайным образом вырабатывает из L_a изотопный ему латинский квадрат H и затем направляет его на проверку и доказывает ему, что H изотопен L_a или H изотопен L^!_a . А так как секретным ключом является изотопия L_a и L^!_a, то при успешном доказательстве изотопии H и L_a или H и L^!_a, будет подтверждена подлинность

2. Схема разделения секрета.

Ключ такой схемы - это латинский квадрат L порядка n. Сам квадрат держится в секрете, открыт только его порядок.

В этой схеме применяются свойства частичных латинских квадратов. Происходит это путем объединения всех критических множеств

L: S= {A_i | A_i критические множества L}. Число критических множеств связано с порядком квадрата, а в этой схеме еще и с количеством участников.

Типовые шаги:

1. Задается латинский квадрат L;
2. Порядок n разглашается, но сам квадрат нет и используется в качестве ключа;
3. Задается множество S, в которое объединяются критические множества L;
4. Каждому участнику выделяется доля (частичный квадрат);
5. Восстановление исходного квадрата L возможно при сборе всех участников и объединении их частей.

Заключение

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

У этого протокола есть три основных преимущества, которые делают его более эффективным в сравнении с другими:

1. Полнота. Если доказывающий знает утверждение, то он сможет убедить в этом проверяющего.

2. Корректность. Если доказывающий не знает утверждение, то он может обмануть проверяющего только с пренебрежимо малой вероятности.

3. Нулевое разглашение. Проверяющий, даже если он ведет себя нечестно, не узнает ничего кроме самого факта, что утверждение известно доказывающему.

Схема разделения секрета в свою очередь является эффективным средством для сокрытия ценной информации. В данной схеме применение латинских квадратов также обосновано, но это применение не дает существенных преимуществ.

В итоге можно сказать, что использование латинских квадратов в криптографии полезно и эффективно и развитие этого направления может привести к значительным успехам в области защиты информации. Ведь как гласит теорема Шеннона: «Совершенными шифрами являются шифры гаммирования, в которых наложение гаммы определяется латинским квадратом».

Список литературы:

1. Википедия [Электронный ресурс]: латинский квадрат — режим доступа: https://ru.wikipedia.org/wiki/Латинский_квадрат (дата обращения 31.03.2020)
2. Молдовян А.А., Молдовян Д.Н., Левина А.Б. Протоколы аутентификации с нулевым разглашением секрета: учеб. пособие для вузов – СПб: Университет ИТМО, 2016 — С.13-23.
3. Википедия[Электронный ресурс]: разделение секрета — режим доступа: https://ru.wikipedia.org/wiki/Разделение_секрета (дата обращения 7.04.2020)
4. Тужилин М.Э. Латинские квадраты и их применение в криптографии: аналит. обзор, 2012, Рос. гос. гум. ун-т — Москва, 2012 - С.50-51.