Криптосистемы, основанные на группах кос

Теория кос появилась в 20-х годах прошлого века. Её основы были заложены немецким математиком Эмилем Артином, но корни этого естественного понятия встречались в работах А. Гурвица (1891 г.), Р. Фрике и Ф. Клейна (1897 г.), и даже в записных книжках К. Ф. Гаусса. Первоначально косы были предложены Артином в качестве математической модели для текстильной промышленности, но приложения этой теории оказались весьма разнообразными, теперь они занимают важное место в комплексном анализе, комбинаторике, квантовой механике и квантовой теории поля.

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

• протокол Аншеля-Аншеля-Гольдфельда;

• протокол обмена ключами К. Н. Ко, аналогичный алгоритму Диффи-Хеллмана;

• схема подписи на сопряжении, схема слепой подписи Verma и др.

Представленные протоколы позволяют решить следующие задачи информационной безопасности:

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

Алгебраические основы группы кос

Представим перестановку из элементов n-множества в виде непрерывного процесса отображения семейства точек с координатами (0,0,1), (1,0,1), …, (n,0,1) в семейство точек с координатами (0,0,0), (1,0,0), …, (n,0,0) на плоскости XYZ. Пусть траектории движения точек не пересекаются между собой и направлены строго вниз. Отсюда имеем, что траектории задаются линиями, строго идущими вниз и соединяющими точки из первого семейсва с точками из второго семейства.

Отобразив линии на плоскость X0Z (рисунок 1), получим пересечения траекторий отображения точек. В точках пересечения линия выше другой та, у которой координата y больше. В результате, имеем объект, определяемый как плоская диаграмма косы (рисунок 1). Траектории отображения точек принято называть нитями. Точки на плоскости, в которых проекции нитей косы пересекаются, называются перекрестками. Отсюда сформулируем определение Косы.

Коса — это математический объект, который состоит из двух параллельных плоскостей в трехмерном пространстве , упорядоченных семейств точек и и из n — простых ломаных , которые не пересекаются между собой и соединяют плоскости таким образом, что между точками и существует биекция. Пример представлен на рисунке 2.

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

Косы, из фиксированного числа нитей, рассматриваемые с точностью до изотопии, обладают естественной структурой группы. Пусть есть две косы А и В, тогда операция умножения кос определяется как вертикальное сжимание и расположение одна над одной (рисунок 4).

Нейтральным элементом в группе КОС является коса с вертикально расположенными нитями (рисунок 5). Обратный элемент в группе КОС задаётся вертикальным отображением (рисунок 6).

Обе операции (умножения и взятие обратного) инвариантны относительно изотопии, т.е. если коса изотопна косе , а коса — косе , то произведение кос изотопно произведению кос , а обратная коса — обратной косе .

Результатом такого построения, при любом натуральном n, является группа изотопических классов кос, обозначим ее через .

Для построения образующих группы кос возьмем такие косы, которые переставляют два соседних элемента i, i+1, где i — натуральное число от 1 до n-1. В этом случае существует два способа перестановки нитей: ­

• если нить i на плоской диаграмме лежит выше, то такая перестановка обозначается ;

• если нить i+1 на плоской диаграмме лежит выше, то такая перестановка обозначается .

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

• где |i-j| ≥ 2.

Рассмотрим случай, когда имеются три точки попарных пересечений трех различных нитей косы, но при этом одна нить проходит под (над) двумя другими. В таком случае нить можно протянуть под двумя другими (рисунок 8):

• где 1 ≤ i ≤ n-2.

Такое движение называют третьим движением Рейдемейстера, которое представлено на рисунке 8.

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

Такое движение называется вторым движением Рейдемейстера (рисунок 9).

Первое движение Рейдемейстера в теории изотопии кос не встречается. Сформулируем следующую теорему. Теорема 1 (Артин). Две косы A и B, представленные в виде композиции образующих элементов, являются изотопными тогда и только тогда, когда коса A отображается в косу B посредством последовательного применения преобразований кос.

Определим как подгруппу группы , образованную . Группу определим как подгруппу группы , образованную , где . Тогда любая коса из коммутативна любой косе из .

Задача поиска сопряженного элемента

Пусть косы и , тогда задача состоит в том, что бы при известных найти неизвестную косу s. Эта задача была решена Ф.А. Гарсидом в 1969 г. Е.А. Элрифай и Г.Р. Мортон представили алгоритм, вычисляющий секретную косу за (n!), где n — количество нитей в косе.

Проблема одновременного поиска множества сопряжений

Пусть такие, что где , или одной из подгрупп . Задача – найти такое что .

При этом проблема поиска сопряжений является частным случаем проблемы одновременного поиска множества сопряжений. Решение проблемы аналогично предыдущей проблеме и имеет сложность порядка (n!), где n — длина косы.

Представление Крамера-Бигелоу

Пусть n — натуральное число, а R — коммутативное кольцо с единицей над R, порожденное элементами q,t ∈ R. Пусть V — линейное пространство над кольцом R размерности порожденное некоторыми элементами

Определим действие группы на пространстве V по следующему правилу:

, где — образующие группы кос, .

Точность этого представления доказана в оригинальной работе Крамера.

Таким образом каждой косе из ставиться в соответствие квадратная матрица размерности n.

Множество сопряженных элементов

Обозначим через SSS(x) – конечный набор сопряжений косы x минимально возможной запутанности. В свою очередь назовем SSS супер высшим множеством. Для каждой такой косы x множество SSS(x) – конечно и алгоритмически вычислимо. Важно заметить, что две косы a и b сопряжены тогда и только тогда, когда a и b принадлежат одному и тому же SSS. Пусть maxinf(x) – максимальный элемент из множества всех inf(x), а minsup(x) – минимальный элемент из множества всех sup(x). Определим множество SSS(x) следующим образом:

Для простоты представления определим множество SSS(x) через ориентированный граф, где из вершины x исходит дуга в вершину y в том случае, когда . Обозначим через S(x, d) – ограничение x на множестве SSS(x):

В дальнейшем под открытым ключом будем понимать пару , где . Важно заметить, что пара отвечает требованиям задачи сопряженнсти. Так как важна именно практическая реализация , введем понятие . – генератор супер высшего множества. Пусть – конечная подгруппа группы кос. Тогда справедливо следующее выражение:

В свою очередь, генератор реализует пару , где и .

Применение групп кос для решения криптографических задач

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

• Обеспечение конфиденциальности информации, т.е. защита от несанкционированного ознакомления с содержанием;
• Обеспечение целостности информации, т.е. защита от несанционированного изменения его нарушителем;
• аутентификация информации, т.е. подтверждение подлинности партнерских сторон, содеражания сообщения, времени генерации сообщения и т.д.;
• удостоверение авторства по отношению к сообщению или документу (обеспечение невозможности отказа от авторства или присвоения его)

Криптосистемы, основанные на группах кос

Основные типы криптосистем построенных на группе кос:

• протоколы обмена ключей;
• системы шифрования;­­
• системы аутентификации;­
• системы электронной подписи.

Устройство ключевой системы является одним и определяющих факторов для криптографической стойкости шифрсистемы. При этом важны оба компонента ключевой системы:

• строение ключевого множества шифра;
• процедуры и протоколы, управляющие всеми этапами жизненного цикла ключей.

Криптография на группе КОС позволяет реализовать два протокола обмена ключами: ­

• Аншеля-Аншеля-Гольдфельда;
• Аналогичный Диффи-Хеллману.

Согласно протоколу распределения ключей DHM (Диффи-Хеллмана-Меркля) необходимо в первую очередь определить некую конечную группу G и элемент g из этой группы. Генерация ключа реализуется посредством выбора соответствующих кос из группы . Необходимо учесть, что каждый из абонентов может рассматривать не отдельные косы, а некоторые композиции кос из заданной группы, что усложняет криптоанализ системы обмена ключами, но, в свою очередь, увеличивает время выработки ключа.

Сообщение, к которому применяется криптографическая функция шифра, называют открытым текстом, а само применение функции шифра к открытому тексту называется шифрованием или зашифрованием. Результат шифрования открытого текста называется шифрованным текстом или криптограммой. Метод шифрования так же базируется на определении “открытой” и “секретной” косы. Персональные косы каждого абонента выбираются из подгрупп и . Шифрование реализуется с помощь однонаправленной хеш – функции , не имеющей коллизии, то есть, если — хеш-функция, то значение не совпадает со значением при условии, что и – элементы группы кос. Шифртекстом является результат операции ”XOR”-суммирования исходного текста и результатом хэш – функции. Сопряжение получаем с помощью “секретной” косы.

Аутентификация — процедура проверки подлинности субъекта, проводимая, как правило, с помощью криптографических преобразований, позволяющая достоверно убедиться в том, что субъект, предъявивший свой идентификатор, на самом деле является именно тем субъектом, идентификатор которого он использует. Криптография на группе КОС позволяет реализовать систему аутентификации с протоколами, основанными на протоколе Фейга-Фиата-Шамира и аналоге протокола Дифи–Хеллмана. Для злоумышленника — процесс перехвата информации заключается в задаче декомпозиции кос, то есть нахождении такой пары a и b из группы кос такой, чтобы y=a*x*b, где x и y — элементы из группы кос.

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

• Группы Bn при любом n являются конечно определенными, то есть порождаются конечными множествами образующих элементов, все соотношения между которыми следуют из конечного множества определяющих соотношений;
• Группы Bn обладают нормальными формами однозначной записи элементов, переход к которым от записей в виде групповых слов эффективен.

Примеры Криптосистем

Среди протоколов обмена ключами выделим два основных — это протокол Аншеля-Аншеля-Гольдфельда и протокол, аналогичный протоколу Диффи-Хеллмана.

В протоколе Аншеля-Аншеля-Гольдфельда в качестве открытого ключа принимается два набора кос где для и . Секретный ключ u, принадлежащий участнику обмена А, состоит из l нитей. Аналогично секретный ключ v, принадлежащий участнику обмена B, состоит из m нитей. Обмен происходит следующим образом :

Такая последовательность действий требует 2m+2l+2 операций умножения и m+l операций нахождения обратных кос. Протокол основывается на проблеме одновременного поиска множества сопряжений.

Демонстрационная программа протокола Аншеля-Аншеля-Гольдфельда на группе кос (C#, NetFramework 4.5):

Протокол, который предложен К.Н. Ко, базируется на протоколе Диффи-Хеллмана. Здесь, открытый ключ р это определённая коса в группе Bn. Секретный ключ, принадлежащий А, представляет собой косу s из подгруппы LBn, а секретный ключ В — косу r из подгруппы RBn. Обмен ключами происходит следующим образом:

Такой протокол требует 8 операций умножения кос и 2 операции нахождения обратной косы. Протокол основывается на проблеме сопряжения кос.

Демонстрационная программа алгоритма Диффи-Хеллмана на группе кос(C#, NetFramework 4.5):

Для шифрования и расшифрования используется хэш-функция . В криптосистеме, основанной на группе кос, используется свойство коммутативности кос построенных в и в .

Генерация ключа

Участник А выбирает достаточно сложную косу . Далее он выбирает косу . Открытым ключом является пара (x, y), где . Секретным ключом является a. А отправляет открытый ключ (x, y) участнику В.

В необходимо отправить сообщение участнику А, зашифровав его с помощью ключа (x, y). Тогда В произвольно выбирает косу . Шифротекстом является пара (c, d), где и Далее В отправляет шифротекст (c, d) участнику А.

Расшифрование

А расшифровывает сообщение (c, d), используя личный ключ a. Для этого он вычисляет . Корректность алгоритма зашифрования и расшифрования доказывается через коммутативность кос a и b:

Такая схема шифрования требует 8 операций умножения кос, 2 операции нахождения обратной косы и 2 применения хэш-функции. Представленная схема основывается на проблеме сопряженности кос.

В этой системе открытый ключ — это пара сопряжённых кос , причём , принадлежащих группе , коса является секретным ключом А. В отличие от предыдущих систем и и принадлежат группе , т.е мы не можем предположить, что принадлежит какой-нибудь из подгрупп или же . Однако по прежнему предположим, что — это односторонняя хэш-функция: . Процедура аутентификации заключается в повторении k раз следующих трёх шагов:

Такой протокол требует 2+4k операций умножения кос, 2k операций нахождения обратных кос и 2k применений хэш-функции. Протокол основывается на проблеме сопряжения кос. Однако недостатком этого протокола является то, что пользователь A вынужден каждый раз выбирать случайную косу. Такой протокол не подходит для частой аутентификации в системе, в которой каждому пользователю присваивается постоянный уникальный идентификатор и пароль. При такой аутентификации пользователь B никак не подтверждает себя, следовательно, если в роли B выступит другой пользователь, A не заметит подмены. Злоумышленник, перехватив все данные, отправляемые пользователями A и B, может применить атаку типа «Маскарад», выдавая себя за пользователя A.

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

Алгоритм подписи представлен на рисунке 14.

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

Демонстрационная программа алгоритма простой электронной подписи на группе кос(C#, NetFramework 4.5):

Такая схема электронной подписи требует 10 операций умножения кос, 3 операции нахождения обратной косы и 2 применения хэш-функции. Высокий уровень секретности достигается группой кос с нитями количества не более 28, в противном случае задача генерации группы SSS(x) является трудоемкой. Качество подписи также повышает индивидульный подбор запутаных кос. Достаточным условием хорошей подписи является отсутствие циклов в графе сопряжения элементов из SSS. Схема подписи основывается на проблеме сопряженности кос.

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

• A выбирает секретную косу , секретный ключ отправителя. Считает косу и получает ;
• A отправляет косу t пользователю B;
• B считает , используя свою секретную косу и отправляет ее A;
• A считает , подписывает сообщение m сгенерированной подписью x.

Подпись действительна, если .

Доказательство: , так как и перестановочны.

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

Генерация доверенного ключа

Соглашение доверенного ключа:

• Исходный подписчик Алиса выбирает косу .
• Алиса вычисляет . Затем, она посылает пару Бобу через защищенный канал.
• Боб проверяет, является ли .

Если это выполняется, он принимает ключ, в противном случае отклоняет.

Генерация доверенной слепой подписи

Когда доверенный подписчик Боб подписывает документ от имени исходного подписчика Алисы. Алгоритм подписи:

• Доверенный подписчик выбирает и вычисляет и посылает для пользователя.
• Скрытие. Пользователь выбирает и вычисляет , и посылает h к доверенному подписчику. Доверенный подписчик вычисляет и посылает пользователю.
• Раскрытие. Пользователь вычисляет и показывает в качестве доверенной слепой подписи сообщения m.

Генерация доверенной слепой подписи (рисунок 16)

Такая схема электронной подписи требует 16 операций умножений кос, 3 операции нахождения обратной косы и 4 применения хэш-функции. Схема электронной подписи вслепую основывается на проблеме нахождения сопряженных кос.

Преимущества и недостатки криптографических преобразований на группах кос

В сравнении с общеизвестным RSA1024, криптографические преобразования на группе кос имеют ряд преимуществ и недостатков. При более высокой вычислительной сложности атаки время зашифрования на группе кос больше, но время расшифрования — меньше. При этом генерация ключа происходит в 168 раз быстрее. Суммарное время зашифрования/расшифрования сообщений c использование криптосистемы на группе кос меньше, чем при использовании RSA (таблица 1).

Глоссарий

Библиографический указатель

Перейти к списку литературы раздела «Криптосистемы, основанные на группах кос (Braid Groups)».