Содержание к диссертации
Введение
1 Ранговые коды 16
1.1 Стандартные известные конструкции ранговых кодов 16
1.1.1 Введение 16
1.1.2 Конструкция 17
1.1.3 Алгоритмы кодирования и декодирования . 19
1.1.4 Приводимые ранговые коды 23
1.1.5 Симметричные ранговые (п, 1,п)-коды . 26
1.2 Разработка ранговых кодов новой конструкции . 28
1.2.1 Введение 28
1.2.2 Конструкция 29
1.2.3 Взаимосвязь с обычными ранговыми кодами . 31
1.2.4 Алгоритмы кодирования и декодирования . 33
1.3 Построение декодирования по информационным совокупностям 38
1.3.1 Введение 38
1.3.2 Информационные совокупности для матричных кодов 41
1.3.3 Декодирование для ранговых кодов 42
1.3.4 Приложение к симметричным ранговым кодам и результаты моделирования 46
1.3.5 Результаты моделирования стираний линиями 48
1.3.6 Оценка числа оставшихся элементов после стирания линиями 51
1.3.7 Максимальное число стертых линий, позволяющих декодирование 53
1.3.8 Выводы 53
2 Криптосистемы с открытым ключом на ранговых кодах 57
2.1 Введение 57
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
Литература
- Алгоритмы кодирования и декодирования
- Описание криптосистемы ГПТ со строковым и столбцевым скремблерами и шумовой матрицей
- Аналоги схем Диффи-Хеллмана, RSA и Эль-Гамаля
- Оптимизация шифрования
Введение к работе
При передаче информации по каналам связи можно выделить две фундаментальные проблемы - защиту передаваемой информации от шумов и защиту информации от несанкционированного доступа. Исторически сложилось, что данные проблемы решаются независимо. Вначале информация защищается от несанкционированного доступа, затем используется защита от шумов.
Защита от шумов обеспечивается помехоустойчивым избыточным кодированием. При декодировании добавленные шумы могут быть исправлены в количестве определяемом избыточностью кодирования. При алгебраическом дискретном кодировании информации вводится дискретное метрическое пространство и шумы измеряются в виде расстояния в метрическом пространстве.
Наиболее распространены помехоустойчивые коды, построенные в метрике Хэмминга, например, коды Рида-Соломона. Одни и те же шумы в кодах с разными метриками могут быть исправлены в разных количествах из-за разного веса ошибки. Особый интерес представляют метрики, в которых часть физических шумов имеет низкий вес.
Матричные коды в ранговой метрике [1] при передаче сигнала одновременно по нескольким частотам хорошо подходят для исправ-
ления ошибок, вызванными импульсными широкополосными или постоянными узкополосными шумами. Ошибки, обусловленные такими шумами, имеют более низкий вес в ранговой метрике, чем в метрике Хэмминга. Ранговые коды были предложены в 1985 г. Расширение классов кодов и создание новых кодов является важной задачей теорией кодирования. Новые коды могут обладать лучшей корректирующей способностью и быть более эффективными в частных применениях.
Теоретическими аспектами защиты информации от несанкционированного доступа занимается криптография. Современные криптосистемы делятся на два типа: симметричные (ключи шифрования и расшифрования - секретные) и с открытым ключом (один ключ - секретный, второй - публично доступный). Симметричные криптосистемы используются для шифрования большого объема данных из-за высокой скорости работы. В основе работы симметричных криптосистем, как правило, находится принцип перемешивания информации, скрытие статистики.
Криптосистемы с открытым ключом используются для электронных цифровых подписей (ЭЦП) и протоколов аутентификации и распределения ключей. Криптосистемы с открытым ключом оперируют с математическими объектами в дискретном пространстве, например, в группе или поле. Они существенно медленнее симметричных криптосистем и поэтому не используются для шифрования большого объема данных. В то же время они более универсальны и более защищены, чем симметричные криптосистемы, с позиции, что один из ключей публичный, а публичный ключ не требует защиты и может использоваться всеми пользователями.
Особый интерес представляют криптосистемы с открытым ключом, построенные на линейных кодах и основанные на трудности решения задачи декодирования сообщения с добавленными искусственными ошибками и при неизвестных порождающей/проверочной матриц кода. Вместе с искусственно добавленными ошибками они могут исправлять и обычные ошибки, возникающие при передаче информации. Открытый ключ может быть построен либо на порождающей матрице (криптосистема типа Мак-Элиса), либо на проверочной матрице (криптосистема типа Нидер-райтера). В 1991 году была опубликована криптосистема с открытым ключом, основанная на ранговых кодах (Габидулин, Парамонов, Третьяков, 1991, [22]). Она получила название ГПТ по фамилиям авторов в русскоязычной литературе и GPT в англоязычной. По сравнению с другими криптосистемами, основанными на линейных кодах, ее преимуществом является маленькая длина открытого ключа и, как следствие, высокая скорость шифрования/расшифрования из-за быстрого алгоритма декодирования. К сожалению, для исходных заявленных параметров криптосистема ГПТ была взломана Гибсоном [23,24]. Одновременно, Гибсон показал, как выбирать параметры криптосистемы. В дальнейшем были предложены модификации, использующие столбцевой и строковый скремблеры [25] и приводимые ранговые коды [6]. В 2005 г. Овербек предложил расширенную атаку Гибсона в [27,28] для исходного варианта ГПТ.
В практических приложениях число выполняемых шифрований данных существенно меньше числа выполняемых расшифрований. Интерес представляют криптосистемы, имеющие быстрое расшифрование. Криптосистема NICE-X [48,49] в отличие от стандартных
криптосистем типа RSA, Эль-Гамаля с кубическим временем расшифрования по битовой длине параметров характеризуется квадратичным временем расшифрования. Криптосистема построена в мнимом квадратичном поле.
Актуальность темы исследования.
Расширение классов кодов и создание новых кодов является важной задачей теорией кодирования. Во-первых, новые коды могут обладать лучшей корректирующей способностью. Во-вторых, новые коды могут быть более эффективными в частных применениях. С 1985 г. известна только одна конструкция ранговых кодов. Важной задачей теории ранговых кодов является расширение класса ранговых кодов, исследование их свойств и построение новых алгоритмов декодирования. При наличии в канале сильных шумов становятся актуальными методы декодирования за пределами корректирующей способности кода.
Важной задачей является построение единых методов совместных помехоустойчивого кодирования и защиты от несанкционированного доступа. Проблема является особенно актуальной для мобильных устройств связи, в которых уменьшение числа вычислительных модулей означает большее энергосбережение.
Актуальной задачей является построение и анализ криптосистем с открытым ключом, обладающих высокой скоростью шифрования/расшифрования с тем, чтобы использовать криптосистемы с открытым ключом для шифрования большого объема данных. Особенно важно обеспечить высокую скорость расшифрования, так как данные шифруются реже, чем расшифруются.
Целью настоящего исследования является:
построение новых ранговых кодов и новых алгоритмов декодирования,
построение и анализ нетрадиционных криптосистем с открытым ключом:
на основе кодов в ранговой метрике из-за возможности обеспечивать одновременную защиту от помех и несанкционированного доступа при передаче данных,
в мнимом квадратичном поле из-за быстрой операции расшифрования.
В соответствии с поставленной целью были определены следующие задачи и вопросы.
Расширение класса кодов в ранговой метрике и построение новых алгоритмов декодирования.
Проведение криптоанализа криптосистем с открытым ключом, основанных на ранговых кодах, и построение криптосистем с улучшенными характеристиками.
Криптоанализ и анализ эффективности криптосистем с открытым ключом, построенных в мнимом квадратичном поле, имеющих быстрое расшифрование.
Методами исследования для решения поставленных задач являются методы дискретной математики, алгебры, теории информации, теории вероятностей, линейной алгебры, комбинаторики.
Научная новизна результатов, полученных в диссертации, заключается в том, что в ней впервые предложено следующее.
Для построения ранговых кодов в качестве порождающей матрицы выбрана (к х п) матрица Фробениуса над конечным полем GF{qN) вида Wgf^lTk-v Ш Є GF(qN) с константой m, gcd(m, N) = 1. Обычная матрица Фробениуса определяется как \\д? ||Г0 _1- Использование матрицы нового вида как порождающей матрицы линейного рангового (п, А;, <і)-кода позволило обобщить и расширить единственную известную конструкцию ранговых кодов 1985 г. с максимальным ранговым расстоянием.
Сделано предположение, что степени (n х п)-матриц над полем GF{2), порождающих поле GF(2n), имеют равномерное распределение элементов над полем GF(2). На основе гипотезы построен метод исправления ошибок стирания веса п для линейных ранговых (п, 1,п)-кодов алгоритмом декодирования по информационным совокупностям. Проведенное моделирование подтвердило гипотезу и показало эффективность алгоритма декодирования.
Показана эквивалентность разных вариантов криптосистемы ГПТ на основе ранговых кодов одной общей форме открытого ключа. Проведенный криптоанализ общей формы криптосистемы, а не исходных вариантов, позволил найти условия существования и зависимость полиномиальных и экспоненциальных атак относительно параметров криптосистемы.
Предложен метод выбора столбцевого скремблера специально-
го вида для криптосистемы на приводимых ранговых кодах. Что позволило создать криптосистему на линейных кодах с искусственной ошибкой веса большего, чем корректирующая способность кода. Одновременно криптосистема может исправлять ошибки, возникающие при передаче по каналу с шумами.
5. Разработан метод быстрого генерирования псевдослучайного целого примитивного идеала мнимого квадратичного поля. Использование метода в алгоритме шифрования криптосистемы NICE-X позволило снизить асимптотическую битовую сложность шифрования с четвертой степени до кубической по битовой длине параметров.
Теоретическая и практическая ценность.
Для коррекции ошибок в каналах с многолучевым распространением используются матричные коды. Матричные коды, построенные в ранговой метрике, успешно исправляют ошибки, вызванные импульсными шумами и эффектом замирания. С 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 докладов в Трудах научных конференций МФТИ.
Научные положения, выносимые на защиту.
Линейные ранговые (тг, fc, d = п—к+\) коды новой конструкции с максимальным ранговым расстоянием.
Декодирование ранговых кодов для плохого канала с мощными узкополосными и импульсными широкополосными шумами по методу информационных совокупностей.
Условия существования и оценка сложности полиномиальных и экспоненциальных атак на разные варианты криптосистемы ГПТ на основе ранговых кодов в зависимости от параметров криптосистемы.
Криптосистема на основе ранговых кодов с искусственной ошибкой высокого веса и наименьшей длиной открытого ключа.
Ускорение шифрования криптосистемы с открытым ключом NICE-X, построенной в мнимом квадратичном поле, и выбор более безопасных параметров схемы.
Содержание работы
Первая глава содержит конструкции ранговых кодов и алгоритм кодирования/декодирования. Вначале описываются известные конструкции ранговых кодов вместе с быстрыми алгоритмами декодирования. Затем приводится новая конструкция ранговых кодов, алгоритм декодирования и обсуждается отличие новой конструкции от ранее известной. В конце главы приводятся алгоритмы декодирования по информационным совокупностям для ранговых кодов для исправления ошибок стирания за пределами кодового расстояния и результаты моделирования исправления ошибок стираний методом информационных совокупностей. Полученные результаты, изложенные в первой главе, опубликованы в [2,3,4,5].
Вторая глава описывает криптосистемы с открытым ключом на ранговых кодах. Глава начинается с оценки криптостойкости криптосистем типа ГПТ. Показывается эквивалентности разных форм
ГПТ одной форме открытого ключа. Детально разрабатывается атака на общую форму открытого ключа на основе атаки Овербека для исходной ГПТ. Оценивается сложность атаки в зависимости от параметров криптосистемы. Предлагается способ для создания стойких параметров. Далее разрабатывается новая криптосистема на ранговых кодах, в которой искусственная ошибка имеет вес не меньше кодового расстояния. Глава заканчивается сравнением новой криптосистемы и ранее известных. Полученные результаты, изложенные во второй главе, опубликованы в [18,19,20,21].
Третья глава содержит описания криптосистем с открытым ключом с быстрым расшифрованием, построенных в мнимых квадратичных полях. Вначале даются необходимые математические основы, затем приводятся опубликованные криптосистемы. Производится анализ свойств криптосистемы, приводится модификация криптосистемы с ускорением шифрования. Полученные результаты, изложенные в третьей главе, опубликованы в [29,30,31,32].
В заключении сформулированы основные результаты диссертационной работы.
Алгоритмы кодирования и декодирования
Единственная известная конструкция кодов исправляющих ошибки в ранговой метрике с быстрым алгоритмом декодирования дается в 1985 [1]. Это коды с максимальным ранговым расстоянием (МРР) коды. В диссертации представлены новые коды МРР [2]. Они - обобщение [1]. Доказывается, что построенные ранговые коды включают обычный ранговый код и определяют новые коды.
Раздел организован следующим образом. Вначале описываются известные ранговые коды. Затем демонстрируется новая конструкция и доказывается, что это МРР код. На первый взгляд построенная конструкция, является ранговым кодом в подполе. Дается доказательство различия кодов. Описаны кодирование и быстрые алгоритмы декодирования.
Основная цель главы - обобщение ранговых кодов, которое позволяет строить новые ранговые коды с быстрым алгоритмом декодирования. 1.2.2. Конструкция Будем рассматривать матрицу /її лр [2т] h Чп Нт — Ы к ;m] 42m] к и М т h[2m] ii n (1.22) h[(d-2)m] h[(d-2)m} h[(d-2)m] і. & для некоторого целого m с элементами hi Є GF(qN), п N, линейно независимыми над GF(q).
Покажем, что Нт является проверочной матрицей МРР кода, если га и N взаимнопростые, т.е. не имеют общих делителей: gcd(m, JV) = 1.
Лемма 1. Если hi,..., /гдг Є GF(qN) линейно независимы над GF(q) и gcd(m,N) = 1, тогда матрица Нт = \\h \\, і — 1,..., N, j = 0,..., N — 1 ие вырождена.
Индекс (jm mod АГ) пробегает все значения от 0 до N — 1. Следовательно, Нт представляет собой перестановку строк матрица Ц/ij; , которая не вырождена (см. [17]). А
Лемма 2. Если hi,...,hN Є GF(qN) линейно независимы над GF(q) и gcd(m,N) = 1, тогда hi,... ,h , рассматриваемые как элементы поля GF{qN) С GF(qNm), линейно независимы над GF(qm).
Предположим, что hi линейно зависимы над GF(qm) С GF(qNm). Выберем аь ... ,aN Є GF{qm) С GF(qNm) так, чтобы: 2J а г = о. Заметим, что а} = а\ = щ. Построим N уравнений возведением в степень qm: Y ciihi = О (E )I(JV-1)TOl = E f-1)ml = o Система N уравнений имеет решение а\,..., а/у если и только если матрица \щmJ является вырожденной. Что противоречит предыдущей лемме. Следовательно, предположение неверно, и hf линейно независимы над GF{qm). к Л ем м а 3. Если hi,...,hn GF(qN), п N, линейно независимы над GF(q) и gcd(m,N) = 1, тогда hi,...,hn, рассматриваемые как элементы GF(qN) С GF(qNm), линейно независимы над GF(qm). Доказательство непосредственно следует из предыдущей леммы, если мы расширим hi,...,hnflphi,...,h . А ТеоремаЗ. Если gcd(m, N) = 1, то матрица Нт определяет проверочную матрицу МРР кода. Случай т = 1 тривиален. Матрица Hi является обычной проверочной матрицей рангового кода.
Для случая т 1 рассмотрим поле GF(QN) — GF(qmN), Q — qm. Элементы hi можно рассматривать как принадлежащие полю GF{QN), но выбранные из подполя GF(qN). Элементы hi линейно независимы над GF(q). Согласно лемме 3, hi линейно независимы над полем GF(qm). Значит, матрица Нт - проверочная матрица для обоих ранговых кодов, над полем GF(QN) и над полем GF(qN), т.к.:
Во-первых, обратим внимание, что построенные коды не являются просто подкодами известных ранговых кодов над подполем GF(qN) с GF(qNm). Подкод над подполем GF(qN) с GF(qNm) определяет код с алгоритмом декодирования над расширенным полем GF(qNm). Таким образом, подкод является кодом na,j\GF{qNm).
Построенные коды построены над GF{qN) с алгоритмами кодирования и декодирования над полем GF{qN). Принципиальным моментом является то, что gcd(ra, N) = 1.
Во-вторых, покажем, что новая конструкция ранговых кодов определяет ранговые коды, которые не могут быть получены известными ранговыми кодами [1].
Нам достаточно показать различие хотя бы для одного примера, например, для кода с двустрочной проверочной матрицей и двустрочной порождающей матрицей: d = 3, к 2, п 4.
Л е м м а 4. Пусть т uv - различные натуральные числа взаимно простые с N (одно из чисел может равняться 1), и пусть т + v 7 0 mod N. Выберем любые два МРР кода с расстоянием d = 37 длиной п 4, к 2 и проверочными матрицами Hv = \\h\i\\ и Hm = 11 - II- Тогда Hv не может быть преобразована в Нт линейными комбинациями строк над GF(qN) (преобразование, полученное линейной комбинацией строк называется строковым скремблером).
Описание криптосистемы ГПТ со строковым и столбцевым скремблерами и шумовой матрицей
Теорема 9. Шум, вызванный шумовой (к х п)-матрицей X столбцевого ранга tx над GF(q) в открытом ключе G = S(G + X) из [22] или Gpub = S(G + Х)Р может быть сконцентрирован только в tx столбцах, т.е., открытый ключ Gpub может быть записан в виде
Gpub = S[XG]P. где X - (к х іх)-матрица над GF(qN) со столбцевым рангом colr(X.\q) =tx и рангом r(X.\qN) = r-%, r-% tx,G- порождающая (к х п — tx)-матрица рангового кода Габидулина, Р - столбцевой скремблер nadGF(q).
Так как столбцевой ранг X над GF(q) равен tx, можно записать Gp„b = S(G + Х)Р = S(G + [Ai..tx0fc+i..„]B)P, где В над GF(q). Далее, G = S(GB-X + [A0])BP = S[XG]P, X = A + [GB]i..tx, G = [GB]«x+i..„. A Теорема 10. Открытый ключ G = S([0G] + [XiX2])P из [25j может быть представлен в виде Gmb = S[0XG]P, где нулевая матрица О отсутствует, если Xi имеет полный столбцевой ранг над GF(q), и X - (k х t- )-матрица столбцевого ранга colr(X.\q) = t-%.
Аналогично предыдущей теореме. А Теорема 11. Открытый ключ Gpub = S[XG]P, где X - (к х I)-матрица и [XG] имеет неполный столбцевой ранг colr[\X\G]\q) = n + tx п + 1, может быть представлена в виде Gpub = S[0XG]P, где X - (к х іх)-матрица с полным столбцевым рангом colr(X.\q) = tx Доказательство просто, принимая во внимание, что G имеет полный столбцевой ранг colr(Gg) = п. А Мы видим, что все представления открытого ключа могут быть записаны в одной форме G = S[0XG]P, где X - (к х х)-матрица полного столбцевого ранга colr(X#) = tx Бесполезность нулевой подматрицы в открытом ключе
Теорема 12. Нулевая подматрица О в открытом ключе Gpub = S[0XG]P не влияет на защищенность, она моэюет быть просто проигнорирована.
Выберем любую подматрицу А из п + tx линейно независимых столбцов в Gjmb, разложим Gpub = [0А]В, где В - невырожденная матрица над GF(q). Тогда, A = врОДРВ"1 = S[XG]P - тоже открытый ключ. Далее мы можем либо атаковать ключ А или выбранные п + tx компонент шифротекста с для ключа А. А
Столбцевой скремблер над расширенным полем
В предыдущих открытых ключах матрица Р задан над основным полем GF(q) для сохранения столбцевого ранга вектора еР-1 при расшифровании. Что если Р выбирать над GF(qN)?
Пусть открытый ключ заданG = S[XG]P, где Х- (kxtx)-матрица над GF(q), G - порождающая (k х п)-матрица рангового кода, Р - (п + tx х п + х)-матрица выбранная над расширенным полем GF(qN) так, что Р-1 = [PiP2], Pi - (п + tx х х)-матрица над GF(qN) и Рг - (n + tx х п)-матрица над GF(q). Такая конструкция матрицы Р над GF(qN) позволяет корректное расшифрование. В самом деле, еР-1 = [еРіїеРг]. Первая часть еРі соответствует X. Вторая часть еРг содержит Р2 над GF(q) и соответствует G. Так как нам нужна только вторая часть для декодирования, расшифрование успешно.
Как мы видим, все представления открытого ключа могут быть записаны в одной общей форме для целей криптоанализа: Gpub = S[XG]P. (2.3) S - строковый скремблер, обратимая (к х &)-матрица над GF(qN). G - порождающая (к х п)-матрица МРР (те, к, б?)-кода. X - шумовая (к х )-матрица над GF(qN) с полным столбцовым рангом colr(X 7) = tx и рангом r(X\qN) = гх, гх tx- Матрица [XG] имеет так же полный столбцевой ранг co\x(\X\G]\q)=n + tx. Р - столбцевой скремблер, (tx + п х tx + те) над GF(q). tx + п может быть больше JV, п N.
Аналоги схем Диффи-Хеллмана, RSA и Эль-Гамаля
Впервые использование описанных классов эквивалентностей квадратичных полей для построения криптосистемы с открытым ключом предложили использовать Дж. Бухманн и X. Вилльямс. В работах [53] и [51] они построили схему обмена ключей по аналогии схемы Диффи-Хеллмана и RSA-подобную систему шифрования. Криптосистемы были построены в мультипликативной группе классов Cl(Af). Как уже упоминалось, операции с классами эквивалентностей идентичны операциям с редуцированными идеалами. Сложность битовых вычислений в алгоритмах обмена ключей, шифрования и расшифрования является кубической величиной 0(logs\Af\) из-за операции возведения классов эквивалентности (редуцированных идеалов) в степень.
Д. Хухляйн, М. Якобсон и С. Паулюс указали способ для улучшения временных характеристик криптосистем. В работе [50] они использовали классы эквивалентностей в двух квадратичных порядках OAJ and 0д9 с дискриминантом Ai, Aq = Aiq2, где q - простое число того же порядка, что и А\. Построенная ими схема является аналогом схемы Эль-Гамаля. Шифрование в этой схеме производится в группе классов Cl(Aq) - редуцированный идеал т, представляющий исходное сообщение га, переводился в другой редуцированный идеал с, представляющий шифротекст. Операция шифрования практически идентична схеме Эль-Гамаля в поле целых чисел р. Расшифрование делается в группе классов С1(А\): редуцированный идеал шифротекста с из Cl(Aq) отображается изоморфизмом ф в редуцированный идеал и из Cl(Ai); к идеалу и применяется алгоритм расшифрования, состоящий из операций возведения в степень, умножения и редуцирования, в итоге получается идеал редуцированный идеал щ из С1(А\); идеал Ui изоморфизмом ф 1 переводится в идеал сообщения m из Cl(Aq).
Отображение идеалов в группу классов максимального порядка Cl(Ai) позволяет увеличить скорость расшифрования приблизительно в 30 раз по сравнению с криптосистемами [53] и [51]: расшифрование имеет кубическую битовую сложность 0(log3\Ai\), а шифрование - 0(log3\Aq\) 0(27 /o 3Ai). Сложность вычисления алгоритмов шифрования и расшифрования как обычно в криптосистемах шифрования с открытым ключом является кубической по длине открытого параметра Aq. Заметим, что криптосистемы Дж. Бухманна и X. Вилльямса могут быть изменены похожим образом для увеличения скорости расшифрования.
Недавно С. Паул юс и Т. Такаги предложили новую систему шифрования с открытым ключом [48], имеющую квадратичную битовую сложность расшифрования, как альтернативу широко используемым в настоящее время системам RSA и Эль-Гамаля. Криптосистема является дальнейшим развитием [50]. Нововведением является использование следующего свойства гомоморфизма ф между группами Cl(Ai) и Cl(Aq): гомоморфизм ф переводит (q — е(Ді, q)) классов Cl(Aq) в один класс С1(А\). Шифрование производится в Cl(Aq) и имеет кубическую сложность вычислений О (fog3 Дд) из-за использования операции возведения в степень. Схема расшифрования аналогична схеме предыдущей работы [50] за исключения того, что в самом алгоритме расшифрования не используется операция возведения идеалов в степень. Сложность расшифрования является квадратичной - 0(log2\Ai\).
Вкратце криптосистема NICE-X выглядит следующим образом. Открытым ключом является дискриминант Aq, его разложение на множители - секретный параметр.
Пусть идеал р принадлежит ядру гомоморфизма Кег(фд), т.е. фч(р) = Red pQ ) Є Рд д). Идеал р - открытый параметр схемы.
Шифрование состоит в следующем. Пусть г - случайный редуцированный идеал в 0дд с нормой N(x) y/\Ai\/4. Редуцированный идеал t задает элемент Cl(Aq), причем фд{х) = ф{х)1 ф 1(фя(г)) = г. Определим редуцированные идеалы t = Red,Aq(pk), с = Red&q(tt), гДе & случайное целое число меньше q — e(Ai,q). Шифрование переводит элемент Cl(Aq) в один из q — e(Ai,q) классов из Cl(Aq), которые гомоморфизмом ф переводятся в один элемент Cl(Ai). Идеал г имеет среди редуцированных идеалов этих классов минимальную норму. Шифротекстом битового сообщения т является [С = тф hash(t),с].
Оптимизация шифрования
Медленное шифрование NICE-X вызвано двумя факторами. Во-первых, в шифровании используется возведение в степень классов эквивалентностей из Cl(Aq). Битовая сложность возведения в степень - кубическая. Операции с классами намного медленнее, чем модульные операции с целыми числами.
Во-вторых, в алгоритме шифрования генерируется большой квадратичный идеал. Общий метод генерирования идеала использует генерирование простого числа. Битовая сложность генерирования n-битового простого числа составляет порядка 0(- - ) или немного лучше в оптимизированных алгоритмах [42].
В результате, мы получим время шифрования четвертой степени по длине параметров схемы.
Эффективная программная реализация NICE-X показала, что возведение в степень классов эквивалентности и генерирование простого числа приблизительно одной величины. Покажем, как можно уменьшить существенно время генерирования большого идеала. Это даст нам ускорение приблизительно в два раза.
Генерирование случайного минимального класса г из группы CI(Ад) означает генерирование случайного минимального редуцированного идеала.
Генерирование идеала означает генерирование пары чисел (a, b):b2 = Aq mod 4а, а 0, — а b а. Общепринятый подход, подразумевает генерирование числа а и дальнейшего решения квадратичного модульного уравнения алгоритмом RESSOL Шэнкса [47]. Именно этот метод был предложен авторами для генерирования идеала в алгоритме шифрования NICE [48]. Немного улучшенный метод заключается в выборе простого числа в форме а = 3 mod 4 и даль-нейшего вероятностного решения b = ±Ag4 mod а. Вероятность успеха - \. Если Aq не является квадратичным остатком по модулю а, нужно взять другое простое число а.
Предлагается более быстрый подход к созданию идеала. Нужно создать набор маленьких идеалов (щ, bj) с битовыми длинами щ порядка 50. Конечный идеал (а, Ь) будет представляться произведением некоторых степеней идеалов: (а, 6) = Пг(аь&г) - Таким образом, необходимо создать набор маленьких простых чисел {aj. Что, позволяет нам избежать генерирования большого простого числа.
Битовая длина а около 250-1000. Достаточно сгенерировать только 5 разных 50-битовых простых чисел щ для конструирования идеала. Действительно, мощность множества возможных значений а составляет (7г(250))5 2220, где 7г(п) - число простых чисел меньше п. Что вполне достаточно для защищенности схемы.
Таким образом, сложность шифрования становится кубической. Программная реализация показала ускорения шифрования примерно в 2 раза (см. результаты программной реализации ниже).
Компонент открытого ключа класс р должен быть генератором ядра Кегф. Порядок ядра равен h = q — e(Ai, q), е(Ді, q) — ±1. Порядок определенно составное число. Так что, произвольный класс р может быть генератором только малой подгруппы ядра. В таком случае, криптосистема взламывается перебором в малом множестве {cpk} of %. Соответственно, класс стойких р состоит из генераторов ядра.
