funzioni unidirezionali

Analisi, algebra lineare, topologia, gruppi, anelli, campi, ...
Rispondi
ndp15
Messaggi: 598
Iscritto il: 18 gen 2007, 19:01

funzioni unidirezionali

Messaggio 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.
Avatar utente
SkZ
Messaggi: 3333
Iscritto il: 03 ago 2006, 21:02
Località: Concepcion, Chile
Contatta:

Messaggio 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
impara il [tex]~\LaTeX[/tex] e mettilo da par[tex]\TeX~[/tex]

Software is like sex: it's better when it's free (Linus T.)
membro: Club Nostalgici
Non essere egoista, dona anche tu! http://fpv.hacknight.org/a8.php
dario2994
Messaggi: 1428
Iscritto il: 10 dic 2008, 21:30

Messaggio 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.
...tristezza ed ottimismo... ed ironia...
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai
fph
Site Admin
Messaggi: 3956
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Messaggio da fph »

Ma avete letto le slides? Perché la definizione del tizio sembra molto più incasinata di così
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
dario2994
Messaggi: 1428
Iscritto il: 10 dic 2008, 21:30

Messaggio 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?
...tristezza ed ottimismo... ed ironia...
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai
Avatar utente
SkZ
Messaggi: 3333
Iscritto il: 03 ago 2006, 21:02
Località: Concepcion, Chile
Contatta:

Messaggio 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
impara il [tex]~\LaTeX[/tex] e mettilo da par[tex]\TeX~[/tex]

Software is like sex: it's better when it's free (Linus T.)
membro: Club Nostalgici
Non essere egoista, dona anche tu! http://fpv.hacknight.org/a8.php
fph
Site Admin
Messaggi: 3956
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Messaggio 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. ;)
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
Avatar utente
SkZ
Messaggi: 3333
Iscritto il: 03 ago 2006, 21:02
Località: Concepcion, Chile
Contatta:

Messaggio 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"
impara il [tex]~\LaTeX[/tex] e mettilo da par[tex]\TeX~[/tex]

Software is like sex: it's better when it's free (Linus T.)
membro: Club Nostalgici
Non essere egoista, dona anche tu! http://fpv.hacknight.org/a8.php
Tibor Gallai
Messaggi: 1776
Iscritto il: 17 nov 2007, 19:12

Messaggio 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...
[quote="Pigkappa"]Penso che faresti un favore al mondo se aprissi un bel topic di bestemmie da qualche parte in modo che ti bannino subito.[/quote]
ndp15
Messaggi: 598
Iscritto il: 18 gen 2007, 19:01

Messaggio da ndp15 »

Grazie a tutti per le risposte!
Cercherò qualcosa di meglio in internet, in inglese magari (giusto Tibor? :) )
Avatar utente
SkZ
Messaggi: 3333
Iscritto il: 03 ago 2006, 21:02
Località: Concepcion, Chile
Contatta:

Messaggio da SkZ »

che stai cercando?
impara il [tex]~\LaTeX[/tex] e mettilo da par[tex]\TeX~[/tex]

Software is like sex: it's better when it's free (Linus T.)
membro: Club Nostalgici
Non essere egoista, dona anche tu! http://fpv.hacknight.org/a8.php
ndp15
Messaggi: 598
Iscritto il: 18 gen 2007, 19:01

Messaggio 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 :roll: )
Avatar utente
Gatto
Messaggi: 487
Iscritto il: 25 nov 2007, 16:36
Località: Roma

Messaggio 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.
"Fu chiaro sin dall'inizio che ogni qual volta c'era un lavoro da fare, il gatto si rendeva irreperibile." (George Orwell - La fattoria degli animali)
Avatar utente
SkZ
Messaggi: 3333
Iscritto il: 03 ago 2006, 21:02
Località: Concepcion, Chile
Contatta:

Messaggio 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
impara il [tex]~\LaTeX[/tex] e mettilo da par[tex]\TeX~[/tex]

Software is like sex: it's better when it's free (Linus T.)
membro: Club Nostalgici
Non essere egoista, dona anche tu! http://fpv.hacknight.org/a8.php
Rispondi