Иллюстрированный самоучитель по защите информации

Предсказание бита

Предсказание бита с помощью однонаправленной функции

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

• Антон генерирует две случайные битовые строки S₁ и S₂;
• Антон присоединяет к сгенерированным S₁ и S₂ бит b, значение которой собирается предсказать;
• Антон вычисляет значение однонаправленной функции Н, используя в качестве аргумента битовую строку (S₁,S₂,b), и вместе с S₁ отсылает Борису полученный результат.

Теперь у Бориса имеется вся необходимая информация, которая не позволит Антону впоследствии изменить предсказанное значение b. Однако проверить правильность предсказания без участия Антона Борис не сможет, поскольку в этом случае ему придется вычислять H^-1 (S₁,S₂,b).

Когда потребуется, чтобы Антон ознакомил со своим предсказанием Бориса, им обоим необходимо будет продолжить выполнение следующих шагов протокола:

1. Антон посылает Борису исходную битовую строку (S₁,S₂,b).
2. Борис вычисляет H(S₁,S₂,b), а затем сравнивает вычисленное значение и S₁ со значением и случайной битовой строкой, присланными ему Антоном на шаге 3. В случае совпадения b действительно представляет собой значение, предсказанное Антоном на шаге 2.

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

Теперь, при предсказании бита с помощью однонаправленной функции, Борису уже не обязательно генерировать какие-либо случайные битовые строки, поскольку Антон использует для предсказания однонаправленную функцию и не сможет смошенничать, составив фальшивое сообщение (S₁, S'₂, b') такое, что H(S_l, S', b') = H(S₁, S₂, b). Антон посылает Борису случайную битовую строку S₁, чтобы у Антона не было возможности путем подбора S₁ и S₂ добиться, чтобы изменилось b и чтобы при этом было сохранено значение H(S₁, S₂, b), которое Антон ранее отослал Борису. Храня S₂ в секрете от Бориса, Антон не дает Борису вычислить значения H(S₁, S₂, b) и H(S₁, S₂, b'), а затем определить b, сравнив эти значения с тем, что прислал ему Антон.

Предсказание с помощью генератора псевдослучайных битовых последовательностей

Для предсказания битового значения Антон может использовать генератор псевдослучайных битовых последовательностей:

1. Борис генерирует случайную битовую строку S_Б и посылает ее Антону.
2. Антон вычисляет случайное начальное значение для генератора псевдослучайных битовых последовательностей. Затем для каждого бита присланной Борисом битовой строки S_Б Антон отправляет Борису либо (а) выходное значение генератора псевдослучайных битовых последовательностей, если этот бит равен 1, либо (б) результат сложения выходного значения генератора псевдослучайных битовых последовательностей со значением, предсказанным Антоном, если соответствующий бит S_Б равен 0.

Когда Антон захочет раскрыть Борису свое предсказание, они должны будут перейти к выполнению последних двух шагов протокола:

1. Антон высылает Борису случайное начальное значение, вычисленное им для генератора псевдослучайных битовых последовательностей на шаге 2.
2. Борис повторяет действия Антона, предпринятые им на шаге 2, чтобы убедиться в том, что Антон не смошенничал.

Если сгенерированная Борисом случайная битовая строка является достаточно длинной, а генератор псевдослучайных битовых последовательностей, которым пользуется Антон, в требуемой степени непредсказуем, то у Антона практически нет шансов обмануть Бориса.