Аннотация:Для безопасной передачи секретных ключей пользователей в криптографических протоколах широко
используется асимметричная криптография, основу которой составляют криптосистемы с открытым ключом.
Криптосистема Мак-Элиса~--- это одна из старейших криптосистем с открытым
ключом.
Она была предложена в 1978 году Р.Дж.~Мак-Элисом. Основная идея построения этой криптосистемы состоит
в маскировке некоторого линейного кода, имеющего эффективные алгоритмы декодирования, под код,
не обладающий видимой алгебраической и комбинаторной структурой. Такие коды принято называть кодами общего положения.
Предполагается, что декодирование кода общего положения является вычислительно трудной задачей.
Следует отметить, что отсутствие эффективных квантовых алгоритмов декодирования кода общего положения делает криптосистему Мак-Элиса важной альтернативой таким криптосистемам, как криптосистема RSA и криптосистема Эль-Гамаля, которые получили широкое практическое применение, но при этом они станут бесполезными в постквантовую эру.
Кодовые криптосистемы обладают одним недостатком, который не позволяет их использовать в устройствах с ограниченными ресурсами. У криптосистемы Мак-Элиса достаточно большая длина ключа. Классическая криптосистема Мак-Элиса строится на основе двоичных неприводимых кодов Гоппы. Для генерации таких кодов необходимо порождать неприводимые многочлены над расширениями конечных полей. Эта задача решается сравнительно медленно и значительное количество ресурсов. Кроме того, для декодирования неприводимых кодов Гоппы применяется алгоритм Паттерсона. Известно, что в этом случае на криптосистему Мак-Элиса возможны атаки по побочным каналам.
В работе М.С. Макаренковой предлагается модификация криптосистемы Мак-Элиса, которая устраняет описанные недостатки криптосистемы Мак-Элиса. М.С. Макаренкова, используя идеи работы D.J.Bernstein, Tung Chou, P.Schwabe <<McBits: fast constant-time code-based cryptography>>, построила криптосистему, в которой алгоритм генерации ключей работает в разы быстрее, чем в классической криптосистеме. Криптосистема была реализована на языке C++, для некоторых рекомендуемых параметров были получены значения скорости работы алгоритмов шифрования, расшифрования и генерации ключей.
В работе удалось модифицировать алгоритм Берлекэмпа-Месси и применить его к декодированию двоичных сепарабельных кодов Гоппы. Замена алгоритма Паттерсона на алгоритм Берлекэмпа-Месси делает известные атаки, использующие побочные каналы, неприменимыми к модифицированному варианту криптосистемы.