В чудное время живем

[mdmx]

Че там пишут, что и без квантов RSA поломали? https://crypto.stackexchange.com/questions/88582/does-schnorrs-2021-factoring-method-show-that-the-rsa-cryptosystem-is-not-secur

Набрёл у https://vitus-wagner.dreamwidth.org/2236410.html

Comments

[juan_gandhi]

Есть и возражения.

[mdmx]

ну это понятно, но уже пора готовиться - квантовый компьютер уже не за горами

[catodon]

Да хрен знает. Кое-какие наработки (и вроде даже рабочие прототипы) есть уже сегодня, но там не те технологии, которые можно репродуцировать массово. А ломать шифры, имея в наличии ресурсы государства, можно уже и сейчас, социально-административными, а не математическими методами.

[catodon]

Даже если автор написал "This destroys the RSA cryptosystem", это еще надо доказать. Я вижу выкладки для нового алгоритма, но не вижу доказательства, что он работает за полиномиальное время. И не вижу эмпирики. Если он действительно нашел метод факторизации с полиномиальным ростом стоимости, то это будет доказательством фундаментального принципа P=NP и будет революцией в теории вычисления. Если же он нашел немного более быстрый метод, но рост стоимости все еще неполиномиален. Для борьбы с этим достаточно будет просто слегка удлинить ключи.

Шнорр - известный исследователь и он прдтвердил, что статья действительно его, а не фейк. Но и серьёзным исследователям свойственно иногда ошибаться. Я не могу разобрать его статью по кирпичикам, и проверить их: я для этого слишком мало знаю в этой области. Будем ждать рецензий других специалистов и эмпирических тестов. И доказательства полиномиальной стоимости.

Присоедимяюсь к этому:
Several people smarter than me are trying to reproduce Schnorr’s results and check his work, and have already raised issues which I’ll append here.

[mdmx]

ну даже если и это просто наброс то все равно он вышел довольно знатный - повод всем призадуматься.

[catodon]

Там пишут, что это попытка доработки попытки двухлетней давности, которая не очень-то и работала. Короче говоря, это еще просто предварительный тезис, который не подтвержден ни формальным доказательством ни эмпирикой. Написать в работе такого уровня (то есть описывающей предварительные непроверенные результаты) фразу "This destroys the RSA cryptosystem" - действительно просто наброс на вентилятор. Задумываться простым юзерам пока не над чем.