Этот ответ ограничивается группами при операции умножения по модулю большого простого числа. $р$, потому что это вопрос (другие группы все чаще встречаются в криптографии, включая группы эллиптических кривых).
Так что будем работать в группе $\mathbb Z_p^*$, обозначение подмножества кольца $\mathbb Z/p\mathbb Z$ образован элементами с мультипликативной инверсией, которые, как можно показать, образуют группу. С $р$ простое, $\mathbb Z/p\mathbb Z$ это поле, и $\mathbb Z_p^*$ это поле меньше нейтрального для добавления. $\mathbb Z_p^*$ можно уподобить целым числам $\{1,2,\ldots,p-2,p-1\}$. Оно имеет $p-1$ элементы. Внутренний закон этой группы - умножение по модулю $р$.
Мы хотим группу $\mathbb Z_p^*$ (или их подгруппа), в которых вычисление дискретного логарифма затруднено. Условия для этого (как доказуемо необходимые, так и предполагаемые достаточные, когда оба выполняются):
- Порядок группы (то есть количество элементов) должен иметь достаточно большой простой множитель $q$ чтобы блокировать Полиг-Хеллман в сочетании с Ро Полларда, который может вычислить логарифм с усилием $\mathcal O\,\left(\sqrt q(\ln n)^3\right)$ и умеренная память, когда-то $р$ и $q$ известны. Таким образом, мы хотим $q$ не менее 256-битной 128-битной защиты.
- $р$ должен быть достаточно большим, чтобы блокировать алгоритмы индексное исчисление. Это потребует $р$ от 2048 до 4096 бит (в зависимости от консерватизма, гипотезы и источника) для 128-битной безопасности, при дальнейшем предположении $р$ не слишком близко к степени небольшого целого числа.
Как настраиваются практические системы дискретного логарифмирования?
Прежде всего, нужно решить, какую структуру дискретного логарифмирования мы хотим настроить, и это зависит от того, для чего мы планируем ее использовать. Обычно используются три вида:
- Полная группа $\mathbb Z_p^*$, с заказом $2q=p-1$ и $q$ основной. Этот используется, когда что-то требует генератора полной группы (как вопрос «генератор мультипликативной группы $\mathbb Z/p\mathbb Z$"принято к письму делает).
- Подгруппа квадратичных вычетов простого порядка $q=(p-1)/2$. Его элементы $у$ в $\mathbb Z_p^*$ что можно записать как $у=и^2$ для некоторого элемента $u$ из $\mathbb Z_p^*$ (а затем и для $u'=p-u$, конечно). Есть стандартные такие группы с генератором $г=2$, видеть RFC 3526. Их можно использовать для большинства целей, не требующих генератора полной группы.
- Меньшее подмножество подмножества квадратичных вычетов с простым порядком $q=(p-1)/r$ для некоторых (даже) $г$. Их называют группой Шнорра. Они используются в оригинальной подписи Шнорра и DSA.
Часто есть причина не использовать (1.): if $г$ является генератором (то есть любой элемент группы может быть представлен в виде $г^х$ ), то от значения $г^х$ легко сказать, если $х$ четно или нечетно (путем вычисления Символ Лежандра). Это противоречит гипотезе, желательной для простых доказательств безопасности, целям доказательств с нулевым разглашением и может позволить атаки (например, шифрование Эль-Гамаля не работает). цена за конверсию).
Иногда есть причина не использовать (2.) и предпочесть (3.): по крайней мере, в приложениях подписи один из компонентов подписи имеет тот же битовый размер, что и $q$, который должен быть большим, но может быть намного меньше, чем $р$. Таким образом, используя небольшой $q$ позволяет использовать более короткие подписи. Вот почему были введены группы Шнорра.
Для (1.) и (2.), порождая $р$ и $q$ сводится к созданию простого $q$ с $p=2q+1$ также премьер. Эффективно провести относительно быстрый тест, $q$ не является составным (например, тест Ферма по основанию 2: проверьте, что $2^{q-1}\bmod q=1$), затем тщательный тест, который $p=2q+1$ является простым; затем тщательный тест, который $q$ является простым. Далее, для небольшого простого числа $s$, он держит $q\bmod s\not\in\{0,(s-1)/2\}$. Таким образом $q\bmod3=2$, $q\bmod5\in\{1,3,4\}$, таким образом $q\bmod30\in\{11,23,29\}$, что сужает поиск. Учитывая немного большую $s$ можно использовать для сита или другого ускорения.
Также можно показать, что для $р$ и $q$ что касается (1.) или (2.), $г=2$ является образующей для (1.) тогда и только тогда, когда $q\bmod4=1$ (эквивалентно $p\bmod8=3$ ); и генератор для (2.) в противном случае. Таким образом, использовать $г=2$ (наименьший возможный генератор, и тот, который немного упрощает некоторые вычисления), мы хотим $q\bmod60\in\{29,41,53\}$ для (1.) и $q\bmod60\in\{11,23,59\}$ для (2.).
Для (3.) мы можем выбрать случайное простое число $q$ желаемого размера, затем случайным образом даже $г$ достаточного размера, чтобы иметь $p=q\,r+1$ основной. Генератор $ г = 2 ^ г $ (если только это $1$, что, по крайней мере, крайне маловероятно; Интересно, возможно ли это):
Если нам нужен генератор случайных чисел, мы можем выбрать случайный секрет $х$ в $[1,q-1]$ и использовать $г$ следующее:
- для (1.) и $p\bmod8=3$: $g\gets2^{2x+1}$
- для (1.) и $p\bmod8=7$: методом проб и ошибок находим $у$ с $y^{(p-1)/2}\bmod p\ne 1$ (равнозначно с $y^{(p-1)/2}\bmod p=p-1$ ); ожидаемое количество попыток составляет около двух, если мы исследуем последовательные нечетные $u$ начиная $и=3$; тогда $ г \ получает и ^ {2x + 1} $.
- для (2.), $g\gets2^{2x}$
- для (3.), $g\gets2^{((p-1)/q)\,x}$
Алгоритм поиска неизвестен. $г$ за полиномиальное время.
Это верно, если факторизация группового порядка неизвестна или если мы ограничимся детерминированный алгоритмы. Но на практике порядок известен, иногда мы можем предсказать генератор, а в противном случае простые вероятностные алгоритмы быстро дадут его.
Есть ли какие-нибудь пакеты с большими номерами?
Python имеет встроенную поддержку больших чисел, и создание параметров является простым упражнением. $(п,г)$ на чистом питоне. Единственными легкими трудностями являются простой тест и случайное генерирование простых чисел. Но их можно сделать на чистом Python, и они поддерживаются в нескольких пакетах, включая SymPy. С $(п,г)$ обычно являются общедоступными, побочные каналы не являются проблемой.
