Um Estudo Sobre Algoritmos de Ataque ao ECC

Resumen

Com o avanço da tecnologia, muitos métodos criptográficos antigos, como a Cifra de César, tornaram-se vulneráveis. Já a criptografia com curvas elípticas (ECC) continua segura dentro de limites computacionais viáveis. Devido ao seu baixo custo computacional, a ECC é eficiente para dispositivos com recursos limitados, sendo usada em smartcards, IoT e criptomoedas. A segurança da ECC baseia-se na dificuldade de resolver o problema do logaritmo discreto (PLD) em curvas elípticas. Esse problema surge na estrutura matemática dessas curvas, que são definidas pela equação de Weierstrass y² = x³ + ax + b sobre um corpo finito F_q. Os pontos da curva, com a operação de soma, formam um grupo em que o PLD é formulado. Para curvas bem escolhidas, resolver o PLD é considerado computacionalmente inviável. A complexidade computacional dos algoritmos utilizados para atacar o PLD é denotada por O(f(t)), em que f é uma função que descreve o crescimento do tempo de execução do algoritmo em função do parâmetro t. Nesse trabalho analisamos o custo computacional de alguns desses algoritmos. Em nossa análise, calculamos a complexidade baseada na quantidade de multiplicações de pontos, pois essa operação é fundamental para os cálculos em criptografia de curvas elípticas e influencia diretamente o custo computacional dos ataques. Usamos [3] como base para esses cálculos. Implementamos operações fundamentais em curvas elípticas utilizando a linguagem de programação Python. Além disso, desenvolvemos e analisamos a implementação dos algoritmos de ataque ao PLD: o método de Pohlig-Hellman, o Big-Step Giant-Step e a abordagem de força bruta. [...]