CENTRO FEDERAL DE EDUCAÇÃO

TECNOLÓGICA DE MINAS GERAIS - CEFETMG

Departamento de Matemática

Uma Pequena Introdução à Criptografia com Curvas elípticas

Belo Horizonte, 2026

Conteúdo
1 Introdução 2

2 Introdução as Curvas Algébricas e Suas Aplicações 3

2.1 Curvas afins . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2 Aplicações do Teorema de Bézout - caso afim . . . . . . . . . . . . . . . . 12
2.3 Plano projetivo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

3 Curvas Elípticas 16
3.1 A Regra Geométrica da Soma . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.2 Estrutura de Grupo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.3 Regra Algébrica da Soma . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.3.1 Lei de Grupo para E/K : y 2 = x3 + ax + b, char(K) ̸= 2, 3 . . . . . 20
3.3.2 Lei de grupo para E/F2m não-supersingular: y 2 +xy = x3 +ax2 +b 23
3.3.3 Lei de grupo para E/F2m supersingular: y 2 + cy = x3 + ax + b . 24
3.4 Ordem do Grupo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.5 Estrutura do Grupo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.6 Representação por Coordenadas Homogêneas . . . . . . . . . . . . . . . . . 26

4 Criptografia com Curvas elípticas 27

4.1 Troca de Chave Diffie-Hellman . . . . . . . . . . . . . . . . . . . . . . . . . 27
4.2 Massey-Omura . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
4.3 O Problema do Logaritmo Discreto . . . . . . . . . . . . . . . . . . . . . . 31
4.4 O Criptossistema Menezes-Vanstone . . . . . . . . . . . . . . . . . . . . . . 37
4.5 Ataques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

1
1 Introdução
Estas notas têm como objetivo apresentar uma introdução às curvas elípticas e à criptogra-
fia baseada nessas curvas, reunindo os principais conceitos necessários para compreender
seus fundamentos matemáticos e suas aplicações. Inicialmente, são revisados tópicos de
curvas algébricas, como curvas afins, o plano projetivo e resultados básicos da geometria
algébrica. Em seguida, são estudadas as curvas elípticas, destacando sua estrutura de
grupo, a lei de composição e diferentes representações. Na parte final, são introduzidos os
principais protocolos criptográficos baseados em curvas elípticas, bem como o problema
do logaritmo discreto e alguns algoritmos de ataque. Ao longo do texto, são apresen-
tados exemplos resolvidos que ilustram os conceitos e algoritmos discutidos, tornando o
conteúdo mais acessível ao leitor.
Embora o material tenha caráter introdutório, recomenda-se que o leitor possua conhe-
cimentos prévios de Álgebra, especialmente de estruturas algébricas, como grupos, anéis
e corpos. Familiaridade com teoria dos números e álgebra linear também é desejável, pois
esses tópicos constituem a base matemática necessária para o estudo das curvas elípticas
e de suas aplicações em criptografia.

2
2 Introdução as Curvas Algébricas e Suas Aplicações
Definição 1. Uma curva algébrica plana é o lugar dos pontos cujas coordenadas satisfa-
zem uma equação do tipo f (x, y) = 0, onde f é um polinômio não constante.

As curvas algébricas planas começaram a serem estudadas há mais de dois mil anos,
muito antes de usar o sistema de coordenadas em geometria. Elas eram estudadas de uma
maneira mais primitiva, como lugares geométricos.
Por exemplo,

1. A parábola é o lugar geométrico dos pontos do plano equidistantes de um ponto

fixo, denominado foco, e de uma reta fixa, denominada diretriz.

2. A elipse é o lugar geométrico dos pontos de um plano cuja soma das distâncias a
dois pontos fixos, denominados focos, é constante.

No final do século 17, o método de Fermat e Descartes para descrever um lugar geomé-
trico no plano por meio de equações de duas variáveis já era bastante conhecido. Usando
métodos de cálculo diferencial as curvas algébricas reais apareceram para reformular vários
problemas
O estudo das curvas algébricas planas envolve relações muito interessantes entre várias
áreas da matemática, entre elas a Álgebra e a Geometria. Além disso, pode-se encontrar
curvas em diversas áreas Segue alguns exemplos de curvas que certamente são conhecidas.

3
Exemplo 1. A reta é um exemplo de uma curva.

Figura 1: Gráfico de uma Reta

Fonte: próprio autor.

Exemplo 2. A Elipse também é uma curva.

Figura 2: Gráfico de uma elipse

Fonte: próprio autor.

Podemos usar as propriedades da elipse para construir a sala do sussurro.

Figura 3: Sala do Sussurro

4
Exemplo 3. A Parábola é uma curva.

Figura 4: Parábola

Fonte: próprio autor.

Podemos ver a aplicação da parábola Igreja da Pampulha.

Figura 5: Igreja da São Francisco na Pampulha

Fonte: [Link]

Fonte: Oliveira. T. C

5
Exemplo 4. Concoide de Nicomedes usada para resolver problema de cálculo de médias
proporcionais.

Figura 6: Gráfico da Concoide de Nicomedes

Fonte: próprio autor.

Exemplo 5. A Folium de Descartes dé usada principalmente em estudos de Geometria

Algébrica e Geometria Analítica, sendo utilizada na análise de curvas algébricas, singula-
ridades e parametrizações.

Figura 7: Gráfico da Folium de Descartes

Fonte: próprio autor.

6
2.1 Curvas afins
Seja k um corpo e An = k × . . . × k = {(a1 , . . . , an ) / ai ∈ k, ∀ i}. An (k) ou simplesmente
An é chamado de espaço afim, ou n−espaço afim.
Para n = 1 temos a reta afim, para n = 2 temos o plano afim.
Seja k um corpo algebricamente fechado e f (x, y) um polinômio não nulo em k[x, y].
Denotamos por Vk (f ) o conjunto dos pontos em k 2 da curva algébrica plana afim, ou
simplesmente, curva algébrica, determinada por f (x, y), isto é,

C = Vk (f ) = {(x, y) ∈ k 2 / f (x, y) = 0}

O grau da curva C é igual ao grau do polinômio que a define.

Exemplo 6. As Curvas Elípticas são curvas afins e usadas em criptografia.

Figura 8: Gráfico de uma Curva elíptica

Fonte: próprio autor.

Um polinômio é dito homogêneo quando todos os seus termos tem o mesmo grau.

Exemplo 7. O polinômio P (x, y, z) = 3x8 − 2x3 y 5 + x7 z − 5x2 y 6 é um exemplo de

polinômio homogêneo.

Seja C é uma curva definida por f ∈ k[x, y]. Observe que f admite uma fatoração, pois
todo anel de polinômios sobre um corpo é domínio de fatoração única. Assim, podemos
escrever f da seguinte forma:
f = f1n1 · · · fknk ,

onde f ′ is São polinômios irredutíveis não-associados. Cada curva definida por fi é cha-
mada de uma componente de f .

7
Exemplo 8. Seja C definida por f (x, y) = x2 − y 2 = (x − y)(x + y). As componentes
aqui são f1 = x − y e f2 = x + y.

Definição 2. Uma curva algébrica C é chamada redutível se existem curvas algébricas

distintas irredutíveis C1 e C2 tais que C = C1 ∪ C2 . Se C não puder ser escrita como a
união de duas ou mais curvas redutíveis, dizemos que C é irredutível.

Exemplo 9. a) A reta é uma curva irredutível, por exemplo f (x, y) = x + y.

b) A curva C definida por p(x, y) = xy é uma curva redutível, pois se p se decompõe

em p1 (x, y) = x e p2 (x, y) = y que definem duas curvas irredutíveis.

Proposição 2.1. A interseção de duas curvas algébricas planas sem componentes em

comum é finita.

Exemplo 10. Seja C1 uma curva plana definida por f (x, y) = x2 − y 2 e C2 uma curva
plana definida por g(x, y) = (x − y)x. A interseção de C1 e C2 é finita? A resposta é não.
Observe que a interseção das curvas f e g é a reta x = y, ou seja, possui infinitos pontos
de interseção.

Figura 9: Inteseção de f e g

Fonte: próprio autor.

Exemplo 11. Podemos ver abaixo exemplos de curvas que se intersectam em uma quan-
tidade infinita de pontos, finita e caso que não se intersectam.

8
 Figura 10: Interseção de duas retas

Fonte: próprio autor.

Figura 11: Interseção de uma parábola e uma circunferência

Fonte: próprio autor.

Figura 12: Interseção de uma parábola e uma circunferência

Fonte: próprio autor.

Como encontrar a interseção de duas curvas C1 e C2 definidas por f e g respectiva-

mente, com f, g ∈ k[x, y]?
Sejam f, g ∈ k[x, y]. Selecione uma das variáveis, digamos x, e escreva f e g como

9
polinômios em y com coeficientes em k[x]:

f (x, y) = a0 y m + . . . + am , m ≥ 1 e g(x, y) = b0 y n + . . . + bn , n ≥ 1.

Definimos a resultante de f e g por

a0 . . . am 0 ... 0 0
0 a0 . . . am 0 ... 0
.. .. .. .. .. .. ..
. . . . . . .
R = Rf,g = 0 0 0 0 a0 . . . am
b0 ... bn 0 ... ... 0
.. .. .. .. .. .. ..
. . . . . . .
0 ... 0 0 b0 ... bn

determinante da matriz (m + n) × (m + n) com n linhas a′ s e m linhas b′ s, [1]

Exemplo 12. Sejam f (x, y) = y 2 + x2 − 4 e g(x, y) = xy − 1, Calcule a resultante de f

eg

Solução 1. Escrevendo os polinômios em função da variável y, obtemos

f (x, y) = y 2 + 0 · y + (x2 − 4)

e
g(x, y) = xy − 1 = (x)y − 1.

Assim,
a0 = 1, a1 = 0, a2 = x2 − 4,

e
b0 = x, b1 = −1.

Como m = 2 e n = 1, a matriz é
 
1 0 x2 − 4
x −1 0 ,
 

0 x −1

cujo determinante é a resultante de f e g.

10
 Calculando o determinante pela primeira linha,

1 0 x2 − 4
Rf,g (x) = x −1 0
0 x −1
−1 0 x −1
=1 + (x2 − 4)
x −1 0 x
= 1 (−1)(−1) − 0 · x + (x2 − 4)(x2 )

= 1 + x2 (x2 − 4)
= x4 − 4x2 + 1.

Portanto,
Rf,g (x) = x4 − 4x2 + 1.

Como verificação, da equação g(x, y) = 0, temos:

xy − 1 = 0

segue que
1
y= , x ̸= 0.
x
Substituindo em f (x, y) = 0, obtemos

1
+ x2 − 4 = 0.
x2

Multiplicando ambos os membros por x2 , resulta

x4 − 4x2 + 1 = 0,

que coincide exatamente com a resultante calculada.

Definição 3. Seja f ∈ k[x, y] − {k} e escreva f = f0 + . . . + fd , onde cada fi é homogêneo

de grau i e fd ̸= 0. Cada componente ax + by de fd é chamada de uma direção assintótica
de f .

Exemplo 13. 1) f (x, y) = 1 − xy tem direções assintóticas x e y.

2) f (x, y) = y 2 − x tem apenas a direção assintótica y

Proposição 2.2. O grau da resultante de duas curvas sem direção assintótica em comum
é
deg(Rf,g ) = deg(f ).deg(g).

11
Teorema 2.3. (Teorema de Bézout- Caso afim) Sejam C e D duas curvas algébricas
definidas por f e g de graus m e n respectivamente. Supondo que C e D não tem
componentes em comum, ou seja, f e g não possuem fatores em comum. Então C e D
têm no máximo mn pontos de interseção, isto é, #C ∩ D ≤ deg(C).deg(D).

2.2 Aplicações do Teorema de Bézout - caso afim

Proposição 2.4. Sejam P1 , . . . , P5 cinco pontos distintos em posição geral em um plano.
Então existe no máximo uma cônica passando por eles.
Teorema 2.5. (Teorema do hexágono de Pascal) Sejam P1 , . . . , P6 seis pontos distintos
sobre uma cônica irredutível C. Se as retas P1 P2 e P4 P5 se intersectam em Q1 , se as retas
P2 P3 e P5 P6 se intersectam em Q2 e se as retas P3 P4 e P6 P1 se intersectam em Q3 , então
os pontos Q1 , Q2 , Q3 são colineares.

Figura 13: Ilustração geométrica do Teorema

Fonte: Próprio autor

Definição 4. Seja C uma curva definida por f . Um ponto P ∈ C é chamado ponto

singular de C se
∂f ∂f
(P ) = (P ) = 0.
∂x ∂y
O conjunto de pontos singulares de C é denotado por Sing(C).
Proposição 2.6. Seja C uma curva algébrica. Então Sing(C) é finito.

2.3 Plano projetivo

Considere a curva xy = 1 e suas assíntotas (eixo x e eixo y). Observe que as assin-
totas nunca encosta na curva em R2 , mas no plano que chamados de projetivo, elas se

12
intersectam no infinito.

Figura 14: A hipérbole e suas assíntotas

Fonte: Próprio autor

Seja k um corpo A3 = {(x, y, z) / x, y, z ∈ k}. Considere a seguinte relação em

A3 − {(0, 0, 0)}
(x1 , y1 , z1 ) ∼ (x2 , y2 , z2 ) ⇔ ∃ λ ∈ k com λ ̸= 0 tal que (x1 , y1 , z1 ) = λ(x2 , y2 , z2 ).
A relação acima é uma relação de equivalência em A3 − {(0, 0, 0)} .
A classe de (x, y, z) ̸= (0, 0, 0) denotada por (x : y : z), ou seja, todo ponto da forma
(a : b : c) é visto como (a : b : c) = {(x, y, z) ∈ A3 / (x, y, z) = λ(a, b, c) com λ ̸= 0}
Definimos P2 = A3 − {(0, 0, 0)} / ∼ como o plano projetivo. Os pontos (x : y : z) são
chamados de coordenadas homogêneas de P2 .
Considere
φ : A2 −→ P2 , φ(x, y) = (x : y : 1).

Observe que φ é injetiva. De fato, suponha que

φ(x, y) = φ(x′ , y ′ ).

Então,
(x : y : 1) = (x′ : y ′ : 1′ )

como pontos de P2 . Pela definição de coordenadas homogêneas, existe um escalar λ não

nulo, tal que
(x, y, 1) = λ(x′ , y ′ , 1).

Comparando a terceira coordenada, obtemos

1 = λ · 1,

13
logo λ = 1. Consequentemente,

x = x′ e y = y′.

Assim,
(x, y) = (x′ , y ′ ),

o que prova que φ é injetiva.

Podemos também interpretar o plano projetivo P2 , como P2 = A2 ∪ L∞ , onde L∞ =

{(x : y : 0) / x ̸= 0 ou y ̸= 0}. Cada ponto da forma (x : y : 0) com x ̸= 0 ou y ̸= 0 é dito
um ponto no infinito.

Definição 5. Uma curva projetiva C em P2 é um subconjunto de P2 que satisfaz

C = {(x, y, z) ∈ P2 / F (x, y, z) = 0, F ∈ k[x, y, z]}

e F é um polinômio homogêneo.
Ou ainda, uma curva plana projetiva C é uma classe de equivalência de polinômios
homogêneos não constantes, F ∈ k[x, y, z], módulo uma relação que identifica dois tais
polinômios, F, G, se um for múltiplo constante um do outro.

O grau da curva projetiva C definida por F (x, y, z) é o grau de F (x, y, z).

Exemplo 14. Vemos aqui dois exemplos de curvas projetivas

1. A equação da reta em P2 é dada por ax + by + cz = 0;

2. F (x, y, z) = z 3 + xyz

Exemplo 15. Duas curvas sempre se intersectam em P2 , inclusive duas retas paralelas.

Figura 15: Trilhos paralelos Figura 16: Trilhos intersectando no infinito

14
 Podemos ver os pontos no infinito nas pinturas artísticas e na construção, como mostras
as figuras 17, 18 e 19. O ponto no infinito nesses casos é chamado de fuga.

Figura 17: Santa ceia com ponto de fuga Figura 18: Santíssima Trindade com ponto
no olho esquerdo de Cristo de fuga nos pés da cruz

Figura 19: Palácio Planalto com dois pontos de fuga

Fonte: Gonçalves. T. S

Proposição 2.7. Sejam F e G curvas planas projetivas. Então F ∩ G é finita, se e

somente se, F e G não admitem componentes em comum.

Teorema 2.8. Teorema de Bézout Se F e G são curvas planas projetivas sem com-
ponentes em comum, então o número de pontos na interseção F ∩ G, contados com
multiplicidade, é igual a deg(G).deg(F ). Isto é

#F ∩ G = deg(G).deg(F ).

15
3 Curvas Elípticas
Essa seção é baseada no livro [7] e tem como objetivo introduzir o estudo das curvas
elípticas, destacando a estrutura de grupo que elas apresentam.

Definição 6. Uma curva elíptica E sobre um corpo K é definida por uma equação

E : y 2 + a1 xy + a3 y = x3 + a2 x2 + a4 x + a6 (1)

onde a1 , a2 , a3 , a4 , a6 ∈ K e ∆ ̸= 0, onde ∆ é o discriminante de E e é definido como

segue: 
∆ = −d22 d8 − 8d34 − 27d26 + 9d2 d4 d6 



2
d2 = a1 + 4a2





d4 = 2a4 + a1 a3 (2)


d6 = a23 + 4a6





2 2 2 

d8 = a1 a6 + 4a2 a6 − a1 a3 a4 + a2 a3 − a4 .
Se L é qualquer corpo de extensão de K, então o conjunto de pontos L-racionais sobre
Eé
E(L) = {(x, y) ∈ L × L : y 2 + a1 xy + a3 y − x3 − a2 x2 − a4 x − a6 = 0} ∪ {∞}

em que ∞ é um ponto no infinito.

Exemplo 16. (Curvas elípticas sobre R) Considere as curvas elípticas

E1 : y 2 = x3 − x
1 5
E 2 : y 2 = x3 + x +
4 4

definidas sobre o corpo R dos números reais. Os pontos E1 (R) \ {∞} e E2 (R) \ {∞} estão
representados na Figura a seguir.

Definição 7. Duas curvas elípticas E1 e E2 definidas sobre K e dadas pelas equações de

Weierstrass

E1 : y 2 + a1 xy + a3 y = x3 + a2 x2 + a4 x + a6
E2 : y 2 + ā1 xy + ā3 y = x3 + ā2 x2 + ā4 x + ā6

são ditas isomórficas sobre K se existirem u, r, s, t ∈ K, u ̸= 0, tais que a mudança de

variáveis
(x, y) → (u2 x + r, u3 y + u2 sx + t) (3)

transforma a equação E1 na equação E2 . A transformação (3) é chamada de mudança de

variáveis admissível.

16
 Figura 20: Exemplo de gráfico de Curvas Elípticas

Fonte: Extraído de [7]

Considere uma equação de Weierstrass dada por

E : y 2 + a1 xy + a3 y = x3 + a2 x2 + a4 x + a6 (4)

definida sobre K pode ser simplificada consideravelmente através da aplicação de mudan-

ças de variáveis admissíveis. Consideramos separadamente os casos em que o corpo K
possui característica diferente de 2 e 3, ou possui característica igual a 2 ou 3.
1. Se a característica de K não for igual a 2 ou 3, então a mudança admissível de
variáveis
x − 3a21 − 12a2 y − 3a1 x a31 + 4a1 a2 − 12a3
 
(x, y) → , −
36 216 24
transforma E na curva
y 2 = x3 + ax + b (5)

onde a, b ∈ K. O discriminante desta curva é ∆ = −16(4a3 + 27b2 ).

2. Se a característica de K for 2, então há dois casos a considerar.
Caso 1: a1 ̸= 0
A mudança de variáveis admissível

a2 a4 + a2
 
a3
(x, y) → a21 x + , a31 y + 1 3 3
a1 a1

transforma E na curva
y 2 + xy = x3 + ax2 + b (6)

onde a, b ∈ K. Tal curva é dita não-supersingular e possui discriminante ∆ = b.

17
 Caso 2: a1 = 0
A mudança de variáveis admissível

(x, y) → (x + a2 , y)

transforma E na curva
y 2 + cy = x3 + ax + b (7)

onde a, b, c ∈ K. Tal curva é dita supersingular e possui discriminante ∆ = c4 .

Se a característica de K é 3, então há dois casos a considerar.
Caso 1: a21 ̸= −a2
A mudança admissível de variáveis
 
d4 d4
(x, y) → x + , y + a1 x + a1 + a3 ,
d2 d2

onde d2 = a21 + a2 e d4 = a4 − a1 a3 , transforma E na curva

y 2 = x3 + ax2 + b (8)

onde a, b ∈ K. Tal curva é dita não-supersingular e possui discriminante ∆ = −a3 b.

Caso 2: a21 = −a2
A mudança admissível de variáveis

(x, y) → (x, y + a1 x + a3 )

transforma E na curva
y 2 = x3 + ax + b (9)

onde a, b ∈ K. Tal curva é dita supersingular e possui discriminante ∆ = −a3 .

3.1 A Regra Geométrica da Soma

A operação de soma em uma curva elíptica E é realizada através do método secante-
tangente, uma construção geométrica que permite obter um terceiro ponto R a partir de
dois pontos dados, P e Q.

• Soma de pontos distintos (P ̸= Q): Traça-se uma reta s que passa pelos pontos
P e Q. Como a equação da curva possui grau 3, essa reta intersecta a curva em um
terceiro ponto T (onde T ∈ s ∩ E). Define-se a soma P + Q = R, sendo R o ponto
obtido pela reflexão de T em relação ao eixo x.

• Soma de pontos idênticos (P = Q): Neste caso, a reta s é a reta tangente à

18
 curva no ponto P . A reta tangente intersecta a curva em um ponto T . O resultado
2P é a reflexão de T em relação ao eixo x.

• Caso vertical: Se a reta s for perpendicular ao eixo x, não existe uma terceira
interseção finita com a curva. Convenciona-se, então, que P + Q = ∞, onde θ é
chamado de ponto no infinito.

Figura 21: Soma de Pontos da curva

Fonte: Extraído de [7]

3.2 Estrutura de Grupo

O conjunto de pontos E(K), munido da operação de soma elíptica, satisfaz os axiomas
de um grupo abeliano:

1. Fechamento: Se P, Q ∈ E, então (P + Q) ∈ E.

2. Associatividade: Para quaisquer pontos P, Q, S ∈ E, tem-se (P + Q) + S =

P + (Q + S).

3. Existência de elemento neutro: Existe um ponto θ tal que P + θ = P para todo

P ∈ E.

4. Existência de elemento inverso: Para todo P ∈ E, existe um ponto Q ∈ E

(simbolizado por −P ) tal que P + Q = ∞.

5. Comutatividade: Para quaisquer pontos P, Q ∈ E, tem-se P + Q = Q + P .

19
 Figura 22: Associativa

Fonte: Extraído de [6]

Figura 23: Elemento Inverso

Fonte: Extraído de [6]

3.3 Regra Algébrica da Soma

3.3.1 Lei de Grupo para E/K : y 2 = x3 + ax + b, char(K) ̸= 2, 3

1) Identidade. P + ∞ = ∞ + P = P para todo P ∈ E(K).

2) Elementos inversos. Se P = (x, y) ∈ E(K), então (x, y) + (x, −y) = ∞. O ponto

(x, −y) é denotado por −P e é chamado de negativo de P ; note que −P é, de fato, um
ponto em E(K). Além disso, −∞ = ∞.
3) Adição de pontos. Sejam P = (x1 , y1 ) ∈ E(K) e Q = (x2 , y2 ) ∈ E(K), onde
P ̸= ±Q. Então P + Q = (x3 , y3 ), onde:
 2  
y2 − y1 y2 − y1
x3 = − x1 − x2 e y3 = (x1 − x3 ) − y1 .
x2 − x1 x2 − x1

4) Duplicação de ponto. Seja P = (x1 , y1 ) ∈ E(K), onde P ̸= −P . Então

20
2P = (x3 , y3 ), onde:
2
3x21 + a 3x21 + a
  
x3 = − 2x1 e y3 = (x1 − x3 ) − y1 .
2y1 2y1

Exemplo 17. Curva elíptica sobre o corpo primo F29

Seja p = 29, a = 4 e b = 20, e considere a curva elíptica

E : y 2 = x3 + 4x + 20

definida sobre F29 . Note que

∆ = −16(4a3 + 27b2 ) = −176896 ̸≡ 0 (mod 29),

logo E é de fato uma curva elíptica.

Exemplo 18. Os pontos em E(F29 ) são os seguintes:

∞, (2, 6), (4, 19), (8, 10), (13, 23), (16, 2), (19, 16), (27, 2),
(0, 7), (2, 23), (5, 7), (8, 19), (14, 6), (16, 27), (20, 3), (27, 27),
(0, 22), (3, 1), (5, 22), (10, 4), (14, 23), (17, 10), (20, 26),
(1, 5), (3, 28), (6, 12), (10, 25), (15, 2), (17, 19), (24, 7),
(1, 24), (4, 10), (6, 17), (13, 6), (15, 27), (19, 13), (24, 22).

Exemplos de adição na curva elíptica são:

(5, 22) + (16, 27) = (13, 6),

e
2(5, 22) = (14, 6).

Exemplo 19 (Corpo Binário ). F2m são corpos finitos binários de característica 2. Uma
maneira de construir F2m é com base polinomial. para essa construção, vamos considerar
os coeficientes em F2 = {0, 1} e o grau máximo m − 1.

F2m = {am−1 z m−1 + am−2 z m−2 + · · · + a2 z 2 + a1 z + a0 : ai ∈ {0, 1}}.

O Número de elementos de F2m é 2m .

Aritmética em F2m

1. Adição e Subtração São operações idênticas e extremamente eficientes:

(a)

21
 I) Realizadas através da soma dos coeficientes módulo 2.

2. Multiplicação e Inverso Para garantir que o resultado permaneça no corpo:

(a) Escolhe-se um polinômio irredutível f (z) de grau m.

(b) O produto é calculado como: r(z) = [a(z) · b(z)] (mod f (z)).
(c) f (z) atua como um "número primo"para polinômios.

Exemplo 20. (Corpo binário F24 ).

Considere o corpo finito F24 construído a partir do polinômio irredutível

f (z) = z 4 + z + 1.

Os elementos de F24 podem ser representados pelos polinômios binários de grau inferior
a 4, isto é,

0 z2 z3 z3 + z2
1 z2 + 1 z3 + 1 z3 + z2 + 1
z z2 + z z3 + z z3 + z2 + z
z + 1 z 2 + z + 1 z 3 + z + 1 z 3 + z 2 + z + 1.
A seguir, apresentam-se alguns exemplos de operações em F24 .

1. Soma:
(z 3 + z 2 + 1) + (z 2 + z + 1) = z 3 + z.

2. Subtração:
(z 3 + z 2 + 1) − (z 2 + z + 1) = z 3 + z.

Como o corpo possui característica 2, vale −a = a para todo a ∈ F24 .

3. Multiplicação:
(z 3 + z 2 + 1)(z 2 + z + 1) = z 5 + z + 1.

Reduzindo o resultado módulo f (z) = z 4 + z + 1, obtém-se

z5 + z + 1 ≡ z2 + 1 (mod z 4 + z + 1).

Portanto,

(z 3 + z 2 + 1)(z 2 + z + 1) = z 2 + 1 em F24 .

22
 4. Inverso multiplicativo:
(z 3 + z 2 + 1)−1 = z 2 ,

pois

(z 3 + z 2 + 1) z 2 ≡ 1 (mod z 4 + z + 1).

3.3.2 Lei de grupo para E/F2m não-supersingular: y 2 + xy = x3 + ax2 + b

1. Identidade. P + ∞ = ∞ + P = P para todo P ∈ E(F2m ).

2. Negativos. Se P = (x, y) ∈ E(F2m ), então (x, y) + (x, x + y) = ∞. O ponto (x, x + y)

é denotado por −P e é chamado de negativo de P ; note que −P é de fato um ponto
em E(F2m ). Além disso, −∞ = ∞.

1. Adição de pontos. Sejam P = (x1 , y1 ) ∈ E(F2m ) e Q = (x2 , y2 ) ∈ E(F2m ), onde

P ̸= ±Q. Então P + Q = (x3 , y3 ), onde

x3 = λ2 + λ + x1 + x2 + a e y3 = λ(x1 + x3 ) + x3 + y1

com λ = (y1 + y2 )/(x1 + x2 ).

2. Dobramento de ponto. Seja P = (x1 , y1 ) ∈ E(F2m ), onde P ̸= −P . Então 2P =

(x3 , y3 ), onde

b
x3 = λ2 + λ + a = x21 + e y3 = x21 + λx3 + x3
x21

com λ = x1 + y1 /x1 .

Exemplo 21. (curva elíptica não-supersingular sobre F24 ) Considere o corpo finito F24
representado pelo polinômio de redução f (z) = z 4 + z + 1. Sejam a = z 3 , b = z 3 + 1, e
considere a curva elíptica não-supersingular

E : y 2 + xy = x3 + z 3 x2 + (z 3 + 1)

definida sobre F24 . Os pontos em E(F24 ) são os seguintes:

23
 ∞ (0011, 1100) (1000, 0001) (1100, 0000)
(0000, 1011) (0011, 1111) (1000, 1001) (1100, 1100)
(0001, 0000) (0101, 0000) (1001, 0110) (1111, 0100)
(0001, 0001) (0101, 0101) (1001, 1111) (1111, 1011)
(0010, 1101) (0111, 1011) (1011, 0010)
(0010, 1111) (0111, 1100) (1011, 1001)
Exemplos de adição em curvas elípticas são (0010, 1111) + (1100, 1100) = (0001, 0001), e
2(0010, 1111) = (1011, 0010).

3.3.3 Lei de grupo para E/F2m supersingular: y 2 + cy = x3 + ax + b

1. Identidade. P + ∞ = ∞ + P = P para todo P ∈ E(F2m ).

2. Negativos. Se P = (x, y) ∈ E(F2m ), então (x, y) + (x, y + c) = ∞. O ponto (x, y + c)

é denotado por −P e é chamado de negativo de P ; note que −P é de fato um ponto
em E(F2m ). Além disso, −∞ = ∞.
1. Adição de pontos. Sejam P = (x1 , y1 ) ∈ E(F2m ) e Q = (x2 , y2 ) ∈ E(F2m ), onde
P ̸= ±Q. Então P + Q = (x3 , y3 ), onde
 2  
y1 + y2 y1 + y2
x3 = + x 1 + x2 e y3 = (x1 + x3 ) + y1 + c.
x1 + x2 x1 + x2

2. Dobramento de ponto. Seja P = (x1 , y1 ) ∈ E(F2m ), onde P ̸= −P . Então 2P =

(x3 , y3 ), onde
2
x21 + a x21 + a
  
x3 = e y3 = (x1 + x3 ) + y1 + c.
c c

3.4 Ordem do Grupo

Seja E uma curva elíptica definida sobre Fq . O número de pontos em E(Fq ), denotado
por #E(Fq ), é chamado de ordem de E sobre Fq .
Teorema 3.1 ((Hasse)). Seja E uma curva elíptica definida sobre Fq . Então:

√ √
q + 1 − 2 q ≤ #E(Fq ) ≤ q + 1 + 2 q

√ √
O intervalo [q + 1 − 2 q, q + 1 + 2 q] é conhecido como o intervalo de Hasse.
Exemplo 22 (Ordens de curvas elípticas sobre F37 ). Seja p = 37. A Tabela lista, para
√ √
cada número inteiro n no intervalo de Hasse [37 + 1 − 2 37, 37 + 1 + 2 37], os coeficientes
(a, b) de uma curva elíptica E : y 2 = x3 + ax + b definida sobre F37 com #E(F37 ) = n.

24
 n (a, b) n (a, b) n (a, b) n (a, b) n (a, b)
26 (5, 0) 31 (2, 8) 36 (1, 0) 41 (1, 16) 46 (1, 11)
27 (0, 9) 32 (3, 6) 37 (0, 5) 42 (1, 9) 47 (3, 15)
28 (0, 6) 33 (1, 13) 38 (1, 5) 43 (2, 9) 48 (0, 1)
29 (1, 12) 34 (1, 18) 39 (0, 3) 44 (1, 7) 49 (0, 2)
30 (2, 2) 35 (1, 8) 40 (1, 2) 45 (2, 14) 50 (2, 0)
Tabela 1: Ordens de curvas elípticas sobre F37

3.5 Estrutura do Grupo

Teorema 3.2. Seja E uma curva elíptica definida sobre Fq . Então E(Fq ) é isomorfo a
Zn1 ⊕ Zn2 onde n1 e n2 são inteiros positivos unicamente determinados tais que n2 divide
tanto n1 quanto q − 1.

Observe que #E(Fq ) = n1 n2 .

1. Se n2 = 1, então E(Fq ) é um grupo cíclico.

2. Se n2 > 1, então diz-se que E(Fq ) tem posto 2.

3. Se n2 for um inteiro pequeno, dizemos que E(Fq ) é quase cíclico.

Como n2 divide tanto n1 quanto q − 1, espera-se que E(Fq ) seja cíclico ou quase cíclico
para a maioria das curvas elípticas E sobre Fq .

Exemplo 23. A curva elíptica E : y 2 = x3 +4x+20 definida sobre F29 tem #E(F29 ) = 37.
Como 37 é primo, E(F29 ) é um grupo cíclico e qualquer ponto em E(F29 ), exceto por ∞,
é um gerador de E(F29 ). O que se segue mostra que os múltiplos do ponto P = (1, 5)
geram todos os pontos em E(F29 ).

0P =∞ 8P = (8, 10) 16P = (0, 22) 24P = (16, 2) 32P = (6, 17)
1P = (1, 5) 9P = (14, 23) 17P = (27, 2) 25P = (19, 16) 33P = (15, 2)
2P = (4, 19) 10P = (13, 23) 18P = (2, 23) 26P = (10, 4) 34P = (20, 26)
3P = (20, 3) 11P = (10, 25) 19P = (2, 6) 27P = (13, 6) 35P = (4, 10)
4P = (15, 27) 12P = (19, 13) 20P = (27, 27) 28P = (14, 6) 36P = (1, 24)
5P = (6, 12) 13P = (16, 27) 21P = (0, 7) 29P = (8, 19)
6P = (17, 19) 14P = (5, 22) 22P = (3, 28) 30P = (24, 7)
7P = (24, 22) 15P = (3, 1) 23P = (5, 7) 31P = (17, 10)

Exemplo 24. Considere F24 como representado pelo polinômio de redução f (z) = z 4 +z+
1. A curva elíptica E : y 2 +xy = x3 +z 3 x2 +(z 3 +1) definida sobre F24 tem #E(F24 ) = 22.
Como 22 não possui fatores repetidos, E(F24 ) é cíclico. O ponto P = (z 3 , 1) = (1000, 0001)
tem ordem 11; seus múltiplos são mostrados abaixo.

25
 0P =∞ 1P = (1000, 0001) 2P = (1001, 1111)
3P = (1100, 0000) 4P = (1111, 1011) 5P = (1011, 0010)
6P = (1011, 1001) 7P = (1111, 0100) 8P = (1100, 1100)
9P = (1001, 0110) 10P = (1000, 1001)

3.6 Representação por Coordenadas Homogêneas

• Um ponto no plano projetivo é representado por uma tripla (X : Y : Z), onde ao
menos uma coordenada deve ser não nula.

• Relação de Equivalência: (X : Y : Z) é o mesmo ponto que (λX : λY : λZ) para

qualquer λ ̸= 0.

• Isso significa que um ponto projetivo representa, na verdade, uma reta que passa
pela origem no espaço tridimensional.

2. A Transição Afim → Projetiva

• Mergulho Afim: Pontos comuns (x, y) são mapeados para o plano projetivo como
(x : y : 1) (onde Z = 1).

• Recuperação de Coordenadas: Para retornar ao plano afim a partir de um ponto

onde Z ̸= 0, calculamos x = X/Z e y = Y /Z.

Exemplo 25. A forma projetiva da equação de Weierstrass

E : y 2 + a1 xy + a3 y = x3 + a2 x2 + a4 x + a6

definida sobre K é

Y 2 Z + a1 XY Z + a3 Y Z 2 = X 3 + a2 X 2 Z + a4 XZ 2 + a6 Z 3 .

O único ponto na linha no infinito que também reside em E é (0 : 1 : 0). Este ponto
projetivo corresponde ao ponto ∞.

26
4 Criptografia com Curvas elípticas
A criptografia de curvas elípticas (Elliptic Curve Cryptography – ECC) foi proposta
de forma independente, em 1985, pelos matemáticos Neal Koblitz, da Universidade de
Washington, e Victor Miller, da IBM. A principal contribuição desses pesquisadores foi
a utilização dos grupos de pontos de curvas elípticas definidas sobre corpos finitos como
alternativa aos grupos multiplicativos tradicionalmente empregados em sistemas de crip-
tografia de chave pública.
A segurança da ECC fundamenta-se no Problema do Logaritmo Discreto em Cur-
vas Elípticas (Elliptic Curve Discrete Logarithm Problem – ECDLP). As curvas elípticas
utilizadas são, em geral, descritas por equações da forma

y 2 = x3 + ax + b,

definidas sobre um corpo apropriado e sujeitas a condições que garantem sua não
singularidade.
Uma das principais vantagens da ECC em relação a sistemas criptográficos clássicos,
como o RSA, é que ela proporciona o mesmo nível de segurança utilizando chaves sig-
nificativamente menores. Por exemplo, uma chave ECC de 256 bits oferece um nível de
segurança comparável ao de uma chave RSA de 3072 bits. Essa característica reduz o
consumo de memória, o custo computacional e o tempo de processamento, tornando a
ECC especialmente adequada para dispositivos com recursos limitados, como smartpho-
nes, cartões inteligentes e dispositivos da Internet das Coisas (IoT).

Problema do Logaritmo Discreto

Esse problema consiste em encontrar o x na equação g x = h dentro de um grupo finito.

No contexto de curvas elípticas, tentamos encontrar o x tal que Q = xP .

É computacionalmente difícil.

4.1 Troca de Chave Diffie-Hellman

1) Alice e Bob concordam com uma curva elíptica E sobre um corpo finito Fq tal que
o problema do logaritmo discreto é difícil em E(Fq ). Eles também concordam com
um ponto P ∈ E(Fq ), tal que, o subgrupo gerado por P tem uma ordem grande
(geralmente, a curva e o ponto são escolhidos de tal forma que a ordem é um primo
grande).

2) Alice escolhe um inteiro secreto a, computa Pa = aP , e envia Pa para Bob.

27
 3) Bob escolhe um inteiro secreto b, computa Pb = bP , e envia Pb para Alice.

4) Alice computa aPb = abP .

5) Bob computa bPa = baP .

6) Alice e Bob usa algum método aceito publicamente para extrair uma chave de abP .

4.2 Massey-Omura
A apresentação do método Massey-Omura e o exemplo desenvolvido nesta seção têm como
referência o trabalho de [8].
Suponhamos que Alice queira enviar uma mensagem para Bob. A mensagem é colo-
cada em um baú. Alice o fecha com seu cadeado e o envia para Bob. Como Bob não
pode remover o cadeado de Alice, ele apenas acrescenta o seu próprio cadeado e devolve
o baú. Alice então remove apenas o seu cadeado, deixando o cadeado de Bob, e envia
novamente o baú. Por fim, Bob remove seu cadeado e abre o baú. Assim, a mensagem
permanece protegida durante todo o processo, sem que Alice e Bob precisem compartilhar
suas chaves.

1) Alice e Bob escolhem uma curva elíptica E sobre um corpo finito Fq , tal que o
problema do logaritmo discreto é difícil em E(Fq ). Defina N = #E(Fq ).

28
 2) Alice representa sua mensagem como um ponto M ∈ E(Fq ).

3) Alice escolhe um inteiro secreto mA com mdc(mA , N ) = 1, computa M1 = mA M , e

envia M1 à Bob.

4) Bob escolhe um inteiro secreto mB com mdc(mB , N ) = 1, computa M2 = mB M1 , e

envia M2 à Alice.

5) Alice computa m−1

A ∈ ZN . Ela computa M3 = mA M2 e envia M3 à Bob.
−1

6) Bob computa m−1

B ∈ ZN . Ele computa M4 = mB M3 . Então, M4 = M é a
−1

mensagem.

Escolha do ponto
Definição de Parâmetros:

• A mensagem m é um número natural no intervalo 0 ≤ m ≤ R.

• Fixamos um número natural t (fator de precisão).

• Escolhemos um corpo finito Fq tal que q > Rt.

Mapeamento para a Curva:

• Para uma mensagem m, testamos valores de x = mt + j, onde j = 1, . . . , t − 1.

• Calculamos f (x) = x3 + Ax + B em Fq .

• Se f (x) for um quadrado em Fq , definimos o ponto Pm = (x,

p
f (x)).

• Caso contrário, incrementamos j e repetimos o processo até encontrar um quadrado.

29
Recuperação da Mensagem:

• Para extrair m a partir do ponto Pm = (x, y), aplica-se a função piso: m = ⌊x/t⌋.

Análise de Falha:

• A probabilidade de o algoritmo não encontrar um ponto após t tentativas é de

aproximadamente 1/2t .

Exemplo 26 (Exemplo retirado da referência 8). Definição da Curva: Consideramos

a curva elíptica E(F751 ) definida por y 2 = x3 − 7x + 2.

Mapeamento do Alfabeto: Identificamos as letras do alfabeto com o conjunto

{10, 11, . . . , 35}, respectivamente.

Mensagem Original: O usuário A deseja enviar a mensagem m = APROVADO-

NOTCC para o usuário B.

Parâmetros de Codificação:

• Como 0 ≤ m ≤ 35 = R, escolhemos t = 20.

• Assim, q = 751 ≥ Rt = 700.

Codificação da Letra A:

• Temos A = 10, logo, 10 · 20 = 200 = x.

• Calculamos f (x) = 2003 − 7(200) + 2 ≡ 452 (mod 751).

• Como a equação y 2 ≡ 452 (mod 751) não tem solução, tomamos x + 1 = 201, onde
f (201) ≡ 135 (mod 751) (também sem solução).

• Tomamos x + 2 = 202, resultando em f (202) ≡ 273 (mod 751).

• A equação y 2 ≡ 273 (mod 751) tem soluções y = 32 ou y = 719. Escolhemos

y = 32, portanto, PA = (202, 32).

Pontos das Demais Letras:

• PP = (501, 53), PR = (541, 104), PO = (485, 263), PV = (621, 324), PD = (261, 110),
PN = (460, 247), PT = (581, 283), PC = (241, 372).

Criptografia pelo Usuário A:

30
 • O usuário A escolhe o inteiro secreto mA = 5, com mdc(5, #E(F751 ) = 764) = 1.

• Computa os pontos: mA PA = 5(202, 32) = (553, 147), mA PP = (535, 214), mA PR =

(232, 634), mA PO = (49, 553), mA PV = (98, 16), mA PD = (627, 163), mA PN =
(529, 475), mA PT = (128, 233), mA PC = (398, 743).

• A envia a Mensagem Criptografada (M.C.) para B:

M.C. = {(553, 147), (535, 214), (232, 634), (49, 553), (98, 16),
(553, 147), (627, 163), (49, 553), (529, 475), (49, 553),
(128, 233), (398, 743), (398, 743)}

Ação do Usuário B:

• O usuário B multiplica cada ponto de (M.C.) por seu inteiro secreto mB = 3

(mdc(3, 764) = 1) e envia para A:

{(263, 658), (627, 163), (50, 509), (111, 745), (691, 589),
(263, 658), (569, 88), (111, 745), (238, 456), (111, 745),
(331, 64), (55, 696), (55, 696)}

Finalização pelo Usuário A:

• O usuário A multiplica cada ponto por m−1

A = 153 e envia para B:

{(324, 143), (261, 110), (10, 593), (237, 187), (140, 362),
(324, 143), (714, 725), (237, 187), (471, 374), (237, 187),
(173, 109), (353, 428), (353, 428)}

Recuperação pelo Usuário B:

• O usuário B recupera a mensagem original multiplicando os pontos por m−1

B = 255.

• A decodificação final é feita calculando a parte inteira de x/t. Exemplo: para

PA = (202, 32), temos [202/20] = 10 = A.

4.3 O Problema do Logaritmo Discreto

A apresentação do método e o exemplo desenvolvido nesta seção têm como referência o
trabalho de [9].
A segurança do esquema ElGamal e de outros protocolos apresentados reside na difi-
culdade do Problema do Logaritmo Discreto em Curvas Elípticas (ECDLP).

31
 Esse problema consiste em encontrar o x na equação g x = h dentro de um grupo finito.
No contexto de curvas elípticas, tentamos encontrar o x tal que Q = xP .
É computacionalmente difícil.
Passo 1: Preparação de Bob no ECDLP Alice deseja enviar uma mensagem m
para Bob.

Algoritmo.

1. Bob escolhe, e mantém em segredo, um inteiro b ∈ N∗ .

2. Ele envia à Alice o valor Q = bP .

3. P é um ponto da curva elíptica conhecido publicamente.

Passo 2: Criptografia por Alice

2. Alice escolhe um inteiro a ∈ N∗ (também o guarda para si).

3. Ela computa os valores do criptograma:

• M1 = aP
• M2 = m + aQ

Passo 3: Decifração por Bob

3. Para decifrar a mensagem m, Bob utiliza sua chave privada b.

4. Ele realiza o seguinte cálculo:

M2 − bM1 = m + abP − baP = m

Resumo das Notações Para a correta execução, as partes devem garantir:

• Segredos (Privados): Inteiros a (Alice) e b (Bob) pertencentes a N∗ .

• Público: Ponto P e Chave Pública Q = bP .

• Criptograma: O par (M1 , M2 ) enviado via canal inseguro.

Passo 1: Mapeamento Numérico do Alfabeto Para iniciar a cifragem, cada letra

do alfabeto é associada a um valor numérico entre 01 e 26.

• A = 01, B = 02, C = 03 . . . Z = 26.

• Este mapeamento permite que o texto seja tratado como dado matemático para as
operações na curva.

32
Exemplo 27. Para a palavra LNCC, primeiro identificamos os números de cada letra
antes de agrupá-las em blocos.
Passo 2: Agrupamento e Concatenação A mensagem é dividida em blocos de
duas letras (neste exemplo, LN e CC).

• Os números associados às letras de cada bloco são concatenados para formar um

único valor escalar.

• Exemplo com o bloco AB:

– A = 01 e B = 02.
– Valor concatenado: 0102 (ou 102).

Passo 3: Mapeamento em Pontos da Curva O valor concatenado é multiplicado por

um ponto público P da curva elíptica.

• Configuração: Curva y 2 = x3 + 373x + 402 sobre F3697 .

• Ponto Base: P = (551, 1946).

• Cálculo para AB:

102 · P = 102(551, 1946) = (3108, 1065)

Resultado Final O par de letras AB é mapeado para o ponto (3108, 1065) na curva
elíptica.
Passo 1: Configuração e Chave Pública de Bob Bob inicia o processo definindo
sua chave privada e os parâmetros da curva y 2 = x3 + 373x + 402 sobre F3697 :

• Chave Privada: Bob escolhe b = 919.

• Ponto Base: P = (551, 1946).

• Chave Pública (Q): Bob calcula Q = bP = 919(551, 1946) = (301, 3454).

Segurança É computacionalmente inviável descobrir b a partir de Q e P (Problema do

Logaritmo Discreto).
Passo 2: Alice Criptografa o Bloco “LN” Alice deseja enviar a string LN, previ-
amente mapeada no ponto m = (2309, 2502):

1. Alice escolhe um inteiro aleatório a = 815.

33
 2. Calcula a primeira parte do criptograma (M1 ):

M1 = 815P = 815(551, 1946) = (958, 14)

3. Calcula o segredo compartilhado para mascarar a mensagem:

aQ = 815(301, 3454) = (837, 2461)

Passo 2: Finalizando o Criptograma de “LN” Para ocultar o ponto m, Alice o soma

ao ponto aQ:

• Segunda parte (M2 ):

M2 = m + aQ = (2309, 2502) + (837, 2461) = (1518, 14)

• Transmissão: Alice envia a Bob o par cifrado:

(M1 , M2 ) = ((958, 14), (1518, 14))

Passo 3: Bob Recupera a Mensagem “LN” Bob recebe (M1 , M2 ) e usa sua chave
privada b = 919 para calcular m = M2 − bM1 :

1. Bob primeiro calcula bM1 :

919(958, 14) = (837, 2461)

2. Subtrai este valor de M2 :

m = (1518, 14) − (837, 2461) = (2309, 2502)

Resultado O ponto (2309, 2502) corresponde exatamente à string LN.

Passo 4: Processamento do Bloco “CC” Para as letras CC, o procedimento é
análogo. O bloco é mapeado no ponto m = (3023, 762):

• Alice utiliza o mesmo segredo compartilhado aQ = (837, 2461).

• Alice calcula o novo M2 :

M2 = (3023, 762) + (837, 2461) = (3084, 2426)

• Alice envia M2 = (3084, 2426) para Bob.

34
Passo 5: Conclusão do Processo Bob recupera a string final repetindo a subtração:

• Cálculo de descriptografia:

m = M2 − bM1 = (3084, 2426) − (837, 2461)

m = (3084, 2426) + (837, −2461) = (3023, 762)

Encerramento Bob recupera a string CC e a mensagem completa LNCC é finalizada

com sucesso.

Exemplo 28. Este exemplo foi extraído da referência [10].

Consideramos a curva elíptica definida sobre o corpo finito F29 :

E : y 2 = x3 + 4x + 20

A curva possui ordem 37 e utilizamos como ponto gerador:

G = (24, 7)

No algoritmo ElGamal, o destinatário escolhe inicialmente uma chave privada b. Em

nossa execução foi escolhido:

b = 28

A chave pública é obtida multiplicando a chave privada pelo ponto gerador:

Q = bG

Logo,

Q = 28(24, 7) = (10, 4)

Portanto:

• Chave privada: b = 28

• Chave pública: Q = (10, 4)

35
 Letra Número Ponto Letra Número Ponto
A 22 (17, 10) N 25 (13, 23)
B 34 (0, 7) O 30 (19, 13)
C 24 (27, 2) P 33 (14, 6)
D 4 (14, 23) Q 27 (15, 2)
E 23 (16, 2) R 21 (1, 5)
F 1 (24, 7) S 37 Neutro
G 15 (17, 19) T 11 (20, 26)
H 14 (16, 27) U 35 (5, 22)
I 20 (8, 10) V 8 (2, 23)
J 18 (3, 28) W 26 (20, 3)
K 17 (8, 19) X 6 (6, 17)
L 29 (2, 6) Y 28 (10, 4)
M 12 (13, 6) Z 7 (19, 16)

Pré-codificação da Mensagem
Antes da criptografia, cada letra da mensagem é associada a um ponto da curva elíptica
por meio de uma tabela de pré-codificação.
A mensagem utilizada foi:

CODIGO

Cada letra é substituída pelo ponto correspondente da tabela:

Letra Ponto da Curva

C (27, 2)
O (19, 13)
D (14, 23)
I (8, 10)
G (17, 19)
O (19, 13)

Assim, a mensagem passa a ser representada por uma lista de pontos da curva elíptica.
Criptografia no ElGamal
Para criptografar a mensagem, escolhe-se um valor aleatório a e calcula-se:

M1 = aG

nesse exemplo, obteve-se:

M1 = (1, 5)

Para cada ponto P da mensagem pré-codificada, calcula-se:

M2 = P + aQ

onde:

• P é o ponto correspondente à letra;

36
 • Q é a chave pública;

• a é o valor aleatório escolhido.

O texto criptografado é enviado como o par: (M1 , M2 ) Descriptografia no ElGamal

Tabela M2
C (8, 10)
O (20, 3)
D Elemento neutro
I (1, 24)
G (20, 26)
O (20, 3)

O destinatário utiliza sua chave privada b para recuperar cada ponto original da men-
sagem.
A recuperação é feita por meio da operação:

P = M2 − bM1

onde:

• M1 e M2 são os valores recebidos;

• b é a chave privada.

Após recuperar os pontos da curva, utiliza-se novamente a tabela de pré-codificação para

transformar cada ponto em letra. Dessa forma, obtemos novamente a mensagem original:

CODIGO

4.4 O Criptossistema Menezes-Vanstone

A apresentação do método e o exemplo desenvolvido nesta seção têm como referência o
trabalho de [9].
Diferente de outros sistemas, no Menezes-Vanstone a mensagem não precisa ser um
ponto da curva.

• Texto Legível (m): Um par ordenado m = (x1 , x2 ), onde x1 , x2 ∈ F∗p .

• Texto Ilegível (r): Uma tripla ordenada r = (y0 , y1 , y2 ).

– y0 é um ponto da curva elíptica.

– y1 , y2 ∈ F∗p são componentes numéricos calculados.

37
Algoritmo: Criptografando a Mensagem Para cifrar m = (x1 , x2 ), Bob realiza os
seguintes passos:

1. Escolhe um inteiro secreto k ∈ F∗p e calcula o ponto y0 = kP .

2. Computa o segredo compartilhado: (c1 , c2 ) = kQ.

3. Mascara a mensagem através de multiplicações modulares:

• y1 = c1 x1 (mod p).
• y2 = c2 x2 (mod p).

4. Envia a tripla r = (y0 , y1 , y2 ) para Alice.

Algoritmo: Descriptografando a Mensagem Ao receber r = (y0 , y1 , y2 ), Alice usa

sua chave privada s para recuperar m:

1. Alice recupera o segredo compartilhado calculando:

sy0 = s(kP ) = k(sP ) = kQ = (c1 , c2 )

2. Utiliza o inverso modular dos componentes para isolar x1 e x2 :

• x1 = y1 (c1 )−1 (mod p).

• x2 = y2 (c2 )−1 (mod p).

3. A mensagem original m = (x1 , x2 ) é recuperada.

Exemplo 29. Exemplo Prático: Mensagem “MCT” Bob deseja enviar “MCT” para Alice
usando a curva Ω : y 2 = x3 + 67110x + 262147 sobre F2097421 .

• Codificação ASCII: M=77, C=67, T=84.

• Formação do Par: Separamos em dois blocos, resultando em m = (7767, 84).

• Parâmetros Públicos:

– P = (1355793, 621792).
– Q = sP = (949594, 812871), com chave privada s = 78771.

Exemplo Prático: Cifragem de Bob

1. Bob escolhe k = 23358 e computa y0 :

y0 = 23358 · P = (1390038, 1344654)

38
 2. Calcula o segredo compartilhado kQ:

kQ = (647014, 449701) = (c1 , c2 )

3. Calcula os componentes cifrados:

• y1 = 647014 · 7767 ≡ 2034443 (mod p).

• y2 = 449701 · 84 ≡ 21306 (mod p).

4. Bob envia r = (y0 , 2034443, 21306) para Alice.

Exemplo Prático: Decifração de Alice

1. Alice calcula s · y0 :

78771 · (1390038, 1344654) = (647014, 449701) = (c1 , c2 )

2. Recupera os valores originais usando inversos modulares:

• x1 = 2034443(647014)−1 ≡ 7767 (mod p).

• x2 = 21306(449701)−1 ≡ 84 (mod p).

Conclusão Ao final, Alice obtém m = (7767, 84), que convertido de volta para ASCII
resulta na mensagem original MCT.

4.5 Ataques
Nesta seção serão apresentados os principais tipos de ataques aplicáveis à Criptografia de
Curvas Elípticas (ECC). Serão discutidos os ataques matemáticos, descrevendo apenas a
ideia geral de seu funcionamento, incluindo força bruta, Baby-Step Giant-Step, Rho de
Pollard e Pohlig–Hellman e tem como referência o livro [7].

Força Bruta

A abordagem de força bruta consiste em testar exaustivamente todas as possíveis chaves

privadas até encontrar a correta. Sua complexidade é O(n), em que n é a ordem do corpo
Fq . Isso significa que seu custo cresce linearmente com a ordem da curva e a chave privada.
Embora ineficiente para curvas grandes, serve como referência para avaliar métodos mais
avançados.

39
Big-Step Giant-Step

O método Big-Step Giant-Step otimiza a busca ao dividir o espaço de soluções em duas

fases: uma pré-computação de valores (passos pequenos) armazenados em uma tabela e
uma busca com saltos maiores (passos grandes). Sua complexidade é proporcional à raiz
quadrada da ordem do grupo dos pontos da curva. Apesar de reduzir significativamente
√
as operações em comparação à força bruta ( reduz operações para O( n)), exige mais
memória para armazenar os valores pré-calculados.

Rho de Pollard

O método ρ de Pollard é um algoritmo probabilístico usado para atacar o problema do

logaritmo discreto em curvas elípticas (ECDLP). Ele gera sequências pseudoaleatórias de
pontos da curva até ocorrer uma colisão, isto é, a repetição de um ponto. Como o grupo
é finito, essas colisões permitem determinar o logaritmo discreto. O número médio de
√
iterações necessárias é aproximadamente 1,2533 n, o que dá ao método complexidade
√
O( n). O nome do algoritmo vem do formato do percurso gerado, semelhante à letra
grega ρ.

Pohlig-Hellman

Já o algoritmo de Pohlig-Hellman utiliza a fatoração da ordem do grupo da curva para

dividir o problema em subproblemas menores, resolvendo cada um separadamente e com-
binando as soluções com o Teorema Chinês do Resto. Sua complexidade depende do
somatório dos fatores primos da ordem do grupo, sendo especialmente eficiente quando
esses fatores são pequenos. O desempenho varia pouco com a chave, pois depende prin-
cipalmente da estrutura do grupo.

Teorema 4.1 (Teorema Chinês do Resto). Se, para todo i ∈ {1, 2, . . . , k},

mdc(ai , mi ) = 1,

então, para quaisquer b1 , . . . , bk , o sistema




 a1 x ≡ b1 (mod m1 )


a2 x ≡ b2 (mod m2 )


..


 .


a x ≡ b (mod m )

k k k

admite solução
x0 = c1 n1 ℓ1 + c2 n2 ℓ2 + · · · + ck nk ℓk ,

40
onde ci é solução de ai x ≡ bi (mod mi ), e ni x ≡ 1 (mod mi ). tem solução li .

Além disso, se y for outra solução, então y ≡ x0 (mod M ). E reciprocamente, se

y ≡ x0 (mod ()M ), então y também é solução do sistema. M = m1 .m2 . . . . .mk .

Introdução ao Algoritmo de Pohlig-Hellman

• Objetivo: Resolver Q = lP onde a ordem n de P é composta.

• Estratégia: Reduzir um ECDLP grande em vários ECDLPs menores em subgrupos.

• Fatoração da Ordem: Seja a fatoração de n:

n = pe11 pe22 . . . perr

• O algoritmo calcula li ≡ l (mod pei i ) para cada i e reconstrói l usando o Teorema

Chinês dos Restos (CRT).

Cálculo de li (mod pe ) Para cada fator pe , escrevemos li na base p:

li = z0 + z1 p + z2 p2 + · · · + ze−1 pe−1

Passo a Passo para os dígitos zj :

1. Dígito z0 : Define-se P0 = np P e Q0 = np Q. Resolve-se Q0 = z0 P0 no subgrupo de

ordem p.

2. Dígito z1 : Define-se Q1 = n
p2
(Q − z0 P ). Resolve-se Q1 = z1 P0 .

3. Generalização (zt ):

t−1
!
n X
Qt = Q− zj pj P = zt P0
pt+1 j=0

Exemplo 30 (Algoritmo de Pohlig–Hellman para resolver o ECDLP). Considere a curva

elíptica E definida sobre F7919 pela equação

E : y 2 = x3 + 1001x + 75.

Seja
P = (4023, 6036) ∈ E(F7919 ).

A ordem de P é
n = 7889 = 73 · 23.

41
 Seja
Q = (4135, 3169) ∈ ⟨P ⟩.

Desejamos determinar
l = logP Q.

1. Primeiro determinamos
l1 ≡ l (mod 73 ).

Escrevemos
l1 = z0 + z1 · 7 + z2 · 72

e calculamos
P0 = 72 · 23 P = (7801, 2071),

Q0 = 72 · 23 Q = (7801, 2071).

Como Q0 = P0 , concluímos que

z0 = 1.

Em seguida, calculamos

Q1 = 7 · 23 (Q − P ) = (7285, 14)

e verificamos que
Q1 = 3P0 .

Logo,
z1 = 3.

Finalmente, calculamos

Q2 = 23 (Q − P − 3 · 7P ) = (7285, 7905)

e verificamos que
Q2 = 4P0 .

Assim,
z2 = 4.

Portanto,
l1 = 1 + 3 · 7 + 4 · 72 = 218.

2. Em seguida, determinamos
l2 ≡ l (mod 23).

42
 Calculamos
P0 = 73 P = (7190, 7003),

Q0 = 73 Q = (2599, 759),

e verificamos que
Q0 = 10P0 .

Logo,
l2 = 10.

3. Por fim, resolvemos o sistema de congruências

l ≡ 218 (mod 73 ),

l ≡ 10 (mod 23).

Aplicando o Teorema Chinês do Resto, obtemos

l = 4334.

Portanto,
logP Q = 4334.

Os próximos exemplos ilustra uma comparação entre os algoritmos de ataque ao ECC

e tem como referência [11].

Exemplo 31. Foram utilizados a curva elíptica

E : y 2 = x3 + 1001x + 75,

definida sobre o corpo finito F7919 , juntamente com o ponto gerador

P = (4023, 6036).

Os valores são a quantidade de somas de pontos realizadas.

43
 CHAVE Força Bruta Pohlig-Hellman BSGS
1000 999 1055 189
2000 1999 1037 200
3000 2999 996 211
4000 3999 978 222
5000 4999 937 234
6000 5999 919 245
7000 6999 878 256

Exemplo 32. Foram utilizados a curva elíptica

E : y 2 = x3 + 5x − 3,

definida sobre o corpo finito F839 , juntamente com o ponto gerador

P = (154, 5).

Os valores são a quantidade de somas de pontos realizadas.

CHAVE Força Bruta Pohlig-Hellman BSGS
100 99 560 63
200 199 588 66
300 299 788 70
400 399 643 73
500 499 843 76
600 599 698 80
700 699 553 63
800 799 753 86

44
Referências
[1] VAINSENCHER, I. Introdução às Curvas Algébricas Planas. Coleção Matemática
Universitária. 2. ed. Rio de Janeiro: IMPA, 2005.

[2] GARCIA, A.; LEQUAIN, Y. Elementos de Álgebra. 5. ed. Rio de Janeiro: IMPA,
2008.

[3] SALEHYAN, P. Curvas Algébricas: uma breve introdução. Minicurso da VII Semana
da Matemática da FEIS–UNESP, Ilha Solteira, 2008.

[4] OLIVEIRA, T. C. Área da superfície e volume da Igreja de São Francisco de Assis.

Monografia (Graduação) – Universidade Federal de Minas Gerais, Belo Horizonte,
2017.

[5] GONÇALVES, T. S. Uma Introdução à Geometria Projetiva para o Ensino Funda-

mental. Dissertação (Mestrado) – Universidade Federal do Rio Grande, Rio Grande,
2013.

[6] SONG, Jimmy. Programming Bitcoin: Learn How to Program Bitcoin from Scratch.
Sebastopol: O’Reilly Media, 2019.

[7] HANKERSON, Darrel; MENEZES, Alfred J.; VANSTONE, Scott. Guide to Elliptic
Curve Cryptography. New York: Springer, 2004.

[8] MEIRELES, Tiago Aprigio Bezerra. Curvas Elípticas e Criptografia. 2023. Trabalho
de Conclusão de Curso (Bacharelado em Matemática) – Faculdade de Matemática,
Universidade Federal de Uberlândia, Uberlândia, 2023.

[9] LARA, P. C. S.; OLIVEIRA, F. B. Curvas Elípticas: Aplicação em Criptografia

Assimétrica. Petrópolis, RJ: LNCC, [s.d.].

[10] ANDRADE, H. D. A. Implementação do Algoritmo ElGamal utilizando Curvas Elíp-

ticas e Curvas Hiperelípticas no SageMath. Trabalho de Conclusão de Curso (Ba-
charelado em Ciência da Computação) – PUC Minas, Belo Horizonte, MG, Brasil,
2025.

[11] ANDRADE, H. D. A.; OLIVEIRA, N. M. G.; DANTAS, D. A. M. Um Es-

tudo Sobre Algoritmos de Ataque ao ECC. Proceeding Series of the Brazi-
lian Society of Computational and Applied Mathematics, v. 12, n. 1, 2026. DOI:
10.5540/03.2026.012.01.05094.

45