Algoritmi di Crittografia (2024/25) - PDF

Algoritmi di Crittografia (2024/25) Notebook 1 Latex definitions Presentazione del corso Informazioni generali sul corso 6 CFU, per 42 ore di lezione, divisi in due moduli: 1. Teoria e algoritmi (4 CFU), prof. Mauro Leoncini 2. Crimine informatico (2 CFU), prof. Antonio Apruzzese...

Algoritmi di Crittografia (2024/25) Notebook 1 Latex definitions Presentazione del corso Informazioni generali sul corso 6 CFU, per 42 ore di lezione, divisi in due moduli: 1. Teoria e algoritmi (4 CFU), prof. Mauro Leoncini 2. Crimine informatico (2 CFU), prof. Antonio Apruzzese Il materiale didattico, in particolare i notebook, sarà disponibile su Moodle. Non è previsto un libro di testo. I notebook delle lezioni e gli appunti sul crimine informatico sono in linea di principio sufficienti per preparare l'esame. Agli interessati suggerisco almeno un paio di testi per lo studio e l'approfondimento personale, uno in lingua inglese e l'altro in lingua italiana. Jean-Philippe Aumasson Serious Cryptography: A Practical Introduction to Modern Encryption No Starch Press Anna Bernasconi, Paolo Ferragina, Fabrizio Luccio Elementi di Crittografia Pisa University Press Esame solo orale. Ricevimento studenti: su richiesta (a distanza o in presenza). Contenuti del corso (modulo Teoria e Algoritmi) Cifrari classici ed elementi base della crittografia simmetrica Prerequisiti matematico/algoritmici per la crittografia asimmetrica Casualità e algoritmi probabilistici Aritmetica modulare Algoritmi di base per la crittografia asimmetrica Scambio di chiavi con il protocollo Diffie-Hellman Protocolli di cifratura (RSA, El Gamal, Rabin) Firma digitale (RSA, El Gamal, DSA)  Curve ellittiche e loro proprietà per applicazioni crittografiche Firma digitale su curve ellittiche Infrastrutture per la certificazione di chiavi pubbliche. Il corso sarà corredato: 1. dalla presentazione (sviluppo e uso) di algoritmi in linguaggio Python 2. dall'uso di librerie crittografiche Software utilizzato Utilizzeremo i seguenti strumenti software: il linguaggio Python 3.11; l'ambiente jupyter-lab per le presentazioni a lezione (quello che stiamo usando ora); (forse, e occasionalmente) l'ambiente di sviluppo Spyder Installazione del software in ambiente virtuale sotto Linux Le istruzioni qui riportate si riferiscono a sistemi basati su Debian GNU Linux (Debian, Ubuntu, Mint,...) Per altre distribuzioni quel che cambia è essenzialmente il package manager sudo apt install python3-virtualenv sudo apt install python3-virtualenvwrapper mkdir ~/.virtualenvs mkvirtualenv AC # Il nome AC è arbitrario workon AC (AC) pip install spyder (AC) pip install ipython (AC) pip install jupyterlab (AC) deactivate Nota: È possibile che il comando mkvirtualenv non sia inizialmente riconosciuto. In tal caso, un workaround consiste nell'aggiungere le seguenti linee di codice al file.bashrc nella propria home: export VIRTUALENVWRAPPER_PYTHON=/usr/bin/python3 export ORKON_HOME=~/.virtualenvs export ARCHFLAGS=’-arch x86_64’ source /usr/local/bin/virtualenvwrapper.sh Attenzione inoltre alla possibilità che che il file virtualenvwrapper.sh non sia stato installato nella directory /usr/local/bin. In tal caso, lo si “localizzi” prima con il comando: dpkg -L virtualenvwrapper | grep virtualenvwrapper.sh e si modifichi poi opportunamente l'ultima riga da inserire in.bashrc. Installazione sotto Windows o Mac Per questi ambienti consigliamo di installare la piattaforma Anaconda (che include IPython, jupyter-lab e spyder). Anaconda è comunque disponibile anche in ambiente Linux. Uso sotto GDrive È possibile usare notebook dal proprio account Google, quindi senza installare nulla sul PC. È necessario accedere a Google drive e aprire i notebook (preventivamente caricati) usando l'applicazione COLAB (COllaborative LABoratory) Nozioni preliminari Scenario classico La crittografia moderna include molteplici ambiti applicativi. Lo scenario "tipico" prevede due attori, tradizionalmente chiamati Alice e Bob, che vogliono scambiarsi informazioni su un canale di comunicazione insicuro, dove un terzo personaggio, Eva, è in grado di intercettare, leggere e modificare i messaggi. Assumendo che, in una data comunicazione, Alice sia il mittente e Bob il destinario, si possono individuare i seguenti requisiti tipici della comunicazione stessa. 1. La confidenzialità del messaggio, ovvero che Eva non sia in grado di comprenderne il contenuto; 2. l'autenticazione del mittente, in base alla quale Bob è certo che il messaggio sia stato effettivamente inviato da Alice; 3. l'integrità del messaggio, in base alla quale Bob è certo che Eva non lo abbia manomesso; 4. il non ripudio, per cui Alice non può negare, in un secondo momento, di aver inviato il messaggio a Bob. Un po' di ulteriore terminologia Plaintext/testo in chiaro è il messaggio che si vuole tenere segreto. Encryption/cifratura è il processo che rende il plaintext incomprensibile per Eva. Nella lingua inglese il testo cifrato è indicato con il termine ciphertext. Ogni processo di cifratura deve evidentemente essere reversibile. Il procedimento che dal testo cifrato restrituisce il plaintext originale è detto decryption/decifrazione. Cifratura e decifrazione sono i due algoritmi che compongono un cifrario/cipher Un cifrario fa uso di informazione segreta, nota come chiave/key Il fondamentale principio di Kerckhoff In uno schema di cifratura, la sicurezza deve risiedere solo nella segretezza della chiave (A. Kerckhoff, La Cryptographie Militaire, 1883) In particolare, la segretezza non deve risiedere nell'algoritmo. Due "tipi" di crittografia Letteralmente per "secoli" crittografia è stato solo un sinonimo di crittografia simmetrica. In un protocollo simmetrico Bob e Alice possiedono la stessa chiave ovvero hanno chiavi che possono essere facilmente determinate l'una a partire dall'altra. Solo in tempi recenti, sulla spinta della necessità di risolvere il problema cruciale dello scambio di chiavi, si è sviluppata la crittografia asimmetrica, in cui una delle due chiavi è posseduta solo da chi, fra Alice e Bob, è il destinatario di una comunicazione. È palese che, nel caso della crittografia asimmetrica, la determinazione della chiave privata a partire dalla chiave pubblica deve essere computazionalmente difficile. Il lavoro fondamentale, che delinea le caratteristiche della crittografia asimmetrica, è del 1976: Whitfield Diffie, Martin Hellman New directions in cryptography IEEE Trans. Inf. Theory (1976) La matematica e l'algoritmica sottostanti i protocollo simmetrici e quelli simmetrici sono sostanzialmente distinte. Sguardo d'insieme alle differenze fra i due tipi di crittografia Crittografia simmetrica Crittografia asimmetrica Una sola chiave per cifrare e Una chiave pubblica per cifrare e una decifrare privata per decifrare Il principale ostacolo è la necessità di Ildell'identità mittente deve essere certo del possessore della un accordo preliminare sulla chiave chiave pubblica Ingestibile in applicazioni che Gestibile con più coppie di chiavi coinvolgono più partecipanti pubblica/privata (servono coppie) (servono O(n ) 2 chiavi) n Algoritmi veloci, anche con supporto Algoritmi lenti hardware  Crittografia simmetrica e asimmetrica lavorano spesso insieme Vantaggi e svantaggi sono speculari e dunque, molto spesso, protocolli applicativi che utilizzano la crittografia fanno uso di entrambe le soluzioni. Al riguardo, il seguente schema esemplifica le interazioni fra i due tipi di crittografia. Lo scenario è relativo alla cifratura. In [189… from IPython.display import display, Image display(Image(filename="./cifratura_schema.jpg")) Crittografia simmetrica Il focus di questo corso è sulla crittografia asimmetrica. In questo primo notebook forniamo tuttavia qualche nozione anche sulla crittografia simmetrica. I concetti base verranno introdotti utilizzando principalmente cifrari classici, del tutto inedeguati a resistere ad attacchi portati con moderni coputer.  Vedremo tuttavia anche un cifrario moderno (anche se superato), che ci consentirà di cogliere le idee oggi alla base della crittografia simmetrica. Principi generali dei cifrari a blocchi Nella struttura di un cifrario simmetrico (a blocchi) si possono individuare due distinte componenti. Una prima componente è l'algoritmo, o semplicemente l'insieme di operazioni che applicano una determinata permutazione ad una porzione del plaintext. Che cosa sia una porzione è evidentemente una caratteristica propria del cifrario. Essa puà essere una singola lettera, un gruppo di lettere o (come nei cifrari moderni) un gruppo di bit, detto comunemente blocco. Una permutazione di un insieme di oggetti è uno dei possibili modi in cui gli n n oggetti si possono disporre linearmente (uno dopo l'altro); cioè è uno dei possibili ordinamenti degli oggetti. In termini matematci, una permutazione (degli elementi) di un insieme è una I funzione invertibile di in se stesso. I Si noti che l'ovvio requisito di invertibilità delle cifratura, che si precisa formalmente con l'invertibilià delle permutazioni, in termini pratici implica che plaintext e ciphertext abbiano sempre la stessa lunghezza. La seconda componente fondamentale di un cifrario è l'algoritmo che, organizzando opportunamente le permutazioni dei singoli blocchi, effettua la cifratura di un plaintext arbitrario. Questa seconda componente è detta mode of operation. Nota. I cifrari a blocchi non sono l'unico tipo di cifrario simmetrico. Un tipo differente è un cifrario che considera il messaggio come un flusso continuo di bit. Un tale cifrario utilizza la chiave per generare un corrispondente flusso di bit (pseudo)casuali, da porre in XOR con i bit del messaggio. In questo caso, che chiaramente si adatta a quelle situazioni (come succede nelle comunicazioni telefoniche) in cui il messaggio non è noto prima che debba iniziare il processo di cifratura, si parla di stream cipher. Sulle permutazioni È noto che, al crescere di , il numero di permutazioni diventa rapidamente enorme, n in quanto cresce come il fattoriale di. n n! = 1 ⋅ 2 ⋅ 3 ⋅ … ⋅ (n − 1) ⋅ n Ad esempio, le possibili permutazioni di 10 oggetti sono già più di 3 milioni. Numero che sale a circa 1300 miliardi nel caso di 15 oggetti. In [120… from math import factorial print(factorial(5))  print(factorial(10)) print(factorial(26)) 120 3628800 403291461126605635584000000 Due cifrari classici: Cesare e Vigenère Consideriamo messaggi scritti in un generico alfabeto e consideriamo un Σ ordinamento circolare dei caratteri (arbitrario ma fissato una volta per tutte). Circolare vuol dire che il primo carattere è considerato il successore dell'ultimo. Nel cifrario di Cesare la cifratura avviene come illustrato di seguito. La permutazione applicata ad ogni carattere consiste in uno slittamento (shift) di posizioni in avanti. k Questo vuol dire che ogni carattere del plaintext viene sostituito con il x carattere che si trova posizioni più avanti rispetto ad nell'ordinamento k x circolare dell'alfabeto. Ad esempio, considerando l'alfabeto inglese e ponendo k = 3 , la viene a sostituita con la , la con la ,..., la con la , la con e la con la. d b e x a y b z c Il mode of operation del cifrario è il più semplice possibile e consiste nell'applicare la stessa permutazione ad ogni carattere. È evidente che chiave "segreta" di cifratura è proprio il valore dello slittamento. k La decifrazione deve rimettere le cose a posto e questo, nel cifrario di cesare, consiste nell'effettuare uno slittamento di posizioni all'indietro, ovvero sostituire k ogni carattere del ciphertext con un carattere nell'alfabeto che precede di x x k posizioni nell'ordinamento circolare. Potremmo anche dire che, se è la chiave di cifratura, la chiave di decifrazione è il k valore opposto,. −k È chiaro che per il cifrario di Cesare il numero di chiavi, che coincide con il numero di possibili slittamenti, è limitato dalla cardinalità dell'alfabeto. Una semplice sfida Consideriamo come alfabeto Σ = {a,b,...,z} ∪ {.} ∪ {,}∪ {'} Sapendo che il cifrario utilizzato è quello di Cesare, a quale testo in chiaro corrisponde il cyphertext kdcxiitzz,ev,yhtjeved,bv,yhth,ew,vxithx? In [123… alphabet = "abcdefghijklmnopqrstuvwxyz.,'" def encrypt(plaintext,key): n = len(alphabet) cyphertext = ''.join([alphabet[(alphabet.find(c)+key)%n] for c in plaint return cyphertext def decrypt(cyphertext,key): return encrypt(cyphertext,-key)  Il procedimento di risoluzione di questa sfida è un caso di crittoanalisi. In questo caso, la crittoanalisi è banale. Dato il numero limitato di chiavi, un attacco a forza bruta ha facile successo, solo con qualche necessaria sottolineatura... In [125… # Attacco a forza bruta al cifrario di Cesare unknowntext = "kdcxiitzz,ev,yhtjeved,bv,yhth,ew,vxithx" for k in range(1,len(alphabet)): print(f"{k}\t{decrypt(unknowntext,k)}") 1 jcbwhhsyy.du.xgsidudc.au.xgsg.dv.uwhsgw 2 ibavggrxxzctzwfrhctcbz'tzwfrfzcuztvgrfv 3 ha'uffqwwybsyveqgbsbay,syveqeybtysufqeu 4 g',teepvvxarxudpfara'x.rxudpdxasxrtepdt 5 f,.sddouuw'qwtcoe'q',wzqwtcocw'rwqsdocs 6 e.zrccnttv,pvsbnd,p,.vypvsbnbv,qvprcnbr 7 dzyqbbmssu.ouramc.o.zuxouramau.puoqbmaq 8 cyxpaalrrtzntq'lbznzytwntq'l'tzotnpal'p 9 bxwo''kqqsymsp,kaymyxsvmsp,k,synsmo'k,o 10 awvn,,jpprxlro.j'xlxwrulro.j.rxmrln,j.n 11 'vum..iooqwkqnzi,wkwvqtkqnzizqwlqkm.izm 12 ,utlzzhnnpvjpmyh.vjvupsjpmyhypvkpjlzhyl 13.tskyygmmouiolxgzuiutoriolxgxoujoikygxk 14 zsrjxxfllnthnkwfythtsnqhnkwfwntinhjxfwj 15 yrqiwwekkmsgmjvexsgsrmpgmjvevmshmgiwevi 16 xqphvvdjjlrfliudwrfrqlofliudulrglfhvduh 17 wpoguuciikqekhtcvqeqpknekhtctkqfkeguctg 18 vonfttbhhjpdjgsbupdpojmdjgsbsjpejdftbsf 19 unmessaggiocifratoconilcifrariodicesare 20 tmldrr'ffhnbheq'snbnmhkbheq'qhnchbdr'qd 21 slkcqq,eegmagdp,rmamlgjagdp,pgmbgacq,pc 22 rkjbpp.ddfl'fco.ql'lkfi'fco.oflaf'bp.ob 23 qjiaoozccek,ebnzpk,kjeh,ebnznek'e,aozna 24 pih'nnybbdj.damyoj.jidg.damymdj,d.'nym' 25 ohg,mmxaacizc'lxnizihcfzc'lxlci.cz,mxl, 26 ngf.llw''bhyb,kwmhyhgbeyb,kwkbhzby.lwk. 27 mfezkkv,,agxa.jvlgxgfadxa.jvjagyaxzkvjz 28 ledyjju..'fw'ziukfwfe'cw'ziui'fx'wyjuiy Cifrari mono-alfabetici Il cifrario di Cesare è forse il più semplice caso di cifrario mono-alfabetico. È tale un cifrario che utilizza una sostituzione fissa per ogni carattere. In altri termini, fissato l'alfabeto di riferimento , un cifrario mono-alfabetico è Σ definito da una singola permutazione ripetuta per tutti i caratteri. In [127… from math import factorial,log10 In [128… log10(factorial(29)) Out[128… 30.946538820206058  Permutazioni ideali e relazioni con la chiave Le permutazioni utilizzate dal cifrario di Cesare sono semplici slittamenti circolari, detti più propriamente rotazioni. Per conoscere una tale permutazione è sufficiente un singolo numero intero, compreso fra 0 e la cardinalità dell'alfabeto, che rappresenta quindi la chiave del cifrario. La proprietà che la chiave determina la permutazione deve valere sempre, anche se il passaggio dalla chiave alla permutazione non è di norma così semplice come nel cifrario di Cesare. La chiave infatti è l'unica informazione segreta e dunque la permutazione deve dipendere necessariamente dalla chiave. Non solo, chiavi diverse devono sempre fornire permutazioni diverse. In caso contrario per un attaccante ci sarebbero meno chiavi distinte da "provare" e questo potrebbe agevolare sensibilmente gli attacchi. Infine, la permutazione dovrebbe il più possibile apparire casuale. Questo garantisce che la conoscenza di come viene mappata una lettera (o un gruppo di bit) non fornisce alcuna conoscenza sulla mappatura delle altre. Nel caso del cifrario di Cesare, la permutazione è tutto fuorché casuale. Se sappiamo che la lettera viene mappata nella lettera , sappiamo immediatamente a d anche che viene mappata in , in e così via. b e c f Un generico cifrario mono-alfabetico Allo scopo di procurarci permutazioni arbitrarie, utilizzeremo la funzione permutation del modulo numpy.random. In [132… from numpy.random import permutation In [133… p=permutation(10) print([i for i in range(10)]) print([int(i) for i in p]) [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] [9, 8, 5, 0, 7, 4, 6, 2, 3, 1] In questo esempio usiamo il seguente alfabeto, composto di 30 simboli In [135… alphabet2 = r"abcdefghijklmnopqrstuvwxyz.,'" factorial(30) Out[135… 265252859812191058636308480000000  Senza starle a contare, il numero di cifre decimali 30! è determinabile nel modo seguente In [137… from math import log10 X = factorial(30) int(log10(X))+1 Out[137… 33 In [138… # Funzione di cifratura def mono_alphabetic_encrypt(plaintext,alphabet,P=None): '''Uses P or otherwise picks a random key/permutation and encypts plaintext over alphabet. Returns cyphertext and key''' from numpy.random import permutation # Possiamo ignorare le accentate perché questo non inficia l'intellegibi # ad un madre-lingua italiano D = {'à':'a','è':'e','é':'e','ì':'i','ò':'o','ù':'u'} if P is None: P=permutation(len(alphabet)) ciphertext = [alphabet[P[alphabet.find(D.get(c,c))]] for c in plaintext] return ''.join(ciphertext),P In [139… c,P = mono_alphabetic_encrypt("dobbiamo proteggerci dai cybercriminali", alp print(c) oarryxkagl'acmddm'pygoxygpqrm'p'ykyux.y La chiave ovviamente non può viaggiare in chiaro; deve in qualche modo essere preliminarmente concordata. Come esercizio, si scriva il semplice codice per la decifrazione. Al riguardo, il seguente codice calcola la permutazione inversa di una permutazione data come array numpy. In [141… from numpy import where In [142… # La corrispondente permutazione inversa Pinv = [int(where(P==i)) for i in range(len(P))] In [143… # Verifica for i in range(len(P)): print(Pinv[P[i]],end='\t') 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 In [144… ''.join([alphabet2[Pinv[alphabet2.find(c[i])]] for i in range(len(c))]) Out[144… 'dobbiamo proteggerci dai cybercriminali' Una seconda challenge: decifrare il testo cifrato che stiamo per creare In [146… # hiddentext.txt contiene un testo in italiano da decifrare P = permutation(len(alphabet2)) with open('hiddentext.txt','r') as f: ciphertext,key = \ mono_alphabetic_encrypt(''.join([l.strip().lower() for l in f.readlines( In [147… print(ciphertext) tlyzeeznc,ph'ttipb,kkztpg,nplypmznn,pclpb,lsplypmznn,pclpghlpm'pc,fzpmlp'nn, czt'sp'yy'palnzsp,enwn,pczlpalylpghzpux xpt,rylneph'plng,olngl'k,p'pkzmmztzp c'yy'pbtlo'pb'eln'pczypbtlo,pf,ywozsplypg,olk'k,pmlpzpkt,f'k,pclpat,nkzspg,o zpnzyyzpal'jzpzpnzlpy'jltlnklspktzpflzxpo'nkznztzpy'pmgzyk'pa'kk'pnzypkt'cwt tzpn,olpclpyw,ehlpzpbztm,n'eelsptlk,tn'tzp'ypn,ozp,tleln'yzp,pbztg,ttztzpw n'pkztd'pfl'pmgzeylznc,pwnpn,ozpczypkwkk,pnw,f,xp'ygwnlpzmzoblxnzypg'm,pcl p'yjwmpmlyznkzpzpb'tm,pmwjlk,pghl't,pghzp'pbtl,tlpnzmmwn'pczyyzpktzpmkt'czpz t'pclpbztpmzpvwzyy'pelwmk'xp'ypo,oznk,pclpmgzeylztzplypg,en,ozplk'yl'n,spghz pzt'pb'tm,p'czew'k,pbztpwnpo'e,pjldd'tt,po'p'nghzpm,yznnzpzpg'b'gzpclpkznztz plnpm,eezdl,nzplpmw,lpnzolglspn,npmlpm'bzf'pvwzyy,pghzpux xpt,rylnep'ftzjjzp b,lpclghl't'k,p.y,ploo'eln'f,pg,ozpwnpo'e,pjznzf,y,spmzobtzplnpo,floznk,spgh zpo,to,t'pg,nklnw'oznkzpkt'pmzpzpmz.pcwojyzc,tzsplnplneyzmzspzplypn,ozp'tg'l g,pclpjwojyzjzzsplypg'y'jt,nzxp'ykt,pghzp.mlyznkz.xpzbbwtzspy'pmk,tl'pclo,mk tzt'pghzpbt,btl,plpmlyzndlpclp'yjwmph'nn,p'fwk,pwnptw,y,pczkztoln'nkzspzp'ng hzpnze'klf,spnzyyzp'ffznkwtzpclph'ttipb,kkztpzpnzyy'py,kk'pg,nkt,py'po'el'p, mgwt'xy'pmgzyk'pclptlk,tn'tzp'ypn,ozp,tleln'yzpclpwn,pczlpbt,k'e,nlmklpbtlng lb'ylpczyy'pm'e'pzpmk'k'pa'kk'pnzypg'm,pclpolnztf'poge,n'e'yyspy'pgwlp'yozn, p'bb'tznkzpmzfztlk'pf,yzf'pzmmztzpzmbtzmm'spnzyy.zcldl,nzplk'yl'n'spc'ypt,gg l,m,p'c'kk'oznk,poget'nnlkxy'pkztd'pfl'pzpvwzyy'pghzpzpmk'k'pozn,patzvwzn k'k'xpvwzyyzpb,ghzpf,ykzspbzt,spmlpzptlfzy'k'pbtzdl,m'xpzpmk'k'pbztg,tm'pnzy y'pmgzyk'pczypn,ozpczyyzpvw'kkt,pg'mzplnpgwlpmlpclflc,n,peylpmkwcznklpclph,e r'tkmxplpy,t,pn,olplk'yl'nlpmzewlf'n,pm,y,plnpb'tkzplpg,ttlmb,ncznklplneyzml xp'eelwnezf'n,spbztpzmzobl,splnclg'dl,nlpclpg,y,tzpczypkwkk,p'mmznklpnzyy.,t leln'yzxpmlpzpg,mlpczglm,pbztpetla,nc,t,spk'mm,at'mm,spg,tf,nzt,pzpmztbzfztc zx Sembra una challenge impossibile, visto che la permutazione è stata scelta a caso fra 30! permutazioni possibili. Critto-analisi Per un generico cifrario mono-alfabetico il numero di possibili chiavi è dunque pari al numero di permutazioni dell'insieme dei caratteri dell'alfabeto. Per l'alfabeto che stiamo considerando (che pure possiamo ritenere "piccolo"), sappiamo che le permutazioni sono più di. Un attacco a forza bruta è pertanto 10 33 fuori discussione. Per i cifrari mono-alfabetici è però efficace una critto-analisi basata sull'analisi delle frequenze. Analisi della frequenze  L'attacco è basato sull'ipotesi (non sempre verificata, o solo parzialmente verificata) che la frequenza con cui compaiono i singoli caratteri nel plaintext sia conforme alla più generale frequenza nella lingua con cui il testo stesso è scritto. È evidente che, in generale, l'ipotesi sarà tanto più verificata quanto più il plaintext è lungo. Per portare questo attacco, conoscendo (o ipotizzando quale sia) la lingua con cui è scritto il plaintext, bisogna dunque disporre di un stima delle frequenze dei caratteri in quella lingua. Le celle di codice che seguono calcolano una tale stima per l'italiano, utilizzando a tale scopo un solo testo "classico" (I promessi sposi). In [151… def countfreq(text, alphabet): '''Given some text, computes the frequencies of the characters included in the alphabet. Returns a dictionary. It is assumed that the alphabet includes lowercase letters only. text is a string but a first attempt is made to check whether filename is the complete name of a file storing the actual text. ''' try: f = open(text,'r') T = ''.join([line.strip().lower() for line in f.readlines()]) f.close() except OSError or FileNotFoundError: # First parameter is the actual text T = text.lower() D = {c:0 for c in alphabet} for c in T: c = {'à':'a','è':'e','é':'e','ì':'i','ò':'o','ù':'u'}.get(c,c) try: D[c]+=1 except KeyError: # Discard not-alphabetic characters pass return D In [152… countfreq("Questo è l'insegnamento di Algoritmi di crittografia",alphabet2) Out[152… {'a': 4, 'b': 0, 'c': 1, 'd': 2, 'e': 4, 'f': 1, 'g': 3, 'h': 0, 'i': 7, 'j': 0, 'k': 0, 'l': 2, 'm': 2, 'n': 3, 'o': 4, 'p': 0, 'q': 1, 'r': 3, 's': 2, 't': 5, 'u': 1, 'v': 0, 'w': 0, 'x': 0, 'y': 0, 'z': 0, ' ': 6, '.': 0, ',': 0, "'": 1} In [153… Fdict=countfreq('promessi_sposi.txt',alphabet2) freq = sorted([(k,v) for k,v in Fdict.items()] ,key=lambda p: p,reverse=T In [154… freq Out[154… [(' ', 196150), ('e', 123641), ('a', 118130), ('o', 98961), ('i', 97929), ('n', 74801), ('r', 67744), ('t', 62555), ('l', 57139), ('s', 56060), ('c', 48112), ('d', 38214), ('u', 36592), ('p', 30455), (',', 26319), ('m', 24275), ('v', 23585), ('g', 17585), ('h', 13834), ('f', 10804), ('b', 10009), ("'", 9955), ('.', 9553), ('q', 8007), ('z', 7776), ('x', 75), ('j', 23), ('y', 8), ('w', 3), ('k', 0)] Come secondo passo calcoliamo le frequenze dei caratteri ciphertext e ordiniamole in senso decrescente. In [156… cFdict=countfreq(ciphertext,alphabet2) cfreq = sorted([(k,v) for k,v in cFdict.items()] ,key=lambda p: p,reverse In [157… cfreq Out[157… [('p', 295), ('z', 200), ("'", 151), ('l', 148), (',', 138), ('n', 116), ('t', 104), ('y', 99), ('k', 87), ('m', 75), ('g', 54), ('c', 49), ('o', 43), ('w', 40), ('b', 38), ('e', 38), ('f', 27), ('s', 26), ('h', 20), ('x', 18), ('j', 14), ('a', 9), ('d', 9), ('v', 6), ('.', 6), ('r', 3), ('i', 2), ('u', 2), (' ', 2), ('q', 0)] Come terzo passo proviamo la corrispondenza (permutazione) secca. Dopodiché, se si inizia a "vedere qualcosa", si eseguono modifiche progressive alla permutazione iniziale. In [159… # Permutazione iniziale invkey = {p:q for p,q in zip(cfreq,freq)} In [160… invkey Out[160… {'p': ' ', 'z': 'e', "'": 'a', 'l': 'o', ',': 'i', 'n': 'n', 't': 'r', 'y': 't', 'k': 'l', 'm': 's', 'g': 'c', 'c': 'd', 'o': 'u', 'w': 'p', 'b': ',', 'e': 'm', 'f': 'v', 's': 'g', 'h': 'h', 'x': 'f', 'j': 'b', 'a': "'", 'd': '.', 'v': 'q', '.': 'z', 'r': 'x', 'i': 'j', 'u': 'y', ' ': 'w', 'q': 'k'} In [161… # Applicazione della permutazione attuale ptext = ''.join([invkey[c] for c in ciphertext]) print(ptext)  rotemmendi harrj ,iller cin ot senni do ,iog ot senni do cho sa dive so anni derag atta 'oneg imnpni deo 'oto che yfwf rixtonm ha onciuoncoali a lessere datta ,roua ,amona det ,roui vitpueg ot ciuolali so e lrivali do 'rinleg ciu e nette 'oabe e neo taboronlog lre voef uanlenere ta scetla 'alla net lradpr re niuo do tpimho e ,ersinammog rolirnare at niue iromonate i ,ercirrere pna ler.a voa scemtoendi pn niue det lplli npivif atcpno eseu,ofnet casi do atbp s sotenle e ,arsi spboli choari che a ,roiro nesspna dette lre slrade era do ,er se qpetta mopslaf at uiuenli do scemtoere ot cimniue olatoanig che era , arsi adempali ,er pn uami bo..arri ua anche sitenne e ca,ace do lenere on si mme.oine o spio neuocog nin so sa,eva qpetti che yfwf rixtonm avrebbe ,io do choarali zti ouuamonavi ciue pn uami benevitig seu,re on uivouenlig che uiru ira cinlonpauenle lra se e sez dpubtedireg on onmteseg e ot niue arcaoci do bpubtebeeg ot catabrinef atlri che zsotenlezf e,,preg ta sliroa douislrera c he ,ri,roi o soten.o do atbps hanni avpli pn rpiti deleruonanleg e anche nem alovig nette avvenlpre do harrj ,iller e netta tilla cinlri ta uamoa iscpraf ta scetla do rolirnare at niue iromonate do pni deo ,rilaminoslo ,ronco,ato detta sama e slala 'alla net casi do uonerva ucminamattg ta cpo atueni a,,ar enle severola viteva essere es,ressag nettzedo.oine olatoanag dat riccoisi a dallauenli ucmrannolfta ler.a voa e qpetta che e slala ueni 'reqpenlalaf qpe tte ,iche vitleg ,erig so e rovetala ,re.oisaf e slala ,ercirsa netta scetla det niue dette qpallri case on cpo so dovodini mto slpdenlo do himxarlsf o t iri niuo olatoano sempovani siti on ,arle o cirros,indenlo onmtesof ammopnme vanig ,er eseu,oig ondoca.oino do citire det lplli assenlo nettziromonatef s o e ciso decosi ,er mro'indirig lassi'rassig cirvineri e ser,everdef In [162… # Funzione che inverte la corrispondenza di v1 e v2 def swap(v1,v2,d): k1 = list(d.keys())[list(d.values()).index(v1)] k2 = list(d.keys())[list(d.values()).index(v2)] d[k1] = v2 d[k2] = v1 Dall'analisi visuale si effettuano poi i seguenti cambiamenti alla permutazione iniziale Si noti che, se si capisce che due lettere sono semplicemente invertite, l'applicazione diswap sistema entrambe le corrispondenze. Se invece una lettera del testo cifrato codifica del testo in chiaro ma non x y y codifica , allora x swap(x, y, invkey) sistema solo la corrispondenza di. y In questo secondo caso, dopo lo swap la lettera che era codificata da ora è y codificata sa. x I passaggi sono (relativamente) tanti, ma via via sempre più ovvi. In [164… swap("i","o",invkey) # i e o sembrano invertite In [165… invkey Out[165… {'p': ' ', 'z': 'e', "'": 'a', 'l': 'i', ',': 'o', 'n': 'n', 't': 'r', 'y': 't', 'k': 'l', 'm': 's', 'g': 'c', 'c': 'd', 'o': 'u', 'w': 'p', 'b': ',', 'e': 'm', 'f': 'v', 's': 'g', 'h': 'h', 'x': 'f', 'j': 'b', 'a': "'", 'd': '.', 'v': 'q', '.': 'z', 'r': 'x', 'i': 'j', 'u': 'y', ' ': 'w', 'q': 'k'} Vigenère: un cfrario poli-alfabetico Il cifrario di Vigenère è un esempio di cifrario poli-alfabetico. Questo vuol dire che uno stesso carattere non è sempre soggetto alla stessa trasformazione. Le chiavi sono qui sequenze di caratteri dell'alfabeto, ciascuno dei quali deve essere interpretato come il numero corrispondente alla sua posizione nell'alfabeto (partendo da 0). Limitandoci all'alfabero inglese, possiamo affermare che, ad esempio, la chiave crypto, va interpretata come la sequenza di numeri 2,17,24,15,19,14 (dove abbiamo usato le virgole per evitare possibili ambiguità). Una volta operata questa corrispondenza, la chiave viene usata nel modo seguente: Il primo carattere del testo viene fatto slittare di 2 posizioni Il secondo carattere del testo viene fatto slittare di 17 posizioni... Il sesto carattere del testo viene fatto slittare di 14 posizioni Il settimo carattere del viene fatto slittare nuovamente di 2 posizioni... In [168… def sommachar(c1,c2): x = ord(c1)-ord('a') y = ord(c2)-ord('a') return chr((x+y)%26+ord('a')) In [169… sommachar('y','h') Out[169… 'f' Ad esempio, se il plaintext fosse algorithms (e la chiave sempre crypto), il ciphertext viene determinato nel modo seguente: key : c r y p t o c r y p plaintext : a l g o r i t h m s ciphertext : c c e d k w v y k h La decifrazione procede in modo analogo, usando la stessa chiave ma con slittamenti all'indietro. Il cifrario di Vigenère può essere analizzato in termini generali (e non come "sequenza" di cifrari di Cesare). Nel caso di Vigenère le porzioni di testo sottoposte a permutazione sono sequenze di lettere, dove questa volta è la lunghezza della chiave. k k La chiave permette dunque di calcolare la cifratura univoca di qualsiasi blocco composto da lettere. k La permutazione è dunque rappresentabile per esteso mediante una tabella di 26 k righe, una per ogni possibile blocco. L'esempio seguente mostra le righe iniziali e finali della tabella corrispondente alla chiave crypto, la cui lunghezza (numero di righe) è 26 6. = 308915776 plaintext ciphertext aaaaaa crypto aaaaab cryptp aaaaac cryptq...... yzzzzz aqxosn zzzzzz bqxosn Attacchi al cifrario di Vigenère  Senza l'ausilio dei computer, il cifrario era pressoché inattaccabile, in caso di chiave essenzialmente casuale. Rimane tutt'oggi difficilmente attacabile in caso di chiave casuale, di lunghezza confrontabile con il testo e non riutilizzata più volte. In quest'ultimo caso, il cifrario "degenera" infatti in una sorta di one-time pad testuale e il one-time pad, detto anche cifrario di Vernam, è l'unico matematicamente inviolabile (come vedremo subito). Se invece la chiave è relativamente corta rispetto al testo è possibile portare un attacco, la cui "prima fase" consiste proprio nell'individuazione della lunghezza della chiave. Si consideri, come esempio guida, il testo cifrato C = fxbxzktwrdvfcsfxbxqwplbn. Notiamo che la sequenza di 4 caratteri fxbx si ripete ad una distanza di 14 posizioni. La ripetizione può certamente essere l'identica "risultante" di differenti caratteri in testo e chiave, ma è pure possibile che essa sia dovuta ad una stessa sequenza nel testo in chiaro. Se questo è il caso, allora devono però essere uguali anche i caratteri della chiave in quelle posizioni. Ma allora, continuando con le deduzioni, o la chiave è lunga almeno 18 caratteri, con al suo interno delle ripetizioni, oppure la chiave ha una lunghezza che è un divisore di 14, il che, in questo caso, vuol dire lunghezza 2 o 7 o 14. Partendo da queste osservazioni, l'attaccante può tentare attacchi esaustivi con le lunghezze ammissibili più corte (sicuramente 2 ma anche 7, se l'alfabeto non è troppo grande) o attacchi basati su dizionario, nel caso delle lunghezze superiori. Ipotesi "di lavoro da parte di Eva": la chiave è lunga 7 Eva può tentare (almeno) 3 strade: Attacco brute force; pesante ma non impossibile perché le chiavi sono "soltanto"26 7 = 8031810176 , cioè approssimativamente 8 miliardi. Analisi delle frequenze: se il testo è abbastanza lungo Eva può stimare le frequenze considerando che due identici caratteri del testo cifrato corrispondono con certezza allo stesso carattere del plaintext se e solo se la loro posizione differisce di un multiplo di 7. Attacco basato sul dizionario: ipotizzando che la chiave non sia una sequenza casuale, Eva può provare tutte le parole di 7 lettere in un dizionario inglese. Se l'attacco basato sul dizionario è chiaramente "parato" mediante l'utilizzo di una chiave casuale, l'analisi delle frequenze richiede una buona dose di fortuna. Ad esempio, anche il carattere più frequente potrebbe non essere individuato se esso viene trasformato in molti caratteri diversi a causa di allineamenti "sfortunati"  (per Eva!) Attacco con l'uso del dizionario Supponiamo di sapere che la lingua del messaggio è l'inglese e che l'alfabeto sia Σ = { , a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z Usiamo l'elenco di parole presenti nel file cracklib-small del pacchetto Debian cracklib-runtime. Nel file ci sono circa 8K parole di 7 caratteri e un attaccante cercherà sicuramente una chiave nel dizionario. Vediamo (pur nella semplicità dell'esempio) come eseguire l'attacco Come prima cosa recuperiamo le parole di 7 lettere dal dizionario In [ ]: # /usr/share/dict/cracklib-small è un dizionario sul "mio computer". Può ess # necessario modificare il path with open('/usr/share/dict/cracklib-small', 'r') as f: W = {b.lower() for w in f if (b := w.strip().split("'")) and len(b)== print(len(W)) In [ ]: list(W)[1000:1020] Dopodichè definiamo solo l'operazione fondamentale per eseguire la decifrazione, ovvero lo slittamento all'indietro In [179… alphabet3 = " abcdefghijklmnopqrstuvwxyz" def leftrotate(x,y,alphabet): return alphabet[(alphabet.find(x)-alphabet.find(y))%len(alphabet)] In [180… leftrotate('c','h',alphabet3) # ruota 'c' di find('h') posizioni verso sx Out[180… 'v' Per evitare di dover controllare circa 8K possibili soluzioni, utilizziamo un modulo Python in grado di rilevare il linguaggio di una sequenza di testo from langdetect import detect_langs,detect Possiamo ora tentare l'attacco In [191… T = "fxbxzktwrdvfcsfxbxqwplbn" N = len(T) candidates = [] Q,R = N//7,N%7 for w in W: key = w*Q+w[:R]  plaintext = ''.join([leftrotate(T[i],key[i],alphabet3) for i in range(N) lang = detect_langs(plaintext) if len(lang)==1 and lang.lang=='en' and lang.prob>0.9999: candidates.append((plaintext,w)) --------------------------------------------------------------------------- NameError Traceback (most recent call last) Cell In, line 5 3 candidates = [] 4 Q,R = N//7,N%7 ----> 5 for w in W: 6 key = w*Q+w[:R] 7 plaintext = ''.join([leftrotate(T[i],key[i],alphabet3) for i in range(N)]) NameError: name 'W' is not defined In [183… len(candidates) # Una buona riduzione da poco più di 8K --------------------------------------------------------------------------- NameError Traceback (most recent call last) Cell In, line 1 ----> 1 len(candidates) NameError: name 'candidates' is not defined L'analisi finale dei plaintext candidati può essere fatta da un essere umano. In [ ]: for c in sorted(candidates,key=lambda p:p): print(c) One-time pad One time pad è "teoricamente" il cifrario più sicuro, anche se è affetto da molteplici problemi di natura pratica che lo rendono di fatto inutilizzabile. Il messaggio (plaintext) da cifrare è una stringa di bit (ed è naturalmente sempre P possibile considerarlo tale). La chiave è una sequenza di bit della stessa lunghezza del testo in chiaro: l' -esimo i bit della chiave viene messo in xor con il corrispondente bit del plaintext per ki pi produrre l' -esimo bit del ciphertext i ci ci = p i ⊕ k i , i = 0, 1, … , |P | − 1 Un semplice esempio key : 0 0 0 1 0 1 1 0 1 0 p : 1 0 1 1 0 0 1 0 0 1 c : 1 0 1 0 0 1 0 0 1 1  Per le proprietà del'or esclusivo, la decifrazione procede allo stesso modo, eseguendo cioè l'operazione con chiave e ciphertext: key : 0 0 0 1 0 1 1 0 1 0 c : 1 0 1 0 0 1 0 0 1 1 p : 1 0 1 1 0 0 1 0 0 1 Scelta della chiave Ogni bit della chiave deve avere valore 0 oppure 1 con uguale probabilità e in modo indipendente dal valore dei bit precedenti 1 prob[ki = 0] = prob[ki = 1] = prob[ki = v|ki−1 = w] = prob[ki = v], v, w ∈ 2 In questo modo, è immediato osservare che per i bit del messaggio cifrato valgono le stesse proprietà, indipendentemente da come sono scelti i bit del messaggio. Per la generica posizione (tralasciamo quindi gli indici per semplicità) vale infatti prob[c = 1] = prob[p ⊕ k = 1] = prob[p = 1 ∧ k = 0] + prob[p = 0 ∧ k = 1] = prob[p = 1] ⋅ prob[k = 0] + prob[p = 0] ⋅ prob[k = 1] = α ⋅ 0.5 + (1 − α) ⋅ 0.5 = 0.5 dove abbiamo indicato con la probabilità che il bit del messaggio sia 1. Lo stessa α conclusione vale ovviamente per la probabilità che il bit del testo cifrato sia 0. Si noti, in particolare, che l'uguaglianza precedente vale anche se o , α = 1 α = 0 cioè se il bit (e più in generale il messaggio) è deterministico. Sicurezza del one-time pad Se la chiave è scelta come indicato sopra ed è la lunghezza del plaintext, ogni n messaggio cifrato ha la stessa probabilità di essere trasmesso. 2 −n Questa è ovviamente il massimo di garanzia perché, rovesciando la prospettiva, per l'attaccante il messaggio "visto" può corrispondere ad uno qualsiasi dei possibili 2 n messaggi in chiaro, tutti con identica probabilità. 2 −n Tuttavia, se la chiave viene utilizzata più volte, l'attaccante può ottenere conoscenza sui messaggi (anche se non direttamente i messaggi in chiaro). Supponiamo, ad esempio, che due messaggi, e , siano stati cifrati usando la C1 C2 stessa chiave. Indicando con la stringa di tutti della stessa lunghezza della K O 0 chiave, abbiamo  C1 ⊕ C2 = (P1 ⊕ K) ⊕ (P2 ⊕ K) = (P1 ⊕ P2 ) ⊕ (K ⊕ K) = (P1 ⊕ P2 ) ⊕ O = P1 ⊕ P2 In questo modo l'attaccante viene a conoscenza dello xor dei due messaggi e dunque, conoscendone uno dei due (o parte di uno dei due) verrebbe a conoscere anche (parte de) l'altro. Obiettivi generali di sicurezza La precedente osservazione riguardo one-time pad ci porta a parlare degli obiettivi generali di sicurezza, almeno nel contesto della cifratura. Il primo obiettivo è, ovviamente, che Eva non sia in grado di comprendere i messaggi. Tuttavia questa è una formulazione troppo generica. Esistono più obiettivi di attacco da parte di Eva, di cui "capire il messaggio" non è neppure il più estremo. Ad esempio, determinare la chiave è ancora più ambizioso perché consente di mettere in chiaro uno o più messaggi. Un altro obiettivo consiste nel far passare per autentico un messaggio che invece Eva ha alterato o prodotto nella sua interezza. Indistinguibilità e non-malleabilità L'indistinguibilità è la proprietà di uno schema di cifratura i cui testi cifrati per un attaccante sono essenzialmente indistinguibili da stringhe di bit generate casualmente. Più precisamente, la proprietà viene descritta in termini di un gioco a due (Alice e Eva). Eva produce due messaggi in chiaro e li sottopone ad Alice; Alice decide, a caso e con uguale probabilità, quale dei due cifrare, e lo presenta ad Eva; Alice vince il gioco se Eva non riesce ad indovinare quale messaggio sia stato cifrato con probabilità significativamente maggiore di.1 Nel concreto questo vuol dire che Eva, dal suo punto di vista, non ha strategie 2 più efficaci rispetto a tirare a caso. Un secondo obiettivo è la non malleabilità. Uno schema di cifratura si definisce non malleabile se, dato un ciphertext C1 corrispondente ad un plaintext , risulta impossibile per Eva creare un secondo P1 ciphertext corrispondente ad un plaintext che abbia una qualche relazione C2 P2 con. P1 Si può intuire come la non malleabilità sia una proprietà che ha a che vedere con l'integrità dei messaggi.  A riguardo del protocollo one-time pad, possiamo affermare che esso, pur essendo sicuro dal punto di vista della indistiguibilità, risulta però un cifrario malleabile quando la chiave venga riutilizzata. Cifrari a blocchi I moderni cifrari simmetrici vengono detti a blocchi perché lavorano su blocchi di dati di lunghezza fissata. Indicheremo genericamente con il numero di bit di un blocco, un valore che B tipicamente si colloca nell'intervallo da 64 a 256. Se il plaintext ha lunghezza minore di , ad esso vengono preliminarmente aggiunti B bit di padding (riempimento). Viceversa, se il plaintext ha lunghezza superiore, esso viene suddiviso in più blocchi che vengono poi cifrati separatamente. Come già detto a suo tempo, il particolare algoritmo con cui i blocchi di uno stesso messaggio vengono cifrati, di modo che si possa poi ricostruire (in sede di decifrazione) il plaintext originale, viene detto mode of operation. Entrambi gli aspetti, padding e mode of operation, sono tutt'altro che banali ed errori di valutazione possono dare vantaggi decisivi ad un attaccante. Scelta di B I valori di indicati sopra derivano dalla necessità di bilanciare due esigenze B contrapposte. Da un lato deve essere un valore piccolo allo scopo di incrementare l'efficienza B facilitando implementazioni in hardware dedicato. D'altro canto, non può essere troppo piccolo per non incorrere in seri rischi di B sicurezza e (ancora dal punto di vista dell'efficienza) ridurre l'overhead legato al trattamento di molti messaggi corti; In particolare, se fosse troppo piccolo, un attaccante potrebbe precompilare una B tabella di posizioni in cui alla generica posizione è memorizzato il plaintext che 2 B i ha come ciphertext. i In tal caso, l'attacco (denominato codebook attack) corrisponderebbe poi ad un semplice table lookup. Se, ad esempio, fosse 32, la tabella avrebbe posizioni, ciascuna di 32 bit (4 B 2 32 byte), per un totale di 4 ⋅ 2 GB, cioè sarebbe del tutto gestibile. 32 = 16 Con B = 64 le dimensioni salirebbero a 2 67 byte, dunque senza ≈ 1.48 ⋅ 10 20 alcuna possibilità di precomputazione e memorizzazione. Sull'attacco codebook È lecito chiedersi: Come può l'attaccante precomputare i ciphertext, visto che non dispone della chiave?  Dopo aver ragionato sugli obiettivi generali di sicurezza, questa domanda ci porta a riflettere sui cosiddetti modelli di attacco. Un modello di attacco è essenzialente un'ipotesi su quelle che sono le armi in mano all'attaccante. Qui ragioneremo solo di modelli black box, in cui l'attaccante non ha accesso o non utilizza informazioni diverse da input e output (plaintext e ciphertext). Esistono anche tipi di attacco che sfruttano fenomeni fisici piuttosto che proprietà matematiche. Per quanto possa a prima vista apparire incredibile, informazioni come il tempo di esecuzione di operazioni su una chiave privata possono essere utilizzate per violare un critto-sistema. Attacchi di questo tipo, che però non potremo prendere in considerazione, vengono detti (attacchi) side-channel. Attack model L'assunzione più semplice è che l'attaccante veda solo il ciphertext e debba costruire l'attacco basandosi su quello. Questo modello di attaccante viene detto Ciphertext-only attacker (COA) COA è un modello in molti casi adeguato (almeno in crittografia simmetrica). Tuttavia, dal punto di vista del difensore, supporre che l'attaccante non conosca nulla al di fuori del testo cifrato può indurre ad abbassare pericolosamente "la guardia". È invece prudente assumere che l'attaccante sia sempre un passo avanti. In ordine di "potenza" crescente, il modello successivo è noto come Known- plaintext attacker (KPA), in cui l'attaccante (preliminarmente all'attacco) è stato in grado di osservare un certo numero di ciphertext con la conoscenza dei corrispondenti plaintext. Nei modelli precedenti, l'attaccante è comunque passivo perché non è lui/lei che determina quali testi cifrati ha possibilità di analizzare. Modelli più potenti prevedono che l'attaccante possa effettuare query. Il primo di tali modelli, in ordine di potenza, è il Chosen-plaintext attacker (CPA), in cui l'attaccante può eseguire le cosiddette encryption query, può cioè scegliere un testo in chiaro e ottenere il corripondente ciphertext. Si noti che questo (CPA) è il modello di riferimento nel caso della crittografia asimmetrica, in cui l'attaccante conosce la chiave di cifratura. L'ultimo modello prevede che l'attaccante possa eseguire, oltre alle encryption query, anche decryption query, possa cioè scegliere un ciphertext e vedere il corrispondente plaintext. Questo modello viene detto Chosen-ciphertext attacker (CCA). Uno schema astratto per descrivere i block cipher Cifratura e decifrazione richiedono una chiave segreta , la cui lunghezza k tipicamente è nel range fra 128 e 256 bit. Sappiamo che, matematicamente, la cifratura è una permutazione poiché plaintext e ciphertext sono composti dallo stesso numero di bit. Ad ogni possibile plaintext di bit deve cioè corrispondere un unico ciphertext di B B bit, e viceversa, altrimenti il procedimento non sarebbe reversibile. Può essere istruttivo visualizzare la cifratura come un processo in due fasi: 1. data la chiave , si seleziona una specifica lookup table , di posizioni, che k Tk 2 B memorizza una specifica permutazione delle sequenze di bit; B 2. la cifratura corrisponde ad un accesso a , usando il plaintext come chiave, Tk per recuperare il corrispondente ciphertext. Come semplice esempio, con B = 3 , a due differenti chiavi potrebbero corrispondere le seguenti tabelle. P base 10 P base 2 C P base 10 P base 2 C 010 000 011 010 000 100 110 001 010 110 001 001 210 010 111 210 010 000 310 011 110 310 011 111 410 100 001 410 100 110 510 101 000 510 101 011 610 110 101 610 110 010 710 111 100 710 111 101 * Naturalmente l'unica informazione delle due tabelle che viene effettivamente memorizzata è la colonna C (ciphertext). Le prime due colonne sono gli indici, rispettivamente in base 10 e in base 2, e rappresentano entrambe il plaintext. Una riflessione su chiavi e permutazioni Utilizzando il modello astratto possiamo ragionare quantitativamente sulle permutazioni effettivamente utilizzabili in un cifrario a blocchi e iniziare una riflessione su quali concretamente impiegare (e quali evitare). Sulla base del principio (che abbiamo enunciato in precedenza) in base al quale a chiavi diverse devono corrispondere permutazioni diverse, è immediato osservare che la lunghezza della chiave determina il numero di lookup table, e dunque di permutazioni, che possono essere utilizzate in un cifrario a blocchi con chiavi di quella lunghezza. Se dunque la chiave è lunga bit, il numero di permutazioni usabili è. k 2 k  Questo valore, apparentemente "grande" (perché esponenziale nella lunghezza della chiave), deve essere visto sullo sfondo del numero totale di permutazioni di B bit. Quest'ultima è una quantità che cresce molto più velocemente con : essa è infatti B pari a (cioè il fattoriale di ). 2 B ! 2 B È interessante verificare quanto dovrebbe essere lunga la chiave per poter utilizzare tutte le permutazioni, in funzione di valori crescenti di. B Con l'aiuto di Python, analizziamo i casi 2 ≤ B ≤ 7 (cioè per blocchi di lunghezza così corta da essere del tutto improponibili in un cifrario reale). In [ ]: from math import factorial,log,log10 print("Valore di B\tNumero di permutazioni\tLunghezza minima della chiave") for B in range(2,8): v = factorial(2**B) if B>3: e = int(log10(v)) m = int(10*(v*10**(-e)))/10 s = f"{m}e{e}" else: s = str(v) print(f"{B}\t\t{s}\t\t\t{int(B*2**B*log(2))}") Interessante anche l'analisi in qualche modo "inversa". Fissiamo cioè una dimensione realistica per la chiave e valutiamo la frazione di permutazioni utilizzabili (rispetto a tutte quelle possibili) al crescere della dimensione dei blocchi. B Ad esempio, con chiavi di 128 bit possiamo usarle tutte solo se B ≤ 5 , dopodiché la frazione di permutazioni utilizzabili diviene rapidamente trascurabile. In [ ]: k = 128 for B in range(5,9): print(f"Frazione di permutazioni utilizzabili con chiavi di {k} bit e "+ f"blocchi di {B} bit: {min(1,2**k/factorial(2**B))}") Quali permutazioni usare? Abbiamo visto che delle permutazioni possibili se ne può usare solo una minuscola frazione. D'altra parte molte permutazioni non andrebbero bene comunque. Ad esempio, le 26 possibili permutazioni usate dal cifrario di Cesare, associate alle 26 possibili chiavi, sono semplici rotazioni, dunque di facile inversione. Delle due permutazioni di sequenze di tre bit presentate nelle tabella riportate sopra (che qui vengono nuovamente riprodotte per comodità) quella di destra non va sicuramente bene perché (quantomeno) rivela sempre il bit meno significativo del plaintext.  P base 10 P base 2 C P base 10 P base 2 C 010 000 011 010 000 100 110 001 010 110 001 001 210 010 111 210 010 000 310 011 110 310 011 111 410 100 001 410 100 110 510 101 000 510 101 011 610 110 101 610 110 010 710 111 100 710 111 101 In generale non vanno bene permutazioni che possono essere espresse mediante trasformazioni lineari affini invertibili sul campo Z2 xP + b = y(x) in cui è una matrice non-singolare di ordine su , mentre (il plaintext), e P B Z2 x b y(x) (il ciphertext) sono vettori riga di elementi, sempre con elementi in. B Z2 Ad esempio, la matrice di sinistra nelle tabelle è rappresentabile come trasformazione lineare affine con 0 1 0 ⎛ ⎞ P = ⎜1 0 0⎟ ⎝ ⎠ 0 0 1 e b = (0 1 1) Se la trasformazione è realizzata come permutazione lineare affine è infatti possibile, nel modello CPA, ricostruire e e dunque invertire la trasformazione b P stessa. Infatti semplicemente è l'immagine di (vettore di tutti zeri). b O y(O) = O ⋅ P + b = O + b = b ed è quindi sufficiente, per determinarlo, effettuare la query che chiede il ciphertext corrispondente al blocco di tutti 0. Una volta noto , siamo in grado di determinare esplicitamente con le sole ulteriori b P query in cui i blocchi da cifrare sono ei = (0, … , 0,. 1 , 0, … , 0) Scrivendo tutte le query in forma matriciale abbiamo: indice i B I ⋅ P = y(I )  ovvero P = y(I ) In altri termini, la risposta alle query ordinate, è proprio la matrice di B trasformazione , che possiamo efficientemente invertire. P Combinazioni lineari affini in Z2 Sul campo il numero di matrici invertibili è dato dalla seguente formula, di Z2 derivazione relativamente semplice n−1 n i n n n 2 n n−1 ∏ (2 − 2 ) = (2 − 1)(2 − 2)(2 − 2 )... (2 − 2 ) i=0 Il seguente codice Python ne implementa il calcolo. In [ ]: from math import factorial In [ ]: def PermInvGF2(n): v = 1 pow = 1 1 possiamo immediatamente concludere che x −1 non esiste. mod n Altrimenti (se cioè ), riscrivendo l'uguaglianza m = 1 1 = a ⋅ x + b ⋅ n nel modo seguente  a ⋅ x = 1 − b ⋅ n e riducendo entrambi i membri modulo , otteniamo n (a ⋅ x) mod n = 1 e questo vuol proprio dire che a = x −1. mod n In [ ]: m,a,b = extended_Euclid(5,7) print(a) (a*5)%7 # a è l'inverso di 5 modulo 7 Si noti però che potrebbe essere un valore negativo. In tal caso un'ulteriore a operazione modulo restituisce l'inverso come numero propriamente di n Zn In [ ]: m,a,b = extended_Euclid(5,31) print(a) print(a*5%31) # a è comunque l'inverso print(a%31) # Se vogliamo l'inverso come elemento di Z_31 Possiamo quindi definire una funzione modular_inverse che usa l'algoritmo di Euclide esteso ed esegue l'operazione modulare finale In [ ]: def modular_inverse(x,n): '''Computes 1/x mod n, if exists''' m,a,b=extended_Euclid(x,n) if m == 1: return a%n In [ ]: modular_inverse(5,31) Teorema cinese dei resti Questo "teorema" dell'aritmetica modulare (ascritto al matematico cinese Sun-Tsu, intorno all'anno 100) ha importanti utilizzi in crittografia. Lo ritroveremo come strumento teorico in alcuni protocolli ma, almeno nel caso dell'RSA, anche come utile strumento per ridurre il tempo di calcolo nelle operazioni di cifratura. Ecco l'enunciato del teorema. Sia un numero intero esprimibile come prodotto di n r > 1 numeri interi fra loro relativamente primi n = n1 ⋅ n2 ⋅ … ⋅ nr Allora il resto della divisione di un qualsiasi intero per è a n completamente determinato dai resti delle divisioni per. In altri termini, esiste una corrispondenza n1 , n2 , … ; nr biunivoca fra e il prodotto cartesiano Zn Zn 1 × Zn 2 × … × Zn r. La dimostrazione è costruttiva. Dato un valore , la -upla corrispondente si trova facilmente: a ∈ Zn r a ⟶ (a mod n1 , a mod n2 , … , a mod nr ) Ad esempio se n = 4 ⋅ 7 ⋅ 9 = 252 e a = 3413 , risulta a ⟶ (1, 4, 2). In [ ]: n1=4 n2=7 n3=9 n = n1*n2*n3 print(n1,n2,n3,n) In [ ]: a = 3413 a1=a%n1 a2=a%n2 a3=a%n3 print(f"{a%n} --> ({a1},{a2},{a3})") Per la trasformazione inversa, l'idea è di "trovare" coefficienti ci ∈ {0, 1} tali che la combinazione lineare: C = c1 a 1 + c2 a 2 + … + cr a r verifichi la proprietà che , C mod ni = ai. In tal caso, per un semplice i = 1, … , r argomento legato alla cardinalità dei due insiemi, potremo concludere che. C = a Per trovare tali coefficienti si procede nel modo indicato di seguito. ci 1. Per i = 1, 2, … , r calcoliamo le quantità , dove cioè è il m i = ∏ nj mi j≠i prodotto di tutti i moduli ad eccezione proprio dell' -esimo. i ni 2. Per "costruzione" MCD(mi , ni ) = 1, e dunque esiste l'inverso m ,−1 mod ni che possiamo calcolare utilizzando l'algoritmo di Euclide esteso. i 3. I valori e i loro inversi consentono ora di definire i valori con le mi ci caratteristiche richieste: −1 ci = mi ⋅ (m mod ni ) Risulta infatti, per , i j ≠ i ci mod nj = 0 perché è multiplo di ci nj E risulta invece −1 −1 ci mod ni = (mi ⋅ (m mod ni )) mod ni = (mi ⋅ m ) mod ni = 1 mod ni = 1 i i  Se dunque poniamo , risulta r C = ∑ ci a i i=1 C mod ni = ai , i = 1, … , r Dunque ha gli stessi resti di , modulo ciascuno degli. C a ni Poiché la cardinalità del prodotto cartesiano Zn 1 × Zn 2 × … × Zn rè la stessa di Zn deve necessariamente risultare. In caso contrario ci dovrebbe essere C = a almeno un elemento di cui non corrisponde nessuna -upla in Zn r Zn 1 × Zn 2 × … × Zn r , il che è chiaramente falso. In [ ]: # Moduli e loro prodotto n1 = 27 n2 = 40 n3 = 11 n = n1*n2*n3 print(f"n={n}\tn1={n1}\tn2={n2}\tn3={n3}") # Coefficienti per la trasformazione inversa m1 = n2*n3 m2 = n1*n3 m3 = n1*n2 invm1=modular_inverse(m1,n1) invm2=modular_inverse(m2,n2) invm3=modular_inverse(m3,n3) c1 = m1*invm1 c2 = m2*invm2 c3 = m3*invm3 print(f"c1={c1}\tc2={c2}\tc3={c3}") In [ ]: c1%n3 Si noti che tutto ciò che abbiamo fatto sinora è rubricabile come "pre- computazione". I calcoli dipendono cioè solo dal modulo e dai divisori coprimi. n ni Se dobbiamo eseguire molti calcoli in , le quantità pre-determinate ovviamente Zn non cambiano Supponiamo, ad esempio, di voler calcolare la seguente funzione per diversi valori del parametro: 2 f (x) = (5x − 12x + 1) mod n Dato , invece di calcolare , calcoliamo a f (a) fa = f (ai ) mod n1 , i = 1, … r e poi "ricostruiamo" grazie al teorema cinese del resto. i f (a) In [ ]: a = 5191 a1 = a%n1 a2 = a%n2 a3 = a%n3 print(f"a={a}\t\ta1={a1}\ta2={a2}\ta3={a3}") fa = (5*a**2-12*a+1)%n fa1 = (5*a1**2-12*a1+1)%n1 fa2 = (5*a2**2-12*a2+1)%n2 fa3 = (5*a3**2-12*a3+1)%n3 print(f"fa={fa}\tfa1={fa1}\tfa2={fa2}\tfa3={fa3}") C = (c1*fa1+c2*fa2+c3*fa3)%n print(f"C={C}") Gruppi e gruppi ciclici e Zn Z ∗ n L'operazione di somma modulare in gode (fra le altre) delle seguenti quattro le Zn proprietà 1. Chiusura: la somma di due elementi di è ancora un elemento di Zn Zn 2. Associatività: (a +n b) +n c = a +n (b +n c) 3. Esistenza el. neutro: chiaramente lo 0 4. Esistenza inverso: l'inverso (o opposto) di è x n − x L'insieme , rispetto all'operazione di somma modulare, è dunque un gruppo Zn Che cosa possiamo dire invece della "struttura" di rispetto alla moltiplicazione? Zn Sappiamo che se è composto non tutti gli elementi di hanno inverso n Zn moltiplicativo. Se dunque è composto, l'insieme non è un gruppo rispetto alla moltplicazione n Zn modulare. Sappiamo però che l'inverso è posseduto dagli elementi che sono coprimi x ∈ Zn con n... e l'insieme di tali elementi forma effettivamente un gruppo rispetto alla moltiplicazione modulare. Si usa indicare tale insieme con la scrittura. Zn ∗ Ad esempio, i numeri di che sono coprimi con 12 sono 1, 5, 7 e 11. Allora Z12 ∗ Z12 = {1, 5, 7, 11} è un gruppo moltiplicativo. Come esercizio, si verifichi dapprima che è un gruppo rispetto alla ∗ Z12 moltiplicazione modulate e poi si provi a dimostrare il fatto in generale per. ∗ Zn Se è primo è un campo n Zn Ovviamente, se è primo, tutti gli elementi di , ad eccezione dello zero, sono n Zn coprimi con e dunque hanno inverso. n Poiché vale (banalmente) anche la proprietà distributiva della moltiplicazione rispetto all'addizione, se è primo allora è un campo finito (o campo di Galois) n Zn Ordine di un elemento in un gruppo Consideriamo un generico elemento di un gruppo. x G Si chiama ordine di il minimo numero di volte che possiamo sommare/moltiplicare x x all'elemento neutro prima di ottenere come risultato nuovamente l'elemento neutro.  Più difficile da spiegare che da capire con semplici esempi. Nel gruppo additivo l'operazione è l'addizione e l'elemento neutro è lo zero. In Z12 tal caso (tralasciando l'indicazione del modulo per semplicità): 1. l'ordine di 2 è 6 perché(((((0 + 2) + 2) + 2) + 2) + 2) + 2 = 0 (cioè applicando 6 volte l'addizione modulare si ottiene 0) e con un minore di addizione non si ottiene 0. 2. L'ordine di 7 è 12; infatti 0 + 7 = 7 7 + 7 = 2 2 + 7 = 9 9 + 7 = 4 4 + 7 = 11 11 + 7 = 6 6 + 7 = 1 1 + 7 = 8 8 + 7 = 3 3 + 7 = 10 10 + 7 = 5 5 + 7 = 0 Nel gruppo moltiplicativo (elemento neutro 1): ∗ Z7 1. l'ordine di 2 è 3 perché e con un numero minore di ((1 ⋅ 2) ⋅ 2) ⋅ 2 = 1 moltiplicazioni non si ottiene 1; 2. l'ordine di 3 è 6 perché 1 ⋅ 3 = 3 3 ⋅ 3 = 2 2 ⋅ 3 = 6 6 ⋅ 3 = 4 4 ⋅ 3 = 5 5 ⋅ 3 = 1 Gruppi ciclici e generatori Il numero di elementi che fanno parte di un gruppo è poi detto ordine di stesso, G G e viene indicato con ord(G) : per l'ordine è 12 mentre per l'ordine è 6. Z12 Z7 ∗ Un gruppo si dice ciclico se esiste un elemento il cui ordine coincide con l'ordine g del gruppo. ord(g) = ord(G) Tale elemento viene detto generatore del gruppo (proprio perché con operazioni successive si ottengono tutti gli elementi del gruppo) o anche radice primitiva In base agli esempi precedenti possiamo quindi dire che 7 è un generatore del gruppo additivo e che 3 è un generatore del gruppo moltiplicativo Z12 Z7 ∗  I gruppi additivi e moltiplicativi , con primo, sono gruppi ciclici. Zn Zn ∗ n Consideriamo ora, per fissare le idee, gruppi moltiplicativi Se è un generatore, vale chiaramente g ∗ i Zp = {g mod p|i = 1, … , p − 1} Per un elemento di ordine h (cioè un elemento che non è un generatore) s < p − 1 è comunque interessante considerare l'insieme: i H = {h mod p|i = 1, … , s} È facile dimostrare che è un sottogruppo ciclico di. H ∗ Zp Sottogruppo vuol dire che è un sottoinsieme di e che è un gruppo! G Va da se che ogni sottogruppo, per essere tale, deve comunque incudere 1. h è chiaramente il generatore del sottogruppo e, se (per un qualche i x = h mod p i ≤ s ), allora, banalmente x −1 mod p = h , proprio perché s−i mod p −1 i s−i s x ⋅ x mod p = x ⋅ x mod p = x mod p = 1 In [ ]: from ACLIB.utils import Euclid, modexp In [ ]: def ord(h,p): if h == 1: return 1 v = h o = 2 while (v:=(v*h)%p) and v!=1: o+=1 return o In [ ]: p = 47 for i in range(1,p): print(i,ord(i,p)) In [ ]: def subgroup(h,p): return [(h**i)%p for i in range(1,ord(h,p)+1)] In [ ]: subgroup(2,11) Teorema di Lagrange e teorema fondamentale dei gruppi ciclici Teorema di Lagrange Qualsiasi sottogruppo di un gruppo di ordine ha necessariamente ordine che è un divisore di. k k Per i gruppi ciclici esiste un risultato più forte.  Teorema fondamentale dei gruppi ciclici Per ogni divisore k dell'ordine del gruppo esiste uno ed un solo sottogruppo di ordine k Esempio: I sottogruppi di sono elencati di seguito, con l'aiuto di un semplice ∗ Z19 programma Python. Si tenga presente che ha ordine 18 e che i divisori non ∗ Z19 banali di 18 sono 2, 3, 6 e 9. In [ ]: p = 19 subgroups = sorted([(h,subgroup(h,p)) for h in range(2,p)], key=lambda pair: for H in subgroups: print(f"Generatore: {H}\tOrdine: {len(H)}\tSottogruppo: {sorted(H[ Primi sicuri (safe prime) Per ragioni che saranno chiare non appena esamineremo il primo protocollo di scambio di chiavi, numeri primi molto importanti sono quelli della forma:p = 2q + 1 , dove anche è primo. q Esempi di tali numeri, detti primi sicuri, sono: 11, 23, 59 e 83. Per un tale numero, il teorema di Lagrange garantisce che i sottogruppi non banali possono avere solo 2 o elementi. q Sappiamo però anche di più (perché abbiamo a che fare con gruppi ciclici) e cioè che esiste un solo sottogruppo di ordine 2 e un solo sottogruppo di ordine. q Vediamo un esempio esaustivo nel caso di p = 23 In [ ]: p = 23 subgroups = sorted([(h,subgroup(h,p)) for h in range(2,p)], key=lambda pair: for H in subgroups: print(f"Generatore: {H}\tOrdine: {len(H)}\tSottogruppo: {sorted(H[ Dall'esempio di vede anche che, se tralasciamo il sottogruppo generato da 22 (che naturalmente è {1, −1 mod 23} = {1, 22} ), ci sono esattamente metà elementi che generano il gruppo intero e metà che generano il sottogruppo di ordine.q Questa è una situazione generale e possiamo anche affermare che, per i primi sicuri (ed escludendo naturalmente 1 e -1), è facile stabilire da che cosa sia formato il sottogruppo di elementi. q Esso è composto precisamente da quegli elementi che sono l'equivalente (in aritmetica modulare) dei quadrati perfetti e che qui vengono detti residui quadratici (modulo )p Per continuare con l'esempio di , il numero è un residuo quadratico perché ∗ Z23 3 (7 ⋅ 7) mod 23 = 3 Se il modulo è primo si può poi dimostrare che ogni quadrato perfetto ha esattamente due radici (come nel caso reale) che sono una l'opposta dell'altra.  La seconda "radice quadrata" di in 3 ∗ Z23 è dunque 23 − 7 = 16 In [ ]: (16**2)%23 Nel caso di primi sicuri, e se escludiamo 1 e -1, il teorema di Lagrange garantisce che un qualsiasi elemento genera o l'intero gruppo o il sottogruppo dei residui quadratici. E sempre grazie al teorema di Lagrange risulta facile capire, per un elemento x scelto a case (e diverso da 1 e -1), in quale caso ci si trovi. Infatti, sapendo che l'ordine di può solo essere o , è sufficiente calcolare x q p − 1 (nel modo che vedremo) x q mod p. Se il risultato è 1, allora l'ordine di è e dunque genera il sottogruppo, altrimenti x q x genera l'intero gruppo ∗ Zp Nella libreria OPENSSL si adotta un approccia ancora più estremo, in cui il generatre è fisso Infatti, quando richiesto di generare un safe prime, OPENSSL restituisce un valore p tale che, per default, 2 è sempre un generatore del gruppo. L'utente ha solo la Z ∗ possibilità di richiedere un diverso generatore, ma solo 3 o 5. p In [ ]: %%sh openssl dhparam -text 2048 In [ ]: %%sh ls -ltr In [ ]: %%sh openssl dhparam -outform PEM -out dhcert.pem 2048 openssl dhparam -inform PEM -in dhcert.pem -check -text Un funzione candidata one-way: l'esponenziale modulare Una computazione fondamentale in crittografia asimmetrica riguarda il calcolo della funzione esponenziale modulare. Per essere one-way la funzione deve essere innanzitutto (computazionalmente) facile da calcolare. Dobbiamo quindi capire se sia possibile calcolare in maniera efficiente quantità del tipo a b. mod n Il problema è delicato per via della grandezza dei numeri in gioco. In applicazioni crittografiche, sia che (oltreché ), possono essere dell'ordine del a b n migliaio di bit ma, giusto per fornire un'idea, supponiamo che la lunghezza sia limitata a 128 bit.  In tal caso è un numero che può arrivare ad avere una quantità di bit pari a a b 128 128 128 2 128⋅2 128 135 log (2 ) = log 2 = 128 ⋅ 2 = 2 2 2 che corrispondono a più di cifre decimali. Evidentemente non esiste alcuna 10 40 possibilità di manipolare numeri di tale grandezza! Poiché però il risultato finale è un numero di "soli" 128 bit, si capisce che bisognerà utilizzare le proprietà dell'aritmetica modulare (che abbiamo visto) per limitare la grandezza dei risultati intermedi. Questo per quanto riguarda lo spazio. Anche il tempo però è un problema se si adotta l'algoritmo "banale" che calcola a b (sia pure con le opportune riduzioni modulo dei risultati intermedi) come prodotto n iteratoa × a × … × a.  In tal caso, infatti, si eseguono esattamente b−1 prodotti modulari moltiplicazioni modulari, una b − 1 quantità improponibile se ha anche "solo" 128 bit. b Prodotto modulare L'esponenziale è basata comunque sul prodotto e dunque introduciamo prima un algoritmo per il calcolo della quantità a ⋅ b mod n Tutto ciò non è inutile anche perché la tecnica è la stessa che adotteremo per l'esponenziale. Questo non dovrebbe sorprendere per il semplice motivo che, come l'esponenziale è un'iterazione della moltiplicazione, il prodotto è un'iterazione della somma. Possiamo infatti calcolare come a ⋅ b , cosa che però vogliamo a + a + … + a  evitare. b−1 addizioni modulari Presentiamo l'algoritmo utilizzando come esempio il calcolo di z = a ⋅ b , con b = 26. 1. Scriviamo in base 2, b 4 3 1 2610 = 110102 = 2 + 2 + 2 2. Utilizzando ora la proprietà distributiva abbiamo 4 3 1 4 3 1 a ⋅ b = a ⋅ 26 = a ⋅ (2 + 2 + 2 ) = a ⋅ 2 + a ⋅ 2 + a ⋅ 2 3. Tutte le quantità del tipo , sia quelle utilizzate nel prodotto (ovvero quelle a ⋅ 2 k con k = 1, 3, 4) sia quelle che "non servono" ( ), possono essere k = 0, 2 calcolate partendo da e raddoppiando il valore ad ogni a0 = a ⋅ 2 0 = a iterazione: ak+1 = 2 ⋅ ak 4. Ad inizio poniamo e ad ogni iterazione sommiamo a se e solo se z = 0 ak z ak "serve", cioè se il -esimo bit di è 1. k b  Nel codice Python che segue: (1) le moltiplicazioni per 2 sono eseguite mediante shift, (2) dopo ogni operazione viene eseguita la riduzione modulo , e (3) i bit di n b vengono rivelati mediante successive divisioni per 2, calcolate ancora mediante shift. In [ ]: def modprod(a,b,n): '''Computes the product ab mod n using additions and shifts only. For the computation of remainders x mod n, we note that x is always less than 2n (except possibly for the input parameters a and b). Hence integer division is not required. ''' def easymod(x): 'x 0 La riscrivo in modo (forse) più immediatamente comprensibile.  prob[A(x) ritorna primo|x è primo] = 1 e prob[A(x) ritorna composto|x è composto] ≥ ϵ La probabilità che l'algoritmo sia corretto quando il numero è composto è dunque limitata inferiormente, indipedentemente dalla grandezza del numero in input. Supponiamo ora che risulti. ϵ = 0.01 Si può certamente obiettare che avere una probabilità di successo (su numeri composti) garantita dell'ordine di non è poi un grande risultato. 10 −2 Tuttavia se la sorgente produce bit indipendenti possiamo aumentare la probabilità di successo in modo arbitrario, come indichiamo di seguito Run indipendenti A partire da si costruisce un algoritmo nel modo seguente. A A ′ Si eseguono run identici di. N A Non appena uno di tali run restituisce valore , anche termina restituendo il True A ′ valore. True Se invece, in tutti gli run, restituisce , allora anche termina restituendo N A False A ′ il valore. False Ci chiediamo quindi che cosa si può dire della correttezza di in funzione del A ′ valore. N Se l'input è primo, ovviamente produrrà sempre il valore , e dunque A False (indipendentemente da come si è scelto ) anche restituisce. N A ′ False Se invece il numero è composto, poiché i run sono eseguiti utilizzando sequenze di bit indipendenti, la probabilità che l'algoritmo restituisca volte False è limitata N superiormente dal prodotto delle singole probabilità:. (1 − 0.01) N = 0.99 N Per N = 2 risulta 0.99 2 = 0.98 Se il procedimento viene ripetuto 69 volte, con input un numero composto, la probabilità che sbagli tutte le volte ?