Sicurezza di Shannon e sicurezza computazionale

Lo scopo della crittografia è quello di rendere dei messaggi incomprensibili a persone non autorizzate a leggerli. È quindi necessario realizzare dei sistemi crittografici che sono sicuri da attacchi di eventuali avversari. In questo elaborato ci occuperemo, appunto, della sicurezza dei sistemi crittografici a chiave private. Si distinguono due tipi di sicurezza, la sicurezza di Shannon che garantisce la sicurezza del sistema di fronte ad avversari con capacità computazionale illimitata, e la sicurezza computazionale che prende in considerazione avversari con potenza di calcolo limitata. Nel primo capitolo, si analizzerà la sicurezza di Shannon e le sue proprietà. Verrà dimostrato il teorema di Shannon che dà condizioni necessarie e sufficienti per cui un sistema crittografico si possa considerare sicuro. Si daranno esempi sia di cifrari che non sono sicuri secondo Shannon, sia di cifrari che godono di tale sicurezza. In particolare verrà descritto e analizzato il cifrario di Vernam, dimostrando che è un cifrario sicuro secondo Shannon. Nel secondo capitolo, invece, la nostra attenzione si sposterà sui cifrari sicuri computazionalmente. Una volta definita la nozione di avversario efficiente si daranno gli strumenti fondamentali per la costruzione di schemi crittografici computazionalmente sicuri. Si definiranno quindi le funzioni unidirezionali, i generatori pseudo-casuali e si darà la nozione di indistinguibilità computazionale. In conclusione si descriverà un sistema crittografico e si dimostrerà che è sicuro computazionalmente.