Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
Еще одна причина, по которой применение функции хэширования в протоколе подбрасывания монеты является нежелательным, — невозможность провести точный анализ стойкости, жизненно необходимый в серьезных приложениях.
Последний протокол, рассматриваемый в книге, представляет собой конкретную реализацию первого протокола. Пройдя курс современной криптографии, мы теперь в состоянии описать хорошую реализацию протокола 1.1 — знаменитый протокол "Подбрасывание монеты по телефону", предложенный Блюмом [43].
19.1 Протокол Блюма "Подбрасывание монеты по телефону"
Рассмотрим спецификацию протокола Блюма "Подбрасывание монеты по телефону". Этот протокол выполняется параллельно, позволяя сторонам согласовать случайное число, состоящее из т бит Как и в протоколе 1.1, Алиса подбрасывает монету, а Боб угадывает результат.
В протоколе Блюма используется большое составное целое число N = PQ, где Р и Q — два больших простых числа, удовлетворяющих условию
P = Q = 3(mod4).
После опубликования протокола Блюма [43] эти целые числа стали называться целыми числами Блюма. Они обладают полезными криптографическими свойствами. В разделе 6.7 указаны некоторые факты из теории чисел, касающиеся чисел Блюма. Эти факты позволяют проанализировать стойкость протокола Блюма.
19.2 Анализ стойкости
В протоколе Блюма Алиса подбрасывает монету, а Боб пытается угадать результат. Следовательно, при анализе стойкости протокола необходимо оценить трудности, с которыми сталкиваются стороны, пытаясь организовать атаку. Существуют две возможности.
726
Часть VI. Криптографические протоколы
Протокол 19.1. Протокол Блюма "Подбрасывание монеты по телефону" (* Этот протокол позволяет Алисе и Бобу согласовать строку, состоящую из тп случайных битов. Как и в протоколе 1.1, Алиса подбрасывает монету, а Боб угадывает результат. *) ПРАВИЛА:
• Стороны ставят цифровую подпись на каждое сообщение, посланное партнеру.
• Стороны прекращают выполнение протокола, если какая-либо проверка (включая верификацию цифровой подписи) обнаруживает нарушение правил.
1. Боб генерирует большое целое число Блюма N — PQ и посылает его Алисе.
2. Алиса генерирует тп случайных чисел: х\, х2, - -., хт 6 иЩ;- Результатами жеребьевки считаются числа (f/), i = 1,2,..., т. Затем она находит числа У\ *— ж2, у2 <— х\,..., ут <— ^(mod N) и посылает их Бобу.
3. Боб генерирует случайные знаки fci, b2, - - -, bm 6 г/{—1,1}, пытаясь угадать знаки чисел [jf), где г = 1,2,..., тп, и посылает их Алисе.
(* Боб завершил угадывание результатов жеребьевки. *)
4. Алиса раскрывает Бобу числа х\, х2,..., хт.
(* Алиса сообщает Бобу результаты его угадывания. *)
5. Боб проверяет условия yi = ж2(mod А7), где г = 1,2,... ,т, и открывает Алисе числа Р nQ.
6. Алиса проверяет условия P = Q = 3(mod 4) и проверяет, являются ли числа Р kQ простыми.
7. Алиса и Боб вычисляют согласованные случайные биты для г = 1,2,..., тп.
J1'
1о
если Боб правильно угадал знак, т.е. = h,
в противном случае.
Алиса жульничает
Может ли Алиса подбросить монету и сообщить Бобу неверные результаты?
Боб обладает преимуществом при угадывании
Может ли Боб угадать результат с преимуществом больше 1/2?
Оба эти вопроса допускают количественный ответ. Во-первых, жульничество Алисы связано с факторизацией целого числа Блюма N. Во-вторых, преимущество Боба при угадывании результата равно 1/2.
Глава 19. Еще раз о "подбрасывании монеты по телефону"
727
Стойкость к жульничеству Алисы
Для того чтобы сжульничать, Алиса должна найти коллизию, т.е. два элемента z\, Z2 € удовлетворяющие следующим условиям.
• z\ EEz|(modA0-
• ® * (I)-
Допустим, что Алисе удалось обнаружить коллизию. Из теоремы 6.18.1 следует, что (^-) = 1. Для этого необходимо, чтобы z\ Ф ±Z2(mod n), т.е.0 < z\ ± ± Z2 < n. Предположим противное, т.е. z\ = —Z2(mod n). Тогда
(n) = ("at") (at) = Gv)'
что противоречит условию коллизии (^) ф (Ц). Теперь из условий
О < zi + Z2 < n, 0 < |zi - z2| < n
и
zi - z\ = (zi + zi) (zi - z2) = 0(mod n)
получаем
0<gcd(zi + z2,Ar) < n.
Итак, Алиса разложила число n на простые множители.
Таким образом, мы доказали, что жульничество Алисы по сложности эквивалентно факторизации числа n, т.е. решению общеизвестной трудноразрешимой задачи. Здесь мы воспользовались методом "сведения к противоречию", принятым при анализе стойкости. Следовательно, второе свойство "волшебной" функции означает невозможность решения трудноразрешимой задачи, да еще в реальном времени.
Итак, функция в протоколе Блюма действительно является однонаправленной.
Преимущество при угадывании
Покажем теперь, что преимущество Боба при угадывании равно 1/2.
При г-м подбрасывании монеты Алиса посылает Бобу число уг = ж2 (mod n). Получив число yl, Боб должен угадать знак числа (|^). По теореме 6.18.3 число у* имеет точно два квадратных корня с положительным символом Якоби и точно два квадратных корня — с отрицательным. Используя алгоритм 6.5, Боб может вычислить каждый из этих четырех квадратных корней. Однако он не может знать, какой из этих корней выбрала Алиса, а значит, он не может угадать знак символа Якоби выбранного Алисой корня. С точки зрения Боба, эта функция представляет
