ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 06.02.2024
Просмотров: 70
Скачиваний: 0
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
СОДЕРЖАНИЕ
РАЗДЕЛ 1. МАТЕМАТИЧЕСКИЕ ОСНОВЫ КРИПТОГРАФИИ
1.1. ДЕЛИМОСТЬ И АЛГОРИТМ ЕВКЛИДА
РАЗДЕЛ 2. КРИПТОГРАФИЧЕСКИЕ СИСТЕМЫ С ОТКРЫТЫМ КЛЮЧОМ
2.1. Основные сведения о криптографических системах
2.2. Шифрование с использованием криптосистемы RSA
2.3. Цифровая подпись в схеме Эль-Гамаль
2.4. Обмен информацией с использованием протокола Шамира
3.2. ПРИМЕРЫ ВЫПОЛНЕНИЯ КОНТРОЛЬНЫХ ЗАДАНИЙ
Затем случайным образом выбирается элемент , такой, что и являются взаимно простыми числами, т.е.
| . | (2.2) |
Замечание 1: Здесь и далее - есть функция Эйлера, определяемая из выражения
| | |
Замечание 2: Для вычисления в условиях схемы RSA можно использовать следующее соотношение, справедливость которого очевидна из определения функции Эйлера
| . | (2.3) |
Несложно убедиться, что данный метод вычисления имеет сложность порядка двоичных операций[7].
Замечание 3: Скорость работы алгоритма шифрования RSA существенным образом зависит от выбора . На практике наиболее используемыми вариантами являются значения , , . Каждое из этих чисел содержит в двоичном представлении только две единицы, поэтому алгоритм повторного возведения в квадрат позволяет выполнить шифрование достаточно быстро[1].
Пара чисел
будет, таким образом являться открытым ключом алгоритма.
Далее с помощью расширенного алгоритма Евклида [1,3] определяется закрытый ключ , такой что:
| . | (2.4) |
Другими словами
| . | (2.5) |
Важно отметить, что и также являются взаимно простыми. Числа и в дальнейшем не используются, однако они должны быть сохранены в секрете, т.к. их разглашение будет означать вскрытие криптосистемы.
При шифровании сообщение разбивается на блоки фиксированной длины (меньшей, чем ). Шифрпреобразование полученных блоков выполняется согласно выражению
| . | (2.6) |
При расшифровке сообщения для каждого зашифрованного блока вычисляется
| . | (2.7) |
Для доказательства применимости данного алгоритма достаточно подробно рассмотреть свойства функции Эйлера [4,8].
Стойкость RSA существенным образом зависит от выбора
и . Как правило, практическую ценность имеет шифрование с ключами длины порядка сотен бит. Другим важным условием стойкости является требование, чтобы значение было по возможности наименьшим [1,7].
В литературе описаны многочисленные модификации схемы RSA, отличающиеся повышенным быстродействием, большей стойкостью и т.д.[1,7,8].
2.3. Цифровая подпись в схеме Эль-Гамаль
В отличие от криптосистемы RSA, построенной на сложности задачи факторизации больших чисел, профессор Стэнфордского университета (США) Тахер Эль-Гамаль (Taher ElGamal) разработал в 1985 г. асимметричную криптосистему, основанную на сложности задачи дискретного логарифмирования [9].
Данная криптосистема (названная его именем), так же как и RSA, является универсальной, т.е. может использоваться как для шифрования данных, так и для цифровой подписи сообщений.
Для генерации пары ключей выбирается простое число и два случайных числа и , меньших :
| , | (3.1) |
| . | (3.2) |
Затем вычисляется значение из выражения
| . | (3.3) |
Открытым ключом является тройка чисел , причем и можно сделать общими для группы пользователей. Секретным ключом является .
Для подписания сообщения , сначала выбирается случайное число
, такое что
| . | (3.4) |
Значение в дальнейшем сохраняется в секрете. Затем вычисляется значение из выражения
| | (3.5) |
Далее с помощью расширенного метода Евклида для нахождения решается следующее уравнение
| . | (3.6) |
Подписью является пара чисел . Для проверки подписи необходимо проверить справедливость равенства:
| . | (3.7) |
Несложно убедиться, что для каждой процедуры подписания необходимо новое значение , выбранное случайным образом. Компрометация значения дает возможность по перехваченным значениям , и восстановить за полиномиальное время значение секретного ключа [1].
Известны модификации данного алгоритма для доказательства идентичности, аутентификации и обмена ключами [1].