Разработка новых кодов в ранговой метрике и криптосистем с открытым ключом тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат физико-математических наук Кшевецкий, Александр Сергеевич

• Кшевецкий, Александр Сергеевич
• кандидат физико-математических наук
• 2007

Оглавление диссертации кандидат физико-математических наук Кшевецкий, Александр Сергеевич

Введение

1 Ранговые коды

1.1 Стандартные известные конструкции ранговых кодов

1.1.1 Введение.

1.1.2 Конструкция.

1.1.3 Алгоритмы кодирования и декодирования

1.1.4 Приводимые ранговые коды.

1.1.5 Симметричные ранговые (п, 1,п)-коды

1.2 Разработка ранговых кодов новой конструкции

1.2.1 Введение.

1.2.2 Конструкция.

1.2.3 Взаимосвязь с обычными ранговыми кодами

1.2.4 Алгоритмы кодирования и декодирования

1.3 Построение декодирования по информационным совокупностям

1.3.1 Введение.

1.3.2 Информационные совокупности для матричных кодов.

1.3.3 Декодирование для ранговых кодов.

Введение диссертации (часть автореферата) на тему «Разработка новых кодов в ранговой метрике и криптосистем с открытым ключом»

2.2 Оценка стойкости криптосистемы ГПТ.59

2.2.1 Описание криптосистемы ГПТ со строковым и столбцевым скремблерами и шумовой матрицей 60

2.2.2 Анализ представлений открытого ключа . 61

2.2.3 Построение атаки.65

2.2.4 Выбор стойких параметров.73

2.3 Разработка криптосистемы с ошибками высокого веса 75

2.3.1 Криптосистема.75

2.3.2 Криптоанализ.79

2.3.3 Пример.82

2.4 Выводы.83

3 Криптосистемы в мнимом квадратичном поле 85

3.1 Введение.85

3.2 Математические основы.88

3.3 Известные криптосистемы.104

3.3.1 Аналоги схем Диффи-Хеллмана, RSA и Эль-Гамаля.104

3.3.2 NICE-X с квадратичным временем расшифрования .105

3.4 Реализация и анализ криптосистемы NICE-X.109

3.4.1 Описание реализации криптосистемы.109

3.4.2 Достоинства и недостатки.111

3.5 Новая модификация криптосистемы NICE-X.111

3.5.1 Оптимизация шифрования .111

3.5.2 Генерирование стойких ключей.ИЗ

3.5.3 Программная реализация.114

3.5.4 Замечания по цифровой подписи.116

3.6 Выводы.118

Заключение 119

Литература 121

Введение

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

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

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

Матричные коды в ранговой метрике [1] при передаче сигнала одновременно по нескольким частотам хорошо подходят для исправления ошибок, вызванными импульсными широкополосными или постоянными узкополосными шумами. Ошибки, обусловленные такими шумами, имеют более низкий вес в ранговой метрике, чем в метрике Хэмминга. Ранговые коды были предложены в 1985 г. Расширение классов кодов и создание новых кодов является важной задачей теорией кодирования. Новые коды могут обладать лучшей корректирующей способностью и быть более эффективными в частных применениях.

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

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

Особый интерес представляют криптосистемы с открытым ключом, построенные на линейных кодах и основанные на трудности решения задачи декодирования сообщения с добавленными искусственными ошибками и при неизвестных порождающей/проверочной матриц кода. Вместе с искусственно добавленными ошибками они могут исправлять и обычные ошибки, возникающие при передаче информации. Открытый ключ может быть построен либо на порождающей матрице (криптосистема типа Мак-Элиса), либо на проверочной матрице (криптосистема типа Нидер-райтера). В 1991 году была опубликована криптосистема с открытым ключом, основанная на ранговых кодах (Габидулин, Парамонов, Третьяков, 1991, [22]). Она получила название ГПТ по фамилиям авторов в русскоязычной литературе и ОРТ в англоязычной. По сравнению с другими криптосистемами, основанными на линейных кодах, ее преимуществом является маленькая длина открытого ключа и, как следствие, высокая скорость шифрования/расшифрования из-за быстрого алгоритма декодирования. К сожалению, для исходных заявленных параметров криптосистема ГПТ была взломана Гибсоном [23,24]. Одновременно, Гибсон показал, как выбирать параметры криптосистемы. В дальнейшем были предложены модификации, использующие столбцевой и строковый скремблеры [25] и приводимые ранговые коды [6]. В 2005 г. Овербек предложил расширенную атаку Гибсона в [27,28] для исходного варианта ГПТ.

В практических приложениях число выполняемых шифрований данных существенно меньше числа выполняемых расшифрований. Интерес представляют криптосистемы, имеющие быстрое расшифрование. Криптосистема ШСЕ-Х [48,49] в отличие от стандартных криптосистем типа RSA, Эль-Гамаля с кубическим временем расшифрования по битовой длине параметров характеризуется квадратичным временем расшифрования. Криптосистема построена в мнимом квадратичном поле.

Актуальность темы исследования.

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

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

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

Целью настоящего исследования является:

1. построение новых ранговых кодов и новых алгоритмов декодирования,

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

В соответствии с поставленной целью были определены следующие задачи и вопросы.

1. Расширение класса кодов в ранговой метрике и построение новых алгоритмов декодирования.

2. Проведение криптоанализа криптосистем с открытым ключом, основанных на ранговых кодах, и построение криптосистем с улучшенными характеристиками.

3. Криптоанализ и анализ эффективности криптосистем с открытым ключом, построенных в мнимом квадратичном поле, имеющих быстрое расшифрование.

Методами исследования для решения поставленных задач являются методы дискретной математики, алгебры, теории информации, теории вероятностей, линейной алгебры, комбинаторики.

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

1. Для построения ранговых кодов в качестве порождающей матрицы выбрана (к х п) матрица Фробениуса над конечным полем вида Ц^ГИСо'.'.'Г-р Ш е с константой т, gcd(ra, ЛГ) = 1. Обычная матрица Фробениуса определяется как \\iZo k-i- Использование матрицы нового вида как порождающей матрицы линейного рангового (п, к, с?)-кода позволило обобщить и расширить единственную известную конструкцию ранговых кодов 1985 г. с максимальным ранговым расстоянием.

2. Сделано предположение, что степени (п х п)-матриц над полем СгР(2), порождающих поле С^(2П), имеют равномерное распределение элементов над полем (?.Р(2). На основе гипотезы построен метод исправления ошибок стирания веса п для линейных ранговых (п, 1,п)-кодов алгоритмом декодирования по информационным совокупностям. Проведенное моделирование подтвердило гипотезу и показало эффективность алгоритма декодирования.

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

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

5. Разработан метод быстрого генерирования псевдослучайного целого примитивного идеала мнимого квадратичного поля. Использование метода в алгоритме шифрования криптосистемы ШСЕ-Х позволило снизить асимптотическую битовую сложность шифрования с четвертой степени до кубической по битовой длине параметров.

Теоретическая и практическая ценность.

Для коррекции ошибок в каналах с многолучевым распространением используются матричные коды. Матричные коды, построенные в ранговой метрике, успешно исправляют ошибки, вызванные импульсными шумами и эффектом замирания. С 1985 г. была известна только одна конструкция ранговых кодов с максимальным ранговым расстоянием и быстрым алгоритмом декодирования. Предложенные новые ранговые МРР коды расширяют класс известных МРР кодов с быстрым алгоритмом декодирования. Использование новых МРР кодов немного повышает стойкость криптосистем на ранговых кодах с открытым ключом. Декодирование по информационным совокупностям для ранговых кодов представляет интерес для исправления ошибок за пределами корректирующей способности кода.

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

Апробация работы.

Результаты диссертационной работы докладывались на российских и международных конференциях:

• International Symposium on Information Theory, ISIT, Adelaide,

Australia, 2005.

• International Symposium on Coding Theory and Applications, ISCTA, Ambleside, UK, 2005.

• Algebraic and Combinatorial Coding Theory, ACCT, Kranevo, Bulguria, 2004.

• International Symposium on Coding Theory and Applications, ISCTA, Ambleside, UK, 2003.

• Algebraic and Combinatorial Coding Theory, ACCT, Tsarskoe Selo, Russia, 2002.

• XLIX, XLVIII, XLVII, XLVI, XLIV ежегодных научных конференциях Московского физико-технического института, Москва-Долгопрудный, 2001-2006.

Основные результаты диссертации неоднократно обсуждались и были одобрены на научных семинарах:

• на научном семинаре в School of Information Science and Technology, Southwest Jiatong University, Китай, 2006 г.;

• на научных семинарах по теории кодирования Института Проблем Передачи Информации РАН, 2005 г.;

• на научных семинарах кафедры радиотехники Московского физико-технического института (ГУ) 2002-2007 гг.;

• на научном семинаре в Department of Information Technology, Lund University, Швеция, 2002 г.

Публикации. По теме диссертации опубликовано 12 работ, из них 1 статья в журнале из списка ВАК, 1 статья в рецензируемом сборнике научных статей МФТИ, 5 статей в сборниках трудов рецензируемых международных научных конференций, 5 докладов в Трудах научных конференций МФТИ.

Научные положения, выносимые на защиту.

1. Линейные ранговые (тг, fc, d = п—к+1) коды новой конструкции с максимальным ранговым расстоянием.

2. Декодирование ранговых кодов для плохого канала с мощными узкополосными и импульсными широкополосными шумами по методу информационных совокупностей.

3. Условия существования и оценка сложности полиномиальных и экспоненциальных атак на разные варианты криптосистемы ГПТ на основе ранговых кодов в зависимости от параметров криптосистемы.

4. Криптосистема на основе ранговых кодов с искусственной ошибкой высокого веса и наименьшей длиной открытого ключа.

5. Ускорение шифрования криптосистемы с открытым ключом ШСЕ-Х, построенной в мнимом квадратичном поле, и выбор более безопасных параметров схемы.

Содержание работы

Первая глава содержит конструкции ранговых кодов и алгоритм кодирования/декодирования. Вначале описываются известные конструкции ранговых кодов вместе с быстрыми алгоритмами декодирования. Затем приводится новая конструкция ранговых кодов, алгоритм декодирования и обсуждается отличие новой конструкции от ранее известной. В конце главы приводятся алгоритмы декодирования по информационным совокупностям для ранговых кодов для исправления ошибок стирания за пределами кодового расстояния и результаты моделирования исправления ошибок стираний методом информационных совокупностей. Полученные результаты, изложенные в первой главе, опубликованы в [2,3,4,5].

Вторая глава описывает криптосистемы с открытым ключом на ранговых кодах. Глава начинается с оценки криптостойкости криптосистем типа ГПТ. Показывается эквивалентности разных форм

ГПТ одной форме открытого ключа. Детально разрабатывается атака на общую форму открытого ключа на основе атаки Овербека для исходной ГПТ. Оценивается сложность атаки в зависимости от параметров криптосистемы. Предлагается способ для создания стойких параметров. Далее разрабатывается новая криптосистема на ранговых кодах, в которой искусственная ошибка имеет вес не меньше кодового расстояния. Глава заканчивается сравнением новой криптосистемы и ранее известных. Полученные результаты, изложенные во второй главе, опубликованы в [18,19,20,21].

Третья глава содержит описания криптосистем с открытым ключом с быстрым расшифрованием, построенных в мнимых квадратичных полях. Вначале даются необходимые математические основы, затем приводятся опубликованные криптосистемы. Производится анализ свойств криптосистемы, приводится модификация криптосистемы с ускорением шифрования. Полученные результаты, изложенные в третьей главе, опубликованы в [29,30,31,32].

В заключении сформулированы основные результаты диссертационной работы.

Заключение диссертации по теме «Теоретические основы информатики», Кшевецкий, Александр Сергеевич

Основные результаты, полученные в данной работе.

1. Разработаны новые линейные ранговые коды с максимальным ранговым расстоянием вместе с алгоритмом быстрого декодирования. Коды являются (п, к, (I = п — к + 1) кодами с максимальным ранговым расстоянием на границе Синглтона. Новые коды являются обобщением единственных ранее известных ранговых кодов 1985 г.

2. Построен алгоритм декодирования ранговых (п, 1, п)-кодов для плохого канала с мощными узкополосными и импульсными широкополосными шумами, вызывающими стирания строк и столбцов в передаваемой кодовой матрице. Найдена доля информационных совокупностей - 29%. Проведено моделирование стираний строк и столбцов и показана возможность декодирования ошибок веса п с шансами 80-100%.

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

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

5. Построена модификация криптосистемы ШСЕ-Х с открытым ключом, построенной в мнимом квадратичном поле с ускоренным шифрованием. Исследована стойкость схемы. Предложен способ выбора более безопасных ключей.

Заключение

Результаты, выносимые на защиту

Список литературы диссертационного исследования кандидат физико-математических наук Кшевецкий, Александр Сергеевич, 2007 год

1. Габидулин Э. М. Теория кодов с максимальным ранговым расстоянием // Проблемы передачи информации. 1985, т. 21, N 1, с. 3-14.

2. Kshevetskiy A., Gabidulin М. The New Construction of Rank Codes // Proc. of IEEE International Symposium on Information Theory (ISIT'2005). 2005, pp. 2105-2108.

3. Кшевецкий А. С., Габидулин Э. M. Декодирование ранговых кодов новой конструкции // В сб. научных трудов «Некоторые проблемы фундаментальной и прикладной математики и их приложениях в задачах физики». М.: МФТИ, 2005, с. 53-61.

4. Кшевецкий А. С. Построение новых ранговых кодов с максимальным ранговым расстоянием // Труды XLVII научной конференции МФТИ: Современные проблемы фундаментальных и прикладных наук. Москва-Долгопрудный. 2004, ч. 1, с. 9-10.

5. A. Kshevetskiy. Information set decoding for rank codes // Proc. of the Ninth International Workshop "Algebraic and Combinatorial Coding Theory" (ACCT'2004). 2004, pp. 254-259.

6. E. M. Gabidulin, A. V. Ourivski, B. Honary, B. Ammar. Reducible Rank Codes and Their Applications to Cryptography // IEEE Transactions on Information Theory. 2003, 49(12), pp. 3289-3293.

7. E. M. Gabidulin, P. Loidreau. Subfield subcodes of maximal rank distance codes // Proc. of the 7-th Int. Workshop on Algebraic and Combinatorial Coding Theory ACCT'2000, Bansko, Bulgaria, . June 2000. pp. 151-156.

8. E. M. Gabidulin, A. V. Paramonov, О. V. Tretjakov. Rank Errors and Rank Erasures Correction // Proceedings of the 4th International Colloquium on Coding Theory. 1992, Armenia, pp. 11-19.

9. E. M. Gabidulin, N. I. Pilipchuk. Transposed Rank Codes Based on Symmetric Matrices // Proc. of the WCC'2003. March 2003, Versailles (France), pp. 203-211.

10. Э. M. Габидулин, H. И. Пилипчук. Симметричные ранговые коды и применение // Проблемы передачи информации. 2004, № 2, с. 3-18.

11. И. E. M. Gabidulin, N. I. Pilipchuk. Symmetric matrices and codes correcting rank errors beyond the ^J bound // Discrete Applied Mathematic. 2006, 154, pp. 305-312.

12. E. Prange. The use of information sets in decoding cyclic codes // IRE Trans. Inform. Theory. 1962, vol. IT-8, pp. S5-S9.

13. Coffey, J. T. and Goodman, R. M. The complexity of information set decoding // IEEE Transactions on Information Theory. 1990, vol. 36, pp. 1031-1037.

14. E. M. Gabidulin. A Class of Two-Dimensional Codes Correcting Lattice-Pattern Errors // Proceedings of the 2nd International Symposium on Information Theory. 1971, Moscow-Yerevan, pp. 4447.

15. Э. M. Габидулин, В. И. Коржик. Коды исправляющие ошибки решетчатой конфигурации // Известия ВУЗов МВССО СССР Радиоэлектроника. 1972, т. 15, No. 4, с. 492-498.

16. E. М. Gabidulin. A Fast Matrix Decoding Algorithm For Rank

17. Error-Correcting Codes // Lecture Notes in Computer Science No. 573. Eds G. Cohen, S. Litsyn, A. Lobstein, G. Zemor, Algebraic coding. Springer-Verlag, Berlin, 1992, pp. 126-132.

18. MacWilliams F. J., Sloane N. J. A. The Theory of Error Correcting Codes // Amsterdam: North Holland Press, 8th ed, 1993.

19. Кшевецкий А. С. Уменьшение размера открытого ключа в криптосистемах на линейных ранговых кодах // Безопасность информационных технологий (БИТ). 2006, т. 3, с. 72-76.

20. Кшевецкий А. С. Выбор стойких ключей для криптосистем на ранговых кодах // Труды XLIX научной конференции МФТИ: Современные проблемы фундаментальных и прикладных наук. Москва-Долгопрудный. 2006, ч. 1, с. 8-8.

21. A. Kshevetskiy, Е. Gabidulin. High-weight errors in reducible rank codes // Proc. of the 8th International Symposium on Communication Theory к Applications (ISCTA'2005). 2005, pp. 71-76.

22. Кшевецкий А. С. Ошибки высокого веса в криптосистемах, основанных на ранговых кодах // Труды XLVIII научной конференции МФТИ: Современные проблемы фундаментальных и прикладных наук. Москва-Долгопрудный. 2005, ч. 1, с. 11-12.

23. Е. М. Gabidulin, А. V. Paramonov, О. V. Tretjakov. Ideals over a non-commutative ring and their application in cryptology // Advances in Cryptology EUROCRYPT'91. LNCS 547, D. W. Davies, Ed., Springer-Verlag. 1991, pp. 482-489.

24. J. K. Gibson. Severely denting the Gabidulin version of the

25. McEliece public key cryptosystem // Designs, Codes and Cryptography. 1995, 6(1), pp. 37-45.

26. J. K. Gibson. The security of the Gabidulin public-key cryptosystem, in: U. M. Maurer, ed. // Advances in Cryptology EUROCRYPT'96, LNCS 1070. 1996, pp. 212-223.

27. Alexei V. Ourivski, Ernst M. Gabidulin. Column Scrambler for the GPT Cryptosystem // Discrete Applied Mathematics 128(1). 2003, pp. 207-221.

28. А. Уривский, Т. Йоханссон. Новые методы для декодирования кодов в ранговой метрике и их применение в криптографии // Проблемы передачи информации. 2002, т. 38(3), с. 287-296.

29. R. Overbeck. A new structural attack for GPT and variants //In Proc. of Mycrypt'2005, vol. 3715 of LNCS. Springer-Verlag, 2005, pp. 50-63.

30. R. Overbeck. Extending Gibson's attacks on the GPT cryptosystem // In Proc. of. WCC 2005, volume 3969 of LNCS. Springer Verlag, 2006, pp. 178-188.

31. A. Kshevetskiy. Modification of the public-key cryptosystem NICE-X // Proc. of the Seventh International Symposium on Communications Theory & Applications (ISCTA'03). 2003, pp. 210-214.

32. Кшевецкий А. С. Криптосистемы с открытым ключом, построенные в квадратичных порядках // Труды XLVI научной конференции МФТИ: Современные проблемы фундаментальных и прикладных наук. Москва-Долгопрудный. 2003, ч. 1, с. 8-8.

33. A. Kshevetskiy. Several properties of public-key cryptosystemsbased on quadratic orders // Proc. of the Eighth International Workshop "Algebraic and Combinatorial Coding Theory" (ACCT'2002). 2002, pp. 172-175.

34. I. Biehl, S. Paulus, Т. Takagi. Efficient Undeniable Signature Schemes based on Ideal Arithmetic in Quadratic Orders // Designs, Codes and Cryptography archive. 2004, Volume 31, Issue 2, pp. 99123.

35. H. Cohen. A Course in Computational Algebraic Number Theory // Series: Graduate Texts in Mathematics. 2000, Volume 138.

36. H. Cohen, and H. W. Lenstra, Jr. Heuristics on class groups // In Number Theory, vol. 1052 of Lecture Notes in Mathematics. Springer-Verlag, 1984.

37. P. Ebinger, E. Teske. Factoring N = pq2 with the Elliptic Curve Method // ANTS 2002, LNCS 2369.

38. S. Hamdy, B. Moller. Security of Crytosystems Based on Class Groups of Imaginary Quadratic Orders // ASIACRYPT 2000, LNCS 1976. 2000.

39. D. Huhnlein. Faster Generation of NICE-Schnorr-Type Signatures // Progress in Cryptology CT-RSA 2001, LNCS 2020. 2001.

40. D. Hiihlein, J. Merkle. An efficient NICE-Schnorr-type signature scheme // Proceedings of PKC 2000, LNCS 1751. 2000.

41. M. Hartmann, S. Paulus and T. Takagi. NICE New ideal coset encryption // CHES, LNCS 1717. 1999.

42. E. Jaulmes, A. Joux. A NICE Cryptanalysis // EUROCRYPT 2000, LNCS 1807. 2000.

43. M. Joye, P. Paillier, S. Vaudenay. Efficient Generation of Prime Numbers // CHES 2000, LNCS 1965. 2000.

44. P. Karu, J. Loikkanen. Practical Comparison of Fast Public-Key Cryptosystems / / Telecommunications Software and Multimedia Lab. at Helsinki Univ.of Technology. 2001, http://www.tml.hut.fi/Opinnot/Tik-110.501/2000/papers.html.

45. A. K. Lenstra, and E. R. Verheul. Selecting cryptographic keysizes In Practice and Theory in Public Key Cryptography // PKCS 2000, LNCS 1751. 2000.

46. R. Peralta, E. Okamoto. Faster Factoring of Integers of a Special Form // IEICE Transactions on Fundamentals of Electronics, Communications, and Computer Sciences. 1996, v. E79-A, n.4.

47. H. Reisel. Prime numbers and computer methods for factorization, 2nd ed. // Birkhauser, Boston, 1994.

48. D. Shanks. On Gauss and composition I, II in R. A. Mollin, (ed.) // Proc. NATO ASI on Number Theory and Applications. Kluwer Academic, Dordrecht. 1989, pp. 163-179.

49. Paulus S., Takagi T. A new public-key cryptosystem over a quadratic order with quadratic decryption time // Journal of Cryptography. 2000, vol. 13, no2, pp. 263-272.

50. J. Buchmann, K. Sakurai, T. Takagi. An IND-CCA2 Public-Key Cryptosystem with Fast Decryption // ICISC'01, LNCS 2288. 2002.

51. D. Hühlein, M. J. Jacobson, Jr., S. Paulus. A cryptosystem based on non-maximal imaginary quadratic orders with fast decryption // Advances in Cryptology EUROCRYPT'98, LNCS 1403. Spriger-Verlag, Berlin. 1998, pp. 294-307.

52. J. Buchmann and H. C. Williams. Quadratic Fields And Cryptography // London Mathematical Society Lecture Note Series 154, Cambridge University Press, Cambridge. 1990, pp. 9-26.

53. Buchmann J., Dullmann S., Williams H. On the complexity and efficiency of a new key exchange system // Advances in Cryptology EUROCRYPT'89, LNCS 434, Springer-Verlag, Berlin. 1990, pp. 597-616.

54. J. Buchmann and H. C. Williams. A key exchange system based on imaginary quadratic fields // Journal of Cryptology. 1988, vol. 1, pp. 107-118.

55. Jacobson M.J. Computing discrete logarithms in quadratic orders // Journal of Cryptography. 2000, v. 13.

56. Hamdy S., Möller B. Security of Cryptosystems Based on Class Groups of Imaginary Quadratic Fields // T. Okamoto (Ed.):

57. Advances in Cryptology, ASIACRYPT 2000, Springer-Verlag LNCS 1976. 2000, pp. 234-247.

58. Ван дер Варден Б. Jl. Алгебра // Москва «Наука», 1979.

59. Айерлэнд К., Роузен М. Классическое введение в современную теорию чисел // 1987.

60. Гекке Э. Лекции по теории алгебраических чисел // Пер. с немецкого Ольшанского Г.И., Райкова Д.А. 1940.

61. D. А. Сох. Primes of the form x2 + ny2 // John Wiley & Songs, Inc.

62. A. Menezes, P. van Ooscort and S. Vanstone. Handbook of Applied cryptography // CRC Press, 1996.

63. Schneier B. Applied cryptography, 2nd edition // John Wiley & Songs, 1996.

64. Коблиц H. Курс теории чисел и криптографии // Научное иза-тельство «ТВП», Москва, 2001.

65. Брассар Ж. Современная криптология. Основы // 1988.

66. Ростовцев А. Алгебраические основы криптографии // СПб.: НПО «Мир и семья», ООО «Интерлайн», 2000.