IDUL 2011
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.
Vedi il sito:
http//www.siriusweb.com/tutorials/gifvsjpg/
SUONO ORIGINALE VS. MP3
CD:
Musica
campionata 44100 volte al secondo
16 bit per campione
Campioni per canali sinistro e destro (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 può 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 1: 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.
Esempio 2: 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. Questa è la nostra tabella di codifica. Ad esempio:
1. <spazio> = 0 (1 bit)
2. e = 10 (2 bit)
3. a = 110 (3 bit)
4. o = 1110 (4 bit)
5. i = 11110 (5 bit)
…
…
? = 1111111111111111111111111111
Osservazioni:
La compressione funziona solo perché la probabilità
di lettere diverse è molto diversa (vocali vs. consonanti
vs. segni di interpunzione)

Non
funzionerebbe su una sequenza casuale di simboli
(entropia massima)
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” è molto più probabile che dopo “z”)

Algoritmo LZ77
Basato sulla presenza di sequenze ripetute: a ciascuna sequenza ripetuta si
sostituisce un puntatore alla posizione e durata della sequenza originale.
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), che usa LZ77 insieme alla codifica di Huffman e
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.

Compressibilità ed entropia
Entropia: misura della quantità di incertezza legata alla
descrizione di un sistema con più stati possibili; dunque è
anche la misura della quantità di informazione necessaria
per descrivere compiutamente tale sistema.
 Intuitivamento, più un sistema è in ordine, più è facile
descriverlo, e dunque meno è l’informazione richiesta.
– moneta: 2 esiti = 1 bit di entropia
– dado: 6 esiti = 2.58 bit di entropia)

Più un testo contiene sequenze simili, minore è la sua
entropia e più è suscettibile ad essere compresso.

Compressibilità ed entropia
La
relazione tra entropia e comprimibilità è
stata sfruttata al contrario per misurare la
distanza/affinità tra “testi” diversi.
Porzioni di DNA
 Testi in lingue diverse (tipologia linguistica)
 Testi di autore sconosciuto (stilometria, ecc.)

Si veda: Baronchelli, Caglioti, Lorento 2006 per un
approccio che usa LZ77 per misurare la somiglianza
testuale.
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.
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
2 bit si codificano 4 distinzioni (22)
Con 3 bit si codificano 8 distinzioni (23)
…
Con N bit si possono codificare 2N distinzioni
differenti
Con
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
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è:
A
B C D E F G H I L M N O P Q R S T U V Z
S T U V Z A B C D E F G H I L M N O P Q R
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). Questa
tecnica è ovviamente possibile solo se chi cerca di violare il
messaggio
Password e GPU
• Le moderne schede grafiche sono in grado di
effettuare operazioni matematiche ad altissima
velocità.
• Queste operazioni possono essere usate per
compiti che non hanno nulla a che fare con la
grafica. Tra i quali, la decodifica delle password.
• Tramite questa tecnica, una password di 7
caratteri può essere riconosciuta in 5 secondi
(si veda http://cyberarms.wordpress.com/2010/08/17/gpucrackers-make-seven-character-passwords-inadequate/)
Quale password è sicura?
Alcuni suggerimenti:
 Password solo numeriche sono molto meno sicure (date di
nascita, numeri di telefono sono sia corte che facili da
scoprire).
 Meglio usare intere frasi, magari senza spazi, con almeno
12 caratteri (AbitoInViaBattisti2; non usare semplicemente
il proprio nome e cognome)
 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)
 esempio: da una serie di numeri primi, il loro prodotto:
2 * 3 * 13 * 17 => 1326
Difficile: f(x) => x
esempio: da un numero, la sequenza ordinata dei suoi fattori primi
1326 => 2 31317
Come si usa?
Per mandare un messaggio sicuro:
1.Il
mittente si procura la chiave pubblica del destinatario (p.es trovandola
su internet)
2.Il mittente usa la chiave pubblica del destinatario per ‘chiudere’ (criptare)
il proprio messaggio, e lo spedisce.
3.Il destinatario riceve il messaggio ed usa la propria chiave privata per
aprirlo (decriptarlo).
4.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.Il
mittente usa la propria chiave privata per criptare il messaggio, e lo
spedisce.
2.Il destinatario, ricevendo il messaggio, usa la chiave pubblica del mittente
per aprirlo.
3.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/anno-I/informatica/node3.html
JPEG: http://www.brycetech.com/tutor/windows/jpeg_compression.html
MP3:

http://it.wikipedia.org/wiki/MP3
Lazzari et al.: Cap 2