WikiSort.ru - Не сортированное

Предварительные действия

• Доверенный центр Т выбирает и публикует модуль ${\displaystyle n=p*q}$ , где p, q — простые и держатся в секрете.
• Каждый претендент A выбирает s взаимно-простое с n, где ${\displaystyle s\in [1,n-1]}$ . Затем вычисляется V${\displaystyle =s^{2}{\pmod {n}}}$ . V регистрируется T в качестве открытого ключа A

Передаваемые сообщения (этапы каждой аккредитации)

• A${\displaystyle \Rightarrow }$ B : ${\displaystyle x=r^{2}{\pmod {n}}}$
• A${\displaystyle \Leftarrow }$ B : ${\displaystyle e\in {0,1}}$
• A${\displaystyle \Rightarrow }$ B : ${\displaystyle y=r*s^{e}{\pmod {n}}}$

Основные действия

Следующие действия последовательно и независимо выполняются t раз. В считает знание доказанным, если все t раундов прошли успешно.

• А выбирает случайное r , такое, что ${\displaystyle r\in [1,n-1]}$ и отсылает ${\displaystyle x=r^{2}{\pmod {n}}}$ стороне B (доказательство)
• B случайно выбирает бит e (e=0 или е=1) и отсылает его A (вызов)
• А вычисляет у и отправляет его обратно к B. Если e=0, то ${\displaystyle y=r}$ , иначе ${\displaystyle y=r*s{\pmod {n}}}$ (ответ)
• Если y=0, то B отвергает доказательство или, другими словами, А не удалось доказать знание s. В противном случае, сторона B проверяет, действительно ли ${\displaystyle y^{2}=x*v^{e}{\pmod {n}}}$ и, если это так, то происходит переход к следующему раунду протокола.

Выбор е из множества {0,1} предполагает, что если сторона А действительно знает секрет, то она всегда сможет правильно ответить, вне зависимости от выбранного e. Допустим, что А хочет обмануть B. В этом случае А, может отреагировать только на конкретное значение e. Например, если А знает, что получит е=0, то А следует действовать строго по инструкции и В примет ответ. В случае, если А знает, что получит е=1, то А выбирает случайное r и отсылает ${\displaystyle x=r^{2}/v}$ на сторону В, в результате получаем нам нужное ${\displaystyle y=r}$ . Проблема заключается в том, что А изначально не знает какое e он получит и поэтому не может со 100 % вероятностью выслать на сторону В нужные для обмана r и х (${\displaystyle x=r^{2}}$ при e=0 и ${\displaystyle x=r^{2}/v}$ при e=1). Поэтому вероятность обмана в одном раунде составляет 50 %. Чтобы снизить вероятность жульничества (она равна ${\displaystyle 1/2^{t})}$ ) t выбирают достаточно большим (t=20, t=40). Таким образом, B удостоверяется в знании А тогда и только тогда, когда все t раундов прошли успешно.