Группа Шнорра

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

с , премьер. Затем выберите любой из диапазона , пока не найдете такой, который ${\ Displaystyle р}$ ${\ Displaystyle д}$ ${\ Displaystyle ч}$ ${\ Displaystyle 1 <ч <р}$

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

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