Составители:
приемлемое время пока не найден, хотя не доказано, что не существует
эффективного алгоритма вычисления дискретного логарифма за
указанное время.
По современным оценкам теории чисел при целых числах a ≈2
664
и
N≈2
664
решение задачи дискретного логарифмирования (нахождение
показателя степени X для известного Y) потребует около 10
26
операций,
т.е. эта задача имеет в 10
3
раз большую вычислительную сложность, чем
задача разложения на множители. Разница в оценках сложности задач
возрастает при увеличении длины чисел.
Кроме того, в настоящее время при построении криптосистем с
открытым ключом широко используются так называемые
однонаправленные функции с «потайным ходом». Такая функция
предполагается легко вычислимой в одном направлении и практически
не
вычислимой в другом при отсутствии дополнительной информации.
При наличии такой информации обратная функция может быть
вычислена за полиномиальное время, рассматриваемой как функция
длины вводимого значения.
Функция f: X → Y относится к классу однонаправленных функций с
«потайным ходом» в том случае, когда она является однонаправленной
и возможно эффективное вычисление обратной
функции, если известен
«потайной ход», то есть секретное число, строка или другая
информация, ассоциирующаяся с данной функцией.
В качестве практического применения однонаправленной функции
рассмотрим алгоритм шифрования данных по схеме RSA.
3.3. Криптосистема шифрования данных RSA
В настоящее время наиболее изученным методом криптографической
защиты, основанным на трудности факторизации больших чисел
и
трудности вычисления дискретных логарифмов, является алгоритм RSA
(названый по начальным буквам фамилий ее изобретателей Rivest,
Shamir, Adleman) [25]. Этот алгоритм может работать как в режиме
шифрования данных, так и в режиме электронной цифровой подписи.
Схема RSA представляет собой блочный шифр, в котором открытый и
зашифрованный тексты представляются целыми числами из диапазона
от 0 до
N – 1 для некоторого N, т.е. открытый текст шифруется блоками,
56
Страницы
- « первая
- ‹ предыдущая
- …
- 52
- 53
- 54
- 55
- 56
- …
- следующая ›
- последняя »
