1. No category

Criptografı́a
Juan Manuel Márquez Bobadilla
Ricardo Reyes Ortega
Andrés Garcı́a
Osbaldo Mata G.
Marı́a Paz Suárez Fernández
1
Re-escritura de palabras usando
transversales y coset-maps
Re-escritura de palabras usando transversales y coset-maps
Juan Manuel Márquez Bobadilla
Julio del 2016
Abstract.
Explicamos la noción de transversal de un subgrupo y las relaciones entre los procesos de reescritura en dos casos: 1) las demostraciones de los teoremas de Schreier y Kurosh acerca de
subgrupos de un grupo libre y un producto libre respectivamente, 2) proceso de re-escritura que
involucra al producto semidirecto de algunos coset-maps. Seremos expuestos a las propiedades
functoriales aplicadas del producto semidirecto de grupos de coset-maps, o equivalentemente
del producto wreath. Se tiene una generalización de la noción de transversal y re-escritura
(coding) en términos de ellos.
§ Introducción
Los procesos de re-escritura que las matemáticas disponen de forma formal (axiomático - deductivas)
dentro de la teorı́a de grupos datan de los años 1920-30s, en tiempos de Walter von Dyck, Kurt
Reidemeister, Otto Schreier, Jakob Nielsen y Alexander Kurosh entre otros. Pero a partir del 2008,
surge el álgebra de transversales fortalecida por el uso del producto semidirecto y los coset-maps.
Diremos que estudiamos los propiedades abstractas de un objeto contemporáneo llamado producto
wreath, una herramienta nueva que involucra factorizar.
Hagamos la siguiente interpretación y simplificación:
Sea G un grupo y sea H < G un subgrupo. Supongamos que X = {xj } puede ser ultilizado para
generar a los elementos de G. supongamos que estos elementos están ordenados empezado con
e < x1 < x1−1 < x2 < x−1
2 < ...
entonces podemos determinar para cualquiera dos “palabras” g1 , g2 ∈ G al comparar sus formas normales
g1 = a1 a2 · · · at ,
y
g2 = c1 c2 · · · cs ,
para determina cuando g1 ≤ g2 o viceversa.
2
Abreviemos Σ = H \ G. Entonces es posible definir un map Σ → G vı́a
Hw 7→ w = min Hw
Observe que si w = a1 a2 · · · at está en su forma normal o reducida entonces wa−1
es mı́nimo en
t
su coset.
Demostración: Sea w mı́nimo en la clase Hw. Sea w = a1 a2 · · · at la forma reducida. Sea m el
mı́nimo de la clase Hwa−1
t , luego
m ≤ wa−1
t .
Pero Hm = Hwa−1
t , entonces Hmat = Hw, por lo que mat ≥ w. Ası́,
m ≥ wa−1
t .
es mı́nimo en su clase 2
Por lo que wa−1
t
Sea T = {t} talque t = t, y los llamamos transversales módulo H. Por la observación demostrada,
decimos que la familia T tiene la propiedad de ser “closed under taking prefixes’’.
Entonces, à-la-Schrereir, definimos
b = tx tx
−1
,
donde t ∈ T y x ∈ X.
Con estas palabras estratégicas, veremos para cada palabra reducida w = a1 a2 · · · ar sucede
w = (ea1 ea1 −1 )(a1 a2 a1 a2 −1 )(a1 a2 a3 a1 a2 a3 −1 ) · · ·
o bien, con las palabras“iniciales”
w0
= e
w1
= a1
w2 = a1 a2
..
.
wr−1
wt
= a1 a2 · · · ar−1
= a1 a2 · · · ar = w
podemos tomar las palabras
wj−1 aj wj −1
que permiten factorizar la palabra original de esta manera:
w = (w0 a1 w1 −1 )(w1 a2 w2 −1 )(w2 a3 w3 −1 ) · · · (wr−1 ar wr −1 ).
Aplicación:
Ilustremos en dos ejemplos: 1) en el grupo simétrico S3 = h a, b | a2 = e , b3 = e , ab = b2 a i, y
2) en grupo libre de rango dos F2 = h a, b | i.
1) En el grupo simétrico.
Para el grupo simétrico S3 presentado y con nombre breve
G = h a, b | a2 = e , b3 = e , ab = b2 a i,
3
tomamos al subgrupo generado por a, H = (a) , y tomamos el cosets-set modulo H para tener
H\G = {Hb2 , Hb , He},
tomamos a los
T = {b2 , b , e}
como transversales módulo H, porque tiene la propiedad “closed under taking prefixes”, bajo el orden
natural
e < a < b < b−1 < ab < ab−1
Entonces calculamos las palabras no triviales:
−1
b2 ab2 a
−1
baba
eaea
= a,
= a,
−1
= a,
Aquı́ estamos viendo como todas ellas quedan en H.
2) En el grupo libre de rango dos.
Para el grupo F2 pensemos que esta generado por las dos letras {x, y} . Y entonces para w ∈ F2
pensamos que son generalizaciones -por ejemplo- de una palabra como
w = xy 6 x−1 y 3 x−1 y 4 x.
Ordenémoslas: e < x < x−1 < y < y −1 < x2 < xy < xy −1 < x−2 < x−1 y < x−1 y −1 < yx <
yx < y 2 < y −1 x < y −1 x−1 < y −2 < x3 < ... podremos siempre determinar de entre dos o más
palabras reducidas quien va primero.
−1
Sea H el subgrupo de F2 que consisten de palabras de longitud par. Entonces tenemos solo dos
cosets: H \ F2 = {Hx , He}. Ası́ T = {x , e} y si X = {x, y}, entonces calculamos:
xxxx−1 = x2 ,
xyxy −1 = xy,
yxyx−1 = yx.
Es sencillo ver que bastan estas tres palabras de longitud 2 para generar las nueves restantes de
la misma longitud dos, y en general, cualquier otra de longitud par, por lo que H = h{x2 , xy, yx}i
libremente y entonces F2 tiene un subgrupo libre de orden tres, o bien F3 ,→ F2
§ Definiciones en Diagramas
Grupo libre.
Con un diagrama como este:
X
,
⊂
: ¿∃F
¿∃! ᾱ ∈ hom : ᾱ|X = α?
∀α
∀Γ
4
preguntamos por un grupo F y un morfismo de grupos que tengan la propiedad de completar (el
diagrama conmutativo) con respecto a cualquier mapeo α hacia cualquier grupo Γ y produzca su
extensión α, un homomorfismo de grupos.
Bueno, se sabe que si para cualquier palabra w talque pueda ser expresada mediante
w = xss11 xss22 · · · xssrr ,
donde xsj están en X y los ij = ±1 para j = 1, ..., r, entonces podemos asignar hasta Γ mediante:
α(w) = α(xs1 )s1 α(xs2 )s2 · · · α(xsr )sr .
Esta mecanismo determina una única extensión α, pues se tiene α|X = α y que además es un morfismo
de grupos.
Productos libre.
∗
Sea σ Gσ el producto libre de una familia de grupos {Gσ }. Esto quiere decir que se tiene un
diagrama:
G
8 k k
ji
+
∀Gi
∃! Φ ∈ Hom
∗
∀Φi
Para una palabra g ∈
∗
k
∀Γ
Gk se dice que tiene una forma normal si para cuando factorizamos
g = a1 a2 · · · at
entonces para las sı́labas as ∈ Gis sucede
as ∈
/ Gis +1 , Gis −1 .
Luego, en caso de disponer de arbitrarios homomorfismos Φis podemos definir
Φ(g) = Φi1 (a1 )Φi2 (a2 ) · · · Φit (at ).
No es difı́cil demostrar que esto define un único homomorfismo de grupos.
Entonces enunciamos los teoremas:
(Teorema de Schreier). Si F es un grupo libre y H < F entonces H también es libre.
(Teorema de Kurosh). Si H es un subgrupo del producto libre
es un producto libre.
∗
s
Gs , entonces H también
Las demostraciones de estos teoremas Subgrupo consiste en encontrar subconjuntos
B⊂H<F
y
Yβ , Z ⊂ H <
5
∗G
σ
σ
los cuales completan los diagramas respectivos:
<H
i
-
B
"
ΓΣo H
α
∀α
τ
∀Γ
π
para H subgrupo en el caso libre, y
?H
i
∗* 9
j
σ
Gσ
jk
/
Yk , Z
Gk
Φ
Ψ
Ψk
# ΓΣ o
∗
∀φk , φ
t
∀Γ
σ
Gσ
π
en el caso de producto libre.
Las varias construcciones en los diagramas involucran operaciones entre grupos. Una es ΓΣ que es
el grupo de las funciones del conjunto Σ al grupo Γ. Otra es el producto wreath ΓΣ o G que usa el
producto semidirecto entre grupos.
Para cualquiera dos w, g ∈ F definimos fw : Σ → H vı́a
fw (Hg) = gw(wg)−1 ,
la cual da una manera de accesar H → H Σ o H vı́a
w 7→ (fw , w),
para, si se dispone de α : B → Γ entonces tenemos la composición H → H Σ o H → ΓΣ o H vı́a
w 7→ (fw , w) 7→ (a ◦ fw , w)
La especificación de quiénes son los subconjuntos B, Yk y Z serán precisadas en la versión completa
que será presentada durante la Escuela de Verano 2016 del Departamento de Matemáticas del CUCEI
de la Universidad de Guadalajara.
Para este curso veraniego, esta nota tiene por objeto ser adyacente a las pláticas del área de álgebra, y
esperamos sirvan para establecer algunas herramientas básicas contemporárenas que motivan el estudio
de procesos de factorizar, como idea central de un proceso de encriptado o des-encriptado. Durante
6
el evento trendremos oportunidad de exponer al oyente con los hechos estándar de la teorı́as de Grupos;
Campos; Módulos y las de Curvas Elı́pticas.
7
Campos Finitos
Campos finitos. (Generalidades)
Definición 0.1. Sea (A, +, ·) un conjunto con dos operaciones binarias definidas en él tal que
1. (A, +) es un grupo abeliano.
2. (A, ·) Es asociativo, es decir
(a · b) · c = a · (b · c) ∀a, b, c ∈ A.
3. Las leyes distributivas se cumplen; esto es,
a · (b + c) = a · b + a · c y (b + c) · a = b · a + c · a.
Entonces decimos que el conjunto (A, +, ·) es un anillo.
Observación 0.1. Una consecuencia de la definición de anillo se sigue de la propiedad general
a · 0 = 0 · a = 0 ∀a ∈ A, entonces (−a) · b = a · (−b) = −(ab) ∀a, b ∈ A.
Definición 0.2. Sea (A, +, ·) un anillo entonces:
(i) A se dice un anillo con unidad, si tiene identidad multiplicativa es decir si existe e tal que
ae = ea = a ∀a ∈ A.
(ii) A es un anillo conmutativo si · es una operación conmutativa.
(iii) A es llamado un dominio integral. Si A es un anillo conmutativo con unidad es decir, si
existe e 6= 0 en el cual ab = 0 implica que a = 0, b = 0.
(iv) A se dice un anillo con división si los elementos no cero de A forman un grupo bajo la
operación ·.
(v) (A, +, ·) es un campo. Si A es un anillo conmutativo con división.
Ejemplos 0.0.1. Los siguientes ejemplos ilustran las estructuras algebraicas definidas previamente.
(i) Sea G un grupo abeliano con +. Si definimos · en G por a·b = 0. Para todo a, b ∈ G; entonces
G es un anillo.
(ii) Los Z enteros forman un dominio integral, pero no forman un campo.
(iii) Los 2Z forman un anillo conmutativo sin unidad.
8
(iv) Si A := {f : f : R → R, tal que f es una función} con las operaciones
+:A×A
→
A
(f + g)(x) 7→ f (x) + g(x)
·:A×A
(f · g)(x)
→
7
→
A
f (x) · g(x)
∀x ∈ R
Entonces (A, +, ·) es un anillo conmutativo con unidad
(v) El conjunto de matrices de dimesión 2 × 2 forman un anillo no conmutativo con identidad
con respecto a la + y · de matrices.
Teorema 0.1. Todo dominio integral finito es un campo.
Dem. Obsérvese que como D es un dominio integral finito sin pérdida de generalidad podemos
suponer que D := {a1 , a2 , · · · , an .} Sea a ∈ D tal que a es fijo y a 6= 0. Entonces aa1 , aa2 , · · · , aan
son distintos porque si aai = aaj i 6= j, entonces a(ai − aj ) = 0 pero a 6= 0 se tiene que ai = aj .
Ası́ todos los elementos de A son de la forma aai , i = 1, · · · n, en particular, e = aai = ai a para
algún i. Luego ai es el inverso multiplicativo de a. Por tanto los elementos no cero de D son un
grupo abeliano, de donde D es un campo
Definición 0.3. Un subconjunto S de un anillo A es un subanillo de A, si (S, +, ·) es un anillo.
Definición 0.4. Un subconjunto I de A es un ideal si satisface:
(1) I es un subanillo de A.
(2) Para todo x ∈ I y a ∈ A se tiene que ax ∈ A y xa ∈ A.
Observación 0.2. Si consideramos R el campo de los reales y Q los racionales como anillo,
observese que el conjunto de los enteros Z es un subanillo de Q. Sin embargo Z no es un ideal en
Q dado que 1 ∈ Z, y 12 ∈ Q pero 1 · 12 = 12 6∈ Z
Dado que los ideales son subgrupos normales de los grupos aditivos de un anillo, por lo tanto un
ideal I define una partición de A, llamado las clases residuales módulo I denotado por
A/I := {[a] : a ∈ A}
donde
[a] := a + I
además,
a + I := {a + i : i ∈ I}
o equivalentemente se puede definir
[a] := {b ∈ A tal que a ≡ b mod I}
Definamos ahora en A/I dos operaciones binarias la suma y multiplicación de la siguiente manera
1) + : A/I × A/I → A/I
((a + I), (b + I)) 7→ (a + b) + I
2) · : A/I × A/I → A/I
(a + J) · (b + J) := a · b + J.
9
Observación 0.3. Notese que a, b ∈ A entonces a + b, a · b ∈ A, por lo tanto las operaciones
anteriores estan bien definidas. Además las operaciones binarias también pueden ser escritas de
la siguiente manera:
(1) [a] + [b] := [a + b]
(2) [a] · [b] := [a · b]
Entonces tenemos el siguiente resultado
Proposición 0.0.1. El conjunto (A/I, +, ·) tiene estructura de anillo. El cual es llamado el anillo
de las clases residuales o el anillo factor de A.
Dem. Sale directo de la definición de las operaciones binarias definidas previamente y utilizando
la estructura del anillo A.
Ejemplo 0.0.1. Z/(n) := {[0], [1], · · · , [n − 1]} donde [0] := 0 + (n), · · · , [n − 1] := (n − 1) + (n).
Teorema 0.2. Sea Z/(p), el anillo de clases residuales de los enteros módulo el ideal generado
por un p primo, entonces Z/(p) es un campo.
Dem. Por el teorema (0.1) es suficiente con demostrar que Z/(p) es un dominio integral. Dado
que [1] es una identidad de Z/(p), y [a][b] = [ab] = [0], si, y solo si ab = kp, para algún k ∈ Z. Por
otro lado dado que p es un número primo, p divide a ab si y sólo, si p divide a ó p divide b. De
donde [a] = [0] o [b] = [0]. Se sigue que Z/(p) no contiene divisores de cero. Finalmente se tiene
que Z/(p) es un campo.
Definición 0.5. Un campo finito es un campo con un número finito de elementos.
El siguiente es nuestro primer ejemplo de un campo finito.
Ejemplo 0.0.2. Supongamos que p = 3, entonces Z/(3) := {[0], [1], [2]}. En este caso Z/(3) es un
campo finito con operaciones definimos las siguientes operaciones binarias:
+
[0]
[1]
[2]
[0]
[0]
[1]
[2]
[1]
[1]
[2]
[0]
·
[0]
[1]
[2]
[2]
[2]
[0]
[1]
[0]
[0]
[0]
[0]
[1]
[0]
[1]
[2]
[2]
[0]
[2]
[1]
Definición 0.6. Sean p un número primo y Fp := {0, 1, · · · , p − 1} y ϕ : Z/(p) → Fp definido por
ϕ([a]) = a, para a = 0, · · · , p − 1. Entonces Fp tiene estructura de campo inducida por la función
ϕ además es un campo finito y se denomina el campo de Galois de orden p.
Ejemplo 0.0.3. Sean Z/(5) y F5 := {0, 1, 2, 3, 4}. Definamos el isomorfismo
ϕ([a]) = a.
Es decir [0] → 0, [1] → 1, [2]
binarias son:
+
0
1
2
3
4
→ 2, [3] → 3, [4] → 4. Entonces las tablas para las dos operaciones
0
0
1
2
3
4
1
1
2
3
4
0
2
2
3
4
0
1
3
3
4
0
1
2
·
0
1
2
3
4
4
4
0
1
2
3
0
0
0
0
0
0
1
0
1
2
3
4
2
0
2
4
1
3
3
0
3
1
4
2
4
0
4
3
2
1
Definición 0.7. Si A es un anillo arbitrario, entonces existe un entero n tal que
na = 0 ∀a ∈ A.
Entonces al mı́nimo n ∈ Z+ que cumple la condición se llama la caracterı́stica de A. Además se
dice que A tiene caracterı́stica (positiva) n.
10
Estructura de los campos finitos.
El campo de los Z módulo un número primo n, es el ejemplo más familiar de los campos finitos, él cual
consta de n elementos. En esta sección daremos algunas propiedades de los campos finitos.
0.0.1
Extensión de campos
Definición 0.8. Sea F un campo y (K, +, ·) un subcampo de F tal que K 6= F. Entonces se dice
que F es una extensión de K.
Observación 0.4. Un campo finito Fp con p primo, no contiene subcampos propios.
Ya que si suponemos que K es un campo propio de Fp , entonces K contiene 0, 1 pero por la clausura
K debe contener todos los elementos de Fp . Luego Fp es K.
Definición 0.9. Un campo que no contiene subcampos propios se llama campo primo.
Definición 0.10. Sea L la extensión del campo K. Si L es considerado como un espacio vectorial
de dimensión finita sobre K. La dimensión de L sobre K es el grado de L sobre K, y se denota
como [L : K].
Concluiremos con el siguiente resultado que da las condiciones de existencia y unicidad de los campos
finitos
Definición 0.11. Sea F un campo finitos con q elementos, y K un subcampo de F. Si
Y
xq − x :=
(x − a)
a∈F
entonces, xq − x ∈ K[x] factoriza en F[x] y F es un ”splitting field” de xq − x sobre K.
Teorema 0.3. Para todo primo p y para todo entero n. Existe un campo finito con pn elementos.
Además cualquier campo finito con q = pn elementos es isomorfo a un ”splitting field” de xq − x
sobre Fp
11
Espacios Proyectivos.
En el año de 1604, Kepler publica su obra “La parte óptica de la Astronomı́a”, en ella Kepler sugiere
agregar al plano un punto al infinito, esto con el fin de dotar a la parábola de un segundo foco, el cual
debiera encontrarse a una distancia infinita del primero.
Por otra parte en 1639, Desargues sugiere que la introducción de puntos imaginarios en el plano
podrı́a simplificar la Geometrı́a Euclidiana. Con ello cada lı́nea en el plano podrı́a dotarse de un punto
“al infinito”, de esta forma dos lı́neas distintas podrı́an intersecarse en exactamente un punto y además
esto permitirı́a introducir una dualidad entre puntos y lı́neas. Mientras esto sucedı́a, Fermat y Descartes
introducen en 1637 las coordenadas en la geometrı́a. Con la inclusión de este nuevo sistema se abrieron
las puertas a la introducción de una notación algebraica dada por Viète y Descartes, de aquı́ surgió la
Geometrı́a Analı́tica. Posteriormente, Moebiüs en 1827 y Plucker en 1830 logran introducir un sistema
coordenado al plano junto con esos puntos al infinito, al espacio obtenido se le llamó espacio proyectivo.
La idea de esta sección es definir curvas en el espacio proyectivo Pn (F), para un campo F. Para ello,
iniciaremos con la definición de curva en el plano, posteriormente introduciremos el espacio proyectivo.
Finalmente hablaremos de la relación, dada por la homogeneización y deshomogeneización de polinomios, entre las curvas en el plano y las curvas en el espacio proyectivo.
Espacios Afines
De manera general, consideraremos un campo F, algebraicamente cerrado.1 Al n-espacio afı́n AnF (o
simplemente An , si no hay confusión) lo definimos como el producto de n veces el campo F, esto es
F × ··· × F.
{z
}
|
n − veces
En otras palabras el conjunto AnF se define como
AnF := {(a1 , a2 , . . . , an )| ai ∈ F}.
Un ejemplo clásico de este espacio es cuando F = C o R. En nuestro caso utilizamos la notación AnF
en lugar de Fn pues el n-espacio afı́n estará dotado de una topologı́a particular, la Topologı́a de Zariski.
Esta topologı́a considera como conjunto cerrado a los conjuntos algebraicos, mismos que definimos a
continuación
Definición 0.0.1.
Un conjunto algebraico en An es el conjunto de ceros comunes a un cantidad finita de polinomios. Es decir, dado un conjunto finito de polinomios f1 , . . . , fm en F[x1 , . . . , xn ], el conjunto
de puntos p ∈ An tales que fi (p) = 0 para todo i = 1, . . . m es un conjunto algebraico y lo denotaremos como V (f1 , . . . fm ) por lo que
V (f1 , . . . , fm ) = {p ∈ An |fi (p) = 0, ∀i = 1, . . . , n} .
1 Esto significa que cualquier polinomio en F[x , . . . , x ] tiene todas sus raı́ces en F. Por ejemplo, R no es un
n
1
campo algebraicamente cerrado ya que el polinomio x2 + 1 no tiene raı́ces en R sino en C.
12
Cuando n = 1, el espacio A1 es llamado recta afı́n. Cuando n = 2, el espacio A2 es llamado el
plano afı́n. Un ejemplo importante de conjunto algebraico en el plano afı́n son las curvas planas.
Definición 0.0.2. Una curva plana es el conjunto algebraico en el espacio afı́n A2 definido por un
solo polinomio.
Ejemplo 0.0.3. Si tomamos el polinomio f (x, y) = x2 − y, entonces la curva plana es la parábola
definida por
V (x2 − y) = (a1 , a2 ) ∈ F2 | a1 = a22
esto es, el conjunto algebraico determinada por el polinomio x2 −y, el cual determina una parábola.
En general, si tomamos los conjuntos algebraicos de la forma
V (Ax2 + 2Bxy + Cy 2 + 2Dx + 2Ey + F )
donde A, B, C, D, E, F ∈ F, entonces estaremos considerando todas las curvas cónicas en A2 .
Además de las cónicas, podemos considerar las curvas cúbicas, esto es las curvas definidas por
polinomios de grado 3. De entre las cúbicas existe un tipo de curva muy importante, las elı́pticas.
Definición 0.0.4. Una curva elı́ptica sobre un campo F es una curva plana (no singular) definida
por V (y 2 − x3 − ax − b). Equivalentemente, una curva elı́ptica está determinada por la ecuación
y 2 = x3 + ax + b,
a, b ∈ F
(0.0.1)
Para que la ecuación determine una curva plana no singular, es necesario pedir que el discriminante
∆ = 4a3 + 27b2 sea no negativo (∆ ≥ 0). La ecuación (0.0.1) es conocida como la ecuación de
Weierstrass reducida.2
Ejemplo 0.0.5. Consideremos la ecuación y 2 = x3 +1. Como se indicó anteriormente, el conjunto
solución de la ecuación es igual al conjunto algebraico V (y 2 − x3 − 1) y por lo tanto, la cúbica es
un conjunto algebraico el cual está representado en la Figura 1.
Figure 1: Cúbica y 2 = x3 + 1.
Espacios Proyectivos.
Sea F un campo, y tomamos el conjunto AnF \ (0, 0, . . . , 0). Sobre este conjunto determinamos la
siguiente relación de equivalencia:
Dados dos puntos p, q ∈ AnF \ (0, 0, . . . , 0) decimos que son equivalentes (p ∼ q) si existe un escalar
λ ∈ F con λ 6= 0 y tal que p = λq.
2 La
ecuación de Wierstrass en su forma general es y 2 + axy + by = x3 + cx + dx + e.
13
Observación 0.0.6. De lo anterior se cumple que p y q son equivalentes si, y solo si existe una lı́nea
por el origen que los contenga. Por esta razón, las clases de equivalencia pueden ser representados
geométricamente por una lı́nea que pasa por el origen (recordando que el origen no forma parte de
la clase). Al conjunto de clases de equivalencia se le conoce como espacio proyectivo y es denotado
por P(AnF ), Pn−1
o simplemente Pn−1 cuando esté claro el campo F sobre el que está definido.
F
Tomando el caso n = 2, el espacio P1 = P(A2 ) es llamado recta proyectiva y puede ser pensado
como el conjunto de lı́neas por el origen en el plano afı́n A2 . Ası́ al tomar un representante de cada
clase obtenemos el semicı́rculo superior identificando los puntos (1, 0) y (0, 1) ya que determinan la
misma clase, quedando la Figura 2, donde cada recta por el origen es una clase de equivalencia.
(0,1)
(1,0)
(-1,0)
Figure 2: Espacio Proyectivo P2
Sin embargo, la elección de la clase puede tomarse de la manera que mejor convenga, Por ejemplo,
si consideramos un punto (x, y) tal que x 6= 0, entonces dicho punto pertenece a la misma clase que
(1, xy ) ası́ la clase de todos los puntos (x, y) con x 6= 0 determinan una recta, la recta x = 1. Para la
clase (x, y) con x = 0, el representante que consideramos es (0, 1). Con esto P1 puede representarse
mediante una recta y un punto “al infinito” obteniendo la Figura 3.
(0,1)
(1,0)
Figure 3: Espacio Proyectivo P2
Ejercicio: ¿Podrı́as determinar el dibujo correspondiente al espacio P2F ? ¿Cómo definir el espacio
afı́n y proyectivo para campos finitos?
14
0.0.2
Cartas coordenadas para el espacio proyectivo.
De ahora en adelante, a la clase de equivalencia de (x0 , . . . , xn ) ∈ An+1 \(0, . . . 0) en PnF la denotaremos
como [x0 : x1 : · · · : xn ]. Mas aún, si tomamos a (x0 , . . . , xn ) como antes entonces existe i, con 0 ≤
i ≤ n tal que xi 6= 0. En consecuencia, (x0 : x1 : · · · : xn ) ∼ (x0 /xi : x1 /xi : · · · : xi /xi : · · · : xn /xi )
y ası́ ambos puntos determinarán la misma clase de equivalencia en PnF , esto es
x0 x1
xi
xn
[x0 : x1 : · · · : xn ] =
:
: ··· :
: ··· :
.
xi xi
xi
xi
En otras palabras, toda clase de equivalencia en PnF tiene una expresión de la forma [x0 : · · · : 1 :
· · · xn ], con el 1 ubicado en la i-ésima entrada, para algún i con 1 ≤ i ≤ n. Con base en lo anterior
determinaremos un cubriente de PnF , para ello definamos los siguientes conjuntos
Ui := { [a0 : · · · : ai : · · · an ] ∈ PnF | , ai = 1 } .
Observación 0.0.7. Note que si (a0 , . . . , an ) es tal que ai 6= 0 y aj 6= 0 con i 6= j, entonces
[a0 : · · · : an ] ∈ Ui ∩ Uj .
Por otra parte para cada i, tendremos una biyección entre Ui y An , la cual está definida en el
siguiente resultado:
Proposición 0.0.8. La aplicación φi : Ui → An definido por :
[a1 : a2 : · · · : ai−1 : 1 : ai+1 : · · · : an+1 ] 7→ (a1 , a2 , . . . ai−1 , ai+1 , . . . , an+1 )
es una biyección.3 .
Para una lectura más amplia relacionada con este resultado consulte [5, Cap. 4].
Ahora bien, ya que todo punto p ∈ PnF está contenido en al menos un subconjunto Ui , entonces
{Ui }ni=0 es una cubierta abierta para PnF . 4
Por lo anterior tenemos que para la recta proyectiva P1F , el cubriente está compuesto por dos
conjuntos (abiertos de Zariski), U0 y U1 , cada uno de los cuales puede considerarse una recta afı́n AF ,
en virtud de la Proposición 0.0.8. Por lo tanto, podemos pensar en P1F como un conjunto cubierto por
dos rectas afines. En este caso un dibujo de los cubrientes se observa en la Figura 4.
(1,1)
(0,1)
(1,0)
Figure 4: Cubrientes afines del P1F
3 La Proposición puede escribirse de manera más general al definir la topologı́a de Zariski en el espacio afı́n y en
el espacio proyectivo. En este caso la Proposición determina que φi es un homeomorfismo, vea [8, Prop. 2.2]
4 La cubierta es llamada cubierta por espacios afines
15
De manera similar, P2F está cubierto por tres conjuntos (abiertos de Zariski), U0 , U1 y U2 los cuales
son isomorfos al plano afı́n A2F . El dibujo obtenido es la Figura 5.
Figure 5: Planos que cubren a P2F
Polinomios y sus soluciones.
Cuando consideramos un polinomio f ∈ F[x1 , . . . xn ], las raı́ces de f determinan la variedad algebraica
afı́n V (f ). Para el espacio proyectivo la situación es diferente, ya que los puntos en el proyectivo
son clases de equivalencia y para que un punto p ∈ PnF sea raı́z del polinomio f , entonces al evaluar
f en cualquier representante de p, el resultado debe ser cero, es decir la raı́z no debe depender del
representante de p.
Ejemplo 0.0.9. Consideremos los puntos (1, 1), (2, 2) ∈ A2 note que (1, 1) ∼ (2, 2), es decir
[1 : 1] = [2 : 2] ∈ P1F . Sin embargo, si tomamos el polinomio f (x, y) = x2 − y, entonces f (1, 1) = 0
y f (2, 2) 6= 0. Por lo tanto el punto p := [1 : 1] no es raı́z de f pues depende del representante
elegido. Más aún, se puede observar que el polinomio f ası́ definido no tiene raı́ces en el proyectivo.
El problema es que el valor de f siempre depende del representante.
Para evitar la dependencia mostrada en el ejemplo anterior es necesario que si p = [a1 : · · · :
an ], entonces f (λa0 , . . . λan )=0, para todo λ ∈ F. Esta condición nos lleva a considerar polinomios
homogéneos.
Definición 0.0.10. Sea d ∈ Z, un polinomio F ∈ F[x1 , . . . , xn+1 ] es un polinomio homogéneo de
grado d si para cualquier escalar λ se cumple que F (λx1 , . . . , λxn ) = λd F (x1 , . . . , xn ).
Un ejemplo de polinomio homogéneo en R[x, y, z] es F (x, y, z) = x2 y − 3zy 2 + 5zxy. En este caso,
F es homogéneo de grado 3.
Notación: De ahora en adelante los polinomios homogéneos serán denotados con mayúsculas.
Ahora bien, si F es homogéneo de grado d, entonces F (a0 , . . . , an ) = 0 implica F (λa0 , . . . λan ) =
λd F (a0 , . . . an ) = 0 y ası́ F se anula en cualquier punto de la forma (λa0 , . . . λan ). Esto nos lleva a la
siguiente
Definición 0.0.11. Sea F ∈ F[x0 , . . . xn ] un polinomio homogéneo y p = [a0 : · · · : an ] ∈ PnF .
Diremos que p es cero (raı́z) de F y escribiremos F (p) = 0 si F (a0 , . . . , an ) = 0.
A continuación introduciremos las raı́ces de polinomios homogéneos como subespacios del espacio
proyectivo y analizaremos los conceptos de homogeneización y deshomogeneización como el procedimiento que permite definir los subconjuntos de raı́ces en cada una de las cartas Ui . Iniciemos entonces
recordando algunos conceptos básicos.
16
Definición 0.0.12. Una variedad proyectiva se define como el conjunto de ceros comunes a un
número finito de polinomios homogéneos. Equivalentemente una variedad proyectiva es V (F1 , . . . Fm ),
donde Fi son homogéneos y
V (F1 , . . . Fm ) := {p ∈ PnF | Fj (p) = 0, ∀j = 1, . . . , m}
Las variedades proyectivas serán denotadas como V (F1 , . . . , Fm ), donde los polinomios Fj ∈
F[x0 , . . . , xn ] son homogéneos y no necesariamente del mismo grado. En consecuencia, una variedad
proyectiva es un subconjunto de Pn definido como
V (F1 , . . . Fm ) := { p ∈ Pn | Fj (p) = 0, ∀j = 1, . . . , m } .
Ahora bien ya que Pn tiene un cubriente {Ui }ni=0 , quisiéramos determinar la variedad V (F1 , . . . Fm )
en la carta Un , es decir quisieramos determinar el conjunto de puntos V (F1 , . . . Fm ) ∩ Un . Esto es
posible a partir de los polinomios homogéneos Fj que definen a V (F1 , . . . , Fm ).
Definición 0.0.13. Sea F ∈ F[x0 , . . . xn ] un polinomio homogéneo. La deshomogeneización de
F (x0 , . . . , xn ) se define como el polinomio obtenido al hacer xn = 1, esto es F (x0 , . . . , xn−1 , 1). La
deshomogeneización de F se denota por F∗ .
Ejemplo 0.0.14. Si F (x0 , . . . , xn ) = x20 + x22 + · · · + x2n , entonces la deshomogeneización es
F∗ = x20 + x22 + · · · + 1.
Observe que la deshomogeneización F∗ es ahora un polinomio no homogéneo en n variables, esto
es F∗ ∈ F[x0 , . . . xn−1 ]. Además si p = [a0 : · · · : an−1 : 1] ∈ Pn es tal que F (a0 , . . . an−1 , 1) = 0,
entonces F∗ (a0 , . . . , an−1 ) = 0.
Ejemplo 0.0.15. Como segundo ejemplo, consideramos la variedad proyectiva V (F ) ⊂ P2C determinada por el polinomio F (x, y, z) = x2 y−3zy 2 +5xyz. La deshomogeneización es F∗ = x2 −3y 2 +5xy.
Por tanto la variedad V (F ) en la carta U2 corresponde a V (x2 + 5xy − 3y 2 ). Dicha variedad afı́n
corresponde a la cónica dada por dos rectas no paralelas
Del ejemplo anterior, si quisiéramos determinar la variedad V (F ) en cada una de las cartas podrı́amos
considerar “deshomogeneizar” en cada una de las variables. Ası́ para x = 1 obtendrı́amos V (y − 3zy 2 +
5yz) = V (y, 1 + 5z − 3zy = V (y) ∪ V (1 + 5z − 3zy) siendo una cúbica que se expresa como la unión
de una recta con una cónica. Por otra parte si hacemos y = 1, entonces nos queda V (x2 − 3z + 5xz)
lo que determina una hipérbola.
A la variedad proyectiva V (F ) ⊂ P2F dada por un solo polinomio homogéneo, le llamaremos curva
proyectiva. Si además F ∈ F[x, y, z], entonces las curva es llamada curva plana proyectiva.
Ejemplo 0.0.16. Una curva en P2C está determinada por un polinomio homogéneo (en tres variables). Más generalmente, está definida por tres curvas, una por cada carta Ui , las cuales están
pegadas entre si. Si tomamos
F (x, y, z) = y 2 z − x2 z − x3 ,
entonces la curva proyectiva correspondiente está definida por tres curvas afı́nes:
En U0 está dada por V (y 2 z − z − 1). En U1 la curva es V (z − x2 z − x3 ) mientras que en U2
obtendremos V (y 2 − x2 − x3 ).
Al lector interesado en las curvas del espacio proyectivo le recomendamos la siguientes lecturas
[5, 6, 8, 13, 17].
17
Criptografı́a
Introducción
La palabra criptografı́a proviene de la palabra “Kriptos” que significa oculto y “graphia”, que significa
escritura. Es el arte de escribir con clave secreta.
El objetivo de la critptografı́a es la protección de información ante observadores no autorizados.
Desde tiempos remotos hasta la actualidad se han enviado mensajes secretos.
Clásicamente, estos mensajes eran utilizados en la diplomacia y su auge fué en la segunda guerra
mundial, útimamente son usados principalmente para mantener seguras las transacciones financieras.
Hoy los métodos combinan los dǵitos del mensaje con otros, y también aparecen algoritmos de gran
complejidad como el DES (inventado por IBM).
Existen trabajos fundamentales sobre los que se apoya toda la criptográfia, como los que citamos a
continuación:
1. A mathematical theory of communication and Communication theory of secrecy systems (1948 −
1949, Claude Shannon )
2. New directions in Cryptography. Escrito por Whitfield Diffie y Martin Hellman en (1976). En este
trabajo se proporciona la criptografı́a de la clave pública.
3. Con el algoritmo RSA en (1977). La criptografı́a alcanza su consolidación.
La criptografı́a tiene las siguientes funciones de seguridad en la información.
1. Confidencialidad. Solamente usuarios autorizados tienen acceso a la información.
2. Integridad de la información. Garantı́a ofrecida a los usuarios de que la información original
no será alterada, tanto como intencionalmente o accidentalmente.
3. Autentificación de usuario. Es un proceso que permite al sistema verificar si el usuario que
accede es auténtico.
4. Autentificación del remitente. Es el proceso que certifica que el mensaje recibido fué
realmente enviado por el remitente.
5. Autentificación del destinatario. Garantiza la identidad del usuario destinatario.
6. No repudio en origen. Que cuando se reciba el mensaje, el remitente no puede negar que ha
enviado el mensaje.
7. No repudio en destino. Que el destinatario no pueda negar no haber recibido el mensaje.
8. Autenticidad de actualidad. Probar que el mensaje es actual.
Los avances de los métodos de factorización, exigen números cada vez mayores a fin de garantizar
la seguridad de los criptosistemas lo cual genenera un inconveniente a la hora de implementar los
algoritmos para la generación y distrubución de claves secretas.
18
El problema se resuelve usando el sistema de cifrado de curvas elı́pticas, estos criptosistemas ofrecen
la seguridad equivalente a los métodos tradicionales, ( RSA, ELGamal, etc.,) pero con un número
menor de dı́gitos obteniendo como ventaja claves más pequeñas, dicha ventaja es muy útil en particular
en circuitos integrados y tarjetas inteligentes. (Ver [9])
Criptografı́a
0.0.3
Aritmética modular y criptografı́a
Existe un sistema secreto fundado en la teorı́a de módulos, el cual tuvo su origen en sistema llamado
Julio Cesar y su auge fue a finales de los años 70. (Ver [15]) Este método consiste en traducir letras en
números como se muestra en la siguiente tabla:
Equivalencia entre letras y números
letra
Eq num
A
0
B
1
C
2
D
3
E
4
F
5
G
6
H
7
I
8
J
9
K
10
L
11
M
12
N
13
O
14
P
15
Q
16
R
17
S
18
T
19
U
20
V
21
W
22
X
23
Y
24
Z
25
Dicho sistema transforma cada letra de un texto enviado en un texto diferente llamado criptosistema.
Para describir el sistema, sea P la equivalencia numérica de una letra en el mensaje enviado y C la
equivalencia numérica del texto encriptado. Entonces
C ≡ P + 3 (mod 26)
Texto
enviado
Texto
encriptado
A
0
3
D
B
1
4
E
C
2
5
F
D
3
6
G
E
4
7
H
F
5
8
I
G
6
9
J
H
7
10
K
I
8
11
L
J
9
12
M
K
10
13
N
L
11
14
O
M
12
15
P
N
13
16
Q
(0.0.2)
O
14
17
R
P
15
18
S
Q
16
19
T
R
17
20
U
S
18
21
V
T
19
22
W
U
20
23
X
V
21
24
Y
W
22
25
Z
X
23
0
A
Y
24
1
B
Z
25
2
C
La ecuación (0.0.2) junto con la previa tabla se le conoce como el algoritmo de Julio Cesar. Para
entender mejor consideremos el siguiente ejemplo.
Ejemplo 0.0.4. Dado el mensaje
PRUEBA
entonces:
1. Reagrupemos nuestro mensaje en un subconjunto de 5 letras más el resto
P RU EBA 
/ P RU EB A .
2. Traducimos el mensaje con la tabla previa y obtenemos el siguiente código
15 17 20 4 1
0
3. Dado que P ≡ C + 3(mod26) entonces, sumando 3 a nuestro código obtenemos:
18 20 23 7 4
4. Al traducir el mensaje enviado es
SUXHED
19
3
5. Que traducido en números tenemos
18 20 23 7 4
3
15 17 20 4 1
0
6. Después de restar 3 se sigue:
7. Traduciendo
P RU EB A 
/ P RU EBA .
En el campo de la criptografı́a, la aplicación de las curvas generalmente son curvas planas y las encontramos en la factorización de un número primo, los cuales fueron desarrollados por Bosma, GolwasserKillian, Atkin y Lenstra y algunos mas. Sin embargo H.W. Lenstra ha obtenido un nuevo método de
factorización que mejora los métodos conocidos anteriormente aunque la mejora no se refleja en la
práctica este mecanismo exhibe que los métodos de factorización no son tan seguros como parecı́a,
además los avances computacionales exigen números cada vez mayores para poder garantizar la seguridad en la factorización.
En la criptografı́a asimétrica o también llamada la criptografı́a de dos claves, se consideran un par de
claves para enviar el mensaje:
1. La clave pública. Se puede entregar a cualquier persona.
2. La clave privada. La debe guardar el propietario de tal forma que solo él tenga acceso.
Algunos algoritmos y tecnologı́as de clave asimétrica son:
• Diffie-Hellman.
• RSA.
• Criptografı́a de curva elı́ptica.
• Criptosistemas de Merkle-Hellman.
• Goldwasser-Micalli.
• Goldwasser-Micalli-Rivest.
Un Protocolo describe como un algoritmo debe usarse. Algunos protocolos que usan los anteriores
algoritmos son:
• DSS y DSA (Digital Signature Standard and Algorithm.)
• PGP
• GPG
• SSH
• SSL
• TLS
20
Uno de los sistemas de criptografı́a de clave pública más comúnes es el sistema RSA, las siglas
significan Rivest, Shamir y Adleman debido a sus autores todos contemporáneos. Por ejemplo Ronald
L. Rivest, nacido en 1947 en la ciudad de Nueva York, Estados Unidos. Adi Shamir, matemático de
nacionalidad israelı́, nació en 1952. L. Adleman nacido el 31 de diciembre de 1945, en California,
Estados Unidos. Curiosamente él es biólogo molecular, infortamático teórico, matemático y critógrafo.
El sistema RSA
El sistema fué desarrollado en 1977. Es válido tanto para cifrar como para firmar digitalmente.
Los mensajes enviados se representan mediante números, y el funcionamiento se basa en el producto,
conocido, de dos números primos de orden de 10200 elegidos al azar y mantenidos en secreto. Se prevé
que su tamaño crezca con el aumento de la capacidad de cálculo de los ordenadores.
Se cree que RSA será seguro mientras no se conozcan formas rápidas de descomponer un número
grande en producto de primos.
La computación cuántica podrı́a proveer de una solución a este problema de factorización.
Criptografı́a de Curva Elı́ptica
El sistema ECC (por sus siglas en inglés), fué propuesta de manera independiente por Neal Koblitz y
Victor Miller en 1985.
Una de las ventajas de la criptografı́a elı́ptica requiere de claves más pequeñas.
y se usa para sistemas para identificación por tarjetas.
Recordemos que una curva elı́ptica en su forma más general esta definida por:
V (Ax3 + Bx2 y + Cx2 z + Dxyz + Ey 2 x + Gy 3 + Hz 3 + Iz 2 x + Lz 2 y).
ver 0.0.4, o equivalentemente en su forma de Weierstrass:
y 2 z + a1 xyz + a2 yz 2 = x3 + a3 x2 z + a4 xz 2 + a5 z 3 , ai ∈ K,
y en el plano afı́n, las curvas elı́pticas son:
y 2 + a1 xy + a2 y = x3 + a3 x2 + a4 x + a5 , ai ∈ K
(0.0.3)
finalmente si definimos y como
1
1
y := y + a1 x + a3
2
2
La ecuación (0.0.3) se reduce a
y 2 = x3 +
Si x := x +
b2
12
b6
b2 2 b4
x + x+
4
2
4
se tiene
y 2 = x3 + 27c4 x − 54c6 .
Asumiendo char(F) 6= 2, 3, entonces la ecuación reducida de Weierstrass es
y 2 = x3 + ax + b, a, b ∈ F
Si ∆ = 4a3 + 27b2 , obtenemos la siguiente clasificación:
• ∆ 6= 0 La curva C no tiene puntos singulares.
• ∆ = 0 y a = 0 La curva C tiene una cúspide.
• ∆ = 0 y a 6= 0 La curva C tiene un nodo.
Observación 0.5. Nosotros nos enfocaremos en curvas elı́pticas sin puntos singulares. (Ver [4])
21
Ejemplo 0.0.5. Sean y 2 = x3 + x + 6 y y 2 = x3 − 14x − 15 dos curvas elı́pticas en su forma
reducida de Weierstrass, las cuales las podemos gráficar utilizando el paquete sage5 mediante las
siguientes instrucciones:
sage:
sage:
sage:
sage:
E=EllipticCurve [1,6]\\
plot( E, -2,2 )\\
E=EllipticCurve [-14,-15]\\
plot( E, -5,5 ] )\\
De donde se tiene
figura 1. y 2 = x3 + x + 6
figura 2. y 2 = x3 − 14x − 15
5 Este
programa se puede encontrar en http:www.sagemath.org/
22
Estructura de grupo de una curva elı́ptica
Teorema 0.4. Teorema de la base finita de Mordell (1923). (Ver [9])
Si C es una cúbica no singular sobre Q, existe un conjunto finito de puntos racionales sobre C tales
que los puntos racionales se pueden encontrar haciendo construcciones de tangentes y secantes a
partir de estos.
Observación 0.6. Si tenemos una curva de grado 3:
1) La recta que pasa por dos puntos, corta a una tercera en un tercer punto.
2) Si dos puntos son racionales el tercero también lo es.
Consideremos P, Q ∈ C y L la recta secante que pasa por P, Q, R o tangente si P = Q.
figura 3. P, Q, R ∈ C, P + Q ∈ C
La anterior gráfica nos define la suma de puntos en una curva elı́ptica C.
Basandonos en lo anterior podemos afirmar:
(C, +) es un grupo abeliano dado que se cumplen las siguientes propiedades:
1. (P + Q) + R = O, O = [0 : 1 : 0].
2. P + O = P, ∀P ∈ C.
3. ∀P ∈ C ∃(−P ) ∈ C. P + (−P ) = O.
4. (P + Q) + R = P + (Q + R), ∀P, Q, R ∈ C.
Observación 0.7. Recordemos que salvo isomorfismos, existe exactamente un grupo cı́clico para
cada cantidad finita de elementos, y los grupos cı́clicos normalmente se denotan simplemente por
el grupo canónico al que son isomorfos: si el grupo es de orden n, para n entero, dicho grupo es el
grupo Zn de enteros {0, · · · , n − 1} bajo la adición módulo n.
23
Ejemplo 0.0.6. Sea la curva elı́ptica C
y 2 = x3 + ax + b mod(p)
la cual es una curva plana, con conjunto de soluciones (p, q) ∈ Zp × Zp , p > 3 primo.
Ahora construiremos el grupo en la curva C, sean P = (x1 , y1 ), Q = (x2 , y2 ) y O. Si x2 = x1 ,
y2 = −y1 entonces P + Q = O. Por otro lado, si x3 = λ2 − x1 − x2 , y3 = λ(x1 − x3 ) − y1 entonces,
P + Q = (x3 , y3 )
donde
λ=



y2 −y1
x2 −x1 ,
Si P 6= Q


3x21 +a
2y1 ,
Si P = Q.
Además
P + O = O + P = P ∀P ∈ C.
Por lo tanto (C, +) es un grupo abeliano. Y para |C| es cercana a p, (por teorema de Hasse) se
tiene
√
√
p + 1 − 2 p ≤ |C| ≤ p + 1 + 2 p.
Ahora nos preguntamos, ¿cómo podemos calcular el número de puntos de una curva
elı́ptica? En la práctica se procede de la siguiente manera:
1) Por fuerza bruta. Probando los puntos que satisfaga la ecuación.
2) Partir de P ∈ C y calculando 2P, 3P hasta obtener el subgrupo hP i = C
3) Cuando #C es un número primo. Entonces cualquier P ∈ C tal que P 6= O es cualquier
generador de la curva elı́ptica C.
4) Algoritmo de Schoof (1985). Calcula el número de puntos de una curva C con una complejidad
O(Log28 (p))
5) En casos particulares C := y 2 = x3 + ax, y 2 = x3 + b Se recomienda el algoritmo de Munuera
Tena (1993).
O(Log28 (p))
A continuación veremos un ejemplo, donde ilustraremos la obtención de los puntos de una curva
elı́ptica utilizando el Algoritmo de Schoof utilizando el paquete singular.
Ejemplo 0.0.7. Si C := {(x, y) ∈ Z11 × Z11 : y 2 = x3 + x + 6} es una curva elı́ptica C, descrita
previamente en la gráfica, entonces con las siguientes instrucciones de singular
"LIB Crypto.lib";
ring r=0,(x,y),lp;
Schoof(11,1,6);
13;
Se observa:
1) C, contiene 13 puntos es decir 12 puntos y el punto al infinito O = (0 : 1 : 0).
2) C es un grupo cı́clico e isomorfo al campo Z13 , i.e. C ' Z13 .
Además para encontrar los puntos de la curva podemos utilizar el paquete sage de la siguiente
manera:
24
sage:
sage:
sage:
sage:
sage:
sage:
sage:
sage:
sage:
sage:
p=11
F_p=GF(p)
a= F_p(1)
b=F_p(6)
E=EllipticCurve([a,b])
m=E.order()
print m, "=",factor(m)
s=E.random_element()
print s
[10 : 2 : 1]
En este caso [10 : 2 : 1] representa un punto de C en coordenadas proyectivas. Si consideramos la
proposición 0.0.8 entonces [10 : 2 : 1] lo podemos identificar con (10, 2) ∈ U2 , de donde obtenemos
los siguientes puntos:
x
y
0
N o existe
1
N o exite
2
4, 7
3
5, 6
4
N o existe
5
2, 9
6
N o existe
7
2, 9
8
3, 8
9 N o, existe
10
2, 9
De la anterior tabla podemos observar lo siguiente, si elegimos p = (2, 7), como punto base,
entonces 2p = (2, 7) + (2, 7).
Por otro lado sea
λ = (3 × 22 + 1)(2 × 7)−1 (mod11)
= 2 × 3−1 mod(11)
= 2 × 4 mod(11)
= 8.
De donde x3 = 82 − 2 − 2 mod(11), y3 = 8(2 − 5) − 7 mod(11) = −31 mod(11) = −9 mod(11) = 2.
Finalmente se tiene que 2p = (5, 2).
En general la criptografı́a de una curva elı́ptica consiste en:
a) Escoger una curva elı́ptica
b) La curva elı́ptica tiene un conjunto de soluciones (x, y)
c) Si los valores pertenecen a un campo finito, entonces los puntos sobre la curva forman un grupo.
d) Tómamos un elemento del grupo y hallamos su logaritmo discreto
6
El logaritmo elı́ptico
6 Recordemos que para una base dada los logaritmos se definen como ax = b si, y sólo si, x = log b.
a
Además los Logaritmos discretos. Es lo mismo que los logaritmos comunes pero en vez de movernos en el campo
de los reales nos moveremos en el grupo discreto.
25
El problema del logaritmo elı́ptico en C respecto a P consiste en encontrar s ∈ Z tal que
Q = sP con P, Q ∈ C en caso de que exista.
El logaritmo elı́ptico nos servirá de base para obtener algoritmos criptográficos de intercambio de
claves y de firma digital.
Algunos algoritmos para calcular el logaritmo elı́ptico, (ver [15])
1) Algoritmo de Silver-Pohlig-Hellma. Este algoritmo consiste en la factorización en (p − 1)
números primos y se elige el primo más grande de la factorización.
√
2) Algoritmo de Pollard el cual necesita
nπ
2
sumas para obtener el logaritmo elı́ptico.
3) Algoritmo NFS (Number field sieve). Proporciona un algoritmo subexponencial.
4) El método de xedni-calculus,(Silverman). Aquı́ se proyectan r combinaciones lineales sobre
el plano y se considera la curva que contiene esos puntos de la proyección.
Elección de la curva
Para la elección de la curva elı́ptica, exı́sten varios métodos o técnicas que describimos a continuación:
• La conjetura de Weil. Es una técnica de elección de la curva sobre Fp , cuando m el orden
es divisible por un número pequeño
• Método global. Tomar una curva sobre los racionales y reducirla modulo un primo p para
obtener una curva sobre un campo finito.
• Método de multiplicación compleja. Este método permite la elección de la curva antes de
construirla.
• Método de elección aleatoria.
1. Se elige la curva de forma aleatoria.
2. Se fija un cuerpo finito Fp
3. Se asume Char(F) 6= 2, 3
4. C := y 2 = x3 + ax + b, a, b ∈ Fp satisface 4a3 + 27b2 6= 0 Se calcula el número de puntos
de la curva y se factoriza.
Criptografı́a y protocolos criptográficos basados en curvas elı́pticas.
Algunos protocolos más comunes son:
• Protocolo de Diffie-Helman usando curvas elı́pticas.
• Los usuarios A y B eligen una curva elı́ptica E sobre un cuerpo finito Zp y un número p primo
grande.
• Rango Normativo
• NITS: National Institute of Standards and Technology.
Ahora nos enfocaremos en el protocolo de Diffie-Helman, el cual describiremos en el siguiente
ejemplo.
Ejemplo 0.0.8. Protocolo Diffie-Helman
Sea C := {(x, y) ∈ Z113 × Z113 : y 2 = x3 + x + 6} una curva elı́ptica la cual tiene orden 117 por
tanto tenemos un isomorfismo con Z117 .
Como P = (31, 83) tiene orden 117, por lo tanto es un generador de la curva C.
26
Protocolo
Ahora describiremos el protocolo:
Sean A, B el emisor y receptor respectivamente. el cual denotaremos en forma simbólica por
A −→ B
1) El usuario A elige un número entero grande nA , y calcula KA = nA P, ahora A envı́a KA a
B, por ejemplo A toma nA = 98, entonces, KA = nA P = (53, 62)
2) B elige un número grande nB , calcula KB = nB P y envia KB a A, B −→ A. Si B elige el
número nB = 101, KB = nB P = (105, 86), B envia a A.
3) A calcula K = nA nB P = 98 · 101(31, 83) = (17, 23), A −→ B
4) El usuario B calcula K = nB KA = nB nA P = 101(53, 62) = (17, 23), B −→ A
5) A, B toman K como clave de sesión en este caso (17, 23).
Utilización del software SAGE para la descripción del protocolo Diffie-Helman
Primero definimos un campo finito como en el anterior ejemplo F113 , con las siguientes instrucciones:
sage: F=FiniteField(113)
ahora, consideramos la curva elı́ptica general con parámetros [a, b, c, d, e]
y 2 + axy + cy = x3 + bx2 + dx + e.
En partı́cular consideremos
y 2 = x3 + x + 6,
en sage seria:
sage: E=EllipticCurve(F,[0,0,0,1,6])
Para calcular el orden de la curva elı́ptica se tiene
sage: print(E.cardinality())
117
Por otro lado elegimos un punto base y calculamos se orden
sage:P=E.point((31,83))
sage:P.order()
entonces el usuario A calcula kA = 98P y el usuario B calcula kB = 101P que en sage seria,
sage:k_A=98*P
sage:k_B=101*P
finalmente se comprueba que los dos usuarios comparten la misma clave común.
sage: k=n_A*k_B=n_B*k_A
sage: print 101*k_A,98*k_B
[17 : 23 : 1], [17 : 23 : 1]
27
Bibliography
[1] G. Baumslag, T. Camps, B. Fine, G. Rosenberg, X. Xu, Designing Key Transport Protocols
Using Combinatorial Group Theory, in Algebraic Methods in Cryptography, Mainz, Germany,
Contemporary Math. 418, (35-43), 2005.
[2] S. R. Blackburn, C. Cid, C. Mullan, Cryptanalysis of three matrix-based key establishment
protocols, Journal of Mathematical Cryptology 5(2) , (2011).
[3] Oleg Bogopolski, Introduction to group theory, European Math. Soc. 2002.
[4] E.Brieskorn-H.Knörrer, Plane Algebraic Curves. Birckäuser Verlag, 1986.
[5] W. Fulton, Algebraic Curves, Addison Wesley Publishing.
[6] P.A. Griffiths, Introduction to Algebraic Curves, Translations of Mathematical Monographs Vol.
76.
[7] M. Hall, The Theory of Groups, McMillan Co., (1967).
[8] R. Hartshorne, Algebraic Geometry, Springer Verlag.
[9] N.Koblitz,Elliptic curve cryptosystems. Mathematics of Computation 48, pp203-209.
[10] H. Kuhn, Subgroup theorems for groups presented by generators and relations, Annals of
Math, 56, No. 1,(1952), 22-41.
[11] A. Kurosh, Die Unterprodukte der freien Produkte von beliebigen Gruppen. Math. Ann., 109,
(1934), 647-660.
[12] S. McLane, A proof of the subgroup theorem for free products, Mathematika 5, (1958), 13-19.
[13] R. Miranda, Algebraic curves and Riemann Surfaces. Graduate studies in Mathematics, AMS.
[14] L. Ribes, B.Steinberg, A wreath product approach to classical subgroup theorems,
L’Enseignement Mathematique (2) 56, (2010), 49-72.
[15] K.Rosen, Elementary Number and Its Applications. Addison-Wesley, 1984.
[16] O. Schreier, Die Untergruppen der freien Gruppen, Abh. Math. Sem. Hamburg Univ., 5,
(1927), 161-183.
[17] Martin Schlichenmaier, Lectures Notes in Physics. An introduction to Riemann Surface, Algebraic Curves and Moduli Space. Springer-Verlag.
[18] A. Weir, The Reidemeister-Schreier and Kurosh subgroup theorems, Mathematika 3, (1956),
47-55.
28