About McEliece cryptosystem with algebraicgeometric Codes.pdf В последние годы внимание многих специалистов в области криптографии с откры-тым ключом уделено развитию кодовых криптосистем, в частности схем Мак-Элиса и1 Работа поддержана грантом РФФИ, проект №6260.2012.10.Нидеррайтера. Их стойкость основана на вычислительной сложности задачи декоди-рования кода, порождающая (или проверочная) матрица которого выглядит как некаяслучайная матрица.С точки зрения стойкости такой системы крайне важен выбор семейства кодов.В «оригинальной» системе Мак-Элиса используется классический двоичный код Гоп-пы. В работе [1] рассматривается возможность применения [961, 771]з1-кодов Гоппы,который, при одинаковой стойкости по сравнению с двоичным кодом Гоппы, дает су-щественно меньшую длину открытого ключа. Продолжение исследований, связанныхс обоснованием преимуществ недвоичных кодов Гоппы, содержится в работе [2].Долгое время считался удачным выбор В. М. Сидельниковым [3] двоичного кодаРида - Маллера. Однако в работе [4] предложен субэкспоненциальный алгоритм ата-ки на такую систему. При этом используется возможность нахождения кодового словаминимального веса кода RM(r, m) как произведения r слов (функций) минимально-го веса из RM(1,m). Этот алгоритм оказался эффективен для кода Рида - Маллератретьего порядка длины 2048.Как показано в [5], к нестойкой системе приводит использование кодов Рида - Со-ломона в системе Нидеррайтера. На первом этапе полиномиального алгоритма вскры-тия системы использована трижды транзитивность группы обобщённых автоморфиз-мов указанных кодов.Ранее автором (см. [6]) найдена конструкция классов алгебро-геометрических ко-дов над различными конечными полями с очень хорошим соотношением скорости иотносительного расстояния, в частности семейство {Cr : [768, 3r - 57, 768 - 3r]256}2=539кодов на кривой над P = GF(28), заданной уравнением y3 = x60 + x57 + x54 + . . . + x3 + 1.Каждый из построенных кодов Cr = C(D, G) определяется дивизорами D и G, гдеD - формальная сумма всех P-рациональных точек Q 1 , . . . , Q768 кривой, а G = r Q^,.Векторами кода C являются векторы значений функций от двух переменных x и yиз некоторого класса Ф0, который, при условии 114 < deg G = 3r < 768, обра-зует линейное подпространство размерности 3r - 57 над полем P с базисом B == { x lyj : j = 0,1, 2, i = 0 , 1 , . . . , r - 20j} пространства Ф всех функций от x, y над P.Из данного кода методом, основанным на проектировании кодов, получаются се-мейства кодов = C(D',G), где D' есть сумма m произвольных P-рациональныхточек кривой при условии 114 < deg G = 3r < m ^ 768. При выполнении указанныхусловий размерности полученных кодов совпадают с размерностью «исходного» ко-да Cr . Таким образом, при фиксированном m получается до ( ) кодов длины mmи размерности 3r - 57. При этом кодовое расстояние d любого из кодов равноd = m - 3r.Нетрудно оценить величину числа m, обеспечивающую стойкость кодовой системык перебору всех 768 сочетаний вошедших в дивизор точек кривой, а также к пере-mбору всех возможных векторов-ошибок.С другой стороны, мы получаем возможность варьировать длину и размерностькодов для получения оптимальных параметров системы.Таким образом были выделены семейства кодов C^: [m, 3r - 57, m - 3Г]256-КОДЫ приm = 150, 739, r = 39, 235.Порождающая матрица каждого из этих кодов C получается из порождающейматрицы кода C удалением 768 - m столбцов, соответствующих точкам кривой, уда-лённым из дивизора D при переходе к дивизору D'.Для рассматриваемых кодов и во введённых обозначениях справедлива следующаятеорема.Теорема 1. Пусть Cr = C(D, G) -код, в котором дивизор D = Qi + . . . + Q768есть сумма всех P-рациональных точек кривой, заданной уравнением y3 = x60 + x57 ++x5 4 + . . . + x3 + 1. Тогда в порождающей матрице этого кода нет одинаковых столбцов.Для каждого фиксированного кода из рассматриваемых семейств при r ^ 127 ификсированном m получается - ( ) различных кодов.18 \ m /Доказательство теоремы конструктивно и даёт возможность выбора точек дивизо-ра D' так, чтобы все полученные коды были различны.Код C при указанных выше значениях r изоморфен пространству Ф0. Описаниеавтоморфизмов алгебры Ф, оставляющих на месте Ф0, дает следующая теорема.Теорема 2. В указанных выше обозначениях при 39 ^ r ^ 127 каждый авто-морфизм линейной алгебры Ф, отображающий Ф0 на себя, задается образами x, y:

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