Содержание к диссертации
Введение
Глава 1. Обоснование необходимости решения задачи генерации криптографически стойкой эллиптической кривой для асимметричной криптосистемы 11
1.1. Симметричные и асилшетричные криптографические системы 11
1.1.1. Понятие асимметричной криптографической системы 11
1.1.2. Сравнительный анализ свойств асимметричной и симметричной криптосистем 15
1.2. Оценка криптографической стойкости асимметричных криптосистем 20
1.2.1. Базовые параметры асимметричной криптосистемы на основе модульного возведения в степень 20
1.2.2. Базовые параметры асимметричной криптосистемы на базе эллиптической кривой 22
1.2.3. Алгоритмы дискретного логарифмирования для оценки стойкости асимметричных криптосистем 26
1.2.4. Сравнительный анализ стойкости криптосистемы на базе эллиптической кривой и криптосистемы на основе модульного возведения в степень 28
1.3. Разработка алгоритма определения факта криптографической стойкости эллиптической кривой 37
1.3.1. Сравнительный анализ требований, предъявляемых к криптографически стойкой эллиптической кривой согласно стандартам асимметричного шифрования ECDSA и ГОСТ Р 34.10-2001 37
1.3.2. Алгоритм определения факта криптографической стойкости эллиптической кривой 40
1.4. Обоснование необходимости решения задачи генерации криптографически стойких ЭК для асимметричной криптосистемы на базе ЭК 41
1.4.1. Обоснование необходимости использования комплексного подхода для решения задачи генерации криптографически стойкой ЭК 41
1.4.2. Разработка метода сравнительной оценки стойкости эллиптических кривых 43
Выводы 44
Глава 2. Методика выбора/генерации криптографически стойкой эллиптической кривой для асимметричной криптосистемы на эллиптических кривых 46
2.1. Определение индексов стойкости ЭК для метода оценки сравнительной стойкости эллиптических кривых 46
2.2. Общая модель выбора криптографически стойкой эллиптической кривой для асимметричной криптосистемы на эллиптических кривых 50
2.3. Методика выбора/генерации криптографически стойкой эллиптической кривой 53
2.3.1. Методы генерации эллиптической кривой 54
2.3.2. Метод выбора эллиптической кривой 57
2.4. Рекомендации по использованию методики выбора/генерации
криптографически стойкой эллиптической кривой 59
Выводы 61
Глава 3. Разработка алгоритмов генерации криптографически стойких эллиптических кривых 63
3.1. Разработка стратегии «случайного выбора» эллиптической кривой 63
3.1.1. Общее описание алгоритма расчёта числа точек ЭК над конечным полем 63
3.1.2. Алгоритм Чуфа для расчёта числа точек ЭК 65
3.1.3. Алгоритм SEA для расчёта числа точек ЭК 72
3.1.4. Алгоритм раннего обнаружения нестойкой ЭК 76
3.2. Разработка стратегии «детерминированной генерации» эллиптической кривой 79
3.3. Достоверность параметров эллиптических кривых, полученных в результате использования стратегии «случайного выбора» эллиптической кривой и стратегии «детерминированной генерации» эллиптической кривой 86
Выводы 88
Глава 4. Анализ результатов использования методики выбора/генерации криптографически стойкой эллиптической кривой для асимметричной криптосистемы на эллиптических кривых 89
4.1. Описание базы криптографически стойких ЭК 89
4.1.1. Количественные характеристики базы 89
4.1.2. Разделение базы ЭК по уровням криптостойкости 92
4.2. Анализ результатов использования стратегии «случайного выбора» эллиптической кривой 94
4.2.1. Анализ количества перебираемых ЭК до нахождения искомой 94
4.2.2. Анализ продолжительности генерации ЭК 98
4.3. Анализ результатов использования стратегии «детерминированной генерации» эллиптической кривой 104
4.4. Защита базы криптографически стойких эллиптических кривых от несанкционированного доступа 108
4.4.1. Использование встроенного метода шифрование mdb-файлов Microsoft Access 108
4.4.2. Метод прозрачного шифрования для защиты базы криптографически стойких эллиптических кривых 116
Выводы 122
Заключение 123
Список использованных источников 124
Приложение. Таблица криптографически стойких эк 132
- Базовые параметры асимметричной криптосистемы на основе модульного возведения в степень
- Общая модель выбора криптографически стойкой эллиптической кривой для асимметричной криптосистемы на эллиптических кривых
- Общее описание алгоритма расчёта числа точек ЭК над конечным полем
- Анализ количества перебираемых ЭК до нахождения искомой
Введение к работе
Актуальность темы. Всё более широкое распространение различного рода информационных систем с использованием средств асимметричной криптографии, с одной стороны, связано с потребностью субъектов системы в надёжном механизме обеспечения аутентичности передаваемых данных, а с другой — с тем, что современные криптографические протоколы обладают высокой степенью стойкости, что позволяет субъектам системы быть абсолютно уверенными в их надёжности. Как показывают исследования ведущих ученых, среди криптосистем (КС) с открытым ключом наиболее стойкими являются КС на эллиптических кривых (ЭК).
Диссертационная работа опирается на результаты исследований таких ученых как Н.Коблиц, Р.Чуф, Дж.Сильверман, А.Аткин, Ф.Моран, С.Ванстоун, А.Менезес, Т.Окамото. В работе получили развитие отдельные положения этих исследований применительно к задаче создания методики генерации криптографически стойкой ЭК и задаче оценки стойкости ЭК.
Проблема выбора криптографически стойкой ЭК для асимметричной КС, связанная, прежде всего, с трудоёмкостью вычислений и сложностью реализации соответствующих алгоритмов, вызвала необходимость разработки методики выбора/генерации криптографически стойкой ЭК, доступной для использования в реальных КС. В работе показано, что наиболее перспективным является подход на основе сочетания стратегий «случайного выбора» ЭК и «детерминированной генерации» ЭК, основанных на использовании метода комплексного умножения и алгоритма SEA, соответственно. Предложенная автором методика позволяет накапливать базу ЭК, предоставляя возможность либо выбрать из уже имеющихся ЭК, либо сгенерировать новую. Использование данной методики повышает криптостойкость всей системы.
Кроме того, при выборе ЭК из базы требуется инструмент для оценки стойкости выбираемой ЭК. Однако наилучшие алгоритмы вычисления кратности точки ЭК имеют экспоненциальную оценку сложности. В работе пред-
ложен метод сравнительного анализа стойкости ЭК, который позволяет разделить базу криптографически стойких ЭК по уровням криптостойкости на основании сравнения порядка циклической подгруппы группы точек ЭК, числа г, с заданными интервалами значений числа г. Предложенный метод предоставляет объективную информацию о стойкости ЭК, так как в его основе лежит сравнение основного показателя криптостойкости ЭК — порядка циклической подгруппы группы точек ЭК.
Целью диссертационной работы является повышение криптографической стойкости асимметричных КС на базе ЭК.
Для достижения поставленной цели в работе сформулированы и решены следующие задачи:
исследование и анализ ассиметричных КС, в частности систем на базе ЭК;
обоснование необходимости совершенствования и модификации алгоритмов генерации ЭК для ассиметричных КС;
модификация алгоритма раннего обнаружения нестойкой ЭК, используемого в рамках алгоритма расчёта точек ЭК SEA;
анализ подходов к генерации ЭК с помощью метода комплексного умножения и на основе случайного перебора ЭК;
-— разработка метода сравнительной оценки стойкости ЭК;
разработка метода защиты mdb-файлов СУБД Microsoft Access, содержащих базу криптографически стойких ЭК;
разработка программного обеспечения, реализующего методику выбора/генерации криптографически стойкой ЭК для асимметричных КС на ЭК.
Методы исследования. В работе использованы методы алгебры, теории чисел, алгебраической геометрии, дискретной математики, теории вероятностей, криптографии, теории сложности.
Достоверность и обоснованность сформулированных в работе выводов, научных положений и рекомендаций обусловлена теоретическими решениями и экспериментальными данными, полученными в работе, и не про-
тиворечат известным положениям наук теории чисел, теории вероятностей и криптографии. Результаты генерации криптостойких ЭК согласуются с известным опытом создания баз ЭК.
Положения, выносимые на защиту:
модифицированный алгоритм раннего обнаружения нестойкой ЭК, позволяющий сократить число перебираемых ЭК в процессе поиска искомой при использовании стратегии «случайного выбора»;
метод сравнительного анализа стойкости ЭК, позволяющий получить сравнительную оценку криптографической стойкости ЭК;
методика выбора/генерации криптографически стойкой ЭК для асимметричной криптосистемы на ЭК, сочетающая в себе методы генерации ЭК с помощью стратегий «детерминированной генерации» и «случайного выбора», а также метод сравнительной оценки стойкости ЭК и метод выбора ЭК;
метод защиты mdb-файлов Microsoft Access на основе шифрования заголовка файла.
Научная новизна работы состоит в следующем:
предложена модификация алгоритма раннего обнаружения нестойкой ЭК, используемого в рамках алгоритма расчёта точек ЭК SEA;
разработан метод сравнительного анализа стойкости ЭК, позволяющий получить сравнительную оценку их криптографической стойкости;
предложена методика выбора/генерации криптографически стойкой ЭК для асимметричной криптосистемы на ЭК, сочетающая в себе методы генерации ЭК с помощью стратегий «детерминированной генерации» и «случайного выбора», а также метод сравнительной оценки стойкости ЭК и метод выбора ЭК;
предложен метод защиты mdb-файлов Microsoft Access на основе шифрования заголовка файла.
Практическая полезность и реализация результатов работы состоит в следующем:
— разработано программное обеспечение, реализующее указанную методику
и позволяющее получать ЭК, отвечающие различным требованиям стойкости, в том числе и требованиям ГОСТ Р 34.10 — 2001, которое может использоваться как отдельно, так и в рамках асимметричной КС;
в результате использования разработанного программного обеспечения получена база, содержащая 5944 криптографически стойких ЭК;
разработанный метод защиты данных, содержащихся в mdb-файлах СУБД Microsoft Access, может быть применён в любом приложении, использующем указанную СУБД.
Личный творческий вклад автора. В работах, указанных в списке публикаций по теме диссертации, автором получены все аналитические выводы и выполнены численные расчеты. Основные теоретические положения и практические рекомендации по теме диссертации, приведенные в этих работах, получены автором самостоятельно.
Апробация работы. Основные результаты и положения работы докла-дывались и обсуждались на следующих конференциях:
Международная научно-техническая конференция по интеллектуальным системам AIS'06 (Дивноморское, 2006);
Региональная научно-техническая конференция «Информационные технологии в образовании» (Марийский государственный технический университет, г. Йошкар-Ола, 2006);
Международная научно-техническая конференция по интеллектуальным системам AIS'07 (Дивноморское, 2007);
Всероссийская научно-техническая конференция «Информационные технологии в образовании» (Марийский государственный технический университет, г. Йошкар-Ола, 2007);
Международная конференция «РусКрипто2008» (Ассоциация «РусКрипто», г. Москва, 2008);
Всероссийская научно-техническая конференция с международным участием «Информационные технологии в образовании» (Марийский государст-венный технический университет, г. Йошкар-Ола, 2008).
Публикации. Основные результаты диссертационной работы изложены в 16 публикациях, в том числе 1 статья в центральном научно-техническом журнале, рекомендуемом ВАК РФ, 4 статьи в трудах международных научных конференций, 1 свидетельство об отраслевой регистрации программы для ЭВМ.
Объем и структура работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы из 63 наименований и одного приложения.
Базовые параметры асимметричной криптосистемы на основе модульного возведения в степень
Асимметричные криптосистем на основе модульного возведения в степень - это криптосистемы с открытым ключом, основанные на проблеме вычисления дискретного логарифма. Примерами таких КС являются следующие: — криптосистема DSA (Digital Signature Algorithm)[29]; — криптосистема Эль-Гамаля (ElGamal)[9]; — криптосистема Шнорра[3];
Отметим, что для успешной реализации и эффективного использования систем данного класса первоначально необходимо выбрать базовые параметры системы. В общем случае это простое число р и целое число g, степени которого по модулю р порождают большое число элементов Zp. Кроме этого для конкретной реализации необходимо выбрать также и ряд дополнительных параметров.
Число х может быть произвольно выбрано из интервала 0 х q, у формируется уже на основании всех параметров, сгенерированных ранее. Таким образом, для успешной реализации указанной КС необходимо сгенерировать математически связанные параметры криптосистемы (для ГОСТ Р 34.10 - 94 это р, q и а), основным из которых является число р, которое в конечном счёте и определяет стойкость системы.
При описании КС указанного класса зачастую не уделяют должного внимания алгоритмам генерации базовых параметров КС, ограничиваясь лишь требованиями, на них накладываемыми. В отличие от других КС на основе модульного возведения в степень, ГОСТ Р 34.10 - 94 чётко определяет данные процедуры. Как отмечалось выше, стойкость КС данного класса основывается на сложности решения задачи дискретного логарифмирования, подробно рассмотренной ниже. Главное, необходимо отметить, что в настоящее время задача дискретного логарифмирования применительно к раскрытию указанной КС решается наиболее эффективно с помощью метода решета числового поля[Л]. Этот и ряд других фактов заставил отказаться от использования данной КС в качестве стандартов асимметричного шифрования. Но, несмотря на это, данные КС остаются актуальными и могут быть использованы при условии генерации ключей достаточно больших размеров (на сегодняшний день это 2048 или 3072 бит).
Переходя к рассмотрению асимметричной криптосистемы на базе ЭК, в первую очередь отметим, что стойкость данной криптосистемы основана на том, что проблема логарифмирования в конечном простом поле является сложной с вычислительной точки зрения. Однако, конечные поля являются не единственными алгебраическими структурами, в которых может быть поставлена задача вычисления дискретного логарифма. В 1985 году Коблиц и Миллер независимо друг от друга предложили использовать для построения криптосистем алгебраические структуры, определенные на множестве точек ЭК[44].
Пусть Е — эллиптическая кривая, Р є Е — точка на этой кривой. Выберем целое число п #Е. Тогда в качестве прямой функции выбирается произведение пР. Для его вычисления по оптимальному алгоритму потребуется не более 2\og2n операций сложения [1]. Обратную задачу формулируют следующим образом: по заданным эллиптической кривой Е, точке Р є Е и произведению пР найти п. В настоящее время все известные алгоритмы решения этой задачи обладают экспоненциального оценкой сложности[4].
Основным методом оценки криптографической стойкости асимметричной КС является применение алгоритма вычисления секретного ключа по известному открытому и оценка характеристик работы этого алгоритма, в первую очередь трудоемкости. Рассматривая КС на базе ЭК, отметим, что, как указано выше, степень их стойкости основана на сложности вычисления кратности точки ЭК. Другими словами на сложности дискретного логарифмирования (ДЛ) на ЭК. Поэтом для вычисления секретного ключа в данном случае так же могут быть применены алгоритмы ДЛ, эффективно работающие в случае КС на основе модульного возведения в степень. Однако метод решета числового поля, успешно работающий в случае с КС на основе модульного возведения в степень, для логарифмирования на ЭК оказывается непригодным в связи с отсутствием определения гладкости точки на ЭК [4]. А алгоритмы, пригодные для вычисления кратности точки ЭК, работают с экспоненциальным временем, что не позволяет эффективно решать указанную задачу. В связи с этим, в общем случае стойкость криптосистем на ЭК выше, чем криптосистем с модульным возведением в степень. Приведем ряд определений, рассмотренных более подробно в работе [14].
В первую очередь приведем формулировку задачи ДЛ. Пусть G - конечная циклическая группа порядка п и а — ее образующий. Дискретным логарифмом элемента Р є G по основанию а (обозначение log ,/?) называется целое число х, О х п — 1 такое, что /? = ах. Задача дискретного логарифмирования (задача ДЛ) может быть сформулирована следующим образом. Дана конечная циклическая группа G порядка п с образующим а и дан произвольный элемент Р є G. Требуется найти число loga j3. Очевидно, что для некоторых циклических групп задача ДЛ решается несложно. Например, для аддитивной группы кольца вычетов Zmno модулю т прологарифмировать некоторый элемент J3 по основанию а - значит решить сравнение ах = J3(mod пі). Это означает, что логарифмирование в группе (Zm,+) можно осуществить с полиномиальной сложностью, оцениваемой величиной 0( log2 п ), то есть задача ДЛ в аддитивной группе кольца вычетов по модулю т не является сложной.
Общая модель выбора криптографически стойкой эллиптической кривой для асимметричной криптосистемы на эллиптических кривых
Для общего описания методики выбора/генерация криптографически стойких ЭК для асимметричной КС построим соответствующую модель выбора (рис. 2.4). Представленная модель служит для описания разработанной методики и показывает структурные составляющие методики и направление информационных потоков между ними.
Показанные на рис.2.4 элементы методики более подробно рассмотрены ниже, здесь же дадим общее описание методики с помощью данной модели. Первоначально отметим, что, как указано на рис 2.4, и методы генерации ЭК, и метод выбора ЭК могут быть использованы независимо друг от друга для получения криптографически стойкой ЭК. Однако в предлагаемой методики метод сравнительного анализа криптографической стойкости ЭК является «связующим звеном», объединяющим эти методы в одну общую методику выбора/генерации криптографически стойкой ЭК. Эллиптическая кривая )
Методы генерации эллиптической кривой Метод выбора эллиптической кривой Метод сравнительнойоценки стойкости эллиптических кривых idHT ZZ ] Стратегия «случайного выбора» эллиптической кривой Защищенная базакриптографически стойкихэллиптических кривых Стратегия «детерминированной генерации» эллиптической кривой V лт Рис.2.4. Методика выбора/генерации криптографически стойкой ЭК для асимметричной КС на ЭК Таким образом, цикл выбора стойкой ЭК для асимметричной КС с использованием данной методики состоит в первоначальной генерации ЭК, дальнейшем присвоении ей индекса криптостоикости и уже окончательным выбором ЭК из базы криптографически стойких ЭК. При этом, как показано далее в п.4.2 и п.4.3, использование разработанной методики является более эффективным, чем указанных методов генерации ЭК по отдельности, так как позволяет использовать все известные подходы во взаимосвязи друг с другом для получения требуемых ЭК. Кроме того данная методика может быть реализована в виде независимого программного обеспечения для генерации ЭК для «внешних» асимметричных КС. При этом использование разработанного программного обеспечения может быть нацелено именно на наполнение базы криптографически стойких ЭК. Данная база может состоять из сотен криптографически стойких ЭК, удовлетворяющих требованиям того или иного стандарта асимметричного шифрования на ЭК. В дальнейшем эта база может заменить «текущую базу», состоящей из 5 ЭК. Отметим, что, как указано на рис 2.4, база должна быть защищена от действий злоумышленника, направленных на подмену криптографически стойкой ЭК на заведомо слабую. Данный вопрос подробно рассмотрен в п.п. 4.4.
Представленная методика в целом или же отдельные её составляющие могут входить в состав асимметричной КС в виде подсистемы генерации криптографически стойких ЭК. Подход с внедрением методики выбора/генерации криптографически стойкой ЭК как единого целого в КС представляется наиболее перспективным, так как использование исключительно метода выбора ЭК из базы ведет к её исчерпыванию, какой бы большой она ни была. А при использовании всего функционала предлагаемой методики данная проблема не стоит.
Кроме этого, методика является достаточно гибкой, и позволяет при изменении как общих требований, предъявляемых к криптографически стойким ЭК, так и конкретных требований Российского стандарта получать ЭК с требуемыми характеристиками с использованием этих же методов и стратегий выбора ЭК. Для этого необходимо лишь изменить ряд константных параметров, таких как ограничение на числа р или г. При этом сами алгоритмы указанных методов останутся без изменений.
Необходимо так же отметить, что при программной реализации данной методики в первую очередь необходимо определиться с вычислительной моделью, используемой для реализации соответствующих алгоритмов. Вычислительная модель в данном случае представляет собой совокупность модулей, обеспечивающих вычисления в конечных полях, в том числе в группе точек ЭК с использованием целых чисел «больших» размерностей, а так же различного рода прикладные алгоритмы, например, такие как «проверка целого числа на простоту». Под «большой» размерностью имеем в виду целые числа длиной несколько сотен бит. Кроме того, для ряда используемых алгоритмов необходимо предусмотреть обеспечение возможности вычислений в кольце полиномов «больших» степеней. Данным требованиям отвечают несколько библиотек, выбор из которых не является принципиальным. В связи с этим в работе предложено использование библиотеки MIRACLE (Multiprecision Integer and Rational Arithmetic C/C++ Library). Библиотека отвечает всем предъявляемым требованиям и, кроме того, свободно распространяется для некоммерческого использования. Более того, библиотека содержит исходные тексты модулей, реализующих алгоритм SEA и алгоритм «комплексного умножения», являющихся важнейшей составляющей методики генерации ЭК.
Как показано с помощью модели выбора криптографически стойкой ЭК методика выбора/генерации криптографически стойкой ЭК представляет собой совокупность методов генерации ЭК и метода выбора ЭК из набора уже имеющихся. В результате использования любого из данных методов на выходе получаем ЭК с известным порядком циклической группы точек. То есть ЭК, для которой возможно использование алгоритма 1.1. для определения факта её стойкости. Опишем каждую составляющую этой методики.
Методы генерации ЭК представляют собой стратегии получения ЭК с известным порядком циклической группы точек. После генерации ЭК, в случае её успешной проверки на криптостойкость, данная ЭК получает «статус» криптографически стойкой и заносится в базу криптостойких ЭК с присвоением ей индекса криптостойкости на основе метода, описанного в п. 1.2.4.
Стратегия «случайного выбора» ЭК заключается в случайном выборе ЭК над полем Yq (именно случайным является определение коэффициентов ЭК а и Ь). Для этой кривой вычисляется количество её точек и порядок циклической группы точек с помощью алгоритма вычисления порядка группы точек ЭК. Далее, зная все параметры ЭК, можно осуществить проверку на криптостойкость.
Построение ЭК E(Fq) (вычисление коэффициентов а и Ъ уравнения ЭК) по известным D, г и N Как уже отмечено выше, в данной работе рассматриваются криптографически стойкие ЭК, удовлетворяющие требованиям п.п.1.3.2, а это означает в данном случае, что недопустимо использовать значения дискриминанта D=l и D=3 и, аналогично предыдущей стратегии q=p. ЭК с D=l или D=3 могут быть отсечены уже после первого шага алгоритма. Так как уже после 1-го этапа алгоритма становится известно число г генерируемой ЭК, следовательно, ещё до начала процесса непосредственной генерации ЭК можно проверить кривую на криптостойкость. При этом аналогично предыдущей стратегии процесс вычисления D, г и N может циклично повторяться до тех пор, пока не будет найдена криптографически стойкая ЭК. В данном случае это особенно актуально, так как этап 2 алгоритма 2.2. является самым трудоёмким и включает в себя процессы генерации и факторизации полиномов больших степеней. Кроме того, в том случае, если полученная ЭК оказывается криптографически стойкой, это одновременно означает, что она отвечает требованиям ГОСТ, накладываемыми на значения инварианта ЭК, так как ЭК с D=l и D=3 отвергнуты после первого шага алгоритма. Таким образом, не посредственно после завершения алгоритма 2.2. ЭК сразу же попадает в базу криптографически стойких ЭК, если её ещё там нет.
Следует добавить, что перед тем как попасть в базу криптографически стойких ЭК, для данной ЭК необходимо выбрать базовую точку, а именно образующую циклической группы точек ЭК, точка должна иметь порядок г. Для её генерации используется алгоритм, описанный в работе[43], подробно алгоритм приведен в п.п.3.3. После выбора образующей циклической группы, координаты этой точки, а также сама ЭК попадают в базу криптографически стойких ЭК.
Общее описание алгоритма расчёта числа точек ЭК над конечным полем
Как показано в п.п.2.2.1 стратегия ««случайного выбора» ЭК опирается на использование алгоритма SEA для вычисления количества точек ЭК и порядка циклической группы точек для случайно выбранной ЭК. Данный алгоритм есть результат усовершенствования алгоритма Чуфа[61] с помощью модификаций, предложенных Элкисом и Аткином, описанных в работе [60]. Первоначально дадим общее, далее детальное описание алгоритма Чуфа для расчёта числа точек ЭК над конечным полем, покажем модификации Аткина и Элкиса, и, наконец, приведем алгоритм раннего обнаружения нестойкой ЭК.
Если же соответствующий НОД равен 1, то искомое гне сравнимо с 0 по модулю /. В случае неразрешимости уравнения ср / (Р) = ± кР на Е[1\ - переход на 2-й этап алгоритма. Иначе рассмотрим равенство ср / (Р) = ± АР подробнее. 1 случай. Если q? і (Р) = - кР, то из (3.1.2) следует, что хщ =0 (mod /). Отсюда, т=0 (mod Г), так как /(Р) Рда. Таким образом, в данном случае искомое / (mod /) найдено. 2 случай. Если р і (Р) = кР, то, из 3.1.2. следует, что (2А: -і(р і ){Р) =0. 2к Поскольку 2кР Ф О для Р є Е[Г\, то т Ф0 (mod /). Откуда ср / (Р) = — Р. Под г ставляя это значение снова в (3.1.2) и сокращая на кфО, получаем х = 4к (mod Г). В данном случае эндоморфизм Фробениуса ср / должен иметь собственное значение в группе Е\Т\.
Тогда необходимо решить уравнение со =к (mod Г). Для его решения со будет выполнено сравнение т = ± 2 со (mod /), и останется лишь определить истинный знак + или —.
Подставляя т = ±2 со (mod /) в (3.1.2), получим р і" ± 2соср / + со = О, или ((Рі+со) =0 тождественно на E\J\ . Поэтому собственное значение линейного отображения ср / на Е[Т\ может быть только ± со (mod Г) (если г - собственное значение, то (г + со) =0 (mod 1)). Проверку существования решения Q є Е[ґ] уравнения (ср ± co)Q =0 осуществляется так же, как осуществляется проверка существования решения уравнения ср / (Р) = ± АР. Пусть Q = (х, у),
Степень данного полинома есть число 1+1. Для определения указанного выше типа числа / необходимо выполнить следующие операции: — вычислить /-ый модульный полином Фі(Х,У)єр[Х, Y[\ — взять j(E) — инвариант ЭК Е и определить 0i(Xj(E)) GFq[Xj; — вычислить тип разложения полученного полинома и определить {гІ)І І,...,І+І, где г, — степень /-го полинома, полученного при разложении 0i(X,j(E)). Утверждение 3.2. Пусть Е - несупервырожденная ЭК, определенная над q с инвариантом j O, 1728. Пусть 0i(x,j) = h]h2...hs есть разложение полинома 0i(XJ(E))eF(l[X\ В виде произведение неприводимых полиномов.
Причём достаточно проверить такие г, которые делят /+1 и удовлетворяют выражению (-1)( + ) В случае если / является «простым Элкиса», то полином F[ имеет два корня А, и р., которые являются собственным значением эндоморфизма Фро-бениуса по модулю /. Если А = д., то это случай для 2-го шага алгоритма Чуфа.
Для его построения используются следующие факты. Существуют ненулевые точки Рь V2&E[I], такие что фр(Рі)=[ A] Pi и фр(Рг)=[ и] Рг- Пусть Ci = (Pi), С2 = (Pi) и Сі Ф С2, где С = (Р) - циклическая подгруппа точек порядка /, такая что фр(С)=С. Степень полинома ( ) есть (/-1)/2. Сам алгоритм построение полинома приведен в работе [60]. Для нахождения t (mod /) с помощью метода, описанного в алгоритме Чуфа, достаточно вычислить только значение А, удовлетворяющее уравнению фр(Р)=[ А] Р, где Р = (х,у)єСД {О}.
Пустьh — Ух [х — х)+ Wx- VА.+\, приведя данное выражение к полиному от х - hx заменяя переменную у выражением для рассматриваемой ЭК, необходимо найти такое значение А, что gcd(hx, F/) l. Тогда t = A+q/A mod /. Важно отметить, что в том случае, если / — «простое Аткина», то мы мы вычисляем лишь возможные значения t (mod /), а если / - «простое Элкиса», то значение вычисляется точное значение t (mod Г). Для вычисления окончательного значения / может воспользоваться Китайской теоремой об остатках в сочетании с методом «больших и малых шагов» Шенкса [62], использующего тот факт, что с большой долей вероятности случайно взятая точка ЭК будет иметь искомый порядок.
В целом за счёт использования полиномов степени (/-1)/2 в случае, если / — «простое Элкиса», и полиномов степени /+1 в случае, если / - «простое Аткина», вместо используемых в алгоритме Чуфа полиномов степени (/2-1)/2 общая временная сложность алгоритма SEA есть 0(log6q), тогда как сложность алгоритма Чуфа оценивается как 0(log q).
Для алгоритма SEA в работе [50] предложено использование алгоритма «раннего обнаружения» нестойкой ЭК. Целью алгоритма является выделение ЭК с простым порядком (то есть где количество точек ЭК есть простое число). Алгоритм использует тот факт, что в процессе вычисления N — числа точек ЭК алгоритм SEA вычисляет значения Т (mod Д), где /$ — попарно простые числа. А так как N=q+l, то на і-м шаге алгоритма можно вычислить значение N (mod /j). При этом если N (mod /;) = 0, значит число N непростое, соответственно данная ЭК не обладает простым порядком и дальнейшие вычисления для данной ЭК не нужны и можно перейти к следующей случайной ЭК. В общем виде алгоритм имеет следующий вид.
Анализ количества перебираемых ЭК до нахождения искомой
Стратегия «случайного выбора» имеет вероятностный характер. То есть искомая ЭК может быть получена после произвольного числа попыток. Однако при многократном использовании стратегии можно проанализировать среднее значение параметров генерации. Табл. 4.2. содержит характеристики генерации ЭК с помощью данной стратегии.
При этом особое значение имеет среднее количество перебираемых ЭК для получения искомой и, соответственно, вероятность её получения. Так как во многом от значения этой вероятности зависит общее время генерации ЭК. Отметим, что полученные данные можно сравнить с теоретическими результатами использования формул, указанными в работе [39], для вероятности нахождения ЭК с числом точек N = кт, где к — «малый» делитель 7Y, а г — «большое» простое число.
Принимая во внимание тот факт, что как указано в работе [39] значение ср как правило лежит «ближе» к левой границе интервала, то есть 0.44, экспериментально полученное среднее значение перебираемых ЭК до нахождения искомой, равное 173, хорошо согласуется с теоретическими результатами, указанными в табл. 4.3. Это с одной стороны позволяет лишний раз убедиться в достоверности данных, полученных в результате использования стратегии «случайного выбора», а с другой стороны предоставляет возможность спрогнозировать результаты использования стратегии для различных длин числа р и ограничений на порядок циклической группы точек ЭК.
Кроме этого рассмотрим результаты эксперимента, который заключался в генерации криптографически стойкой ЭК с простым порядком группы точек с помощью разработанной стратегии «случайного выбора». В результате данного эксперимента сгенерировано 456 ЭК. При этом среднее количество перебираемых ЭК составило 394 ЭК. Используя формулу (4.1.), найдем теоретическое значение ECcount.
Для ср = 0,45 вычисленное значение ECcount в точности совпадает с экспериментально полученным. При том, что как указано в работе [39] корректное значение константы ср лежит «ближе» к левой границе интервала, полученное значение хорошо согласуется с теоретическими результатами, указанными в табл. 4.4.
Так же отметим, что в рамках описанного эксперимента для генерации ЭК с простым порядком группы точек был использовании оригинальный метод раннего обнаружения нестойкой ЭК в соответствии с работой [50]. Подробный сравнительный анализ методов обнаружения нестойкой ЭК дан ниже. Но первоначально отметим, что среднее число нестойких ЭК при генерации ЭК с простым порядком оказывается более чем в 2 раза больше среднего числа нестойких ЭК при генерации криптографически стойкой согласно п.п.1.3. Таким образом, при генерации криптографически стойкой ЭК согласно п.п.1.3 получаем вероятность её нахождения, равную 0,58 % при ве роятности нахождения криптографически стойкой ЭК с простым числом точек, равной 0,25%.
Среднее времени расчета числа точек произвольно взятой ЭК зависит от срабатывания алгоритма раннего обнаружения нестойкой ЭК. То есть если произвольно взятая ЭК не была отвергнута как нестойкая с помощью алгоритма раннего обнаружения, то для такой ЭК алгоритм SEA сработал до конца и число точек было рассчитано. В данном случае время расчета есть время работы алгоритма SEA. Иначе алгоритм SEA был прерван на j-м шаге, и время расчета есть промежуток времени от начала работы алгоритма SEA до его прерывания. При этом можно оценить вероятность прерывания алгоритма на j-м шаге. Где j-ый шаг ассоциируем с расчетом N (mod /,) в процессе алгоритма SEA.
Применив выражение (4.7) к формуле (4.4), вычислим значения Vt для случая генерации криптографически стойкой ЭК с простым числом точек. При этом на каждом z -м шаге, то есть для любого из указанных выше /,-, может произойти прерывание алгоритма SEA. Кроме этого вычислим weakEC-counti - количество ЭК, для которых происходит прерывание на і-м шаге при переборе ЭК в процессе поиска искомой для стратегии «случайного выбора».
Вычисленные данные показывают, что общее время, необходимое для поиска криптографически стойкой ЭК, во многом зависит от числа ЭК, для которых алгоритм SEA выполняет полный расчет, то есть без срабатывания алгоритма раннего обнаружения нестойкой ЭК. А именно общее вычисленное время Е allECtime имеет значение 2446,5 с. при времени, затрачиваемом на полный расчет 1938,7 с, то есть allECtimefuuSEA составляет 79% от общего времени поиска ЭК. Отметим, что в результате эксперимента по поиску криптографически стойкой ЭК с простым числом точек экспериментально было получено среднее количество ЭК, для которых был произведен полный расчет по алгоритму SEA, которое составило 22 кривых. Данное значении хорошо согласуется с вычисленным и равным в среднем 26 ЭК. При этом в результате указанного эксперимента среднее время генерации составило 2442 с. при теоретически вычисленном выше 2454,6 с. Некоторые отличие между теоретическими данными и экспериментальными можно объяснить тем, что, во-первых, формула (4.6) даёт лишь сравнение, справедливое для вероятности Р,-, а, во-вторых, вытекающая из сравнения (4.6) формула (4.7) носит приблизительный характер с учетом принятых допущений.
Приведем результаты описанных выше вычислений для случая поиска криптографически стойкой ЭК с г 2254, то есть для ЭК, содержащихся в базе криптографически стойких ЭК. При этом согласно используемой стратегии раннего обнаружения нестойкой ЭК по п.п.3.1.4 число j-ых шагов, которые ассоциируем с расчетом N (mod /,), на которых алгоритм SEA может быть прерван, сокращается. А именно для 1 = 2 если N (mod 2) Ф О, то алгоритм не будет прерван, однако для / = 3 если N (mod 3) Ф О и при этом на предыдущем шаге 7Y (mod 2) Ф О, то имеем N (mod 6) ф О, а в этом случае для р 2 полу-чаем значение r 2 , то есть такая ЭК не является криптографически стойкой, и алгоритм расчета точек SEA будет прерван. Таким образом, на 0-м шаге имеем вероятность прерывания алгоритма, равную вероятности делимости N на 6, вычисляемую по формуле .
