Nail | 16 Sep 11:42 2004
Picon

Re: scusate......

On Wed, Apr 09, 2003 at 12:55:40AM +0200, Marco Marabelli wrote:
> mi riferisco all'ultimo msg postato ... ma nessuno ha da dire qualcosa al
> riguardo?
> (mi riferisco al paper di quei ricercatori indiani che sembra abbiano
> trovato un modo per dedurre se un numero e' primo o no, senza passare per
> tentativi.....)
> Non ne sento parlare da nessuna parte, non e' una bufala (qualcosa si trova
> su Internet), e il fatto che non si sia fatto clamore mi sembra
> _per_lo_meno_ abbastanza singolare.
> Mi e' quasi venuto in mente che ci sia dietro qualche interesse commerciale
> ...
> ma probabilmente e' una stupidata ;oP
> 
> Cosa ne pensate?
> 

Un motivo della poca notorieta' della cosa a mio
parere e' dato dal fatto che il metodo e' si, certo,
ma ha anche solo una complessita' computazionale teorica che lo rende
poco utilizzabile, per ora.

Non l'ho qui sottomano, ma se non ricordo male il test richiede
O(lg^6 n f(lg lg n)) con f(x) polinomiale (per essere rigorosi sarebbe
12 e non 6 ma quasi tutti prendono per buona l'assunzione che serve
per abbassare l'esponente)
Facendo 2 conti, con 1024 bit di numero, si hanno circa 2^60 passi.
Infattibile per un oggetto che deve TAROVARE numeri primi tirandoli a caso.
Questa e' piu' o meno la stessa complessita' del metodo a curve ellittiche,
anch'esso non proprio diffusissimo, con l'unica differenza che non e'
randomizzato.
(Continue reading)

Aurelio Bignoli | 19 Sep 18:49 2004
Picon

Re: scusate......

Nail writes:
 > Non l'ho qui sottomano, ma se non ricordo male il test richiede
 > O(lg^6 n f(lg lg n)) con f(x) polinomiale (per essere rigorosi sarebbe
 > 12 e non 6 ma quasi tutti prendono per buona l'assunzione che serve
 > per abbassare l'esponente)

sull'ultimo numero di "Lettera Matematica PRISTEM", una rivista
pubblicata da Springer-Verlag Italia, c'è un interessante articolo [*]
dedicato ai numeri primi e ai metodi per verificare la primalità, tra
cui AKS. In particolare gli autori dimostrano che:

«la stima asintotica della complessità di AKS è Õ(log^10.5 N) (e
dunque polinomiale di grado al più 11 rispetto alla lunghezza
dell'input).»

Õ coinvolge effettivamente un polinomio di log log N:

«Si afferma invece che il tempo è Õ(log^d N) se è O(log^d N), a meno di
un ulteriore fattore polinomiale nel logaritmo del logaritmo di N (il
che specifica ancora meglio il numero dei passi della sua attuazione,
ma lo mantiene ad un livello polinomiale rispetto al parametro
decisivo, cioè il logaritmo di N).»

[*] Stefano Leonesi, Sonia L'Innocente, Marika Marconi, Carlo
    Toffalori - "Primi e segreti" - Lettera Matematica PRISTEM 52,
    giugno 2004, pp. 10-20
________________________________________________________
http://www.sikurezza.org - Italian Security Mailing List

(Continue reading)

Sala Massimiliano | 20 Sep 10:09 2004
Picon
Picon

Test sui primi

> 
> On Wed, Apr 09, 2003 at 12:55:40AM +0200, Marco Marabelli wrote:
> > mi riferisco all'ultimo msg postato ... ma nessuno ha da dire qualcosa al
> > riguardo?
> > (mi riferisco al paper di quei ricercatori indiani che sembra abbiano
> > trovato un modo per dedurre se un numero e' primo o no, senza passare per
> > tentativi.....)
> > Non ne sento parlare da nessuna parte, non e' una bufala (qualcosa si trova
> > su Internet), e il fatto che non si sia fatto clamore mi sembra
> > _per_lo_meno_ abbastanza singolare.
> > Mi e' quasi venuto in mente che ci sia dietro qualche interesse commerciale
> > ...
> > ma probabilmente e' una stupidata ;oP
> > 
> > Cosa ne pensate?
> > 
> 

Ciao,

il test funziona eccome e la ricerca su come renderlo piu' efficiente e'
attivissima. Per ora pero' ci sono dei metodi probabilistici piu' 
veloci (tipo quelli detti da Nail) e quindi a livello pratico non ha
un grande impatto.
Ma anche se riuscissero a farlo in maniera spaventosamente veloce,
non cambierebbe niente dal punto di vista di RSA.
Capisco che a un non esperto il modo piu' furbo di fattorizzare un
numero possa sembrare di provare un sottinsieme "furbo" di divisori,
ma non e' assolutamente cosi'.
Per cui qualunque succeda sui test per verificare se un numero e' primo o 
(Continue reading)

Cristiano Longo | 21 Sep 09:45 2004
Picon

Re: Test sui primi

Si ma qualcuno sa dove sia reperibile questo papero? Almeno il titolo ...

In data Mon, 20 Sep 2004 10:09:38 +0200 (CEST), Sala Massimiliano 
<sala@...> ha scritto:

>>
>> On Wed, Apr 09, 2003 at 12:55:40AM +0200, Marco Marabelli wrote:
>> > mi riferisco all'ultimo msg postato ... ma nessuno ha da dire qualcosa 
>> al
>> > riguardo?
>> > (mi riferisco al paper di quei ricercatori indiani che sembra abbiano
>> > trovato un modo per dedurre se un numero e' primo o no, senza passare 
>> per
>> > tentativi.....)
>> > Non ne sento parlare da nessuna parte, non e' una bufala (qualcosa si 
>> trova
>> > su Internet), e il fatto che non si sia fatto clamore mi sembra
>> > _per_lo_meno_ abbastanza singolare.
>> > Mi e' quasi venuto in mente che ci sia dietro qualche interesse 
>> commerciale
>> > ...
>> > ma probabilmente e' una stupidata ;oP
>> > > Cosa ne pensate?
>> >
>>
>
> Ciao,
>
> il test funziona eccome e la ricerca su come renderlo piu' efficiente e'
> attivissima. Per ora pero' ci sono dei metodi probabilistici piu' veloci 
(Continue reading)

Sala Massimiliano | 22 Sep 12:10 2004
Picon
Picon

Test sui primi (paper)

> ----------------------------------------------------------------------
> 
> From: Cristiano Longo <cristiano_longo@...>
> Subject: Re: [crypto] Test sui primi

> Si ma qualcuno sa dove sia reperibile questo papero? Almeno il titolo ...

http://www.cse.iitk.ac.in/news/primality.html

ciao

	Max

P.S. so che c'e' gente che sta migliorando parecchio la complessita'
dell'algoritmo, non mi ricordo chi, se vuoi mi informo.
Rimane il fatto che persino un'improbabile complessita' quadratica 
non toccherebbe RSA.

________________________________________________________
http://www.sikurezza.org - Italian Security Mailing List
borzoi | 28 Sep 14:12 2004
Picon

I "mirabilia" del cifrario di Vernam

Buongiorno a tutti,
ho trovato in giro per la Rete gente che vanta mirabilia dei propri
prodotti di encryption basati sul cifrario di Vernam. Per quel poco che
so, il cifrario di Vernam ha il grosso difetto di richiedere lo scambio su
canale sicuro di una chiave di dimensioni comparabili col messaggio. Mi
pare perciò piuttosto improbabile che possa essere utilizzato con profitto
per uno scambio di informazioni via Internet. Voi che ne pensate?
Cordialmente,

Paolo De Nictolis
________________________________________________________
http://www.sikurezza.org - Italian Security Mailing List

william maddler | 28 Sep 17:38 2004
Picon

Re: I "mirabilia" del cifrario di Vernam

beh... dipende dal contesto...
certo potrebbe risultare pressoche` inutilizzabile per gestire delle 
transazioni on line (proprio per il problema della dimensione delle 
chiavi)... la stessa cosa potrebbe invece non essere vera per lo 
scambio di informazioni ad esempio via email... la chiave di cifratura 
potrebbe essere un programma, un'immagine, un file audio... 
probabilmente anche un device (in ambiente linux) come un cd audio... 
cifrare una mail utilizzando Vernam ed un cd audio come chiave (da 
4800Mbit)... beh... potrebbe anche essere niente male in effetti... 

l'unico punto debole della catena e` ovviamente lo scambio 
dell'informazione sulla chiave da usare

imho

On Tuesday 28 September 2004 14:12, borzoi@... wrote:
> Buongiorno a tutti,
> ho trovato in giro per la Rete gente che vanta mirabilia dei propri
> prodotti di encryption basati sul cifrario di Vernam. Per quel poco
> che so, il cifrario di Vernam ha il grosso difetto di richiedere lo
> scambio su canale sicuro di una chiave di dimensioni comparabili col
> messaggio. Mi pare perciò piuttosto improbabile che possa essere
> utilizzato con profitto per uno scambio di informazioni via Internet.
> Voi che ne pensate? Cordialmente,
>
> Paolo De Nictolis
> ________________________________________________________
> http://www.sikurezza.org - Italian Security Mailing List

--

-- 
(Continue reading)

Xarabas | 28 Sep 19:41 2004
Picon

Re: I "mirabilia" del cifrario di Vernam

Anche se si utilizza un sistema a chive pubblica per scambiarsi la chiave
vernam, la sicurezza diminuisce notevolmente; per esempio se due persone si
scambiano la chiave vernam utilizzando l'RSA a 4096bit, una terza persona
non andrebbe a crackare la chiave vernam che magari è di 16000bit, ma
tenterebbe il crack della chiave RSA così da trovare la chiave vernam.
L'utilizzo di questo cifrario può essere proficuo se le persone che lo
utilizzano hanno la possibilità di scambiarsi la chiave in modo sicuro. Un
mio amico ha fatto un ActiveX comprendente anche il vernam che teoricamente
può avere chiavi fino a 3.689.348.814.741.908bit, ma il problema di come
scambiarsi la chiave rimane.

----- Original Message -----
From: <borzoi@...>
To: <crypto@...>
Sent: Tuesday, September 28, 2004 2:12 PM
Subject: [crypto] I "mirabilia" del cifrario di Vernam

> Buongiorno a tutti,
> ho trovato in giro per la Rete gente che vanta mirabilia dei propri
> prodotti di encryption basati sul cifrario di Vernam. Per quel poco che
> so, il cifrario di Vernam ha il grosso difetto di richiedere lo scambio su
> canale sicuro di una chiave di dimensioni comparabili col messaggio. Mi
> pare perciò piuttosto improbabile che possa essere utilizzato con profitto
> per uno scambio di informazioni via Internet. Voi che ne pensate?
> Cordialmente,
>
> Paolo De Nictolis
>
>

(Continue reading)

Alessio Dessi | 28 Sep 23:30 2004
Picon

Re: I "mirabilia" del cifrario di Vernam

non sono aggiornato sugli algoritmi di cifratura caotica .. ma in
teoria se esistesse una funzione veramente caotica ( espressa sotto
forma di formula matematica ) dipendente da alcuni parametri
basterebbe trasmettere solo questi parametri, la funzione che si sta
utilizzando e da quale punto si inziano ad unsare i valori generati da
questa funzione per mascherare i dati inviati sul canale.. così
facendo si potrebbe genereare da ambedue i lati una chiave della
lunghezza desiderata senza doverla trsmettere per intero e senza che
sia necessario sapere quanto questa dovrà essere lunga.

ciao
Alessio

On Tue, 28 Sep 2004 14:12:47 +0200 (CEST), borzoi@...
<borzoi@...> wrote:
> Buongiorno a tutti,
> ho trovato in giro per la Rete gente che vanta mirabilia dei propri
> prodotti di encryption basati sul cifrario di Vernam. Per quel poco che
> so, il cifrario di Vernam ha il grosso difetto di richiedere lo scambio su
> canale sicuro di una chiave di dimensioni comparabili col messaggio. Mi
> pare perciò piuttosto improbabile che possa essere utilizzato con profitto
> per uno scambio di informazioni via Internet. Voi che ne pensate?
> Cordialmente,
> 
> Paolo De Nictolis
> ________________________________________________________
> http://www.sikurezza.org - Italian Security Mailing List
>
________________________________________________________
http://www.sikurezza.org - Italian Security Mailing List
(Continue reading)

Alessio | 29 Sep 13:15 2004
Picon

Re: I "mirabilia" del cifrario di Vernam

On Tue, Sep 28, 2004 at 11:30:43PM +0200, Alessio Dessi wrote:
> non sono aggiornato sugli algoritmi di cifratura caotica .. ma in
> teoria se esistesse una funzione veramente caotica ( espressa sotto
> forma di formula matematica ) dipendente da alcuni parametri
> basterebbe trasmettere solo questi parametri, la funzione che si sta
> utilizzando e da quale punto si inziano ad unsare i valori generati da
> questa funzione per mascherare i dati inviati sul canale.. cos?
> facendo si potrebbe genereare da ambedue i lati una chiave della
> lunghezza desiderata senza doverla trsmettere per intero e senza che
> sia necessario sapere quanto questa dovr? essere lunga.
> 

Questo e' il metodo su cui si basa buiona parte degli Stream Cipher 
usati attualmente: prendo due PRNG estremamente difficili da prevedere (es.
Mersenne Twister) e uso la chiave dell'utente come seme per il PRNG.
Poi magari faccio semplicemente XOR tra il messaggio e l'output del PRNG di
lunghezza pari al messaggio.

L'utilizzo del cifrario di Vernam nella realta' puo' avvvenire a mio parere
solo se chiave e mssaggio viaggiano su due canali differenti come ad esempio
un CD portato da qualcuno e una trasmissione elettronica.
Per quanto sia un oggetto estremamente comodo anche dal lato teorico, questo
tipo di cifrario ha ben poche applicazioni conosciute (ditemi se sbaglio, poi)

Bye,
	Alessio
________________________________________________________
http://www.sikurezza.org - Italian Security Mailing List
(Continue reading)


Gmane