IDUL 2009
COMPRESSIONE E CRIPTAZIONE
Compressione




Concetto di compressione
Compressione con e senza perdite
Esempi
Principali programmi e formati in uso
Compressione di dati
Comprimere dei dati significa ricodificarli in un modo che
permetta di occupare un numero minore di byte rispetto alla
codifica originale, preservando (interamente o parzialmente) il
contenuto.
 Metodo generale: eliminare l’informazione ridondante—quella
che può essere ricostruita a partire da altre informazioni
presenti nel documento stesso
La ricostruzione deve essere:




Effettuabile in maniera puramente meccanica
senza bisogno di alcuna conoscenza specifica sul tipo di dato
che è stato compresso
Idealmente, la codifica e specialmente la decodifica devono
essere computazionalmente leggere (per tempo e memoria)
Compressione di dati: metodi
generali



Immagini: zone di colore uniforme possono essere
codificate insieme, regolarità geometriche catturate da
formule, immagini in movimento possono essere
rappresentate specificando solo ciò che cambia sulla
scena.
Musica: non tutti i suoni sono ugualmente percepibili
all’orecchio umano. L’ MP3 comprime danneggiando i
suoni meno percepibili.
Testi: I caratteri di un testo in una lingua umana sono
disposti in maniera NON casuale.
Esistono molte regolarità nella successione delle lettere
di una lingua, che permettono di omettere determinate
informazioni e ricostruirle integralmente.
Compressione con e senza perdite



Se il processo di decompressione porta a dati che
sono identici a quelli che sono stati compressi in
origine, si dice che la compressione è senza
perdite (”lossless”): (i dati prima della
compressione sono identici a quelli che sono stati
compressi e poi decompressi.)
Se invece il risultato della decompressione è un
file simile ma non identico a quello originale, si
parla di compressione con perdite (“lossy”)
Esempi di compressione lossy sono i formati MP3,
JPEG, MPEG, divx, ogg vorbis, ecc.
GIF VS. JPEG
GIF (75279 bytes)
JPEG (15975 bytes)
JPEG: PIU’ / MENO COMPRESSO
Rappresentare colori intermedi
Tecnica del “dithering”: alternare pixel di colori diversi
per ottenere un colore intermedio.
http//www.siriusweb.com/tutorials/gifvsjpg/
SUONO ORIGINALE / MP3

CD:





Musica campionata 44100 volte al secondo
16 bit per campione
Campioni per sinistra e destra (stereo)
Totale: 1 411 200 bits x secondo
= 32 MB per una canzone di 3 minuti
MP3

Sfrutta conoscenza dei limiti dell’udito
umano per ridurre la quantità di informazione
da immagazzinare:



Escludi suoni che l’orecchio non puo’ udire
Quando c’è un suono particolarmente rumoroso,
non registrare gli altri suoni
Fattore di riduzione: anche 10 volte (= 3MB
per canzone “media”)
Compressione senza perdite



Viste le caratteristiche del linguaggio umano, per i testi,
come per i programmi, si usano solo metodi di
compressione ”lossless” (in cui cioè, decomprimendo, si
ottiene un testo identico a quello da cui si era partiti).
Infatti, perdere un solo byte in un programma
comprometterebbe in modo irreparabile il suo
funzionamento, così come perdere un ”non” in una
asserzione ne invertirebbe il significato.
Si ottiene così un rapporto di compressione medio
attorno al 40% (variabile, a seconda del grado di
ridondanza dei testi ed all’algoritmo usato).
Esempio: Codifica di Huffman


Un modo per comprimere senza perdite un
insieme di dati è codificarli in modo tale che i
tipi di dati più frequenti siano codificati con
meno bit.
Il messaggio è accompagnato da una tabella
di codifica (che varierà da testo a testo)
Algoritmo di Huffman

Supponiamo di ordinare le lettere minuscole dell’ italiano in base alla
frequenza con cui appaiono. In ordine di frequenza decrescente,
otterremo ad esempio la serie:
<spazio> e a o i n r t l c s u d p m , h v g b . f ‘ ’ z q ” ?

Se potessimo usare meno bit per rappresentare le lettere sulla
sinistra che quelle sulla destra avremmo un modo per rappresentare
in modo più compatto il testo. Esempio:
1. <spazio> = 0 (1 bit)
5. i = 11110 (5 bit)
2. e = 10 (2 bit)
…
3. a = 110 (3 bit)
…
4. o = 1110 (4 bit)
? = 1111111111111111111111111111
Osservazioni:



La compressione funziona solo perché la
probabilità di lettere diverse è molto diversa
(vocali vs. consonanti vs. segni di interpunzione)
Prima di codificare il messaggio l’algoritmo deve
analizzarlo interamente e costruire una tabella di
codifica basata sulla frequenza.
Algoritmi più raffinati sostituiscono alla
frequenza assoluta la probabilità basata sul
contesto (p.es. “u” dopo “q” è più probabile)
Esempio 2: informazione messa a
fattore
“A A A A A A A A A A A A A A A A A A A A A A A A A A A A
AAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAA
A A A A A A A A A A A” (600 byte)
= “300 volte ‘A ’ ” (13 byte)
Metodo usato p.es. nelle immagini per aree di colore uniforme.
Compressibilità ed entropia



Tutti i sistemi di compressione sfruttano una ridondanza
nella informazione. Un testo formato da sequenze
puramente casuale di caratteri non può essere
compresso.
Più un testo contiene sequenze simili, più è suscettibile
ad essere compresso.
Questa idea è stata sfruttata al contrario per misurare la
“distanza” tra testi diversi.
Porzioni di DNA
 Testi in lingue diverse (tipologia linguistica)
 Testi di autore sconosciuto (stilometria, ecc.)
Si veda: Baronchelli, Caglioti, Lorento 2006

TEORIA DELL’INFORMAZIONE
Dobbiamo a Claude
Shannon e Warren Weaver
la prima definizione teorica
rigorosa del concetto di
comunicazione ed il primo
schema astratto di tutti i
processi comunicativi,
elaborati alla fine degli anni
‘40
LA COMUNICAZIONE SECONDO
SHANNON & WEAVER
La comunicazione è il trasferimento di informazioni
mediante segnali da una fonte a un destinatario

Lo schema della comunicazione di Shannon e
Weaver è un modello astratto della
comunicazione. Esso ha l’obiettivo di individuare la
forma generale di ogni processo comunicativo e i
fattori fondamentali che lo costituiscono, quegli
elementi, cioè, che devono essere presenti ogni
qual volta si verifichi un passaggio di informazione
IL MODELLO
‘NOISY CHANNEL’
TEMI CENTRALI DELLA TEORIA
DELL’INFORMAZIONE




Entropia come misura della quantità di incertezza
o informazione presente in un segnale casuale.
Informazione come SCELTA tra ALTERNATIVE
Un MESSAGGIO viene usato per comunicare
quale tra queste alternative e’ vera / interessa.
Come e’ possibile sviluppare il codice più
efficiente (= che richiede il minor numero di bit)
per trasmettere questa informazione?
MINIMO NUMERO DI BIT
RICHIESTI PER CODICE





Con 2 bit si codificano 4 distinzioni (22)
Con 3 bit si codificano 8 distinzioni (23)
…
Con N bit si possono codificare 2N distinzioni
differenti
In generale, se devo rappresentare N
distinzioni, devo usare almeno log2 N bit
NUMERO DI BIT NECESSARI PER
RAPPRESENTARE INFORMAZIONE


Se il problema è quello di dover rappresentare M
informazioni differenti si deve selezionare il numero
di N bit in modo tale che
2N >= M
Esempio: per rappresentare 40 informazioni
differenti devo utilizzare 6 bit perché
26 = 64

5 bit non sono sufficienti perché 25 = 32
Programmi di compressione


Gran varietà di programmi di (de)compressione,
parzialmente incompatibili tra loro. Trattandosi di
programmi che funzionano su qualsiasi tipo di dato,
adottano sempre compressione senza perdite.
Il più noto, ma non il più efficiente, è probabilmente
WinZip (shareware). Crea file con suffizzo .zip Effettua
sia (de)compressione che (de)archiviazione (il processo
di raccolta di un insieme di cartelle, sotto cartelle e file in
esse contenuti in un unico file, che può poi venire
compresso e trasmesso facilmente e poi riaperto
ricostruendo la struttura originale)
Programmi di compressione
Si stanno diffondendo numerosi programmi basati su algoritmi
alternativi, più rapidi o con un migliore rapporto di compressione
rispetto al formato “zip”. Da citare:




Formato bzip2 (variante migliorata del formato gzip, crea file con
suffisso .bz2)
WinRAR (programma commerciale), basato su formato di
compressione RAR, crea file con suffisso .rar
7-zip (programma open source, scaricabile gratuitamente da
http://sourceforge.net/projects/sevenzip/), basato sul formato 7z
(grado di compressione dichiarata: dal 30 al 70% migliore del
formato zip). Crea file con suffisso .7z
Formati PAQ: ottengono eccellente compressione senza perdite, al
costo di tempi di compressione molto lenti e grande uso di memoria.
Programmi di compressione
(2)



Con alcuni programmi è possibile creare file compressi
“autoscompattanti ’; si tratta di file .exe che una volta
attivati si decomprimono automaticamente.
Altri formati (ad esempio .msi “Microsoft Installer”)
fanno partire il programma di installazione che
decomprime il contenuto del file (in questo caso, un
programma) e lo installa.
Un limite pratico di tali formati è che, trattandosi di
programmi eseguibili, sono un buon veicolo per la
diffusione di virus.
Criptazione


Al contrario che nel mondo degli oggetti fisici, in cui il
modo di preservare la proprietà di un oggetto è
principalmente quello di impedire l’ appropriazione
indebita da parte di terzi, nel mondo delle informazioni
trasmesse a distanza la possibilità di criptare dati
trasmessi in modo che non siano comprensibili a terzi
stà diventando il sistema prevalente di difesa delle
informazioni.
Notate che mentre un file si può comprimere una sola
volta (dati già compressi non possono essere compressi
ulteriormente), si può criptare più di una volta (proprio
come un testo può essere tradotto da una lingua ad
un’altra e da qui ad una terza, ecc. mentre non si può
riassumere all’ infinito).
Un esempio di criptazione
‘minima’:
Slq rleet ilq hfrrps ip stabzf dpbf
rp zpbztdfp ulz csf alqdf tahczf
hol‘ qf ipzpbbf dpf lzf arfzzpbf.
Fo vcfsbt f ipz vcfq lzf l‘ htaf iczf
labf alqdf alqdfnnpf l fauzf l mtzbl
hol slq ulsaplz zpstdf qf ufczf!
Bfsb’l‘ frfzf hol utht l‘ upc‘ rtzbl
rf ulz bzfbbfz ilq gls ho’pt dp bztdfp,
ipzt‘ ilqq’fqbzl htal ho’pt d’ot ahtzbl...
Come aprire il codice

La chiave per decifrare il testo è 6: mettendo in corrispondenza
due alfabeti slittati di 6 posti e ruotati in modo che la A segua la
Z, cioè:

ABCDEFGHILMNOPQRSTUVZ
STUVZABCDEFGHILMNOPQR
1 2 3 4 5 6 ...


e facendo corrispondere i caratteri della riga di sopra a
quelli della riga di sotta si decifra il testo.
Come rompere il codice

Due aspetti:



Capire di che codice si tratta.
Trovare in qualche modo la chiave.
Nel caso banale della rotazione, si può procedere per tentativi, o
con statistiche sulla probabilità di ciascuna lettera (se la lettera A
ha una certa probabilità di occorrere in un testo, la lettera che
corrisponde alla A si tradirà, in testi sufficientemente larghi, per il
fatto di avere la stessa probabilità).



Nella criptografia ‘semplice’, si usa la stessa chiave
per ‘chiudere’ (= criptare) ed ‘aprire’ (= decriptare) il
messaggio (esempio: USA Federal Data Encryption
Standard (DES)).
Per motivi matematici, più la chiave è lunga,
maggiore è la sicurezza del messaggio. Anche gli
algoritmi posso avere vari gradi di sicurezza
Una chiave troppo corta è suscettibile a metodi di
attacco “a forza bruta” (=provare tutte le
combinazioni)
Quale password è sicura?
Alcuni suggerimenti:
 Password solo numeriche sono meno sicure (date di
nascita, numeri di telefono sono facili da scoprire).
 Meglio usare iniziali di una frase (Abito In Via
Cesare Battisti 2) p.es. o di un titolo (ma meglio non
“3MSC”).
 Usare sia lettere maiuscole che minuscole.
 Inserire dei numeri nella password.
Limiti della criptazione
semplice


Se non c’è un modo sicuro di trasmetter la
chiave, chi si impossessa della chiave può
leggere il messaggio.
E se c’era un modo sicuro per trasmettere la
chiave, perché non si è usato per trasmettere
il messaggio stesso?
Soluzione: Sistema cifrato a chiave
doppia




Una chiave fa il contrario di quello che fa l’altra: se una chiude,
l’altra apre, e viceversa. La stessa chiave non può sia aprire che
chiudere lo stesso documento.
Una chiave è pubblica (diffusa su internet, pubblicata da fonti
autorevoli, e potenzialmente nota a tutti), l’altra chiave è privata e
segreta.
E’ impossibile dedurre una chiave conoscendo l’altra.
Esempio: algoritmo RSA, basato sul concetto di “funzione a
senso unico”, una funzione f() in cui :
 Facile: x  f(x)
 Difficile: f(x)  x
(Esempio: la moltiplicazione di due numeri primi )
Come si usa?
Per mandare un messaggio sicuro:
1.
2.
3.
4.
Il mittente si procura la chiave pubblica del destinatario (p.es
trovandola su internet)
Il mittente usa la chiave pubblica del destinatario per ‘chiudere’
(criptare) il proprio messaggio, e lo spedisce.
Il destinatario riceve il messaggio ed usa la propria chiave privata
per aprirlo (decriptarlo).
Se un terzo si impossessasse del messaggio, potrebbe
facilmente sapere le chiavi pubbliche di mittente e destinatario,
ma non quella privata del destinatario. Poiché quest’ultima è
indispensabile per aprire il messaggio, esso resterebbe
indecifrabile.
Come si usa?
Per trasmettere un messaggio autenticato (”firma elettronica ”)
1.
2.
3.
Il mittente usa la propria chiave privata per criptare il
messaggio, e lo spedisce.
Il destinatario, ricevendo il messaggio, usa la chiave pubblica
del mittente per aprirlo.
Se il messaggio non si ‘apre’, vuol dire che il mittente non era
quello dichiarato, ma un terzo che ha tentato di ‘falsificare’ la
firma.
I due sistemi si possono combinare insieme, criptando un
messaggio 2 volte. E garantendo sia la vera origine del
messaggio che il suo contenuto.
Trasmissione sicura
Chiave pubblica A
Messaggio
di A
Chiave pubblica B
Messaggio
di A
B
A
Chiave privataA
Chiave privataB
Firma digitale
Chiave pubblica A
Messaggio
di A
Chiave pubblica B
Messaggio
di A
B
A
Chiave privataA
Chiave privataB
Trasmissione sicura + firma digitale
Chiave pubblica A
Messaggio
di A
Chiave pubblica B
Messaggio
di A
B
A
Chiave privataA
Chiave privataB
RIFERIMENTI / SITI



Rappresentazione digitale delle immagini e
compressione:
 http://www.med.unifi.it/didonline/annoI/informatica/node3.html
JPEG: http://www.brycetech.com/tutor/windows/jpeg_compression.html
MP3:
 http://it.wikipedia.org/wiki/MP3