Re: [crypto] Re: fattorizzato un numero di 1039 bit (Lapo Luchini)

Ho dato un'occhiata al paper che hanno rilasciato recentemente su IACR: 
http://eprint.iacr.org/2007/205

> Uhm... bene, ho dato un'occhiata ai numeri di Mersenne, giusto per nn
> dire baggianate, cmq, hanno svariate proprietà che possono aiutare
> nella sua fattorizzazione. 

Beh, effettivamente si chiama SpecialNFS non a caso (vedi anche dopo)!

Però, sì, c'è una bella differenza tra il caso particolare trattato e il 
caso generale:

"It must be stressed [...] that our work does not imply that 1024-bit 
RSA moduli can now be
factored by a comparable effort."

> Tuttavia non riesco a capire bene perchè ci
> si debba preoccupare tropppo... voglio dire, intanto il numero da
> fattorizzare era in realtà dell'oridne di 2^1017 (per via del fattore
> già noto - ok, fa poca differenza, ma la fa).
In realtà, non credo sia molto corretto quanto che stai affermando:

"The factor 5080711 was already known, so we obtained the new 
factorization of the composite
1017-bit number (2^1039 −1)/5080711. The SNFS, however, cannot take 
advantage of
the factor 5080711. Therefore, the difficulty of our SNFS factoring 
effort is equivalent
to the difficulty of the effort that would be required for a 1039-bit 
number that is very
close to a power of two. This makes our factorization the first SNFS 
factorization
that reaches the 1024-bit milestone."


> Inoltre, ci hanno messo
> 9 anni impiegando una quantità di risorse assolutamente non
> convenzionale... non tutti i crittoanalisti hanno a disposizione i
> cluster di tre diversi istituti a disposizione per lavorare in
> parallelo.

9 anni? Io leggo da http://actualites.epfl.ch/presseinfo-com?id=441:
"The 11-month job took a century of computer time."

O anche:

"On March 6, computer clusters from three institutions --€“ the EPFL,
the University of Bonn and NTT in Japan -- reached the end of eleven
months of strenuous calculation, churning out the prime factors of a
well-known, hard-to-factor number that is a whopping 307 digits long."

(http://blog.wired.com/wiredscience/2007/05/mighty_mathemat.html)

I 9 anni li ho visti saltare fuori solo qui (parla Lenstra):
"Last time, it took nine years for us to generalize from a special to a 
non-special hard-to factor number (155 digits)."//

In ogni caso, giusto per puntualizzare il caso di RSA 1024:

"[...] according to all information available to us, and as far as we 
know to
anyone else in the open community, factoring a 1024-bit RSA modulus is
still beyond the capabilities of anyone with resources a few orders of 
magnitude larger than ours."

Approposito, qualcuno sa, per caso, che tipo di risorse sarebbero invece 
sufficienti per perseguire un simile fine? (niente algoritmo di Shor e 
computer quantistici: non vale!)
Mi piacerebbe capire cosa intendono con "A Few orders".


> Come altro argomento, nove anni per fattorizzare un numero
> cmq sia "speciale", ossia con certe prorpietà può voler dire parecchio
> più tempo per un numero normale, senza le proprietà dei numeri di
> Mersenne o altre cose particolari.


Sì, qui hai ragione (ma non ci sono voluti 9 anni):

"Factoring an RSA modulus of comparable size would be several orders of 
magni-
tude harder. Even factoring a 768-bit RSA modulus would be substantially 
harder
than a 1024-bit ‘special’ one. Simply put, this is because RSA moduli 
require usage
of the general number field sieve algorithm (NFS), which runs much 
slower than the
SNFS on numbers of comparable size."

Però (però, però): " Nevertheless, the aspects of our effort where
we made most progress apply equally well to NFS as they apply to SNFS.
They will therefore also have an effect on the assessment of feasibility 
of NFS-based
factorizations such as those of RSA moduli. This need for re-assessment 
is the main reason
that we feel that our result should be reported in the cryptologic 
literature."

Da cui, forse, la constatazione di Lenstra: "I won't make predictions, 
but let's just say it might be a good idea to stay tuned".//

> Come ultima nota, è piuttosto
> facile, attualmente, almeno che io sappia, produrre una crittografia
> rsa a 2048 bit invece che 1024... il che vuol dire che, a meno che non
> venga trovato un algoritmo efficiente, il tempo e le risorse da
> impiegare in un simile calcolo sono decisamente al di là della portata
> di quasi chiunque...

Direi di sì. Tra l'altro, notavo guardando: 
http://www.openssl.org/docs/HOWTO/keys.txt

"The number 2048 is the size of the key, in bits. Today, 2048 or
higher is recommended for RSA keys, as fewer amount of bits is
consider insecure or to be insecure pretty soon."

Anche se, riprendendo Lenstra, ci teniamo ben lontani:

"We estimate that the effort we spent would
suffice to factor a 700-bit RSA modulus."

Nella parte finale viene fornita una prova euristica a sostegno del 
fatto che: "by the
time we manage to factor a 768-bit RSA modulus—something we are convinced we
are able to pull off—the relative effort of factoring a 1024-bit RSA 
modulus will look
at least 5 times easier than the relative effort of factoring a 768-bit 
RSA modulus
compared to a 512-bit one". Tenendo conto che: "the first published 
factorization
of a 512-bit RSA modulus is less than a decade ago."

Il paper, in ogni caso, sintetizza bene le varie fasi che hanno portato 
alla fattorizzazione di quel numero
(compresa la motivazione relativa alla sua scelta).



--
Nietzsche said that people killed God. Well? I'm still alive.