- •Лекция 6 Пост-квантовая криптография
- •Влияние квантового компьютера на существующие криптосистемы
- •Новые криптосистемы
- •Параметры схем электронной подписи
- •Схемы шифрования и обмена ключами
- •Параметры схем шифрования и распределения ключей
- •2. Криптосистемы на основе алгебраического кодирования
- •Пример линейного кода
- •Декодирование линейных кодов
- •Криптосистемы на основе алгебраического кодирования
- •Криптосистема Ниддерайтера 1986 г.
- •Алгоритмы шифрования -дешифрования
- •Выводы
Криптосистемы на основе алгебраического кодирования
Роберт |
Геральд |
Мак-Элис, |
Ниддерайтер |
1978 год |
1986 год |
Описание КС Мак-Элис
2. КриптосистемаМас-Элис
Если пользователь A хочет сгенерировать свою пару открытый/закрытый ключ, то эта процедура реализуется следующими шагами:
1) генерируется случайная порождающая матрица GA для специального подкласса двоичных (n, k)-кодов (скажем, для кода Гоппы), которые гарантированноисправляют tA ошибок и имеютполиноминальносложный алгоритм декодирования;
GAk×n
2) генерируется случайная двоичная несингулярная (т. е. имеющаяненулевой определитель) матрица S A размером k ×k ;
SAk×k
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)большая битовая длина как открытого, так и закрытого ключей.
Последнее свойство особенно существенно ограничивает практическое применениеКС Мак-Элис.