Todo sistema criptográfico é baseado em um problema matemático
que é intratável computacionalmente. Sistemas criptográficos em curvas
elípticas são baseados na dificuldade do problema do logaritmo discreto em
curvas elípticas (ECDLP - Elliptic Curve Discrete Logarithm Problem).
Nas seções anteriores foi definida a operação de adição sobre
elementos de um grupo de curvas elípticas. Considerando o caso em que
um ponto é somado a ele mesmo, isto é, a partir de um ponto P
pertencente à curva elíptica, o ponto 2P é obtido dobrando o ponto P. Neste
momento, o ponto P pode ser adicionado ao ponto 2P, resultando o ponto
3P. A determinação de um ponto nP é conhecida como Multiplicação por
Escalar do ponto. O problema do logaritmo discreto é baseado na
intratabilidade do produto da multiplicação por escalar.
Apesar da operação utilizada ser uma seqüência de somas, a
operação de multiplicação por escalar também é representada por uma
notação de multiplicação (nP = PxPxPx...xP n vezes), explicando a utilização
da palavra logaritmo para definir o problema.
O problema do logaritmo discreto é definido da seguinte maneira: dados os
elementos R e Q pertencentes ao grupo, e um primo P, achar um número k
tal que R = Qk mod P. O número k é chamado de logaritmo discreto de R
na base Q.