Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
I corsi di Scienze Matematiche Fisiche e Naturali
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

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=pn con p numero primo.
Si fissi una base ordinata (v1, … , vn) di F riguardato come spazio vettoriale sul suo sottocampo minimo.
Sia u un qualunque elemento di F  ⇒  u individua una n-pla (a1, … , an) di elementi di {0,…, p-1} tale che u=a1v1+…+anvn (si ricordi che con il simbolo aivi si indica sia il multiplo di vi secondo il numero ai che il prodotto degli elementi ai ,vi di F)  ⇒  la n-pla (a1, … , an) individua il numero a(u)=a1pn-1+…+an-1p+an 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=pn con p numero primo.
Si fissi un polinomio f(x) appartenente a Zp[x] irriducibile su Zp di grado n.
Dato che due campi finiti dello stesso ordine sono isomorfi, si può supporre che sia F=Zp[x]/I con I=(f(x)).
Sia u un qualunque elemento di F  ⇒  u individua un polinomio r(x) appartenente a Zp[x] nullo oppure di grado minore di n tale che u=r(x)+I  ⇒  r(x) individua una n-pla (a1, … , an) di elementi di {0,…, p-1} tale che r(x)=[a1]pxn-1+…+[an-1]px+[an]p   ⇒  la n-pla (a1, … , an) individua il numero a(u)=a1pn-1+…+an-1p+an 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=Zr e la funzione di cifratura sia del tipo f(P)= AfP+Bf con Af appartenente a Zr* e Bf appartenente a Zr (cfr. Lezione 6): quindi la chiave di cifratura deve essere una coppia appartenente al prodotto cartesiano Zr * x Zr.
Si scelga un campo F di ordine q=p2 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}2  che è contenuto nel quadrato cartesiano {0,…,r-1}2  ⇒  la coppia (a(u),b(u)) individua la coppia ([a(u)]r ,[b(u)]r) appartenente al quadrato cartesiano (Zr)2.
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=Mh1(Zr) e la funzione di cifratura sia del tipo f(P)= AfP+Bf con  Af appartenente a Glh(Zr) e Bf appartenente a Mh1(Zr) (cfr. Lezione 7).
Quindi la chiave di cifratura deve essere una coppia appartenente al prodotto cartesiano Glh(Zr)xMh1(Zr).
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 (h2+h)-pla di elementi di {0,…,r-1} che indichiamo con
(a11,…,a1k,a21,…,a2h,…, ah1,…,ahh,b11,…, bh1)  ⇒  tale (h2+h)-pla individua le due matrici

A(u)=([aij]p) appartenente a Mhh(Zr) e B(u)=([bij]p) appartenente a Mh1(Zr).
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=g0,g,…,gm-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=gn.

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:

  1. è nota la fattorizzazione di q-1 in prodotto di numeri primi
  2. 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 p1 , … , pt 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=gn.
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 p1 , … , pt .
Si fissi quindi un i appartenente a  {1,…,t}, e si ponga p=pi e β=βi .
Sia ap l’unico numero tale che n≡ap (mod pβ) e 0≤ap≤pβ-1.
L’obiettivo a questo punto è determinare ap .
Si consideri l’espansione di ap in base p: ap =xβ-1pβ-1+…+x1p+x0 .
Si calcoleranno ora, uno alla volta i coefficienti  x0 , x1 ,…, xβ-1 .
Si calcolano tutti gli elementi dell’insieme Xp = {aє F*  | ap =1}
A tale scopo basta osservare che Xp (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 x0 , si osservi che (g^{\frac{q-1}{p}})^{x_0} appartiene a Xp .
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 x0 si calcola b^{\frac{q-1}{p}} e si individua l’elemento di Xp con cui esso coincide.
Allo scopo di calcolare x1 , si osservi che (g^{\frac{q-1}{p}})^{x_1} appartiene a Xp .
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 x1 si calcola b^{\frac{q-1}{p^2}}(g^{\frac{q-1}{p^2}x_0})^{-1} e si individua l’elemento di Xp con cui esso coincide.
Si procede in modo analogo per determinare i successivi coefficienti.
Una volta determinati tutti i coefficienti x0 , x1 ,…, xβ-1 ,si calcola ap =xβ-1pβ-1+…+x1p+x0 .

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=bc.

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 gab conoscendo ga e gb.

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 ga.
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 gb.
Entrambi gli utenti sono in grado di calcolare l’elemento gab=(ga)b=(gb)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.

I materiali di supporto della lezione

W. Diffie, M.E. Hellman: “New directions in cryptography”, IEEE Transactions on Information Theory IT-22, (1976), 644--654.

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion