М. И. Анохин, Н. П. Варновский, В. М. Сидельников, В. В. Ященко "КРИПТОГРАФИЯ В БАНКОВСКОМ ДЕЛЕ"

Геовикипедия
wiki.web.ru

Поиск

Главная страница

Конференции: Календарь / Материалы

Каталог ссылок

Словарь

Форумы

В помощь студенту

Последние поступления

Геология | Курсы лекций

Обсудить в форуме

Добавить новое сообщение

Вперед: 11.3.4 Алгоритм Хеллмана - Рейнери Вверх: 11.3 Логарифмирование в GF(q)* Назад: 11.3.2 Алгоритм Полига - Хеллмана Содержание Предметный указатель

11.3.3 Логарифмирование в полях простого порядка

В этом подразделе мы считаем, что , т. e. будем рассматривать дискретное логарифмирование в группе , где -- простое число. Для удобства мы будем работать с полем вычетов $\mathbb{Z}_p$ по модулю и с его мультипликативной группой $\mathbb{Z}_p*$ .

В работе Коямы [Koy] приведены результаты о логарифмировании в $\mathbb{Z}_p*$ , которые означают следующее: 1. Сложность решения уравнения , где $a,b\in\mathbb{Z}_p*$ , не зависит от и .

2. Решить систему уравнений

$\displaystyle \left\{\begin{aligned} a_1^{\vphantom{X}x}=b_1\\ a_2^x=b_2 \end{aligned}\right.$

не легче, чем одно уравнение

( $a,a_1,a_2,b,b_1,b_2\in\mathbb{Z}_p*$ ).

Положим $L(p)=e^{\sqrt{\ln p\,\ln\ln p}}$ . Следующий алгоритм приводится в виде схемы, не претендующей на подробное описание:

1. Разложить на простые множители (с помощью одного из алгоритмов факторизации целых чисел): $p-1=\prod\limits_{r\in\rho}r^{e_r}$ , где $\rho$ -- конечное множество простых чисел, а $e_r\geqslant1$ .

2. Выбрать границу гладкости $L_{1}=[L(p)^{c}]$ (где -- некоторая константа) и найти множество $\pi$ всех простых чисел, не превосходящих $L_{1}$ (множество $\pi$ называется факторной базой).

3. Случайно перебирая целые числа , $1\leqslant t\leqslant p-2$ , выбрать те, для которых либо $a^t\bmod p$ , либо $ba^t\bmod p$ является гладким по отношению к границе гладкости $L_{1}$ , т. е.

$\displaystyle a^t$	$\displaystyle \equiv\prod_{s\in\pi}s^{\alpha_s(t)}\mkern5mu({\rm mod}\,\,p),$ где $\displaystyle \alpha_s(t)\geqslant0,$	(2)
или
$\displaystyle ba^t$	$\displaystyle \equiv\prod_{s\in\pi}s^{\beta_s(t)}\mkern5mu({\rm mod}\,\,p),$ где $\displaystyle \beta_s(t)\geqslant0.$	(3)

4. Пусть на предыдущем этапе найдены гладких чисел $a^{u_i}\bmod p$ , $i=1,\ldots,I$ , и гладких чисел $ba^{v_j}\bmod p$ , $j=1,\ldots,J$ . Построить векторы показателей

$\displaystyle \overline\alpha_i$	$\displaystyle =(\alpha_s(u_i)\bmod(p-1))_{s\in\pi}$ для $\displaystyle i=1,\ldots,I$
и
$\displaystyle \overline\beta_j$	$\displaystyle =(\beta_s(v_j)\bmod(p-1))_{s\in\pi}$ для $\displaystyle j=1,\ldots,J.$

Отметим, что если через $\overline\lambda$ обозначить вектор $(\log s)_{s\in\pi}$ , то, логарифмируя соотношения (2) и (3), можно получить, что

$\displaystyle u_i$	$\displaystyle \equiv\left(\overline\alpha_i,\overline\lambda\right) \mkern5mu({\rm mod}\,\,p-1)$ для $\displaystyle i=1,\ldots,I$	(4)
и
$\displaystyle \log b+v_j$	$\displaystyle \equiv\left(\overline\beta_j, \overline\lambda\right)\mkern5mu({\rm mod}\,\,p-1)$ для $\displaystyle j=1,\ldots,J,$	(5)

где $(\cdot,\cdot)$ обозначает скалярное произведение по модулю

$\displaystyle ((x_s)_{s\in\pi},(y_s)_{s\in\pi})=\sum_{s\in\pi}x_sy_s\bmod(p-1).$

5. Для каждого $r\in\rho$ выразить один из векторов $\overline\beta_j\bmod r^{e_r}$ через векторы $\overline\alpha_i\bmod r^{e_r}$ . Для того, чтобы это было возможно, должно быть достаточно велико.

6. Пусть на предыдущем этапе найдено соотношение $\overline\beta_j\equiv\sum\limits_{i=1}^{I}\gamma_i \overline\alpha_i\mkern5mu({\rm mod}\,\,r^{e_r})$ , где $\gamma_i\in\mathbb{Z}_{r^{e_r}}$ . Тогда из (4) и (5) следует, что

$\displaystyle \log b\equiv-v_j+\left(\overline\beta_j,\overline\lambda\right) \... ...bda\right)\equiv-v_j+\sum_{i=1}^{I}\gamma_i u_i\mkern5mu({\rm mod}\,\,r^{e_r})$

и, следовательно, мы можем найти $(\log b)\bmod r^{e_r}$ .

7. Вычислив $(\log b)\bmod r^{e_r}$ для всех $r\in\rho$ , с помощью китайской теоремы об остатках найти $(\log b)\bmod(p-1)$ .

Приведенный алгоритм описан в работе Адлемана [Adl], но основные идеи этого алгоритма были изложены в работе Вестерна и Миллера [WM] в 1968 г. В [Adl] получена эвристическая оценка $O(L(p)^{c_{1}})$ его сложности при условии использования одного из субэкспоненциальных алгоритмов для факторизации . В этой работе рассмотрен и случай, когда не является порождающим $\mathbb{Z}_p*$ , т. е. логарифмирование производится в подгруппе группы $\mathbb{Z}_p*$ . Также замечено, что этот общий случай можно свести к случаю, когда является порождающим $\mathbb{Z}_p*$ .

Заметим, что, вообще говоря, факторизация не является необходимой. Достаточно найти один гладкий элемент $ba^v\bmod p$ и пытаться выразить его через произведение степеней гладких элементов $a^{u_i}\bmod p$ , т. е. проводить исключение в показателях сразу по модулю .

На этапе 5 алгоритма приходится решать разреженные системы линейных уравнений в кольцах вычетов $\mathbb{Z}_m$ . В ряде работ (см. [Copp], [COS]) указано, что метод гауссова исключения здесь не является оптимальным. Предлагается использовать, например, алгоритмы Ланцоша [Lanc] или Видемана [Wied] (см. об этом [COS]). В работе [Gord] описан новый метод исключения, предложенный Померансом.

Дальнейшее развитие указанного метода логарифмирования в $\mathbb{Z}_p*$ получено Копперсмитом, Одлыжко и Шреппелем в работе [COS]. Сложность вычисления дискретного логарифма доведена до $L(p)^{1+o(1)}$ . Согласно [McC90, стр. 66], алгоритм [COS] был реализован на ЭВМ; результат (см. [LaMO]) позволяет предположить, что вычисление логарифма в $\mathbb{Z}_p*$ на ЭВМ можно проводить за реальное время при порядка $10^{100}$ .

Михаил Анохин

Проект осуществляется при поддержке:
Геологического факультета МГУ,
РФФИ