RSA сломали?
От: BlackEric http://black-eric.lj.ru
Дата: 03.03.21 19:42
Оценка: 13 (3)
Fast Factoring Integers by SVP Algorithms

Claus Peter Schnorr

Abstract.

To factor an integer N we construct n triples of pn-smooth integers u, v, |u−vN| for the
n-th prime pn. Denote such triple a fac-relation. We get fac-relations from a nearly shortest vector of
the lattice L(Rn,f ) with basis matrix Rn,f ∈ R
(n+1)×(n+1) where f : [1, n] → [1, n] is a permutation
of [1, 2, ..., n] and (Nf(1), ..., Nf(n)) is the diagonal of Rn,f . We get an independent fac-relation
from an independent permutation f
0
. We find sufficiently short lattice vectors by strong primal-dual
reduction of Rn,f . We factor N ≈ 2
400 by n = 47 and N ≈ 2
800 by n = 95. Our accelerated strong
primal-dual reduction of [GN08] factors integers N ≈ 2
400 and N ≈ 2
800 by 4.2 · 109
and 8.4 · 1010
arithmetic operations, much faster then the quadratic sieve QS and the number field sieve NFS
and using much smaller primes pn. This destroys the RSA cryptosystem.


Там 12 страниц математики
https://github.com/BlackEric001
Re: Постоянно ломают.
От: halo Украина  
Дата: 04.03.21 08:54
Оценка: 5 (1)
Здравствуйте, BlackEric, Вы писали:

BE>Fast Factoring Integers by SVP Algorithms


BE>Claus Peter Schnorr


BE>

BE>Abstract.

BE>... This destroys the RSA cryptosystem.


BE>Там 12 страниц математики





https://old.reddit.com/r/programming/comments/lwqi2w/this_destroys_the_rsa_cryptosystem/gpj0cjx/

theoldboy

Well the paper is dated "work in progress 31.10.2019" and the RSA cryptosystem hasn't collapsed yet so I guess not. The paper itself doesn't make that claim btw, I assume it was submitted there by someone who wasn't the author.
Anyway, no-one uses RSA keys as small as 800 bits. 512 bits was broken in 1999 and the current record is 829 bits.
2048 bits has been the recommended minimum for a long time now, and even Windows blocked the use of keys less than 1024 bits, back in 2012.



https://old.reddit.com/r/programming/comments/lwqi2w/this_destroys_the_rsa_cryptosystem/gpipwac/

remind_me_later

HN discussion here
TL;DR: This is likely just a speedup. It's still not known if the solution only works for an unknown subclass of RSA integers, or if it is easily generalizable to all integers.
STL;DR: As long as the RSA key uses 4096 bits or higher, it should be fine.
Side note: It's weird that the examples given are 400 & 800 bit keys.... (Given that the examples shown were 2⁴⁰⁰ & 2⁸⁰⁰)



https://old.reddit.com/r/programming/comments/lwqi2w/this_destroys_the_rsa_cryptosystem/gpiwcqf/

Kered13

Apparently someone took a draft that was published in 2019 and reposted it with the RSA claim, which does not appear in the original paper.
https://www.reddit.com/r/crypto/comments/lwevey/ruffing_from_the_abstract_on_eprint_not_in_the/gphh9sl/



https://en.wikipedia.org/w/index.php?title=RSA_Factoring_Challenge&oldid=978707125

RSA-250 [ * ] 250 829 Feb 28, 2020[11] F. Boudot, P. Gaudry, A. Guillevic, N. Heninger, E. Thomé and P. Zimmermann



https://old.reddit.com/r/crypto/comments/lwevey/ruffing_from_the_abstract_on_eprint_not_in_the/gphh9sl/

bascule

I strongly suspect it's fake.
It's a repost of an outdated 2019 version of this paper: https://www.math.uni-frankfurt.de/~dmst/teaching/WS2019/SVP9.pdf
The original paper is about applying CVP/SVP to factoring. It doesn't mention RSA whatsoever.
The ePrint contains the (as noted in the OP) spelling-mistake accusations of it being able to "destroye" the RSA cryptosystem.
Seems like a prank.

Re: RSA сломали?
От: BlackEric http://black-eric.lj.ru
Дата: 04.03.21 09:09
Оценка: 4 (1)
Здравствуйте, BlackEric, Вы писали:

Кажется, не все.

Does Schnorr's 2021 factoring method show that the RSA cryptosystem is not secure?
https://github.com/BlackEric001
Re: RSA сломали?
От: vsb Казахстан  
Дата: 04.03.21 10:53
Оценка:
Рано или поздно сломают. Давно пора на EC переходить.
Re: Чем дело кончилось?
От: Sharov Россия  
Дата: 05.04.21 19:21
Оценка:
Здравствуйте, BlackEric, Вы писали:

Показалось или таки действительно что-то серьезное нашли и замяли?
Кодом людям нужно помогать!
Re[2]: Чем дело кончилось?
От: mike_rs Россия  
Дата: 06.04.21 09:58
Оценка:
Здравствуйте, Sharov, Вы писали:

S>Здравствуйте, BlackEric, Вы писали:


S>Показалось или таки действительно что-то серьезное нашли и замяли?


чувак заявил что нашел легкий способ факторизации и выкатил кучу формул, на что ему посоветовали решить своим методом любой из открытых челленджей RSA в качестве демонстрации. Дальше тишина. Как считаешь — действительно что-то серьезное нашли ?
Re[3]: Чем дело кончилось?
От: Sharov Россия  
Дата: 06.04.21 10:40
Оценка:
Здравствуйте, mike_rs, Вы писали:

_>чувак заявил что нашел легкий способ факторизации и выкатил кучу формул, на что ему посоветовали решить своим методом любой из открытых челленджей RSA в качестве демонстрации. Дальше тишина. Как считаешь — действительно что-то серьезное нашли ?


Может и нет, а может сказали заткнуться. Хотя в наше время во второе верится сложнее, учитывая, что
вся математика доступна. Так что скорее всего показалось.
Кодом людям нужно помогать!
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.