The Reed - Muller code square and equivalence classes of McEliece - Sidelnikov cryptosystem private keys.pdf Криптосистема Мак-Элиса - Сидельникова [1] является модификацией распространённой кодовой криптосистемы Мак-Элиса [2]. Кодовыми называются криптосистемы, основанные на задачах из теории кодов, исправляющих ошибки. Такие системы обладают одной отличительной особенностью: одному и тому же открытому ключу может соответствовать некоторое множество секретных ключей, поэтому секретные ключи могут быть разбиты на классы эквивалентности. Вопрос изучения этих классов актуален, так как знание их структуры позволяет строить эффективные атаки на кодовые криптосистемы [3]. Секретным ключом криптосистемы Мак-Элиса - Сидельникова является кортеж (H1,H2, Г), где H1,H2, Г - матрицы над полем GF(2), причём H1,H2 -невырожденные, а Г - перестановочная. Открытым ключом криптосистемы является матрица G' = (H1R || H2R) • Г, где символом || обозначена конкатенация матриц по столбцам; R - стандартная форма порождающей матрицы кода Рида - Маллера RM(r, m). В [4] установлена связь между классом эквивалентности [(H1,H2, Г)] секретных ключей и множеством G(H1,H2) подстановок Г, для которых существуют невырожденные двоичные матрицы Hj, H2, такие, что (H1R || H2R) • Г = (HjR || H2R). Поэтому задача изучения классов эквивалентности секретных ключей свелась к задаче изучения структуры множества G. Пусть C - код с порождающей матрицей (R || HR), где H = H-1H2. Утверждение 1. C2 С RM(2r,m) х RM(2r,m). Теорема 1. Если C2 = RM(2r,m) х RM(2r,m), то G = Aut(RM(r,m)) х Aut(RM(r,m)). Таким образом, для случая равенства можно получить описание классов эквивалентности. В случае строгого вложения можно рассмотреть матрицу H специального вида, такую, что в ней существует ортогональная подматрица H, которая расположена с точностью до перестановки строк и столбцов следующим образом: " H H1 " 0 H2 J Для матрицы вида (1) верны следующие факты. Теорема 2. Если матрица H имеет вид (1), то имеет место строгое вложение C2 С RM(2r,m) х RM(2r,m). Теорема 3. Если выполнено строгое вложение C2 С RM(2r, m) х RM(2r, m) и подпространство, порождённое строками матрицы (HT | 0 || E | 0), пересекается с (C2)x, то матрица H имеет вид (1). Утверждение 2. Доля матриц вида (1) среди невырожденных матриц размера k х k есть O(k22-k). Таким образом, доля матриц H вида (1) мала, а значит, почти всегда известна структура множества G и можно описать классы эквивалентности секретных ключей криптосистемы Мак-Элиса - Сидельникова.

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