Introduzione

Le comunicazioni hanno sempre rivestito un ruolo molto importante nella storia dell' uomo.
Nella società odierna, lo scambio d'informazioni è divenuto il punto nevralgico di tutti i rapporti interpersonali.
Il continuo sviluppo tecnologico ha portato alla nascita di innumerevoli sistemi di comunicazione, che stanno velocemente sostituendosi ai più tradizionali mezzi.
Ormai la maggior parte dei documenti, scritti, messaggi, corrispondenza, etc... vengono realizzati, gestiti e scambiati mediante strumenti informatici che sono decisamente più comodi dei corrispondenti mezzi tradizionali, ma pongono tutta una serie di nuove problematiche.
Infatti uno dei problemi maggiori in cui si potrebbe incappare è la possibilità da parte di terzi di intercettare, ascoltare e modificare le informazioni, compromettendo in questo modo l'affidabilità del canale:

Fig. Canale insicuro

Da sempre si è sentito il bisogno di avere dei canali "sicuri" per le comunicazioni: la crittografia è questione antica.
Gnu Privacy Guard(GnuPG) si colloca in questo scenario come uno strumento crittografico progettato per comunicare e immagazzinare dati in modo sicuro. Nasce in Germania nel 1997 per opera di Werner Koch come un sistema crittografico alternativo a PGP totalmente open source che rispetta lo standard internet OpenPGP, descritto nella RFC 2440. Utilizza un sistema “ibrido” (simile a quello utilizzato da PGP) con l’utilizzo combinato di algoritmi simmetrici (crittografia tradizionale) e asimmetrici (crittografia a chiave pubblica).
GnuPG supporta molti sistemi operativi tra cui i principali sono Linux, FreeBSD, OpenBSD, NetBSD, Windows 95/98/NT/2000/ME/XP e MacOS X. L’utilizzo avviene tramite linea di comando, ciò vuol dire che per utilizzarlo è necessario digitare una serie di comandi sul prompt di sistema, un po’ come avveniva nei vecchi sistemi MsDos. Esistono, tuttavia, anche dei front-end grafici che consentono di utilizzare il software in maniera più intuitiva, come il GPA Privacy Assistant per sistemi Gnu/Linux basato sulle librerie GTK o il WinPT per sistemi Microsoft Windows.
Inoltre sono stati realizzati dei plug-in per integrare GnuPG nei più conosciuti client di posta elettronica come Eudora, Microsoft Outlook, Mutt, Pine e sistemi quali Mozilla, MacGPG e così via.
Nel corso della trattazione introdurremo la crittografia in generale soffermandoci in particolare sulla crittografia simmetrica e asimmetrica analizzandone gli aspetti principali. Dopodichè faremo una breve panoramica su PGP per poi introdurre finalmente che cosa è GnuPG. Analizzeremo come avviene la cifratura e la decifratura in GnuPG e in che modo sia possibile apporre firme digitali ai documenti. Illustreremo, a questo punto, gli algoritmi supportati e in particolare vedremo la cifratura e firma con ElGamal e la firma con DSA. Spiegheremo, di seguito, il modello utilizzato per la convalida delle chiavi noto come Web of Trust, confronteremo GnuPG e PGP evidenziandone le differenze. Infine mostreremo i passi da seguire per l'installazione e i comandi principali per l'uso di GnuPG.

Crittografia

Era utilizzata spesso in contesti di guerra per permettere comunicazioni sicure tra le truppe ma il suo odierno utilizzo è sicuramente meno bellicoso e tocca la sfera della riservatezza personale tramite le odierne comunicazioni telematiche.
Tuttavia la sua importanza in ambito militare e strategico ha portato, nel corso degli anni, allo sviluppo di tecniche sempre più complesse che utilizzano algoritmi derivanti dalle più avanzate conoscenze matematiche. Nella figura seguente sono riportati alcuni tra i più importanti sistemi crittografici della storia, ulteriori informazioni è possibile reperirle qui:

Fig. La Crittografia nella storia

Con la progressiva crescita di complessità degli algoritmi, si è arrivati anche a definire alcuni requisiti di base che qualsiasi sistema crittografico deve soddisfare affinché possa essere considerato sufficientemente robusto (cioè difficilmente attaccabile da tentativi di crittoanalisi da parte del nemico): uno di questi requisiti è che la robustezza del sistema non deve dipendere dalla segretezza dell'algoritmo (il cosiddetto principio di Kerckhoff ). Questo perchè, come illustrato nella seguente figura, è possibile effettuare Reverse Engineering ripercorrendo al contrario i passi effettuati durante lo sviluppo di una applicazione: Analisi dei Requisiti, Disegno e Implementazione.

Fig. Reverse Engineering

Nel settembre del 1995, due studenti dell'università di Berkeley, Ian Goldberg e David Wagner, riuscirono a rompere lo schema del generatore dei numeri casuali di Netscape effettuando reverse-engineering  (ulteriori informazioni sono reperibili qui).

Crittografia a chiave Simmetrica e a chiave Asimmetrica

Nella crittografia tradizionale viene utilizzata un unica chiave (sia per codificare, sia per decodificare i messaggi) che deve essere concordata precedentemente, mediante un "canale sicuro". Di seguito sono illustrati i passi da seguire per inviare un messaggio quando si utilizza un algoritmo simmetrico (nella seguente figura assumiamo che Biagio invia il messaggio ad Annarella):

Fig. Crittografia a chiave simmetrica

La crittografia a chiave pubblica, invece, permette a due (o più) persone di comunicare in tutta riservatezza anche se non si sono mai incontrate prima e dunque non è mai stata concordata alcuna chiave di codifica.
La crittografia a chiave pubblica si basa su una coppia di chiavi: una chiave pubblica e una chiave privata. La chiave pubblica serve per codificare il messaggio, mentre quella segreta serve per decodificarlo (come se una cassaforte avesse due chiavi distinte, una usata per aprirla e una per chiuderla). Di seguito sono illustrati i passi da seguire per scambiarsi un messaggio quando si utilizza un algoritmo asimmetrico:

Fig. Crittografia a chiave asimmetrica

La differenza rispetto alla crittografia tradizionale sta dunque nel fatto che adesso non è più necessario trovare un luogo sicuro nel quale vedersi e scambiarsi la chiave di codifica/decodifica, in quanto anche nel caso in cui la chiave pubblica venisse intercettata non ci sarebbe assolutamente nessuna conseguenza per la sicurezza: le chiavi pubbliche che viaggiano liberamente in rete possono solo crittare e non decrittare i messaggi.
Un altro utilizzo dei cifrari a chiavi asimmetriche è quello di firmare documenti digitali. Per fare ciò la chiave privata verrà usata per firmare (cifrare) mentre la chiave pubblica per verificare (decifrare).

PGP

Uno dei software che è divenuto molto famoso nell’ultimo decennio in tema di crittografia è il PGP (Pretty Good Privacy), sviluppato da Phil Zimmermann nel 1991.

È un software di crittografia per la posta elettronica e la protezione dei file di uso personale che consente di firmare una e-mail lasciando il testo in chiaro, oppure cifrarla senza firmarla, o fare tutte e due le cose insieme.

L'interesse suscitato da questo strumento attirò a sé moltissimi interessati, ma scatenò sull'autore l'ira del governo statunitense visto che i sistemi di cifratura forte sono assimilati alle armi e fino ad alcuni anni fa ne era quindi proibita l'esportazione.
Copie di PGP vennero scaricate all'estero poche ore dopo la messa on-line del programma; il risultato fu che nel 1993 Zimmerman venne messo sotto inchiesta, con la prospettiva di pesanti sanzioni penali. Dopo tre anni la vicenda si concluse senza esiti negativi per la propria persona.

Questa improvvisa popolarità di PGP calamitò l'attenzione di diverse software house e Zimmermann, probabilmente stravolto dalle questioni giudiziarie e intrigato da proposte commerciali, non perse tempo a vendere i diritti di PGP. Il programma comunque, anche se con notevoli limitazioni nell'utilizzo, rimane gratuito per uso personale e non commerciale.

GnuPG

 

 

Cos'è GnuPG

 

Gnu (acronimo ricorsivo di "GNU's Not Unix") Privacy Guard (GnuPG) è uno strumento per comunicare in modo sicuro nato in Germania nel 1997 per opera di Werner Koch, uno sviluppatore indipendente interessato alla crittografia open source. GnuPG è un sistema crittografico che permette la cifratura/decifratura e autenticazione di messaggi. La cifratura/decifratura si basa su un sistema “ibrido” simile a quello usato da PGP con l’utilizzo combinato di algoritmi simmetrici (crittografia tradizionale) e asimmetrici (crittografia a chiave pubblica), ma non preclude la possibilità di cifrare/decifrare anche solo con algoritmi simmetrici. L'autenticazione di documenti o dei messaggi avviene attraverso l'utilizzo delle firme digitali.

GnuPG supporta molti sistemi operativi tra cui i principali sono Linux, FreeBSD, OpenBSD, NetBSD, Windows 95/98/NT/2000/ME/XP e MacOS X. E' possibile utilizzarlo anche su altri sistemi operativi come: AIX, BSDI , HPUX, IRIX, MP-RAS, OSF1, OS/2, SCO, SunOS, Solaris, USL Unixware, ma a causa della mancanza di una sorgente di entropia ben testata, dovrebbe essere usato con cautela.
L’utilizzo di GnuPG avviene tramite linea di comando, ciò vuol dire che per utilizzarlo è necessario digitare una serie di comandi sul prompt di sistema, un po’ come avveniva nei vecchi sistemi MsDos.
Esistono, tuttavia, dei front-end grafici che consentono di utilizzare il software in maniera più intuitiva, come il GPA Privacy Assistant per sistemi Gnu/Linux basato sulle librerie GTK o il WinPT per sistemi Microsoft Windows.
Inoltre sono stati realizzati dei plug-in per l'integrazione con i più conosciuti client di posta elettronica come Eudora, Microsoft Outlook, Mutt, Pine e sistemi quali Mozilla, MacGPG e così via.

Il cuore della gestione delle chiavi presente in GnuPG è la nozione di firma di chiavi. Tale nozione è utilizzata anche in uno schema noto come "Web of Trust" (rete della fiducia), la quale estende la certificazione delle chiavi non firmate di proprio pugno. Infatti la convalida di una chiave può esser fatta da qualcun’altro di cui ci si fida.

GnuPG consente ad un utente di possedere una coppia di chiavi primaria e zero o più coppie di sottochiavi addizionali. La sottochiave può essere una chiave di firma DSA, una chiave di sola cifratura ElGamal, una di firma RSA oppure una di cifratura RSA.

Avere più di una sottochiave può essere utile in quanto gli User ID associati alla propria chiave pubblica principale vengono convalidati dalle persone con le quali si comunica. Cambiare la chiave primaria necessita, quindi, una ricertificazione ma ciò potrebbe risultare difficile e dispendioso.
D'altro canto è opportuno cambiare periodicamente le chiavi di cifratura per migliorare la sicurezza, se infatti una chiave viene compromessa, tutti i dati criptati con quella chiave saranno vulnerabili. Cambiando chiave invece, solo i dati cifrati con la chiave compromessa saranno rivelabili.

Utilizzando le sottochiavi cambiare una chiave risulta più semplice poiché queste sono autofirmate con la propria chiave di firma principale all'atto della generazione. Non è necessario, quindi, farsi riconvalidare la nuova chiave da tutti gli altri utenti.

La coppia di chiavi primaria e le sottochiavi sono raggruppate assieme per facilitarne la gestione nel portachiavi (spesso considerato semplicemente come un’unica coppia di chiavi).

Attualmente, sulla scia del successo di GnuPG, stanno nascendo molti altri progetti crittografici open source basati su questo software, come il GPGME (GnuPG Made Easy, un sistema API crittografico riservato agli sviluppatori per la realizzazione di applicazioni basate sulla crittografia a chiave pubblica) o come il progetto GNUTLS (un’implementazione alternativa del protocollo di comunicazione TLS/SSL con licenza GPL).

 

 

 

 

 

Cifratura e decifratura in GnuPG

 

GnuPG fa uso di diversi concetti di crittografia come algoritmi simmetrici, algoritmi a chiave pubblica, e hashing Oneway.
Gli algoritmi asimmetrici non sono una soluzione ideale poiché le operazioni di cifratura e decifratura a chiave pubblica sono molto più costose delle corrispondenti operazioni sui sistemi simmetrici.
Ciò nonostante gli algoritmi a chiave pubblica rappresentano uno strumento efficace per distribuire le chiavi degli algoritmi simmetrici e per questo vengono usati in sistemi di crittografia ibridi (nota: la sicurezza di un algoritmo ibrido non è mai più forte del più debole algoritmo utilizzato).

 

 

 

 

 

 

Modalità Ibrida

Sia PGP che GnuPG possono utilizzare algoritmi ibridi. In particolare GnuPG funziona utilizzando l'algoritmo asimmetrico ElGamal per condividere una chiave che sarà utilizzata nel sistema simmetrico scelto (RIJNDAEL, 3DES, BLOWFISH...).

Fig. Cifrare in GnuPG

 

 

Fig. Decifrare in GnuPG

Il messaggio viene quindi criptato usando tale chiave, detta chiave di sessione, e successivamente spedito al destinatario.
La chiave di sessione (criptata utilizzando l’algoritmo a chiave pubblica/privata) e il messaggio da spedire (cifrato con l’algoritmo simmetrico) sono automaticamente combinati in un solo pacchetto.
Il destinatario usa la propria chiave privata per decifrare la chiave di sessione che viene poi usata per decifrare il messaggio.
Se un malintenzionato riuscisse a decifrare una chiave di sessione, egli sarebbe in grado di leggere solo un messaggio, quello criptato con quella chiave di sessione. Il malintenzionato dovrebbe ricominciare l'attacco e decifrare un’altra chiave di sessione per poter leggere un altro messaggio.

 

 

Modalità Simmetrica

I documenti posso anche essere criptati senza l'utilizzo della crittografia a chiave pubblica. Al suo posto è possibile utilizzare un algoritmo di crittografia simmetrico per cifrare il documento. Con la cifratura a chiave simmetrica, un documento può essere cifrato con una chiave simmetrica derivata dal passphrase fornita al momento in cui il documento viene criptato, o mediante un meccanismo a due fasi simile al metodo ibrido descritto sopra, con l'unica differenza che la chiave di sessione è anch'essa cifrata con un algoritmo di cifratura simmetrico usando una chiave segreta condivisa.

Per una buona sicurezza, la passphrase utilizzata non dovrebbe essere la stessa usata per proteggere la propria chiave privata. Ovviamente la passphrase deve essere conosciuta anche dalla nostra controparte, per poter decifrare il messaggio. La cifratura simmetrica è anche utile per rendere sicuri i propri documenti su disco tenendo segreta la passphrase usata.
 

 

 

Generazione di chiavi simmetriche

Possiamo dividere le chiavi simmetriche usate da GnuPG in due categorie:

- chiavi di sessione
- chiavi simmetriche derivanti da passphrase

Le chiavi di sessione usate da GnuPG sono generate come numeri random e sono differenti per ogni messaggio.
Queste sono usate per la cifratura simmetrica dei messaggi e poi a loro volta sono cifrate o con chiave pubblica del destinatario (modalità ibrida) o con un'altra chiave simmetrica derivante dal passphrase (cifratura simmetrica a due fasi). Il pacchetto con la chiave di sessione cifrata viene anteposto al pacchetto con i dati cifrati e il tutto è spedito al destinatario.

Le chiavi simmetriche derivanti da passphrase sono ottenute applicando alla passphrase una particolare funzione chiamata String-to-key (s2k).
La funzione s2k effettua varie operazioni sul passphrase come l'aggiunta di dati random e l'applicazione di una funzione hash, su più iterazioni, fino ad ottenere la chiave simmetrica. Tutti i dati che occorrono per la decifratura sono memorizzati in un particolare campo (anteposto alla chiave cifrata) detto specificatore S2K.

 

 

Modalità di cifratura simmetrica

GnuPG effettua la cifratura simmetrica usando una variante del Cypher Feedback Mode (modalità CFB). In questa modalità viene usato un vettore di inizializzazione (IV) avvalorato con tutti zero, il testo in chiaro viene fatto precedere da 10 ottetti di cui i primi 8 sono random e il 9° e 10° sono uguali al 7° e al 8°:

Fig. Variante CFB

 

La ripetizione di 16 bit negli 80 che precedono il testo in chiaro permettono a chi decifra il messaggio di controllare immediatamente se la chiave di sessione è corretta.
Questa variante del CFB fa uso di un CFB shift pari a 8 ottetti (64 bit) che rappresenta anche la lunghezza del blocco usato dall'algoritmo di cifratura.
La cifratura e la decifratura avvengono secondo i seguenti algoritmi:

 

Fig. Cifratura/Decifratura con variante CFB

 

Dove R₁ rappresenta i primi 8 ottetti e R₂ sono gli ultimi 2 ottetti che precedono il testo in chiaro; P₁,P₂,...,P_k rappresentano i blocchi di 64 bit del testo in chiaro; ε_k(.) rappresenta l'applicazione dell'algoritmo di cifratura scelto usando la chiave k. La notazione X_[i,i+1] rappresenta rispettivamente l' (i)-esimo e l' (i+1)-esimo byte di un blocco di dati X per 0 £ i £ 7, mentre X_[i-j] rappresenta  l'intervallo  dal (i)-esimo all' (j)-esimo byte  di un blocco di dati X per 0 £ i £ j £ 7. Il simbolo ' ° ' è l'operatore di concatenazione, mentre il simbolo ' Å ' è l'operatore logico or esclusivo (XOR). C₁ rappresenta il 1° blocco di 64 bit di dati cifrati;  C₂ rappresenta il 2° blocco di dati cifrati di 16 bit, mentre C_i per 3 £ i £ k+2 rappresenta l' i-esimo blocco di 64 bit di dati cifrati.

 

 

 

Firma Digitale in GnuPG

 

Una firma digitale è un valore calcolato con un algoritmo crittografico apposto ad un data object che deve godere delle seguenti proprietà:

• deve essere facilmente prodotta dal legittimo proprietario

• nessun utente deve poter riprodurre la firma di altri

• chiunque deve poter facilmente verificare la firma

• deve essere non ripudiabile (il firmatario non può negare la sua firma)

Un sistema di firma digitale deve garantire due importanti proprietà:

1. E' difficile trovare due documenti che possiedono la stessa firma digitale
2. Data una firma è difficile recuperare il documento che l' ha prodotta

E' possibile apporre una firma digitale a un documento utilizzando gli algoritmi a chiave pubblica/privata e funzioni hashcome illustrato in figura:

Fig. Firmare in GnuPG

 

Per generare la firma, quindi, calcoliamo l'hash del documento che verrà poi cifrato usando la chiave privata del firmatario.

• Viene scelto un numero primo p molto grande e un generatore gÎZ_p^* con 1<g<p-1

• Viene scelto un intero K_prv tale che 1<K_prv<p-1 dove MCD(K_prv,p-1)=1 , che è utilizzato come chiave privata

• Viene calcolato il valore K_pub=g^Kprvmodp

La chiave pubblica sarà costituita dalla tripla (p,g,K_pub).

Generazione del numero primo

In ElGamal i numeri primi vengono generati seguendo l'algoritmo basato sui suggerimenti proposti da Chae Hoon Lim e Pil Joong Lee in Crypto '97 (pag. 260). Nell'articolo, i due studiosi hanno presentato un attacco di "key recovery" che potrebbe rivelare parti o, in molti casi, l'intera chiave segreta di molti schemi basati sul problema del logaritmo discreto. E' possibile contrastare questo attacco aggiungendo esplicitamente dei passi di controllo, tuttavia, tali controlli diminuiscono l'efficienza dell'algoritmo.
E' preferibile perciò utilizzare dei numeri primi sicuri oppure un primo p tale che ogni fattore primo di (p-1)/2q è più grande di |q|. Questi ultimi, in particolare, risultano essere molto più veloci da generare e sembrano essere forti (contro gli attacchi conosciuti) quanto i primi sicuri.

Per generare un primo p tale che p=2qp₁+1, prima bisogna scegliere un primo casuale p₁ di lunghezza |p|-|q|-1 e poi, provando per dei primi q (di grandezza |q|) scelti a caso, verificare che p=2qp₁+1 sia primo. Quindi è necessario generare un certo numero di primi q per trovare un primo p; considerando che il numero di primi nell'intervallo [1,x] (dove x è un intero maggiore di zero) è asintotico a x/lnx (Teorema dei numeri primi), se calcoliamo casi favorevoli su casi possibili, la probabilità di scegliere in maniera casuale un numero primo è 1/lnx (quindi per generare un primo p di 1024 bit occorrono circa 710 primi q). Fortunatamente, cercare i numeri primi q, non richiede molto tempo poiché la grandezza di q è abbastanza piccola se comparata con quella di p (in genere q è grande 160 bit mentre p è 768 bit).
Utilizzando questa idea, risulta più efficiente generare un primo p della forma p=2_*q_*p_1*..._*p_n+1, dove i p_i sono dei primi di grandezza maggiore (o al più uguale) a |q|. Il numero di p_i necessari e la loro grandezza la si determina risolvendo la disuguaglianza seguente: L=|p_i|≈(|p|-|q|-1)/n≥|q|.

A questo punto si genera un pool di m numeri primi di lunghezza L da cui verranno scelti gli n p_i. Si hanno, quindi, il coefficiente binomiale di m su n candidati per p. Considerando la densità dei primi è possibile rendere questo numero grande a sufficienza per garantire che ci siano sufficienti probabilità affinché un primo p sia generato da questo pool. Per esempio, per un primo p di 1024 bit e q di 200 bit è possibile scegliere  L=206 bit, n=4 e m=18 così da avere circa 3000 candidati per p che ci assicurano con alta probabilità il successo dell'algoritmo.

Dunque, seguendo i suggerimenti proposti nell'articolo dai due studiosi, i passi da eseguire sono i seguenti:

1. Genera un numero primo q di 160, 200 o 240 bits rispettivamente per le chiavi di lunghezza 768, 1024, 2048 bits
2. Calcola il numero n di fattori primi necessari e ne sceglie la lunghezza che deve essere almeno pari a quella di q
3. Crea un pool di numeri primi (la cui dimensione di default è m=3n+5) ognuno della lunghezza determinata al passo 2
4. Ottiene una nuova permutazione dal pool (p₁, ... ,p_n), se si sono analizzate tutte le permutazioni torna al passo 3
5. Calcola un candidato ad essere eletto numero primo come p=2_*q_*p_1*..._*p_n+1
6. Controlla che il candidato sia della lunghezza desiderata (questo può cambiare q se sembra non essere possibile generare un primo della lunghezza desiderata)
7. Controlla se il candidato è effettivamente un primo usando le divisioni banali e il test di Miller-Rabin
8. Se è un primo vai al passo 9, altrimenti vai al passo 4
9. Ricerca un generatore per il gruppo ciclico Z_p^* di ordine p-1 utilizzando la fattorizzazione ricavata per costruzione al passo 5

Ricerca del generatore di un gruppo ciclico Z_p*

L'algoritmo per cercare un generatore prende in input il gruppo ciclico Z_p^* di ordine p-1 e la scomposizione in fattori primi di p-1=p₁^e1_*p₂^e2...._*p_k^ek_.
Osserviamo che tale scomposizione è ottenuta dal passo 5 dell'algoritmo per la generazione del numero primo e risulta uguale a: p-1=2_*q_*p_1*..._*p_n.

L'algoritmo opera nel seguente modo:

1. sceglie un elemento a caso g Î Z_p^*
2. for i from 1 to k do
3.     calcola b ¬ g^(p-1)/pi
4.      if b=1 then vai al passo 1
5. return (g)
    

Cifratura

La cifratura di un messaggio è un’operazione un po’ più complessa rispetto a quella effettuata mediante RSA, infatti se Biagio vuole inviare un messaggio ad Annarella, posto che (p,g,Kpub_A) sia la tripla dei valori pubblici di Annarella (calcolate secondo i passi specificati sopra), deve effettuare le seguenti operazioni:

• Rappresentare il messaggio m che si vuole spedire come un intero 1£M£p-1 (Scegliendo p sufficientemente grande questa rappresentazione è sempre possibile; in alternativa, se M>p-1, il messaggio può essere suddiviso in più blocchi M_i con i=0,1,2,3,... tale che 1£M_i£p-1 )

• Scegliere un intero casuale d tale che 1<d<p-1

• Calcolare dºg^dmodp

• Calcolare eºM*(g ^Kpub)^dmodp

• Inviare come messaggio cifrato C la coppia (d,e)

Decifratura

Annarella per decifrare il messaggio C deve effettuare le seguenti operazioni:

• Tramite la sua chiave privata K_prv calcola d^p-1-Kprvmodp che risulta essere uguale a :

d^p-1-Kprvmodp =d^p-1*d^-Kprvmodp

Poichè gÎZ_p^* è possibile applicare il teorema di Eulero che dice:

XÎZ_n^*ÞX^f(n)º1modn

quindi

d^p-1º(g ^d)^p-1modpº1modp

allora

(d^p-1*d^-Kprv)modp=(1*d^-Kprv)modp= (g^d)^-Kprvmodp=((g^Kprv)^d)^-1modp

dimostrando che d^p-1-Kprvº((g^Kprv)^d)^-1modp

(d^p-1-Kprv*e)modp=(((g ^Kprv )^d)^-1*M*(g ^Kprv )^d)modp 

Vengono combinati insieme 5 ingredienti : Numero Primo p Generatore g Chiave pubblica KpubA Numero casuale d Messaggio M Viene generata la coppia (d,e) che rappresenta il messaggio cifrato C     Il messaggio C viene inviato tramite un qualsiasi mezzo di comunicazione Il destinatario del messaggio C utilizza il numero primo p e la sua chiave privata Kprv per decifrarlo

Sicurezza

Quindi rompere l'algoritmo di ElGamal equivale a risolvere efficientemente tale problema.

• Selezionare un numero primo q tale che 2¹⁵⁹<q<2¹⁶⁰

• Scegliere t tale che 0£t£8 e selezionare un numero primo p con 2^511+64*t<p<2^512+64*t che gode della proprietà: q|(p-1).

• Selezionare un generatore a dell'unico gruppo ciclico di ordine q in Z_p^* in questo modo:
  1. Scegli a caso un elemento gÎZ_p^* e calcola a=g^(p-1)/qmodp.
  2. Se (a=1) allora vai al passo 1 altrimenti ritorna a.

• Seleziona un intero a caso s tale che 1£s£q-1.

• Calcola b = a^smodp.

• Calcolare un numero casuale r tale che 1£r£q-1 (l'inverso di r esisterà certamente poiché 1£r£q-1, e gcd(r,q)=1 in quanto q è primo).

• e'=SHA1(M)*d^-1modq

• e''=g*d^-1modq

• Se (a^e'*b^e''modp)modq=g allora la firma è valida

 

Rete di fiducia

(Web of Trust)

 

Un punto debole degli algoritmi a chiave pubblica è la diffusione delle chiavi: un malintenzionato potrebbe manomettere il portachiavi di un utente oppure spacciarsi per qualcun'altro facendo circolare una falsa chiave pubblica per un certo UserID. L'impostore potrebbe, a questo punto, intercettare e decifrare il messaggio, successivamente cifrarlo con la vera chiave pubblica del destinatario originale e inviarglielo, senza che quest'ultimo si renda conto dell'intercettazione.

Ad esempio, supponiamo che il malintenzionato voglia tenere sotto controllo i messaggi che Biagio spedisce ad Annarella. Il diavoletto crea una nuova coppia di chiavi pubblica/privata e rimpiazza la copia della chiave pubblica di Annarella in possesso di Biagio con la nuova chiave pubblica. Successivamente si mette ad intercettare i messaggi che Biagio spedisce ad Annarella. Ogni messaggio intercettato viene decriptato utilizzando la nuova chiave privata e recriptato usando la vera chiave pubblica di Annarella per poi inviarglielo. Tutti i messaggi spediti da Biagio ad Annarella possono ora essere letti dal diavoletto. Questo tipo di attacco prende il nome di man in the middle ed è illustrato nella seguente figura:

Fig. Man in the Middle

La soluzione adottata da GnuPG (e anche dal PGP) è la firma delle chiavi: una chiave pubblica può essere firmata da altre persone, certificando così che la chiave appartiene veramente alla persona che sostiene di esserne il proprietario (convalida della chiave).
Una chiave viene convalidata verificando l’impronta digitale della chiave stessa e successivamente firmando la chiave per certificarla come chiave valida.
L’impronta digitale di una chiave può essere velocemente visualizzata con il comando gpg --fingerprint, questa va verificata con il possessore di quella chiave.
Ciò può essere fatto di persona, per telefono o attraverso un qualsiasi altro mezzo con il quale sia possibile garantire che si sta comunicando con il vero possessore della chiave (canale sicuro).
Se l’impronta digitale che si ottiene eseguendo il comando è la stessa impronta digitale che il possessore della chiave detiene, allora si può essere sicuri di possedere una corretta copia della chiave. Dopo aver controllato l’impronta digitale, si può procedere alla firma in modo da convalidarla.
Sfortunatamente questa procedura risulta antipatica quando, per qualche motivo, si debba convalidare un gran numero di chiavi o comunicare con persone che non si conoscono direttamente.
GnuPG risolve questo problema con un potente e flessibile modello basato sulla fiducia, noto come Web of Trust (rete della fiducia), il quale non richiede all’utente di convalidare personalmente ogni chiave che viene importata. Una notazione grafica comunemente usata per rappresentare la "rete della fiducia" è quella dei grafi orientati. In tale notazione, ogni nodo rappresenta una coppia (userID, chiave pubblica) mentre, gli archi orientati specificano le firme apposte dall'utente associato alla userID del nodo origine sulle chiavi indicate nei vari nodi destinazione. Ad esempio, il grafo seguente mostra la firma apposta da Annarella sulla chiave pubblica di Biagio:

N.B.	negli esempi che seguiranno useremo sempre la convenzione di omettere le chiavi pubbliche dai nodi.

La rete della fiducia, quindi, descrive le relazioni di fiducia esistenti tra un gruppo di chiavi. I cammini che si possono individuare nel grafo associato al Web of Trust prendono il nome di Trust Paths (percorsi di fiducia).

 

Vediamo ora in dettaglio il funzionamento del "Web of Trust". In tale modello la responsabilità di convalidare le chiavi pubbliche è delegata a persone di cui ci si fida. Ad ogni chiave GnuPG assegna un valore, noto come "fiducia nel proprietario" (ownertrust), per esprimere quanta fiducia si ha nel possessore di quella chiave per quanto riguarda la firma di altre chiavi. Così, se non si ha fiducia nel proprietario di una chiave, le eventuali firme apposte da quest’ultimo su un'altra chiave verranno ignorate durante il calcolo del valore di validità della chiave.

Un possessore di chiavi, in questo modello, può essere collocato in uno dei seguenti livelli di fiducia:

Sconosciuto	non c’è nessuna informazione sul giudizio che il possessore della chiave ha nel firmare altre chiavi
Nessuna	il possessore non firma opportunamente le chiavi degli altri
Marginale	il possessore capisce le implicazioni che comporta firmare una chiave ed è capace di convalidare le chiavi propriamente prima di firmarle
Piena	il possessore ha un'eccellente comprensione di ciò che comporta firmare una chiave e la sua firma su una chiave è tanto valida quanto la propria

Sconosciuto	non c’è nessuna informazione sulla validità della chiave pubblica (le chiavi del proprio portachiavi che non siano le proprie hanno inizialmente questo livello di fiducia)
Nessuna	la chiave pubblica non appartiene alla persona che sostiene di esserne il proprietario
Marginale	la chiave pubblica potrebbe appartenere alla persona che sostiene di esserne il proprietario
Piena	la chiave pubblica appartiene veramente alla persona che sostiene di esserne il proprietario

2. il percorso delle chiavi firmate (trust path) che risale dalla chiave K alla propria chiave è al massimo di cinque passi.

La lunghezza del percorso, il numero delle chiavi con validità marginale richiesto e il numero di chiavi con validità piena possono essere modificati con le opzioni --max-cert-depth, --marginals-needed e --completes-needed rispettivamente. I valori dati precedentemente sono quelli preimpostati in GnuPG.

Ad esempio (Caso 1.b):

- Annarella ha piena fiducia in Biagio
- Biagio ha convalidato la chiave di Carla

Se Annarella è convinta che Biagio sia capace di convalidare propriamente le chiavi di altri, allora, Annarella può dedurre che la chiave di Carla sia valida senza dover necessariamente eseguire alcun controllo.
Semplicemente lei usa la propria copia (convalidata) della chiave pubblica di Biagio per controllare che la firma apposta da Biagio alla chiave di Carla sia buona.

E’ importante distinguere tra "fiducia nella chiave" e "fiducia nel possessore della chiave", lo scenario che si potrebbe avere è il seguente:
la chiave di Biagio è valida per Annarella in quanto è stata lei a firmarla, ma Annarella potrebbe non fidarsi di Biagio e della sua capacità di convalidare propriamente le chiavi che egli firma.
In questo caso, riferendosi all’esempio precedente, Annarella non considererebbe valida la chiave di Carla basandosi solo sulla firma di Biagio.

Consideriamo, ora, il seguente esempio di web of trust (caso 1.c):

- Annarella non ha fiducia nella capacità di Biagio nel firmare altre chiavi
- Annarella ha fiducia marginale in Luana, Roberta e Vittoria
- Luana, Roberta e Vittoria hanno convalidato la chiave di Carla

Poiché ci sono 3 persone con fiducia marginale che hanno convalidato la chiave di Carla, l'algoritmo la considera valida (caso 1.c) e Annarella potrà utilizzarla senza dover effettuare ulteriori controlli.

Altra situazione possibile è la seguente (Caso 2):

- Annarella ha fiducia piena in Biagio, Carla, Salvatore, Marco e Sergio
- Sergio ha convalidato la chiave di Angelo

L'algoritmo non considera la chiave di Angelo valida perché la lunghezza del trust path che risale da Angelo ad Annarella è 6 (caso 2).

GnuPG vs PGP

Oggi il PGP è un prodotto commerciale a tutti gli effetti, venduto in varie configurazioni e ricco di opzioni. Ad onor del vero, ne esiste una versione freeware, ma con notevoli limitazioni sia nell'utilizzo che nelle funzioni offerte.
PGP freeware (scaricabile qui), infatti, può essere usato soltanto da:

con le seguenti limitazioni:

GnuPG è nato come un sostituto completo e gratuito del PGP che non usa l'algoritmo di crittografia IDEA, protetto da copyright, e quindi può essere utilizzato senza restrizioni.

A differenza del PGP, infatti, GnuPG fa parte della famiglia di strumenti e applicazioni GNU, realizzate e distribuite in accordo con la Licenza Pubblica Generica (GPL) della Free Software Foundation (FSF) che si basa sulle cosiddette "quattro libertà":

Si tratta di concetti molto importanti, che avvantaggiano tutti, compresi gli sviluppatori, che vedono i loro prodotti migliorati dagli stessi utenti.
Questi possono così contribuire costruttivamente al miglioramento dei programmi anziché limitarsi alla semplice segnalazione di problemi ai produttori. Questi ultimi traggono il loro vantaggio dalla più ampia diffusione dei programmi e dai servizi aggiuntivi che ne possono derivare: assistenza, formazione, consulenza, etc.

Le caratteristiche di GnuPG sono molto interessanti, e come per tutti i progetti open source, in continuo miglioramento:

Installazione e Uso GnuPG

Nella sezione seguente mostreremo come installare GnuPG (ver 1.2.1) evidenziando i comandi da eseguire e i controlli necessari per assicurarsi di avere una copia non modificata dei sorgenti. In seguito forniremo una guida ai comandi principali necessari per l'utilizzo quotidiano di GnuPG. La macchina test sui cui svolgeremo tali operazioni ha la seguente configurazione:

Installazione

Innanzitutto dobbiamo scaricare i sorgenti GnuPG dalla homepage. A questo indirizzo si troveranno anche link a siti mirror. Fatto  ciò è di fondamentale importanza verificare l’integrità dei file scaricati per sincerarsi che nessuno abbia modificato i sorgenti. I passi da seguire sono:

- calcolare il message digest MD5 del file scaricato (gnupg-x.y.z.tar.gz):

- verificare che l’output sia uguale a quello pubblicato nell’announcement list:

 A questo punto siamo sicuri dell’integrità dei file scaricati, possiamo procedere con l’installazione.

 Spostiamoci nella directory che contiene il codice sorgente e lanciamo il comando ./configure:

Con ./configure –help è possibile vedere le impostazioni disponibili per la compilazione. Se ci sono problemi di internazionalizzazione, è possibile usare le librerie gettext incluse nel sorgente, usando l'opzione --with-included-gettext, o disabilitarle usando l'opzione --disable-NLS.
E' inoltre possibile specificare il generatore di numeri casuali da utilizzare mediante l'opzione: --enable-static-rnd = [Generatore da utilizzare]

Esistono diversi tipi di generatori che variano in base al sistema operativo utilizzato come ad esempio:

• /dev/random, utilizzato nei sistemi Linux e *BSD, attivabile inserendo la stringa "linux". Questo generatore fornisce un'entropia di alta qualità catturando il rumore esterno come gli intervalli tra i vari interrupt del sistema, generati da dispositivi come interfacce di rete, dischi rigidi, tastiera, mouse, etc.
  (Anche gli utenti di Solaris, con installato il pacchetto SUNWski, possono usare /dev/random)

• Entropy Gathering Daemon (EGD), fornisce una buona scelta sui sistemi che non dispongono di buoni generatori di numeri casuali, attivabile inserendo la stringa "egd". Si tratta di un demone Perl che controlla l'attività del sistema e la trasforma in dati casuali

• Generatore Unix, se nessuno dei precedenti metodi è presente, è possibile usare tale generatore inserendo la stringa "unix". Tuttavia questo generatore è molto lento e andrebbe evitato, inoltre la qualità dei numeri casuali generati non è molto buona, quindi ne è sconsigliato l'uso per cifrare dati importanti
   

E’ ora possibile compilare il programma con il comando make, dopodichè bisogna eseguire il comando make install per copiare il programma e le pagine di manuale nella directory di installazione (che, a meno di modifiche apportate al ./configure, sarà usr/local/share/gnupg/):

È possibile eseguire GnuPG suid root, in modo che il programma giri con tutti i diritti dell'utente root e non scriva dati in locazioni di memoria teoricamente accessibili da altri. Si tenga però presente che eseguire il programma con i permessi root rende più pericolosi gli effetti di un eventuale cavallo di Troia (un cavallo di Troia che gira come utente root può danneggiare l’intero sistema). Se si sceglie, per questo motivo o per altri, di non eseguire GnuPG suid root, è possibile disabilitare il relativo messaggio di avvertimento ("gpg: Attenzione: si sta usando memoria insicura!") impostando no-secmem-warning in ~/.gnupg/options.

• è lunga
• contiene caratteri speciali (non alfanumerici)
• è molto difficile da indovinare (quindi niente nomi, date di nascita, numeri di telefono o di carta di credito, ecc.)
• contiene sostituzioni sistematiche, come o -> 0  oppure  l -> 1