Дискретная математика. Математические вопросы криптографии. Ерош И.Л. - 50 стр.

UptoLike

Составители:

Рубрика:

5. НЕКОТОРЫЕ ДОПОЛНИТЕЛЬНЫЕ ЗАДАЧИ,

ИСПОЛЬЗУЮЩИЕ ИДЕИ С ОТКРЫТЫМ

РАСПРЕДЕЛЕНИЕМ КЛЮЧЕЙ

5.1. Бросание жребия по открытому каналу

Предположим, что Алиса и Боб недавно развелись и хотят с помо-

щью жребия решить, кому достанется, например, их общая машина.

Вопрос о принадлежности машины они хотят решить по телефону

путем бросания жребия, при этом естественно стремление обоих к тому,

чтобы игра была честной.

Протокол обмена сообщениями при этом может выглядеть следую-

щим образом:

Все целые числа делятся на два класса: четные и нечетные. Пусть

нечетным числам соответствует решка монеты, а четным – орел. Так,

числам 1, 3, 5, 7, 9,…соответствует решка, а числам 2, 4, 6, 8, 10,… –

орел. Алиса и Боб договариваются об использовании некоторой одно-

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

пень: x

≡ a mod p. Фактически они должны согласовать значения k и p.

Затем Алиса выбирает некоторое целое число x , возводит его в сте-

пень k и полученное a передает Бобу. Боб, получив a, не знает, соответ-

ствует оно четному числу или нет и наугад принимает решение, напри-

мер, считает, что Алиса выбрала число y, которое сообщает Алисе.

Тогда Алиса передает Бобу число x, которое она использовала для вы-

числения a. Боб сравнивает x и y по mod 2, если x є y mod 2, то Боб

угадал и машина достается ему, если же x ≠ y mod 2 , то машина доста-

ется Алисе.

5.2. Определение “лишних” абонентов

Пусть секрет разделен между всеми участниками совещания по

открытому каналу так, как это было сделано в примере 3 разд. 4.4.

"Разделение секрета".