Home

Federica EU

1/14

Maria De Falco » 11.Immersione dei testi in chiaro e sistemi crittografici in una curva ellittica

Una conseguenza dell’algoritmo della divisione euclidea

Lemma 11.1
Siano a e b numeri naturali positivi. Allora esistono e sono univocamente determinati due numeri naturali m e j tali che a=mb+j con 1≤j≤k.
Tali numeri possono essere calcolati con complessità O((log(hk)²).
Dimostrazione
Si dimostrerà in primo luogo l’esistenza di m e j. Siano q e r rispettivamente il quoziente e il resto della divisione euclidea di a per b ⇒ a=qb+r con 0≤r≤k-1.
Se r>0, basta quindi porre m=q e j=r.
Se invece r=0, allora a=qb, sicché q>0 e quindi basta porre m=q-1 e j=k.
Si dimostrerà ora l’unicità di m e j. Sia m₁k+j₁=m₂k+j₂⇒ (m₁-m₂)k=(j₂-j₁) ⇒ (m₁-m₂)=0 ⇒ m₁=m₂ e j₁=j₂ .
La stima sulla complessità del calcolo è una diretta conseguenza della Proposizione 1.12.

Immersione di {0 ,…, h-1} in una curva ellittica

Si supponga di volere costruire un sistema crittografico in cui l’insieme delle unità di messaggio in chiaro sia un sottoinsieme di una curva ellittica su un campo finito.
Si supponga che l’insieme delle unità di messaggio in chiaro debba avere ordine h.
Si scelgano un campo finito F il cui ordine sia maggiore di h e una curva ellittica E su F.
E’ ovviamente sufficiente costruire un meccanismo attraverso il quale l’insieme {0 ,…, h-1} venga immerso in E.
Sia f(x,y)=0 l’equazione di E, e sia q l’ordine del campo F.
Si scelgano una funzione biettiva μ:F→ {0 ,…, q-1} e un numero naturale k tale che hk<q.
Sia m un qualunque elemento di {0 ,…, h-1}.
Si sceglie un numero naturale j tale che 1≤j≤k ⇒ 1≤mk+j≤hk≤q-1.

Immersione di {0 ,…, h-1} in una curva ellittica

Sia u l’unico elemento di F tale che μ(u)= mk+j e si consideri l’equazione f(u,y)=0.
Se questa equazione ha soluzioni, si sceglie una soluzione v e al numero m si fa corrispondere il punto (u,v) appartenente a E.
Se invece questa equazione non ha soluzioni, si sceglie un altro numero j’ tale che 1≤j’≤k e si ripete il procedimento.
Viceversa, si illustrerà ora il procedimento attraverso il quale, dato un punto (t,z) di E ∩ F² ottenuto applicando il meccanismo sopra descritto ad un numero appartenente a {0 ,…, h-1}, si determina tale numero.
Si lavora sull’elemento t appartenente a F; si ha che μ(t) appartiene all’insieme {1 ,…, hk}. Segue allora dal Lemma 11.1 che esiste un unico numero naturale s appartenete a {0 ,…, h-1} tale che μ(u)=mk+j con 1≤j≤k.
Dunque s è il numero cercato.

Protocollo di Diffie-Hellmann per le curve ellittiche

Analogo, per le curve ellittiche, del protocollo di Diffie-Hellman per lo scambio di chiavi
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 una curva ellittica E su un campo finito, un punto Q appartenente a E (che abbia un periodo elevato, più o meno dell’ordine di grandezza di |F|) e un meccanismo attraverso il quale ogni elemento di E individua una chiave di cifratura (ad esempio utilizzando la prima coordinata, che è un elemento di F).
L’utente A sceglie un numero naturale a appartenente a {0 ,…, |<Q>|-1}; A tiene segreto il numero a e comunica a B l’elemento della curva aQ.
L’utente B sceglie un numero naturale b appartenente a {0 ,…, |<Q>|-1}; B tiene segreto il numero b e comunica a A l’elemento della curva bQ.
La chiave di cifratura sarà quella individuata da (ab)Q.
Si noti che entrambi gli utenti possono calcolare l’elemento (ab)Q perché (ab)Q=a(bQ)=b(aQ).

Sistema di Massey-Omura per le curve ellittiche

Analogo, per le curve ellittiche, del sistema di Massey-Omura
Tenendo conto del procedimento descritto nella prima slide, si può supporre che l’insieme delle unità di messaggio inchiaro sia un sottoinsieme di una curva ellittica E su un campo finito F.
Si supponga inoltre che sia noto |E|.
Si supponga che un utente A voglia inviare un messaggio P ad un utente B.
L’utente A sceglie due numeri naturali u_A ,v_A appartenenti a {0 ,…, |E|} (coprimi con |E|) tali che

[u_A]_|E|[v_A]_|E|= [1]_|E|

L’utente B sceglie due numeri naturali u_B ,v_B appartenenti a {0 ,…, |E|} (coprimi con |E|) tali che

[u_B]_|E|[v_B]_|E|= [1]_|E|

L’utente A calcola e invia all’utente B l’elemento u_AP.
L’utente B calcola e invia all’utente A l’elemento u_Bu_AP.
L’utente A calcola e invia all’utente B l’elemento v_Au_Bu_AP, cioè l’elemento u_BP (cfr. Proposizione 5.2).
L’utente B calcola v_Bu_BP, cioè l’elemento P (cfr. Proposizione 5.2).

Sistema di El Gamal per le curve ellittiche

Analogo, per le curve ellittiche, del sistema di El Gamal
Sono fissati per tutti gli utenti del sistema:

Una curva ellittica su un campo finito F e l’insieme M, che è un sottoinsieme di E
Un punto Q di F* (che abbia un periodo elevato, più o meno dell’ordine di grandezza di |F|).

Ogni utente A sceglie un numero naturale a appartenente all’insieme {0 ,…, |<Q>|-1}.
L’utente A, tenendo segreto il numero a, calcola e rende pubblico la propria chiave di cifratura aQ.
Un utente che voglia inviare un messaggio P all’utente A, sceglie un numero naturale k appartenente all’insieme {0 ,…, |<Q>|-1} e invia ad A la coppia (kQ , P+(ak)Q).
Quando l’utente A riceve un messaggio cifrato C=(Q₁ , P₁), calcola il messaggio in chiaro P tenendo presente che P₁=P+aQ₁ , sicché P=P₁-aQ₁.

Un esempio

Esempio 11.2
Si supponga di voler costruire un sistema crittografico in cui l’insieme delle unità di messaggio in chiaro abbi ordine 10 e sia un sottoinsieme di una curva ellittica su un campo finito.
Sia F=Z₇₁ e sia E la curva ellittica su F di equazione y²=x³-x.
Seguendo il procedimento descritto nelle prime slides, si costruirà un meccanismo attraverso il quale l’insieme verrà immerso in E.
Si consideri la funzione biettiva μ:F ⇒ {0 ,…, 70} tale che μ([a]₇₁) è il resto della divisione euclidea di a per 71.
Si fissi il numero naturale k=7.
Sia ora mє {0 ,…, 9}.
Scelto j tale che 1≤j≤7 , allora 1≤7m+j≤70, e μ([7m+j]₇₁)=7m+j

Un esempio

Esempio 11.2
Se l’equazione y²=[7m+j]₇₁³-[7m+j]₇₁ ha una soluzione [v]₇₁ in Z₇₁ , allora ( [7m+j]₇₁ , [v]₇₁ ) sarà il punto di E che corrisponderà ad m.
Ad esempio, sia m=2
Si proverà con j=1:
dunque 7m+j=15, e quindi [7m+j]₇₁³-[7m+j]₇₁ = [15]₇₁³-[15]₇₁ = [23]₇₁
Dato che [7]₇₁ è un generatore di F* e [23]₇₁ =[7]₇₁¹⁵, segue che [23]₇₁ non è un quadrato in F*
Bisogna quindi provare con un altro valore di j

Un esempio

Si proverà con j=7:
dunque 7m+j=21, e quindi [7m+j]₇₁³-[7m+j]₇₁ = [21]₇₁³-[21]₇₁ = [10]₇₁
Dato che [7]₇₁ è un generatore di F* e [10]₇₁ =[7]₇₁³⁴, segue che [10]₇₁ è un quadrato in F*

Dato che $[10]_{71}=[62]_{71}^2$ , l’elemento m=2 corrisponderà all’unità di messaggio ([21]₇₁, [62]₇₁)

Un esercizio sulle curve ellittiche

Esercizio 11.3
(Lo svolgimento di questo esercizio richiede la conoscenza dei teoremi riguardanti la struttura dei gruppi abeliani finiti; per un riferimento su questo argomento, si veda, ad esempio il testo:
D.J.S. Robinson, “A Course in the Theory of Groups”, Springer)
Sia F un campo di ordine 71, e si consideri la curva ellittica su F di equazione y²=x³-x.
(1) Si determini l’ordine di E
(2) Si determini la struttura del 2-sottogruppo di Sylow di (E,+)
(3) Si determini la struttura del 3-sottogruppo di Sylow di (E,+)

Un esercizio sulle curve ellittiche

Svolgimento dell’esercizio
(1) Sia χ il carattere quadratico di F (cfr. Lezione 7).
Si osservi che F* ha ordine 70 e quindi non ha elementi di periodo 4; ne segue che -1 non è un quadrato in F*, per cui χ(-1)=-1, e che se un elemento u è un quadrato in F*, allora il suo opposto -u non è un quadrato.
$\vert E \vert =72 + \sum _{u\in F} \chi (u^3-u)=$
Si ha χ(0)=0.
Inoltre, per ogni u appartenente a F*, (-u)³-(-u)=-(u³-u), e quindi
$\chi ((-u)^3-(-u))= \chi (- (u^3-u))=- \chi (u^3-u)$
Da quanto detto segue che
$\sum _{u\in F} \chi (u^3-u)=0$
e quindi |E|=72

Un esercizio sulle curve ellittiche

(2) Dato che 72=2³∙3² , il 2-sottogruppo di Sylow E₂ di E ha ordine 8.
Dato che ogni gruppo abeliano finito è somma diretta di gruppi ciclici, si verifica una (ed una sola) delle seguenti possibilità:
(i) E₂ è ciclico (e quindi ha un unico elemento di periodo 2)
(ii) E₂ è una somma diretta H⊕K con H gruppo ciclico di ordine 2 e K gruppo ciclico di ordine 4 (e quindi ha tre elementi di periodo 2)
(iii) E₂ è una somma diretta H⊕K⊕L con H,K,L gruppi ciclici di ordine 2 (e quindi ha sette elementi di periodo 2)
Per stabilire quale delle eventualità si verifica, è sufficiente stabilire quanti elementi di periodo 2 ci sono in E.
Sia (u,v) un elemento di E∩F².
(u,v) ha periodo 2 ⇔ (u,v)=-(u,v)=(u,-v)⇔ v=-v⇔ v=0 (perché (F,+) non ha elementi di periodo 2) ⇔ u³-u=0 ⇔ u(u-1)(u+1)=0 ⇔ u=0 oppure u=1 oppure u=-1
Dunque in E gli elementi di periodo 2 sono esattamente tre (cioé (0,0) , (1,0) , (-1,0)), sicché E₂ è una somma diretta H⊕K con H gruppo ciclico di ordine 2 e K gruppo ciclico di ordine 4

Un esercizio sulle curve ellittiche

(2) Dato che 72=2³∙3² , il 3-sottogruppo di Sylow E₃ di E ha ordine 9.
Dato che ogni gruppo abeliano finito è somma diretta di gruppi ciclici, si verifica una (ed una sola) delle seguenti possibilità:
(i) E₃ è ciclico (e quindi ha due elementi di periodo 3)
(ii) E₃ è una somma diretta H⊕K con H e K gruppi ciclici di ordine 3 (e quindi ha otto elementi di periodo 3)
Per stabilire quale delle eventualità si verifica, è sufficiente stabilire quanti elementi di periodo 3 ci sono in E.
Sia (u,v) un elemento di E∩F².
(u,v) ha periodo 3 ⇔ 2(u,v)=-(u,v)=(u,-v)
Dunque, se (u,v) ha periodo 3, deve essere verificata la seguente uguaglianza (cfr. Definizione 7.6):
$(\frac{3u^2-1}{2v})^2-2u=u$ da cui segue:
$(3u^2-1)^2=12uv^2=12u^4-12u^2$ e quindi $3u^4-6u^2-1=0$

Un esercizio sulle curve ellittiche

Si è quindi dimostrato che se (u,v) ha periodo 3, allora u è radice dell’equazione 3x⁴-6x²-1=0; tale equazione ha al più 4 radici.
Sia T il sottoinsieme di F i cui elementi sono tutte e sole le prime coordinate di tali elementi; poiché l’opposto di un elemento di periodo 3 ha ancora periodo 3, ogni elemento di T è prima coordinata di esattamente due elementi di periodo 3.
Sia tє T; in particolare esiste un punto (t,z) appartenente ad E, e quindi t³-t=z² . Si è già osservato che l’opposto di un quadrato non può essere ancora un quadrato, sicché T non può coincidere con l’insieme delle radici dell’equazione 3x⁴-6x²-1=0. Ne segue che T ha ordine minore di 4, e quindi E non ha otto elementi di periodo 3.
Pertanto E₃ è ciclico.
__________________________________
Si è quindi completamente determinata la struttura del gruppo abeliano (E,+):
(E,+)=H⊕K⊕L
con H gruppo ciclico di ordine 2, K gruppo ciclico di ordine 4, L gruppo ciclico di ordine 9