Home

Federica EU

1/12

Maria De Falco » 9.Premesse all'uso dei campi finiti in crittografia. Problema del logaritmo discreto. Algoritmo di Silver-Pohlig-Hellmann. Protocollo di Diffie-Hellmann

Biezioni tra un campo di ordine q e {0, …, q-1}

Si è visto che esistono diversi meccanismi attraverso i quali strutturare un opportuno insieme numerico come insieme delle unità di messaggio in chiaro di un sistema crittografico.
Sia ora F un campo finito; si vedrà nel seguito come tale campo possa essere utilizzato per la costruzione di protocolli crittografici e crittosistemi. A tale scopo, detto q l’ordine del campo, il primo essenziale passo è la costruzione di una “buona” biezione tra F e l’insieme numerico {0, … ,q-1}.
Si presenteranno ora due esempi di meccanismi per costruire tali biezioni.
Esempio 11.1
Si ponga q=pⁿ con p numero primo.
Si fissi una base ordinata (v₁, … , v_n) di F riguardato come spazio vettoriale sul suo sottocampo minimo.
Sia u un qualunque elemento di F ⇒ u individua una n-pla (a₁, … , a_n) di elementi di {0,…, p-1} tale che u=a₁v₁+…+a_nv_n (si ricordi che con il simbolo a_iv_i si indica sia il multiplo di v_i secondo il numero a_i che il prodotto degli elementi a_i,v_i di F) ⇒ la n-pla (a₁, … , a_n) individua il numero a(u)=a₁p^n-1+…+a_n-1p+a_n appartenente all’insieme {0,…, q-1}.
La funzione μ:F→{0,…,q-1} definita ponendo μ(u)=a(u) è biettiva (cfr. Proposizione 1.6).

Biezioni tra un campo di ordine q e {0, …, q-1}

Esempio 11.2
Si ponga q=pⁿ con p numero primo.
Si fissi un polinomio f(x) appartenente a Z_p[x] irriducibile su Z_p di grado n.
Dato che due campi finiti dello stesso ordine sono isomorfi, si può supporre che sia F=Z_p[x]/I con I=(f(x)).
Sia u un qualunque elemento di F ⇒ u individua un polinomio r(x) appartenente a Z_p[x] nullo oppure di grado minore di n tale che u=r(x)+I ⇒ r(x) individua una n-pla (a₁, … , a_n) di elementi di {0,…, p-1} tale che r(x)=[a₁]_px^n-1+…+[a_n-1]_px+[a_n]_p ⇒ la n-pla (a₁, … , a_n) individua il numero a(u)=a₁p^n-1+…+a_n-1p+a_n appartenente all’insieme {0,…, q-1}.
La funzione μ:F → {0,…,q-1} definita ponendo μ(u)=a(u) è biettiva (cfr. Proposizione 1.6).

Campi finiti e chiavi di cifratura

Si esibiranno ora due esempi di costruzione di un meccanismo attraverso il quale opportuni elementi di un campo individuano una chiave di cifratura.
Esempio 11.3
Si supponga di volere usare un sistema crittografico in cui M=C=Z_r e la funzione di cifratura sia del tipo f(P)= A_fP+B_f con A_fappartenente a Z_r* e B_f appartenente a Z_r (cfr. Lezione 6): quindi la chiave di cifratura deve essere una coppia appartenente al prodotto cartesiano Z_r* x Z_r.
Si scelga un campo F di ordine q=p² con p numero primo minore di r (ma non troppo più piccolo).
Si fissi poi una biezione μ tra F e l’insieme {0,…,q-1}.
Sia ora u un elemento di F ⇒ u individua un elemento μ(u) appartenente a {0,…,q-1} ⇒ μ(u) individua la coppia (a(u),b(u)) appartenente al quadrato cartesiano {0,…,p-1}² che è contenuto nel quadrato cartesiano {0,…,r-1}² ⇒ la coppia (a(u),b(u)) individua la coppia ([a(u)]_r,[b(u)]_r) appartenente al quadrato cartesiano (Z_r)².
Se la classe di congruenza [a(u)]_r è invertibile, la coppia ([a(u)]_r,[b(u)]_r) può essere scelta come chiave di cifratura.

Campi finiti e chiavi di cifratura

Esempio 11.4
Si supponga di volere usare un sistema crittografico in cui M=C=M_h1(Z_r) e la funzione di cifratura sia del tipo f(P)= A_fP+B_f con A_f appartenente a Gl_h(Z_r) e B_f appartenente a M_h1(Z_r) (cfr. Lezione 7).
Quindi la chiave di cifratura deve essere una coppia appartenente al prodotto cartesiano Gl_h(Z_r)xM_h1(Z_r).
Si scelga un campo F finito di ordine $q < r^{h^2+h}$ (ma non troppo più piccolo).
Si fissi poi una biezione μ tra F e l’insieme {0,…,q-1}.
Sia ora u un elemento di F ⇒  u individua un elemento μ(u) appartenente a {0,…,q-1} che è contenuto in
$\left\{0, ..., r^{h^2+h}-1\right\}$ ⇒  μ(u) individua una (h²+h)-pla di elementi di {0,…,r-1} che indichiamo con
(a₁₁,…,a_1k,a₂₁,…,a_2h,…, a_h1,…,a_hh,b₁₁,…, b_h1) ⇒  tale (h²+h)-pla individua le due matrici

A(u)=([a_ij]_p) appartenente a M_hh(Z_r) e B(u)=([b_ij]_p) appartenente a M_h1(Z_r).
Se la matrice A è invertibile, la coppia (A(u),B(u)) può essere scelta come chiave di cifratura.

Problema del Logaritmo Discreto

Sia G un gruppo (dato in notazione moltiplicativa), e sia g un elemento di G\{1}; se m è il periodo di g, allora si ha

<g>={1=g⁰,g,…,g^m-1}.
Si è visto, nella lezione 8, che per alcune classi notevoli di gruppi è possibile, grazie al metodo dei quadrati ripetuti, calcolare in un tempo polinomiale (rispetto ad opportuni input) le potenze degli elementi di un gruppo appartenente ad una di tali classi.
D’altra parte, anche in queste classi di gruppi, non è in generale possibile compiere in tempo polinomiale l’operazione ”inversa dell’elevamento a potenza”:
Problema del Logaritmo Discreto
Non esiste un algoritmo efficiente che, comunque scelti un gruppo finito G, un elemento g appartenente a G, un elemento b appartenente a <g>, permetta di calcolare un numero naturale n tale che b=gⁿ.

Problema del Logaritmo Discreto

Il problema del logaritmo discreto non è in generale risolvibile nè nei gruppi moltiplicativi dei campi finiti né nei gruppi costruiti su curve ellittiche.
Si illustrerà, nelle slides successive, un algoritmo che permette di risolvere il problema del logaritmo discreto nel gruppo moltiplicativo di un campo finito F il cui ordine q verifichi le seguenti condizioni:

è nota la fattorizzazione di q-1 in prodotto di numeri primi
q-1 è “smooth”, cioè i suoi fattori primi sono ”piccoli” (cfr. Smooth number)

Algoritmo di Silver-Pohlig-Hellmann

Sia F un campo finito di ordine q tale che sia nota la fattorizzazione di q-1 in prodotto di numeri primi, e sia g un generatore di F*.
Sia q-1= $(p_1)^{\beta _1} \dots p_t^{\beta _t}$ , con p₁ , … , p_t primi a due a due distinti e si supponga che questi primi siano “piccoli”.
Sia b un elemento di F*; allora esiste un numero naturale n tale che b=gⁿ.
Si tenga presente che l’insieme dei numeri naturali con tale proprietà costituisce una classe di congruenza modulo q-1 (cfr. Proposizione 5.2).

Algoritmo di Silver-Pohlig-Hellmann

Prima Fase
Si opera, uno alla volta, su ciascuno dei primi p₁ , … , p_t.
Si fissi quindi un i appartenente a {1,…,t}, e si ponga p=p_i e β=β_i .
Sia a_p l’unico numero tale che n≡a_p (mod p^β) e 0≤a_p≤p^β-1.
L’obiettivo a questo punto è determinare a_p .
Si consideri l’espansione di a_p in base p: a_p =x_β-1p^β-1+…+x₁p+x₀.
Si calcoleranno ora, uno alla volta i coefficienti x₀, x₁,…, x_β-1.
Si calcolano tutti gli elementi dell’insieme X_p = {aє F* | a^p =1}
A tale scopo basta osservare che X_p (visto che F*=<g> è ciclico di ordine q-1) coincide con
< $g^{\frac{q-1}{p}}$ > = $\{ 1, g^{\frac{q-1}{p}} , (g^{\frac{q-1}{p}})^2 , \dots , (g^{\frac{q-1}{p}})^{(p-1)} \}$ .
Allo scopo di calcolare x₀ , si osservi che $(g^{\frac{q-1}{p}})^{x_0}$ appartiene a X_p .
D’altra parte
$(g^{\frac{q-1}{p}})^{x_0}=(g^{\frac{q-1}{p}})^{x_0+ x_1p + \dots + x_{\beta -1}p^{\beta -1}}= (g^{\frac{q-1}{p}})^n=b^{\frac{q-1}{p}}$ .

Algoritmo di Silver-Pohlig-Hellmann

Dunque per determinare x₀ si calcola $b^{\frac{q-1}{p}}$ e si individua l’elemento di X_p con cui esso coincide.
Allo scopo di calcolare x₁ , si osservi che $(g^{\frac{q-1}{p}})^{x_1}$ appartiene a X_p .
D’altra parte,
$(g^{\frac{q-1}{p}})^{x_1}=(g^{\frac{q-1}{p^2}})^{x_1p}=$
$=(g^{\frac{q-1}{p^2}})^{x_1p +x_2p^2+ \dots + x_{\beta -1}p^{\beta -1}}=(g^{\frac{q-1}{p^2}})^{x-x_0}=$
$=(g^{\frac{q-1}{p^2}})^x(g^{\frac{q-1}{p^2}x_0})^{-1}=b^{\frac{q-1}{p^2}}(g^{\frac{q-1}{p^2}x_0})^{-1}$

Dunque per determinare x₁ si calcola $b^{\frac{q-1}{p^2}}(g^{\frac{q-1}{p^2}x_0})^{-1}$ e si individua l’elemento di X_p con cui esso coincide.
Si procede in modo analogo per determinare i successivi coefficienti.
Una volta determinati tutti i coefficienti x₀, x₁,…, x_β-1 ,si calcola a_p =x_β-1p^β-1+…+x₁p+x₀.

Algoritmo di Silver-Pohlig-Hellmann

Seconda Fase
Una volta determinati tutti i numeri $a_{p_1} , \dots , a_{p_t}$ , si applica il Teorema Cinese del resto per risolvere il sistema di equazioni congruenziali
$\left\{\begin{array}{l}x\equiv a_{p_1}(mod\; p_1^{\beta_1})\\ ... \\ x\equiv a_{p_1}(mod \;p_t^{\beta_t})\end{array}$
Sia c una soluzione di tale sistema; allora y=b^c.

Asserto di Diffie-Hellmann

I sistemi crittografici presentati nella Lezione 6 sono detti “simmetrici” perché conoscendo la chiave di cifratura è computazionalmente possibile determinare la chiave di decifratura.
Naturalmente, gli utenti di un crittosistema simmetrico devono tenere segreta la chiave di cifratura (per questo motivo i sistemi simmetrici vengono detti anche “a chiave privata”); pertanto hanno la necessità di scegliere una chiave di cifratura e comunicarla tra di loro in maniera riservata.
Nel 1976 Whitfield Diffie e Martin Hellmann proposero un meccanismo attraverso il quale due utenti possono scambiarsi in maniera riservata una chiave di cifratura.
Tale meccanismo è basato sul seguente asserto:

Asserto di Diffie-Hellman

Non esiste un algoritmo efficiente che, comunque scelto un campo finito F, un elemento g appartenente a F*, degli interi a,b appartenenti a {0,…,|<g>|-1}, permetta di calcolare g^ab conoscendo g^a e g^b.

Protocollo di Diffie-Hellmann

Siano A e B due utenti di un sistema crittografico che hanno la necessità di scegliere e scambiarsi una chiave di cifratura.
I due utenti fissano di comune accordo un campo finito F, un elemento g appartenente a F* (possibilmente un generatore) e un meccanismo attraverso il quale opportuni elementi di F individuano una chiave di cifratura.
L’utente A sceglie un numero naturale a appartenente a {0,…, |<g>|-1}; A tiene segreto il numero a e comunica a B l’elemento del campo g^a.
L’utente B sceglie un numero naturale b appartenente a {0,…, |<g>|-1}; B tiene segreto il numero b e comunica ad A l’elemento del campo g^b.
Entrambi gli utenti sono in grado di calcolare l’elemento g^ab=(g^a)^b=(g^b)^a.
Se l’elemento determina una chiave di cifratura, essa sarà quella quella che gli utenti A e B utilizzeranno.
E’ evidente che il campo F scelto per applicare il Protocollo di Diffie-Hellmann deve essere tale che nel gruppo F* non sia risolvibile il Problema del Logaritmo Discreto.