RSA не всё
Mar. 4th, 2021 09:47 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
beldmitОпровержение RSA, кажется, опровергают. В каком-то месте определитель матрицы подсчитан неправильно, и вместо квадрата там должен быть факториал. Из-за этого количество операций соответственно возрастает.
https://crypto.stackexchange.com/questions/88582/does-schnorrs-2021-factoring-method-show-that-the-rsa-cryptosystem-is-not-secur/88601#88601
https://crypto.stackexchange.com/questions/88582/does-schnorrs-2021-factoring-method-show-that-the-rsa-cryptosystem-is-not-secur/88601#88601
no subject
Date: 2021-03-04 08:56 am (UTC)По-моему фигню он там пишет. С какой стати у детерминанта факториальная сложность? Даже банальный метод Гаусса для детерминанта дает O(n3).
no subject
Date: 2021-03-04 09:16 am (UTC)no subject
Date: 2021-03-04 09:22 am (UTC)А там что-то есть про перестановки [1, n] -> [1, n], которых как бы n!
Я вот не готов сейчас потратить много времени на то, чтобы въезжать в это совсем точно, но фокус, как мне кажется, в том, что n входит не только в число операций подсчета определителя, а еще и в сложность каждой операции. Как писали в другом комменте, если у тебя O(1) операций над числами длины O(n!), то результирующая сложность-то все равно O(n!)
no subject
Date: 2021-03-04 09:32 am (UTC)Если n входит в сложность, каждой операции алгоритма с полиномиальным числом операций от n, То сложность остается полиномиальной, только к показателю степени единичка прибавляется.
В общем, как-то трудно поверить что Шнорр мог ТАК лажануться. В то что лажанулся комментатор на стэкэксчедже верится больше.
no subject
Date: 2021-03-04 10:28 am (UTC)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 и пришел к выводу, что в реальности метод не будет существенно быстрее имеющихся.
no subject
Date: 2021-03-04 09:27 am (UTC)И вот отсюда вопрос: есть ли практический смысл потихоньку (то есть не аврально, а постепенно с истечением сертификатов и ребилдом инстансов) переводить свою SSL- и SSH-систему ключей (я не назову ее PKI, потому что Infrastructure в ней, увы, нет) на ECDSA?
no subject
Date: 2021-03-04 09:35 am (UTC)1. Эллиптика вроде бы местами ещё и быстрее и менее ресурсоёмка, не знаю, насколько это актуально.
2. RSA классический сильно неустойчив по отношению к side-channel атакам.
Но это не значит, что про эллиптику тоже ничего не накопается. Ну и это, придут квантовые компьютеры - «мы все умрём».
no subject
Date: 2021-03-04 10:14 am (UTC)Не все. У них фигня вроде изложенной чуть выше: сложность взлома O(1), шанс правильно прочесть его результат — 2^-N.