Асимметричные криптосистемы 1 страница

Методы криптоанализа ассиметричных криптосистем 67

Хеш-функции 57

Электронная подпись 35

Н.Я. Горбунова

Редакторы: Р.Д. Игнатова

Лабораторный практикум

ЦИФРОВАЯ СХЕМОТЕХНИКА

Евгений Леонидович Собакин

Условные обозначения и сокращения

Работа 5. Счётчики импульсов

Работа 4. Функциональные свойства регистров

Работа 3. Полные арифметические сумматоры

Работа 2. Функциональные свойства полных декодеров

Работа 1. Логические элементы

Общие сведения и требования

Работа 6. Мультиплексоры-селекторы (Часть 1)

Работа 7. Мультиплексоры-селекторы (Часть 2)

Литература

Приложение 1

Приложение 2

Научный редактор доцент, к.т.н. Цимбалист Э.И.

Подписано к печати 14.05.99.

Формат 60х84.16. Бумага писчая №2.

Плоская печать. Усл. Печ. Л. 5, 58. Уч. –изд. Л. 5.05

Тираж 200 экз. Заказ 213 Цена С.17

ИПФ ТПУ. Лицензия ЛТ №1 от 18.07.94.

Ротапринт ТПУ. 634034, Томск, пр. Ленина 30.

2.1. Электронная подпись на основе криптосистемы RSA 38

2.2. Электронная подпись на основе криптосистемы Эль Гамаля 39

2.3. Стандарты электронных подписей 42

2.4. Электронная подпись на основе решения системы сравнений 47

2.5. Коллективная и композиционная электронная подпись 51

2.6. Слепая электронная подпись 54

3.1.Требования к хеш-функции 58

3.2. Итерационные хеш-функции 59

3.3. Хеш-функции на основе симметричных блочных

криптоалгоритмов 65

4.1. Методы, основанные на алгоритмах разложения на множители 67

4.2. Методы, основанные на алгоритмах вычисления

дискретного логарифма 70

Литература 80

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

1.1. Общая характеристика и классификация асимметричных криптосистем

Определение 1.1. Под криптосистемой с открытым ключом понимают систему [6,7]:

, (1.1)

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

Центральным понятием теории асимметричных криптосистем является понятие односторонней функции [6]. Пусть дана функция:

, (1.2)

определенная на множестве , для которой существует обратная функция:

. (1.3)

Функция называется односторонней, если вычисление по формуле (1.2) является сравнительно простой задачей, требующей немного времени, а вычисление по (1.3) – задача сложная, требующая привлечения массы вычислительных ресурсов, например 10⁶-10⁹ лет работы мощного суперкомпьютера. Данное определение, конечно, не является строгим. Рассмотрим более точное определение односторонней функции [9].

Определение 1.2. Пусть и - конечные множества. Односторонней функцией:

, (1.4)

называется обратимая функция, удовлетворяющая следующим условиям:

1) легко вычисляется, т.е. если дано , вычислима за полиномиальное время (существует полиномиальный алгоритм вычисления );

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

Непосредственно односторонняя функция в криптографии не используется. Применяется односторонняя функция с секретом (одностороння функция с «лазейкой», односторонняя функция с «ловушкой»).

Определение 1.3. Пусть и - конечные множества. Односторонней функцией с секретом

, (1.5)

называется обратимая функция, удовлетворяющая следующим условиям:

1) легко вычисляется, т.е. если дано , вычислима за полиномиальное время (существует полиномиальный алгоритм вычисления );

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

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

Таким параметром в асимметричных криптосистемах является, как правило, закрытый ключ .

Рассмотрим односторонние функции, используемые в криптографии [6].

Дискретное экспоненцирование и логарифмирование. Пусть

, (1.6)

где - некоторое простое число, а . Обратная функция обозначается:

, (1.7)

называется дискретным логарифмом.

Рассмотрим на примере простоту вычисления (1.6). Пусть требуется вычислить . Введем величину представляющую собой целую часть и определим числовой ряд :

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

и в соответствии с выражением [6]:

, (1.8)

вычислим значение . Для вычислений потребовалось всего восемь операций умножения.

Справедливо утверждение [6]: количество операций умножения при вычислении (1.6) по рассмотренному методу не превосходит .

Задача вычисления (1.7) не является тривиальной. Для ее решения используются различные математические методы, при этом требуется операций. Следовательно, чем больше значение , тем сложнее вычислить (1.7). Например, если количество десятичных знаков в записи числа равно 90, то количество операций для вычисления (1.6) равно примерно 600. Для перспективных компьютеров (для современных компьютеров это пока не доступно) время на одну операцию составляет 10^-14 сек., тогда вычисление (1.6) занимает 6•10^-12 сек., а вычисление (1.7) занимает 10³¹ сек.»10²² лет (количество операций - 10⁴⁵).

Таким образом, можно утверждать, что (1.7) является односторонней функцией. Вместе с тем, не существует строгого математического доказательства отсутствия возможности вычисления (1.7) также «быстро» как и (1.6).

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

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

2) задача разложения чисел вида:

, (1.9)

является очень трудновыполнимой, если известно только , а и - большие простые числа.

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

. (1.10)

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

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

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

. (1.11)

В общем случае не существует эффективного алгоритма вычисления по и . Таким образом, можно использовать вектор для шифрования -битового сообщения путем вычисления произведения (1.11).

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

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

1.2. Элементы теории чисел

Алгоритмы асимметричной криптографии базируются на классической теории чисел. Рассмотрим минимум из этой теории, позволяющий уяснить суть методов и алгоритмов асимметричной криптографии [5,6].

Определение 1.4. Целое положительное число называется простым, если оно делится без остатка только на единицу и само на себя.

Определение 1.5. Два числа называются взаимно простыми, если они не имеют ни одного общего делителя кроме единицы.

Теорема 1.1. Основная теорема арифметики. Любое целое положительное число может быть представлено в виде произведения простых чисел, причем единственным образом.

Определение 1.6. Пусть дано целое число 1. Значение функции Эйлера равно количеству чисел ряда 1, 2, 3, …, , взаимно простых с .

Рассмотрим пример: . Сформируем числовой ряд: 1, 2, 3, 4, 5, 6, 7, 8, 9. Проверим числа ряда на взаимную простоту с 10 и получим следующий результат: 1, 2, 3, 4, 5, 6, 7, 8, 9. Выделены числа взаимно простые с 10. Таким образом - =4.

Теорема 1.2. Пусть - простое число, тогда .

Рассмотренную теорему примем без доказательства.

Теорема 1.3. Пусть и - простые числа, причем . Тогда .

□ В числовом ряду 1, 2, …, не взаимно простыми с будут числа:

и .

Всего таких чисел будет . Следовательно, количество чисел, взаимно простых с будет

. ■

Теорема 1.4. Теорема Ферма. Пусть - простое число и . Тогда

.

Рассмотренную теорему примем без доказательства и рассмотрим поясняющий пример. Пусть =13, =2. Тогда:

.

Теорема 1.5. Теорема Эйлера. Пусть и - взаимно простые числа. Тогда

.

Рассмотренную теорему примем без доказательства, но рассмотрим поясняющий пример. Пусть =5 и =12. Тогда, учитывая, что , получаем:

.

Теорема 1.6. Пусть и - простые числа, и - произвольное целое число. Тогда

.

Рассмотрим пример. Пусть =5, =7, тогда =35. Функция Эйлера имеет значение 24. При 2 и 9, имеем

.

Определение 1.7. Число , удовлетворяющее выражению:

,

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

Данное обозначение для инверсии можно переписать и по другому:

.

Умножение на соответствует делению на при вычислении по модулю . Можно ввести отрицательные степени при вычислениях по модулю:

.

Вычислить инверсию числа можно с помощью обобщенного алгоритма Евклида.

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

1.3. Криптосистема RSA

Криптосистема RSA названа была так в честь ее разработчиков: Рона Ривеста (Ron Rivest), Ади Шамира (Adi Shamir) и Леонарда Адлемана (Leonard Adleman). Криптосистема RSA является одной из самых используемых в мире асимметричных криптосистем.

Определение 1.8. Криптосистема с открытым ключом RSA формально определяется следующим образом [6-9]:

, (1.12)

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

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

, .

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

Рассмотренные действия являются подготовительными. Будем считать, что абонент хочет передать абоненту сообщение . Сообщение должно удовлетворять условию .

Абонент осуществляет шифрование в соответствии с выражением:

, (1.13)

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

Абонент , получивший криптограмму расшифровывает ее:

. (1.14)

Докажем справедливость (1.14).

□

Равенство означает, что для некоторого справедливо равенство:

.

Согласно теореме 1.3

.

На основании этого, и следуя теоремe 1.6, имеем:

. ■

На основании вышесказанного можно сделать следующие выводы:

1) протокол криптосистемы RSA шифрует и расшифровывает информацию корректно;

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

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

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

Дата добавления: 2014-12-26