dxdt.ru: занимательный интернет-журнал

ML-KEM/Kyber – быстрая криптосистема. На типовой современной аппаратуре она быстрее и чем X25519, и чем ECDH, и чем RSA. К тому же – с заявленной постквантовой стойкостью. Почему подобную криптосистему не внедрили для Интернета раньше, и в качестве основной? Можно же предположить, что вместо RSA и классического протокола Диффи-Хеллмана разработали бы что-то сразу с постквантовой стойкостью?

Публикация алгоритма Шора тут, очевидно, играет важную роль. Но криптосистемы с постквантовой стойкостью предлагались и раньше, до публикации Шора. Да, современного понятия о “постквантовой стойкости” тогда не было, но неверно и считать, что алгоритм Шора взламывает всё, что было предложено раньше этого алгоритма. Например, криптосистема McEliece, в исходном варианте, предложена в 1978 году, за 16 лет до алгоритма Шора. Но алгоритм Шора не позволяет взломать McEliece, а постквантовая стойкость может идти в качестве автоматического бонуса. Однако современные варианты McEliece стали внедрять на практике недавно, уже после того, как “постквантовый шум” набрал обороты, и как раз по причине стойкости к алгоритму Шора. Так что, пусть постквантовая стойкость и возможна без алгоритма Шора, но само по себе это ничего не гарантирует в плане внедрения криптосистем.

Кстати, что касается алгоритмов ML-KEM/Kyber, то соответствующая сложная задача (LWE) была сформулирована в 2005 году, но исходные вычислительные проблемы на решётках (SVP и др.) – тоже изучались заметно раньше, с начала 80-х годов прошлого века.

Базовые причины массового внедрения именно криптосистем, не стойких к взлому алгоритмом Шора, те же, по которым не было никаких инструментов криптографической защиты в такой важной технологии, как DNS, где криптографии не могло появиться изначально из-за стремления к строгой оптимизации ресурсов и по причине общего “экзотического статуса” алгоритмов.

Во-первых, в конце 70-х и начале 80-х годов прошлого века криптография, как ни крути, являлась даже более эзотерической областью, чем она есть сейчас. Тут, несомненно, важен вопрос регулирования и “криптовойн”. То есть, вот мы разбираем достаточно узкий вопрос: почему придумали, разработали и внедрили именно RSA с FFDH (классический вариант Диффи-Хеллмана, в конечном поле), а не что-то вроде McEliece/Kyber – но предположим, на минуточку, что регулирование в отношении “понижения стойкости” тут сыграло важную роль: в каких-то криптосистемах стойкость снижать проще, чем в других. Естественно, этот процесс напрямую связан с алгоритмическими особенностями криптосистем. В той же ML-KEM контролируемо снизить стойкость, оставаясь на уровне компьютерных систем начала 80-х годов прошлого века, несколько сложнее, чем реализовать то же самое для RSA, которая тут более “гладкая”. Речь, конечно, не идёт о планах грубо сломать криптосистему, выбрав нестойкие параметры – это не сложно сделать и для ML-KEM/Kyber. Под “контролируемым снижением” тут надо понимать такое снижение стойкости, которое выполняется из предположения, что реализация не обваливается совсем, становясь игрушечной. Конечно, это больше похоже на попытку выдать желаемое за действительное. Для процесса запрета стойкой криптографии сохранение стойкости просто не могло рассматриваться в качестве первостепенного критерия. Более того, та же исходная версия McEliece предоставляла лишь что-то около 64-битов стойкости. С другой стороны, как теперь понятно, странное и строгое регулирование внедрению конкретно RSA не помешало, но даже поспособствовало, выделив эту криптосистему при помощи административных и социальных рычагов. В момент резкого роста масштабов практического применения RSA, другие криптосистемы, ещё и не реализованные на практике, тут же оказались заведомо надолго заперты на периферии технологии, в области теоретической криптографии.

Во-вторых, использование “криптографических преобразований” для передачи данных в вычислительной сети 80-х годов не просто выглядело излишним, но и вызвало обоснованные опасения относительно неоптимального расхода драгоценной пропускной способности: тут каждый байт на счету, а предлагается нарастить данные ключами на много килобит. И когда RSA оказалась вне конкуренции, те же эллиптические криптосистемы довольно долго пробирались на уровень практики, опираясь именно на короткие, если сравнивать с RSA, ключи. Короткие ключи очень удобны. В криптосистемах типа ML-KEM – и, тем более, McElice, – ключи очень длинные. Даже если предположить, что вместо ECDSA/ECDH развивалось бы что-то подобное Kyber, то килобитные ключи однозначно бы закрыли путь к внедрению: потому что – какой смысл жертвовать так много байтов? Сейчас этот смысл полностью сводится к желаемой постквантовой стойкости.

Но если бы в качестве массовых криптосистем с 70-х годов прошлого века использовались криптосистемы, стойкие к алгоритму Шора, то этот алгоритм вряд ли стал бы настолько популярным и известным. А ведь сейчас универсальная слава алгоритма Шора является единственным локомотивом, тянущим за собой в массы популярность “квантовых компьютеров”. Сама концепция квантовых вычислений – всё равно развивалась бы, поскольку она не привязана к криптографии. Не отменяет это и интереса к задаче быстрой факторизации, которая тоже важна и без криптографии. Но если не стала бы RSA популярной, если бы использовалась вместо неё стойкая к алгоритму Шора криптосистема, то не сложилось бы и “хайпа” вокруг “квантовых компьютеров”. Получается, тут есть и некоторая “обратная причинность”: постквантовые криптосистемы не внедрили потому, что спустя три десятка лет возник “квантовый хайп”.

Странная история.

Адрес записки: https://dxdt.ru/2025/03/22/15234/