Algoritmi di Crittografia Asimmetrici

Introduzione

Gli algoritmi asimmetrici sono detti così perché la chiave utilizzata per cifrare un messaggio M è diversa da quella impiegata per decifrare il messaggio cifrato. Supponendo che Alice voglia inviare un messaggio cifrato a Bob, per cifrare il messaggio viene utilizzata una chiave kc. Successivamente Alice invia il messaggio cifrato, che Bob decifrerà con una chiave kd. La chiave per cifrare è pubblicamente disponibile per chiunque voglia mandare un messaggio a Bob, mentre quella per decifrare è posseduta esclusivamente da Bob.

Prima di comunicare con Alice, Bob genererà le due chiavi kc e kd. Bob invierà la chiave per cifrare ad Alice, che potrà utilizzare per cifrare i messaggi.

Generalmente la chiave per cifrare viene detta chiave pubblica, e quella per decifrare chiave privata. In questo modo è possibile inviare la chiave pubblica, che serve solo per cifrare e non per decifrare, attraverso un canale non sicuro o addirittura essere pubblica per chiunque. Gli algoritmi asimmetrici garantiscono che è molto difficile ricavare la chiave privata avendo quella pubblica.

Problema della fattorizzazione dei numeri interi

Vedi anche Problema della fattorizzazione dei numeri interi

Gli algoritmi basati sul problema della fattorizzazione dei numeri interi si basano sulla difficoltà di calcolare la scomposizione in numeri primi di un numero. Per il teorema fondamentale dell'aritmetica ogni numero intero è scomponibile in un prodotto di numeri primi. Le possibili scomposizioni possono essere molteplici, ma quella in numeri primi è unica.

Ad esempio il numero n = 120 può essere scomposto nei numeri primi seguenti:
120 = 2*2*2*3*5
ma può essere scomposto anche in:
120 = 4*30 = 2*60 = 15*8 = 5*24 = …

Dato un numero n che è prodotto di due numeri primi p e q, la sua scomposizione sarà unica. È stato dimostrato che, a partire da n, ricavare i numeri p e q è un problema NP completo. Su questa caratteristica è fondata la crittografia della fattorizzazione dei numeri interi (Integer Factorization Cryptography - IFC).

L'algoritmo IFC più celebre è l'algoritmo RSA (per la crittografia e per la firma digitale) inventato da Ron Rivest, Adi Shamir e Leonard Adleman nel 1977. Il nome dell'algoritmo deriva dalle iniziali dei tre inventori.

Problema del logaritmo discreto

Vedi anche Problema del logaritmo discreto

Sulla crittografia dei logaritmi discreti (Discrete Logarithm Cryptography - DLC) si basano gli algoritmi ElGamal (per la crittografia), DSA (per la firma) e il protocollo di scambio chiave di Diffie-Hellman.

Gruppi

Si considera l'insieme degli interi modulo n, indicati con Zn, ovvero gli interi {0, 1, …, n-1}. Le operazioni come la addizione, la sottrazione e la moltiplicazione sono effettuate modulo n.

Esempio:
Considerando Z12, allora 10 + 5 = 3, perché 10 + 5 = 15 e 15 mod 12 = 3

La divisione di due numeri $a,\:b \in Z_n$ è data dal prodotto di a per l'elemento inverso di b, indicato con b-1 ed è definita se questo elemento inverso esiste. Se esiste, soddisfa la proprietà seguente:

(1)
\begin{align} b b^{-1} mod\:n = 1 \end{align}

Esempio:
Considerando Z7, allora dato b = 5, il suo inverso è b-1 = 3 perché bb-1 = 15 mod 7 = 1

Dato Zn, un suo elemento a è invertibile se a è coprimo con n. Da questa osservazione si deduce che se n è primo, allora tutti gli elementi, tranne 0, saranno invertibili.

Un gruppo (G, *) è un insieme G con una operazione binaria * che soddisfa le seguenti proprietà:

  • proprietà associativa: $a * (b * c) = (a * b) * c \: \forall a, b, c \in G$
  • elemento identità: esiste un elemento $i \in G$ tale che $a * i = i * a = a,\:\forall a \in G$
  • elemento inverso: $\forall a \in G$ esiste un elemento $a^{-1} \in G$ tale che $a * a^{-1} = a^{-1} * a = i$

L'ordine di un gruppo G è dato dal numero dei suoi elementi.

L'insieme Zn assieme all'operazione di addizione modulo n forma un gruppo di ordine n. Lo stesso insieme all'operazione di moltiplicazione non forma un gruppo, perché non tutti gli elementi possiedono un elemento inverso. I numeri interi modulo n che possiedono un elemento inverso sono tutti e quelli che sono coprimi con n. Questo insieme di numeri forma un gruppo con l'operazione di moltiplicazione, e viene indicato con Z*n. Il numero di elementi di questo gruppo, ovvero il numero dei coprimi con n inferiori a n è pari alla funzione phi(n) di Eulero di n. Nel caso n sia un numero primo, allora phi(n) = n-1, e tutti gli interi inferiori a n (tranne 0) avranno il moltiplicativo inverso.

Esempio: Moltiplicativi inversi del gruppo Z19

a 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
a-1 1 10 13 5 4 16 11 12 17 2 7 8 3 15 14 6 9 18

Un gruppo G è detto ciclico se esiste un valore $\alpha \in G$, detto generatore, tale che $\forall b \in G$ esiste un intero i tale che $b = \alpha^i mod:\b$.

Esempio: Valori di i per il generatore $\alpha=2$ del gruppo Z19

b 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
i 18 1 13 2 16 14 6 3 8 17 12 15 5 7 11 4 10 9

Esempio:
Dato il gruppo Z19, l'elemento b = 13 è generato da $\alpha = 2$ tramite l'intero i = 5, perché
25 mod 19 = 32 mod 19 = 13

Il problema del Logaritmo discreto (Discrete Logarithm Problem - DLP) è definito come segue: dato un gruppo ciclico G di ordine n, un generatore $\alpha$ di G e un elemento $b \in G$, il logaritmo discreto di b, indicato con

(2)
\begin{align} \log_{\alpha} b \end{align}

è quell'elemento $x \in G$ tale che $\alpha x = b$.
L'elemento x esiste sempre, poiché essendo un gruppo ciclico, ogni elemento di G è una potenza di $\alpha$.

Problema di Diffie-Hellman

Il problema di Diffie-Hellman (Diffie-Hellman Problem - DHP) è definito come segue: dato un numero primo p, un generatore $\alpha$ di Zp* e gli elementi $\alpha^a mod\:p$ e $\alpha^b mod\:p$, trovare $\alpha^{ab} mod\:p$.

Curve Ellittiche

Vedi anche Curve Ellittiche
La crittografia delle curve ellittiche (Eliptic Curve Cryptography - ECC) è alla base degli algoritmi di Diffie-Hellman su Curve Ellittiche, oltre che dell'algoritmo di firma ECDSA.

Sicurezza

Nel documento SP800-57 [1], pubblicato dal NIST, è presente una stima sulla lunghezza delle chiavi necessaria per evitare ragionevolmente una loro eventuale compromissione.

2010 2010 - 2030 > 2030
DLP (tipo Elgamal, Diffie-Hellman, DSA) 1024, 160 2048, 224 3072, 256
IFP (tipo RSA) 1024 2048 3072
ECC 160 224 256

Riepilogo

Fattorizzazione Interi Logaritmo Discreto Curve Ellittiche
Scambio Chiave Protocollo Diffie-Hellman, Protocollo Menezes-Qu-Vanstone Diffie-Hellman su Curve Ellittiche, Menezes-Qu-Vanstone su Curve Ellittiche
Firma RSA, Rabin-Williams, ESIGN DSA, Nyberg-Rueppel ECDSA, Nyberg-Rueppel su Curve Elittiche
Cifratura RSA, Rabin ElGamal, DHIES
Bibliography
1. NIST, SP800-57 part 1, "Recommendation for Key Management – Part 1: General (Revised)", 2006, Sito web: http://csrc.nist.gov/publications/nistpubs/800-57/SP800-57-Part1.pdf
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License