Application of edge local complementation to McEliece cryptosystem structural analysis.pdf В криптосистеме Мак-Элиса одному и тому же открытому ключу могут соответствовать несколько секретных ключей, следовательно, они могут быть разбиты на классы эквивалентности. Возможность подобрать эквивалентный ключ напрямую влияет на стойкость данного метода шифрования, так как ключ для расшифрования не уникален. Имеющиеся исследования в данной области рассматривают ограниченный набор кодов с тривиальной группой автоморфизмов и неприменимы в структурном анализе криптосистемы Мак-Элиса. Возникает проблема поиска альтернативы предложенным методам, применимой к циклическим кодам. Вопрос изучения классов эквивалентности двоичных линейных кодов является основным в данной работе. С помощью простых преобразований двоичный линейный код можно представить в виде двудольного графа. Введённая в [1] операция ELC (Edge Local Complemetation, рёберное локальное дополнение) над ним позволяет рассматривать различные эквивалентные коды, а орбита двудольного графа под ELC является полным классом эквивалентности для кода, отвечающего данному графу. Этот способ подходит для дальнейших исследований, поскольку в целом не зависит от структуры кода. Данный метод представления и обработки графов позволяет по-новому представить классы эквивалентности двоичных кодов и классифицировать все ELC-орбиты кодов различной длины. Двоичный линейный [n, к]-код C соответствует (k, n - k)-двудольному графу G на n вершинах с матрицей смежности определённого вида. Применение любой последовательности ELC-операций к графу G, соответствующему коду C, преобразует его в граф, код которого эквивалентен C. Пусть коды C и C эквивалентны, их порождающие матрицы соответственно C и C', G и G' -двудольные графы, отвечающие C и C'. Тогда G' изоморфен графу, полученному последовательностью ELC-операций над G. Для исследования реализованы две программы на языке С. Одна из них строит по длине порождающего полинома циклического кода все возможные графы, проводит различное количество ELC-преобразований, находит изоморфные графы и подсчитывает количество классов эквивалентности (число орбит). Вторая программа принимает на вход длину двух кодов (первый - циклический) и их значения и с помощью ELC определяет, являются ли эти два кода эквивалентными. Выбор языка программирования обусловлен тем, что для нахождения изоморфных графов использована программа nauty [6], написанная на C. Поскольку в классической теории кодирования имеют применение только двудольные графы, непосредственным предметом изучения являются только они. В качестве входного набора данных генерируются все возможные порождающие многочлены для указанной пользователем длины. Любому двоичному линейному коду и соответствующей ему порождающей матрице можно сопоставить некоторый двудольный граф и его матрицу смежности и обратно. Поэтому вместо графов удобнее создавать порождающие матрицы кодов и работать с ними. В таблице приведены количество классов эквивалентности и затраченное на обработку время для многочленов различной длины. Длина многочл. Длина кода Классы эквивал. Время работы 3 7 1 < 0,01 с 4 9 1 < 0,01 с 5 11 3 < 0,01с 6 13 12 < 0,01с 7 15 31 7с 8 17 68 3663 с 9 19 168 707691 с (8 дней) Вычисления проводились на процессоре Intel Core i7 2.50 GHz. Помимо нахождения количества орбит, решается проблема поиска всех эквивалентных циклических кодов. При переборе кодов каждому из них сопоставляется орбита, после чего начинает обрабатываться следующий код и проверяется его присутствие в ранее найденных орбитах. Так как операция ELC над циклическими кодами замкнута, то есть не выводит за рамки циклических кодов, можно сказать, что все орбиты будут состоять только из них и, следовательно, находя все орбиты, мы находим все циклические коды, эквивалентные данному. В работе [1] на суперкомпьютере подсчитаны классы эквивалентности для графов с количеством вершин не более 12. На пользовательском компьютере за адекватное время удалось реализовать вычисления для 10 вершин. В данной работе только на пользовательском компьютере удалось корректно работать с графами с 17 вершинами (порождающий многочлен длины 9, код длины 19). Более важной задачей является сравнение двух кодов, один из которых циклический, на эквивалентность. Реализована программа, решающая эту задачу. Сравнение происходит следующим образом: для данного циклического графа строится орбита, после чего в ней ищется второй граф, приведённый к требуемому виду. В случае обнаружения можно утверждать, что графы эквивалентны, иначе - обратное. На персональном компьютере за приемлемое время определяется эквивалентность или её отсутствие для кодов длины 19 (граф с 37 вершинами). В ходе работы рассмотрена и изучена операция рёберного локального дополнения и эквивалентность двудольных графов и, как следствие, двоичных линейных кодов. Для циклических кодов улучшен достигнутый ранее результат скорости и качества вычислений их классов эквивалентности, а также реализован эффективный алгоритм сравнения на эквивалентность двух кодов, один из которых циклический.

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