Corso di Algebra Avanzata Teoria dei Codici e Crittografia: 4 Crittografia

 

Crittografia

1) Nozioni di base

Terminologia

  • Plaintext (testo in chiaro), ciphertext (testo cifrato), chiave (segreto usato da algoritmo), algoritmo di cifratura.
  • Modalità: simmetrica (stessa chiave per cifrare/decifrare) vs asimmetrica (coppia chiavi pubblica/privata).
  • Obiettivi di sicurezza: confidenzialità, integrità, autenticazione, non-ripudio.

Proprietà matematiche utili

  • Operazioni modulo , inversi modulari, esponenziazione modulare — base per RSA.
  • Nozioni su funzioni unidirezionali e trapdoor functions (funzione facile da calcolare ma difficile da invertire senza informazione segreta).

2) Cifrari classici (teoria + esempi)

Cesare (shift cipher)

Regola: per ogni lettera su alfabeto :


E(P) = (P + k) \bmod 26

Esempio: plaintext CRITTOGRAFIA, .

  • C→F, R→U, I→L, T→W, T→W, O→R, G→J, R→U, A→D, F→I, I→L, A→D
  • ciphertext: FULWWRJUDILD

Debolezze: spazio chiave piccolo (26) → brute force e analisi di frequenza.

Attività rapida: cifrare SICUREZZA con e decifrare QNUUXJXX.

Vigenère

Regola: chiave ripetuta; per lettera 


E_i = (P_i + K_{i}) \bmod 26

Esempio: plaintext ATTACCOALLABARCA, chiave LEONE.
Risultato: LXHNGNSOYPLFOEGL (passaggi: A+L, T+E, ...).

Debolezze/attacco: Kasiski, analisi delle distanze, analisi di frequenza su sotto-sequenze.

Attività: cripta PROVASEGRETA con chiave MELA; prova a rompere una Vigenère con chiave di lunghezza 3 usando conteggi di frequenza.

Sostituzione monoalfabetica

Regola: permutazione dell’alfabeto (es. A→Q, B→W, ...).
Esempio: mappa QWERTYUIOPASDFGHJKLZXCVBNM; plaintext SEMPRE SICURO → LTDHKT LOEXKG.

Debolezze: analisi di frequenza, pattern (bigrammi/trigrammi).
Attività: crea una chiave casuale e cifra un paragrafo; poi scambia con un compagno per tentare il criptoanalisi.

Trasposizione (es. trasposizione a colonne)

Idea: permutare la posizione delle lettere (non sostituirle).
Algoritmo comune (colonnare): scrivi il testo per righe in un numero di colonne e leggi per colonne secondo un ordine dato.

Esempio rapido: plaintext BENVENUTI, 3 colonne →

B E N
V E N
U T I

Leggi colonna 1,2,3 → BVU EET NNI (dipende dall’implementazione).

Attività: implementa la trasposizione colonnare con chiave numerica 3 1 4 2.

3) Crittografia asimmetrica — principi

  • Chiave pubblica/p privata: chiunque può cifrare con la chiave pubblica; solo il possessore della chiave privata può decifrare.
  • Basata su funzioni difficili da invertire (fattorizzazione di grandi interi per RSA; logaritmo discreto per Diffie-Hellman/ECC).
  • Vantaggi: scambio sicuro di chiavi, firme digitali. Svantaggi: più lenta, usata spesso per cifrare chiavi sessione (ibrido).

4) RSA — spiegazione passo-passo e esempio numerico

Algoritmo (alto livello)

  1. Scegli due grandi primi e .
  2. Calcola . è il modulo.
  3. Calcola .
  4. Scegli tale che e .
  5. Calcola inverso modulare di modulo : .
  6. Chiave pubblica: . Chiave privata: (e se vuoi ottimizzare).

Cifratura: .
Decifratura: .

Nota pratica: nella realtà si applicano padding (es. RSA-OAEP) prima di cifrare, altrimenti ci sono vulnerabilità.

5) Funzioni hash: proprietà e uso

Definizione: funzione che mappa inputs di lunghezza arbitraria a digest di lunghezza fissa. Proprietà desiderate:

  • Preimage resistance: dato è difficile trovare tale che .
  • Second preimage resistance: dato , è difficile trovare con .
  • Collision resistance: è difficile trovare qualsiasi coppia con .

Esempi storici: MD5 e SHA-1

  • MD5 produce digest a 128 bit; SHA-1 produce digest a 160 bit.
  • Vulnerabilità: sono stati trovati attacchi pratici che generano collisioni (MD5 già rotto; SHA-1 vulnerabile a collisioni pratiche). Non usare MD5/SHA-1 per firme o per nuovi sistemi di integrità crittografica; sono usabili solo come checksum non-sicuri o per compatibilità.

Esempi noti (valori standard)

  • MD5("abc") = 900150983cd24fb0d6963f7d28e17f72
  • SHA-1("abc") = a9993e364706816aba3e25717850c26c9cd0d89d
  • MD5("hello") = 5d41402abc4b2a76b9719d911017c592
  • SHA-1("hello") = aaf4c61ddcc5e8a2dabede0f3b482cd9aea9434d

Uso corretto degli hash

  • Per memorizzare password: non solo hash semplice — usare salt ed algoritmi adatti a password hashing (PBKDF2, bcrypt, scrypt, Argon2).
  • Per integrità di file: preferire SHA-256 o SHA-3.
  • Per firme digitali: usare hash sicuri (SHA-256/384/512) + algoritmo di firma.

Esempio Python (hashlib):

import hashlib

text = b"hello"
md5_digest = hashlib.md5(text).hexdigest()
sha1_digest = hashlib.sha1(text).hexdigest()

Commenti

Posta un commento