О вычислительной сложности алгоритмов факторизации и дискретного логарифмирования Черепнев Михаил Алексеевич

Содержание к диссертации

Введение

1 Показательные сравнения 41

1.1 О подъёме решений показательных сравнений 41

1.2 Сравнительная стойкость протокола Диффи Хеллмэна и задачи дискретного логарифмирования 46

1.3 О полиномиальной эквивалентности задач дискретного логарифмирования и Диффи-Хеллмэна на некоторых стандартных кривых 56

2 Некоторые свойства распределения простых чисел 60

3 Использование некоммутативной операции для построения систем защиты информации 71

4 Задача Бризолиса 91

5 Гиперэллиптические кривые 101

5.1 Арифметика дивизоров 101

5.1.1 Алгоритмы сложения и приведения дивизоров 102

5.1.2 Алгоритмы приведения матриц 113

5.2 Ядро спуска Вейля 122

5.2.1 Исследование группового гомоморфизма метода спуска Вейля 122

6 Решение разреженных систем линейных уравнений над GF(2) 132

6.1 Замечания о симметрических матрицах 134

6.2 Блочные алгоритмы 139

6.2.1 Новый алгоритм типа Ланцоша-Паде (первая версия) 139

Вероятностный анализ 165

6.2.2 Распараллеленные версии блочных алгоритмов с распределёнными операциями 170

6.2.3 Итоговые оценки и тесты 185

6.2.4 Дальнейшие исследования 187

Новый алгоритм типа Видемана-Копперсмита 187

Связь между приближениями рядов по положительным и отрицательным степеням формальной переменной 192

7 Решение разреженных систем линейных уравнений над GF(p) 209

7.1 A -ортогональный базис пространства Крылова и метод Ланцоша 210

7.2 A -ортогональный базис пространства Крылова и матричные приближения Паде 213

7.3 Рекуррентные формулы для приближений Паде 216

7.4 Блочный метод Ланцоша-Паде 219

7.5 Универсальный блочный метод Ланцоша-Паде 229

IV Заключение

• Сравнительная стойкость протокола Диффи Хеллмэна и задачи дискретного логарифмирования
• О полиномиальной эквивалентности задач дискретного логарифмирования и Диффи-Хеллмэна на некоторых стандартных кривых
• Алгоритмы сложения и приведения дивизоров
• Рекуррентные формулы для приближений Паде

Введение к работе

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

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

Предмет исследования - теоретико-числовые алгоритмы факторизации, дискретного логарифмирования и решения больших разреженных систем над конечным полем, а также смежные алгоритмические вопросы.

Цель работы - Оптимизация и адаптация рассматриваемых теоретико-числовых алгоритмов под современные программно-аппаратные средства. Получение теоретических и практических оценок вычислительной сложности этих алгоритмов. Выявление зависимости вычислительной сложности рассматриваемых алгоритмов от способа задания и параметров входных данных.

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

Научная новизна работы состоит в строго доказанных новых теоремах и корректных теоретико-числовых алгоритмах с доказанными оценками на время работы, объём требуемой памяти, объём передачи данных и эффективность использования параллельных вычислений.

Построен новый алгоритм решения задачи дискретного логарифмирования с оракулом Диффи-Хеллмэна. Как результат применения этого алгоритма получено новое выражение сложности задачи дискретного логарифмирования через сложность задачи Диффи-Хеллмэна. Как следствие построенного алгоритма доказана полиномиальная эквивалентность задачи дискретного логарифмирования и задачи Диффи-Хеллмэна для некоторых кривых, удовлетворяющих действующему стандарту цифровой подписи ГОСТ Р 34.10-2012. Построен алгоритм, сводящий вскрытие схемы Диффи-Хеллмэна к решению системы полиномиальных уравнений с оценками на её степень.

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

снизу на число первообразных корней, удовлетворяющих условию Бризолиса, которые приводят к оценке числа таких точек снизу.

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

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

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

1. Доказана полиномиальная эквивалентность задач дискретного логарифмирования и
Диффи-Хеллмэна в случае ограниченной длины ветвей дерева Пратта (в частности для
некоторых кривых ГОСТ Р 34.10-2012). Кроме того, представленное доказательство даёт
алгоритм решения задачи дискретного логарифмирования из алгоритма решения задачи
Диффи-Хеллмэна в группах, образованных некоторыми подмножествами исходной группы с
некоторыми специальными операциями, связанными с оракулом Диффи-Хеллмэна.

2. Получены новые оценки на величину и количество простых делителей чисел вида p — 1.

1. Задача универсальной подделки цифровой подписи ГОСТ Р 34.10-1994 сведена к нахождению неподвижных точек функции дискретного логарифма. Тем самым доказано, что указаный ГОСТ без проверки длины подписи является нестойким. Получены аналитические формулы для указанных неподвижных точек, а также получена оценка на их число снизу.

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

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

Достоверность и обоснованность результатов обеспечиваются строгими математическими доказательствами теоретических результатов и подтверждаются компьютерными программами, результатами и замерами времени их работы и объёма используемой памяти. Все результаты, приведённые в основной части диссертации (1-7 глава), являются новыми, снабжены разъяснениями используемых понятий и определений. Результатами диссертации, выносимыми на защиту, являются:

1. В общем случае получена оценка сверху на сложность задачи дискретного логарифмирования через сложность задачи Диффи-Хеллмэна. Данная оценка в ряде случаев приводит к полиномиальной эквивалентности этих задач. Полученная оценка обобщает результаты работы Боера 1988 года и работы Маурера 1994 года на общий случай. Эта теорема вошла в обзор Маурера и Вулфа 2001 года ” Diffie-Hellman Protocol” в качестве одного из итоговых результатов. Впервые рассмотрена функция максимальной длины дерева Пратта s{m) числа m. Это дерево введено в рассмотрение в 1975 году Праттом, который предложил его для

использования в алгоритме проверки простоты. В 1997 году Шуф показал, что алгоритм общего применения (generic algorithm), решающий задачу Диффи-Хеллмэна, не может быть ”простым” (имеет экспоненциальную сложность для групп простого порядка). Однако, доказанная теорема об оценке применима не только к алгоритмам общего применения, но и к алгоритмам, работающим с элементами фиксированной группы, связанными несколькими специальными групповыми операциями.

Функция s{m) была в 2008 году исследована Фордом, Конягиным и Люка, которые получили для неё нетривиальные оценки. Полученная ими оценка сверху отличается от тривиальной несколько лучшей константой в показателе. Поэтому её применение совместно с рассматриваемой оценкой не даёт новой информации о связи сложностей задач дискретного логарифмирования и Диффи-Хеллмэна. В этой же работе была высказана гипотеза об асимптотическом поведении функции s{m) как О (In In т) для почти всех т. Применение этой оценки уже приводит к нетривиальным результатам. А именно, в случае полиномиальности решения задачи Диффи-Хеллмэна получается алгоритм решения задачи дискретного логарифмирования, работающий "почти” полиномиально (лучше субэкспоненты).

Изложенный метод, применён к оценке сложности задачи дискретного логарифмирования на группе точек эллиптической кривой простого порядка р, где р — 1 раскладывается на маленькие взаимнопростые множители. Такой случай возможен для кривых, удовлетворяющих ГОСТ Р 34.10-2012. Показано, что в этом случае задачи дискретного логарифмирования и Диффи-Хеллмэна полиномиально эквивалентны. Кроме того, построен конструктивный полиномиальный алгоритм вычисления дискретного логарифма при помощи оракула Диффи-Хеллмэна.

2. Доказаны теоремы о величине и числе простых делителей чисел вида р—1, где р - простое число. Эти теоремы предоставляют информацию о структуре одного шага дерева Пратта, которую можно использовать и при построении алгоритма дискретного логарифмирования с оракулом Диффи-Хеллмэна. Получена новая оценка снизу функции Эйлера для почти всех аргументов.

3. Проведён анализ некоторых известных некоммутативных групп на стойкость построенной на их основе схемы открытого распределения ключа, предложенной В.М.Сидельниковым [1]. Доказано, что задача разложения на множители в них является полиномиальной, а схема В.М.Сидельникова с их использованием — нестойкая. Предложен пример некоммутативной мультипликативной операции с несколько большей сложностью задачи разложения на множители.

4. Показано, что задача универсальной подделки ГОСТ Р 34.10-1994 [26] сводится к нахождению неподвижных точек в задаче дискретного логарифмирования. Построены аналитические формулы для вычисления пар (x,R), удовлетворяющих сравнению

x = R^x( mod p),x,R Є Z,(R,p) = I, отличные от общеизвестных: (д,д⁹ ^ modp-i)^ _Гд_Є д _ первообразный корень, удовлетворяющий условию (д,р — 1) = 1 (условие Бризолиса). В этих формулах R уже необязательно первообразный корень. Доказана теорема о существовании решения с R, имеющим достаточно большой простой порядок. Получены оценки на число первообразных корней, удовлетворяющих условию Бризолиса.

5. Проведён анализ метода спуска Вейля при решении задачи дискретного
логарифмирования на эллиптических кривых над полем характеристики 2. Основным

инструментом в этом исследовании выбрано представление Мамфорда приведённых дивизоров парой многочленов. Данное представление можно корректно связать с классами дивизоров (по модулю дивизоров рациональных функций).

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

6. Проанализирована сложность линейного этапа алгоритма факторизации целых чисел. Предложен новый алгоритм решения разреженных систем линейных уравнений над GF(2), которые возникают при решении этой задачи алгоритмами с факторной базой. Доказано, что параллельная реализация построенного алгоритма работает быстрее алгоритма Видемана-Копперсмита 1993г., который был применён при постановке последнего рекорда факторизации чисел RSA в декабре 2009 г. Предложенная техника не только сохраняет возможность частичного распараллеливания высокого уровня при решении таких систем (то есть часть алгоритма может быть реализована на не связанных друг с другом кластерах), но позволяет вообще исключить использование кластеров большой мощности. Другими словами, эта техника позволяет распараллелить весь алгоритм на связанные медленным каналом (Internet) вычислители, единственное требование к которым - это возможность содержать в оперативной памяти рассматриваемую задачу (матрицу линейной системы). Помимо уменьшения времени на решение линейной системы, предложенный алгоритм не требует кратного увеличения оперативной памяти сверх объёма, необходимого для хранения указанной матрицы, как это было при постановке рекорда целой факторизации в декабре 2009 года при помощи алгоритма Видемана-Копперсмита. Таким образом, предложенный алгоритм превосходит алгоритм Видемана-Копперсмита по всем основным параметрам. Преимуществом по сравнению с алгоритмом Монтгомери 1994г. является более высокая точка насыщения, что позволяет решать значительно большие системы на многопроцессорной вычислительной технике. Таким образом, предложенный алгоритм оказывается на сегодняшний день наилучшим для использования на многопроцессорной технике с несколькими сотнями независимых вычислительных узлов.

7. Построен новый алгоритм решения разреженных систем линейных уравнений над GF(p), которые возникают при решении задачи дискретного логарифмирования алгоритмами с факторной базой. Этот алгоритм обладает теми же преимуществами, что и, описанный выше, алгоритм для поля GF{2).

Структура диссертации. Диссертация состоит из введения, 7 глав, списка литературы и приложения. В приложении изложены сведения, необходимые для понимания основного текста диссертации, а также текст и результаты работы компьютерной программы, реализующей предлагаемый алгоритм решения больших разреженных линейных систем. Общий объём диссертации 294 страницы.

Сравнительная стойкость протокола Диффи Хеллмэна и задачи дискретного логарифмирования

Теорема останется верной, если В = Р(р), где Р(-) - некоторый полином, \р\ - длина записи числа р. Связь между сложностями задач дискретного логарифмирования и Диффи-Хеллмэна может быть установлена в общем случае. Введём следующие обозначения. Пусть G(t,m) — произвольная коммутативная циклическая группа порядка т с операцией, которую будем в дальнейшем обозначать +, требующей для своего выполнения t битовых операций, и пусть L(t,m) обозначает минимальное количество битовых операций, необходимых для решения задачи дискретного логарифмирования в группе G(t,m), то есть при известных а, Ь Є G(t,m) найти п Є Zmi такое, что а = nb, (1.7) здесь nb есть b + 6, где элемент b повторяется п раз. Не ограничивая общности дальнейших рассуждений, будем считать b образующим группы G(t,m). Пусть D(t,m) — неубывающая по т оценка количества битовых операций, необходимых для решения задачи Диффи-Хеллмэна: при известных 2i, 22 и Ь таких, что а\ = n\b}a2 = n2b} найти а3 = {плп2)Ъ. (1.8)

Пусть D (t,m) — также неубывающая по т оценка количества битовых операций, необходимых для решения той же задачи при помощи алгоритмов, количество битовых операций в которых удовлетворяет неравенству D {t,m) tD {C,m), для некоторой абсолютной константы С (например таких, которые используют только операции, сложность которых не более, чем сложность групповой операции). Прежде чем сформулировать теорему, сделаем несколько замечаний. Пусть г=1

Замечание. Маккарли в [92] доказал, что, в случае г = 3,pi = 2 и а2 = «з = 1; количество битовых операций, необходимых для разложения на простые множители числа р — 1, есть 0(D(t,p — 1) + log (р — 1)) и не превосходит D(t,p-l)-log2(p-l), если константу из О, также как и все абсолютные константы в дальнейшем, считать учтённой в основании логарифма. Принимая во внимание тот факт, что для всех известных алгоритмов разложения на множители этот случай представляется наиболее трудоёмким, эта оценка кажется правдоподобной и для р — 1, разлагающихся на большее число простых множителей. Замечание. Поиск первообразного корня по модулю р, как было описано в первой главе, можно осуществить следующим образом. Количество первообразных корней по м,одулю р равно (р(р — 1); где (р - функция Эйлера. Поэтому, принимая во внимание известную оценку Ландау [93] Т) 4 {п) С log log п где С — некоторая абсолютная константа, можно считать эффективной случайную выборку g Є {1,...,р— 1} с последующей проверкой выполнения неравенств gVi ф\ (modp), i = l,...,r. (1.9)

В случае успеха, число g является первообразным корнем по модулю р. Количество битовых операций, необходимых для проверки соотношений (1.9), не превосходит logp и(р) 1у(р — 1), где 1у(р — 1) - количество различных простых делителей числа р — 1, а и{р) - число битовых операций, необходимых для умножения по модулю р. Несложные вычисления показывают, что, действуя таким способом, за logp log logp и(р) v(p — 1) битовых операций, мы найдём первообразный корень по модулю р с вероятностью 1 — е с + о(1) при р —оо. Повторяя эту операцию конечное, но большое число раз, получим вероятность, близкую к единице. Кроме того, применяя преобразование Абеля, находим, что log(2 3 5 Ps) = slogs + o(slogs), где pa - s-e простое число, поэтому где log log Pj \loglogp/ v{p-l) p= П РІ Таким образом, первообразный корень (mod р) можно найти за и(р) log р арифметических операций с вероятностью, близкой к единице.

Оба эти замечания касаются случая несертифицированной задачи дискретного логарифмирования. В случае же сертифицированной задачи разложение р— l,Pi — 1, і = 1,... ,r, qij — 1 для простых qij \ Pi и так далее на простые множители, а также первообразные корни по модулям р,Рі, і = 1,... ,r,qij и т.д. считаются известными.

Для произвольного т = YYi=iPiai рассмотрим разложения на простые множители чисел Pi — 1, г = 1,..., г , разложения q — 1 для простых qij \ pi, и так далее. Получившееся разветвление называется деревом Пратта числа т, а встречающиеся простые числа - его узлами. Свяжем узлы q с узлом pi. Назовём ветвью максимальную последовательность связанных друг с другом узлов. Обозначим s = s(m) длину наибольшей ветви дерева т.

Следующая теорема устанавливает связь между сложностями задач дискретного логарифмирования и Диффи-Хеллмэна в общем случае. Теорема 1.3. [23] Для сертифицированной задачи дискретного логарифмиров L{t,m) slog2mD{... D{D{t,m),m)...), (1.10) где справа стоит s- кратная итерация функции D(t}m)} L{t,m) tslog2m{D {G\m))s. (1.11) Теорема 1.4. [23] В случае, если оценка из приведённого выше замечания для числа операций, необходимых для разложения на множители, выполняется для любого простого р, то утверждение теоремы 1.3 останется верным и без условия сертифицированности, но только для вероятностных алгоритмов дискретного логарифмирования. Подобная оценка с s = 1, но только для простых т, удовлетворяющих некоторому условию гладкости, была получена ранее в теореме 1.2 (см. также [94]).

Для простоты рассмотрим сначала случай, когда т - простое число, т = р. Без ограничения общности можно считать, что в уравнении (1.7) п ф 0 (mod р), а Ь - не единичный элемент группы G(t,p). Введём на множестве элементов {nb п ф 0 (mod р)} новую групповую операцию, заданную равенством П\Ъ 0 пф = {П\П2)Ъ. Количество битовых операций, необходимых для выполнения этой операции, равно, очевидно, D(t,p). Так как отличные от нуля вычеты по простому модулю образуют циклическую группу по умножению, мы получаем циклическую группу порядка p(p)=p-i = Y[piai с аддитивной операцией 0, где рі, і = 1,... ,r, - различные простые числа, а г = 1у(р — 1). Обозначим эту группу G(D(t,p),p — 1). Ясно, что Ь - единичный элемент этой группы. Пусть д — первообразный корень по модулю р, тогда дЬ - образующий группы G(D(t,p),p — 1). Эта группа является прямой суммой примарных циклических групп порядка piai с образующими соответственно дф, где 9г = дщЩ (modp), i = l,...,r. Пусть п = gv (mod р). Уравнение (1.7) можно переписать в виде а = 0 6 = ginib 0 0 дгПгЪ, і где р — 1 1 пг рга% v = —— пг (mod ai ), i = l,...,r, Рг0і или а = щ (gib) 0 0 nr (grb), где операция (операция умножения на натуральные числа элементов группы G(D(t,p),p — 1) определена для операции 0 так же, как для +, а именно где операция 0 связывает / элементов. Заметим, что / при этом можно считать вычетом по модулю р — 1. Количество битовых операций, необходимых для такого умножения с применением бинарного алгоритма, очевидно, не превосходит logn-D(t,p). Теперь, чтобы определить число п в выражении (1.7), будем искать числа ПІ , а затем найдём п по формуле

Для этого потребуется не более, чем v(p— 1) log (р — l)D(t,p) битовых операций. Ещё v(p — 1) log (р — 1)(и(р) + t) битовых операций необходимо для вычисления gi,gib при известных д и b для всех і = 1,...,г. Затем, решая задачу дискретного логарифмирования в циклической подгруппе порядка ріаі группы G(D(t,p),p — 1), порождённой элементом дф, найдём такое t{: что щ = и- (д{Ь). (1.12) Для этого потребуется L(D(t,p),piai) битовых операций. Причём, очевидно, что гьг—— = U (mod р.04). Рг0і С помощью алгоритма Евклида элемент - - по модулю piai можно обратить за Рг г и{р) logpiai битовых операций, поэтому количество битовых операций, необходимых для нахождения каждого ПІ при известных а , 6, не превосходит L{D{t,p),p )+и{р) logрг\ (1.13)

О полиномиальной эквивалентности задач дискретного логарифмирования и Диффи-Хеллмэна на некоторых стандартных кривых

В открытом доступе имеется описание некоторой группы G и двух ее коммутативных подгрупп Н и Л, при этом предполагается, что не единичные элементы h Є Н,г Є R не коммутируют. Абоненты А и В для выработки общего секретного ключа поступают следующим образом. Каждый из них независимо друг от друга случайно вырабатывает по одному элементу из Н и R и в последующем держит их в секрете: \ЬА Є Н}ГА Є R для А, \ів Є Н} г в Є R для В. Далее они находят элементы дл = Ь АГА , 9в = в в и обмениваются ими по открытому каналу связи (и, тем самым, делают их общедоступными). Для выработки общего ключа абонент А берет свои "секретные"элементы ІІА,ГА и полученный по открытому каналу связи элемент дв и образует произведение hAfjB A- Аналогично абонент В образует произведение квдл в- Из определений вытекает, что ІІА9ВГА = hA{hBrB)rA = {ІІАІІВ){ГВГА) = {ІІВІІА){ГАГВ) = Ь,В{Ь,АГА)ГВ = ІІВ9АГВ = 9 Тем самым, общий секретный ключ д выработан.

Заметим, что если г А коммутирует с Кв (г в коммутирует с НА), ТО д = длдв ( 9 = 9В9А ) и, тем самым, не является секретным. Если внешний наблюдатель хочет найти секретный ключ д, то он должен решить следующую задачу: по известным описаниям G,H,R и известным элементам Е G, дв Є G найти элемент д = JiAgBTA = hsgA B, не зная элементов ІІА А В В Естественный путь для решения этой задачи: сначала "разложить на множители "известный элемент GG, (ИЛИ (JA Є G), то есть найти его представление в виде 9в = hBTB, hB Є H,rB Є R с неизвестными НвіТв- Такое представление единственно из-за условия некоммутативности элементов из Н и R. Действительно, если бы существовало два различных представления hefB = heTB, то тогда неединичный элемент Ifg Уїв = твТв 1 лежал бы в пересечении Н и R7 тем самым, коммутировал бы и с Н и с R. Пусть эта задача решена. Тогда внешний наблюдатель берет найденные им элементы Уїв Є Н, г в Є R, известный элемент (JA Є G и находит интересующий его ключ УІВЯА В Таким образом, стойкость описанной системы определяется сложностью "разложения на множители"в группе G, то есть решением заведомо совместного уравнения g = hr,geG,heH,reR с известным д и неизвестными /гиг. Иногда удобнее это уравнение записывать в следующем виде: у = дх, д Є G,y Є Н,х Є R (3.1) с известным д и неизвестными у и х. При этом сложность решения меняется несущественно: добавляется обращение элемента г - нахождение г-1, что при знании порядка группы является полиномиально разрешимой задачей. Резюмируем для удобства все требования на группы, вытекающие из соображений реализации системы и оценки ее стойкости: 1. Свойства групп H,R позволяют эффективно вырабатывать случайные элементы из Н и R. 2. Свойства групп G,H,R позволяют эффективно вычислять произведения элементов из этих групп. 3. Группа G такова, что позволяет эффективно передавать по открытому каналу связи ее элементы. 4. Сложность решения заведомо совместного уравнения (3.1) достаточно высока.

Подчеркнем, что требование "любые не единичные элементы h Є Н,г Є R не коммутируют "не включено в этот список. Дело в том, что это требование очень сильное и существенно ограничивает класс допустимых групп. Оно введено выше только для упрощения первого описания системы, поскольку гарантирует невозможность явного вы-ражения секретного элемента д через известные элементы дл и дв (в виде д = длдв , или д = двдл)- В общем случае, когда не исключена вероятность выбора коммутирующих элементов ГА И їів , г в и ЇІА , при анализе и оценке стойкости системы необходимы дополнительные рассмотрения. При этом стойкость системы понижается из-за ненулевой вероятности появления таких ситуаций.

Одновременно с этим пропадает свойство единственности разложения на множители, единственности решения уравнения (3.1). Но это не меняет логики описанного метода нахождения секретного ключа д: для этого достаточно использовать произвольное разложение на множители". Оба разных разложения дают один и тот же элемент д. Действительно, пусть дв = hBrB = hBrB с некоторыми Іів}їів Є Н}гв}гв Є R. Тогда с = JI -JIB = гвгв1 Є Я П Л, и элемент коммутирует со всеми элементами из Н и R. Тогда Ъвдлгв = {Ъвс)дА{с 1гв) = Нвдлгв = 9 С учетом этих замечаний дальше не будем следить за выполнением требования о том, чтобы любые не единичные элементы h Є Н,г Є R не коммутировали, а для уравнения (3.1) будем искать произвольное решение.

Ниже будут рассмотрены некоторые алгебраические структуры с целью нахождения групп с высокой сложностью решения уравнения (3.1) с учетом требований 1-3.

Алгоритмы сложения и приведения дивизоров

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

В 1985 году Эль-Гамаль [8] предложил оригинальные схемы шифрования и электронной подписи. Самую большую известность приобрела схема электронной подписи, на основе которой в дальнейшем было создано очень много криптографических протоколов для решения различных конкретных задач защиты информации. Один из примеров - стандарт электронной подписи ЦБ РФ, описанный ниже. Пусть р - простое число, GF(p) = (д), то есть д - первообразный корень по модулю р. A В к єд {1,...,р-1}, у = дк (mod р) У г Єд {1,...,р-1}, t = gr (mod р) пусть m - сообщение, s - решение сравнения rs + kt = т (mod р - 1), 5Є {1,...,P-1}. w,(s,t) tG{l,...,p-l}, ? S Є {1,...,р-1}, ? gm = y ts (mod p). Если последние проверки выполнены, то подпись принимается, в противном случае не принимается.

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

Конечно, умение подписывать в этом протоколе не сложнее задачи дискретного логарифмирования. Однако вопрос об эквивалентности этих задач пока открыт. DSA (стандарт электронной подписи США) Пусть [?] р, q - простые числа, q\p - 1, д Є (Z/pZ) - элемент порядка q: сообщение т лежит в некотором множестве сообщений М. Хеш-функция h : M ZJ. А В x Єд Z/gZ, у = gx (mod p), у ueRZ/qZ\{l}, r = gu (mod p) (mod g), s = u l(h(m) + ят) (mod q), Проверка (r,s) Ф (0,0). (mrs,r) v = s_1 (mod g), 0 r q? 0 s q? r = gvh(m)yvr (mod p) (mod g).

Здесь под первым взятием по модулю подразумевается получение наименьшего положительного вычета.

Для построения цифровой подписи в ГОСТе Центрального банка РФ 1996 года используется аналогичная схема, где выражение для получения s заменено на следующее: s = uh(m) + xr (mod q), а соответствующее проверочное равенство выглядит как Г = gsh(m) y-rh(m) (moc[ pj (mod q). Отметим [19, 20] важность проверки неравенств в последнем шаге работы ГОСТа. Дело в том, что, решив с помощью китайской теоремы об остатках при некотором с следующую систему I г = с (mod q) I r = Rc (mod p), где R = (gy-1)11 , мы получим пару (s = r (mod q),r), удовлетворяющую проверочному соотношению, причём 0 г pq} 0 s q. Заметим также, что выполнение указанной системы при некотором с эквивалентно выполнению сравнения r = Rr (modp). (4.1) Значит, умение решать это сравнение относительно г Є {1,...,(/ — 1} даст возможность подписывать любое сообщение, то есть осуществлять универсальную подделку. Отметим, что решение рассматриваемого сравнения не сводится сразу к задаче дискретного логарифмирования, хотя, с другой стороны, с помощью Китайской теоремы об остатках оно может быть легко решено для г Є {1,... ,pq— Аналогичные рассмотрения для схем цифровой подписи Эль-Гамаля и DSA приводят к сравнению вида г = CRr (modp),r Є {l,...,g — 1}, что снова приводит к сравнению (4.1) с условием г = С\г\г Є {1}... }q — 1}. В книге Р.К. Ги ” Нерешенные задачи теории чисел" [46] приводится следующая задача, называемая задачей Бризолиса: для каких простых р существует первообразный корень g(modp) и целое х : 1 х р — 1 такое, что х = дх (mod р)?

В 2003 году появилась диссертация М.Л.Кэмпбелл ” О неподвижных точках дискретных логарифмов” [ПО], которая посвящена доказателству того, что для любого простого р существует первообразный корень д по модулю р7 взаимнопростой с р — 1, то есть (g,p-1) = 1. (4.2)

Эти первообразные корни дают решение сравнения x = Rx (mod p);x,R Є Z,(r,p) = 1, (4.3) в виде х = g,R = д9 (modP-!)5 ГдЄ д, очевидно, также первообразный корень, то есть решение задачи Бризолиса. Доказательство использует оценки тригонометрических сумм, в частности оценку Полиа-Виноградова (см.[126], глава 23), а также объёмные компьютерные вычисления. Вопрос о построении конкретных решений, а также оценке их количества, тем самым, остался открытым.

В данной главе [45] получены некоторые общие решения уравнения (4.3), а также получена оценка снизу на число первообразных корней, удовлетворяющих условию (4.2) для случая, когда р — 1 не содержит ” маленьких” нечётных простых множителей. Будем обозначать a (mod р) наименьший положительный вычет по модулю р. Лемма 4.1. [Щ Пусть d \ р — 1 1) Уравнение (4-3) не имеет решений среди пар (ж, R), таких, что ordpR \ d} тогда и только тогда, когда для любого щ Є {1,... ,d — 1} выполнено (d,gu (mod р)) \щ. 2)Уравнение (4-3) не имеет решений среди пар (ж, R), таких, что ordpR = d} тогда и только тогда, когда для любого щ Є {1,..., d — 1} выполнено (d, gu (mod p)) Ф (uo,d).

Рекуррентные формулы для приближений Паде

Пусть F[IE],F(:C) соответственно кольцо многочленов и поле рациональных функций над полем F. Элемент называется алгебраическим, если он алгебраический над полем рациональных чисел Q. В этом случае, очевидно, он является корнем многочлена с целыми коэффициентами. Элемент а называется целым над кольцом К, если он является корнем многочлена с коэффициентами из К со старшим коэффициентом равным единице.

Если в этом определении К = Z, то говорят о целых алгебраических числах. При помощи теоремы о симметрических многочленах нетрудно показать, что сумма и произведение двух алгебраических элементов, а также обратный элемент к любому алгебраическому также является алгебраическим. Таким образом, алгебраические над фиксированным полем элементы также образуют поле. Аналогично доказывается, что целые элементы над фиксированным кольцом образуют кольцо. Подробные доказательства можно найти, например, в [3].

Кольцо К называется целозамкнутым в некотором объемлющем кольце L, если каждый элемент аЄІ, целый над К, снова лежит в К. Для конечных полей и полей нулевой характеристики верна следующая теорема: Теорема 5.1. [129](0 примитивном элементе) Пусть F(«i,...,ah) - конечное алгебраическое расширение поля F. Тогда для некоторого алгебраического над F элемента а (ah... ,ah) = F(a). Необходимые для понимания дальнейшего текста свойства дивизоров гиперэллиптических кривых изложены в приложении.

Пусть Fq(x,y) - квадратичное расширение поля Fq(x), образованное присоединением алгебраического элемента второй степени у, удовлетворяющего следующему уравнению гиперэллиптической кривой С [127, 128]: у2 + f(x)y + h(x) = 0, degf(x) g, degh(x) = 2g + 1. (5.1) Пусть Fq - алгебраическое замыкание поля Fq, а кривая С является гладкой. Для каждого (дробного) идеала а кольца Fq[x,y] определим diva = Т,прР, (5.2) где точки Р соответствуют простым идеалам кольца Fq[x,y], которые мы будем обозначать той же буквой, а их кратности пр определены разложением идеала а в произведение простых идеалов: a = UPnp. (5.3) Это определение корректно, так как согласно [129, Теорема 19 гл.У, 8, ], кольцо Fq[x,y] является областью с однозначным разложением на простые идеалы.

При этом отображение (5.2) задаёт изоморфизм якобиана кривой (5.1), то есть группы дивизоров, и группы (дробных) идеалов кольца Fq[x,y], определённый равенством Fg(x,y)(«) = SnpP-P00Snp, (5.4) где PQO - бесконечно удалённая точка (продолжение нормирования, порождённого простым делителем идеала -), которая в данном случае в силу [48, лемма 2.4 1 глава 2, часть 1] единственна. Два идеала а, (3 С Fq{x,y) называются подобными, если существует такой элемент 7 Є Fq[x,y]: что ja = (3. Соответствующие им дивизоры (5.2) в рассматриваемом случае будут подобны (их разность является дивизором элемента 7)- При этом отображение (5.2) задаёт изоморфизм группы классов подобных дивизоров (якобиан поля Fq{x,y)) и группы классов подобных идеалов кольца Fq[x,y]. Подобие идеалов и дивизоров будем, как и раньше, обозначать . Все конечные нормирования поля Fq{x) соответствуют идеалам вида (х — хо), где Хо Є Fq (это все простые идеалы кольца Fq[x\). При расширении кольца Fq[x] до кольца Fq[x,y], где у удовлетворяет уравнению (5.1), идеал (х — Хо) перестаёт быть простым и раскладывается в произведение двух, возможно, одинаковых простых идеалов: (х-хо,у-уо),(х-х0,у-у0), (5.5) где у0 - сопряжённое к уо решение уравнения (5.1) при х = Хо. Действительно, каждый из них, очевидно, делит идеал (х — хо), а перемножив эти идеалы при помощи уравнения (5.1), легко увидеть, что их произведение делится на (х — х$). Кроме того, идеалы (5.5) — простые, так как они состоят из всех многочленов, обращающихся в ноль в точках соответственно Р = Р(хо,уо) и Р = Р(хо,у0) (в скобках указаны координаты точек). Действительно, для а(х),Ь(х) Є Fq[x] выполнена следующая цепочка следствий: a(x) + уЬ(х)\х=ХО:У=Уо = 0 = а(ж) + у&(ж) - (у - уо)Ь(х)\х=ХО:У=Уо = 0 = а(ж) + у&(ж) — (у — уо)Ь(х) = а(х) + уоЬ(х) = (х — хо)с(х) для некоторого с(ж) Є [ж]. Значит, а(ж) + у&(ж) Є (х — Хо}у — уо). Поэтому где QXo - нормирование поля Fq(x), отвечающее простому идеалу (х — XQ) , а Fq(x,y)(iX Хо)) = Рх0,»о + о,!7о " 2 оо, (5.6) где Р(хо,уо), Р = Р(хОіУо) - нормирования поля, отвечающие простым идеалам (5.5). Действительно, согласно [140, Теорема 4, гл. 1] дивизор элемента поля имеет нулевую степень. Коэффициент 2 при бесконечно удалённой точке означает, что идеал - в соответствующем кольце нормирования поля Fq(x,y) является квадратом простого идеала.

В дальнейшем мы будем говорить только о дивизорах нулевой степени и бесконечно удалённую точку будем опускать. Дивизор D = трР поля Fq(x,y) определён над Fqj если Da = T1mpPa = D для любого а Є Gal(Fq/Fq) или D = J2kmk J2a Р Приведём некоторые примеры. При Хо Є Fq дивизор (5.6) определён над Fq. Определёнными над Fq будут дивизоры J2a Fq(x)(x - xoa),J2a Fq(x,y)(x - xoa)-Отсюда, очевидно, следует: Замечание. Любой, определённый над Fq, дивизор поля эквивалентен некоторому полуприведённому дивизору D = гпрР, определённому над Fq, mo есть для всех конечных точек Р выполнено: тр 0, а если гпр 0 ; то rrip = 0 при Р = P}rrip = 1; при Р = Р (см. также [60, Appendix Л. 4-2])