Шептунов М. В. - Теория множеств (1023559), страница 7

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 7)

.

Далее, обозначим область значений функции через f[X].

Определение 2.26. Функция f называется однонаправленной (или односторонней), если её значение f(x) может быть легко вычислено для каждого аргумента xX, в то время как почти для всех yf[X] отыскание xX, при котором f(x)=y, является трудновычислимым.

Однонаправленные функции не следует путать с функциями, которые являются математически необратимыми из-за того, что у них нет взаимнооднозначности (т. е. у них существует несколько различных значений x, при которых f(x)=y, либо таких значений нет вовсе).

Однонаправленная функция H применяется к сообщению произвольной длины M и возвращает значение

фиксированной длины m.

Вычислять значение фиксированной длины по входным данным произвольной длины позволяют многие функции, но однонаправленные (односторонние) функции обладают следующими дополнительными свойствами:

1. зная M, легко вычислять h;

2. при заданном h задача отыскания M, при котором

H(M)=h,

является вычислительно трудоёмкой;

1. при заданном M задача отыскания другого сообщения M^’, при

котором

H(M)=H(M^’),

также является вычислительно трудоёмкой.

Смысл применения однонаправленных хеш-функций (их ещё называют функциями расстановки) состоит в обеспечении для M уникального значения, а именно своеобразного “отпечатка пальца” конкретного сообщения.

Существуют приложения, где необходимо соблюдение дополнительного требования, обычно называемого устойчивостью к коллизиям. Смысл его в том, что задача отыскания двух случайных сообщений M и M^’, для которых

H(M)=H(M^’),

должна быть вычислительно трудоёмкой.

Аналогом однонаправленной функции в быту является разбитая вдребезги стеклянная бутылка, ибо расколоть её на мелкие осколки легко, а вновь собрать воедино весьма сложно.

Строгого математического доказательства существования однонаправленных функций пока не дано, так же как и не придумано пока строгих правил их построения.

Одним из простейших претендентов на однонаправленную функцию является целочисленное умножение.

Известно, что перемножить два любых, пусть и очень больших, числа относительно нетрудно, тогда как даже для компьютера задача разложить подобное произведение на множители требует немалых затрат времени. Например, самому мощному из существующих компьютеров не под силу за приемлемое время разложить на множители четырёхзначное десятичное число, которое является произведением двух примерно одинакового размера простых чисел.

Другим весьма важным примером претендента на однонаправленную функцию является модульное возведение в степень, иногда называемое модульным экспоненцированием (с фиксированными основанием и модулем). Пусть n и a – целые числа, такие, что

,

и пусть также

{0, 1, 2, …, n-1}.

Тогда модульным возведением в степень, или экспоненцированием (относительно основания a и модуля n), называется функция

,

определяемая как

,

где – положительный остаток при делении i на j. Сразу не очевидно, что указанную функцию возможно вычислить эффективно, когда длина каждого из трёх параметров a, n, m составляет несколько сотен знаков. То, что это действительно так, демонстрируется на примере:

.

Приведённый пример показывает, что a²⁵ можно вычислить с помощью всего лишь четырёх возведений в квадрат и двух умножений. При вычислении

приведение по модулю желательно делать после каждого возведения в квадрат и каждого умножения, чтобы избежать получения очень больших целых чисел.

Задача вычисления функции, обратной модульному возведению в степень, известна как задача дискретного логарифмирования. Суть её в следующем: даны целые числа a, n, x, требуется найти такое целое m (при условии его существования), что

.

Например, 21=16. Таким образом, число 4 – это дискретный

логарифм 16 с основанием 5 по модулю 21.

Можно при желании убедиться, что число 3 вообще не имеет логарифма с основанием 5 по модулю 21. На сегодняшний день персональные ЭВМ позволяют легко и быстро вычислять большие модульные экспоненты. Однако, в настоящее время неизвестно ни одного алгоритма вычисления дискретных логарифмов больших чисел за приемлемое время даже на самых мощных быстродействующих суперкомпьютерах.

Хотя строго и не доказано, что эффективных алгоритмов для этого не существует, имеются веские основания предполагать, что последняя из рассмотренных операций действительно суть однонаправленная функция.

Очевидно, что однонаправленные функции не могут непосредственно использоваться в качестве криптосистем (т. е. когда m шифруется как f(m) при использовании указанных функций даже законный получатель не смог бы определить исходного сообщения).

Гораздо более употребимым криптографическим понятием является понятие однонаправленной функции с потайным ходом (лазейкой).

Определение 2.27. Функция

называется однонаправленной (односторонней) функцией с потайным ходом (лазейкой), если:

1. и сама f, и обратная ей f ^-1, могут эффективно вычисляться;

2. при известном эффективном алгоритме вычисления даже полное

описание его работы не должно давать возможности построить эффективный алгоритм вычисления f ^–1.

Определение 2.28. Секрет, при помощи которого можно эффективно

вычислять f ^–1, называется потайным ходом (лазейкой) для функции f.

Хорошим аналогом однонаправленной функции с лазейкой в

образном плане служат обыкновенные часы. Их легко разобрать на

большое количество мелких деталей, из которых затем весьма сложно вновь собрать. Однако при наличии необходимой инструкции собрать их будет относительно несложно.

Претендент на однонаправленную функцию с потайным ходом во многом напоминает уже рассмотренную просто однонаправленную функцию. Этим претендентом является модульное возведение в степень, но с фиксированной экспонентой и модулем.

Пусть m и n – целые числа, а определено также, как и ранее. Тогда модульное возведение в степень (относительно экспоненты m и модуля n) есть функция

.

Необходимо чётко понимать разницу между ранее рассмотренной функцией и функцией . Операция, обратная , известна как извлечение корня m-ой степени из x по модулю n: даны целые числа m, n, x; найти такое целое a (при условии его существования), что

.

Например, 5 является корнем 4-й степени из 16 по модулю 21, т. е.

. Стоило бы попытаться найти другие корни 4-й степени из 16 по модулю 21.

Для случая, когда экспонента m и модуль n являются

фиксированными, существует эффективный алгоритм вычисления

для любого основания a. В противоположность задаче дискретного логарифмирования, тем не менее известно о существовании также и эффективного алгоритма извлечения корня m-й степени из x по модулю n (либо выяснения, что корня такого нет) для любого заданного x. Феномен здесь в том, что мы не знаем, как построить этот эффективный алгоритм при заданных лишь m и n. Другими словами,

известно, что функция на самом деле является не однонаправленной, поскольку мы знаем, что она может быть эффективно

обращена, но, несмотря на этот факт, не знаем, как это сделать (!).

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

Качественная однонаправленная хеш-функция чаще всего непротиворечива, т. е. весьма сложно получить два различных образа, для которых хеш-значение будет одним и тем же.

Собственно процесс хеширования в криптографии тайной не является. Однонаправленная функция обеспечивает необходимый уровень защиты именно благодаря своей однонаправленности.

Обычно по выходу такой функции невозможно понять, что было подано на её вход, а изменение лишь одного бита образа приводит к смене в среднем половины битов соответствующего хеш-значения.

2.9. Вопросы для самоконтроля

1. Что называется n-местным отношением ?

2. Приведите пример n-местного отношения.

3. Как могут обозначаться отношения ?

4. Перечислите шесть основных свойств отношений, запишите

для них соответствующие формулы.

1. Дайте определение отношению эквивалентности, приведите

примеры.

1. Как обозначается отношение эквивалентности ?

2. Что такое класс эквивалентности ?

3. Является ли параллельность двух прямых частным случаем

отношения эквивалентности ?

1. Дайте определение отношению порядка.

2. В чём разница между отношениями строгого и нестрогого

порядка ?

11. Каковы необходимые и достаточные условие доминирования ?

1. Что такое соответствие ?

2. Что называют областью отправления и областью прибытия

соответствия ?

1. Что такое график соответствия ?

2. Что называют областью определения и областью значений

соответствия ?

16. Приведите пример соответствия.

1. Что такое отображение ?

2. Какими способами обозначается отображение ?

3. Является ли отображение частным случаем соответствия ?

4. Что такое перестановка множества ?

5. Приведите пример отображения.

6. Поясните взаимосвязь понятий “отношение”, “соответствие”,

“отображение”.

1. Что такое функция ?

2. В чём разница между полными и частичными функциями ?

3. Перечислите способы задания функции.

4. Что называют сужением функции ?

5. Объясните, что такое инъективная, сюръективная и биективная

функции.

1. Какая функция называется обратной ?

2. Что такое функционал ?

3. Что понимается под вычислительно сложными задачами

(трудно решаемыми задачами) ?

1. Какие шифры называют условно стойкими, какие вычислительно

стойкими, а какие безусловно стойкими ?

32. Что представляет собой однонаправленная (односторонняя) функция и однонаправленная функция с потайным ходом (лазейкой) ?

Характеристики

Список файлов книги