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



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


вида

$c=a\cdot b_1+b_2$
, где Fq -- конечное поле с q

элементами. Отметим, что при каждом b из B функция

$\varphi (x,b)$
является перестановкой элементов поля
$\mathbf F_q$
, а функции
$\{\varphi (x,b);b\in B\}$
- дважды транзитивной группой перестановок на
$\mathbf F_q$
. Несколько более сложная конструкция позволяет построить систему имитозащиты, которая практически исключает возможность навязывания не только фиксированного элемента
$a'$
, но и какого-либо
$a'$
, отличного от 
$a$
. Отметим, что в рассмотренном примере одновременно с имитозащитой осуществляется и шифрование сообщения
$a$
.

С конца 70-ых годов после пионерской работы Диффи и Хеллмана было предложено значительное количество различных способов построения однонаправленных функций, предназначенных для использования в реальных системах открытого шифрования, хотя сама работа Диффи и Хеллмана была посвящена другому вопросу -- открытой генерации ключей. Основная часть этих систем открытого шифрования, построенных, до сих пор оказалась не стойкой.

Наиболее известной на настоящий момент, используемой на практике и достаточно стойкой (2001 г.) является система RSA (сокращение от фамилий авторов - Rivest, Shamir, Adleman). В этой системе законный пользователь X для построения однонаправленной функции F=FX выбирает число n=nX, являющееся произведением двух достаточно больших простых чисел p и q, и целое число z=zX такое, что

$1, [ZEBR_TAG_img src=
, где (r,m) -- наибольший общий делитель чисел r и m,
$\varphi (n)$
-- функция Эйлера (количество натуральных чисел, не превосходящих n и взаимно простых с n, или порядок мультипликативной группы
$Z_n^*$
вычетов по modn взаимно простых с n). Открытая информация, представленная целым числом w,
$(\omega,n)=1$
, шифруется с помощью общеизвестной функции

$F\colon\omega\rightarrow\theta=\omega^z\pmod n$
, действующей на
$Z_n^*$
. Числа n="nX" и zX всех абонентов сети засекреченной связи обычно помещают в общедоступный справочник. Таким образом, любой абонент может послать секретное сообщение абоненту X.

Секретная информация (ключ) законного пользователя X

состоит из чисел p и q, на которые разлагается число n. Знание p и q позволяет вычислить значение функции Эйлера

$\varphi (n)=(p-1)(q-1)$
, а затем с помощью алгоритма Евклида -- число z`, для которого
$zz'=1\pmod{\varphi (n)}$
. Очевидно, обратное преобразование
$F^{-1}_X$
имеет вид




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