Quante password di otto caratteri esistono? Quanti indirizzi può avere una rete? Quanti tentativi servono, al massimo, per indovinare un PIN? Sono domande di conteggio, e quasi tutte si risolvono combinando poche regole elementari. Il calcolo combinatorio sembra a volte una raccolta di formule da imparare a memoria; in realtà le formule derivano tutte da questi principi, e chi li padroneggia può ricostruirle quando servono.
Regola del prodotto
Se un'operazione si compone di due fasi, la prima eseguibile in m modi e la seconda in n modi indipendentemente dalla scelta fatta nella prima, allora l'operazione completa si può eseguire in m · n modi.
La regola si estende a k fasi: n₁ · n₂ · … · nₖ.
Esempi:
- Un PIN di 4 cifre: 10 · 10 · 10 · 10 = 10⁴ = 10.000 possibilità.
- Una password di 8 caratteri scelti tra 26 lettere minuscole: 26⁸, circa 2,09 · 10¹¹.
- Un menù con 3 primi, 4 secondi e 2 dolci: 3 · 4 · 2 = 24 pasti diversi.
La regola del prodotto è la stessa che dà la cardinalità del prodotto cartesiano: |A × B| = |A| · |B|.
Regola della somma
Se un oggetto si può scegliere da un primo gruppo in m modi oppure da un secondo gruppo in n modi, e i due gruppi sono disgiunti (nessun oggetto sta in entrambi), allora le scelte totali sono m + n.
Esempio: una password di lunghezza compresa tra 6 e 8 caratteri minuscoli. Le password di lunghezza diversa sono casi disgiunti, quindi il totale è 26⁶ + 26⁷ + 26⁸.
Se i gruppi non sono disgiunti la somma conta due volte gli elementi comuni; in quel caso serve il principio di inclusione-esclusione.
Combinare le due regole
Quasi ogni problema reale richiede di alternare somma e prodotto. Un metodo affidabile:
- dividere i casi in modo che siano disgiunti (regola della somma);
- contare ciascun caso come sequenza di scelte indipendenti (regola del prodotto).
Esempio: un codice identificativo è formato da 2 lettere seguite da 3 cifre, oppure da 3 lettere seguite da 2 cifre (alfabeto di 26 lettere). Primo tipo: 26² · 10³ = 676.000. Secondo tipo: 26³ · 10² = 1.757.600. I due tipi sono disgiunti, perché la posizione del primo numero è diversa. Totale: 2.433.600.
Regola del complemento
Spesso è più facile contare ciò che non si vuole e sottrarlo dal totale.
Domanda: quante password di 8 caratteri, scelte tra 26 minuscole e 10 cifre, contengono almeno una cifra?
Contare direttamente «almeno una» è scomodo: una cifra, due cifre, tre… Il complemento è semplice: le password senza cifre sono 26⁸. Il totale è 36⁸. Quindi:
36⁸ − 26⁸ ≈ 2,82 · 10¹² − 2,09 · 10¹¹ ≈ 2,61 · 10¹²
Ogni volta che compare «almeno uno», il complemento è la prima cosa da provare.
Regola della divisione
Se un procedimento conta ogni oggetto esattamente d volte, il numero di oggetti è il conteggio diviso per d.
Esempio: in quanti modi 5 persone possono sedersi attorno a un tavolo rotondo, se contano solo le posizioni relative? Le disposizioni in fila sono 5 · 4 · 3 · 2 · 1 = 120. Ma ogni disposizione circolare corrisponde a 5 disposizioni in fila, ottenute ruotando. Quindi i modi distinti sono 120 / 5 = 24.
La regola della divisione è quella che, applicata alle permutazioni, produce i coefficienti binomiali.
Un'applicazione alla sicurezza
I principi di conteggio sono il fondamento della stima della robustezza di una password o di una chiave. Lo spazio delle possibilità per una password di lunghezza L su un alfabeto di N simboli è Nᴸ. Si esprime spesso in bit come L · log₂ N.
| Alfabeto | N | bit per carattere |
|---|---|---|
| solo cifre | 10 | ≈ 3,32 |
| minuscole | 26 | ≈ 4,70 |
| minuscole e maiuscole | 52 | ≈ 5,70 |
| lettere e cifre | 62 | ≈ 5,95 |
Due osservazioni pratiche emergono subito. Primo, la lunghezza pesa più dell'alfabeto, perché sta all'esponente: aggiungere due caratteri minuscoli porta più bit che passare da 26 a 62 simboli su una password già lunga. Secondo, questi numeri valgono solo se ogni carattere è scelto davvero a caso. Una password costruita da una persona, con una parola e un numero alla fine, occupa una parte minuscola dello spazio teorico. Nel mio lavoro questa distinzione tra spazio teorico e spazio effettivo è il punto da cui parto ogni volta che valuto una politica sulle password.
Il conteggio aiuta anche a leggere i limiti dei tentativi. Un PIN da 4 cifre con un blocco dopo 3 errori dà a chi tira a indovinare 3 possibilità su 10.000: è il limite dei tentativi, più che la lunghezza del codice, a proteggere davvero.
In sintesi
- Regola del prodotto: scelte indipendenti in sequenza si moltiplicano.
- Regola della somma: casi disgiunti si sommano.
- Quando compare «almeno uno», contate il complemento e sottraete.
- Se ogni oggetto viene contato d volte, dividete per d.
- Lo spazio di una password è Nᴸ: la lunghezza conta più dell'alfabeto, ma solo se la scelta è casuale.
