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

Алгоритм работы протокола

1. Предварительная обработка. Алиса выбирает случайное число ${\displaystyle r}$ , меньшее ${\displaystyle q}$ , и вычисляет ${\displaystyle x=g^{r}{\pmod {p}}}$ . Эти вычисления являются предварительными и могут быть выполнены задолго до появления Боба.
2. Инициирование. Алиса посылает ${\displaystyle x}$ Бобу.
3. Боб выбирает случайное число ${\displaystyle e}$ из диапазона от ${\displaystyle 0}$ до ${\displaystyle 2^{t}-1}$ и отправляет его Алисе.
4. Алиса вычисляет ${\displaystyle s=r+we{\pmod {q}}}$ и посылает ${\displaystyle s}$ Бобу.
5. Подтверждение. Боб проверяет что ${\displaystyle x=g^{s}y^{e}{\pmod {p}}}$

Безопасность алгоритма зависит от параметра t. Сложность вскрытия алгоритма примерно равна ${\displaystyle 2^{t}}$ . Шнорр советует использовать t около 72 битов, для ${\displaystyle p\geq 2^{512}}$ и ${\displaystyle q\geq 2^{140}}$ . Для решения задачи дискретного логарифма, в этом случае, требуется по крайней мере ${\displaystyle 2^{72}}$ шагов известных алгоритмов.

Пример

Генерация ключей:

• Выбирается простое ${\displaystyle p=48731}$ и простое ${\displaystyle q=443}$ (${\displaystyle q|p-1}$ )
• Вычисляется ${\displaystyle g}$ из условия ${\displaystyle g^{q}=1{\pmod {p}}}$ , в данном случае ${\displaystyle g=11444}$
• Алиса выбирает секретный ключ ${\displaystyle w=357}$ и вычисляет открытый ${\displaystyle y=g^{-w}{\pmod {p}}=7355}$ ключ
• Алиса отправляет открытый ключ ${\displaystyle (p,q,g,y)}$ соответственно равный ${\displaystyle (48731,443,11444,7355)}$ , закрытый оставляет у себя — ${\displaystyle w=357}$

Проверка подлинности:

• Алиса выбирает случайное число ${\displaystyle r=274}$ и отсылает ${\displaystyle x=g^{r}{\pmod {p}}=37123}$ Бобу.
• Боб отсылает Алисе число ${\displaystyle e=129}$
• Алиса считает ${\displaystyle s=(r+w*e){\pmod {q}}=255}$ и отправляет ${\displaystyle s}$ Бобу.
• Боб вычисляет ${\displaystyle z=g^{s}*y^{e}{\pmod {p}}=37123}$ и идентифицирует Алису, так как ${\displaystyle z=x}$ .

Атаки на Схему

Генерация подписи

1. Предварительная обработка. Пегги выбирает случайное число ${\displaystyle r}$ , меньшее ${\displaystyle q}$ , и вычисляет ${\displaystyle x=g^{r}{\pmod {p}}}$ . Это стадия предварительных вычислений. Стоит отметить, что для подписи разных сообщений могут использоваться одинаковые открытый и закрытый ключи, в то время как число ${\displaystyle r}$ выбирается заново для каждого сообщения.
2. Пегги объединяет сообщение ${\displaystyle M}$ и ${\displaystyle x}$ и хеширует результат для получения первой подписи:

   ${\displaystyle S_{1}=H(M|g^{r}{\bmod {p}})}$

3. Пегги вычисляет вторую подпись. Необходимо отметить, что вторая подпись вычисляется по модулю ${\displaystyle q}$ .

   ${\displaystyle S_{2}=r+wS_{1}{\bmod {q}}}$ .

4. Пегги отправляет Виктору сообщение ${\displaystyle M}$ и подписи ${\displaystyle S_{1}}$ , ${\displaystyle S_{2}}$ .

Проверка подписи

1. Виктор вычисляет ${\displaystyle X=g^{S_{2}}y^{S_{1}}{\bmod {p}}}$ (либо ${\displaystyle X=g^{S_{2}}y^{-S_{1}}{\bmod {p}}}$ , если вычислять ${\displaystyle y}$ как ${\displaystyle y=g^{w}{\pmod {p}}}$ ).
2. Виктор проверяет, что ${\displaystyle H(M|X)=S_{1}}$ . Если это так, то он считает подпись верной.

Эффективность

Основные вычисления для генерации подписи производятся на этапе предварительной обработки и на этапе вычисления ${\displaystyle wS_{1}{\bmod {q}}}$ , где числа ${\displaystyle w}$ и ${\displaystyle S_{1}}$ имеют порядок ${\displaystyle 140}$ битов, а параметр ${\displaystyle r}$  — ${\displaystyle 72}$ бита. Последнее умножение ничтожно мало по сравнению с модульным умножением в схеме RSA.

Проверка подписи состоит в основном из расчета ${\displaystyle X=g^{S_{2}}y^{S_{1}}}$ , который может быть сделан в среднем за ${\displaystyle 1.5l+0.25t}$ вычислений по модулю ${\displaystyle p}$ , где ${\displaystyle l=[log_{2}q]}$ есть длина ${\displaystyle q}$ в битах.

Более короткая подпись позволяет сократить количество операций для генерации подписи и верификации: в схеме Шнорра ${\displaystyle O(\log _{2}q\log _{2}^{2}p)}$ , а в схеме Эль-Гамаля ${\displaystyle O(\log ^{3}p)}$ .

Пример

Генерация ключей:

1. ${\displaystyle q=103}$ и ${\displaystyle p=2267}$ . Причем ${\displaystyle p=22q+1}$ .
2. Выбирается ${\displaystyle f=2}$ , который является элементом в поле ${\displaystyle Z_{2267*}}$ . Тогда ${\displaystyle {\frac {p-1}{q}}=22}$ и ${\displaystyle g=2^{22}{\bmod {2}}267=354}$
3. Пегги выбирает ключ ${\displaystyle w=30}$ , тогда ${\displaystyle y=1206}$
4. Секретный ключ Пегги — ${\displaystyle 30}$ , открытый ключ — ${\displaystyle (103,2267,354,1206)}$ .

Подпись сообщения:

1. Пегги нужно подписать сообщение ${\displaystyle M=1000}$ .
2. Пегги выбирает ${\displaystyle r=11}$ и вычисляет ${\displaystyle g^{r}=354^{11}=630mod2267}$ .
3. Предположим, что сообщение — ${\displaystyle 1000}$ , и последовательное соединение означает ${\displaystyle 1000630}$ . Также предположим, что хеширование этого значения дает дайджест ${\displaystyle H(1000630)=200}$ . Это означает ${\displaystyle S_{1}=200}$ .
4. Пегги вычисляет ${\displaystyle S_{2}=r+wS_{1}modq=11+30*200mod103=11+26=37}$ .
5. Пегги отправляет Виктору ${\displaystyle M=1000}$ , ${\displaystyle S_{1}=200}$ и ${\displaystyle S_{2}=37}$ .

Преимущества

В то время, как в вычислительном плане модификация Брикелл и МакКерли менее эффективна, чем схема Шнорра, данный метод имеет преимущество, так как основывается на трудности двух сложных задач:

• вычисление логарифма в циклической подгруппе порядка ${\displaystyle q}$ в ${\displaystyle \mathbb {Z} _{p}^{*}}$ ;
• вычисление факториала ${\displaystyle p-1}$ .