группа Шнорра

Группа Шнорра , предложенная Клаусом П. Шнорром большую подгруппу простого порядка , представляет собой $\mathbb {Z} _{p}^{\times }$ , мультипликативная группа целых чисел по модулю $p$ для какого-то премьера $p$ . Чтобы создать такую группу, сгенерируйте $p$ , $q$ , $r$ такой, что

p=qr+1

с $p$ , $q$ основной. Тогда выбирайте любой $h$ в диапазоне $1<h<p$ пока не найдешь такого, что

h^{r}\not \equiv 1\;({\text{mod}}\;p)

.

Это значение

g=h^{r}{\text{ mod }}p

является генератором подгруппы $\mathbb {Z} _{p}^{\times }$ порядка $q$ .

Группы Шнорра полезны в дискретных журналов на основе криптосистемах , включая подписи Шнорра и DSA . В таких приложениях обычно $p$ выбирается достаточно большим, чтобы противостоять исчислению индексов и связанным с ним методам решения проблемы дискретного журнала (возможно, от 1024 до 3072 бит), в то время как $q$ достаточно велик, чтобы противостоять атаке «дня рождения» на проблемы дискретного журнала, которая работает в любой группе (возможно, от 160 до 256 бит). Поскольку группа Шнорра имеет простой порядок, она не имеет нетривиальных собственных подгрупп, что препятствует атакам на конфайнмент из-за небольших подгрупп. Реализации протоколов, использующих группы Шнорра, должны проверять, где это возможно, что целые числа, предоставленные другими сторонами, на самом деле являются членами группы Шнорра; $x$ является членом группы, если $0<x<p$ и $x^{q}\equiv 1\;({\text{mod }}p)$ . Любой член группы, кроме элемента $1$ также является генератором группы.