Capitolo 1:Introduzione

In molte circostanze che si presentano quotidianamente, come prelievo di soldi, firme di contratti, firme di documenti legali, etc. una firma convenzionale scritta a mano viene apposta su un documento. Tale firma, come di consueto, serve per specificare la persona responsabile del documento che è stato firmato. Ciò che si tratterà in questa sezione sono gli schemi di firme, anche noti come firme digitali, i quali consentono di poter firmare documenti o messaggi memorizzati in forma elettronica. Nel prosieguo della trattazione si indicherà con 'Alice' e 'Bob' due utenti che vogliono scambiarsi dei messaggi firmati, e con 'Oscar' un utente (nemico) che cerca di falsificare una firma.

Alice vuole mandare un messaggio M a Bob e in qualche modo insieme a questo messaggio M vuole produrre una certa firma elettronica per indicare che quel messaggio è proprio il suo.
Ciò si sa facilmente farlo se la cosa funziona su supporto cartaceo, infatti se si ha un certo documento allora alla fine si appone la firma, quello che vorremmo fare è la stessa cosa se anzichè avere un supporto cartaceo si avesse un file, cioè una sequenza di bit.
La prima idea che viene in mente è che si potrebbe digitalizzare la firma di Alice e appenderla alla fine di ogni messaggio M da firmare.
Questo metodo non funziona perchè essendo la firma una sequenza di bit, chiunque può tagliare quest'ultima parte e appenderla a qualunque altro file, firmando il documento illegalmente. Questo dipende essenzialmente perchè la firma così prodotta è indipendente dal messaggio.
Le proprietà che si vorrebbe da una firma elettronica sono :

1. La firma digitale deve poter essere prodotta solo da Alice.
2. Nessun altro utente deve poter riprodurre la firma di Alice.
3. Chiunque deve poter essere in grado di verificare che la firma sia di Alice.

Quindi nasce l'esigenza di individuare schemi di firma che siano sicuri da possibili attacchi, i quali, se efficaci, potrebbero dare adito, ad un nemico, di falsificare delle firme.
Si analizzeranno due schemi di firme(DSS e RSA), ma è opportuno dapprima discutere alcune fondamentali differenze tra firme convenzionali e firme digitali.
La prima differenza concerne le modalità con cui un messaggio viene firmato: nella firma convenzionale, la firma è parte integrante del messaggio, mentre con la firma digitale essa non è attaccata fisicamente al messaggio da firmare, così l'algoritmo, che viene usato per firmare, la deve in qualche modo "legare" al messaggio. In quest'ultimo caso il messaggio firmato è costituito dalla coppia (Messaggio,Firma).
La seconda differenza riguarda la verifica della firma. Una firma convenzionale è verificata confrontandola con un'altra firma autenticata. Certamente questo non è un metodo sicuro poichè qualcuno potrebbe facilmente falsificare la firma. Le firme digitali possono essere verificate usando un algoritmo di verifica pubblicamente noto, così "ognuno" può verificare una firma digitale.
Un'altra differenza fondamentale è che una copia di un messaggio digitale firmato è identica all'originale, mentre una copia di un documento firmato può di solito essere distinta dall'originale.
Questo fa capire che uno schema di firme digitali, deve essere tale da prevenire il possibile riutilizzo di un dato documento. Per esempio, se Alice firma un messaggio digitale col quale autorizza Bob a prelevare $ 1000 dal suo conto bancario, allora desidera che tale operazione venga eseguita una sola volta, così il messaggio dovrebbe contenere delle informazioni, come la data, che ne impedirebbe il suo riutilizzo.
Dalle considerazioni fatte emerge che i due elementi fondamentali in uno schema di firma sono: un algoritmo di firma e un algoritmo di verifica. Alice può firmare un messaggio M usando un algoritmo di firma sig_k che usa alcune informazioni segrete che sono note solo a Alice. La firma risultante y = sig_k(M) può successivamente essere verificata usando l'algoritmo di verifica pubblico ver_k, il quale data una coppia (M, F) dove M è il messaggio ed F è la firma, ritorna una risposta "vero" o "falso" rispettivamente, a secondo che la firma sia autentica oppure no. Tale verifica viene realizzata grazie a delle informazioni che Alice ha memorizzato in un apposito file pubblico e, condizione fondamentale è che da queste informazioni non deve essere possibile, ovviamente, poter ricavare le informazioni segrete di Alice.
Una definizione formale di uno schema di firme è la seguente:

Uno schema di firme digitale è una quintupla (P,A,K,S,V), dove le seguenti condizioni sono soddisfatte:

• P è un insieme finito di possibili messaggi
• A è un insieme finito di possibili firme
• K, lo spazio delle chiavi, è un insieme finito di possibili chiavi
• Per ogni k  Î K c'è un algoritmo di firma sig_k Î S e un corrispondente algoritmo di verfica ver_kÎ V.
  Ogni sig_k :P->A e  ver_k :P x A->{vero,falso} sono funzioni tali che la seguente equazione è soddisfatta per ogni messaggio M Î P e per ogni firma F Î A:
  
  ver_k(M,F)= vero se F=sig_k(M) e falso     altrimenti
  

Per ogni k  Î K le funzioni sig_k e ver_k devono essere funzioni facili da calcolare  per una maggiore efficienza dello schema, mentre dovrebbe essere computazionalmente difficile per Oscar "falsificare" la firma di Alice su di un messaggio M. Cioè, dato M, solo Alice deve essere in grado di calcolare una firma F tale che ver_k(M,F)=vero.
Una schema di firme è detto incondizionatamente sicuro se, qualunque siano le risorse (tempo e hardware) di Oscar, è impossibile falsicare le firme. Uno schema di firme non può essere incondizionatamente sicuro, poichè Oscar potrebbe testare tutte le possibili firme y per un messaggio M usando l'algoritmo pubblico ver_k, fino a quando egli trova una giusta firma. Naturalmente questo tipo di attacco risulta essere computazionalmente oneroso soprattutto se l'insieme delle firme è molto grande. Ma, dato sufficiente tempo, Oscar può sempre riuscire a falsificare la firma di Alice, così il nostro scopo è di individuare schemi che siano computazionalmente sicuri.
Nelle successive sezioni si tratteranno diversi schemi di firme quali RSA e DSS.