Криптография - статьи



О современной криптографии - часть 10


Другими идейно близкими к открытому шифрованию являются методы построения "открытого ключа" (public key), т. е. методы создания общего ключа двух абонентов или большего числа абонентов, недоступного для внешнего наблюдателя, с помощью обмена между ними информацией по общедоступному каналу связи. После создания ключа пользователи могут использовать его, например, как ключ для традиционного симметричного шифрования.

Для примера рассмотрим один популярный метод построения открытого ключа в сети абонентов Xj,

$j=1,\ldots,N$
, предложенный Диффи и Хеллманом. Пусть
$\mathbf F_q$
-- конечное поле с достаточно большим числом элементов q и
$\xi$
-- первообразный элемент мультипликативной группы G этого поля. Каждый из абонентов Xj и Xi один независимо от другого выбирают по секретному числу xj,xi,
$0. Затем абоненты каким-либо образом обмениваются элементами [ZEBR_TAG_img src=
,
$a_i=\xi^{x_i}$

поля, например, помещают их в общедоступный справочник. Для образования секретной связи между Xj и Xi первый абонент вычисляет элемент

$(a_i)^{x_j}=(\xi^{x_i})^{x_j}$
, а второй --
$(a_j)^{x_i}=(\xi^{x_j})^{x_i}$
. Таким образом, у каждого из абонентов образуется один и тот же элемент
$\xi^{x_ix_j}$
поля
$\mathbf F_q$
, который и является "открытым ключом".

С сохранением основной идеи метода в качестве G вместо мультипликативной группы конечного поля можно использовать любую циклическую группу. В частности, в  рассматривалась группа, образованная

$\mathbf F_q$
-рациональными точками эллиптической кривой, заданной над некоторым подполем конечного поля
$\mathbf F_q$
. Изучались также и некоторые другие группы G.

Проблема оценки стойкости для приведенного примера на первый взгляд сводится к определению сложности вычисления

$\xi^{xy}$
при известных
$a=\xi^x$
и
$b=\xi^y$
(задача Диффи -- Хеллмана). В настоящее время эта задача решается следующим образом: сначала вычисляются число x -- индекс элемента
$a$
(дискретный логарифм
$a$
по основанию
$\xi$
), а затем находится ключ
$\xi^{xy}=b^x$
. Решение уравнения

\begin{displaymath} \xi^x=a \end{displaymath}

в какой-либо группе обычно называют задачей логарифмирования. Проблема поиска нетривиальных эффективных методов логарифмирования является одной из центральных для современной криптографии и рассматривалась во многих работах (подробный обзор имеется в ).




Содержание  Назад  Вперед