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

Il 04/06/07, Giulia Biagini<giulia@xxxxxxxxxxxxx> ha scritto:
> Ho dato un'occhiata al paper che hanno rilasciato recentemente su IACR:
> http://eprint.iacr.org/2007/205

Carino. Me lo devo spulciare per bene, ma carino :)
> > 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."
Vorrei anche vedere. La crittografia RSA è considerata sicura proprio
perchè ci vuole tempo, troppo tempo per forzarla. Se va bene,
naturalmente :)

> > 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."
Beh, chiaro, devi valutare 1/2^22 valori in meno. Come ho detto cambia
poco, ma cambia. Si riduce la scala. Rimane sempre un valore assurdo,
ma considerando che valutare 2^n invece che 2^(n+1) valori vuol dire
valutarne la metà, anche un piccolo aiuto fa comodo...

> > 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."

> 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)."//
Colpa mia. Ho confuso. Chiedo venia :)

> 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".
Uhm... per 2^1024 valori, senza alcuna informazione sul numero, e
usando solo ed esclusivamente la forza bruta... Parecchi. Se vuoi ti
facico il conto, ma con la forza bruta ti ci vuole un tempo sovrumano,
per fattorizzare una chiave a 1024 bit. Usando algoritmi e trucchetti
vari puoi scendere a qualche anno... Con un calcolo distribuito...
Forse meno, ma non ci credo molto. Mi sono appena fatto un paio di
conti, e con la forza bruta ci vuole più tempo di quanto ne ha a
disposizione il sole prima di spegnersi... forse ho sbagliato un paio
di ordini di grandezza, ma sono raigonevolmente sicuro... :)


> > 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."
Non è un ragionamento scorretto, ma è pur vero che su un numero
"normale" non puoi usare i trucchetti che usi sui numeri di Mersenne o
altri numeri particolari... Quindi, io direi che dalla metà ai 3/4 del
lavoro fatto da sti tipi (onore al merito, per carità) non si può
applicare alla fattorizzazione di una chiave rsa... forse qualcosa
meno della metà, ma non ci conto... per inciso, devo ancora legger eil
paper, sto andando molto ad ochcio :)


> 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".//
Ok stay tuned, ma senza farne un dramma. Per parte mia non penso che
con gli attuali mezzi la crittografia a 1024 bit sia esattamente
insicura...

> > 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."
Ottimistica come previsione. Stiamo parlando di una stratosfera di
valori in più. Chiaro che non ci vai di forza bruta, o almeno non
solo, ma spingersi a dire che lo sforzo per fattorizzare una chiave a
1024 bit sarà 5 volte più leggero rispetto all'attuale fattorizzazione
di un valore a 768 bit, mi pare un poco pretenzioso. Se stanno
sviluppando nuovi algoritmi, o migliorando quelli esistenti, ne
possiamo parlare... fermo restando il fatto che 2^n/5 rimane sempre
tanta roba :)

--
---
Blackstorm
*Con due angeli ed un'amica al seguito*

Datemene uno con un browser testuale, un eroe fuori dal cinema alle tre di
notte. Datemelo che ti accompagni sempre a casa, anche se piove, anche se fa
freddo, anche se un passo più in là finisce il mondo. Datemelo che scriva
lettere belle non a me, e se poi le leggo va be', mica è colpa mia.{Angelus}

God saves. (And take only half damage.)

[ICQ #116647346]