«ЭЛЕМЕНТЫ ТЕОРИИ ЧИСЕЛ И КРИПТОЗАЩИТА Учебное пособие Составители: Б. Н. Воронков, А. С. Щеголеватых Издательско-полиграфический центр Воронежского государственного университета 2008 Утверждено научно-методическим ...»

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ

УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ

УНИВЕРСИТЕТ»

ЭЛЕМЕНТЫ ТЕОРИИ ЧИСЕЛ

И КРИПТОЗАЩИТА

Учебное пособие Составители:

Б. Н. Воронков, А. С. Щеголеватых Издательско-полиграфический центр Воронежского государственного университета 2008 Утверждено научно-методическим советом факультета прикладной математики, информатики и механики 27 февраля 2008 г., протокол № Рецензент канд. физ.-мат. наук, доц. К. П. Лазарев Учебное пособие подготовлено на кафедре технической кибернетики и автоматического регулирования факультета прикладной математики, информатики и механики Воронежского государственного университета.

Рекомендуется для студентов 4-го курса дневного отделения и 4-го курса вечернего отделения.

Для специальности 010501 — Прикладная математика и информатика

СОДЕРЖАНИЕ

Предисловие…………………………………………....……….. 1. Основные понятия и определения………………………………..

2. Элементы теории чисел и модулярная арифметика…………….. 2.1. Малая теорема Ферма. Теорема Эйлера …………………... 2.2. Квадратичные вычеты и закон взаимности.……………….. 2.3. Вычисление обратных по модулю величин………………... 2.4. Сравнение арифметических операций по их трудоемкости...... 2.5. Нахождение простых чисел…………………………………. 3. Формальное определение криптосистемы……………………..... 4. Криптосистема Эль Гамаля……………………………………..... 5. Криптосистема RSA (R. Rivest, A. Shamir, L. Adleman)……...… 6. Методы распределения криптографических ключей…….……... 6.1. Распределение секретных ключей с обеспечением конфиденциальности и аутентификации…………………...….... 7. Криптография с использованием эллиптических кривых…….... 7.1. Аналог обмена ключами по схеме Диффи-Хеллмана ……... 7.2. Протокол обмена ключами по схеме Месси-Омуры…..…..

7.3. Протокол распределения ключей Менезеса-Кью-Ванстона (MQV-протокол)…………………… 7.4. Протокол Эль Гамаля для криптосистемы с использованием эллиптических кривых…

7.5. Обоснование протоколов с использованием модулярной арифметики……………………………………......... 8. Цифровая подпись………………………………………..……….. 8.1. Стандарт DSS, алгоритм DSA………………………………. 8.2. Обобщенная схема цифровой подписи Эль Гамаля……….. 8.3. Схема цифровой подписи Эль Гамаля с возвратом сообщения……………………………………………………...………. 8.4. Цифровая подпись с использованием точек эллиптической кривой………………….……………………...... 9. Модели атаки нарушителя………………………………………... 10. Модель несанкционированной подмены передаваемой информации…………………...……………………………………… Библиография…………………………………………………… Предисловие Для современного этапа научно-технического развития характерен стремительный рост потоков передаваемой информации. В связи с этим возникает острая необходимость в совершенствовании традиционных телекоммуникационных систем и создании новых, более совершенных, способных увеличить быстродействие используемых технических устройств, повысить безопасность и обеспечить экономичность самого процесса обмена информацией.

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

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

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

Источники основных понятий и определений :

ГОСТ Р 50922-96 Защита информации: термины и определения. Госстандарт России.

ГОСТ Р 51583-00 Защита информации. Порядок создания автоматизированных систем в защищенном исполнении. Общие положения. Госстандарт России.

ГОСТ Р 51624-00 Защита информации. Автоматизированные системы в защищенном исполнении. Общие требования. Госстандарт России.

ОСТ 45.127-99. Система обеспечения информационной безопасности Взаимоувязанной сети связи Российской Федерации. Термины и определения.

Информация — сведения о лицах, предметах, фактах, событиях, явлениях и процессах независимо от формы их представления.

Сообщение — информация, представленная в определенной форме.

Формы представления разнообразны: письменный текст, речь, музыка, графическое изображение, электромагнитное поле, взаимное расположение предметов в пространстве и т. д.

Дискретные сообщения — сообщения, вырабатываемые дискретными источниками, среди которых выделяются источники цифровой информации.

Дискретная информация — информация, зафиксированная в дискретном сообщении.

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

Сигнал — переносчик, параметры которого находятся в однозначном информационном соответствии с сообщением.

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

Информационная безопасность — состояние информации, информационных ресурсов и информационных систем, при которой, с требуемой вероятностью, обеспечивается защита информации.

Информационные ресурсы — документы, массивы документов (архивы, фонды), программы для ЭВМ, базы данных, существующие отдельно или в составе информационных систем.

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

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

Закрытая информация содержит государственную, коммерческую или иную тайну.

Секретная информация содержит государственную тайну.

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

Защищаемая информация — информация, являющаяся предметом собственности и подлежащая защите в соответствии с требованиями правовых документов или требованиями, устанавливаемыми собственниками информации.

Утечка информации — неконтролируемое распространение защищаемой информации.

Утечки трех видов:

а) разглашение, б) несанкционированный доступ к информации, Уничтожение информации — утрата информации при невозможности ее восстановления.

Блокировка информации — невозможность ее использования при сохранности.

Модификация информации — изменение ее содержания по сравнению с первоначальной.

Цена информации — полезность информации для участников информационного рынка.

Ценность информации — полезность информации для ее владельца (пользователя).

Угрозы информации:

а) нарушение конфиденциальности — потеря ценности информации при ее раскрытии;

б) нарушение целостности — потеря ценности информации при ее модификации или уничтожении;

в) нарушение доступности — потеря ценности информации при невозможности ее оперативного использования;

г) нарушение устойчивости к ошибкам — потеря ценности информации при сбоях в информационных системах.

Эффективность защиты информации — мера соответствия уровня информационной безопасности требованиям при заданном ресурсе на ее защиту.

Политика безопасности — набор документированных норм, правил и практических приемов, регулирующих управление, защиту и распределение информации ограниченного доступа.

Структурная схема системы связи представлена на рис. 1.

Рис. 1. Общая структурная схема системы связи: 1 — источник информации;

2 — передатчик; 3 — приемник; 4 — адресат (получатель); 5 — источник шума и помех.

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

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

Криптосистема — система, реализованная программно, аппаратно или программно-аппаратно и осуществляющая криптографическое преобразование информации.

Криптоанализ (наука о дешифрации) — раздел прикладной математики, в котором изучаются модели, методы, алгоритмы, программные и аппаратные средства анализа криптосистемы или ее входных и выходных сигналов с целью извлечения конфиденциальных параметров, включая открытый текст.

Совокупность криптографии и криптоанализа образует новую науку — криптологию Текст — набор элементов алфавита имеющий определенный логический смысл. Открытый текст (ОТ) — исходное, шифруемое сообщение.

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

Обычно ключ — последовательность символов того же алфавита, в котором набрано сообщение. Пространство ключей — набор всевозможных значений ключа.

Дешифрование — нахождение ключа или открытого текста на основе шифрованного текста.

Расшифрование — нахождение открытого текста на основе известного ключа и шифра.

Криптостойкость –— характеристика шифра, определяющая его стойкость к дешифрации. Часто криптостойкость измеряется количеством операций, необходимых для перебора всех возможных ключей, или интервалом времени, необходимого для дешифрования (MIPS-годы).

MIPS (Million Instructions Per Second) — миллион инструкций в секунду.

Криптограмма — шифрованный текст (ШТ).

Основная идея шифрования — скрытие смысла передаваемого сообщения.

Выделяют два класса криптосистем:

симметричные (одноключевые) криптосистемы;

асимметричные (двухключевые) криптосистемы.

Методы симметричного шифрования: 1. Перестановки. 2. Подстановки.

3. Гаммирование. 4. Аналитическое преобразование шифруемых данных.

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

Рис. 2. Структурная схема передачи шифрованных сообщений: 1 — отправитель; 2 — устройство шифрования; 3 — устройство расшифрования; 4 — получатель;

5 — перехватчик (злоумышленник); 6 –– канал связи; 7 –– генератор ключей.

Алфавит — конечное множество используемых для шифрования знаков.

Z33 — 32-буквенный русский алфавит и пробел.

Z256 — расширенный ASCII (American Standard Code for Information Interchange – Американский стандарт кодирования для обмена информацией (KOИ8)).

Иногда смешивают два понятия: шифрование и кодирование. Для шифрования надо знать открытый текст, алгоритм шифрования и секретный ключ. При кодировании нет ничего секретного, есть только замена символов открытого текста или слов на заранее определенные символы.

Методы кодирования направлены на то, чтобы представить открытый текст в более удобном виде для передачи по телекоммуникационным каналам, уменьшения длины сообщения (архивация), повышения помехоустойчивости (обнаружение и исправление ошибок) и т. д. В принципе кодирование, конечно же, можно рассматривать как шифр замены, для которого «набор» возможных ключей состоит только из одного ключа (например, буква «а» в азбуке Морзе всегда кодируется знаком « · » – и это не является секретом).

2. Элементы теории чисел и модулярная арифметика [1; 7; 10] При разработке алгоритмов шифрования используется ряд понятий теории чисел и модулярной арифметики.

Теория чисел, или высшая арифметика, изучает свойства целых чисел.

Как наука она оформилась, начиная с открытий П. Ферма. Под целыми числами понимают числа …, -4, -3, -2, -1, 0, 1, 2, 3, 4, … Особое место среди целых чисел занимают натуральные числа – целые положительные числа 1, 2, 3, 4, … Высшая арифметика — дедуктивная наука, основанная на законах арифметики. Целые числа образуют бесконечный ряд (множество) Z, где выполняются основные арифметические операции: сложение, вычитание и умножение. Частное от деления целых чисел не всегда является целым числом. Поэтому множество целых чисел образует кольцо.

Мы назовём одно число a делителем другого числа b, если b = a c для некоторого числа c. Примем обозначение a /b, означающее, что a делит b нацело, или a является делителем b. Если число a не является делителем другого числа b, то используем обозначение: a не делит b.

Натуральное число p называется простым, если p > 1 и не имеет положительных делителей, отличных от 1 и p. Натуральное число N называется составным, если N > 1 и имеет, по крайней мере, один положительный делитель, отличный от 1 и N.

Основная теорема арифметики. Всякое натуральное число N, кроме 1, можно представить как произведение простых множителей причем единственным образом, с точностью до порядка следования сомножителей.

Среди простых сомножителей разложения (2.1) могут быть и равные. Если обозначить различные из них p1, p2,…, pk и допустить, что они встречаются в разложении соответственно 1, 2,..., k раз, то разложение (2.1) преобразуется к виду и называется каноническим разложением.

Общий делитель нескольких целых чисел — это число, на которое делятся все данные числа без остатка. Наибольший из делителей называется наибольшим общим делителем (НОД). Форма записи НОД такая:

(a, b) = c, где c — НОД чисел a и b.

Единица не является ни простым, ни составным числом, так как иначе не удастся доказать основную теорему арифметики.

Взаимно простые числа — это два или несколько целых чисел, наибольший общий делитель которых равен единице, т.е. ( a, b) = 1, при этом для любых неотрицательных чисел m и n справедливо: ( a, b ) = 1.

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

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

Алгоритм Эвклида. Пусть a и b будут целыми числами и b > 0 (так как (a, b) = (–a, –b), это не умаляет общности). Мы используем повторно свойство делимости следующим образом (пример для a = 390 и b = приведён справа от главного изложения).

rn-2 = br n-1q n-1 + rn, 0 rn< rn-1;

где qi,— частное, а ri — остаток от деления (все 0).

Остатки r 2, r 3,... постоянно уменьшаются, так что в конце концов они должны стать равными нулю. Очевидно, что (a, b) = (a, b) = ( r2, b) = = (r2, r3) =... = (rn-1, rn ) = rn, так как в действительности rn | rn-1.

Отсюда НОД a и b является последним ненулевым остатком в вышеописанном процессе повторного деления.

Следовательно, наибольший общий делитель (390, 170) = 10. Заметим, что это было получено без разложения на множители каких-либо чисел.

На сегодняшний день алгоритм Эвклида, несмотря на более чем 2000-летнюю историю, остается наиболее эффективным алгоритмом из известных.

Наименьшим общим кратным (НОК) отличных от нуля чисел N1, N2, …, Nn называют наименьшее положительное число, кратное всем этим взаимно простых чисел равно их произведению.

Фи-функция Эйлера (n) определяет число целых положительных чисел, не превосходящих n и взаимно простых с n.

Здесь p и pi — простые числа, и i — натуральные числа.

Свойства фи-функции Эйлера:

1. Мультипликативность:

2. Сумма значений фи-функции Эйлера от всех положительных делителей d числа n равна n :

Пусть n — натуральное число. Если два целых числа a и b при делении на n дают один и тот же остаток, то они называются сравнимыми по модулю n. Отношение сравнимости было введено Карлом Фридрихом Гауссом и записывается как Читается: a сравнимо с b по модулю n. Все четные (нечетные) числа сравнимы по модулю два. 30 16 5 23(mod 7), так как Из соотношения a b (mod n ) следует отношение делимости n ( a b ), т.е. разность сравнимых по модулю n чисел кратна модулю n и, следовательно, сравнима с нулем по данному модулю. Из равенства a = b следует сравнение a b по любому модулю.

У равенств и сравнений имеется много общих свойств:

3) обе части сравнения можно почленно складывать и вычитать:

4) обе части сравнения можно почленно умножать:

Замечание. Все сравнения в пунктах 1) — 4) осуществляются по одному и тому же модулю.

Специфические свойства сравнений:

5) обе части сравнения можно разделить на общий делитель, если он взаимно прост с модулем 4 не сравнимо с 2 по модулю 3, так как (3, 3) = 3 1;

6) обе части сравнения и модуль можно умножить на одно и то же натуральное число, а также разделить на любой их общий положительный делитель:

7) если сравнение имеет место по нескольким модулям, то оно имеет место по модулю, равному общему наименьшему кратному этих модулей:

8) если сравнение имеет место по mod n, то оно имеет место и по модулю d, равному любому делителю числа n :

9) общий делитель одной части сравнения и модуля является также делителем второй части сравнения :

Для сравнений справедливы основные законы арифметики:

(a ± b) mod m [a mod m ± b mod m] mod m (ассоциативность);

(a b) mod m [a mod m b mod m] mod m (коммутативность);

[с (a ± b)] mod m [с a mod m ± с b mod m] mod m (дистрибутивность).

Все целые числа, которые при делении на n дают один и тот же остаток r, объединяют в один класс, обозначая его Z i. Очевидно, что при делении на n возможны n остатков:

Следовательно, все целые числа можно разбить на n классов:

которые называются классами вычетов по модулю n. Каждый класс Z i содержит бесконечное количество сравнимых между собой целых чисел, объединенных одним соотношением Замечание. Различные классы вычетов по модулю n не содержат общих элементов и, таким образом, являются непересекающимися классами. Например, при n = 2 все целые числа разбиваются на два непересекающихся класса: четные и нечетные числа. Числа одного и того же класса называются вычетами этого класса.

Полной системой вычетов по модулю n называют набор чисел, содержащий по одному вычету из каждого класса. В качестве «представителя» класса можно взять любой вычет класса. Однако чаще всего пользуются наименьшими неотрицательными вычетами, когда в формуле N = nq + r число q = 0. В этом случае полная система вычетов по модулю n составляется из остатков r : 0, 1, 2, 3,..., (n 1).

Приведенной системой вычетов по модулю n называют набор чисел из полной системы вычетов, которые являются взаимно простыми с модулем n.

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

10) слагаемое, стоящее в какой-либо части сравнения, можно переносить в другую часть, переменив его знак на обратный;

11) к каждой части сравнения можно прибавить любое число, кратное модулю;

12) обе части сравнения можно возвести в одну и ту же степень.

Если модуль класса вычетов представляет собой простое число, то множество вычетов по этому модулю образует конечное поле (поле Галуа).

Полем называется коммутативное кольцо, в котором у каждого ненулевого элемента есть обратный. Поскольку произведение двух ненулевых элементов поля снова является ненулевым элементом (вследствие отсутствия в поле делителей нуля), операция умножения ассоциативна, имеется нейтральный для операции умножения элемент 1 и каждый ненулевой элемент а имеет обратный элемент a, то множество отличных от нуля элементов поля образует абелеву группу по умножению. Эта группа называется мультипликативной группой поля.

Ненулевые элементы кольца вычетов Zm тогда и только тогда образуют группу относительно операции умножения по модулю m, когда m — простое число. Следовательно, для простого числа р кольцо Zp является полем. Это конечное поле принято обозначать GF ( p ). Его элементы {0, 1,…, (p – 1)} — это всевозможные остатки от деления целых чисел на р, а алгебраические действия с ними — сложение и умножение по модулю р.

Характеристикой поля называется такое наименьшее положительное число k, для которого k a 0(mod p ), а GP ( p ). Если такого элемента не существует, то считается, что характеристика поля равна нулю.

Каждое поле Галуа содержит единственное наименьшее подполе, число элементов которого равно простому числу. Следовательно, характеристика каждого поля Галуа является простым числом.

Для конечного поля справедлива малая теорема П. Ферма.

лое число. Тогда a a (mod p). Если p не делит a, тогда a 1 (mod p).

Доказательство. Предположим сначала, что p не делит a, так что (а, р) = 1, и рассмотрим р – 1 чисел а, 2а, 3а,..., (р – 1)а. Ни одно из них не кратно p ( p | ja означает, что p | j, так как р — простое число и p не делит a). Также не найдётся двух чисел, которые конгруэнтны (сравнимы) по модулю р, так как ja ka (mod p) означает j k (mod p). Следовательно, по модулю р эти р – 1 чисел различны и не равны нулю. Итак, числа 1, 2, 3,..., р – 1 должны располагаться в соответствующем порядке. Перемножая их, мы получим Числа 2, 3,..., р – 1 все являются взаимно простыми с р и могут сюда следует, что a 1 (mod p). Умножение на а даёт a a (mod p).

Если, с другой стороны, р | a, тогда р и а оба 0 (mod p), а из этоp го следует, что a a (mod p).

Обобщением малой теоремы Ферма является теорема Эйлера для составного модуля.

Теорема Эйлера. Пусть n > 0 и предположим, что (a, n) = 1. Тогда a 1 (mod n), где (n) — фи-функция Эйлера.

Доказательство. Пусть r1, r2,..., rk (k = (n) ) будут целыми числами Z 1, n и взаимно простыми с n. Рассмотрим a r1, a r2,..., a rk.

Из представленных членов не найдётся двух, которые сравнимы по mod n (a ri a rj, что означает ri rj (mod n), так как (a, n) = 1) и все они взаимно простые ((a, n) = ( ri, n) = 1, что означает (a ri, n) = 1). Следовательно, среди них существуют (n) таких, что их наименьшие положительные вычеты по модулю n должны быть точно числами r1, r2,..., rk в соответствующем порядке. Отсюда так что, сокращая ri, так как они взаимно простые с n, мы получим искоk мое сравнение 1 a (mod n).

Функция (n) является мультипликативной, т.е. если (m, n) = 1, тогда (mn) = ( m) ( n). Принято, что (1) = 1 и ( 2) = 1.

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

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

-метод факторизации Полларда. Пусть f(x) = x + 1 и запишем f2(x) = f(f(x)), f3(x) = f(f2(x)) и т. д. Пусть ak =f k(1). (Следовательно, а = 2, а2 = 5, аk+1 = ak 2 + 1). Конечно, вместо этого f можно использовать другие полиномы. Предположим, что мы хотим представить N в виде сомножителей, т.е. найти простое число р (возможно наименьшее простое число), для которого p | N. Конечно, последовательность {ak}, взятая по модулю р или по модулю N в конце концов будет повторяться, и ожидается, что это повторение будет происходить быстрее по модулю p, чем по модулю N. (Действительно, повторение будет реальной возможностью, если количество членов превзойдёт p ). Следовательно, мы надеемся, что ai aj (mod p) для j > i и j не достаточно большое. Заметим, что тогда at aj-i+t (mod p) для всех t i. Конечно, мы не можем решить задачу нахождения ai mod p, пока мы не знаем, что собой представляет р, но мы можем решить задачу нахождения ai по модулю N, мы просто запишем (Чтобы не связываться с aj – ai, требуется, чтобы эта разность быстро становилась очень большой).

Проделаем простое усовершенствование: так как i < j, то существует целое число t, для которого i < t j и (j - i) | t. (Это становится понятным, если задать вопрос, почему должно существовать целое число k, для которого i /(j – i) < k j /(j – i), и тогда используйте t = k(j – i)). Более того, at = ak(i-i ) a(k+1)(j-1) a(k+2)(j-1)... a2k(j-1) a2t (mod p), т.е. вместо контроля i и j мы должны рассмотреть at и a2t для t = 1, 2, 3,... Таким образом, метод заключается в следующем:

Заменим х на f (x), y на f (f (y)); таким образом, теперь x = a2, y = a4. Найдём (x – y, N).

Повторим: теперь х = a3, у = a6. Найдём (x – y, N).

Продолжаем до тех пор, пока (x – y, N) не станет равным 1 или N.

Конечно, х и у сокращаются по модулю N на каждой стадии, используя x:= (x – N) · INT(x / N), и т. д. Заметим, что вышеприведённый метод значительно лучше, чем сохранение ai в массиве, даже учитывая, что ai вычисляется дважды. При этом удаётся избежать проблемы, связанной с большими массивами чисел повышенной точности.

(р – 1) метод факторизации Полларда. Одной из версий этого метода будет следующая. Предположим, что р — простое число, а k такое, что (р – 1) | k! Это означает, что все простые сомножители числа (р – 1) будут меньше k. Теорема Ферма утверждает, что 2k! 1 (mod p).

Предположим, что мы хотим разложить на множители данное целое число N. Возьмём малое целое число, скажем, 2 и вычислим последовательно где k является разумно большим (но не слишком большим!). Если р — простой множитель N, тогда, естественно, р является множителем числа (2 k! – 1N, N) и НОД будет скорее р, чем N. (Обозначение хN принято для наименьшего положительного вычета x по модулю N). Этот метод можно проверить на числах, которые являются произведением двух простых чисел. Заметим, что для успеха вычислений мы должны потребовать, чтобы все простые множители искомого фактора р были бы k.

Китайская теорема об остатках. Пусть m1, m2,..., mr — положительные числа, причем, каждая пара взаимно простая: (mi, mj) = 1 для i j. Тогда система сравнений имеет единственное решение — сравнение по модулю произведения m1 m... mr.

Доказательство. Существование решения может быть доказано индукцией или следующим образом. Пусть ki для i = 1,..., r будет произведением всех положительных чисел m за исключением mi. Конечно, (ki, mi) = 1, так что ki имеет обратное число ni по модулю mi. Тогда есть искомое решение. Например, m1 является сомножителем n2,..., nr и k1 n1 1 (mod m1), Отсюда x a1 (mod m1). Таким же образом доказываются другие сравнения.

Порядком числа а по модулю n, если (a, n) = 1, называется наиk меньшее целое k > 0 такое, что a 1 (mod n). Это записывается как k = ordn a и произносится, что а имеет порядок k по модулю n. Естественно, что ordn a (n). Заметим, что если (a, n) > 1 и k > 0, то невозможно для a быть сравнимым с 1 (mod n). Если а имеет порядок k mod n, тогда в некоторых книгах используют выражение “а является показателем k по модулю n”.

Предположим (a, n) = 1. Тогда a 1 (mod n), если ordn a | k. Отсюда получим, что степень а, которая сравнима с 1, не только ordn a, но точно кратна этому порядку. В особенности это нужно помнить, когда ordn a | (n) и если р — простое число, то ordn a | (p – 1).

Доказательство. Предположим, что а 1, где k > 0 и пусть k = q ordn a + r, где 0 r ordn a. Тогда, по модулю n, Отсюда и из определения порядка следует, что r = 0 как число наименьшей положительной степени а, которое сравнимо с единицей.

Число а, для которого (a, n) = 1 и ordn a = (n) называется примитивным корнем по модулю n. Таким образом, если модуль n делится на два различных простых нечётных числа, то для него не существует примитивного корня.

Определим основные свойства примитивных корней. Если предположить, что g является примитивным корнем по модулю n, то выполняются следующие свойства:

а) для любых целых чисел r и s, по модулю n. Они, следовательно, по модулю n точно являются числами, взаимно простыми с n; положительные вычеты являются точно положительными целыми числами (n – 1) и взаимно простыми с n.

Доказательство а) предположим, что r s. Тогда g g g (mod n), и так как (g, n) = 1, то можно сократить g s из обеих частей, чтобы получить g r–s 1 (mod n). Таким образом, (n) = ord n g | (r – s), что даёт искомый результат. Обратное утверждение также действительно;

б) это действительно применение пункта (а); так как нет двух степеней 0, 1, 2,..., (n) – 1, которые могли быть сравнимыми по модулю (n).

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

Теорема. Предположим, что а является примитивным корнем по модулю 2 для некоторого k 3. Тогда а является также примитивным корнем по модулю 2. Следовательно, не существуют примитивные корk ни по модулю 2 для k 3.

Доказательство. Очевидно, что а является нечётным числом. Мы имеем (2 k 1 ) = 2 k 2. Предположим, что в действительности порядок а по моk-1 k- дулю 2 меньше, чем 2. Следовательно, степень числа 2 будет меньше, чем (k – 2) :

а 2 1(mod 2k 1 ) для некоторого r (0 r k – 3). Последовательное возведение в квадрат показывает, что а а2 1 0(mod 2 k ). Однако это противоречит предположению, что а является примитивным корнем по модулю 2. Это показывает, что порядок а равняется (2 k 1 ) = 2 k 2, что и требовалось доказать.

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

Известно [5], что для простого числа р степени числа а с показателями от 1 до (р – 1) порождают все целые числа в ряду от 1 до (р – 1) в точности по одному разу. Любое целое число b можно представить в форме в классах вычетов. Отсюда вытекает, что для любого целого числа и любого первообразного корня а простого числа р можно найти ровно один показатель степени i, для которого Значение показателя степени i, называют индексом числа b по модулю р при основании а, или дискретным логарифмом.

Для дискретного логарифма принята форма записи ind а, р (b) и справедливы следующие выражения:

2.2. Квадратичные вычеты и закон взаимности Простые числа р, которые появляются при разложении в непрерывную дробь числа n, имеют особые свойства: для каждого такого р существует х, для которого х n (mod p).

Определение. Пусть р является нечётным простым числом, а число n не делится на p. Тогда n называется квадратичным вычетом по модулю р, если n x (mod p) для некоторого х (записывается nRp), или квадратичным невычетом по модулю р, если не существует таких х (записыn вается nNp). Мы также будем использовать символ Лежандра. Он определяется так: для p, не делящего n, будет = + 1, если nRp, и = –1, если nNp. Конечно, = 1 для любого n, = 1 для любого р. Случаем р = 2 пренебрегаем, так как он неинтересен (для каждого нечётного числа выполняется n 1 (mod 2)). Для выбранного простого числа р мы можем найти n, для которого принадлежность к nRp определяется возведением в квадрат по очереди чисел х = 1, 2,..., р – 1. Например, для р = 5 получим 1R5, 4R5, в то же время, 2N5, 3N5.

Критерий Эйлера для квадратичных вычетов. Если g является примитивным корнем по модулю p, где р — нечётное простое число, и пусть p не делит n, причем n g (mod p) для некоторого k. Тогда, если Основные свойства символа Лежандра:

а) альтернативное утверждение критерия Эйлера :

n(p-1) / 2 (mod p) (здесь р является простым числом и p не деp лит n);

б) если р является простым числом и p не делит n, то в) если р является простым числом и p не делит n, то p p для любого целого k.

Закон квадратичной взаимности. Если р и q являются различными нечётными простыми числами, тогда =, если оба не являются сравнимыми с 3 (mod 4). Это эквивалентно утверждению Доказательство. В плоской системе координат х и у отметим целые числа 1, 2,..., у и образуем прямоугольник с вершинами (0, 0), (p / 2, 0), (p / 2, q / 2), (0, q/2). Прямоугольник внутри себя содержит точки сетки ( p 1) 1 (q 1), обе координаты которых являются целыми числами.

Рассмотрим диагональ прямоугольника, которая описывается уравнением y = xq / p для 0 х р/2 и 0 у q / 2, и поэтому не может содержать никаких других точек решётки.

2),..., (k, ), расположенные ниже диагонали. Таким образом, обоp значая через М общее число точек решётки, получим = (–1).

Аналогично, если N представляет собой количество точек, располоp p q женных выше диагонали, тогда = (–1). Отсюда = (–1), а так как N + M = ( p 1) (q 1), то последний результат завершает доказательство.

Квадратичный закон взаимности обнаруживает простое и в то же время замечательное взаимоотношение между разрешимостью сравнений х2 n (mod p) и х2 p (mod n).

Вычислим, например, для некоторых простых чисел р.

есть 1.

закона взаимности, Обобщением символа Лежандра является символ Якоби, который деn лает вычисление значительно проще, так что отпадает необходиp мость в разложении n на сомножители.

Определение символа Якоби. Пусть k является нечётным числом, большим нуля, а (n, k) = 1 и предположим, что k является произведением (необязательно различных) простых чисел: k = p1 p2... pr, тогда Заметим, что все эти символы Лежандра определены, так как нет pi, которое может разделить n (k и n являются взаимно простыми). Таким обn разом, = ±1, и если так случится, что k будет простым числом, тогда символы Якоби и Лежандра совпадут. Заметим также, что если nRk, тогда обратная теорема не верна, как это видно из следующего в то время как х 2 (mod 15) не имеет решений.

Это позволяет символ Якоби рассматривать менее полезным, чем символ Лежандра, но символ Якоби описывает несколько критических свойств символа Лежандра. Они, действительно, очень полезны.

Основные свойства символа Якоби:

а) если k является нечётным числом и > 0, а (k, n) = (k, m) =1, тогда б) если k является нечётным положительным целым числом, а Доказательство следует немедленно из определения символа Якоби совместно с соответствующими свойствами символа Лежандра.

2.3. Вычисление обратных по модулю величин [2; 4; 10] Определение. Целое число а является обратным числу b по модулю n, если выполняется сравнение: ab 1 (mod n).

Теорема. Для целых а и n существует b такое, что ab 1 (mod n), если и только если (a, n) = 1. Когда b существует, оно также будет взаимно простым с b и единственным по модулю n. Последнее утверждение означает: если ab 1 (mod n), тогда b b (mod n).

Доказательство. Если ab 1(mod n), тогда ab = 1 + k n, так что некоторый общий множитель а и n должен делить 1, что даёт (a, n) = (аналогично (b, m) = 1). Обратно, если (а, n) = 1, тогда, используя алгоритм Евклида, найдём такие целые числа b и k, что ab + n k = 1. Для этого b Для нахождения числа а необходимо решить сравнение Это эквивалентно нахождению таких значений целых чисел х и k, что Существует три основных способа нахождения числа а, обратного числу b по модулю n:

1. Проверять путем поочередной подстановки чисел натурального ряда в формулу, пока не будет найдено число а, удовлетворяющее 2. Используя фи-функцию Эйлера (n), можно вычислить 3. С помощью расширенного алгоритма Евклида.

В этом случае при решении сравнения a х 1 mod n алгоритм Евклида позволяет найти а ( 1)Qk 1 (mod n), где Qk 1 — знаменаа тель предпоследней подходящей дроби разложения в непрерывную дробь.

Непрерывная дробь имеет вид:

где qi — частное в цепочке следующих равенств:

где ri — остатки от деления.

Поскольку остатки от деления ri в алгоритме Евклида представляют собой строго убывающую последовательность натуральных чисел, то обеспечивается сходимость представленного алгоритма. При этом получается, что rk — общий делитель чисел а и n. Любой общий делитель чисел а и n делит и rk. Таким образом, rk =( а, n).

Последовательности {Рm } и {Qm } числителей и знаменателей подходящих дробей в непрерывной дроби определяются рекуррентно:

Для решения более сложных сравнений a у 1 (mod n), т.е. определяют у а (mod n), а затем находят х а 1b(mod n) у b(mod n).

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

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

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

Информация в виде позиционного двоичного кода представляет собой набор из k разрядов для представления любого целого числа х между и 2 1, а именно, x = (d k d k 1...d 2 d1 ) по основанию 2. Веса 2 в этом представлении являются целыми степенями по этому числовому основанию (j = 1, 2, …, k).

Рассмотрим теперь использование ряда весов w1, w2,..., wn для представления n—разрядного числа x = (ck ck 1...c2 c1 ) в том же виде, а именно:

Для данных положительных целых чисел порядка s (где s n), выбеs) рем веса w j Для s = 2, например, получим весовую последовательность: w1=1, w1 = 2, w1 = 3, w1 = 5, w1 = 8, w1 = 13 и т. д. Эта последовательность является известными числами Фибоначчи.

Эта конструкция получается по индукции, т.е. итеративно, и генерирует представление х сначала наиболее значимым разрядом с дальнейшим понижением веса последующих разрядов. Пусть yn = x, тогда образуем последовательно числа y n 1, y n 2,..., y1 в соответствии с алгоритмом Иными словами, число х последовательно уменьшается с помощью некоторых коэффициентов последовательности wn, wn 1,..., w1, взятых в порядке понижения их веса, пока не достигнем отрицательного результата.

Если вес wj в настоящее время вычитается из текущей разности, тогда сj = 1;

в противоположном случае сj = 0. Например, если s = 2, n = 6 и х = 19, тогда эта конструкция получается из весовой последовательности 13, 8, 5, 3, 2, 1 (выписанной ранее), представление 1910 = (1010012) получается следующим образом:

делителей, включая 1, но исключая само число n, равно самому n.

Существует связь между совершенными числами и простыми числами Мерсенна.

Если известно разложение числа на простые множители, то можно указать все делители этого числа, а также найти их сумму, которую обозначим через (n), где n — само число. При этом для совершенных чисел справедлива формула (n) = 2n.

Прежде чем выявить связь между совершенными числами и простыми числами Мерсенна, полезно описать метод, позволяющий определить, является ли число вида M(m) = 2 – 1 действительно простым.

Теорема. Пусть р будет нечётным простым числом, а q будет проq стым числом. Предположим, что q | (2 – 1). Тогда q имеет вид 1 + 2kp для целого числа k. Все делители 2р – 1, простые или составные, будут иметь такой же вид.

Доказательство. Исходя из малой теоремы Ферма, q | (2 – 1), так равенство 1. Это приводит к (q – 1) = rp, но р является нечётным, а (q – 1) является чётным, так что r должно быть чётным числом, скажем, r = 2k. Из последнего утверждения следует, так как если q1 1 и q 1 (mod 2p), тогда q1 · q2 1 (mod 2p).

Для примера выберем р = 31, что означает, что любой делитель числа (2 – 1) должен иметь вид (1 + 62k), так что простота числа 2 – может быть проверена быстро путём пробного деления на числа этого специального вида.

Теорема о чётных совершенных числах. Если n является чётным совершенным числом, тогда существует m такое, что 2 – 1 является проm-1 m стым числом, а n = 2 (2 – 1).

Доказательство. Предположим, что n является чётным совершенs ным числом и представимо как n = 2 t, где t является нечётным числом.

Тогда так что 2 | (t). Возьмем, скажем, (t)= 2 q. Продолжим далее, чтобы показать, что q = 1.

Предположим, что q > 1, так что t = (2 – 1)q, Тогда q является собственным множителем t, a t имеет различные множители 1, q, t (и, возможно, другие), обеспечивая (t) 1 + q + t, С другой стороны, Это противоречие доказывает, что q = 1, обеспечивая t = 2 – 1, и (t) = 1 + t. Последнее уравнение показывает, что t — простое число, так что n = 2 (2 – 1), где второй сомножитель является простым.

Таким образом, существует тесная связь между чётными совершенными числами и простыми числами Мерсенна. Значения m, при которых число становится простым, сами все являются простыми. Приведем несколько первых простых чисел Мерсенна при m = 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127,521, 607, 1279, 2203, 2281, 3217, 4253,...

При разложении составного числа на нечетные простые множители часто используют числа Кармайкла.

Числом Кармайкла называется составное число n, которое удовлеn- творяет сравнению b 1 (mod n) для всех b, являющихся взаимно простыми с n (в честь Р. Д. Кармайкла, который предложил их в 1912 г.).

Конечно, давая определение, мы не доказали, что такие числа существуют, но приведём пример. Пусть n = 561 = 3 · 11 · 17. Таким образом, (b, 561) = 1 означает, что (b, 3) = (b, 11) = (b, 17) = 1. Используя малую теорему Ферма, b2 1 (mod 3) предполагает, что b 560 = (b2)280 1 (mod 3);

b10 1 (mod 11) означает, что b560 = (b10)56 1 (mod 11);

b16 1 (mod 17) означает, что b560 = (b16)35 1 (mod 17).

Так как 3, 11 и 17 являются тремя различными простыми числами, то это означает, что b 1 (mod 561).

Теорема. Пусть n = q1 q2... qk, где qi — различные простые числа и k 2. Предположим, что для каждого i, (qi – 1) | (n – 1). Тогда n будет числом Кармайкла.

Заметим, что простые числа должны быть нечётными, так как, если q1 = 2, тогда n — чётное, а q2, будучи нечётным, не удовлетворяет условию (q2 – 1) | (n – 1).

Наряду с определением, приведенным ранее, криптосистемой называют совокупность A = { X, K, Y, E, D} множеств, для которых выполняются следующие свойства [5] :

Dk ( Ek ( x)) = x ;

Здесь: X, Y, K — конечные множества возможных открытых текстов, шифрованных текстов и ключей соответственно;

Ek : X Y — правило зашифрования на ключе k K ; множество Dk : Ek ( X ) X — правило расшифрования на ключе k K, и Обычно предполагают, что если k K представляется в виде k = (ko ; k s ), где ko – открытый ключ для зашифрования информации, а k s — секретный ключ для расшифрования (причем k s ko ), то Ek понимается как функция Ek o, а Dk — как функция Dk s.

Условие 1 отвечает требованию однозначности расшифрования (принцип обратимости).

Условие 2 означает, что любой элемент y Y может быть представлен в виде y = Ek (x) для подходящих x X и k K. Отметим также, что в общем случае утверждение «для любых k K и y Ek ( X ) выполняется равенство Ek ( Dk ( y )) = y » является неверным.

Совокупность множеств — алгебраическая модель шифра.

Определение. Целое x, удовлетворяющее сравнению a b(mod n), называется дискретным логарифмом числа b по модулю n и по основанию a.

Криптосистема Эль Гамаля была предложена в 1985 году американцем арабского происхождения Тахер Эль Гамалем. Данная система базируется на сложности решения задачи дискретного логарифмирования, то есть определении числа x при известных параметрах a, b и n в сравнении a b(mod n).

A = { X, K, Y, E, D} шифрсистема Эль Гамаля определяется следующим образом.

Обозначим: Z p = {0;1; 2;... ; ( p 1)} — множество чисел, представляющее собой полную систему вычетов для некоторого простого числа p ;

Z * — множество обратимых элементов совокупности Z p ; X = Z *, Правило зашифрования определяется следующей формулой:

Ek o ( M ) = (C1; C2 ), где M — открытый текст; (C1; C2 ) — шифр.

тор — случайное целое число из интервала 1 r ( p 2), необходимое для реализации схемы вероятностного шифрования, при которой зашифрование одинаковых блоков открытого текста будет давать различные шифрованные тексты (открытый текст и ключ не определяют шифрованный текст однозначно).

Правило расшифрования:

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

Доказательство корректности алгоритма Эль Гамаля Требуется доказать выполнимость условия обратимости:

Действительно [5] :

Здесь учтено, что M < p и [ ( ) ] mod p = 1.

Необходимость использования различных значений рандомизатора r C2 (C2 ) 1 = M ( M * ) 1, т.е. открытый текст M * может быть вычислен по известному M.

Так как криптостойкость системы Эль Гамаля определяется сложностью решения задачи дискретного логарифмирования в совокупности Z p, то следует учесть, что в настоящее время эта задача неразрешима при p, содержащем примерно 300 десятичных цифр. Рекомендуется также, чтобы число ( p 1) содержало большой простой делитель.

Вероятностный характер шифрования может быть отнесен к достоинствам системы Эль Гамаля, такие схемы обладают, как правило, большей криптостойкостью, чем детерминированные алгоритмы.

Недостатком системы является удвоение длины шифрованного текста по отношению к открытому тексту.

5. Криптосистема RSA (R. Rivest, A. Shamir, L. Adleman) Наиболее широкое признание и применение в современном мире получила схема шифрования с открытым ключом RSA, аббревиатура которого исходит от фамилий авторов Р. Л. Ривеста, А. Шамира и Л. М. Адлемана. Основой надёжности этого метода является огромная трудность факторизации очень больших целых чисел. Метод также требует использования очень больших простых чисел (150-значных и более), которые практически находятся вероятностными методами, подобными изложенным ранее.

Основы создания криптосистемы RSA, рассматриваемой далее, берут своё начало из экспоненциального шифрования [10]. Они были открыты С.

Полигом и М. Хэллманом [9;10]. Идея довольно проста. Выбирается простое число р и ключ кодирования е, который является взаимно простым с ( p ) = p 1. Блок открытого текста, который предполагается зашифровать, сначала преобразуется в числовую форму (один из методов осуществления этого приведён ниже), а потом разбивается на подблоки цифр, которые, если рассматривать их как обычные числа, будут < р.

Предположим, например, что р = 37 781, а подблоки цифр сообщения в числовом виде выглядят как Чтобы зашифровать это послание, заменим каждое четырёхзначное число Mi (существующее «открытым текстом» в виде четырёхзначных чиe сел) на Ci Mi (mod p), 0 < Ci < p. Таким образом, выбирая е = 367 (которое является взаимно простым числом с р – 1 = 37 780 = 22 · 5 ·1889), зашифрованной формой будет (т. е. 8069 37 059 (mod p)).

Как может быть это послание расшифровано, т.е. возвращено к первоначальной цифровой форме и, далее, к обычному языку? Пусть d (ключ расшифрования) будет таким, что de 1 (mod( p – 1)). То есть d просто представляет собой инверсию е по модулю (p – 1), так как (е, р – 1) = 1, и которая может быть вычислена методами определения обратных по модулю величин. В представленном случае d = 3603. Теперь согласно малой теореме Ферма, так как (p – 1) | (ed – 1). Таким образом, возводя каждое (пятизначное) зашифрованное число в степень d и приводя по mod p, мы раскроем первоначальное (четырёхзначное) число. То есть (37 0593603) mod p = 8069 и т. д.

Чтобы использовать этот метод для отправки секретных посланий между двумя людьми А и В, которые оба желают знать р (вся шифрация производится по модулю p), А необходимо выбрать шифровальный ключ е, в то время как В должен произвести соответствующую расшифровку ключом d. Конечно, В может выбрать другой шифровальный ключ е для отправки посланий А, так как А знает соответствующий ключ расшифровки d, для которого d e 1 (mod (p – 1)).

Раскрытие этого шифра достаточно сложно, даже если р известно и если соответствующие открытый текст M и зашифрованный текст С изe вестны, так что C M (mod p ). Проблема заключается в том, что не существует простого способа определения е из такого сравнения, когда р представляет большое простое число.

Если простое число р и ключ шифрования (экспоненциального) е являются оба раскрытыми в экспоненциальном шифровании, тогда, конечно, всё потеряно (или найдено): ключ расшифрования может быть просто найден как инверсия е по модулю р – 1. Метод криптографии с открытым ключом является искусным способом посылки секретных сообщений между двумя (или другим каким-либо числом) людьми, даже когда ключи шифрования открыты (отсюда название), потому что нахождение ключей для расшифрования является вычислительно трудной задачей.

Сама идея достаточно проста. Если два абонента сети, которых обозначим А и В, соответственно, хотят установить скрытую связь, каждый выбирает два больших простых числа: pR, qR и pG, qG. Пусть nR = pR qR, nG = pG qG. Числа nR и nG могут быть известны окружающим, так как используемые простые числа достаточно большие. Каждый выбирает ключ шифрования: еR и еG, каждый из которых будет взаимно простым с ( nR ), (nG ), соответственно. (Заметим, что ( pq ) = ( p 1)(q 1), когда p и q являются простыми). Эти шифровальные ключи могут также быть известны окружающим. Каждый человек, знающий свои р, q и е, может просто рассчитать инверсию d для е по модулю (n). Но посторонний человек, знающий только n и е, имеет незначительный шанс вычислить d без действительного разложения на простые сомножители n, а А реально не в состоянии вычислить dG, а В не сможет определить dR.

Когда А захочет послать сообщение В, он преобразует его обычным способом в числовые блоки. Он также использует шифровальный ключ В еG (который, как все шифровальные ключи, общеизвестен), чтобы зашифровать каждый блок Р в соответствии с правилом шифрования EG:

Заметим, что, выполнив это шифрование, А будет не в состоянии расшифровать его снова, так как он не знает dG. Однако В будет находиться не в таком безнадёжном положении: зная оба dG и nG, он сможет расшифровать с помощью правила расшифрования:

Таким образом, DG (ЕG(Р)) Р (mod nG) на основе тех же самых аргументов, какие были использованы в случае экспоненциального шифрования.

Конечно, когда В пожелает отправить послание R, он использует правило шифрования а А расшифрует согласно правилу расшифровки DR (С ) С (mod nR ).

Снова DR (ЕR(Р)) Р (mod nR). Вспомните, что А знает ER, EG и DR, в то время, как В знает ER, EG и DG.

Важной частью написанного послания является подпись, чью индивидуальность подтверждает получатель тем, что сообщение действительно получено от персоны, которую затребовал отправитель. Удивительно, что возможно послать подпись, используя также открытый метод RSA шифрования. Предположим, что nR < nG (конечно, оба А и В знают об этом) и то, что А желает послать подпись В, т. е. последовательность символов в конце послания, которую В должен сделать, чтобы раскрыть смысл послания, которое могло бы прийти только от А. Предположим, что в действительности подпись представляет собой один блок открытого текста Р. Тогда А зашифровывает его с помощью представления DR(P) в меньших блоках перед дальнейшим шифрованием его как S. В конце этого сообщения А тогда посылает подпись S. Когда получатель В расшифрует конец послания, используя ключ расшифрования d G, получается настоящая тарабарщина, а именно:

(конечно, DR(P) является числом). Бессмыслица получится, когда В будет стремиться превратить эти числа в слова. Предполагая, что это является подписью, он для этого использует Е R, которое раскрывает В; когда оно переводится в слова, то приобретает смысл. Заметим, что только отправитель А знает DR, так что только он может послать специфическую тарабарщину DR в конце послания.

Доказательство корректности алгоритма RSA [5] Определение. Пусть n = p q, где p и q — простые числа. Пусть X = Y = Z n –– множество открытых текстов, которое по объему совпадает с множеством шифрованных текстов и равняется полной системе вычетов по модулю n.

Предположим, что ключевое пространство имеет вид () — функция Эйлера, (e, (n)) = 1. Представим ключ k K в виде k = (ko ; k s ), где ko = (n, e) — открытый ключ; k s = (d ) — секретный ключ.

Правила зашифрования и расшифрования в системе RSA определим следующим образом для x X и y Y :

Пусть, в соответствии с определением криптосистемы RSA, n = p q, Для любого целого числа x и простого p по малой теореме Ферма Если ( x, p ) = p, то p | x, следовательно, x 0(mod p ). Отсюда следует (5.4).

Если ( x, p ) = 1, то по малой теореме Ферма x 1(mod p ). Отсюда также следует (5.4).

Из соотношения (5.1) следует e d = k ( n) + 1, k > 0 целое. Отсюда и из (5.3) получаем следующую цепочку равенств и сравнений:

Чтобы доказать сравнение y x(mod n), используем следующую лемму.

Лемма. Пусть a, b, c — натуральные числа, причем ( a, b) = 1, т.е. a и b –– взаимно простые. Тогда: 1) если b |( a c ), то b | c ;

В нашем случае a = p, b = q, ( p, q ) = 1, То есть y x(mod n) для всех x, включая те, для которых ( x, n) 1.

Тремя возможными подходами к криптоанализу алгоритма RSA являются следующие:

1) простой перебор, который предполагает проверку всех возможных 2) математический анализ. Существует несколько подходов такого рода, но все они, по сути, эквивалентны нахождению множителей произведения двух простых чисел;

3) анализ временных затрат, который опирается на анализ времени выполнения алгоритма расшифрования.

Защита против простого перебора в случае RSA остается той же, что и для других криптосистем, — использование большого пространства ключей. С этой точки зрения, чем больше разрядность е и d, тем надежнее защита. Однако из-за сложности вычислений, как при генерировании ключей, так и при шифровании/расшифровании: чем большим оказывается размер ключа, тем медленнее работает криптосистема.

Математический анализ обеспечивает три различных подхода к криптоанализу RSA:

1) разложение n на два простых его множителя. Это позволит вычислить ( n) = ( p 1)(q 1), на основании чего можно будет 2) определение непосредственно (n) без предварительного опреp и q. Это также позволит определить 3) определение непосредственно d без предварительного определения (n).

Чтобы избежать выбора значений n, которые могут быть разложены на множители с малыми затратами, предлагается следующие ограничения относительно p и q:

1) значения p и q должны различаться по длине на несколько разрядов;

2) как ( p 1), так и ( q 1) должны содержать в своих разложениях достаточно большой простой множитель;

3) НОД ( p 1, q 1) должен быть достаточно малым.

Кроме того, доказано, что если e < n и d < n4, достаточно легко.

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

1) постоянное время возведения в степень. Этого можно добиться увеличением этого времени до определенного уровня, одинакового для всех случаев;

2) случайные задержки;

3) маскировка. Умножение шифрованного текста на случайное число перед тем, как выполнять возведение в степень.

В некоторых продуктах RSA Data Security предлагается возможность использования функции маскировки. В них операция М = С mod n с личным ключом выполняется следующим образом:

1) генерируется секретное случайное число r в диапазоне от 0 до n – 1;

2) вычисляется С С (mod n), где е является открытым значениre ем показателя степени;

3) вычисляется М (С ) (mod n) для обычной реализации RSA;

ляет собой мультипликативное обратное значение r mod n. Результат будет корректным, если выполнится равенство При использовании маскировки общая производительность продукта RSA Data Security снижается на 2...10 %.

6. Методы распределения криптографических ключей Для распределения ключей используют несколько методов, которые можно сгруппировать в следующие классы [8; 11; 12] :

1) публичное объявление;

2) публично доступный каталог;

3) авторитетный источник открытых ключей;

4) сертификаты открытых ключей.

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

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

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

Такая схема включает следующие элементы:

1) уполномоченный объект поддерживает каталог с записями, включающими имя и открытый ключ для каждого участника;

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

3) любой участник может заменить существующий ключ новым в любой момент или из-за того, что открытый ключ был где-то уже использован для пересылки достаточно большого объема данных или из-за компрометации ключа;

4) периодически объект, уполномоченный вести каталог, публикует весь каталог или дополнения к нему;

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

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

Авторитетный источник открытых ключей. Эта схема предполагает наличие некоторого центрального объекта, уполномоченного поддерживать динамический каталог открытых ключей всех участников обмена данными. Кроме того, каждому из участников достоверно известен открытый ключ центра, но только центр знает соответствующий личный ключ.

При этом выполняются следующие действия:

1) инициатор А посылает сообщение с меткой даты/времени авторитетному источнику открытых ключей с запросом о текущем открытом ключе участника В;

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

— открытый ключ участника В, который участник А может использовать для шифрования сообщений, предназначенных для получателя В;

— оригинальный запрос, чтобы сторона А имела возможность сопоставить ответ с ранее отправленным запросом и убедиться, что запрос не был изменен на пути к авторитетному источнику;

— оригинальную метку даты/времени, чтобы отправитель А мог удостовериться, что это сообщение не является одним из старых сообщений от авторитетного источника, содержащим ключ, отличный от текущего открытого ключа 3) инициатор А сохраняет открытый ключ участника В и использует его для шифрования сообщения, направляемого получателю В и содержащего идентификатор отправителя А и оказию, которая выступает в качестве уникальной метки 4) респондент В получает открытый ключ участника А от авторитетного источника точно таким же способом, каким отправитель А получил открытый ключ получателя В;

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

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

1) любой участник должен иметь возможность прочитать сертификат, чтобы определить имя и открытый ключ владельца сертификата;

2) любой участник должен иметь возможность проверить, что сертификат исходит из авторитетного источника сертификатов и не является подделкой;

3) только авторитетный источник сертификатов должен иметь возможность создавать и изменять сертификаты.

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

Для участника А авторитетный источник обеспечивает сертификат вида где KRавт — личный ключ, используемый авторитетным источником;

KU В — открытый ключ участника В; IDА — идентификатор участника А;

Т — дата/время отправления. Участник А может переслать этот сертификат любому другому участнику, который прочтет и примет сертификат:

где KU авт — открытый ключ авторитетного источника; KU А — открытый ключ участника А.

Так как сертификат можно прочитать только с помощью открытого ключа авторитетного источника сертификатов, это дает гарантию того, что сертификат пришел именно от авторитетного источника. Элементы IDА и KU А сообщают получателю имя и открытый ключ владельца сертификата. Метка даты/времени Т определяет срок действия сертификата. Метка даты/времени должна быть защищена от следующей последовательности действий. Нарушитель узнает личный ключ А. По этой причине А генерирует новую пару ключей (личный и открытый) и обращается к авторитетному источнику сертификатов за новым сертификатом. Тем временем нарушитель воспроизводит сообщение со старым сертификатом и отсылает его В. Если В будет шифровать сообщения, используя старый скомпрометированный ключ, нарушитель сможет прочитать это сообщение.

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

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

Сущность предложенной схемы заключается в следующем. Если инициатор А намерен обменяться данными с пользователем В, то предлагается следующая процедура:

1) сторона А генерирует пару (открытый/личный) ключей ( KU А, KRА ) и передает сообщение стороне В, содержащее KU А и идентификатор отправителя А IDА ;

2) получатель В генерирует секретный ключ К и передает этот ключ инициатору сообщения А зашифрованным с помощью открытого 3) пользователь А вычисляет DKRА [ EKU А [ К S ]], чтобы восстановить секретный ключ. Поскольку только пользователь А может расшифровать это сообщение, только два участника обмена А и В будут знать значение К А ;

4) участник А уничтожает ключ KRА, а участник В — ключ KU А.

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

Этот протокол уязвим в отношении активных атак. Если нарушитель Е имеет возможность внедрения в канал связи, то он может скомпрометировать связь без того, чтобы быть обнаруженным, следующим образом:

1) участник А генерирует пару открытый/личный ключи ( KU А, KRА ) и передает сообщение адресату В, содержащее KU А и идентификатор участника А IDА ;

2) нарушитель Е перехватывает сообщение, создает собственную пару открытый/личный ключи ( KU Е, KRЕ ) и передает сообщение адресату В, содержащее KU Е, IDА ;

3) В генерирует секретный ключ К S и передает ЕKU Е [К S ];

4) нарушитель Е перехватывает это сообщение и узнает К S, вычисляя DKR Е [ E KU Е [ К S ]] ;

5) нарушитель передает участнику А сообщение Е KU А [К S ].

В результате оба участника А и В будут знать К S, но не будут подозревать, что К S также известен нарушителю Е. Поэтому стороны А и В могут начать обмен сообщениями, используя К S. Нарушитель Е больше не будет активно вмешиваться в канал связи, а просто будет перехватывать сообщения. Зная К S, нарушитель может расшифровать любое сообщение, а участники А и В не будут подозревать о существовании проблемы. Таким образом, простой протокол оказывается полезным только в случае пассивного перехвата сообщений.

с обеспечением конфиденциальности и аутентификации Схема, представленная на рисунке 3, обеспечивает защиту как от активной, так и пассивной атаки.

Будем исходить из того, что А и В уже обменялись открытыми ключами по одной из схем, описанных выше. Далее предполагается выполнить следующие действия:

1) сторона А использует открытый ключ В для пересылки стороне В шифрованного сообщения, содержащего идентификатор участника А ( IDА ) и оказию ( N1 ), используемую для идентификации данной транзакции;

2) пользователь В посылает сообщение пользователю А, зашифрованное с помощью KU А, содержащее полученную от него оказию ( N1 ) и новую оказию ( N 2 ), сгенерированную пользователем В.

Присутствие N1 в сообщении убеждает участника А в том, что респондентом является сторона В;

3) сторона А возвращает N 2, шифруя сообщение открытым ключом стороны В, гарантируя В, что респондентом является сторона А;

4) участник А выбирает секретный ключ К S и посылает участнику В сообщение М = Е KU В Е KRА [К S ]. Шифрование этого сообщения открытым ключом стороны В гарантирует, что только участник В сможет прочитать его, а шифрование личным ключом участника А, — что только участник А мог послать его;

5) сторона В вычисляет DKU А Е KR В [М ], чтобы восстановить секретный ключ.

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

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

— скорость выполнения процедуры. Этой логике соответствует много приложений, особенно ориентированных на передачу транзакций, где сеансовые ключи должны меняться очень часто. Распределение сеансовых ключей с помощью схемы с открытым ключом могло бы сделать производительность системы слишком низкой из-за относительно высоких требований к вычислительным ресурсам при шифровании и расшифровании по данной схеме. В случае трехуровневой иерархии шифрование с открытым ключом применяется лишь иногда, чтобы изменить главный ключ, разделяемый пользователем и ЦРК;

— обратная совместимость. Гибридную схему можно легко реализовать в виде расширения уже имеющейся схемы, предполагающей использование ЦРК с минимальными изменениями предусмотренной процедуры и программного обеспечения.

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

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

Сам по себе алгоритм ограничивается обменом ключей.

Эффективность алгоритма Диффи — Хеллмана опирается на трудность вычисления дискретных логарифмов.

Обмен ключами по схеме Диффи — Хеллмана происходит следующим образом. В этой схеме имеются два открытых числа : простое число q и целое, являющееся первообразным корнем q. Предположим, что пользователи А и В намерены обменяться ключами. Пользователь А выбирает случайное целое число Х А < q и вычисляет YА А (mod q ). Точно также пользователь В независимо выбирает случайное целое число Х В < q и вычисляет YВ Х В (mod q ). Каждая сторона сохраняет значение Х в тайне и делает значение Y свободно доступным другой стороне.

Пользователь А вычисляет ключ по формуле К (YВ ) А (mod q ), а польХ зователь В — по формуле К (YА ) В (mod q ). По этим двум формулам вычисления дают одинаковые результаты, как следует из вычислений.

Обе стороны обменялись секретными ключами. Поскольку при этом ХА и Х В были только в личном пользовании и поэтому сохранялись в тайне, нарушителю придется работать только с q,, А и В. Таким образом, нарушителю придется вычислять дискретный логарифм, чтобы определить ключ Х В = ind, q (YВ ).

После этого он сможет вычислить ключ К точно так же, как это делает пользователь В.

Защищенность обмена ключами по схеме Диффи — Хеллмана опирается на высокую трудность нахождения дискретного логарифма большого простого числа.

Для примера выберем простое число q = 97 с первообразным корнем = 5. Пользователи А и В выбирают секретные ключи Х А = 36 и Х В = 58, соответственно. Каждый вычисляет открытый ключ:

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

Имея 44 и 50, нарушителю не удастся с легкостью вычислить 75.

На рисунке 4 представлен простой протокол, в котором применяются вычисления в соответствии со схемой Диффи — Хеллмана [9]. Предположим, что пользователь А собирается установить связь с пользователем В и использовать секретный ключ, чтобы зашифровать сообщения, передаваемые с помощью такой связи. Пользователь А может сгенерировать одноразовое секретное значение Х А, вычислить значение А и отослать последнее пользователю В. В ответ пользователь В генерирует секретное значение Х В, вычисляет B и посылает B пользователю А. Оба пользователя теперь могут вычислить их общий ключ. Необходимые открытые значения q и должны быть известны заранее. Пользователь А может также выбрать эти значения на свое усмотрение и включить их в первое сообщение.

Можно рассмотреть другой пример использования алгоритма Диффи — Хеллмана для группы пользователей локальной сети. В этом случае каждый пользователь должен сгенерировать секретное значение Х А для долгосрочного применения и вычислить открытое значение А. Все полученные таким образом открытые значения вместе с открытыми глобальными значениями q и сохраняются централизованно в некотором каталоге. В любой момент пользователь В может получить доступ у открытому значению пользователя А, вычислить секретный ключ и использовать его для пересылки шифрованного сообщения пользователю А.

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

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

Это породило множество проблем, особенно для узлов связи, специализирующихся на электронной коммерции, где требуется защита больших транзакций. В связи с этим появился конкурент RSA — это криптография на основе эллиптических кривых (ЕСС — Elliptic curve cryptography). Появились стандарты по криптографии с открытым ключом ЕСС, например, IEEE P1363.

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

Свойства эллиптических кривых. Эллиптические кривые описываются кубическими уравнениями следующего вида:

где a, b, c, d, g являются целыми числами.

Определение эллиптической кривой включает некоторый элемент, обозначаемый О и называемый несобственным элементом (точкой бесконечности, нулевым элементом).

Из определения эллиптической кривой следует, что если три точки эллиптической кривой лежат на одной прямой линии, то их сумма есть О.

Из этого определения вытекают следующие правила сложения над точками эллиптической кривой:

1) объект О выступает в роли нулевого элемента при сложении, т.е.

О = – О и для любой точки на эллиптической кривой Р + О = Р;

2) вертикальная линия пересекает эллиптическую кривую в двух точках с одной и той же абсциссой х. Эта линия пересекает кривую и Р1 = ( х, у ), Р2 = ( х, у ). Точкой со знаком «минус» является точка с той же координатой х, но с противоположным по знаку координатой у;

3) чтобы сложить две точки Q и R с разными координатами х, необходимо провести через эти точки прямую и найти третью точку пересечения Р1 этой прямой с эллиптической кривой. Существует только одна точка, если прямая не является касательной к эллиптической кривой в какой-либо из точек. В таком случае нужно положить Р1 = Q или Р1 = R, соответственно. Затем нужно воспользоваться выражением Q + R= – Р1 ;

4) чтобы удвоить точку Q, необходимо провести касательную в точке Q и найти другую точку пересечения S. Тогда Q + Q = 2Q = – S.

Вышеприведенные свойства сложения подчиняются всем обычным свойствам сложения, например, коммутативному и ассоциативному законам. Умножение точки Р эллиптической кривой на положительное число k также определено: это сумма k копий точки Р. Так, 2Р = Р + Р, 3Р = Р + +Р + Р и т. д. Следовательно, в случае криптографии с использованием эллиптических кривых приходится иметь дело с редуцированной формой эллиптической кривой, которая определяется над конечным полем.

Особый интерес для криптографии представляет объект, называемый эллиптической группой по модулю р, где р является простым числом. Такая группа определяется следующим образом. Выберем два неотрицательных целых числа а и b, которые меньше р и удовлетворяют условию (детерминанту) тогда Е р ( а, b) обозначает эллиптическую группу по модулю р, элементами которой являются пары неотрицательных целых чисел (х, у), которые меньше р и вместе с точкой в бесконечности О удовлетворяют условию Эллиптическая кривая над полем действительных чисел с ненулевым дискриминантом представляет собой гладкую кривую, в каждой точке которой можно провести касательную. В случае характеристики 2 существуют две разновидности эллиптических кривых: суперсингулярные и несуперсингулярные. Суперсингулярные — это эллиптические кривые, для которых левая часть уравнения (7.1) имеет вид у + by. Несуперсингулярные — это эллиптические кривые, для которых левая часть уравнения (7.1) имеет вид у + аху. Эллиптической кривой соответствует эллиптический интеграл, не берущийся в элементарных функциях.

у 2 х3 + х + 1. Детерминант (4 13 + 27 12 ) mod 23 = 8 0, что удовлетворяет условиям эллиптической группой по модулю 23.

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

Нахождение точек на эллиптической кривой производится по следующему алгоритму:

1) для каждого значения х, удовлетворяющего 0 x < p, вычисляется 2) для каждого из полученных на предыдущем шаге значений выясняется, имеет ли это значение корень квадратный по модулю р.

Если нет, то во множестве Е р ( а, b) нет точек с этим значением х.

Если корень существует, то имеются два значения у, соответствующих операции извлечения квадратного корня (исключение составляет случай у = 0). Эти значения (х, у) и будут точками Правила сложения в Е р ( а, b) соответствуют геометрическим приемам, которые могут быть записаны следующим образом :

2) если Р = ( х, у ), то Р + ( х, у ) = О. Точка ( х, у ) является отрицательным значением точки Р и обозначается (–Р). Точка ( х, у ) лежит на эллиптической кривой и принадлежит Е р ( а, b) ;

определяется в соответствии с правилами где Для примера рассмотрим следующий случай. Пусть Р = (0,0) на эллиптической кривой Требуется найти 2Р = Р + Р, 3Р= Р + Р + Р.

Решение. Преобразуем уравнение эллиптической кривой путем замены переменных у = у 1 2 и х = х + 1 3 к виду На этой кривой точка Р становится точкой Q = (–1/3, ). Используя формулы удвоения, получим 2Q = (2 / 3, –). Далее вычисляем 3Q = (2 / 3, ).

Заметим, что 3Q = –(2Q), и следовательно, Q является точкой порядка 5, т.е. 5Q = О. Возвращаясь к исходной кривой, имеем 2 Р = (1,1), 3Р = (1,0) = 2 Р.

Не трудно показать, что операция сложения точек эллиптической кривой коммутативна и ассоциативна, т.е. множество точек вместе с точкой бесконечности О образует абелеву группу. Такое доказательство получают в проективной геометрии с использованием следующего утверждения:

если три прямые L1, L2, L3 пересекают кубическую кривую в девяти точках Р1, Р2,..., Р9 с возможностью совпадения и пусть L1, L2, L3 — три прямые, пересекающие эллиптическую кривую в точках Q1, Q2,..., Q9, при этом Рi = Qi, i = 1,8, то также Р9 = Q9.

Более естественно точка бесконечности определяется в проективных координатах.

Проективной плоскостью над полем F называется множество классов эквивалентности троек ( X, Y, Z ), в которых хотя бы один элемент ненулевой. Эквивалентными считаются тройки, если элементы одной из них получаются умножением на скаляр другой: ( X, Y, Z ) ( X, Y, Z ), если для некоторого элемента F (X, Y, Z ) = ( X, Y, Z ), такие классы эквивалентности называются проективными точками. Проективные точки с ненулевым элементом Z принадлежат классу эквивалентности, содержащему единственную точку вида ( х, у, 1). Она просто вычисляется х = X / Z, у = Y / Z. Таким образом, проективная плоскость может быть определена как множество всех точек ( х, у ) обычной (аффинной) плоскости с дополнением точек, для которых Z = 0. Эти точки можно представить как линию в бесконечности и рассматривать эту линию как «горизонт» плоскости. Всякое уравнение G ( X, Y ) = 0 кривой в аффинной плоскости соответствует однородному уравнению G ( X, Y, Z ) = 0 для соответствующих проективных точек: просто заменим по схеме х = X / Z, у = Y / Z и умножим на степень Z, чтобы избавиться от знаменателей.

Например, если применить эту процедуру к аффинному уравнению эллиптической кривой у = х + ах + b, то получится проективное уравнение Y 2 Z = X 3 + аXZ 2 + bZ 3. Это уравнение выполняется для проективной тройки ( X, Y, Z ), Z 0 тогда и только тогда, когда соответствующая аффинная точка ( х, у ), где х = X / Z, у = Y / Z удовлетворяет уравнению эллиптической кривой у = х + ах + b.

Какие еще проективные точки ( X, Y, Z ), кроме точек с Z 0, удовлетворяют уравнению G ( X, Y, Z ) = 0 ? Подставляя Z = 0 в уравнение, получаем Х = 0. Но имеется только один класс эквивалентности троек ( X, Y, Z ), где оба элемента Х и Z ненулевые — класс, содержащий (0, 1, 0).

Это и есть точка, которую обозначаем О. Это точка пересечения оси у с линией бесконечности.

Для эллиптической кривой характеристики 2 используются следующее представление:

1) для несуперсингулярного случая используется представление у 2 + а1ху = х3 + а2 х 2 + а6 и формулы при сложении различных точек выглядят так а при удвоении 2) для суперсингулярного случая используется представление у + а3 у = х + а4 х + а6 и формулы при сложении различных точек выглядят так а при удвоении Определим свойства эллиптических кривых над полем Галуа GF (2n ). Рассмотрим также суперсингулярные и несуперсингулярные эллиптические кривые, основное различие между которыми состоит в том, что для суперсингулярных кривых известен порядок (количество точек) соответствующей группы (в данном случае GF (2 ) ).

При нечетном n имеется 3 класса изоморфных суперсингулярных эллиптических кривых (при четном n имеется 7 классов), стандартными представлениями которых являются кривые:

При нечетном n число точек первой кривой равно 2 + 1 и 2n ± 2n +1 + 1 для второй и третьей (знак + или – выбирается в зависимости от кривой и от сравнения по модулю 8). Группы этих кривых при нечетном n являются циклическими. Указанные значения легко вычисляются с использованием теоремы Вейля.

Теорема Вейля. Пусть — эллиптическая кривая над полем Fq и m –– порядок ее группы. Тогда для порядка M (n) группы эллиптической кривой Fq n над любым полем Fq n, являющимся расширением поля Fq, справедлива формула где и — корни квадратного уравнения х tx + q = 0, в котором коэффициент t = q + m + 1.

По теореме Хассе [10] выполняется неравенство t 4q и в случае строгого неравенства корни квадратного уравнения и будут комплексными.

В качестве примера найдем порядок группы эллиптической кривой в случае 2. Рассматривая 2 над полем GF ( 2), получим на ней точки:

(0,0), (0,1), (1,0), (1,1) и нулевой элемент О — всего пять элементов циклической группы. Таким образом, q = 2, m = 5, t = – 2, откуда находим корни квадратного уравнения х + 2 х + 2 = 0 : = 1 + i и = 1 i или в тригонометрической записи комплексных чисел По теореме Вейля получим поскольку n ±3(mod 8).

Окончательно получаем Для определения порядка группы эллиптической кривой существуют другие методы : см. алгоритм Скуфа и др.

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

Операция сложения на основе эллиптических кривых является аналогом операции умножения по модулю простого числа в RSA, а многократное повторное сложение — аналогом возведения в степень. Криптографическую систему на основе эллиптических кривых строят на основе трудности решения проблемы разложения на множители произведения двух простых чисел. В одних случаях, например, для аддитивной группы, заданной на множестве вычетов целых чисел по модулю простого числа эта проблема легко решается с использованием процедуры на основе алгоритма Евклида. В других случаях, например, для мультипликативной группы на множестве классов вычетов положительных чисел по модулю простого числа субполиномиальные алгоритмы для этой проблемы неизвестны. Для группы точек эллиптической кривой трудность проблемы дискретного логарифма не уступает сложности этой проблемы в общей постановке для произвольной группы. Исключение составляют некоторые суперсингулярные эллиптические кривые, для которых проблема дискретного логарифма решается эффективно.

7.1. Аналог обмена ключами по схеме Диффи-Хеллмана Обмен ключами с использованием эллиптических кривых может быть выполнен следующим образом. Сначала выбирается большое простое число p и параметры а и b для эллиптической кривой в уравнении (7.1).

Это задает эллиптическую группу точек Е р ( a, b). Затем в Е р ( a, b) выбирается генерирующая точка G = ( х, у ). При выборе G важно, чтобы наименьшее значение n, при котором nG = O оказалось очень большим простым числом. Параметры Е р ( a, b) и G криптосистемы являются параметрами, известными всем участникам.

Обмен ключами между пользователями А и В можно провести по следующей схеме:

1) сторона А выбирает целое число n А < n. Это число будет личным ключом участника А. Затем участник А генерирует открытый ключ РА = n А G. Открытый ключ представляет собой некоторую точку из Е р ( a, b) ;

2) сторона В выбирает аналогично личный ключ nВ и вычисляет открытый ключ РВ = nВ G ;

3) участник А генерирует секретный ключ К = n А РВ, а участник В генерирует секретный ключ К = nВ РА.

Две формулы, полученные в п. 3) дают один и тот же результат, поскольку Чтобы взломать эту схему, нарушитель должен будет вычислить k по данным G и kG, что представляется трудным делом.

В качестве примера выберем р = 211, Е211 (0, – 4), что соответствует эллиптической кривой у = х 4 и G = ( 2,2). Нетрудно сосчитать, что 241G = О. Личным ключом участника А является n А = 121, поэтому открытым ключом участника А будет РА = 121( 2,2) = (115,48). Личным ключом участника В будет nВ = 203, поэтому открытым ключом участника В будет РВ = 203(2,2) = (130,203). Общим секретным ключом является 121(130, 203) = 203 (115, 48) = (161, 169).

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

7.2. Протокол обмена ключами по схеме Месси-Омуры Пусть Е — эллиптическая кривая порядка n, а е — некоторое целое, причем, (е, n) = 1, 1 < e < n. Используя алгоритм инвертирования, найдем Используем то свойство, что законы модулярной арифметики над целыми числами и над точками эллиптической кривой идентичны. Любую точку Р эллиптической кривой можно вычислить по формулам Очевидно, что Q = P. Протокол Месси-Омуры основан на этой идее, реализуемой с учетом трудности решения проблемы определения скалярного множителя, соответствующего данной точке эллиптической кривой относительно базовой точки, умножаемой на этот скаляр, т.е. на проблеме дискретного логарифма для эллиптических кривых.

Обмен ключами между пользователями А и В можно провести по следующей схеме:

1) сторона А выбирает целое число е А < n и вычисляет по формуле (7.2) d А. Это число е А будет личным ключом шифрования участника А. Число d А будет личным ключом расшифрования участника А.

Затем участник А помещает свое сообщение m в некоторую точку Рm эллиптической кривой и умножая на свое секретное значение е А получает точку (генерирует открытый ключ) 2) сторона В выбирает аналогично еВ и d В, которые являются личными ключами шифрования и расшифрования, соответственно, участника В. Затем участник В, умножая свое секретное значение еВ на открытый ключ Р А получает точку (генерирует открытый ключ) 3) это значение отсылается участнику А;

4) участник А вычисляет 5) и отсылает полученную точку В;

6) умножая полученную точку на свой секретный ключ расшифрования d В, участник В получает точку Рm, соответствующую сообщению m участника А:

Вычисляя РО, участник А снимает действие своего ключа шифрования :

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

7.3. Протокол распределения ключей Менезеса-Кью-Ванстона Данный протокол имеет принципиальное отличие от вышеперечисленных. Дело в том, что рассмотренные ранее протоколы не защищены от атаки так называемого «посредника». Под посредником здесь имеется в виду криптоаналитик, с самого начала контролирующий открытый канал связи участников А и В и мешающий их нормальному общению. Посредник способен, перехватывая сообщения, проходящие по открытому каналу, и посылая участникам А и В свои сообщения, создавать у легитимных абонентов впечатление нормальной работы протокола, в то время как на самом деле каждый из участников будет общаться непосредственно с посредником.