Post on 02-May-2015
transcript
Il Paradosso dei compleanni
e … la pirateria informaticaAutori:
BARRETTA DOMENICOCASCARINO ROBERTACICCARELLI SARADI GIROLAMO VINCENZADI MAIOLA ANNA DI NARDO ILARIAGALLARELLO SIMONEGIORDANO VINCENZA GRANATA FEDERICAGRANATA GIUSY
Autori:MAURIELLO TONYAORDINE LEOPOLDO D’ALTERIO CARLOPUGLIESE FRANCESCORUSSO PASQUALESOZIO PIERLUIGITRINCHILLO MARIA GIUSEPPINAProf. MALLARDO ANGELAPIANESE SERAFINA
PREMESSAPARADOSSO:
Dal greco παρά (contro) e δόξα (opinione) ovvero
andare contro l’opinione comune (quella più diffusa)
L’EVENTO ALLA BASE DEL PARADOSSO DEI COMPLEANNI:
«In un insieme G di N persone c’è almeno una coppia
costituita da persone nate
nello stesso giorno e nello stesso mese.»
In tale contesto, non si considera il giorno dell’anno bisestile e si considerano equiprobabili i 365 giorni dell’anno rispetto alla nascita di una persona. Inoltre d’ora in poi consideriamo i giorni dell’anno numerati da 1 (1 Gennaio) fino a 365 (31 Dicembre) in modo da eliminare il riferimento al mese.
Ragioniamo
MA è proprio così ?
Nel paradosso dei compleanni emerge in maniera del tutto spontanea la questione della determinazione del minimo intero N per il quale l’evento considerato risulta avere probabilità maggiore di 1/2.
IDEA INTUITIVA:
l’opinione comune suggerisce che il gruppo debba essere formato da almeno:
183 (>365/2)
persone.
Impostazione assiomatica
•
•
• se gli eventi sono a due a due incompatibili (per )
In particolare
P()= 1 – P()
• la legge del prodottoP(
Impostiamo il problema
Si supponga ora di aver, in qualche modo, ordinato le persone dell’insieme per cui si può parlare della prima persona, della seconda persona e così via. Inoltre, consideriamo i seguenti eventi:
: «la prima persona è nata in un qualsiasi giorno dell’anno»
e, per ,
: «la -ima persona è nata in un giorno diverso dai giorni di nascita delle persone a lei precedenti».
La Probabilità …
In una situazione come quella che stiamo considerando (ricordiamo che abbiamo supposto «equiprobabili» i 365 giorni dell’anno rispetto alla nascita di una persona) si può adottare la definizione classica di probabilità:
per ogni evento
P() =
La legge del prodotto…
Pertanto, passando all’evento negato, la probabilità che ci sia almeno una coppia costituita da persone nate nello stesso giorno vale:
Fornisce immediatamente la probabilità che le persone dell’insieme sono nate tutte in giorni differenti:
Allora…
La tabella seguente riporta i valori di per alcuni valori di
2 0,00274 24 0,53834
10 0,11695 30 0,70362
15 0,25290 40 0,89123
19 0,37912 50 0,97037
20 0,41144 60 0,99412
21 0,44369 70 0,99916
22 0,47570 80 0,99991
23 0,50730 90 0,99999
Conclusione
Basta che l’insieme sia formato da soltanto 23 persone, per avere
maggiore di 1/2
la probabilità di trovare almeno una coppia di persone nate lo stesso giorno.
EsempioDa una indagine dell’espresso Web in un articolo del 19 gennaio 2008 esaminando le 43 date di nascita e 39 di morte di Presidenti americani
Polk e Harding nacquero il: 2 novembre
Carter e Heisenhower nacquero il 14 ottobre;
Truman e Ford morirono il 26 dicembre,
Polk e Buchanan morirono il 15 giugno
tre presidenti, Jefferson, Adams e Monroe, morirono il 4 luglio.
Applicazione alla crittografia
Crittografare un messaggio significa «nascondere» l’informazione utilizzando una «chiave».
Ipotizziamo che:
un certo messaggio sia codificato con stringhe numeriche di 4 elementi.
Per nasconderle si provveda a moltiplicare tutti i numeri della stringa per un intero lungo un byte (8 bit)
ESEMPIOSe la stringa è 4 7 5 6, che nel sistema binario si esprime come:
Essa attraverso un intero K detto chiave viene trasformata in una nuova stringa detta crittogramma.
0 0 0 0 0 1 0 0 4
0 0 0 0 0 1 1 1 7
0 0 0 0 0 1 0 1 5
0 0 0 0 0 1 1 0 6
Per esempio quella che si ottiene moltiplicando tutti i numeri per 8 sarà
0 0 1 0 0 0 0 0 32
0 0 1 1 1 0 0 0 56
0 0 1 0 1 0 0 0 40
0 0 1 1 0 0 0 0 48
0 0 0 0 0 1 0 0 4
0 0 0 0 0 1 1 1 7
0 0 0 0 0 1 0 1 5
0 0 0 0 0 1 1 0 6
x 8(Chiave)
Crittogramma
Problema
Ipotesi:
Se un messaggio contiene due crittogrammi codificati con la stessa chiave esso è decifrabile.
Un hacker (pirata informatico) vuole: assegnato un blocco di crittogrammi trovare due stringhe codificate con la stessa chiave.
Come Applicare il Paradosso?Sapendo che le possibili chiavi che si ottengono
con 1
byte sono:
=256
abbiamo calcolato la probabilità che,
Presi n crittogrammi, tra questi n ce ne siano almeno due generati dalla stessa chiave k.
La probabilità è data dalla formula:
P(n)=
Calcolo della distribuzione di probabilità
Utilizziamo un foglio di calcolo per determinare la funzione che caratterizza questa probabilità
0 10 20 30 40 50 60 70 80 90 1000
0.2
0.4
0.6
0.8
1
1.2
probabilità Attacco
Rappresentazione grafica dei risultati
Conclusione
Con soltanto 20 Crittogrammi ha una probabilità maggiore del 50% di trovare stringhe codificate con la stessa chiave e
dunque vista l’ipotesi fatta decifrare la chiave di accesso.
Con 40 Crittogrammi tale probabilità sarebbe
addirittura maggiore del 90%.
Grazie per l’attenzione
Ringraziamo i professori Aniello Buonocore e Luigia Caputo per aver con
estrema professionalità suscitato il nostro interesse riguardo al calcolo delle probabilità, argomento a noi non noto,
nonché per la collaborazione e la disponibilità mostrata durante la stesura
della presentazione.