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



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


$\theta\rightarrow\theta^{z'}=\omega\pmod n$
и может быть реализовано абонентом X достаточно быстро - за
$O((\ln n)^2\ln\ln n)$
операций даже без использования "быстрых" алгоритмов умножения целых чисел.

Так как незаконный пользователь не знает разложения n, то простейший для него способ вычисления функции, обратной к F, состоит в разложении n на множители с последующим вычислением

$\varphi (n)$
. В общем случае сложность решения задачи разложения является достаточно большой. В течение нескольких последних десятилетий математиками было найдены несколько нетривиальных алгоритмов разложения целых чисел на множители. В частности, удалось разложить 155-разрядное девятое число Ферма
$2^{2^9}+1$
на три простых множителя. Множители имеют примерно одинаковое число разрядов. Считается, что система RSA имеет достаточную стойкость, если n имеет более 512 двоичных разрядов.

Теория кодирования доставляет много примеров стойких систем открытого шифрования. Пусть

$\mathcal C$
-- линейный код над
$\mathbf F_q$
с параметрами (n,k,b), который имеет простое декодирование, и M -- его порождающая
$k\times n$
-матрица. Пусть H -- невырожденная
$k\times k$
-матрица и
$\Gamma$
-- перестановочная
$n\times n$
-матрица.

Открытой информацией является k-мерный вектор

$\omega\in\mathbf F_q^k$
, шифрованной -- n-мерный вектор

$\hbox{\itshape ш}=\omega H\cdot M\cdot\Gamma+\mathbf e$
(функция
$F_X(\omega,K)$
), где
$\mathbf e$
-- случайный вектор веса

$wt(\mathbf e)\leqslant [(d-1)/2]$
. Секретный ключ образуют матрицы H и
$\Gamma$
, а общедоступным ключом является матрица
$M'=H\cdot M\cdot\Gamma$
. Случайный элемент
$\mathbf e$
генерирует отправитель. Матрицы H и
$\Gamma$
"маскируют" матрицу M.

Получив

$\hbox{\itshape ш}$
, абонент X вычисляет следующие элементы:

$\hbox{\itshape ш}'=\hbox{\itshape ш}\Gamma^{-1}$
, декодирует
$\hbox{\itshape ш}'$
, т. е. представляет его в виде
$\hbox{\itshape ш}'=\mathbf a+\mathbf e'$
,

$\mathbf a\in\mathcal C$
,
$wt(\mathbf e')\leqslant [(d-1)/2]$
, где

$\mathbf a=\omega H\cdot M$
, и, наконец, с помощью последнего соотношения находит w.

Проделать последнюю цепочку вычислений злоумышленнику трудно из-за того, что он не знает

$\Gamma$
. Поэтому ему трудно декодировать код
$\mathcal C'$
с порождающей матрицей M`, который для него является кодом "общего положения". Известно, что сложность N декодирования таких кодов имеет вид
$N=2^{c\min(k,n-k)}$
, т. е. при относительно небольших k и n-k является неприемлемо большой.

Если в качестве

$\mathcal C$
взять код Боуза -- Чоудхури -- Хоквингема или код Рида -- Маллера, то при подходящем k и n мы получим стойкую систему открытого шифрования. Если же в качестве
$\mathcal C$
взять код Рида -- Соломона, то получим слабую систему. Кодовые системы имеют алгоритм зашифрования информации существенно более быстрый, чем системы RSA.




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