Криптосистемы на основе алгебраического кодирования

Роберт	Геральд
Мак-Элис,	Ниддерайтер
1978 год	1986 год

Описание КС Мак-Элис

2. КриптосистемаМас-Элис

Если пользователь A хочет сгенерировать свою пару открытый/закрытый ключ, то эта процедура реализуется следующими шагами:

1) генерируется случайная порождающая матрица GA для специального подкласса двоичных (n, k)-кодов (скажем, для кода Гоппы), которые гарантированноисправляют tA ошибок и имеютполиноминальносложный алгоритм декодирования;

GAk×n

2) генерируется случайная двоичная несингулярная (т. е. имеющаяненулевой определитель) матрица S A размером k ×k ;

SAk×k

PAn×n

3) генерируется случайная перестановочная	n ×n матрица PA
(перестановочной называется такая матрица PA ,	произведение

которой на любой вектор дает лишь перестановку его позиций. Такая матрица содержит в каждой строке и в каждом столбце по одной единице, а остальные ее элементы – нули.);

4) вычисляется матрица

SA GA PA

(ее размерность

GA =

будет

k ×n

);

Задается параметр безопасности tA

5) публикуется открытый ключ

, и сохраняется в

GA , tA

тайне секретный ключ

(S A , GA , PA ) .

n

n

k

×

n

× n

k

= k

SA

k

GA

PA

GA

Шифрование КС Мак-Элис

Если пользователь В хочет зашифровать сообщение M для пользователя А, то он долженвыполнитьследующие шаги:

1)получить от А открытый ключ ( GA , tA ) ;

2)преобразовать сообщение M в последовательность

двоичных блоков Mi длины k. Далее для	каждого из
полученных блоков проделать следующие шаги 3–5;
3) сгенерироватьслучайный двоичный вектор	Zi длины n и
веса (т. е. числа единицв нем) не более tA ;

4)вычислить двоичный вектор Ci = MiGA Zi ;

5)послать вектор Ci к пользователю А как криптограмму для сообщения Mi .

			Дешифрование КС Мак-Элис
	Для того чтобы восстановить сообщение					Mi	по
криптограмме Ci, пользователь А должен выполнить следующие
шаги:					P−1, где PA−1 – это
	1) вычислить C			=C		матрица, обратная
P		;	i	i	A
A
	2) используя известный алгоритм декодирования для кода с

порождающейматрицей GA , исправитьне более tA ошибок в
C		, что даст некоторый двоичный вектор				длины k;
i				−1	Mi
	3) восстановить Mi
			= Mi S.A
	Для доказательства		того,	что описанная		выше процедура

действительно восстанавливает зашифрованное сообщение Mi ,
преобразуем сначала представлениедля Ci:
Ci =Ci PA−1 =(MiGA Zi )PA−1 =	(3.15)

=(Mi SAGA PA Zi ) PA−1 =(Mi SA )GA Zi PA−1.

Из выражения (3.15) видно, что двоичный вектор C							представляет
					i
собой закодированноеЛК (с порождающей матрицей GA) сообщение
(Mi S A )		с добавкой двоичного шума			Zi PA−1 веса не более tA ,
так как	PA−1	будет также перестановочной матрицей,					умножение на
которую сохраняет вес слова Zi , который был определен ранее не
болеечем tA .
Поскольку		код с	порождающей	матрицей		GA		может
гарантированно исправить не менее				tA	ошибок, это означает, что
по C	пользователь A может абсолютно точно восстановить (Mi S A ),
i
причемсложность декодирования будет при этомполиномиальной.
Наконец,		исходное	сообщение	Mi	восстанавливается			после
умножения последнего результата на				S A−1, т. е.

Mi S A S A−1 = Mi .

Заметим, что в отличие от метода РША и подобно тому, как это было в шифре Эль-Гамаля, метод Мак-Элис является рандомизационным, поскольку случайный вектор помехи Zi не входитв составключей этой КС.

Если на шаге 1 генерирования ключей используется семейство кодов Гоппы, то можно иметь в виду [3], что для

любого неприводимого над полем	GF(2m )		многочлена
g(x) степени tA существует двоичный		код	Гоппы	длины
n = 2m с числом информационных символов		k ≥ n −mtA ,		где

tA – число ошибок, исправляемых этим кодом, причем этот код имеетполиномиальносложный алгоритм декодирования.

СтойкостьКС Мак-Элис

Рассмотрим две основные атаки на КС Мак-Элис:

1) зная Ci	, GA	,	tA , можно попытаться исправить
ошибки в Ci , но поскольку, как легко убедиться, порождающая
матрица GA	является		совершенно	случайной,	для
определяемого	ей кода		не известно непереборных методов

исправления ошибок, а переборные практически нереализуемы присоответствующем выборе параметровисходногокода;

2) для восстановления

Mi

можно попытаться случайно выбрать

k столбцов в матрице

.

Если

теперь

обозначим

через

GA

G

,C

,

Z

ограничение

,C , Z

этими столбцами,

то будет

k

k

G

A

i

k

(

Сk

i

выполняться уравнение

+Zk )= Mi Gk .

Если случайно

окажется, что

Zk

=

0 и

несингулярна, то

M

i

может

быть

G

k

получено как решение уравненияCk = M Gk. Однако вероятность

того, что

Zk

= 0 , оказывается равной

Cnk−t / Cnk ,

и

при

соответствующем выборе параметров она будет весьма малой величиной.

Для обеспечения высокой стойкости КС Мак-Элис рекомендуются следующие ее параметры [3]: n =1024 бит, t = 38, k > 644 .

Представленный ранее материал позволяет сформулировать следующие основныесвойстваКС Мак-Элис:

1)достаточно предсказуемая стойкость;

2)простота шифрованияи дешифрования;

3)увеличение длины криптограммы по сравнению с длиной сообщенийв n / k раз;

4)большая битовая длина как открытого, так и закрытого ключей.

Последнее свойство особенно существенно ограничивает практическое применениеКС Мак-Элис.