Crittografia ellittica e il Digital Sign Algorithm (DSA)

Lo scopo di questa prima sezione e quello di illustrare alcuni dei concetti fondamentali su cui si basa la crittograa attuale. Dato che lo studio sar a indi- rizzato verso la crittograa su curve ellittiche, una delle metodologie denominate a chiave pubblica, sar a di fondamentale importanza capire la profonda dieren- za che vi e tra la crittograa a chiave pubblica, e la pi u antiquata e ineciente crittograa a chiave privata. Come prima denizione si pu o dare: Denizione 1 : la crittograa e lo studio di tecniche matematiche applicate al- la sicurezza informatica, ovvero ad applicazioni sulla riservatezza, sull’integrit a dei dati, autenticazione utenti e autenticazione dell’origine dei dati. Le funzioni crittograche sono valutate, solitamente, secondo tre caratteristiche principali: livello di sicurezza. Dicile da quanticare. Spesso si descrive a secon- da del numero di operazioni necessarie per sfondare il sistema di sicurezza, secondo il metodo pi u eciente conosciuto; ecienza. Viene quanticata a seconda del tasso di bits per secondo che la funzione pu o criptare; facilit a di implementazione. Sostanzialmente consiste nella facilit a di poter usare gli algoritmi relativi al tipo di crittograa considerato. Generalmente parlando la crittograa e basata, in particolare quella pubbli- ca, su problemi computazionali nel risolvere determinate operazioni. Parlando informalmente si dir a: Denizione 2 : un problema computazionale e facile o trattabile se pu o es- sere risolto in tempi polinomiali rispetto ai bit che compongono il numero da computare; in altre parole se esiste un algoritmo eciente in grado di risolvere il problema in tempi polinomiali. In particolare si denir a con O (f(n)) il limite massimo in tempo, per risolvere un determinato problema, o algoritmo, data la grandezza dell’input iniziale n. Quindi si pu o dare il limite generale di trattabilit a come: Denizione 3 : un algoritmo in tempi polinomiali e un algoritmo dove la fun- zione che risolve il problema, nel peggior caso necessita di un tempoO n k dove n e la grandezza in bits dell’input e k e una costante. Qualunque altro algoritmo che non pu o essere limitato da una funzione polinomiale e detto un algoritmo in tempi esponenziali. Quasi tutti gli algoritmi non polinomiali, o come appena denito, gli algoritmi esponenziali sono considerati intrattabili, e di conseguenza sicuri. 2