RSA не всё

[beldmit]

Опровержение RSA, кажется, опровергают. В каком-то месте определитель матрицы подсчитан неправильно, и вместо квадрата там должен быть факториал. Из-за этого количество операций соответственно возрастает.

https://crypto.stackexchange.com/questions/88582/does-schnorrs-2021-factoring-method-show-that-the-rsa-cryptosystem-is-not-secur/88601#88601

Comments

[vitus_wagner]

По-моему фигню он там пишет. С какой стати у детерминанта факториальная сложность? Даже банальный метод Гаусса для детерминанта дает O(n³).

[beldmit]

Там не сложность, а оценка.

[elglin]

Это если элементы матрицы имеют длину О(1).
А там что-то есть про перестановки [1, n] -> [1, n], которых как бы n!
Я вот не готов сейчас потратить много времени на то, чтобы въезжать в это совсем точно, но фокус, как мне кажется, в том, что n входит не только в число операций подсчета определителя, а еще и в сложность каждой операции. Как писали в другом комменте, если у тебя O(1) операций над числами длины O(n!), то результирующая сложность-то все равно O(n!)

[vitus_wagner]

Если n входит в сложность, каждой операции алгоритма с полиномиальным числом операций от n, То сложность остается полиномиальной, только к показателю степени единичка прибавляется.

В общем, как-то трудно поверить что Шнорр мог ТАК лажануться. В то что лажанулся комментатор на стэкэксчедже верится больше.

[elglin]

А вот лажанулся же, если говорить про оценку определителя.
det R(n,f) = det diag(N*f(1), N*f(2)... N*f(n), N*lnN) = N^(n+1) * lnN * (f(1)*...*f(n)) = N^(n+1) * lnN * n!
А в статье вместо n! идет n(n+1)/2 , то есть (f(1) + ... + f(n)). Дальше уже вопрос, насколько это ломает итоговую оценку сложности, на stackexchange указывают, что именно там дальше подламывается, но не дают полную цепочку до итоговой оценки сложности.
Но ошибка подсчета определителя налицо. Конец второй страницы препринта.
Ну и уже кто-то проверил: https://github.com/lducas/SchnorrGate и пришел к выводу, что в реальности метод не будет существенно быстрее имеющихся.

[elglin]

Имею философский вопрос. Допустим, опровержение опровергнуто. В зависимости от своей системы верований это можно посчитать как еще один тревожный звоночек (поправил же за год Уайлз свое доказательство теоремы Ферма) или как еще одно доказательство того, что RSA достаточно стреляный воробей.

И вот отсюда вопрос: есть ли практический смысл потихоньку (то есть не аврально, а постепенно с истечением сертификатов и ребилдом инстансов) переводить свою SSL- и SSH-систему ключей (я не назову ее PKI, потому что Infrastructure в ней, увы, нет) на ECDSA?

[beldmit]

Скорее да, потому что
1. Эллиптика вроде бы местами ещё и быстрее и менее ресурсоёмка, не знаю, насколько это актуально.
2. RSA классический сильно неустойчив по отношению к side-channel атакам.

Но это не значит, что про эллиптику тоже ничего не накопается. Ну и это, придут квантовые компьютеры - «мы все умрём».

[filin]

придут квантовые компьютеры - «мы все умрём».

Не все. У них фигня вроде изложенной чуть выше: сложность взлома O(1), шанс правильно прочесть его результат — 2^-N.