ВУЗ:
Составители:
сит от той задачи, которая стоит перед противником, и от того, какая ин-
формация о схеме ему доступна. Поэтому стойкость систем приходится
определять и исследовать отдельно для каждого предположения о против-
нике.
В-третьих, необходимо уточнить, какой объем вычислений можно
считать "практически неосуществимым". Из сказанного следует, что эта
величина не может быть просто константой, она должна быть представлена
функцией от растущего параметра безопасности. В соответствии с тезисом
Эдмондса алгоритм считается эффективным, если время его выполнения
ограничено некоторым полиномом от длины входного слова (от параметра
безопасности). В противном случае говорят, что вычисления по данному
алгоритму практически неосуществимы. При этом сами криптографические
системы должны быть эффективными, т.е. все вычисления, предписанные
той или иной схемой, должны выполняться за полиномиальное время.
В-четвертых, необходимо определить, какую вероятность можно счи-
тать пренебрежимо малой. В криптографии принято считать таковой лю-
бую вероятность, которая для любого полинома p и для всех достаточно
больших п не превосходит 1/р(п), где п – параметр безопасности.
Итак, при наличии всех указанных выше определений, проблема
обоснования стойкости криптографической системы сводится к доказа-
тельству отсутствия полиномиального алгоритма, который решает задачу,
стоящую перед противником. Но здесь возникает еще одно и весьма серь-
езное препятствие: современное состояние теории сложности вычислений
не позволяет доказывать сверхполиномиальные нижние оценки сложности
для конкретных задач рассматриваемого класса. Из этого следует, что на
данный момент стойкость криптографических систем может быть установ-
лена лишь с привлечением каких-либо недоказанных предположений. По-
этому основное направление исследований состоит в поиске наиболее сла-
бых достаточных условий (необходимых и достаточных) для существова-
ния стойких систем каждого из типов. В основном, рассматриваются пред-
положения двух типов – общие (или теоретико-сложностные) и теоретико-
числовые, т.е. предположения о сложности конкретных теоретико-
числовых задач. Все эти предположения в литературе обычно называются
криптографическими.
3.2. Односторонние функции и функции-ловушки
Центральным понятием в теории асимметричных криптографических
систем является понятие односторонней функции.
Под односторонней функцией понимается эффективно вычислимая
функция, для обращения которой (т.е. для поиска хотя бы одного значения
аргумента по заданному значению функции) не существует эффективных
алгоритмов. Заметим, что обратная функция может и не существовать.
Под функцией будем понимать семейство отображений {f
n
}, где
:,()
nm
n
f
mmn→=
∑
∑
.
Для простоты предположим, что п пробегает натуральный ряд, а ото-
бражения f
n
, определены всюду. Функция f называется честной, если
(), ( ())qx nqmn n∃∀ ≥
.
Функцией-ловушкой называется односторонняя функция, для которой
обратную функцию вычислить просто, если имеется некоторая дополни-
тельная информация, и сложно, если такая информация отсутствует.
В качестве задач, приводящих к односторонним функциям, можно
привести следующие:
1. Разложение числа на простые сомножители. Вычислить произведе-
ние двух простых чисел очень просто. Однако, для решения обратной зада-
чи – разложения заданного числа на простые сомножители – эффективного
алгоритма в настоящее время не существует.
2. Дискретное логарифмирование в конечном простом поле (проблема
Диффи-Хеллмана). Допустим, задано большое простое число р и пусть g –
примитивный элемент поля GF(p). Тогда для любого а вычислить g
a
(mod р)
просто, а вычислить а по заданным k = g
a
(mod р) и р оказывается затрудни-
тельным.
Криптосистемы с открытым ключом основываются на односторонних
Страницы
- « первая
- ‹ предыдущая
- …
- 50
- 51
- 52
- 53
- 54
- …
- следующая ›
- последняя »
