Параметры домена в схеме идентификации Шнорра

Недавно я изучал схему идентификации Шнорра. В книге Стинсона и Патерсона « Криптография: теория и практика » о параметрах домена в схеме идентификации Шнорра говорится следующее:

Для схемы требуется доверенный орган, или TA, который выбирает некоторые общие системные параметры (параметры домена) для схемы следующим образом:

1. $р$ является большим простым числом (т. е. $p\ок. 2^{2048}$).

2. $q$ является большим простым делителем $p-1$ (т.е. $ д \ приблизительно 2 ^ {224} $).

3. $\alpha \in\mathbb{Z}_p^*$ порядок $q$

4. $t$ параметр безопасности такой, что $q>2^t$. (Параметр безопасности — это параметр, значение которого может быть выбрано для обеспечения желаемого уровня безопасности в данной схеме. Здесь вероятность противника обмануть Алису или Боба равна $2^{-t}$, так $t=80$ обеспечит достаточную безопасность для большинства практических приложений.)

Мой вопрос в том, как мы можем найти такие $р$, $q$, $\альфа$ и $t$? И почему это должно быть $p\ок. 2^{2048}$, $ д \ приблизительно 2 ^ {224} $ и $t=80$?

Нам понадобится эффективный тест на простоту, чтобы получить $р$ и $q$. Если вас устраивают вероятные простые числа, то Миллер-Рабин test будет достаточно для большинства практических целей.Напишите IsPrime() для теста.

Сначала выберите $t$ в соответствии с требованиями безопасности вашей схемы. Есть шанс $2^{-t}$ что обманщик может разрушить схему наугад, поэтому выбор $t=80$ означает, что даже если ваш злоумышленник попытался подделать вашу систему наугад $2^{80}$ раз они в среднем преуспеют только один раз. Позволить противнику $2^{80}$ попытки обмануть вашу систему вряд ли будут реальным предложением, поэтому $t=80$ в этом плане считается нормальным.

Теперь мы находим $q$, оно должно быть достаточно большим, чтобы противник не смог решить дискретные логарифмы в произвольной группе $q$ элементы (например, с помощью малыш-шаг-гигант-шаг метод), а также больше, чем $2^т$. Если $ д \ приблизительно 2 ^ {224} $ тогда примерно $2^{112}$ групповые операции потребуются для метода, и поэтому по крайней мере $2^{112}$ для BS-GS потребуются вычислительные операции. Чтобы найти 224-битный $q$ генерировать случайное 223-битное число $n$ и разреши $q_0=2^{223}+n$. Вычислить IsPrime($q_0$) и в случае успеха пусть $q=q_0$ в противном случае увеличить $q_0$ на 1 и повторяем до тех пор, пока не добьемся успеха.

Теперь мы находим $р$, оно должно быть достаточно большим, чтобы противник не смог решить дискретные логарифмы по модулю $р$ (например, с помощью сито числового поля). Если $p\ок. 2^{2048}$ Рекомендации Национального института стандартов и технологий предложить, по крайней мере $2^{112}$ потребуются вычислительные операции. Чтобы найти 2048-битный $р$, генерировать случайное 1824-битное число $м$ и разреши $p_0=q(2^{1824}+m)$. Вычислить IsPrime($p_0$) и в случае успеха пусть $р=р_0$ в противном случае увеличить $p_0$ к $q$ и повторяем, пока не добьемся успеха.

Теперь мы находим $\альфа$. Позволять $r=(p-1)/q$ Обратите внимание, что $г$ является целым числом. Начните с $г=2$. Вычислить $\alpha_0\экв г^г\пмод р$, если $\alpha_0\not\equiv 1\pmod p$ брать $\альфа=\альфа_0$, иначе увеличить $г$ на 1 и повторять до тех пор, пока не получится.

Параметры выбираются для обеспечения 112-битной классической вычислительной безопасности, другие параметры обеспечивают другие уровни безопасности, например. $q\примерно 2^{160}$ и $p\ок. 2^{1024}$ обеспечит около 80-бит классической вычислительной безопасности и $ q \ приблизительно 2 ^ {256} $ и $p\ок. 2^{3072}$ обеспечит примерно 128-бит классической вычислительной безопасности.