в Б, одновременно получить информацию

Можно ли, двигаясь из А в Б, одновременно получить информацию о пути движения из Б в А? (чтобы упростить решение обратной задачи)

Не трудно видеть, что в рассмотренной ситуации, для любого водителя, участвующего в этом процессе, есть единственный способ поиска решения обратной задачи (то есть, возвращение из пункта Б в пункт А) – это полный перебор возможных вариантов.
Характерная особенность рассмотренного процесса заключается в том, что сложность решения прямой задачи (движение из А в Б) намного проще решения обратной задачи, которая может даже не иметь решения. Именно по этой причине, функция, описывающая рассмотренную выше ситуацию, называется однонаправленной.
Положение может измениться, если кто-либо из участников процесса движения секретно обзаведется, например, вертолетом (или воздушным шаром, или чем-либо, позволяющим ему изменить механизм движения). Понятно, что для него решение прямой задачи (движение из А в Б), и обратной (движение из Б в А), обладают одинаковой сложностью. Такую задачу называют однонаправленной задачей с секретом. В рассмотренном случае «секретом» является наличие вертолета у одного из участников ([5]).
Таким образом, для обладателей секрета, решение обратной задачи имеет сложность, такую же, как и для прямой задачи, в то время как для всех остальных участников движения, обратная задача может даже не иметь решения.
Уитвелд Диффи и Мартин Хеллман показали, что

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

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

Содержание Назад Вперед

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