Предшественницей схем, с описанием которых мы познакомимся в этом пункте, является простая и изящная односторонняя функция. Так принято называть функцию f , отображающую двоичные последовательности одной фиксированной длины (например, 100) на двоичные последовательности какой-нибудь другой фиксированной длины (например, 120):
100 120
f:F -->F
и не имеющую известной обратной функции. Иначе говоря, если вам
сообщают, что
f(X)=1010001...11011110
то вы не можете восстановить значение Х , даже если вам известно,
как вычислено значение . Последнее утверждение не вполне точно:
теоретически Х можно найти, проверяя по очереди все возможные Х
до тех пор, пока не совпадет с заданной последовательностью.
Однако по существу такой метод обращения функции неосуществим,
так как проверять пришлось бы слишком много различных Х. Итак,
мы можем сказать, что -- односторонняя функция, если легко
вычисляется при любом Х, в то время как не поддается вычислению
почти при всех Y из области значений функции .
Односторонние функции находят широкое применение в ЭВМ. Обычно "пользователи" вычислительных машин выбирают пароли, удостоверяющие их личность при подключении к системе. Хранить эти пароли в массиве данных самой ЭВМ опасно, так как трудно обеспечить секретность. Вместо этого можно взять одностороннюю функцию и хранить в массиве данных значения от паролей. Так как функция не допускает обращения, "плохой мальчик" не может узнать пароль по этим данным. С другой стороны, если кто-нибудь подключается к ЭВМ, то он вводит свои пароль Р, компьютер вычисляет и сравнивает с последовательностями, хранящимися в массиве данных.