CRITTOGRAFIA Flashcards
CRITTOGRAFIA
La crittografia è la scienza di comunicare messaggi segreti e quindi cerca di cifrare e decifrare i messaggi. Ad ogni lettera dell’alfabeto si associa un numero [lo 0 corrisponde allo spazio tra le parole, l’1 corrisponde alla A… ]
esempio: CIAO SO ➝ 3 9 1 15 0 19 15
CRITTOGRAFIA CLASSICA
La crittografia classica o simmetrica si basa sul fatto che c’è un’unica chiave che deve essere necessariamente scambiata tra 2 utenti (il pericolo che questa chiave sia intercettata è alto).
- L’operazione di cifratura è la seguente.
Sia d la chiave e c la funzione di cifratura.
c : ℤ₂₇ ➝ ℤ₂₇
x ⟼ x + d
- L’operazione di decifratura ƒ è l’operazione inversa.
ƒ : ℤ₂₇ ➝ ℤ₂₇
x ⟼ x - d
CRITTOGRAFIA A CHIAVE PUBBLICA
A = (eᴬ, dᴬ) , B = (eᴮ, dᴮ)
Ogni utente ha a disposizione una coppia di chiavi, di cui una PUBBLICA, cioè a disposizione di tutti (eᴬ, eᴮ) e una chiave PRIVATA conosciuta solo dall’utente stesso (dᴬ, dᴮ).
IL CRITTOSISTEMA RSA
Vediamo come un utente A costruisce le sue chiavi.
- A sceglie un naturale m molto grande, primo con tutti gli interi corrispondenti alle unità di messaggio (lettere) che vuole codificare [m è primo con 0, 1, …, 26].
Innanzitutto sappiamo che presa una unità di messaggio a, quindi un intero compreso tra 1 e 26, allora, per il Teo di Eulero, aᵠ⁽ᵐ⁾ ≡ 1 modm poiché (a, m) = 1.
Scelgo due interi s,t che sono uno l’inverso dell’altro mod𝜑(m)
⟹ s • t ≡ 1 mod𝜑(m)
⇒ 𝜑(m) | s•t - 1 , cioè k∈ℤ s•t = k𝜑(m) + 1
Se prendo una unità di messaggio la cui rappresentazione numerica è un intero 1 ≤ a ≤ 26 [per il Teo di Eulero ∀(1≤a≤16) primo con m aᵠ⁽ᵐ⁾ ≡ 1 modm.
⟹ ((a)ˢ)ᵗ = aˢᵗ = aᵏᵠ⁽ᵐ⁾ ⁺ ¹ = aᵏᵠ⁽ᵐ⁾ • a = (aᵠ⁽ᵐ⁾)ᵏ • a ≡ 1ᵏ•a ≡ a modm
A sceglie quindi la sua chiave pubblica (m, s) e sulla base di m [o meglio 𝜑(m)] ed s sceglie come privata t.
Supponiamo che l’utente B voglia comunicare con A una messaggio segreto. B manda ad A una lettera ā. B rappresenta ā nell’intero a (1 ≤ a ≤ 26) poi prende la chiave pubblica di a e calcola aˢmodm. A riceve aˢmodm, poi (aˢ)ᵗ = a modm
SICUREZZA DEL CRITTOSISTEMA RSA
Per aumentare la sicurezza del sistema RSA si sceglie come dispari m un prodotto di primi molto grandi (primi titanici)
m = p₁ • p₂ p₁, p₂ primi titanici
𝜑(m) = 𝜑(p₁ • p₂) = 𝜑(p₁) • 𝜑(p₂) = (p₁ - 1) • (p₂ - 1)
Dunque C per violare il crittosistema deve necessariamente conoscere p₁ e p₂.
CIFRATURA ➝ eseguire il prodotto tra primi titanici ed elevare a potenza l’unità di messaggio a per S
DECIFRATURA ➝ calcolare i fattori di un dispari molto grande in tempi efficienti (tempo polinomiali).
