Algunos contenidos específicos de la criptografía de curva elíptica
Hay dos relaciones posicionales entre dos líneas rectas diferentes en el plano: intersección y paralela. La introducción del infinito es la unificación de dos relaciones diferentes.
AB⊥L1, L2∑L1, la línea recta AP gira en sentido antihorario desde AB alrededor del punto a, y p es el punto de intersección de AP y l 1.
Q=∠BAP→p /2 AP → L2
Imagina que hay un punto P∞ en L1 que es la intersección de L2 y L1, llamado punto infinito.
En la recta L1 sólo puede haber un punto infinito.
(Porque solo puede haber una recta L2 paralela a L1 cuando pasa por el punto A, y las dos rectas solo pueden tener una intersección.)
Conclusión:
1* Un conjunto de rectas paralelas sobre un plano, con infinitos puntos en común * * *.
(Para distinguirlo del infinito, los puntos en el plano original se llaman puntos ordinarios)
2* Cualesquiera dos líneas rectas que se cruzan L1 y L2 en el plano tienen un infinito diferente. puntos.
Razón: si no, L1 y L2 tienen un punto infinito común P ∞, y hay dos líneas rectas diferentes que pasan por dos puntos diferentes A y P∞, lo cual es inconsistente con el axioma.
3*. Todos los puntos infinitos forman una recta infinita.
Nota: El plano euclidiano forma naturalmente un plano proyectivo mediante la suma de un punto infinito y una línea recta infinita.
(2) Coordenadas homogéneas
Se introduce el sistema de coordenadas en la geometría analítica y se estudia el espacio euclidiano mediante métodos algebraicos.
Entre. Este método de coordenadas también se puede ampliar para establecer una fotografía plana en el plano fotográfico.
Sistema de coordenadas.
L2 l 1
l 1:a 1x+b 1y+c 1 = 0
L2: a2x+b2y+c2=0
Entre ellos, A1 y B1 no son iguales a 0 al mismo tiempo; A2 y B2 no son iguales a 0 al mismo tiempo.
Configuración
d = a 1 b 1 Dx = b 1 c 1 Dy = c 1 a 1
a2 b2 b2 c2 c2 a2
Si D≠0, entonces las dos rectas L1 y L2 se cortan en un punto común P(x, y), cuyas coordenadas son x=Dx/D, y = dy/d.
Esta La solución grupal se puede expresar como: x/dx = y/dy = 1/d.
(Convención: cuando los denominadores Dx y Dy son 0, el numerador correspondiente también debe ser 0)
La expresión anterior se puede resumir como (Dx, Dy, d).
Si D=0, L1∑L2, entonces l 1 y L2 se cruzan en el punto infinito P∞.
Este punto P∞ se puede representar mediante una recta L que pasa por el origen O y es paralela a L2.
La ecuación de esta recta L es: a2x+b2y=0.
Para unificar las coordenadas de puntos ordinarios y puntos infinitos, se utilizan las coordenadas de puntos
(x, y, z) significa que x, y, z no pueden ser cero al mismo tiempo, para el punto Normal,
(X, Y), tiene Z≠0, x=X/Z, y=Y/Z, por lo que hay:
Es decir,
X/Dx = Y/Dy = Z/D,
Existe una abstracción de coordenadas mejor, X, Y, Z), por lo que para infinito hay Z= 0.
También establecido.
Nota:
a). Si el número real p≠0, (pX, pY, pZ) y (X, Y, Z) representan el mismo punto. Esencialmente representado por (X:Y:Z). De estos tres componentes sólo dos son independientes.
& ltpre & gt;Las coordenadas con esta característica se denominan coordenadas homogéneas.
b) Existe una recta euclidiana L, y su ecuación en el sistema de coordenadas rectangular plano Oxy es:
ax+by+c=0
Entonces las coordenadas homogéneas de cualquier punto ordinario (X, Y) en L son (X, Y, Z), Z≠0, sustituye:
aX+bY+cZ=0
Las coordenadas (X, Y, Z) del punto infinito sumado a L deben satisfacer aX+bY=0, Z = 0, la ecuación de una línea recta infinitamente larga en el plano es naturalmente: ¡Z=0! !
⑶Curva elíptica en cualquier dominio
K es un dominio, y el plano fotográfico P2(K) en K es un conjunto de clases de equivalencia {(X:Y:Z)}. Considere la siguiente ecuación de Weierstrass (ecuación cúbica homogénea):
Y2Z+a 1x yz+a3yz 2 = X3+a2X2z+a4xz 2+a6z 3
(donde el coeficiente ai∈K , o ai∈K es un campo algebraicamente cerrado de K)
Se dice que la ecuación de Weierstrass es suave o no singular, lo que significa que se aplica a todos
Para lo siguiente El punto de proyección P=(X:Y:Z) ∈ P2(K),
F(X, Y, Z)= Y2Z+a 1x yz+a3yz 2-X3-a2X2Z-a4xz 2 - a6z 3 = 0
Al menos una de las tres derivadas parciales del punto P no lo es.
0 si esta ecuación se llama singular.
La definición de curva elíptica e:
La curva elíptica e es la ecuación suave de Weierstrass en P2(K).
Todos los conjuntos de soluciones.
Y2Z+a 1x yz+a3yz 2 = X3+a2X2Z+a4xz 2+a6z 3
Nota:
a) Hay exactamente uno en la elíptica El punto de la curva E se llama punto infinito. Es decir, (0:1:0) está representado por θ.
b) La ecuación de Weierstrass de la curva elíptica se puede expresar en forma de coordenadas no homogéneas:
Supongamos que x=X/Z, y=Y/Z, entonces la principio La ecuación se transforma en:
y2+a 1xy+a3y = x3+a2 x2+a4x+a6⑴
En este momento, la curva elíptica E es la ecuación (1) en el plano proyectivo P2(K) El conjunto de todas las soluciones puntuales triviales de , más un punto infinito θ.
c) Si a1, a2, a2, a4, a6∈K, entonces se dice que la curva elíptica E está definida en K, expresada por E/K. Si e puede definirse en k, entonces. k-
& ltpre & gt; El conjunto de puntos racionales se representa como E(K), que es el conjunto de todos los puntos de coordenadas racionales en E más el punto infinito θ.
(4) Curva elíptica en el dominio real r
Suponiendo que K=R, entonces la curva elíptica se puede expresar como una curva normal en el plano.
Punto, más el punto infinito θ.
Algoritmo de suma de puntos de curva elíptica en el campo de números reales r:
Supongamos que L ∈ P2(R) es una línea recta. Debido a que la ecuación de E es cúbica, L y E tienen exactamente tres puntos de intersección en P2(R), marcados como P, Q, R Q y R respectivamente.
(Nota: si L es tangente a E, entonces P, Q, R Q, R no son necesariamente diferentes). Defina la operación ⊙ en e de la siguiente manera:
Supongamos que P, Q ∈ E, l es la recta que conecta P y Q (si P=Q, l toma la recta tangente al punto P); sea la relación entre l y e Otro punto de intersección;
Luego toma la línea recta L' que conecta r e infinito. Entonces el otro punto de intersección de L' y e se define como P≥Q Q.
La imagen real de la página anterior es una generalización de la curva elíptica y2 = x3-x, que es una abstracción de la curva específica. Explique la operación más específicamente:
Supongamos que P=(x1, y1), Q=(x2, y2), P⊙Q=(x3, y3),
Desde P Q Partiendo de la definición, suponiendo que y=αx+β es la ecuación que pasa por la recta L entre P y Q, podemos calcular:
α=(y2-y1)/(x2-x1), β=y1- αx1
Obviamente, el punto (x, αx+β) de la recta L está sobre la curva elíptica E,
Si y sólo si (α x+ β) 2 = x3-x.
P⊙Q=(x1,y1) (x2,y2)=(x3,y3) =(x3,-αx3+β))
Donde x3 =α2-x 1-x2 =((y2-y 1)/(x2-x 1))2-x 1-x2;
y3 =-y 1+((y2-y 1)/(x2- x 1))(x 1-x3)
Cuando P=Q: P⊙Q=(x3, y3) Cálculo:
x3 =((3x 12-1) / 2y 1)2-2x 1;y3 =-y 1+((3x 12-1)/2y 1)(x 1-x3)
Nota:
a) Si Las líneas rectas L y E se cruzan con tres puntos P, Q, R Q y R (no necesariamente diferentes), entonces (P⊙Q)R=θ (como se puede ver en la figura).
b) Supongamos P∈E, P⊙θ =P (en este momento, supongamos Q= θ, es fácil ver que L = L’).
c) Para P, Q∈E es: p ⊙ q = q ⊙ p.
d) Supongamos que P∈E, entonces podemos encontrar -P∈E de modo que P -P= θ.
E) Supongamos que P, Q, R∈E tienen (P⊙Q)⊙R= P⊙(Q⊙R).
En resumen, sabemos que E pares de operaciones forman un grupo abeliano.
f) Las reglas anteriores se pueden extender a cualquier dominio, especialmente a los dominios finitos. Supongamos
La curva elíptica está definida en el campo finito Fq (q=pm), entonces
E(Fq)={(x, y)∈Fq×Fq | a 1xy +a3y = x3+a2 x2+a4x+a6 }∩{θ}
¿Verdad? ¿Qué pasa con el mar al final de la latitud? Grupo Senbel. Sea f q representar un campo finito de q elementos y use E(Fq) para representar la definición de Fq.
La curva elíptica e.
Teorema 1. (Teorema de Haas) Si el número de puntos de E(Fq) es #E(Fq), entonces
| #E(Fq)-q-1|≤2q1/2
>( 1) Curva elíptica en FP (campo de números primos, p es un número primo)
Texto p & gt3 a, b Fp 4a3+27b2 0 a b
Una ecuación de curva elíptica en Fp es:
y2=x3+ax+b ⑵
Todas sus soluciones (x, y), (x Fp, y Fp), más un nombre llamado "Hanghang" ?
¿Hacer clic? ¿Hermoso? ¿Caries┑cerebro? ¿Estúpida recaudación de fondos? Xia Qiao (Fp), mediante el teorema de Haas
Sabe: P+1-2p 1/2 ≤# E(FP)≤P+1+2p 1/2.
El conjunto E(Fp) corresponde a las siguientes reglas de suma, y se establece la suma.
Grupo Abel:
(i) θ⊙ θ=θ(elemento unitario)
(ii) (x, y)⊙ θ=(x , y), sea (x, y) ∈E(Fp)
(iii) (x, y)⊙ (x,-y)=θ, sea (x, y) ∈E(Fp ) , es decir, el inverso del punto (x, y).
Es (x, -y).
(iv) Supongamos que (x1, y1) y (x2, y2) son elementos no recíprocos en E(Fp), entonces
(x1, y1) ⊙ (x2 , y2) = (x3, y3), donde
x3=α2-2x1, y3= α(x1-x3)-y1
y α=(y2-y 1) / (x2-x1)(3).
(5) (Regla aritmética de dos puntos)
Supongamos (x1, y1) ∈ e (FP), y1 ≠ 0, entonces 2(x1, y1)=(x3 , y3), donde
x3= α2-2x1, y3=α(x1-x3)-y1
Aquí α = (3x12+A)/(2Y1) (4)
Nota: Si #E(Fp)=p+1, entonces la curva E(Fp) se llama supersingular; de lo contrario, se llama supersingular.
No es un número súper impar.
Ejemplo: Curva elíptica en F23
Supongamos que y2=x3+x+1 es una ecuación en F23 (a=b=1), entonces la curva elíptica
La solución de la ecuación de la recta en F23 es (punto y2=x3+x+1):
(0, 1), (0, 22), (1, 7), (1 , 16), (3, 10), (3, 13), (4, 0), (5, 4), (5, 19), (6, 4), </pre>
<pre>(6,19),(7,11),(7,12),(9,7),(9,11,3),(11,20),(12,4 ), (12, 19), (15438/pre>
<pre>(13,16),(17,3),(17,20),(18,3) ,(18,20),(19, 5),(19,18);θ.
El grupo E (F23) tiene 28 puntos (incluido el punto θ en el infinito).
Curva elíptica en F2m
.La elipse no singular definida por los parámetros a, b∈F2m y b≠0 en F2m
La curva circular E(F2m) es una ecuación
y2. +xy=x3+ax2+b ⑸
El conjunto solución (x, y), donde x, y∈F2m, junto con θ
Las reglas de suma de E(F2m) son las siguientes. :
(i) θ +θ= θ
(ii) Supongamos (x, y) ∈E(F2m), entonces (x, y)⊙ θ=(x, y).
(iii) Supongamos (x, y) ∈E(F2m), entonces (x, y)+(x, x+y) = θ,
Eso. es decir, el inverso del punto (x, y) es (x, x+y)
(iv) Reglas de suma para dos puntos diferentes y no equivalentes:
Hacer (. x1, y1), (x2, y2) ∈E(F2m) y x1≠x2
(x1, y1) (x2, y2) = ( x3, y3), donde
<. p>x3 =α2+α+x 1+x2+ay3=α(x1+x3)+x3+y1
Donde α= (y2+y1)/ (x2+x1)
㈤Regla de los dos puntos
Ordenar (x1, y1) ∈E(F2m), donde x1≠ 0. Regla
2( x1, y1)=(x3, y3), donde
X3 = α 2+α+a, Y3 = x12+(α+1) x3, Donde α = (x1+y1/x1)
Es fácil ver que el grupo E(F2m) es un grupo abeliano
Ejemplo: Curva elíptica en F24
p>F(x)=x4+ x+1 es un polinomio irreducible en F2, lo cual es fácil de ver.
F24=F2[x] / (f(x)) = {(k0, k1, k2, k3) | (k0, k1, k2, k3)=kk1α+k2α2+k3α3, </pre>
<pre>α es el punto cero de f(x), ki∈F2}
Supongamos que la curva elíptica no singular en F24 tiene la siguiente ecuación Definición :
Y2+xy=x3+α4x2+1. Tenga en cuenta que f(α)=0.
La ecuación debe expresarse como:
(1000)y2+(1000)xy =(1000)x3+(1100)x2+(1000)1985, n/pre>< /p >
& ltpre & gt;La base es la dificultad del problema de logaritmo discreto definido en el grupo de puntos de la curva elíptica.
(1) ¿Conoces el punto de E(Fq)? El grupo Bell de los monos dorados de Yunnan ubicado en la cúspide de latitud
Supongamos p∈E(Fq), si el período de p es grande, incluso si
P ⊙ P ⊙.. .⊙ P = θ ( * * * Añadido t P)
Se mantiene el entero positivo más pequeño t, con suerte t es grande.
(t = p periodo, expresado como ∏(p)=t).
Para Q∈E(Fq), debe haber un entero positivo m.
Q = m & ampmiddotP = p ⊙...⊙ P (* * *t P agregado)
Definición
M=㏒pQ ( m es el logaritmo de q con base p como base).
El grupo E(Fq) formado por los puntos de la curva elíptica y su logaritmo discreto.
Este problema es difícil. Las curvas elípticas de los campos base Fq y Fq se dan en forma definida.
Seleccione un punto con un período mayor en E(Fq), como el punto P=(xp, yp).
Su período es un número primo grande n, registrado como ∏ (P) = n (número primo).
Nota: En este criptosistema, la curva específica y el punto P y su n son
Esta es información pública. La forma del sistema criptográfico adopta el sistema Eigamal, que es relativamente completo.
Analogía.
a) Generación de claves
Bob (usuario) realizó los siguientes cálculos:
I) Seleccione aleatoriamente un entero en el intervalo [1, n-1] d.
Ii) Punto de cálculo Q:= Presión diferencial (fase de presión diferencial)
Iii) Bob reveló su clave pública - (E (FQ), P, N, Q )
Iv) La clave privada de Bob es un número entero d!
Alice quiere enviar el mensaje m a Bob. Alice ejecuta:
I) Encuentra la clave pública de Bob (E(Fq), p, n, Q),
Ii) Representar m como un elemento de dominio m∈Fq,
Iii) Seleccionar un número aleatorio k en el intervalo [1, n-1],
Iv) Según Puntos de cálculo de la clave pública de Bob (X1, y 1):= KP(k P fases).
v) Calcular el punto (x2, y2): = kq, si x2=0, volver al paso iii).
ⅵ) Calcular c:= m & middotx2
ⅶ) Envía datos cifrados (x1, y1, C) a Bob.
b) El proceso de descifrado de Bob
Bob recibe el texto cifrado de Alice (x1, y1, C) y lo ejecuta.
I) Usando la clave privada d, calcule el punto (x2, y2): = d (x1, y1), y luego calcule x2-1= en Fq.
Recupere los datos de texto plano calculando m:= C & middotX2-1.