L'algoritmo RSA: un approccio algebrico ed astratto Dott. Ing. … · 1.3. CENNI DI CRITTOGRAFIA...

L'algoritmo RSA: un approccio algebrico ed

astratto

Dott. Ing. Tiziano Binda

Summary 0.0.1. Il seguente lavoro mira ad esaminare l'algoritmo a chiave pub-blica/privata RSA. Per dimostrare la valenza teorica di tale algoritmo si presenter-anno il teorema di Eulero/Fermat e il piccolo teorema di Fermat secondo l'approcciodi Hernstein. Si illustreranno le basi della teoria dei gruppi, in particolare i gruppi�niti, le classi di resto, laterali destri e teorema di Lagrange per i gruppi �niti. Sifaranno poi osservazioni di carattere algoritmico e computazionale per giusti�carel'e�cacia pratica di questo algoritmo, e metterne in evidenza i limiti.

Indice

Capitolo 1. La crittogra�a: una introduzione storica 51.1. L'esigenza della comunicazione di informazioni riservate 51.2. Il �cifrario Cesare� 61.3. Cenni di crittogra�a simmetrica 71.3.1. Codici monoalfabetici: crittogra�a da settimana enigministica 71.4. La seconda guerra mondiale e la macchina �Enigma� 81.4.1. Codici polialfabetici: crittogra�a �da prete� 91.5. L'informatica e la crittogra�a 91.5.1. Macchine dell'informazione 91.5.2. La chiave, forza di un protocollo simmetrico e il problema

computazionale 91.5.3. La chiave, debolezza di un protocollo simmetrico 101.6. La crittogra�a Asimmetrica 101.6.1. L'RSA, la chimera della crittogra�a 111.7. Chiave ( o chiavi?) e canali sicuri 111.7.1. Il problema computazionale 12

Capitolo 2. I gruppi dell'algebra astratta. Le basi 132.1. De�nizione di gruppo 132.2. Esempi 142.3. Lemmi 152.3.1. Ordine di gruppi 162.3.2. Gruppi ciclici 162.4. Sottogruppi 172.4.1. relazione di congruenza per sottogruppi 172.4.2. Laterali (destri) 182.4.3. Il teorema di Lagrange per i gruppi �niti 192.5. Teorema di Eulero 202.5.1. Sintesi della dimostrazione 222.6. Piccolo teorema di Fermat 222.7. Considerazioni numeriche 222.7.1. Piccolo Teorema di Fermat 222.7.2. Teorema Cinese del Resto 23

Capitolo 3. L'RSA - perché funziona 253.1. Due Primi Grandi 253.2. Chiave Pubblica. Chiave Privata. 253.3. L'algoritmo 263.4. Codi�ca e Decodi�ca: un esempio 273.5. Applicazioni 293.5.1. Comunicazione segreta 293.5.2. Non ripudio 293.5.3. Firma digitale 293.6. Limiti Computazionali 29

3

4 INDICE

Appendice 31Esempio 31Secondo esempio 31Sorgenti Ansi-C 34

CAPITOLO 1

La crittogra�a: una introduzione storica

Una delle prime notizie documentate dell'uso della crittogra�a, come la inten-diamo oggi, è storicamente attribuita a Giulio Cesare. Egli, come evidenziato dallaVita dei Cesari di Svetonio, usava giá una sorta di cifratura per inviare i suoidispacci ai suoi luogotenenti. Questo accadeva quasi 21 secoli fa.

Per migliaia di anni, re, regine e generali hanno avuto bisognodi comunicazioni e�cienti per governare i loro Paesi e comandarei loro eserciti. Nel contempo, essi compresero quali conseguenzeavrebbe avuto la caduta dei loro messaggi in mani ostili: infor-mazioni preziose sarebbero state a disposizione delle nazioni rivalie degli eserciti nemici. Fu il pericolo dell'intercettazione da partedegli avvessari a promuovere lo sviluppo di codici e cifre, tecnichedi alterazione del messaggio destinate a renderlo comprensibile so-lo alle persone autorizzate. �Simon Singh, �Codici & Segreti� -Introduzione

1.1. L'esigenza della comunicazione di informazioni riservate

Nell'era dell'informazione non c'è molto da dire sull'esigenza di comunicare inmodo sicuro, e segreto, fra due parti. Oggi siamo costantemente collegati con glialtri e spesso abbiamo bisogno di fare comunicazioni in modo riservato, garantendol'autenticitá del contenuto, del mittente e anche del destinatario. L'esempio piùemblematico è quello dell'home banking, ovvero della gestione diretta attraversointernet del proprio conto corrente.

Un cliente ha la necessitá di autenticarsi, ovvero di fornire credenziali che di-mostrino il più inequivocabilmente possibile che egli è chi asserisce di essere. Peresempio la mia banca raggiunge questo scopo attraverso una terna di informazioni:Nome Utente, Password, Data Chiave. È chiaro che chiunque avesse a disposizionequeste tre informazioni sarebbe a tutti gli e�etti identi�cato come titolare di quelconto corrente, e come tale gli sarebbe garantito libero accesso a tutte le funzionidispositive, per esempio fare un boni�co di tutto il denaro su un altro conto corrente,magari estero.

Più in piccolo possiamo pensare a una tessera bancomat. Per poter accedereai servizi bancomat una persona deve fornire, oltre alla tessera, anche un numeroche identi�chi il titolare.

È forse meno ovvio che il problema dell'autenticazione può scaturirsi anche alcontrario, ovvero anche il destinatario spesso ha bisogno di identi�carsi in manierainequivocabile. Immaginiamo di accedere a uno sportello bancomat tru�aldino1:dentro il bancomat c'è un tizio che prende la vostra tessera, legge il vostro PIN(Personal Identi�er Number) e li immette in un secondo, e vero, bancomat. Voiavete chiesto 100 Euro e lui ne preleva 200, tenendosi 100 Euro come commissione.Benchè bu�o questo tipo di attacco è teoricamente e praticamente possibile e in

1C'è un �lm (Killer per caso) in cui Ezio Greggio compie esattamente questa manovra.

5

6 1. LA CRITTOGRAFIA: UNA INTRODUZIONE STORICA

nomenclatura va sotto il nome di Man in the middle (e trova nell'hijacking la suamiglior realizzazione), ovvero furto di credenziali.

Figura 1.1.1

Party �Man in the Middle�

Per tornare all'esempio dell'homebanking se un sito potesse spacciarsi per il sitodella nostra banca potrebbe, una volta convinti noi stessi di essere il sito originale,rubarci le credenziali di accesso e divertirsi a piacimento con i nostri dati.

Questo tipo di attacco è possibile anche se tecnicamente complicato da metterein piedi. Questo spiega perché quando ci colleghiamo per la prima volta al sitodella banca, ci appaia una �nestra che ci chiede se accettare oppure no un certocerti�cato di autenticitá del sito stesso.

Allo stesso modo, le informazioni che inviamo al sito devono essere protette.Esse devono essere disponibili a noi, alla banca e a nessun altro. Se qualcuno rius-cisse a monitorare la connessione e da questa attivitá estrapolare le informazionidi autenticazione saremmo punto e a capo. Inoltre potrebbe anche curiosare infor-mazioni sensibili, come per esempio i saldi dei nostri conti correnti e le operazioniche eseguiamo. Quindi l'intero tra�co di informazioni deve essere in qualche modoprotetto fra mittente e destinatario da occhi indiscreti.

1.2. Il �cifrario Cesare�

Agli albori, le informazioni sensibili erano associate più all'attivitá militaree politica che a quella �nanziaria. Il primo uso ampamente documentato di unsistema crittogra�co risale a Gaio Giulio Cesare. Egli, a partire dalle campagne inGallia, prese l'abitudine di comunicare i suoi dispacci scrivendoli su pergamena ea�dandoli poi a galoppini, una sorta di servizio postale. Dato però che si trovavain territorio nemico, e che anche i galli conoscevano il latino, si presentava l'ovvianecessitá di impedire che queste informazioni potessero cadere in mano nemica. Sei galli, catturando o corrompendo un galoppino, avessero potuto sapere in anticipotattiche, entitá, posizioni delle truppe e ordini dello stesso Cesare ne avrebberotratto un ovvio vantaggio tattico e strategico.

Per ovviare a questo problema, e anche per certi�care che l'autore del dispacciofosse egli stesso, Cesare prese a scrivere i suoi dispacci in modo diverso: primali scriveva in latino, poi li trascriveva sulla pergamena da a�dare al galoppinoapplicando un trucco. Anzichè scrivere per esempio �A�, egli scriveva �D�. Al postodi �B� scriveva �E� e così via. Chiaramete al posto di �Z� metteva �C� e al postodi �Y� metteva �B�. Ogni lettera veniva, quindi, scambiata con quella che stavatre posizioni più avanti. Inoltre per ovviare al problema delle ultime tre letteredell'alfabeto egli stabilì che dopo �Z� si dovesse ricominciare con �A� e così via,chiudendo quindi il protocollo 2di cifratura.

2Un protocollo non è altro che un insieme di regole da seguire per rispettare una certaprocedura. In questo caso le regole per cifrare e decifrare il messaggio.

1.3. CENNI DI CRITTOGRAFIA SIMMETRICA 7

Figura 1.2.1. Gaio Giulio Cesare

Allo stesso modo, invertendo l'associazione (ovvero spostando indietro di treposizioni nell'alfabeto con l'ovvia precauzione di far precedere �Z� ad �A�) si potevatornare al messaggio originale, ovvero decifrare il messaggio.

Questo tipo di protocollo a noi può far sorridere, e forse far venire il dubbio chei galli non fossero questi maestri di sagacia. Va però detto che questo fu il primocaso di cifratura della storia, e che, almeno secondo alcuni storiogra�, da quellavolpe che Cesare era, faceva accompagnare i dispacci cifrati da altri in chiaro nondel tutto a�dabili. Così i galli si tenevano le informazioni in chiaro senza sospettareche invece le altre in versione criptica avessero una qualche valenza.

1.3. Cenni di crittogra�a simmetrica

Il cifrario Cesare, come viene chiamato, è un esempio di crittogra�a simmetrica.Come è facile notare il sistema di cifratura/decifratura si inverte con facilitá. Seindichiamo con CC(3) l'algoritmo che sostituisce a ogni lettera quella che sta treposizioni più avanti secondo il protocollo discusso sopra, è ovvio che CC(-3) eseguirála decifratura. Se preferiamo possiamo creare un algoritmo DCC(3)=CC(-3) cheesegue la decifratura. La simmetria di questi codici sta nel fatto che l'algoritmo dicifratura è in sostanza lo stesso che si usa in decifratura: basta una banale inversionedel parametro di cifratura.

1.3.1. Codici monoalfabetici: crittogra�a da settimana enigministi-ca. Ogni tipo di codice che sostituisce �a numero uguale carattere ugualè' vienechiamato monoalfabetico. Questo a signi�care che c'è sempre e solo un'associ-azione fra un determinato carattere nel testo in chiaro3 e un determinato caratteredel testo cifrato. Quindi, nell'esempio del cifrario Cesare, ogni �A� in chiaro vieneriscritta come �D� nel cifrato. È evidente che quindi vale anche il viceversa, ovveroogni �D� nel cifrato dovrá essere ritrasformata in �A� nel testo decifrato.

Per sua stessa costruzione, il cifrario Cesare può essere esteso �no a fornire,usando l'alfabeto inglese, 26 diversi modi di crittare uno stesso messaggio. È la-palissiano che CC(0)=CC(26) e che applicare CC(0) a un testo produrrá nient'altroche il testo in chiaro stesso. Ci sono quindi 26 diversi codici Cesare costruibili conquesto protocollo, dei quali uno banale.

3Si dice testo in chiaro il testo con il messaggio non codi�cato


L'algoritmo di cifratura/decifratura rimane identico per tutti e 25 i cifrari ce-sare. Quello che cambia è l'entitá dello spostamento in avanti. In tutti i sistemi dicifratura esistono questi due elementi: l'algoritmo e la chiave, ovvero il parametro,che fa lavorare in qualche modo l'algoritmo. Anche se si conosce l'algoritmo, lamancanza della chiave rende comunque di�coltoso risalire al messaggio in chiaro.Questo si ottiene, ovviamente, avendo un'ampia scelta di chiavi ovvero avendo uninsieme di chiavi grande. Così da garantire che anche provandole tutte, il temponecessario per trovare quella giusta sia mediamente improponobile.

Per esempio per violare un cifrario cesare non ci vuole molta fatica. Una voltache si sa che un messaggio è stato cifrato usando un cifrario Cesare basta provarlitutti e 25 per trovare quello giusto ed avere quindi la chiave di decifrazione. Diparticolare nota il fatto che non è a�atto necessario trasformare tutto il testo inquesta fase, ma solo poche parole e veri�care se esse hanno senso. Appena trovatauna possibile corrispondenza si decifra tutto il testo e �cest voilá tout� il gioco èfatto.

Va da sè che spesso fa comodo aggiungere caratteri al nostro alfabeto: segnidi punteggiatura, accenti e gli stessi spazi bianchi sono elementi importanti chedevono essere considerati. Quindi si può costruire un alfabeto esteso che contengatutti i simboli che noi vogliamo nascondere e associare a ogni simbolo un altro nelmedesimo alfabeto. Così facendo, e dando il sistema di trascrizione fra un alfabetoe l'altro, si può eseguire la cifratura e la decifratura del messaggio. Siccome si usaun singolo alfabeto, o meglio una singola corrispondenza biunivoca fra l'alfabeto inchiaro e quello cifrato, questi codici vengono anche detti monoalfabetici.

Per dare qualche numero, se si dispone di un alfabeto di 10 caratteri, quanticodici monoalfabetici, anche banali, si possono costruire?

Al primo carattere si può associare uno qualsiasi degli altri 10. Al secondo unodegli altri 9 rimasti (uno è andato �persò' dato che è giá stato associato al primocarattere). Al terzo uno degli altri 8 rimasti e così via. Dato la ovvia indipendenzadella scelta del secondo carattere rispetto alla scelta del primo, stante che non sipossono scegliere lo stesso carattere, per il resto non ci sono vincoli: il numerototale di alfabeti diversi è 1 ∗ 2 ∗ 3 ∗ ... ∗ 9 ∗ 10 = 10! = 3628800. Ora se passassimoa un alfabeto a 26 caratteri, come ad esempio l'inglese, avremmo 26! > 4 ∗ 1026 cheè un numero decisamente enorme.

Questi numeri potrebbero far credere che rompere un codice di questo tiposia quindi un'impresa titanica. Eppure, come nel racconto �Gli omini danzantì' diSherlock Holmes, è possibile, e spesso senza nemmeno avere a disposizione grandipotenze di calcolo.

Conoscendo informazioni del messaggio, come per esempio la lingua in cui èscritto, il tema di cui tratta, lo stile dell'autore, è possibile fare delle osservazionidi carattere statistico. Per esempio in una certa lingua come l'inglese, il caratterepiù spesso ripetuto è la vocale �è'. Quindi se disponiamo di un testo cifrato di unacerta lunghezza, possiamo ipotizzare che il carattere che occorre più spesso sia quelloassociato al carattere �è'. Andando avanti in questo modo, studiando le parole chesi ottengono e scartando le ovvie associazioni che portano a �non sensè', si possonoindovinare, sempre più in fretta, le altre associazioni fra lettere dell'alfabeto inchiaro e lettere dell'alfabeto cifrato. E proprio così che questa generazione di codicidivenne rapidamente obsoleta e debole, nel senso che si poteva facilmente risalire altesto in chiaro anche senza la chiave.

1.4. La seconda guerra mondiale e la macchina �Enigma�

L'idea successiva fu quella di non basarsi su un unico alfabeto. In e�eti se nepossono usare per esempio due: uno per i caratteri in posizione dispari e uno per

1.5. L'INFORMATICA E LA CRITTOGRAFIA 9

quelli nelle posizioni pari. Oppure ne potrei usare 10: uno per il primo carattere, unsecondo per il secondo e così via �no al decimo per poi ripartire dal primo alfabeto.

In questo modo anche il numero degli alfabeti diventa un'incognita e non dipoco conto.

1.4.1. Codici polialfabetici: crittogra�a �da prete�. Storicamente, unodei primi a proporre un sistema di questo tipo per cifrare testi fu un abate tedesco:Trithemius, nato nel 1472. Per la loro natura non monoalfabetica, questi cod-ici si dicono polialfabetici, e per lungo tempo i crittogra� si sentirono frustratinell'impossibilitá di violarli.

Su questo principio venne costruita la macchina enigma, strumento di crit-togra�a usato dai tedeschi durante la seconda guerra mondiale. Convinti di avereuno strumento inviolabile, i tedeschi usarano pesantemente la cifratura e ci si �-darono ciecamente. Eppure uno dei padri dell'informatica, Alan Turing, avevascoperto delle falle in questo sistema, e mise il suo genio a disposizione del propriopaese, la Gran Bretagna, per violare engima. Usando l'analisi statistica, alcunedebolezze dovute ai fattori umani e ad alcune imperfezioni tecniche, egli risucì, ingenere, ad aver la meglio su Enigma. E per quando le sue brillanti intuizioni nonbastavano, aveva costruito delle �bombè' (veri e propri calcolatori) che provavanobrutalmente tutte le possibilitá.

1.5. L'informatica e la crittogra�a

Come si vede il problema di violare la crittogra�a era ormai diventato un prob-lema di matematica, ingegneria elettrica e sociale, ovvero quello di sfruttare glierrori e la pigrizia umana, e un problema di informatica, nel senso di provare il piùrapidamente possibile una quantitá di chiavi nel tentativo di isolare quella giusta.

1.5.1. Macchine dell'informazione. I calcolatori, proprio per la loro natu-ra, sono gli stumenti ideali per implementare sistemi crittogra�ci e strumenti dirottura di sistemi crittogra�ci. L'aumento esponenziale dei messaggi scambiatidurante l'ultima guerra mondiale ha creato un problema di sovrabbonadanza diinformazione che andava immagazzinata e processata. Si è stimato che l'esercitonazista abbia trasmesso ben oltre un milione di dispacci nell'ultima guerra. Lecapacitá di immagazzinare, processare e fare ricerche è diventata critica, oltre aquella di poter eseguire operazioni aritmetico logico massivamente su enormi molidi dati.

1.5.2. La chiave, forza di un protocollo simmetrico e il problemacomputazionale. Ora che si è chiarito che la forza di un protocollo sta nellachiave vediamo di chiarire meglio questo punto.

Se le chiavi disponibili fossero poche, basterebbe provarle tutte e analizzare isingoli testi decifrati proposti per trovare poi quello giusto. Quindi va da sè chedobbiamo avere un vasto insieme di chiavi nel quale prendere la nostra, cosicchèla probabilitá che scegliendone a caso una si prenda quella giusta sia piccola. Peresempio un insieme di un miliardo di chiavi può sembrare adeguato, ma se si pensacon quale velocitá oggi un computer di media potenza può provare queste combi-nazioni, ci si rende conto che non sono molte. Per amor di chiacchiera si immaginiche un computer possa provare un milione di chiavi al secondo, cifra tutto som-mato ragionevole, allora gli basterebbero 1000 secondi, meno di venti minuti, peresaurire tutto lo spazio delle chiavi. Una sicurezza probabilmente insu�ciente perla maggior parte delle possibili applicazioni. Si tenga poi conto che grandi soci-etá e organizzazioni governative possono disporre di ben altre risorse informatiche.Si conclude che per avere delle garanzie da parte del nostro protocollo dobbiamoavere uno spazio delle chiavi molto più grande. Si ricordi che in media è su�ciente


provare la metá di tutte le chiavi per trovare quella giusta. Inoltre è verosimile cheun computer abbastanza veloce possa provare 1000 miliardi di chiavi in un giorno(pari a 10 milioni al secondo circa), che in un anno sono quasi 500 mila miliardi dichiavi.

Si conclude quindi che per avere una chiave che mediamente possa resisterealmeno un anno, bisognerebbe avere uno spazio di almeno un milione di miliardi dichiavi, sempre che i computer non aumentino di prestazioni nel frattempo.

1.5.3. La chiave, debolezza di un protocollo simmetrico. In tutto questodiscorso c'è un unico grosso neo: la chiave. Essa deve essere disponibile sia al mit-tente che al destinatario. Deve quindi essere in qualche modo distribuita fra di essiin modo sicuro. Va da sè che un modo di distribuire dati in modo sicuro è proprioquello che ci manca, e quindi è proprio questo l'anello debole di questa catena.Inoltre ogni chiave è soggetta a un fenomeno di usura (invecchiamento o aging ininglese). Più viene adoperata piu lascia tracce di sè. Queste tracce furono utilizzateproprio durante la seconda guerra mondiale a Bletchey Park per trovare sistemi de-cisamente più rapidi per identi�care la chiave che i nazisti usavano quel giorno.Per dirla il più semplicemente possibile, l'unico modo davvero sicuro di crittare unmessaggio è quello di usare una chiave grande quanto il messaggio stesso, e di nonriutilizzare la chiave mai più. Ogni volta che la si riutilizza si possono usare tecnichee processi statistici per ridurre progressivamente lo spazio delle chiavi. Il risultatoè quello di riportare il problema entro valori e tempi accettabili, e fu quello che gliinglesi realizzarono, sia attraverso le bombe di Turnig che Colossus.

Inoltre la distribuzione delle chiavi porta a un problema logistico e organizza-tivo enorme e estremamente dispendioso, dato che esse devono essere consegnatemassivamente e in modo sicuro. Rubare la chiave equivale a rompere il codice atutti gli e�etti.

1.6. La crittogra�a Asimmetrica

In quest'ottica sono entrati in scena i sistemi asimettrici. Essi usano due chi-avi, diverse, una per cifrare e una per decifrare. Quello che deve essere chiaro èche esiste sempre un unico algoritmo di cifratura che chiameremo C. La chiavedi cifratura la chiameremo CK (Cipher Key) e quella di decifratura DK(decipherKey). Chiameremo T il testo in chiaro da cifrare, CT (Ciphred Text) il testo cifratoe DT (Dechipred Text) il testo decifrato. Dopo questa mole di de�nizioni possiamoquindi descrivere l'algoritmo asimmetrico:

Algorithm 1.6.1. CT=C(T,CK). CT è ottenuto dall'algoritmo C applicato altesto T secondo la chiave CK.

Viene inviato in modo non sicuro CT al nostro destinatario. Egli calcola quindiDT.

DT=C(CT,DK), applicando l'algoritmo C su CT con la chiave DK. Si deveavere che DT=T e il protocollo si chiude.

Il truco sta nel fatto che il destinatario crea le due chiavi, CK e DK. Si tieneDK per sè, nascosta, e invia, anche in chiaro, CK al mittente. Il mittente applical'algoritmo C su T con CK e invia CT al destinatario.

Inserire qui un'immagine delle fasi dell'algoritmo

Ora, per ritrasformare CT in DT=T si ha bisogno di DK, che non è stata trasmessae quindi sta al sicuro dal destinatario. Il fatto di usare due chiavi distinte, di cuiuna nascosta, garantisce la sicurezza. O almeno sempre che sia di�cile ricostruireDK da C e CK. Se così non fosse il gioco non starebbe in piedi.

L'idea può essere schematizzata così: Io ho una cassa alla quale applico unmio lucchetto. Mi tengo la chiave e invio la cassa al destinatario. Egli appone un

1.7. CHIAVE ( O CHIAVI?) E CANALI SICURI 11

secondo lucchetto, sempre sullo stesso anello, si tiene la chiave e mi rinvia la cassa.Io ricevo la cassa, levo il mio lucchetto con la mia chiave e la rinvio al destinatarioche la riceve chiusa con il suo solo lucchetto. Che quindi può levare senza problemi.La cassa ha sempre viaggiato chiusa a chiave, e quindi in modo sicuro.4

1.6.1. L'RSA, la chimera della crittogra�a. Di�e e Hellman teorizzaronoper primi questo protocollo nel 1975. Bello in teoria, ma in pratica irrealizzabileper via della procedura �a due lucchettì' che si sposa male con le operazioni chein genere possiamo fare. Infatti quando noi facciamo una sequenza di azioni, pertornare indietro dobbiamo fare le azioni opposte ma in ordine invertito. Immaginatedi girarvi a destra e fare 5 passi. poi di girarvi a sinistra e farne altri 5. Pertornare al punto di partenza dovrei fare 5 passi indietro, girarmi a destra, farealtri 5 passi indietro poi girarmi a sinistra. Se invertissi l'ordine delle due rotazionimi troverei in un posto diverso. La ricerca di una funzione con queste proprietáproseguì per due anni senza nessun successo �no al 1977 quando Rives, Shamir eAdlemann scoprirono come usare i moduli e le operazioni su di essi per implementareil protocollo simmetrico.

Questo protocollo sará analizzato nel dettaglio nel capitolo 3, dopo aver appre-so i rudimenti della teoria dei gruppi, irrinunciabile base teorica a giusti�cazionedell'e�cacia del protocollo.

1.7. Chiave ( o chiavi?) e canali sicuri

Per poter cifrare e decifrare si ha quindi bisogno di una informazione comune,la chiave. Essa deve essere la stessa da entrambe le parti, e si pone quindi l'ovvioproblema della distribuzione sicura di questa chiave. Se essa cadesse in mani ne-miche tutto il sistema sarebbe compromesso. Allo stesso modo se avessi un canalesicuro per trasferire la chiave, perché non usare lo stesso sistema per trasferire tuttoil messaggio? È il classico cane che si morde la coda.

In quest'ottica sono entrati in scena i sistemi asimettrici. Essi usano due chiavi,diverse, una per cifrare e una per decifrare. Quello che poi deve essere chiaro èche esiste sempre un unico algoritmo di cifratura che chiameremo C. La chiavedi cifratura la chiameremo CK (Cipher Key) e quella di decifratura DK(decipherKey). Chiameremo T il testo in chiaro da cifrare, CT (Ciphred Text) il testo cifratoe DT (Dechipred Text) il testo decifrato. Dopo questa mole di de�nizioni possiamoquindi descrivere l'algoritmo asimmetrico:

Algorithm 1.7.1. CT=C(T,CK). DT è ottenuto dall'algoritmo C applicato altesto T secondo la chiave CK.

Viene inviato in modo non sicuro DT al nostro destinatario. Egli calcola quindiDT

DT=C(CT,DK), applicando l'algoritmo C su CT con la chiave DK. Si deveavere che DT=T e il protocollo si chiude.

Il truco sta nel fatto che il destinatario crea le due chiavi, CK e DK. Si tieneDK per sè, nascosta, e invia, anche in chiaro, CK al mittente. Il mittente applical'algoritmo C su T con CK e invia CT al destinatario.

Ora, per ritrasformare CT in DT=T si ha bisogno di DK, che non è statatrasmessa e quindi sta al sicuro dal destinatario. Il fatto di usare due chiavi distinte,di cui una nascosta, garantisce la sicurezza. O almeno sempre che sia di�cilericostruire DK da C e CK. Se così non fosse il gioco non starebbe in piedi.

L'idea può essere schematizzata così: Io ho una cassa alla quale applico unmio lucchetto. Mi tengo la chiave e invio la cassa al destinatario. Egli appone un

4Questo bellissimo esempio è preso �as is� direttamente da �Codici & segretì'


secondo lucchetto, sempre sullo stesso anello, si tiene la chiave e mi rinvia la cassa.Io ricevo la cassa, levo il mio lucchetto con la mia chiave e la rinvio al destinatarioche la riceve chiusa con il suo solo lucchetto. Che quindi può levare senza problemi.La cassa ha sempre viaggiato chiusa a chiave, e quindi in modo sicuro.

1.7.1. Il problema computazionale. Al giorno d'oggi è solo un problema diforza bruta, ovvero provare tutte le possibili combinazioni della chiave �no a trovarequella giusta. I computer moderni hanno capacitá di calcolo inimmagginabili solopochi decenni di anni fa. I codici che usiamo non sono intrinsecamente sicuri, masolo probabilmente5 sicuri. Ovvero oggi ci vorrebbero anni o decine di anni perprovare tutte le possibili chiavi. Questo perché non esistono algoritmi e�cienti,ovvero rapidi, per risolvere certi problemi, come per esempio trovare i fattori di unnumero intero grande, dell'ordine delle centinaia di cifre decimali. La sicurezza stasolo in questo fatto. Quindi, al crescere della potenza di calcolo dei computer, ose si trovasse un procedimento che permettesse di arrivare molto rapidamente allasoluzione, il nostro codice diverrebbe violabile.

L'RSA si basa sul fatto che per trovare i fattori di un numero grande ci vuoleun tempo proporzionale alla radice del numero stesso, ovvero per trovare i fattoridi un numero che vale circa un milione ci vogliono, salvo casi triviali, un migliaio dioperazioni. Se il numero ha 10 cifre, ci vogliono un numero con 5 cifre di operazioni(circa 100.000). Per un numero che avesse, per dire, 18 cifre, ci vorrebbero circa unmiliardo di operazioni. Per un numero con 100 cifre ci vorrebbero circa 10 alla 50operazioni, numero decisamente enorme.

5Ovvero si ha una probabilitá grande che non si possa rompere il codice in un tempo breve.Si noti che la probabilitá di non rompere il codice è funzione decrescente del tempo a disposizione.

CAPITOLO 2

I gruppi dell'algebra astratta. Le basi

2.1. De�nizione di gruppo

Qui e nel prosieguo faremo riferimento a un insieme G, �nito o no che sia. Essoè composto da vari elementi. Fra questi elementi de�niamo una certa operazionebinaria, ovvero un'applicazione che presi come argomenti due elementi dell'insiemeG, restituisca un elemento ancora di G. Chiameremo questa operazione �+�1, anchese non vorremo nè dovremmo confonderla con la somma ordinaria.

∀a, b ∈ G,∃c ∈ G : c = a+ b

Nel linguaggio delle applicazioni, o funzioni, dovremmo scrivere c = +(a, b)dove la funzione �+� ha per argomenti i valori rappresentati dalle variabili a e b erestituisce il valore c. Va da sè' che il valore di c è unico, ovvero ogni volta chefacciamo a+ b otteniamo sempre e solo un certo c 2.

La propietá summonenzionata viene detta di chiusura. Ovvero, computandoattraverso �+� una qualsiasi coppia di elementi di G, si ottiene sempre un elementodi G; non si può �scapparè' da G attraverso �+�.

È forse meno ovvio che non è detto che a + b = b + a. Questo è vero perl'usuale somma, ma se intendiamo una funzione con due argomenti, diventa piùspontaneo immaginare che lo scambio degli argomenti possa portare in generalea un valore diverso3. Per esempio4 si pensi all'elevamento a potenza, dove a puòessere l'esponente e b la base o viceversa. Ovviamente lo scambio della base conl'esponente in genere porta ad un risultato diverso.

Più semplicemente basta considerare la sottrazione dove a− b = b− a è vera see solo se a = b.

Una seconda importante proprietá di questa operazione è l'associativitá:

∀a, b, c ∈ G : (a+ b) + c = a+ (b+ c)dove il signi�cato delle parentesi è quello naturale di regolare la precedenza nell'ap-plicazione dell'operazione. Vediamo come diventerebbe in forma di funzione:5

∀a, b, c ∈ G : +( +(a, b) , c) = +(a, +(b, c) )ovvero anche eseguendo l'ordine delle operazioni diversamente, il risultato noncambia.

Ogni insieme dotato di operazione che gode delle proprietá enunciate sopra,chiusura ed associativitá, è detto semigruppo.

1In realtá, almeno per gruppi astratti, potrebbe essere più sagace usare l'operazione �-� cheanche nell'aritmetica ordinaria non è commutativa. Solo si perderebbe la capacitá di de�nire ilmonoide (N,+) .

2Va da sè che se esistesse un d diverso da c tale che d = +(a, b) = c , per la ransitivitádell'uguaglianza d = c contro l'ipotesti che siano distinti.

3Per esempio i generale f(a, b) 6= f(b, a)4L'esempio è macchinoso, la sottrazione si presterebbe decisamente meglio!!!5Da notare che siccome +() produce come risultato un elemento di G allora è perfettamente

lecito che +() possa essere considerato come un argomento di un'altra operazione +().

13

14 2. I GRUPPI DELL'ALGEBRA ASTRATTA. LE BASI

Se inoltre in G, semigruppo, esiste un elemento, che chiameremo e, tale che

∀a ∈ G, a+ e = e+ a = a

chiameremo e elemento neutro di �+� in G, e diremo che (G,+) è un monoide.Se poi

∀a ∈ G,∃b ∈ G : a+ b = b+ a = e

diremo che b è elemento inverso di a e in generale lo indicheremo con a−1. Se ognielemento di G è invertibile, ovvero ammette elemento inverso, diremo che (G,+) hala struttura di un gruppo.

Riassumendo:

(1) Un insieme G dotato di un'operazione, detta �+�, chiusa e associativa sidirá che è un (una struttura di) semigruppo.

(2) Se (G,+) è semigruppo ed ha elemento neutro, diremo che (G,+) ha lastruttura di un monoide.

(3) Se (G,+) è un monoide e ogni elemento di G ammette inverso, diremo che(G,+) ha la struttura di un gruppo.

(4) Se (G,+) è un gruppo e l'operazione �+� è commutativa, diremo che (G,+)ha la struttura di un gruppo commutativo (o abeliano).

Il numero di elementi dell'insieme G, spesso indicato come supporto della strutturaalgebrica in esame, porta poi ad un'altra distinzione: gruppi �niti e gruppi non�niti.

2.2. Esempi

Example 2.2.1. L'usuale operazione di somma e l'insieme dei numeri naturaliN. Consideriamo quindi la struttura (N,+).

La somma di due numeri naturali è sempre un numero naturale. Come bensappiamo �n dalle elementari, l'ordine in cui si sommano gli addendi non cambia ilrisultato �nale, e quindi la somma ordinaria è associativa. Il numero 0 è il nostroelemento neutro, dato che aggiunto a qualsiasi numero non cambia il numero stesso.

Per l'inverso abbiamo qualche problema: il numero da sommare a 4 per farlodiventare 0 è -4, e non è un naturale.

Quindi (N,+) è un monoide, ma non un gruppo.

Se considerassimo l'insieme dei numeri interi (ovvero Z) allora avremmo sì ungruppo. Gruppo fra l'altro commutativo e in�nito.

Example 2.2.2. Dell'orologio. Immaginiamo di avere un orologio da polsoanalogico, ovvero con le lancette. Sul quadrante compaiono i numeri dall'1 al 12.Se ora sono le ore 4, fra 5 ore saranno le ore 9. Se passano altre 4 ore saranno le ore1. La somma delle ore su un orologio è quindi un'operazione chiusa e associativa,come nell'esempio precedente. L'elemento neutro è il valore 12 (ovvero un girocompleto delle lancette). Vediamo se riusciamo a trovare gli elementi inversi.

L'inverso di un'ora è il numero di ore da sommargli per arrivare alle ore 12.Quindi l'inverso di 1 è 11, di 2 è 10, di 3 è 9 e così via. La cosa più bu�a di questogruppo è che l'inverso di 12 è 12 (che in realtá non è per nulla strano, essendo 12l'elemento neutro allora deve essere inverso di sè stesso come vedremo nel prossimoparagrafo). L'operazione, come sopra, è pure commutativa.

Abbiamo quindi che l'insieme G = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12} con la som-ma sul quadrante dell'orologio è un gruppo abeliano. Ed è �nito, come si vede.

Fin qui abbiamo visto solo gruppi, o monoidi, commutativi, cosa che potrebbeportarci a credere che la commutativitá sia un qualcosa di scontato. Un bell'esempiodi gruppi non commutativi potrebbero essere il gruppo delle permutazioni, il gruppodelle matrici quadrate con la moltiplicazione. Un altro bell'esempio più facile da

2.3. LEMMI 15

immaginare è quello degli itinerari: immaginatevi a New York con tutte le stradeche si incrociano ad angolo retto. Immaginate un itinerario del tipo �svolta a destrae poi a sinistrá'. Immaginiamo di invertire l'ordine delle svolte e come si vede daldisegno il punto che si raggiunge non è esattamente lo stesso.

Figura 2.2.1. Itinerari a New York

2.3. Lemmi

Per lemma intendiamo una sorta di teorema, ovvero una veritá dimostrata conun procedimento logico deduttivo a partire dai nostri assiomi. La lieve di�erenzacon un teorema è che il lemma viene enunciato e poi dimostrato, all'opposto deiteoremi. Spesso però si tratta solo di quisquiglie e di�erenze marginali. In realtáquello che indichiamo come teoremi sono spesso delle veritá logicamente dedottema di interesse primario. I lemmi invece sono, spesso, usati a supporto delle di-mostrazioni stesse e in qualche misura più banali, fors'anche ovvi, dei teoremi. Ciònonostante qui ne elencheremo e dimostreremo alcuni dei più fondamentali nellateoria dei gruppi.

Lemma 2.3.1. L'elemento neutro di un gruppo è unico

Dimostrazione. Consideriamo (G,+). Per de�nizione, e è un elemento neu-tro, ma non è stato assunto che sia anche l'unico. Immaginiamo quindi che ne esistaalmeno un secondo che chiameremo f distinto da e. Essendo entrambi elementineutri possiamo scrivere che e + f = f e anche e + f = e. Per quanto detto nelparagrafo 1, questo porta a concludere e = f contro l'ipotesi iniziale. Avendo ot-tenuto un assurdo signi�ca che l'ipotesi è falsa e che quindi non esiste un secondoelemento con le stesse proprietá di e che quindi è unico in (G,+).

Riassumendo

∃e, f : e 6= f : ∀a ∈ G =⇒ e+ a = a+ e = f + a = a+ f = a =⇒ e = e+ f = f

�

Quanto appena detto è vero per un generico gruppo. Ovvero vale per tutti igruppi.

Lemma 2.3.2. Leggi di cancellazione. Dato un gruppo (G,+) e tre elementi,diciamoli a, x, y appartenenti a G, se a + x = a + y allora x = y, e viceversa, sex+ a = y + a =⇒ x = y.

Dimostrazione. Nel gruppo (G,+) esiste l'elemento neutro e. Ovviamenteesiste anche un elemento b inverso di a, ovvero tale che b + a = e. Quindi x =e + x = (b + a) + x = b + (a + x) = b + (a + y) = (b + a) + y = e + y = y, checonclude la dimostrazione. �

Ovvero si può cancellare a dalle equazioni. Attenzione però. L'elemento ugualesi può cancellare solo se si presenta sullo stesso lato dell'operazione, oppure sel'operazione è commutativa.

Si noti che in questa dimostrazione abbiamo usato l'ovvio assioma cose logica-mente equivalenti (uguali) possono essere interscambiate senza alterare il valore diun'espressione.

Lemma 2.3.3. Unicitá dell'inverso

∃!b ∈ G : b+ a = a+ b = e


Dimostrazione. Come prima neghiamo la tesi e vediamo dove ci conduce,ovvero dato a ∈ G esistano b, c ∈ G entrambi inversi di a e tali che b 6= c. Per leproprietá dell'elemento inverso, possiamo scrivere e = a + b ed e = a + c da cuia+ b = a+ c. Ma per il lemma precedente siamo quindi obbligati a concludere cheb = c contro l'ipotesi iniziale, che quindi è falsa. Quod Erat Demostrandum, l'unicaalternativa è che non esistano due elementi distinti inversi di uno stesso elemento,ovvero che l'elemento inverso sia quindi unico. �

Lemma 2.3.4. L'inverso dell'inverso è l'elemento stesso

∀a ∈ G : (a−1)−1 = a

Dimostrazione. Chiariamo cosa vogliamo dimostrare: ∀a ∈ G : (a−1)−1 = a. De�niamo allora b = a−1 e calcoliamone l'elemento inverso. b−1 : b−1 + b = eè equivalente a scrivere b−1 + a−1 = e . Ora aggiungiamo a a destra di entrambele espressioni ottenendo b−1 + a−1 + a = e + a ⇐⇒ b−1 + e = a ⇐⇒ b−1 = a .Riscrivendo b = a−1 si ottiene (a−1)−1 = a. �

Lemma 2.3.5. (a+ b)−1 = b−1 + a−1.

Dimostrazione. Basta provare che b−1 + a−1 è l'inverso di a + b. Vediamosubito che

(b−1+a−1)+(a+b) = b−1+(a−1+(a+b)) = b−1+(a−1+a)+b = b−1+e+b = b−1+b = e

e si ha concluso. �

D'ora in avanti parleremo sempre di gruppi, e per non appesantire la notazionescriveremo spesso G intendo con esso la struttura (G,+) che è gruppo. L'abuso dilinguaggio sará comunque sempre accompagnato dalle parole, ed evitato quando ilcontesto non sia immediatamente esplicito.

2.3.1. Ordine di gruppi. Un caso in cui si può �confonderè' G con (G,+) èquando parliamo dell'ordine di un gruppo. Esso non è altro che la cardinalitá6 delsupporto del gruppo G. Va da sè che in generale ha senso parlare della cardinalitá diun insieme quando essa è �nita, e così anche per l'ordine di un gruppo. Arriviamoquindi alla seguente de�nizione

Definition. L'ordine di un gruppo �nito (G,+), che indicheremo semplice-mente con o(G) invece di o( (G,+) ), è la cardinalitá dell'insieme G a supporto delgruppo.

2.3.2. Gruppi ciclici. Di tutti i gruppi possibili ce n'è una categoria partico-lare che va sotto il nome di gruppo ciclico. Questi gruppi particolari, �niti, hannoalmeno un elemento che è in grado, a furia di essere computato da solo, di generaretutti gli altri. L'esempio più semplice è quello del gruppo delle ore visto prima.Se ci si pensa le ore 1, per somme successive, possono generare tutte le altre ore.Non bisogna però credere che questa proprietá sia naturale del numero 1. Infatti ilnumero 1 non è un generatore del gruppo (Z,+). Come si veri�ca facilmente, ogninumero positivo, cioè naturale, si può scomporre come somma �nita di unitá. Manon c'è modo di ottenere un numero negativo come somma di numeri positivi.

Per i gruppi �niti invece le cose non vanno esattamente così.

Problem 2.3.6. Trovare tutti i generatori del gruppo delle ore dell'orologio.

Enunciamo quindi un classico teorema di teoria dei numeri:

Theorem 2.3.7. Un gruppo �nito con p elementi dove p è un numero primoallora è un gruppo ciclico.

6Ricordiamo che per cardinalitá intendiamo il numero di elementi, se �nito, di un insieme

2.4. SOTTOGRUPPI 17

Da notare che il viceversa non è vero. Dato un elemento si può costruire ungruppo di ordine qualsiasi che ammette quell'elemento come generatore.

Inoltre si può facilmente costruire un gruppo di ordine 4 che non sia ciclico. Sipensi al gruppo G che abbia come supporto l'insieme di 4 elementi G = {e, a, b, c, }dove e è l'elemento neutro. Posto che a+a = b+b = c+c = e e posto, per esempio,a+ b = c; a+ c = b; b+ c = a è il gruppo, commutativo, cercato.

La dimostrazione al momento si omette. Sará poi vista come un corollariodell'importantissimo teorema di Lagarange per i gruppi �niti.

2.4. Sottogruppi

Definition. Un sottogruppo di un gruppo, i.e. (G,+), è un sottoinsieme di Gche è comunque gruppo rispetto alla medesima operazione + de�nitia in (G,+).

Sia quindi A ⊂ G tale che A sia sottogruppo di G. Scriveremo d'ora in poi cheA ∈ sg(G,+) dove per sg(G,+) intendiamo l'insieme di tutti i possibili sottogruppidi (G,+).

2.4.1. relazione di congruenza per sottogruppi. In questo paragrafo in-dicheremo sempre con H ∈ sg( G,+) un sottogruppo di (G,+).

Si prenda un elemento a ∈ G e si cerchino gli elementi b ∈ G che soddis�no laproprietá che a + b−1 ∈ H. L'insieme, d'ora in avanti lo chiameremo classe, deglielementi b ∈ G che rispettano la condizione di pocanzi gode di alcune interessantiproprietá:

Definition. La classe di congruenza di a ∈ G modulo H viene de�nita comel'insieme degli elementi b ∈ G tali che a+b−1 ∈ H e scriveremo che a ≡ b mod H ={b ∈ G : a+ b−1 ∈ H}.

La classe di congruenza è quindi un sottoinsieme di G. Elenchiamo alcune ovvieproprietá:

(1) a ≡ a mod H. Per assurdo, come potrebbe essere il contrario?(2) Se a ≡ b mod H ⇐⇒ b ≡ a mod H.(3) Se a ≡ b mod H e b ≡ c mod H allora a ≡ c mod H.(4) Se a 6= b mod H ⇐⇒ b 6= a mod H.

Dalle prime tre proprietá di sopra, la cui dimostrazione viene lasciata come utileesercizio al lettore con l'unica indicazione di ricordare che H è sottogruppo e quindigruppo a sua volta, portano a concludere che:

Lemma 2.4.1. La relazione di congruenza modulo un sottogruppo in (G,+) èuna relazione di equivalenza, ovvero una relazione ri�essiva, simmetrica e transiti-va.

La quarta proprietá non fa altro che ricordarci che classi di equivalenza diversesono disgiunte, ovvero non hanno in comune nemmeno un elemento.

Example. Classi di resto: si consideri il gruppo (Z,+) il gruppo additivo deinumeri interi. Si prenda il sottoinsieme dei multipli di 5, ovveroH = {...,−15,−10,−5, 0, 5, 10, ...} ={x ∈ Z : ∃n ∈ Z : x = 5 ∗ n} . H è ovviamente un sottogruppo rispetto alla som-ma. Si consideri il numero 23. La classe di resto di 23 è composta dai numeri{23, 28, 33, ..., 3,−2,−7, ...}, come si deduce immediatamente dal fatto che 23 ≡ xmod H =⇒ 23 − x ∈ H. Ovvero che 23-x deve essere multiplo di 5. Quindi a23 si deve sottrarre un numero tale che il risultato sia un multiplo di 5 e questo èpossibile se e solo se 23 e x danno lo stesso resto nella divisione per 5.

Si osservi che una classe di congruenza non è necessariamente un gruppo, datoche in genere non vi appartiene l'elemento neutro.


2.4.2. Laterali (destri). D'ora innanzi passeremo alla più classica e tradizionalenotazione moltiplicativa. Ovvero l'operazione che prima chimavamo genericamente�+� ora la denoteremo genericamente �*�. Tranne negli esempi, ovviamente.

Definition. Si chiama classe laterale destra di un sottogruppo H di un grup-po (G, ∗), il sottoinsieme degli elementi di G ottenuti applicando l'operazione delgruppo a tutti gli elementi di H con un dato elemento di a ∈ G. Detto in simboli

a ∈ G,H ∗ a = {z ∈ G : z = h ∗ a, h ∈ H}

Un esempio tipico è il gruppo G = (Z,+) e il suo sottogruppo dei multipli diun certo numero, per esempio 5. È ovvio che somme e di�erenze di multipli di 5danno ancora multipli di 5. Ora si prenda un qualsiasi elemento x ∈ Z e si consideril'insieme H+x, dove H è il sottoinsieme dei multipli di 5, ai quali si somma il valoredi x. Esso è una classe laterale dei multipli di 5. Si prenda in considerazione il valorex = 2, allora la classeH+2 = {5n+2 : n ∈ Z} = {...,−3, 2, 7, 12, ...}. La prima cosada notare è che H+2 = H+7 = H−3 = H+2+5n, n ∈ Z. Le possibili, e distinte,classi laterali sono solo 5 e in sostanza sono H = H+0;H+1;H+2;H+3;H+4 checoincidono con le classi di resto modulo 5. Inoltre si nota che ogni classe laterale puòessere messa in corrispondenza biunivoca, con lo stesso procedimento, con l'insiemea supporto del sottogruppo H, ovvero

H | h1 h2 ... hn ...l l l l

H + a | h1 + a h2 + a ... hn + a ...

Ogni classe 7 Ha contiene tanti elementi quanti sono gli elementi di H. Perconvincersene basta veri�care che se così non fosse dovrebbero esistere almeno dueelementi di H, distinti, che moltiplicati con a darebbero lo stesso risultato, ovvero

∃h1 6= h2 : h1a = h2a

Tenuto conto che però nel gruppo G ogni elemento è invertibile, allora esiste dicerto l'inverso di a che sará chiamato a−1 8 . Si Computi a−1 con l'equazione disopra e si ottiene

h1aa−1 = h2aa

−1 =⇒ h1 = h2

contro l'ipotesi h1 6= h2! L'assurdo porta a concludere che Ha non contiene menoelementi di H, e certamente nemmeno di più, e quindi Ha e H hanno la stessacardinalitá.

∀a ∈ G, o(Ha) = o(H)

Qui c'è da rimarcare l'abuso di linguaggio nel parlare di o(Ha). A rigore nonc'è nessuna garanzia che Ha sia un sottogruppo9, e quindi non si può parlare diordine. Comunque ci si permetterá di confondere l'ordine di un sottogruppo con lacardinalitá di un insieme mantenendo, per comoditá, lo stesso simbolismo.

In maniera analoga si può procedere induttivamente come mostrato nello schemi-no in cui a ogni elemento di H si associava un unico elemento in Ha.

Si considerino ora due laterali destri di H, Ha e Hb, dove a, b ∈ G. Essendosottoinsiemi di G possono aversi solo tre alternative:

7D'ora innanzi, per non appesantire la notazione, scriveremo Ha in luogo di H∗a e passeremoalla notazione moltiplicativa.

8L'inverso di a è l'elemento a−1 tale che a ∗ a−1 = a−1 ∗ a = 1, con 1 elemento neutro delgruppo. Inoltre basta ricordarsi che devono valere le leggi di cancellazione.

9Anzi, si può facilmente dimostrare che Ha è sottogruppo se e solo se a ∈ H!

2.4. SOTTOGRUPPI 19

(1) Ha = Hb se entrambi i laterali sono composti da tutti e soli gli stessielementi

(2) Ha ∩Hb = ∅ se i laterali non hanno in comune nemmeno un elemento(3) Ha ∩ Hb = F 6= ∅ se i laterali hanno in comune solo qualche elemento

(quelli nell'insieme F, ma non tutti!).

Ora si desidera dimostrare che il terzo caso non è possibile. Allora, ancora perassurdo, si immagini di trovarsi in questo caso. Si prenda f ∈ F . Come tale èf ∈ Ha e f ∈ Hb ovvero devono esistere due elementi di h1, h2 ∈ H tali che

h1a = f = h2b

Da questa relazione, e ricordando che H è sottogruppo, allora in H esiste h−11

elemento inverso di h1. Applicando h−11 all'ultima equazione otteniamo

h−11 h1a = h−1

1 h2b =⇒ a = h−11 h2b

h−11 h2 è il prodotto di due elementi di H e quindi, sempre perché H è sottogruppo,

rappresenta un elemento di H, ovvero ∃h ∈ H : h = h−11 h2 . Questo porta a

concludere che a = hb ∈ Hb. Ma quindi ora consideriamo l'insieme Ha = {x : x =ha, h ∈ H}. Ogni elemento in Ha si può riscrivere come ha = hhb ∈ Hb. E siconclude che quindi ogni elemento di Ha è un elemento di Hb. Potendo scrivereb = h−1a è vero anche il viceversa e si ha concluso che se due laterali hanno incomune anche un solo elemento, allora li hanno in comune tutti.

Inoltre va chiarito �n da subito che se a 6= b e Ha = Hb allora non è a�attogarantito che ha = hb, che anzi è falso per le leggi di cancellazione. Ha = Hbsigni�ca che i due insiemi sono composti dagli stessi elementi, ma essi possonoessere generati in maniera diversa. Il procedimento di sopra mostra come generaregli elementi di Ha da quelli di Hb e viceversa.

Queste osservazioni permettono di a�ermare il seguente

Lemma 2.4.2. Due classi laterali di un sottogruppo o coincidono o sono dis-giunte.

Ora ci sono tutti gli strumenti per dimostrare il teorema di Lagrange.Si osservi che in realtá potremmo dire di più sui laterali destri. Per esempio che

la relazione di appartenenza a uno stesso laterale è una relazione di equivalenza.Anzi, che appartenere allo stesso laterale signi�ca che i due elementi sono congruentimodulo H. Se infatti a ∈ Hb possiamo moltiplicare entrambi i termini per b−1

ottenendo ab−1 ∈ H =⇒ a ≡ b mod H.

2.4.3. Il teorema di Lagrange per i gruppi �niti.

Theorem 2.4.3. (di Lagrange per gruppi �niti) Dato un gruppo �nito (G, ∗),in cui sia de�nita l'operazione *, e un sottogruppo H di G, allora l'ordine di Hdivide l'ordine di G.

o(H)|o(G)

Dimostrazione. Si basa su come si possono �raccoglierè'10 gli elementi diG. Da G si raccolgono tutti gli elementi di H, che sono o(H). Poi si prende unaltro elemento di G detto g. Considerando Hg, essa o coincide con H o non necondivide nemmeno un elemento, per quanto dimostrato poc'anzi. Nel secondocaso si avranno 2o(H) elementi distinti. Proseguendo con tutti i possibili laterali siotterrá uno schema simile al seguente

10Raggruppare è forse più azzeccata, ma si rischia di diventare ripetitivi


Tabella 1. Schema 1

h1 h2 ... hn−1 hnh1g h2g ... hn−1g hng...

......

......

Come si vede, su ogni riga ci sono n elementi, tanti quanti l'ordine di H. Ogniriga corrisponde a un distinto laterale destro, ovvero se gli elementi di un certolaterale sono giá stati presi in considerazione non si ripeteranno. Ogni distintolaterale aggiunge sempre o(H) elementi. Alla �ne si avranno enumerati tutti glielementi di G su k righe, ciascuna di n = o(H) elementi.

C'è solo da convincersi che vengono enumerati tutti gli elementi di G. Si ricordiche H è sottogruppo e quindi l'elemento neutro ne fa parte. Considerando tutti ipossibili elementi in Hg al variare di g ∈ G viene naturale veri�care che g ∈ Hg eche quindi l'unione di tutti i laterali destri contiene almeno tutti gli elementi di G.Chiamato iG(H) il numero di distinti laterali destri di H in G, e allora

o(G) = iG(H)o(H)

�

Essendo l'ordine di G multiplo intero dell'ordine di H la conclusione è chel'ordine di un sottogruppo divide l'ordine del gruppo relativo o(H)|o(G). E per lageneralitá con cui abbiamo scelto H , che è un qualsiasi sottogruppo, si concludeche

L'ordine di un qualsiasi sottogruppo di un gruppo �nito è undivisore dell'ordine del gruppo di partenza.

2.5. Teorema di Eulero

Theorem 2.5.1. Sia a un numero intero e n un numero naturale primi fraloro. Allora aφ(n) ≡ 1 mod n.

Per il resto del paragrafo n sará sempre un numero naurale. Per comprendereappieno questo teorema bisogna speci�care cosa si intende per mod n e per lafunzione φ() .

Definition. Due numeri interi sono congruenti modulo n quando la lorodi�erenza è multipla, intera, del numero n.

Interessante notare che in genere la de�nizione data, specie in informatica, nonè esattamente questa ma �Due numeri sono congruenti modulo n se danno lo stessoresto nella divisione per n�. Basta però qualche esempio per convincersi che lede�nizioni indicano la stessa proprietá.

Si considerino i numeri 8 e 13 modulo 5. Come si nota, il resto di 8 diviso 5 è3 che è lo stesso di 13 mod 5. Infatti 13− 8 = 5 che è multiplo di 5.

Usando l'algoritmo della divisione ogni numero intero a può essere scritto come

a = q ∗ n+ r

dove r < n ovviamente è il resto della divisione intera, mentre q il quoziente.Per tornare all'esempio precedente, notiamo che 13 − 8 = 5 è multiplo di 5, e

scriveremo 8 ≡ 13 mod 5.Allo stesso modo 102 e 1577 sono congruenti modulo 5, dato che 1577− 102 =

1475 che è multiplo di 5. Come si nota un qualnque numero intero è congruente

2.5. TEOREMA DI EULERO 21

modulo n a uno e un solo numero minore di n. Quindi quando si parla di con-gruenza modulo n ci si può limitare a considerare solo gli elementi minori di n, echiaramente maggiori o uguali di 0. Si può anche dimostrare che questa relazioneè di equivalenza.

Example. Si prenda il numero 24. Elencando tutti i naturali minori di 24 siottiene il seguente insieme:

I24 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23}

In questo insieme si cerchino solo quei numeri che non hanno divisori comuni con24, ovvero che sono coprimi con esso. Si scomponga in fattori primi 24: 24 = 8∗3 =23 ∗ 3. Quindi 24 ha come divisori primi i numeri 2 e 3.

Si genera quindi l'insieme J che contiene tutti i numeri di I che però non hannonessun divisore comune, eccetto il numero 1, con 24. Allora J24 = {1, 5, 7, 11, 13, 17, 19, 23}.Come si nota la cardinalitá di J24 è 8. La cardinalitá dell'insieme Jx è proprio lanostra funzione φ().

#Jx = φ(x)

Questa de�nizione, certamente non molto rigorosa, ha però il vantaggio di essereimmediatamente operativa. Si può provare a fare un altro esempio, ovvero calcolarela φ(35), esempio non casualmente scelto come prodotto di due numeri primi.11

Gli elementi di Jn rispetto alla moltiplicazione modulo n formano un gruppo,come visto precedentemente. Essi sono esattamente φ(n). Ora ricordando che presoun elemento di un guppo �nito, chiamiamolo a ∈ G, si può costruire il sottogruppociclico generato da a come

(a) = {g ∈ G : g = an, n ∈ N}

ovvero di tutti gli elementi di G ottenbili come �potenzè' di a, esso è un sottogruppo,e quindi il suo ordine deve dividere l'ordine di G. Ovvero o(a)|o(G) e quindi esisteun naturale k ∈ N tale che o(G) = k o(a). Si può allora concludere che

ao(G) = ak o(a) = (ao(a))k

Nell'ultimo passaggio si è sfruttato il fatto che i k o(a) possono essere computati inqualsiasi modo, ovvero li si può raggruppare in k righe da o(a) elementi a ciascuna.

k righe

ao(a) =o(a)︷︸︸︷

a ∗ a ∗ ... ∗ a

ao(a) =o(a)︷︸︸︷

a ∗ a ∗ ... ∗ a...

...

ao(a) =o(a)︷︸︸︷

a ∗ a ∗ ... ∗ a

Ma per la de�nizione di ordine di un elemento12, ao(a) = 1 e moltiplicando 1 k voltecon sè stesso si riottiene sempre 1 e quindi

(ao(a))k = 1k = 1

11E l'insieme da calcolare sará composta, guarda un pò!, da 24 elementi, ovvero 6*4. E alloradi prova anche con φ(6) e con φ(10) così che i neuroni siano invitati a cercare la correlazione giusta.

12Questa dimostrazione è stata fatta in una lezione rpecedente, anche se non è male ricordareil fatto che gruppo e sottogruppo sono �niti, con tutte le consguenze che ne derivano.


2.5.1. Sintesi della dimostrazione. Ora, la classe di resto modulo n haesattamente, come visto prima, φ(n) elementi, che quindi è il suo ordine. Nelleipotesi del teorema di Eulero si a�erma che i numeri a e n sono coprimi fra loro,e quindi a ≡ an mod n è congruente a un elemento di Jn. Passando ai moduli, isottogruppi ciclici (a) e (an) sono uguali, (a) ≡ (an), e quindi sottogruppi di Jn.Per il teoema (2.4.3) di Lagrange allora o(a)|o(Jn) = φ(n), ovvero φ(n) = k ∗ o(a).Abbiamo che φ(n) deve essere multiplo intero dell'ordine del sottogruppo ciclicogenerato dall'elemento a. Quindi

aφ(n) ≡ ak∗o(a) mod n ≡ (ao(a))k mod n ≡ 1k mod n ≡ 1 mod n

Che è la tesi voluta.

2.6. Piccolo teorema di Fermat

Nella stessa �loso�a del teorema precedente, si ha il seguente teorema:

Theorem 2.6.1. Dati due numeri interi, diciamoli a e p, con l'unico vincoloche p sia un numero primo, allora

ap ≡ a mod p

Si distinguono due casi fondamentali

(1) a è multiplo di p, ovvero ∃n ∈ N : a = n ∗ p. Va da sè che anche ap èmultiplo di p. Quindi, per de�nizione dell'operazione di modulo, a ≡ 0mod p e anche ap ≡ 0 mod p che conclude a ≡ ap mod p.

(2) a non è multiplo di p, ovvero @n ∈ N : a = n ∗ p anzi, esiste un numero0 < r < p tale che a = n ∗ p + r. In questo caso allora a e p non hannodivisori comuni (p ha come unico divisore non banale p stesso che nondivide a) e quindi, applicando in questo caso il teorema (2.5.1) di Eulerosi ottiene che aφ(p) ≡ 1 mod p. Maφ(p) = p − 1, infatti tutti i numeriinteri più piccoli di p non hanno altri divisori comuni con p se non ilnumero 1! Questo ci porta a scrivere ap−1 ≡ 1 mod p. Moltiplicandoentrambi i membri per a si ottiene

ap ≡ a mod p

che conclude la dimostrazione.

In questa dimostrazione abbiamo anche dimostrato che φ(p) = p − 1. In mododiverso si poteva notare che tutti i numeri maggiori di zero e minori di p nonpossono avere divisori comuni con p: p è primo. Quindi sono tutti coprimi con pe sono p-1. Jp contiene p-1 elementi e quindi φ(p) = p − 1 ⇔ p ∈ P Quod eratdemostrandum.

2.7. Considerazioni numeriche

Per poter gettare le basi dell'RSA si devono applicare i teoremi appena visti inchiave numerica, ovvero sui numeri interi.

2.7.1. Piccolo Teorema di Fermat. Un modo equivalente di formulare ilPTF è il seguente

Theorem 2.7.1. Dato un numero primo p e un secondo numero tale che a ≡ 1mod (p− 1) allora per qualsiasi intero m si ha ma ≡ m mod p.

Si vuole arrivare a questo teorema partendo da quello che giá si dispone. Allorasi noti che da questo deriva subito il PTF nella formulazione della sezione precedentegrazie all'osservazione che p = 1 + (p− 1) ≡ 1 mod (p− 1) = 1 mod φ(p).

Armati da questo fatto, si passa a notare che se a ≡ 1 mod (p − 1) alloraa = 1 + k(p− 1) . Ma a questo punto la dimostrazione è analoga a quella fatta per

2.7. CONSIDERAZIONI NUMERICHE 23

(2.6.1) , considerando il caso in cui p divide m oppure no e scomodando il teoremadi Eulero nel secondo caso.

Lo studente provi per esercizio ad adattare la dimostrazione del PTF (2.6.1) aquesta variante, giocando con le proprietá banali delle potenze e delle clasi di resto.

2.7.2. Teorema Cinese del Resto. L'ultimo mattone è il seguente corollariodel più generale teorema Cinese del Resto.

Theorem 2.7.2. Dati due numeri primi distinti detti p, q e un terzo numero ztale che:

(1) z ≡ 1 mod p(2) z ≡ 1 mod q

Allora z ≡ 1 mod (pq).

Example. Siano p = 7 e q = 11 . Si cerchi z con le proprieá richieste dallepremesse del teorema. Ovviamente 1 andrebbe benissimo. Si provino in sequenza:

1, 8, 15, 22, 29, 36, 43, 50, 57, 64, 71, 78, 85, ..., 7k + 1, ...1, 12, 23, 34, 45, 56, 67, 78, 89, ..., 11j + 1, ...I numeri che rispettano le ipotesi sono gli z del tipo z = 7k + 1 = 11j + 1. Si

consideri quindi z − 1 = 7k = 11j . L'ovvia considerazione è che z − 1 è multiplosia di 11 che di 7. Stando la primalitá quindi è anche multiplo di 77.

7k = 11j

Impone che

(1) 7 divida j che quindi ne è multiplo intero: j = 7 ∗ j(2) 11 divida k che quindi ne è multiplo intero: k = 11 ∗ k

Da cui segue che 7k = 7 ∗ 11 ∗ k = 11j = 11 ∗ 7 ∗ j che conclude che k = j ma cosapiù importante che z − 1 è multiplo di 77.

Dall'ultima relazione segue che z − 1 = 77k =⇒ z ≡ 1 mod 77.La generalizzazione di questo teorema al caso in cui p e q siano generici è

esattamente analoga all'esempio appena visto e si invita lo studente a cercarla.Altro fatto interessante, e che sará utile, è il viceversa:

Lemma 2.7.3. Dato n = pq con p, q numeri primi, e un numero x tale chex ≡ 1 mod pq allora x ≡ 1 mod p e x ≡ 1 mod q.

La dimostrazione si basa sempre su argomenti di carattere numerico ed è facileda intuire dopo quanto detto sopra.

L'ultimo fatto che rimane è una generalizzazione del Teorema (2.7.2) :

Theorem 2.7.4. Dati due numeri primi distinti detti p, q e un terzo numero ztale che:

(1) z ≡ m mod p(2) z ≡ m mod q

Allora z ≡ m mod (pq).

CAPITOLO 3

L'RSA - perché funziona

3.1. Due Primi Grandi

L'RSA si basa su due numeri primi grandi. Essi devono essere grandi pergarantire la sicurezza, solo di tipo probabilistico sia chiaro, che non si possa rompereil codice. È ovvio che nell'esempio che andremo ad illustrare si useranno numeripiccoli anche se non c'è alcun problema ad usare numeri anche di 9 cifre se si usaun linguaggio di programmazione di capacitá superiori. Per esempio il linguaggioJava ha nelle sue librerie la classe BigInt che permette di gestire numeri interi nonnegativi di grandezza arbitraria (in teoria �no al milione di cifre), anche se connumeri di tale dimensione i tempi di calcolo, ovviamente, si allungano.

Si prendano quindi due numeri primi, p e q.

p = 61q = 53

Si consideri ora n = p ∗ q = 61 ∗ 53 = 3233 e φ(n) = (p− 1) ∗ (q− 1) = 60 ∗ 52 =3120.1

Ora si sceglie un numero e che deve essere coprimo con φ(n). Questo test diprimalitá si può eseguire con l'algoritmo di Euclide che ha un complessitá quadraticanel numero delle cifre dei numeri coinvolti.

Per esempio si scelga e = 77, con l'unica limitazione che sia coprimo e minoredi n.

Come si vede dalla �gura 3.1.1, l'inverso di e è il numero, chiamiamolo d,1013. Ovvero e ∗ d = 1 mod φ(n). Sará a partire da questi tre numeri e, d, n cherealizzeremo l'algoritmo di cifratura.

3.2. Chiave Pubblica. Chiave Privata.

Dai tre numeri e, d, n si producono le due chiavi: (e, n) detta chiave pubblica;(d, n) detta chiave privata. Come è naturale la prima sará disponibile a chiunque,mentre la seconda sará custodita gelosamente dal proprietario. I numeri primi p, qsi possono tranquillamente distruggere, dato che non hanno più nessun ruolo nellacifratura.

Per poter realizzare appieno il protocollo c'è però la necessitá di un depositocentrale delle chiavi pubbliche. Al giorno d'oggi esistono siti web che si occu-pano proprio di questi aspetti, mettendo a disposizione le risorse necessarie per lacreazione di questi database di chiavi pubbliche. Esattamente come un elenco del

1Se un numero n è prodotto di due primi, p e q, i numeri più piccoli di n che non sono coprimicon n sono quelli che sono multipli di p o di q. Ora, n = pq; quindi {p, 2p, ..., kp, ..., (q − 1)p}sono tutti e soli i numeri minori di n che hanno in comune il fattore p con n stesso. Essi sonochiaramente q − 1, dato che pq = n. E fra essi non ce n'è nessuno che è anche multiplo di q, ilprimo sarebbe pq che però è escluso. Analogamente si vede che ci sono p − 1 numeri multipli diq e minori di n che non sono multipli di p. I numeri minori di n sono ovviamente n-1. Di essice ne sono p− 1 + q − 1 = p+ q − 2 che non sono coprimi con n. In totale si hanno quindi che inumeri minori di n e coprimi con esso sono: n− 1− (p+ q− 2) = n− p− q+ 1 = pq− p− q+ 1 =

p(q − 1)− (q − 1) = (p− 1)(q − 1) che conclude la dimostrazione.

25

26 3. L'RSA - PERCHÉ FUNZIONA

Figure 3.1.1. Euclide esteso

telefono, ognuno può cercare al suo interno il numero, che in questo caso sará lachiave pubblica, del nostro destinatario ed usarla per preparare, cifrare, il messag-gio che vogliamo mandargli. Come si vedrá nella prossima sezione, per decifrare ilmessaggio serve la chiave privata, che è appannaggio solo del destinatario, il qualesará quindi l'unico a poter ricavare il testo in chiaro.

L'idea è quella di un lucchetto con due toppe, ciascuna associata a una chiavediversa. E ciascuna con una funzione diversa: una permette di chiudere la serratura,l'altra di aprirla. Sul web c'è una copia della chiave che permette la chiusura dellucchetto, e quindi disponibile a tutti. La chiave per aprire è invece conservata solodal destinatario.

Altro esempio è quello di una serratura e due chiavi distinte: una gira in sensoorario per chiudere e l'altra, distinta, può girare in senso antirorario per aprire.

3.3. L'algoritmo

Il mittente dispone, in qualche modo, della chiave pubblica del destinatario.Alla peggio essa può essere anche trasmessa direttamente, e in chiaro, dallo stessodestinatario: non c'è nessun motivo perché essa debba essere tenuta segreta, equindi trasmessa in modo sicuro. Questa chiave è la coppia (e, n) (e sta per en-cryption key).

Quello che ora deve essere chiaro è che un messaggio può essere diviso in blocchi,e che ad ogni blocco può essere associato, con una relazione biunivoca, un numerointero. Questo deriva facilmente dal fatto che in informatica ogni informazione è difatto trasformata in una stringa di bit, che in quanto tale può essere interpretatacome un numero, intero, in base binaria2.

Ci sará quindi una preelaborazione del testo per dividerlo in blocchi di dimen-sione compatibile con l'operazione di cifratura. Nella seguente operazione aritmet-ica si chiamerá m il blocco di messaggio da cifrare e c il risultato della sua cifratura:

c = me mod n

2In genere questo fatto va anche sotto il nome di processo di aritmetizzazione di Gï¾÷del.

3.4. CODIFICA E DECODIFICA: UN ESEMPIO 27

Il valore c è uno degli in�niti esemplari possibili che mod n sono fra loroequivalenti, e in genere si prende il valore fra 0 e n che è spesso il rappresentantedella classe di equivalenza che è il risultato dell'operazione di cifratura. Da qui inpoi avremo sempre a che fare con l'aritmetica mod n e sulla classe di equivalenzadegli elementi come appena de�nito.

L'operazione di decifratura, partendo dalla chiave privata (che ricordiamo è lacoppia (d, n)) e il ciphertext, è

t = cd mod n

Si noti che

t = (

c︷︸︸︷me mod n)d mod n = (me)d mod n = med mod n

Per come li abbiamo costruiti, ed = 1 mod (φ(n)) = 1 mod ((p − 1)(q − 1)).Ora si deve dimostrare che dall'ultima relazione deriva che ed = 1 mod (p − 1) eanalogamente che ed = 1 mod (q − 1). La dimostrazione è quasi banale e ritengoche sia un utile esercizio da proporre agli studenti, cosï¾÷ da scomodare qualchecapacitá di lavorare con i numeri interi.

Quanto detto porta a veri�care le ipotesi del PTF 2.7.1 che permette allora diconcludere che med = m mod p e med = m mod q. Ora sfruttando il teorema2.7.4 si può concludere che med = m mod n e ricordando che me = c che t = cd

mod n = med mod n = m mod n che ci assicura di essere tornati al punto dipartenza, ovvero la decodi�ca del messaggio originale.

3.4. Codi�ca e Decodi�ca: un esempio

Si prendano due numeri primi per esempio 17 e 19. Si useranno numeri piccoliper permettere di poter gestire questi calcoli con un foglio elettronico e utilizzarecaratteri a 8 bit come elementi di base dell'algoritmo.

n = p ∗ q = 323 con φ(n) = 288.Si scelga per esempio e = 5. Attraverso l'algoritmo di Euclide esteso si calcola il

valore di d che deve essere tale che e∗d = 1 mod φ(n). Nel nostro caso l'algoritmoarriva a computare il numero 115, che però è congruo −1 mod 288. Si computiquindi il numero 288 − 115 = 173 che, come si dimostra facilmente, è congruo 1mod 288.

Abbiamo quindi la chiave pubblica (5, 323) e la chiave privata (173, 323).Un modo semplice per procedere alla cifratura è quello di dividere il messaggio

in blocchi e di eseguire quindi la cifratura di ogni blocco secondo la procedura

c = me mod n

Va da sè che la dimensione di ogni blocco non può eccedere il valore di n,altrimenti perderemmo la biunivocitá dell'algoritmo. I possibili valori di ogniblocco, una volta trasformato in numero naturale, devono essere interni all'insieme{0, .., n − 1}. Tutti i valori più grandi non potrebbero essere decodi�cati perchécongrui, modulo n, a un valore in {0, .., n− 1}.

La parte più di�cile di questo algoritmo rimane valutare me. Infatti per valorianche non elevati di e il valore ottenuto rapidamente eccede il valore massimorappresentabile dalle variabili intere in genere in uso nei calcolatori. Non rimaneche notare il seguente fatto:

me mod n = (m ∗ (me−1 mod n) mod n

e sfruttare l'ovvia relazione di ricorrenza. Pagando il calcolo del modulo a ognipassaggio si riesce a tenere sotto controllo il valore calcolato cosï¾÷ che non diventimai troppo grande. Solo che con questo algoritmo bisogna procedere ad eseguire e


Figure 3.4.1. Euclide Esteso

moltiplicazioni e moduli. Un modo decisamente più sagace è quello di riscrivere ilnumero e nelle sue cifre binarie:

e = enen−1...e1e0 =n∑i=0

2iei

Questo fatto permette di calcolare

(3.4.1) me = mPn

i=0 2iei =n∏i=0

m2iei

Si noti che

m2i+1= m2i∗2 = (m2i

)2

fatto che permette di passare da un elemento a quello successivo nella produttoria(3.4.1) con un'unica operazione (modulo n). Le cifre binarie signi�cative del numeroe sono chiaramente inferiori a log2 e + 1 3. Nella produttoria, sempre modulo n, itermini diversi da uno sono tutti e soli quelli delle cifre binarie di e che sono 1, eanche qui sono al più log2 e + 1. Cosï¾÷ in un tempo proporzionale al numero dicifre binarie del numero e si può cifrare il nostro messaggio.

Dopo questa dissertazione sarebbe interessante chiedere agli studenti perché,in genere, valori popolari di e sono nella forma 2k + 1 (come per esempio 65537 e257 per citare i due più famosi sul web [?]).

Fatte queste considerazioni si hanno a disposizione tutti gli strumenti percostruire l'RSA. Si può usare un foglio elettronico, non sarebbe di�cile costru-irne uno con openCalc, oppure un qualsiasi linguaggio di programmazione dal C, alPascal o Java o il php. In appendice ci sono per esempio due programmi in ANSI-C.

Detti programmi possono essere usati per decodi�care la sequenza di numeriproposta come esercizio in appendice nella tabella 1.

3Qui e non è il numero di Nepero ma l'elemento della chiave pubblica (e, n).

3.6. LIMITI COMPUTAZIONALI 29

3.5. Applicazioni

In questa sezione si immaginerá che due partner (che chiameremo come si usain nomenclatura Alice (A) e Bob (B) ) vogliano comunicare in modo sicuro usandol'RSA. Si diranno EA e DA le chiavi pubblica e privata di Alice; EB e DB le chiavi,pubblica e privata, di Bob.

3.5.1. Comunicazione segreta. Alice decide di mandare un messaggio seg-reto a Bob per �ssare il loro prossimo appuntamento. Prende la chiave pubblica diBob EB e il proprio messaggio m. Applica l'algoritmo RSA a (EB ,m) ottenendoil crittogramma c che manda in chiaro, anche se si spera non via sms!, a Bob. Perpoter risalire al messaggio originale ci vuole la chiave segreta di Bob DB che soloBob dovrebbe avere, garantendo quindi la riservatezza della corispondenza.

3.5.2. Non ripudio. Se vi è mai capitato di ricevere un biglietto, una mail oun messaggio da qualcuno che si spacciava per un altro sapete di cosa si parla. Unfalso, magari ben fatto, può essere un brutto tranello in cui cadere. Questa sezioneha lo scopo di illustrare come l'RSA possa essere usato per garantire che il mittentenon sia un impostore.

Alice vuole mandare il suo messaggio a Bob, ma Bob è sospettoso perché sache Enrico potrebbe giocargli un tiro mancino. Allora chiede a Alice di usare la suachiave privata DA e l'RSA sul messaggio, prima di inviarglielo.

Alice prende il messaggio m e applica l'RSA con la sua chiave privata (DA,m)ottenendo il messaggio r. Ora per tornare al messaggio originale basta applicarel'RSA con la chiave pubblica di Alice e quindi RSA(EA, r) sará m, con la garanziache solo Alice dovrebbe conoscere la propria chiave privata, e quindi solo ella puòaver predisposto questo messaggio. L'unico inconveniente di questo modo di pro-cedere è che chiunque può leggere il messaggio inviato da Alice.

3.5.3. Firma digitale. Il passo successivo è proprio quello di coniugare ledue tecniche precedenti per arrivare a quella che in gergo si chiama �rma digitaleche garantisce la riservatezza della comunicazione e la certezza del mittente.

Alice prende il proprio messaggio m e vi applica la propria chiave privata ot-tenendo il messaggio c1 = RSA(DA,m) garantendone quindi la provenienza. Oraesegue a c1 la cifratura con la chiave pubblica di Bob ottenendo c2 = RSA(EB , c1).Invierá c2 a Bob che potrá quindi invertire la sequenza delle cifrature: d1 =RSA(DB , c2) = c1 toglie la cifratura al messaggio c2, garantendo che solo Bob lopossa decifrare. Ora, usando la chiave pubblica di Alice, si calcola RSA(EA, c1) =m togliendo anche il secondo lucchetto e risalendo a m. Grazie al fatto che siaAlice che Bob hanno bisogno di una chiave segreta, si garantisce la riservatezza el'autenticitá del messaggio.

3.6. Limiti Computazionali

L'RSA codi�ca un blocco del messaggio sempre con lo stesso algoritmo. Questosigni�ca che al ripetersi di uno stesso valore di un blocco, il valore cifrato sará lostesso. In teoria dei codici si dice che il sistema è monoalfabetico, ovvero a simbolouguale corrisponde simbolo uguale. Questo è particolarmente visibile nell'esempioche abbiamo costruito e in cui abbiamo usato i byte, caratteri in sostanza, comeblocco elementare di cifratura. Se guardiamo nel �le cifrato, per esempio, a tutte lelettere 'è corrisponde sempre lo stesso valore. Questa sarebbe una grave falla, comestoricamente si è mostrato, che permette facilemente di risalire al testo in chiaroanche in assenza della chiave. Questo problema si può in qualche misura aggirareprendendo un numero n grande, cosï¾÷ da usare blocchi molto grandi e renderela vita più di�cile al nostro oppositore. Ma questo rende la vita di�cile anche a


noi, dato che i numeri che vengono coinvolti diventano grandi e quindi il tempo pereseguire le operazioni sul pc aumenta in modo signi�cativo.

Inoltre bisogna ricorrere a numeri primi molto grandi per avere una buonaprobabilitá che ci voglia molto tempo per risalire dal valore n ai suoi fattori. Fattoriche permetterebbero di ricavare il valore d e quindi la chiave segreta. Altri problemipoi nel trovare numeri primi grandi e sul fatto di poter garantire che siano primi.

Appendice

Esempio

Tratto dalle ultime parole famose, ovvero Le mille balle blu di P. Gomez e M.Travaglio. La chiave privata è (173, 323).

Table 1.

47 53 271 115 165 286241 230 230 42 223 109241 223 131 190 22 18122 230 241 109 22 165249 75 223 249 182 223104 22 181 22 230 5322 165 241 193 104 271109 223 84 204 86 5688 223 229 271 190 22165 42 223 104 271 109223 230 42 115 165 19042 193 319 53 42 230223 69 42 169 271 190230 42 67 193 87 22109 169 22 42 223 206271 190 109 53 115 131

42 230 22 193 193

Secondo esempio

Nelle tabelle successive sono presenti in totale 91 righe contenenti 6 numeri in-teri ciascuna. Esse sono il risultato ottenuto cifrando con l'RSA un �le di testo di 1,7kBytes. La chiave pubblica usata è stata (65537, 1.054.159.999) a cui corrispondela chiave privata (473.930.225, 1.054.159.999). Il testo è stato cifrato dividendolo inblocchi di 3 caratteri consecutivi, generando un numero intero secondo l'algoritmoseguente:

n = c1 ∗ 256 ∗ 256 + c2 ∗ 256 + c3

dove ci rappresenta la codi�ca ASCII del carattere corrispondente. Adattando ilcodice C in appendice, con i dovuti accorgimenti tecnici per gestire numeri interisenza segno a 64 bits anzichè gli usuali a 32 bits, si può risalire al testo in chiaro. Iragazzi riconosceranno, con stupore e forse un �lo di acredine, delle famose terzineche hanno certo studiato al terzo anno.

31

32 APPENDICE

Table 2. Da decodi�care434894881 602794454 393495317 621525751 149898611 309631509336886207 341338898 604254301 869740089 332421753 986114580327935613 729505350 1004095412 434697326 1031046096 324686420369612399 919205262 146191105 1011124673 221469240 689150077879552975 304262447 525988921 440803595 332421753 144347134221469240 795330775 93700353 923380078 66836385 927550986995900967 89170801 304262447 357435288 851344472 621309628221469240 726949157 119838521 304262447 204456281 807564915986114580 728779296 158764863 728779296 699944947 938076340537773534 642142636 221469240 407974636 370524385 65578719970947344 405135790 637541685 753210703 919190559 731660040678383641 216906641 675749335 204456281 3808877 667286760181614087 710121705 385700313 433794888 211599400 364303433725198506 28596418 603795005 447845759 657453728 1038184623637541685 858216684 346897738 662817518 621525751 20534112761081449 559100821 182755874 276603473 591571773 804591562214373862 453620340 727046824 988292166 161194989 721033360204789965 159667465 559100821 182755874 594033345 131987742322953054 284432872 734524718 331591431 690081102 68703162761081449 753323880 357435288 718413310 421800349 333068946778825974 223692008 517136440 667286760 246211302 629760928457963668 900772580 1037682016 725459038 123421878 313396229155427619 392799365 1011036094 970947344 760377179 843073343303299396 332421753 805083373 504198368 833116136 531018665190709359 629760928 747751941 559100821 182755874 64099784232410558 28596418 726949157 873491498 1020552568 855596029782752504 1052236693 232263437 216906641 727046824 464528653787162714 548625789 221042347 212855281 733451800 760377179262392795 425100643 689150077 178072729 444727333 304262447473475490 621072674 243228444 149898611 972713313 718413310864274382 232263437 440125122 95336576 434697326 336886207456256517 736556072 246254310 98052877 906080284 198784804429476484 498130094 425100643 641464063 856575661 782752504351017668 621525751 282453309 604061275 275008724 885928321153349028 51089135 849996943 970947344 811219008 304262447729505350 89170801 456256517 304089234 637541685 826120568295940845 381378694 852825894 116322831 360150109 745741179596963101 629760928 621072674 3190243 837942458 364303433554556162 265120873 433794888 504100055 885928321 207659234474354031 885928321 322953054 178072729 480334417 5149851346897738 1039853369 574947187 531156226 65578719 46079440519944863 913691524 434697326 953010784 18843759 101678171328596418 265120873 614533158 204789965 554603608 31339622981725354 970947344 953010784 906080284 771545021 453596075316589627 774609732 517115961 958175242 708178867 394829403621525751 155427619 227538200 961311810 1039853369 285751800221911063 272127171 835108008 526524219 123421878 470407715256490574 629760928 1034099050 154586067 345956374 537773534439610177 643230772 166982162 10385257 173636945 448701078577556605 616653483 582122835 400746913 264781004 745741179589932194 221911063 924432284 226485054 609511802 957885712

SECONDO ESEMPIO 33

Table 3. Da decodi�care (continua)

547887615 591571773 123421878 765978360 441034489 827322029653461402 913691524 1011036094 970947344 498193786 216906641123356433 992413514 938076340 117323785 434697326 1031046096593219415 985877414 221911063 750505581 747751941 559100821819145418 50136477 42251423 324686420 203951956 34094095143914623 322953054 285802235 21860734 37590102 44372968

69405795 821402957 211665734 637541685 827322029 629760928274563921 938076340 900772580 29720949 643230772 2721271711046588943 970947344 862022251 358210560 1008192909 18520555131987742 64635042 801775415 480334417 932300167 28596418603795005 313881245 86567421 629924272 770899502 737525733554556162 387667064 32410558 204789965 791253024 372175383873305144 988292166 246211302 643230772 324686420 1039853369624528236 1039853369 351924947 480334417 537773534 69405795305159420 824358304 552295846 582122835 970947344 341338898895150982 1038184623 341217664 42251423 776909040 849996943464528653 346424657 522749372 331591431 166922142 173487170473475490 541369134 75305114 861602028 1033165567 589334439549067336 477271239 736556072 1033165567 493909757 389971601916885157 545953306 667286760 1030869140 905998024 297186661985368404 791253024 736556072 559100821 182755874 640997842637541685 365832073 467414788 861726652 1004270699 407283285835108008 934771844 835108008 552295846 804002793 64635042246211302 304262447 397655766 1050306134 425645494 996473268621525751 905998024 538510611 918255281 732675606 9323001671037682016 905998024 104972005 965567070 683601352 1987848041046588943 734271086 313396229 852825894 198006186 97714912365578719 791162878 215131823 204789965 72188748 596931336851344472 833116136 173636945 728248184 873305144 357682319246245863 971750397 159667465 341338898 1050306134 10959730313396229 852825894 204789965 159667465 856686407 52546207

272127171 1046588943 400746913 466640447 480191711 10356869511002359727 178072729 480334417 381378694 346031135 480191711341338898 313396229 632792358 878645986 480334417 123421878760377179 635287017 440803595 637541685 852825894 98494565332313967 621525751 59819722 64635042 825964690 216906641

542521029 945629796 198006186 579976134 391854488 148721409574947187 734271086 10385257 433794888 211599400 621072674574947187 734271086 327935613 334481100 159667465 760377179674852722 986114580 689150077 178072729 871285336 743197063

91753835 49299308 906080284 391854488 218705020

34 APPENDICE

Sorgenti Ansi-C

2008�01�04 euclide�ex.c 1

file:///home/tt/ansiC�s/euclide�ex.c

#include<stdio.h>intmain(){inta,b,r,q,x1=0,x2=1,x,B,A;printf("Gimmefirstnumber(phi(n))");scanf("%d",&a);if(a<0)a=Aa;printf("Gimmesecondnumber(e)");scanf("%d",&b);if(b<0)b=Ab;if(b>a){r=a;a=b;b=r;}B=b;A=a;r=1;printf("A\t\tQ\t*\tB\t+\tR\t\tx1\tx2\n");while((r)!=0){r=a%b;q=a/b;//printf("%d\t=\t%d*%d\t+\t%d.x1=%d\tx2=%d\n",a,q,b,r,x1,x2);printf("%d\t=\t%d\t*\t%d\t+\t%d\t.\t%d\t%d\n",a,q,b,r,x1,x2);a=b;b=r;if(r!=0){x=x2*q+x1;x1=x2;x2=x;}else{/*x=x2+x1;x1=x2;x2=x;*/}///*Parechesidebbafinirequandosiarivaadavereilrestougualea1!!!!*/}printf("Dcandidateis%d:",x);x1=x;x=(x2*B)%A;if(x!=1){printf("thatisA1mod%d",A);if(x==AA1){x2=(x2*x2*B)%A;x=(x2*B)%A;printf("\tNewx2=%dhasrest=%d\n",x2,x);printf("Calculatedas%dA%d=%d\n",A,x1,AAx1);}elseprintf("UHOH!!!!\n");}else{printf("\n%disOKandsoitistheinverseof%dmod%d.\n",x2,B,A);}return0;}Euclide Esteso

SORGENTI ANSI-C 352008�01�04 RSA.c 1

file:///home/tt/ansiC�s/RSA.c

/*rsa�3.c*Eseguelacodificarsadiunfileditestoilcuinomevienelettodatastiera*inunfileditesto,uninteroperriga,dinomelettodatastiera.*Datastierasifornisconoanchelachiavepubblica(n,e)perlacifratura**Sesipassaunparametroaggiuntivoinlinea,ilprogrammaesegueladecifratura:*Sidàilnomedelfilecontenenteilcyphertexteilfilenameperladecodifica*oltreallachiaveprivata(n,d).*LicenzaLGPLV2byeng.TizianoBinda**/#include<stdio.h>intenc(int,int,int);intmain(intargc,char*argv[]){intn,e,m,c,i;charch;FILE*S,*D;charnf[30],s[1024];printf("Fileditestodiinput:");//fgets(nf,30,stdin);gets(nf);printf("Fileditestodioutput:");//fgets(s,1024,stdin);gets(s);printf("DAmmin:");scanf("%d",&n);printf("Dammie/d:");scanf("%d",&e);if((S=fopen(nf,"rt"))==NULL){printf("Errorediaperturadelfilediinput(%s)!!\n",nf);return1;}if((D=fopen(s,"wt"))==NULL){printf("Errorediaperturadelfiledioutput(%s)!!\n",s);return1;}if(argc==1){printf("Encoding!!\n");while((ch=fgetc(S))!=EOF){c=enc(n,e,(int)ch);fprintf(D,"%d\n",c);}}else{printf("Decoding!!\n");while((fscanf(S,"%d",&m))==1){c=enc(n,e,m);printf("%c",c);fprintf(D,"%c",(char)c);}}fclose(S);fclose(D);return0;}RSA.c pagina 1

36 APPENDICE2008�01�04 RSA.c 2

file:///home/tt/ansiC�s/RSA.c

intenc(intn,inte,intm){inti=1,c=1;for(;i<=e;i++)c=(c*m)%n;returnc;}

Figure 3.6.1. RSA.c Pagina 2

L'algoritmo RSA: un approccio algebrico ed astratto Dott. Ing. … · 1.3. CENNI DI CRITTOGRAFIA...

Documents

Transcript of L'algoritmo RSA: un approccio algebrico ed astratto Dott. Ing. … · 1.3. CENNI DI CRITTOGRAFIA...