Qualche giorno fa, durante un'estemporanea visita su FB, mi è caduto l'occhio su uno spiritoso commento di una mia amica di origine austriaca: siccome era la giornata del tedesco si era divertita a pubblicare una parola piuttosto lunga in tale lingua: “Bundespräsidentenstichwahlwiederholungsverschiebung” di ben 51 caratteri...Scherzosamente io avevo commentato che tale parola, scritta al contrario e con l'aggiunta di qualche numero, avrebbe potuta essere una buona parola chiave.
L'amica mi aveva risposto un po' sconsolata (o almeno avevo così interpretato la faccina triste con cui aveva concluso la sua replica) che tale parola chiave avrebbe solo allungato di poco il tempo necessario a un algoritmo di forza brutta per individuarla.
Sul momento non feci troppo caso alla sua risposta ma poi, ripensandoci, mi sono reso conto che era seria e che, a chi non ha fatto studi di informatica, alcuni concetti possono non essere chiari: in questo caso la relazione che intercorre fra gli algoritmi di forza bruta (AFB) e la lunghezza delle parole chiave.
Prima di tutto una premessa: per semplicità con AFB intenderò qui e nel seguito un algoritmo che cerca di individuare la parola chiave corretta semplicemente formando tutte le combinazioni possibili, di lunghezza crescente, utilizzando un insieme preciso di caratteri alfanumerici e simboli.
In realtà difficilmente le persone usano parole chiave costituiti da una sequenza di caratteri equiprobabili, tipo ij4208fMn o mnf4329[}r9T2s, ma usano parole di senso compiuto, composte o comunque che abbiano almeno un suono eufonico. Questo permette di scrivere varianti di AFB notevolmente più efficienti anche se, almeno per me, è difficile stimare di quanto...
Il problema di un algoritmo AFB è che dovendo generare tutte le parole chiave deve avere necessariamente una complessità pari al loro numero.
Qualche esempio: supponiamo di aver a disposizione solo 3 caratteri (a, b e c) quante parole chiave di lunghezza 1 possiamo ottenere? Semplicemente tre: “a”, “b” e “c”.
E quante di lunghezza due?
Aa, ab, ac, ba, bb, bc, ca, cb e cc. Ovvero 9.
E di lunghezza tre?
Aaa, aab, aac, aba, abb, abc, aca, acb, acc, baa, bab, bac, bba, bbb, bbc, bca, bcb, bcc, caa, cab, cac, cba, cbb, cbc, cca, ccb e ccc. Se non ho fatto errori dovrebbero essere 27.
La formula per trovare il numero di parole di una certa lunghezza è quindi pari al numero di simboli utilizzabili elevato al numero di caratteri usati: quindi 3^1=3, 3^2=9 e 3^3=27
Il numero di parole che AFB deve generare dovrà quindi essere a sua volta esponenziale.
Si potrebbe pensare: “E il problema dov'è? Tanto i calcolatori moderni sono velocissimi...”
Il problema lo vediamo subito: supponiamo che per individuare una chiave di 20 lettere un calcolatore necessiti di 1 secondo. Quanto tempo gli occorrerebbe per scoprire una chiave di 21 caratteri?
Come abbiamo visto dipende dalla dimensione dell'alfabeto utilizzabile: quindi 26 lettere che diventano 52 considerando maiuscole e minuscole, più le 10 cifre, più almeno altri 28 caratteri (tipo + - = $ % etc...) che si ottengono facilmente con la tastiera. In totale abbiamo un alfabeto di 90 simboli.
Questo significa che il numero di parole di lunghezza 21 sarà 90 volte maggiore di quelle di lunghezza 20. Siccome AFB necessità di un tempo proporzionale al numero di parole allora impiegherà non 1 secondo ma 90 secondi: ovvero 1 minuto e mezzo.
Sembrerebbe quindi che la mia amica abbia ragione: ovvero che allungando la lunghezza della parola chiave gli AFB ci mettano solo qualche minuto in più per individuarla...
Ma se la parola chiave invece che di 21 caratteri fosse di 22? Quanto tempo impiegherebbe per individuarla? Ovviamente 90x90 (cioè 90^2) secondi: ovvero 8100 secondi, cioè 135 minuti, ovvero 2 ore e 15 minuti. Insomma trovare la parola chiave non è più così immediato: si può andare a mangiare una pizza mentre il calcolatore è impegnato...
Sì, ma l'organizzazione XXX non ha mica solo un calcolatore, ne ha cento che possono lavorare contemporaneamente sulla stessa parole chiave!
D'accordo: anzi supponiamo che l'organizzazione XXX non abbia 100 calcolatori disponibili ma 1000. Questo significa che per trovare una parola chiave impiegherebbe un millesimo del tempo necessario usando solo un calcolatore.
Questo significa che:
Parola lunghezza 20 → non 1 secondo ma un millesimo di secondo
Parola lunghezza 21 → non 90 secondi ma 90 millesimi di secondo
Parola lunghezza 22 → non 8100 secondi ma 8,1 secondi
Ma se la parola fosse lunga 25 caratteri?
Allora i mille calcolatori avrebbero bisogno di 8,1 secondi moltiplicato 90*90*90 (*1) e cioè 5.904.900 secondi, cioè 98.415 minuti, cioè 1.640 ore, cioè 68 giorni...
Ecco che, sebbene fattibile, inizia a essere un fastidioso inconveniente individuare una parola chiave di 25 caratteri...
Il lettore scettico potrebbe avere ancora qualche perplessità e pensare che magari l'NSA con i suoi supercalcolatori non avrebbe problemi a usare un AFB per individuare parole chiave (siamo nell'ipotesi che siano completamente casuali!) anche molto lunghe.
Supponiamo che l'NSA possa individuare una parola chiave di 20 lettere in un miliardesimo di secondo, ovvero un milione di volte più velocemente che mille calcolatori.
Di quanto tempo avrebbe bisogno per individuare una parola di 30 caratteri?
Ormai sappiamo che calcoli fare: un miliardesimo di secondo moltiplicato 90^10 (90 elevato 10).
Ovvero 5.904.900.000 x 5.904.900.000 miliardesimi di secondi: ovvero 34.870.000.000 secondi, cioè 403.570 giorni, cioè 1.105 anni. Ovvero, se si inizia nel 2017 si finisce nel 3122...
E se la parola chiave fosse lunga 51 caratteri (da cui la mia battuta originaria)?
Basta moltiplicare un miliardesimo di secondo per 90^(51-20)=90^31 oppure, un pelino più facile, 1.105 anni moltiplicato 90^21.
Che, ora che ci penso, equivale a 1.105x1.105x1.105x90 ovvero 121.430.936.300: appena 121 miliardi di anni, ovvero un po' più di 8 volte l'età dell'universo!!
Conclusione: la morale è che gli algoritmi di complessità esponenziale (come l'AFB versione base che abbiamo considerato qui) NON sono buoni: non importa quanto sia veloce il vostro calcolatore perché si impallerà comunque...
Nota (*1): o, se preferite, 1 millesimo di secondo moltiplicato 90*90*90*90*90...
Nessun commento:
Posta un commento