CTX - Lecture Notes Summary

Informazioni Lezione

Cosa Studia la Crittografia?

Cifrario di Cesare

• Cifratura a Permutazione

• Possibili Raffinazioni

  • Cifrario di Vernam

Crittografia Moderna

• Funzione Trappola

Complessità di un Algoritmo

Informazioni Lezione

Divisibilità

• Anelli Euclidei

• Massimo Comun Divisore

  • MCD e Ideali

  • Ideali Principali

  • MCD come Ideale

• Numeri Coprimi e Identità di Bézut

Irriducibilità e Primalità

• Elementi Irridicubili

  • Elementi irriducibili in \(\mathbb{K}[X]\)

• Elementi Primi

• Primo Teorema di Euclide

  • Primo \(\implies\) Irriducibile

  • Irriducibile \(\implies\) Primo

Teorema Fondamentale dell'Aritmetica

• Esistenza

• Unicità

Informazioni Lezione

Numeri di Fibonacci

• Proprietà dei Numeri di Fibonacci

  • \(F_n = \frac{\alpha^n - \alpha'^n}{\sqrt{5}} \quad \forall n\)

  • \(F_n > \alpha^{n-2} \quad \forall n \geq 3\)

  • \(MCD(F_{n+1}, F_{n+2}) = 1 \quad \forall n\)

  • \(\alpha^n = F_n \alpha + F_{n-1} \quad \forall n \geq 2\)

Notazione O-Grande

• Esempio

Scrittura Posizionale

• Lunghezza e grandezza di un numero

• Come Pensiamo ai Numeri

Complessità di un Algoritmo

• Complessità Polinomiale ed Esponenziale

• Complessità Operazioni Elementari

• Complessità Operazioni Non Elementari

  • Massimo Comun Divisore

  • Fattoriale

  • Prodotto tra Interi

  • Prodotto tra Polinomi

  • Idendità di Bézout

Informazioni Lezione

Elementi Invertibili in \(\mathbb{Z}_n\)

Divisori dello \(0\) in \(\mathbb{Z}_n\)

Calcolo dell'inverso in \(\mathbb{Z}_n\)

Congruenze di Primo Grado

• Esistenza di Soluzioni

  • Condizione Necessaria

  • Condizione Sufficiente

  • Enumerare le Soluzioni

Teoremi

• Piccolo Teorema di Fermat

  • Dimostrazione 1

  • Dimostrazione 2

  • Corollario: Calcolo delle potenze

• Teorema Cinese dei Resti

Condivisione di un Segreto

• Caso specifico \(s = 3\)

  • Funzionamento

  • Analisi

• Caso generale \(s > 3\)

  • Funzionamento

  • Analisi

Informazioni Lezione

Funzioni Moltiplicative

• La funzione di Eulero è Moltiplicativa

• Calcolo di \(\varphi(n)\)

  • Caso 1: \(n = p\)

  • Caso 2: \(n = p^a\)

  • Caso 3: \(n = p_1^{a_1}p_2^{a_2}...p_h^{a_h}\)

  • Formula Generale

• Teorema \(\sum_{d | n} \varphi(d) = n\)

Teorema di Eulero

• Dimostrazione

  • Caso 1: \(n = p^a\)

  • Caso 2: \(n = p_1^{m_1}p_2^{m_2}...p_h^{m_h}\)

• Corollario

Informazioni Lezione

Esponenziazione Modulare

• Algoritmo Iterativo

• Algoritmo Ricorsivo

Fattorizzazione di Numeri Particolari

Numeri di Mersenne

Numeri di Fermat

• Proprietà dei Numeri di Fermat

• I numeri primi sono infiniti (Duh!)

• Numeri di Fermat e Poligoni Regolari

Algoritmo di Fermat

• Esempio

Teorema di Wilson

Numeri Perfetti

• Numeri Perfetti e Primi di Mersenne

Informazioni Lezione

Modello Matematico di Crittosistema

Cifrari Monoalfabetici

• Cifrario di Cesare

  • Analisi del Cifrario di Cesare

• Cifrari Affini

  • Numero di chiavi

  • Crittoanalisi dei cifrari affini

Cifrari Polialfabetici

• Cifrario di Hill

  • Inversa di una Matrice a Coefficienti in un Anello

  • Esempio di Utilizzo

Crittoanalisi

• Esempio: Sistemi Lineari in \(\mathbb{Z}_{26}\)

Informazioni Lezione

Funzioni Trappola

• Esempio di Funzione Univoca

Cifrari Esponenziali

• Correttezza

• Sicurezza

  • Logaritmo Discreto

  • Baby Steps, Giant Steps

Diffi-Hellman Key Exchange

Crittografia a Chiave Pubblica

Calcolo Radice Quadrata

Informazioni Lezione

Sistema RSA

Correttezza RSA

Sicurezza RSA

• Conoscere \(\varphi(n_i) \implies\) Fattorizzare \(n_i\)

• È possibile calcolare \(d\) senza \(\varphi(n_i)\)?

  • Algoritmi Deterministici e Algoritmi Probabilistici

  • Algoritmo probabilistico che calcola \(\varphi(n)\) dato \(d\)

Firma Digitale con RSA

• Funziona?

Lecture Info

Problema dello Zaino (Knapsack)

• Esempi

• Digressione: \(\mathbb{P}\) vs \(\mathbb{NP}\)

• Istanze particolari: successioni supercrescenti

Cifrario di Merkle-Hellman

• Il sistema è sicuro?

0-Knowledge Proofs

• Esempio: Logaritmo discreto