Curve Ellittiche

Una curva piana è definita come l'insieme dei punti che soddisfano l'equazione F(x,y)=0. Le curve piane più semplici sono linee (equazione con incognite x e y con grado 1), coniche (grado 2) e cubiche (grado 3).
Le curve ellittiche sono curve di tipo cubico. Nella crittografia si impiegano curve ellittiche i cui coefficienti dell'equazione sono elementi di GF(q), ovvero di un campo finito. I punti sulla curva sono coordinate nella forma (x,y) dove sia x che y sono elementi di GF(q).

Le curve ellittiche interessanti per la crittografia possono essere definite tramite l'equazione di Weierstrass. Nei campi di tipo GF(q) l'equazione è:

(1)
\begin{equation} y^2 = x^3 + ax + b \end{equation}

dove q è un numero primo maggiore di 3 e i coefficienti a e b sono interi modulo p che soddisfano la condizione seguente:

(2)
\begin{align} 4a^3 + 27b^2 mod p \neq 0 \end{align}

Il vincolo (2) assicura che non esistano radici multiple dell'equazione (1).
Nei campi di tipo GF(2^m), l'equazione è:

(3)
\begin{equation} y^2 + xy = x^3 + ax^2 + b \end{equation}

dove a e b sono elementi di GF(2m) e b diverso da 0.

Dato un campo K, i punti di una curva ellittica sono quei punti (x, y) che risolvono l'equazione F(x,y) = 0, ovvero

(4)
\begin{align} E = \left\lbrace O \right\rbrace \cup (x,y) \in K \times K \vert y^2 + xy = x^3 + ax^2 + b \end{align}

Un punto particolare sempre appartenente alla curva è il punto all'infinito, che si indica con O. Il numero di punti di una curva ellittica (compreso O) è detto ordine di E, ed è indicato con #E(GF(q)).

Addizione

Si può definire una operazione di addizione, nel modo seguente
Sia P = (x,y) un punto appartenente ad E. Allora l'inverso (-P) è definito come

(5)
\begin{equation} -P = (x,-y) \end{equation}

nel caso di campi GF(q)
e

(6)
\begin{equation} -P = (x, x+y) \end{equation}

nei campi di tipo GF(2m)

Il punto all'infinito O ha la proprietà di essere l'elemento neutro per la addizione, ovvero

(7)
\begin{eqnarray} P + O = P \\ P + (-P) = 0 \\ O + O = O \end{eqnarray}

Addizione completa

Dati due punti P0 e P1 con coordinate (x0, y0) e (x1, y1), rispettivamente, allora il punto P2 = P0 + P1 viene calcolato in questo modo:

Se P0 o P1 sono il punto all'infinito O allora si applica la proprietà precedente. Altrimenti, se $x_0 \neq x_1$ si pone

(8)
\begin{align} \lambda = \frac{(y_1 - y_0)}{(x_1 - x_0)} mod\:p \end{align}
(9)
\begin{eqnarray} x_2 = \lambda^2 - x_0 - x_1\:mod\:p \\ y_2 = (x_1 - x_2)\lambda - y_1\:mod\:p \end{eqnarray}

Se $x_0 = x_1$ e $y_0 \neq y_1$, oppure $P_0 = P_1$ e $y_1 = 0$, allora $P_2 = O$. Altrimenti, se $P_0 = P_1$ e $y_1 \neq 0$ allora

(10)
\begin{eqnarray} \lambda &=& \dfrac{3x_1^2 + a}{2y_1}\:mod\:p \\ x_2 &=& \lambda^2 - x_0 - x_1\:mod\:p \\ y_2 &=& (x_1 - x_2)\lambda - y_1\:mod\:p \end{eqnarray}

L'addizione completa ha le seguenti proprietà:

  • commutativa: P1 + P2 = P2 + P1
  • identità: P + O = P
  • inverso: dato P, esiste P' tale che P + P' = O
  • associativa: (P1 + P2) + P3 = P1 + (P2 + P3)

Inoltre valgono anche le consuete proprietà della sottrazione: dati P1 e P2 si ha:
(P1 + P2) - P2 = P1
-(P1 + P2) + P2 = - P1

Moltiplicazione scalare

I punti di una curva ellittica possono essere sommati tra loro ma non moltiplicati tra loro. Si può effettuare una moltiplicazione scalare, ovvero moltiplicare un punto P per un intero n attraverso somme

(11)
\begin{align} nP = P + P + ... + P \mbox{ (n volte) } \end{align}

Inoltre si hanno le seguenti proprietà:

(12)
\begin{eqnarray} 0P &=& O \\ (-n)P &=& n(-P) \end{eqnarray}

Un sistema semplice per effettuare una moltiplicazione scalare consiste nel calcolo dei punti attraverso raddoppi successivi. Dato un punto P, si calcola 2P = P + P, 4P = 2P + 2P, 8P, ecc.
Quindi 23P = 16P + 4P + 2P + P

Ordine di un punto

Data una curva E, per un punto P appartenente alla curva si può definire il più piccolo intero tale che mP = O. Questo intero m è detto ordine di P. Di può dimostrare che l'ordine di un punto divide sempre l'ordine della curva. Dato un punto P, il cofattore h è definito come il rapporto tra l'ordine della curva #E e l'ordine del punto P.

Problema del logaritmo discreto su curve ellittiche

Il Problema del logaritmo discreto su curve ellittiche (Elliptic Curve Discrete Logarithm Problem - ECDLP) è definito in questo modo: data una curva ellittica E, definita su un campo finito GF(q), un punto P con ordine n e un punto Q, trovare l'intero k < n tale che Q = kP. L'intero k è detto logaritmo discreto di Q su base P e di indica con

(13)
\begin{align} k = \log_P Q \end{align}

Sistemi crittografici

Quando si impiegano le curve ellittiche per la crittografia, è necessario che le due parti condividano i parametri seguenti: (q, FR, S, a, b, P, n, h) dove

  • q è l'ordine del campo finito
  • FR è il tipo di rappresentazione delle coordinate x,y
  • S è un seed con il quale si è generata casualmente la curva
  • a e b sono i parametri dell'equazione di Weierstrass
  • P è un punto della curva
  • n è l'ordine di P
  • h è il cofattore, ovvero #E/n

Una volta scelti questi parametri, che sono pubblici e noti a tutti, un utente genera la propria coppia di chiavi sfruttando il problema del logaritmo discreto su curve ellittiche, scegliendo un numero casuale k < n (se fosse k >= n allora si avrebbe Q=O) e calcolando il punto Q = kP. L'intero k è la chiave privata, mentre il punto Q è la chiave pubblica.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License