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 » 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)2).
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 m1k+j1=m2k+j⇒  (m1-m2)k=(j2-j1) ⇒  (m1-m2)=0 ⇒  m1=m2 e j1=j2 .
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 ∩ F2 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 uA ,vA appartenenti a {0 ,…, |E|} (coprimi con |E|) tali che

[uA]|E|[vA]|E| = [1]|E|

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

[uB]|E|[vB]|E| = [1]|E|

L’utente A calcola e invia all’utente B l’elemento uAP.
L’utente B calcola e invia all’utente A l’elemento uBuAP.
L’utente A calcola e invia all’utente B l’elemento vAuBuAP, cioè l’elemento uBP (cfr. Proposizione 5.2).
L’utente B calcola vBuBP, 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:

  1. Una curva ellittica su un campo finito F e l’insieme M, che è un sottoinsieme di E
  2. 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=(Q1 , P1), calcola il messaggio in chiaro P tenendo presente che P1=P+aQ1 , sicché P=P1-aQ1 .

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=Z71 e sia E la curva ellittica su F di equazione y2=x3 -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]71) è 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]71)=7m+j

Un esempio

Esempio 11.2
Se l’equazione y2=[7m+j]713 -[7m+j]71 ha una soluzione [v]71 in Z71 ,  allora ( [7m+j]71 , [v]71 ) 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]713 -[7m+j]71 = [15]713 -[15]71  = [23]71
Dato che [7]71 è un generatore di F* e  [23]71 =[7]7115 , segue che [23]71 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]713 -[7m+j]71 = [21]713 -[21]71  = [10]71
Dato che [7]71 è un generatore di F* e  [10]71 =[7]7134 , segue che [10]71 è un quadrato in F*

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

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 y2=x3 -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)3-(-u)=-(u3-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=23∙32 , il 2-sottogruppo di Sylow E2 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) E2 è ciclico (e quindi ha un unico elemento di periodo 2)
(ii) E2 è 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) E2 è 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∩F2.
(u,v) ha periodo 2 ⇔ (u,v)=-(u,v)=(u,-v)⇔ v=-v⇔ v=0 (perché (F,+) non ha elementi di periodo 2) ⇔  u3-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é E2 è 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=23∙32 , il 3-sottogruppo di Sylow E3 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) E3 è ciclico (e quindi ha due elementi di periodo 3)
(ii) E3 è 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∩F2.
(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  3x4-6x2-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 t3-t=z2 . 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 3x4-6x2-1=0. Ne segue che T ha ordine minore di 4, e quindi E non ha otto elementi di periodo 3.
Pertanto E3 è 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

  • 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