Pagina 1 di 1
funzioni unidirezionali
Inviato: 04 giu 2010, 19:17
da ndp15
Sposto in MNE, non essendo argomenti di utilità olimpica -- HP
Nel seguente
corso a pagina 7 viene data la definizione di funzione unidirezionale. Considerando che state parlando con un ragazzo di 5°, sapreste spiegarmi in maniera il più comprensibile possibile tale definizione?
Ovviamente a livello intuitivo i concetti contenuti nella slide precedente li ho chiari, vorrei riuscire a tradurre in parole ciò che è scritto in linguaggio matematico nella definizione.
Inviato: 04 giu 2010, 20:35
da SkZ
mi pare di capire che una funzione (non inettiva) e' unidirezionale se e' difficile/impossibile trovare un algoritmo che e' capace di trovare una collisione (ovvero un input con lo stesso output della funzione ma non necessariamente l'input iniziale) in tempi "umani" o utili.
fai conto delle password che vengono conservate tramite checksum: quando inserisci la password viene operato il checksum su di essa e confrontato con quello memorizzato.
il checksum e' unidirezionale se la probabilita' che, partendo dal dato memorizzato e usando un qualunque algoritmo, si ottenga un input che ti permetta di effettuare il login e' infnitesimale rispetto all'inverso di una potenza del numero di caratteri usati per l'input
Inviato: 04 giu 2010, 21:24
da dario2994
Uhm... un poco più semplice:
Una funzione $ $f $ è unidirezionale se:
dato $ $x $ esiste un algoritmo che ti sputa fuori $ $f(x) $ in tempo polinomiale
Non esiste una algoritmo polinomiale (wiki dice probabilistacamente polinomiale ma non so cosa vuol dire) che dato $ $a $ riesca $ $a $ sputare fuori $ $b $ tale che $ $f(b)=a $ (o almeno non riesce a farlo se non in rarissimi casi)
Insomma a parole vuol dire: dato x è facile trovare f(x) ma dato f(x) è difficile trovare x.
Insomma serve a crittare la roba. Ho una password e la critto con una funzione unidirezionale... ci riesco in breve tempo. Ora la password crittata posso darla a chiunque ma questo chiunque non riuscirà a risalire alla mia password se non in tempi enormi.
Inviato: 04 giu 2010, 21:31
da fph
Ma avete letto le slides? Perché la definizione del tizio sembra molto più incasinata di così
Inviato: 04 giu 2010, 21:35
da dario2994
Io le slides le ho lette, non c'ho capito nulla mi è parso che facessero anche cagare come dispense quindi ho usato l'enorme sapere (a volte corrotto) fornito da wiki.
Comunque nelle slides nella definizione usa un PR[]<=... ma PR che vuol dire?
Inviato: 04 giu 2010, 23:05
da SkZ
Pr sta per probabilita'.
la probabilita' di trovare una collisione e' minore dell'inverso della potenza intera del numero di caratteri binari usati
Inviato: 04 giu 2010, 23:07
da fph
Comunque nelle slides nella definizione usa un PR[]<=... ma PR che vuol dire?
Credo che voglia dire "probabilità". Ci ho messo un po' a fare il parsing di quella riga piena di roba non definita, ma credo che l'idea sia:
-ti viene dato y=f(x), dove f è una funzione
-tu vuoi costruire un algoritmo A che dato y calcoli una controimmagine di y secondo f a tua scelta, z (non per forza z=x)
-questo algoritmo non deve funzionare sempre, ma basta che abbia una certa probabilità p di indovinare (p è una mia notazione, lui non gli dà un nome)
-ora, fai variare tutti questi oggetti in funzione della dimensione dell'input k; in soldoni, vuoi che per ogni possibile scelta di A_k "famiglia di algoritmi", la probabilità p_k di indovinare va a zero esponenzialmente o quasi (perlomeno "battendo" tutti i polinomi). Se questo succede, chiami f (o meglio la famiglia f_k) una funzione one-way.
Considerato che sto parlando con un ragazzo di quinta e che quindi non deve sostenere un esame con il professore in questione, direi che potresti guardarti intorno e cercare qualche altra dispensa.
Inviato: 04 giu 2010, 23:34
da SkZ
allora una funzione e' "trascurabile" se
$ $\forall M>0\; \exists x_M\; : \;f(x)\leq x^{-M}\; \forall x>x_M $, ovvero se per ogni M positivo f(x) e' definitivamente minore di $ $ x^{-M} $
una funzione e' unidirezionale se la probabilita' di trovare una sua collisione e' "trascurabile"
Inviato: 05 giu 2010, 14:57
da Tibor Gallai
"Quadrati residui"... Per me quelle slide le ha fatte uno che ha assorbito la teoria dei numeri per vie un po' traverse...
Inviato: 05 giu 2010, 18:32
da ndp15
Grazie a tutti per le risposte!
Cercherò qualcosa di meglio in internet, in inglese magari (giusto Tibor?
)
Inviato: 05 giu 2010, 19:12
da SkZ
che stai cercando?
Inviato: 06 giu 2010, 11:22
da ndp15
SkZ ha scritto:che stai cercando?
fph ha scritto: direi che potresti guardarti intorno e cercare qualche altra dispensa.
La questione di fondo è che sto facendo la tesina sulla crittografia, e citando le funzioni unidirezionali mi sembrava fosse necessario mettere una definizione rigorosa, capendola magari. Chiaramente nell'esposizione orale dirò solo che:" Data x è facile calcolare f(x), data f(x) è difficile calcolare x" (e forse è già troppo tecnica come definizione
)
Inviato: 06 giu 2010, 11:35
da Gatto
ndp15 ha scritto:
La questione di fondo è che sto facendo la tesina sulla crittografia, e citando le funzioni unidirezionali mi sembrava fosse necessario mettere una definizione rigorosa
Probabilmente non ti capirebbe nemmeno la prof di matematica, figuriamoci gli altri... penso sia meglio se ti limiti a dare un'idea come hai detto per non perdere l'interesse della commissione.
Inviato: 07 giu 2010, 04:22
da SkZ
viewtopic.php?t=12770
vai sul semplice
il libro nella discussione che linko penso sia buono per quello che ti serve
e ci fai pure collegamenti con storia e altro