В современной алгебраической криптографии используется самые различные вычислительно сложные задачи, которые возникают в теории труп, колец и других алгебраических систем. Одной из предположительно сложных задач является задача об извлечение корней в некоторых некомутативных кольцах, например, в кольце кватернионов, коэффициенты которых берутся из кольца вычетов по модулю N.
В работе Сато-Араки [3] была описана некаторая цифровая подпись, криптостойкость которой основана на сложности этой задачи. Однако в статье Копперсмита[2] были указаны две атаки, которые делают подпись Сато-Араки не надежной.
В 2014 году опубликована статья Ванга и Ху [4], в которой приводится модифицированный вариант подписи, который, как утверждают авторы, не позволяет произвести атаки Копперсмита.
В нашей работе сделано следующее. Во-первых, описан протокол подписи, несколько более общий, чем в статье Ванга и Ху [4], который пригоден для широкого класса колец, в частности, для алгебр Клиффорда. Во-вторых, изложен общий метод, позволяющий сделать эту цифровую подпись надежной в течении любого достаточно продолжительного времени (при некоторых естественных допущениях). В третьих, дан обзор состояния задачи об извлечении корней в ряде алгебр Клиффорда и близких по строении колец. Обнаружилось, что если не считать случая кольца Гамильтоновых кватернионов над полем действительных чисел, и некоторых других алгебр, также над полем действительных чисел, об извлечении корней в дискретном случае в алгебрах Клиффорда известно очень мало. Можно предположить, что эта задача является в данный момент вычислительно сложной (то есть эффективных алгоритмов сейчас не существует). Ввиду этого можно сделать вывод, что предлагаемая нами подпись, дополнена упомянутым выше алгоритмом повышения криптостойкости, будет достаточно надежной.
Опишем вкратце содержание работы. В главе 1 изложены результаты работ Сато- Араки, Копперсмита, Ванга и Ху [3],[2],[4]. В главе 2 сначала описано обобщение подписи Ванга и Ху на случай произвольного кольца. Затем описан метод повышения криптостойкости, который мы называем маскировкой исходного кольца. В главе 3 описаны некоторые алгебры: обобщенные кватернионы, силит-кватернионы, биква-тернионы и изложены имеющиеся на данный момент сведения об извлечении корней в этих алгебрах. Случай алгебр кватернинов над кольцами действительных чисел мы не рассматриваем, так как, во-первых, он хорошо известен [11], а во-вторых, он не может быть применен в криптографии, где требуется только дискретные величины. Результаты работы были доложена на студенческой научной конференции КФУ 15 апреля 2016 года.
