Crypto Paper: RSA destroyes vis Schnorr

[grarpamp]

https://eprint.iacr.org/2021/232
Cryptology ePrint Archive: Report 2021/232

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′. We find sufficiently short lattice vectors
by strong primal-dual reduction of Rn,f. We factor N≈2400 by n = 47
and N≈2800 by n = 95. Our accelerated strong primal-dual reduction of
[Gama, Nguyen 2008] factors integers N≈2400 and N≈2800 by 4.2⋅109 and
8.4⋅1010 arithmetic operations, much faster then the quadratic sieve
{\bf QS} and the number field sieve {\bf NFS} and using much smaller
primes pn. This destroyes the RSA cryptosystem.

Category / Keywords: secret-key cryptography / Primal-dual reduction,
SVP, fac-relation

Date: received 1 Mar 2021

Contact author: schnorr at cs uni-frankfurt de