Эвристика Фиата-Шамира — это общий метод построения неинтерактивной схемы доказательства (или подписи) из интерактивной схемы доказательства знаний. Ан пример интерактивной схемы, поддающейся эвристике Фиата-Шамира, является Шнорр-идентификация протокол в группе Шнорра. Я так понимаю вопрос(тот другой ответ обсудить более общую перспективу эвристики Fiat-Shamir).
Группа Шнорра — это подгруппа простого порядка $q$, и генератор $г$, принадлежащий мультипликативная группа по модулю какое-то простое $р$. Эта основная группа $\mathbb Z_p^*$ порядок $\varphi(p)=p-1$. Так как порядок подгруппы делит порядок группы, $q$ должно быть простым делением $p-1$. С $г$ является генератором, он должен быть таким, чтобы $g^q\equiv1\pmod p$ и $g\not\equiv1\pmod p$. Группа Шнорра обычно определяется как три целых числа $(р, д, г)$.
Насколько большим должно быть простое число $р$ быть? Как выбрать $р$ чтобы, например, алгоритм Полига—Хеллмана или другие известные алгоритмы не смогли его взломать?
Чтобы группа Шнорра представляла криптографический интерес, задача дискретного логарифма должна быть сложной в группе Шнорра. Это подразумевает сопротивление известным алгоритмам DLP. Алгоритм, практически определяющий необходимый размер $р$ в группе Шнорра является вариантом DLP GNFS, который исчисление индекса специализируется на $\mathbb Z_p^*$. текущая запись это 795-битный бит $р$, а минимальный рекомендуемый размер для текущих приложений — 2048 бит или 3072 бит для «2030 и более поздних версий».
Также необходимо, чтобы $q$ достаточно велик, чтобы Ро Полларда для DLP невыполнимо. Его стоимость составляет около $\Тета(\sqrtq)$ групповые умножения. Таким образом, рекомендуется минимум 224-битный или 256-битный $q$.
Этих требований достаточно, чтобы обеспечить Полиг-Хеллман Алгоритм не бояться. Это потому, что Pohlig-Hellman требует решения DLP в каждой подгруппе порядка $q^k$ с $k\ge 1$, $q$ премьер, и $q^k$ порядок деления базовой группы; и $к=1$ самый простой случай.
Как выбрать первообразный корень $г$?
Этот вероятностный полиномиальный алгоритм времени будет делать:
- выбрать случайное простое число $q$ желаемого размера
- выбрать случайно даже $г$ для премьер $p=qr+1$ желаемого размера
- выбрал случайно $s$ в $[2,p-2]$, и вычислить $g=s^{(p-1)/q}\bmod p$, до тех пор $g\ne1$ (что почти наверняка)
- в качестве проверки согласованности, проверьте $g^q\bmod p=1$ (это верно, если не было ошибки).
Безопасно ли использовать одинаковые значения $р$ и $г$ на пару испытаний?
Да. Очевидно, что знание решения конкретного DLP в группе Шнорра не помогает решить другие несвязанные случайные DLP в той же группе Шнорра (остается возможность того, что некоторые предварительные вычисления могут быть амортизированы между несколькими DLP, но это незначительно).
Почему лучше использовать группу Шнорра вместо безопасного простого числа $р$?
Безопасный премьер $р$ соответствует $p-1=2q$, или же $г=2$ выше. Хотя технически это по-прежнему соответствует определению группы Шнорра, это не соответствует ключевой мотивации групп Шнорра: наличие порядка $q$ гораздо меньшего размера, чем $р$. Это интересно, потому что показатели находятся в $\mathbb Z_q$, значит короче $q$ приводит к более быстрому возведению в степень, более коротким секретам и (в распространенном варианте эвристики Fiat-Shamir) более коротким подписям. А также поиск $р$ немного больше участвует. Насколько нам известно, использование группы Шнорра с достаточно большими $q$ и $р$ так же безопасно, как использование безопасного прайма $р$ сопоставимого размера.
