Logaritmo discreto

Na matemática, para determinados números reais ${\displaystyle a}$ e ${\displaystyle b}$, o logaritmo ${\displaystyle \log _{b}(a)}$ é um número ${\displaystyle x}$ tal que ${\displaystyle b^{x}=a}$. O logaritmo discreto generaliza este conceito para um grupo cíclico. Um exemplo simples é o grupo de inteiros módulo um número primo (como 5) sob a multiplicação modular de elementos não nulos.

Por exemplo, considere ${\displaystyle b=2}$ no grupo multiplicativo módulo 5, cujos elementos são ${\displaystyle \{1,2,3,4\}}$. Então: $${\displaystyle 2^{1}=2,\quad 2^{2}=4,\quad 2^{3}=8\equiv 3{\pmod {5}},\quad 2^{4}=16\equiv 1{\pmod {5}}.}$$ As potências de 2 módulo 5 percorrem todos os elementos não nulos, portanto, os logaritmos discretos existem e são dados por: $${\displaystyle \log _{2}1=4,\quad \log _{2}2=1,\quad \log _{2}3=3,\quad \log _{2}4=2.}$$

Mais genericamente, em qualquer grupo ${\displaystyle G}$, as potências ${\displaystyle b^{k}}$ podem ser definidas para todos os inteiros ${\displaystyle k}$, e o logaritmo discreto ${\displaystyle \log _{b}(a)}$ é um inteiro ${\displaystyle k}$ tal que ${\displaystyle b^{k}=a}$. Na aritmética modular em relação a um inteiro ${\displaystyle m}$, o termo mais comumente usado é índice: Pode-se escrever ${\displaystyle k=\mathbb {ind} _{b}a{\pmod {m}}}$ (lê-se "o índice de ${\displaystyle a}$ na base ${\displaystyle b}$ módulo ${\displaystyle m}$") para ${\displaystyle b^{k}\equiv a{\pmod {m}}}$ se ${\displaystyle b}$ for uma raiz primitiva de ${\displaystyle m}$ e ${\displaystyle \gcd(a,m)=1}$.

Os logaritmos discretos são rapidamente computáveis em alguns casos especiais. No entanto, não se conhece nenhum método eficiente para calculá-los em geral. Na criptografia, a complexidade computacional do problema do logaritmo discreto, juntamente com sua aplicação, foi proposta pela primeira vez no Problema de Diffie–Hellman. Vários algoritmos importantes em criptografia de chave pública, como o ElGamal, baseiam sua segurança na suposição de dificuldade computacional de que o problema do logaritmo discreto (PLD) sobre grupos cuidadosamente escolhidos não tem solução eficiente,^[1] e em um grupo geral de caixa preta carece totalmente de uma solução subexponencial.

Seja ${\displaystyle G}$ um grupo qualquer. Denote sua operação de grupo por multiplicação e seu elemento neutro por ${\displaystyle 1}$. Seja ${\displaystyle b}$ qualquer elemento de ${\displaystyle G}$. Para qualquer inteiro positivo ${\displaystyle k}$, a expressão ${\displaystyle b^{k}}$ denota o produto de ${\displaystyle b}$ com ele mesmo ${\displaystyle k}$ vezes:^[2]

${\displaystyle b^{k}=\underbrace {b\cdot b\cdot \ldots \cdot b} _{k\;{\text{fatores}}}.}$

De forma semelhante, seja ${\displaystyle b^{-k}}$ o produto de ${\displaystyle b^{-1}}$ com ele mesmo ${\displaystyle k}$ vezes. Para ${\displaystyle k=0}$, a ${\displaystyle k}$-ésima potência é a identidade: ${\displaystyle b^{0}=1}$.

Seja ${\displaystyle a}$ também um elemento de ${\displaystyle G}$. Um inteiro ${\displaystyle k}$ que resolve a equação ${\displaystyle b^{k}=a}$ é chamado de logaritmo discreto (ou simplesmente logaritmo, neste contexto) de ${\displaystyle a}$ na base ${\displaystyle b}$. Escreve-se ${\displaystyle k=\log _{b}a}$.

As potências obedecem à identidade algébrica comum ${\displaystyle b^{k+l}=b^{k}\cdot b^{l}}$.^[2] Em outras palavras, a função

${\displaystyle f\colon \mathbf {Z} \to G}$

definida por ${\displaystyle f(k)=b^{k}}$ é um homomorfismo de grupos do grupo dos números inteiros ${\displaystyle \mathbf {Z} }$ sob a adição sobre o subgrupo ${\displaystyle H}$ de ${\displaystyle G}$ gerado por ${\displaystyle b}$. Para todo ${\displaystyle a}$ em ${\displaystyle H}$, ${\displaystyle \log _{b}a}$ existe. Inversamente, ${\displaystyle \log _{b}a}$ não existe para valores de ${\displaystyle a}$ que não estão em ${\displaystyle H}$.

Se ${\displaystyle H}$ for infinito, então ${\displaystyle \log _{b}a}$ também é único, e o logaritmo discreto equivale a um isomorfismo de grupos

${\displaystyle \log _{b}\colon H\to \mathbf {Z} .}$

Por outro lado, se ${\displaystyle H}$ for finito de ordem ${\displaystyle n}$, então ${\displaystyle \log _{b}a}$ é único apenas até a congruência módulo ${\displaystyle n}$, e o logaritmo discreto equivale a um isomorfismo de grupo

${\displaystyle \log _{b}\colon H\to \mathbf {Z} _{n},}$

onde ${\displaystyle \mathbf {Z} _{n}}$ denota o grupo aditivo de inteiros módulo ${\displaystyle n}$.

A fórmula familiar de mudança de base para logaritmos comuns permanece válida: Se ${\displaystyle c}$ for outro gerador de ${\displaystyle H}$, então

${\displaystyle \log _{c}a=\log _{c}b\cdot \log _{b}a.}$

O problema do logaritmo discreto é considerado computacionalmente intratável. Para um computador clássico (ou seja, não quântico), nenhum algoritmo eficiente (de tempo polinomial) é conhecido ainda para o cálculo de logaritmos discretos em geral.

Um algoritmo geral para computar ${\displaystyle \log _{b}a}$ em grupos finitos ${\displaystyle G}$ consiste em elevar ${\displaystyle b}$ a potências ${\displaystyle k}$ cada vez maiores até que o ${\displaystyle a}$ desejado seja encontrado. Esse algoritmo às vezes é chamado de multiplicação por tentativa. Requer um tempo de execução linear no tamanho do grupo ${\displaystyle G}$ e, portanto, exponencial no número de dígitos do tamanho do grupo. Assim, trata-se de um algoritmo de tempo exponencial, prático apenas para pequenos grupos ${\displaystyle G}$.

Algoritmos mais sofisticados existem, geralmente inspirados em algoritmos semelhantes para a fatoração de inteiros. Esses algoritmos são executados mais rapidamente do que o algoritmo ingênuo, alguns deles em tempo proporcional à raiz quadrada do tamanho do grupo e, portanto, exponencial na metade do número de dígitos do tamanho do grupo. Entretanto, nenhum deles é executado em tempo polinomial (no número de dígitos do tamanho do grupo).

• Baby-step giant-step (Passo-bebê passo-gigante)
• Crivo do corpo de funções
• Algoritmo de cálculo de índice
• Crivo do corpo de números geral
• Algoritmo de Pohlig–Hellman
• Algoritmo rho de Pollard para logaritmos
• Algoritmo do canguru de Pollard (também conhecido como algoritmo lambda de Pollard)

Existe um algoritmo quântico eficiente criado por Peter Shor.^[3]

Também existem algoritmos clássicos eficientes em certos casos especiais. Por exemplo, no grupo dos números inteiros módulo ${\displaystyle p}$ sob adição, a potência ${\displaystyle b^{k}}$ torna-se um produto ${\displaystyle b\cdot k}$, e a igualdade significa congruência módulo ${\displaystyle p}$ nos números inteiros. O algoritmo de Euclides estendido encontra ${\displaystyle k}$ rapidamente.

No Diffie–Hellman, é usado um grupo cíclico módulo um primo ${\displaystyle p}$, permitindo um cálculo eficiente do logaritmo discreto com Pohlig–Hellman se a ordem do grupo (sendo ${\displaystyle p-1}$) for suficientemente suave, isto é, não possuir grandes fatores primos.

Embora o cálculo de logaritmos discretos e a fatoração de inteiros sejam problemas distintos, eles compartilham algumas propriedades:

• ambos são casos especiais do problema do subgrupo oculto para grupos abelianos finitos;
• ambos os problemas parecem ser difíceis (não há algoritmos eficientes conhecidos para computadores não quânticos);
• para ambos os problemas, algoritmos eficientes em computadores quânticos são conhecidos;
• os algoritmos de um problema são frequentemente adaptados para o outro, e;
• a dificuldade de ambos os problemas tem sido usada para construir vários sistemas criptográficos.

Existem grupos nos quais calcular logaritmos discretos é aparentemente difícil. Em alguns casos (por exemplo, subgrupos de ordem prima grande de grupos ${\displaystyle \mathbf {Z} _{p}^{\times }}$), não apenas não há um algoritmo eficiente conhecido para o pior caso, como a complexidade do caso médio pode ser demonstrada como sendo quase tão difícil quanto o pior caso usando autorredutibilidade aleatória.^[4]

Ao mesmo tempo, o problema inverso da exponenciação discreta não é difícil (ele pode ser computado eficientemente usando a exponenciação por quadratura, por exemplo). Essa assimetria é análoga àquela existente entre a fatoração de inteiros e a multiplicação de inteiros. Ambas as assimetrias (e outras possíveis funções de via única) têm sido exploradas na construção de sistemas criptográficos.

Escolhas populares para o grupo ${\displaystyle G}$ na criptografia de logaritmo discreto (CLD) são os grupos cíclicos ${\displaystyle \mathbf {Z} _{p}^{\times }}$ (por exemplo, o sistema ElGamal, a Troca de Chaves Diffie-Hellman e o Algoritmo de Assinatura Digital) e subgrupos cíclicos de curvas elípticas sobre corpos finitos (veja Criptografia de curvas elípticas).

Embora não exista nenhum algoritmo publicamente conhecido para resolver o problema do logaritmo discreto em geral, as três primeiras etapas do algoritmo do crivo do corpo de números dependem apenas do grupo ${\displaystyle G}$, e não dos elementos específicos de ${\displaystyle G}$ cujo ${\displaystyle \log }$ finito é desejado. Ao pré-computar essas três etapas para um grupo específico, é necessário realizar apenas a última etapa, que é muito menos custosa computacionalmente do que as três primeiras, para se obter um logaritmo específico naquele grupo.^[5]

Acontece que grande parte do tráfego da internet usa um punhado de grupos que têm ordem de 1024 bits ou menos, por exemplo, grupos cíclicos com ordem dos primos Oakley especificados na RFC 2409.^[6] O ataque Logjam usou essa vulnerabilidade para comprometer uma variedade de serviços de internet que permitiam o uso de grupos cuja ordem era um número primo de 512 bits, grau conhecido como de exportação.^[5]

Os autores do ataque Logjam estimam que a pré-computação, muito mais difícil, necessária para resolver o problema do logaritmo discreto para um número primo de 1024 bits estaria dentro do orçamento de uma grande agência de inteligência nacional, como a NSA dos EUA. Os autores especulam que a pré-computação contra primos DH de 1024 bits amplamente reutilizados está por trás das alegações contidas em documentos vazados da NSA de que a agência é capaz de quebrar grande parte da criptografia atual.^[5]

• Percy Ludgate e o logaritmo irlandês

• Richard Crandall; Carl Pomerance. Capítulo 5, Prime Numbers: A computational perspective, 2ª ed., Springer.
• Stinson, Douglas Robert (2006). Cryptography: Theory and Practice 3 ed. London, UK: CRC Press. ISBN 978-1-58488-508-5 

Predefinição:Algoritmos da teoria dos números Predefinição:Criptografia de chave pública Predefinição:Premissas de dificuldade computacional