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

--===============0473046223==
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: quoted-printable

Ho dato un'occhiata al paper che hanno rilasciato recentemente su IACR:=20
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=C3=A0 che possono aiutare
> nella sua fattorizzazione.=20

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

Per=C3=B2, s=C3=AC, c'=C3=A8 una bella differenza tra il caso particolare=
 trattato e il=20
caso generale:

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

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

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


> Inoltre, ci hanno messo
> 9 anni impiegando una quantit=C3=A0 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=3D441:
"The 11-month job took a century of computer time."

O anche:

"On March 6, computer clusters from three institutions --=E2=82=AC=E2=80=9C=
 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=20
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=20
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=20
magnitude larger than ours."

Approposito, qualcuno sa, per caso, che tipo di risorse sarebbero invece=20
sufficienti per perseguire un simile fine? (niente algoritmo di Shor e=20
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=C3=A0 pu=C3=B2 voler dire =
parecchio
> pi=C3=B9 tempo per un numero normale, senza le propriet=C3=A0 dei numer=
i di
> Mersenne o altre cose particolari.


S=C3=AC, qui hai ragione (ma non ci sono voluti 9 anni):

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

Per=C3=B2 (per=C3=B2, per=C3=B2): " Nevertheless, the aspects of our effo=
rt 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=20
of NFS-based
factorizations such as those of RSA moduli. This need for re-assessment=20
is the main reason
that we feel that our result should be reported in the cryptologic=20
literature."

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

> Come ultima nota, =C3=A8 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=C3=A0 della por=
tata
> di quasi chiunque...
>

Direi di s=C3=AC. Tra l'altro, notavo guardando:=20
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=20
fatto che: "by the
time we manage to factor a 768-bit RSA modulus=E2=80=94something we are c=
onvinced we
are able to pull off=E2=80=94the relative effort of factoring a 1024-bit =
RSA=20
modulus will look
at least 5 times easier than the relative effort of factoring a 768-bit=20
RSA modulus
compared to a 512-bit one". Tenendo conto che: "the first published=20
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=20
alla fattorizzazione di quel numero
(compresa la motivazione relativa alla sua scelta).



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


--===============0473046223==
Content-Type: text/plain; charset="iso-8859-1"
MIME-Version: 1.0
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline

________________________________________________________
http://www.sikurezza.org - Italian Security Mailing List
--===============0473046223==--