The generalized automorphisms of Reed-Muller code and McEliece-Sidelnikov public key cryptosystem..pdf Криптосистема Мак-Элиса-Сидельникова относится к классу кодовых криптосистемс открытым ключом. Криптосистема была предложена В. М. Сидельниковым вработе [1].Кратко опишем устройство криптосистемы Мак-Элиса-Сидельникова. Пусть R -(k х n)-порождающая матрица кода Рида-Маллера RM(r, m). Секретным ключомкриптосистемы является кортеж (Hl , H2, . . . , Hu, Г). Здесь Hl , H2, . .. , Hu - невырожденныеk х k-матрицы над полем F2 = (0 ,1 }, которые выбираются случайно и равновероятноиз множества G L (F 2) всех двоичных невырожденных k х k-матриц надполем F2. Матрица Г - перестановочная (u n х u n)-матрица.Открытым ключом криптосистемы Мак-Элиса-Сидельникова является матрицаG' = (HlR|H2R| ... ||HuR) Г, где символом || обозначена конкатенация матриц постолбцам. Алгоритмы шифрования и расшифрования подробно описаны в [1].Два секретных ключа (Hl , H2, . .. , Hu, Г) и (H i, H2, . . . , H , Г') назовем эквивалентными,если соответствующие им открытые ключи совпадают, то есть выполняетсясоотношение (HlR|H2R| ... ||HuR) Г = (HiR||H2R|| . .. ||H'R) Г'.Рассмотрим множество G(Hl , H2, . .. , Hu), состоящее из перестановок Г . Sun, длякоторых существуют невырожденные двоичные матрицы H i, H2, . . . , H ', такие, что(HlR|H2R| . .. H H R ^ = (HiR|H2R|| ... ||H'R). В работе такие множества называютсямножествами обобщенных автоморфизмов кода Рида-Маллера. Отметим, чтоэти множества, в отличие от множества обычных автоморфизмов, не всегда являютсягруппами.Вопрос изучения эквивалентных секретных ключей, а значит, и вопрос изучениямножества открытых ключей, сводится к изучению множеств G(Hl , . .. , Hu), то естьобобщенных автоморфизмов.Обобщенные автоморфизмы и структура множества открытых ключей могутоказаться полезными для криптоанализа криптосистемы Мак-Элиса-Сидельникова.Так, знание некоторой структуры группы автоморфизмов обощенных кодов Рида-Соломона позволило В. М. Сидельникову и С. О. Шестакову [2] произвести взлом криптосистемыМак-Элиса на основе этих кодов.Перейдем к описанию множеств обобщенных автоморфизмов.В случае произвольного u справедлива следующая теорема.Теорем а 1. Пусть для невырожденных матриц D l , D2, ... , существуют такиеперестановки Pj(1 ^ i ^ n) из Sn, что D lR = R Pl , D2R = R P2, ... , DuR = R Pu.Обозначим через P l [1],P2[2],.. .,Pu[u] перестановки из A u(RM (r,m )), соответствующиеперестановкам Pl , P2 ... , Pu. И пусть H - любая невырожденная матрица.Тогда G (E ,. . . , E) = Pi[1] P2[2]. .. P„[u] G (H D i,. . . , HD«).Описание множества G (E ,. .. , E ) получено Г. А. Карпуниным [3].Рассмотрим теперь случай u = 2.Для некоторого вектора a = ( a i , . .. , an), а = 1, рассмотрим матрицу T- вида(1 00 1i -- ai a20 0iI00\vПервый случай - i = 1. Справедлива теорема.Теорем а 2. Пусть i = 1, тогдаG (E ,T i) = {Г G G(E, E)|(0|(e1 © a )R )r G RM (r,m ) x RM (r ,m )}.Здесь символом ei обозначен вектор, у которого на первом месте стоит 1 , а на всехостальных местах - 0.При изучении обобщенных автоморфизмов в случае i > 1 возникает необходимостьв исследовании эквивалентности некоторых специальных (k - 1)-мерных подпространствкода Рида-Маллера RM(r, m). В результате изучения подпространствкода Рида-Маллера получено описание множества G(E,T~) для i > 1. Теорема 3 даетэто описание.Теорем а 3. Пусть RM(r, m) - код Рида-Маллера, такой, что 2r ^ m, i > 1, H -любая невырожденная двоичная матрица, a - произвольный двоичный вектор, у которогов координате с номером i стоит единица. Тогда множество G (H, HT~) содержит теи только те перестановки Г, которые могут быть представлены в виде Г = Г (о^Цад),где ol, or - автоморфизмы кода Рида-Маллера RM(r, m), а для перестановки Г выполняютсядва условия:1) если R' - (k - 1) x n-матрица, получающаяся выкидыванием строки с номером iиз матрицы R, то (R'HR/) r / = (R; ||R;);2) если rl - строка матрицы R с номером i, то (ri |aR )r/ G RM(r, m) x RM(r, m).

Скачать электронную версию публикации