Криптографические протоколы

ПРОТОКОЛ ПОДБРАСЫВАНИЯ МОНЕТЫ НА ОСНОВЕ КОРНЕЙ СРАВНЕНИЯ $z=u^2 \pmod n$ , ЯВЛЯЮЩИХСЯ КВАДРАТИЧНЫМИ ВЫЧЕТАМИ		Протокол CFQR
Примитивный протокол	Протокол подбрасывания монеты по телефону

Постановка задачи

Пусть A (Alice) и B (Bob) находятся на удалении друг от друга, и они не доверяют друг другу. Они хотят подбросить монетку по телефону.

Описание протокола

1) $ A$ случайным образом выбирает два разных больших простых числа $ p$ и $ q$ , вычисляет их произведение $ n=pq$ , сообщает $ n$ $ B$ .

2) $ B$ выбирает случайное целое число $u \in{(1,n/2)}$ , вычисляет его квадрат $z=u^2 \pmod n$ , отправляет $ z$ $ A$ .

3) $ A$ вычисляет $\pm x$ и $\pm y$ - четыре квадратичных корня из $z \pmod n$ . Это возможно, поскольку $ A$ знает разложение $ n$ на два простых множителя. Пусть $ x'$ будет меньшим из двух чисел $x \pmod n$ и $-x \pmod n$ . Пусть $ y'$ будет меньшим из двух чисел $y \pmod n$ и $-y \pmod n$ . Заметим, что $ u=x'$ или $ u=y'$ . $ A$ выбирает наугад $ u=x'$ или $ u=y'$ . $ A$ находит наименьшее число $ i$ такое, что $ i$ -й разряд справа в двоичном представлении $ x'$ отличается от соответствующего разряда в $ y'$ . $ A$ сообщает $ B$ наугад один из вариантов " $ i$ -й разряд справа в твоем числе и есть 0" или " $ i$ -й разряд справа в твоем числе и есть $ 1$ ".