Расчёты учёных из Коннектикутского университета и Университета Нью-Мексико (оба — США) свидетельствуют о том, что криптосистема Мак-Элиса может противостоять квантовым атакам.

Профессор Массачусетского технологического
института Питер Шор.

Разработанный в 1978 году алгоритм Мак-Элиса относится к классу систем с открытым ключом. В эту же группу криптосистем входят, как известно, популярные схемы Эль-Гамаля и Райвеста — Шамира — Адлемана (RSA). Все они базируются на использовании односторонних функций с «лазейкой», то есть функций, которые позволяют легко вычислить значение f(x) по известному x, но не дают возможности проделать (за разумное время) обратную операцию. «Лазейка» — это ключ, некий y, при объединении с f(x) образующий достаточную для быстрого расчёта x пару. В основу системы RSA, к примеру, положена задача факторизации (разложения чисел на простые множители), которая считается сложной.

Все эти рассуждения, однако, справедливы только для классических компьютеров. Ещё в 1994 году американский математик Питер Шор предложил квантовый алгоритм факторизации, уменьшающий время решения задачи. Если он будет реализован, системы Эль-Гамаля и RSA окажутся под угрозой взлома.

Криптосистема Мак-Элиса имеет несколько отличающееся математическое основание, что, как показали авторы рассматриваемой работы, позволяет ей отражать квантовые атаки. К сожалению, она не слишком популярна и редко используется на практике; одним из основных её недостатков считается огромный размер открытого ключа.

Необходимо понимать, что математики не гарантируют полной защищённости системы Мак-Элиса, поскольку они не могут предугадать, какие квантовые (или классические) алгоритмы появятся в будущем.

Препринт статьи можно скачать с сайта arXiv.

Подготовлено по материалам Technology Review.

Текст: Дмитрий Сафин