МЕНЮ

Каталог

ПРОТОКОЛ ПОДБРАСЫВАНИЯ МОНЕТЫ НА ОСНОВЕ КВАДРАТИЧНОГО ВЫЧЕТА ПО МОДУЛЮ ЧИСЛА БЛЮМА ДЛЯ СОГЛАСОВАНИЯ СТРОКИ, СОСТОЯЩЕЙ ИЗ m СЛУЧАЙНЫХ БИТОВ Протокол CFB
Примитивный протокол Протокол подбрасывания монеты по телефону

 

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

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

Составное целое число $ n$ называется целым числом Блюма, если $ n=pq$, где $ p$ и $ q$ - разные простыые числа, удовлетворяющие условию $ p\equiv q\equiv 3 \pmod n$. 

Участники протокола ставят цифровую подпись на каждое сообщение, посланное партнеру. 
Участники прекращают выполнение протокола, если какая-либо проверка (включая верификацию цифровой подписи) обнаруживает нарушение правил. 

1) $ B$ случайным образом выбирает два разных больших (80-значных) простых числа $ p$ и $ q$, удовлетворяющих условию $ p\equiv q\equiv 3 \pmod n$, и вычисляет их произведение $ n=pq$, т.е. генерирует большое целое число Блюма. $ B$ посылает $ n$ $ A$. 

Замечание. Для выбора $ n$ может быть использован доверенный посредник, который будет генерировать $ n$ по правилам, заданным Бобом. 

2) Если $ A$ верит, что $ n$ является произведением два разных больших (80-значных) простых чисел $ p$ и $ q$, удовлетворяющих условию $ p\equiv q\equiv 3 \pmod n$, то эта часть протокола может быть пропущена. В противном случае, $ A$ проверяет, что $ n$ обладает следующими двумя свойствами: 
a) $ n$ является 160-значным числом и $ n=1 \pmod 4$, из последнего следует, что $ n$нечетно и $ \left(-\frac{1}{n}\right)=+1$. 
b) для некоторого $ x$ почти наверняка существует $ y$ такое, что $ x^2=y^2 \pmod n$ и$ \left(\frac{x}{n}\right)\neq\left(\frac{y}{n}\right)$. 

3) $ A$ случайным образом выбирает $ m$ целых чисел $ x_1, x_2, ..., x_m \in Z_n^*$ вычисляет$ y_1=x_1^2 \pmod n, y_2=x_2^2 \pmod n, ..., y_m=x_m^2 \pmod n$ и отправляет их $ B$. 

4) $ B$ выбирает наугад $ b_1, b_2, ..., b_m \in \{-1,1\}$ и отправляет их $ A$. 

5) $ A$ определяет $ m$ случайных битов $ r_1, r_2, ..., r_m$, где $ r_i=1$, если $ \left(\frac{x_i}{n}\right)=b_i$, $ r_i=-1$ - в противном случае, для всех $ i=1, 2, ..., m$, и отправляет $ x_1, x_2, ..., x_m$ $ B$. 

6) $ B$ проверяет, что $ y_1=x_1^2 \pmod n, y_2=x_2^2 \pmod n, ..., y_m=x_m^2 \pmod n$. 

7) $ B$ вычисляет $ \left(\frac{x_1}{n}\right)$, $ \left(\frac{x_2}{n}\right)$, ..., $ \left(\frac{x_m}{n}\right)$, таким образом определяет $ r_1, r_2, ..., r_m$.

 

Основные сведения
Авторы

Manuel Blum

 
Ссылки
  • M.Blum, "Coin Flipping by Telephone: A Protocol for Solving Impossible Problems", Proceedings of the 24th IEEE Computer Conference (CompCon), 1982, pp. 133-137.
  • M.Blum, "Coin flipping by telephone -- A protocol for solving impossible problems," ACM SIGACT News, vol. 15, no. 1, pp. 23-27, Dec. 1983.
  • Венбо Мао. Современная криптография. Теория и практика = Modern Cryptography: Theory and Practice. — М.: Вильямс, 2005. — 768 с. -С.726.