A criptografia por trás da Bytecoin

As operações nas quais toda criptomoeda baseia-se (ou das quais parte) são algoritmos criptográficos. O Bitcoin tem apenas dois tipos: as funções hash e a assinatura digital. Por mais surpreendente que pareça, a criptografia (ou encobrimento de informações) nem sequer é mencionada no artigo original de Satoshi Nakamoto (para ser claro, as chaves privadas dos usuários são armazenadas criptografadas, mas isso é apenas uma função da carteira específica, não do protocolo descrito no documento técnico original).

Vamos observar essas operações mais atentamente:

Publicidade

A função hash é uma função que pode ser usada para mapear dados de tamanho arbitrário (mas finito) para dados de tamanho fixo. Por exemplo, uma string:

Estou vendendo uma GPU GTX 1080

pode transformar-se em

12e6fa4e89a97ea2

por meio de várias operações matemáticas nos bytes de origem dessa string. As funções hash têm uma extraordinária propriedade chamada de efeito “avalanche”: se uma entrada sofre uma leve alteração, o resultado é completamente diferente. Portanto, o exemplo:

Estou vendendo uma GPU GTX 1081

pode tornar-se

0a9eeee64b55d39a

Consequentemente, as funções hash podem ser consideradas “digitais únicas” dos dados, o que os torna insubstituíveis tratando-se de manter o dados de uma blockchain (essencialmente, uma cadeia de hashes) imutáveis e as transações irreversíveis.

A assinatura digital é um esquema matemático que Maria pode usar para provar a autoria (ou posse) de algo e João pode usar para verificar essa autoria. Essencialmente, é semelhante à uma assinatura à mão numa folha de papel. As criptomoedas usam as assinaturas digitais de duas maneiras: primeiro, garantem a autoria de uma determinada transferência e segundo, impedem que uma pessoa má intencionada manipule uma transação (trocando o remetente, por exemplo), uma vez que a assinatura original não seria mais verificável. Essa segunda propriedade é mediada pelo uso de assinaturas digitais no hash da transação.

De modo geral, o funcionamento da blockchain não requer outras operações: a assinatura prova a titularidade das moedas e outros ativos digitais, e o hash garante a integridade e a imutabilidade dos dados. Mas há uma grande variedade de algoritmos de assinatura digital e hash! Além disso, alguns algoritmos podem ser implementados numa vasta gama de objetos matemáticos. Por fim, mas não menos importante, as operações matemáticas podem ser executadas de forma diferente: pode-se contar 2⁸ como 2₀*2₁*…*2₇ (sete multiplicações) ou como (((2²)²)²) (três quadrados).

Nesse quesito, a Bytecoin distingue-se da maioria das criptomoedas. Não trata-se apenas do tipo fundamentalmente diferente de assinaturas (as assinaturas em anel são usadas para provar a autoria de forma anônima, sem apontar para o autor), mas de um aparato matemático distinto (curvas elípticas de Edwards) e uma distinta biblioteca de software para operações criptográficas básicas, escritas pelo famoso criptógrafo D.J. Bernstein.

Assinaturas digitais

As funções hash serão descritas em maios detalhes no próximo artigo. Antes de entrarmos em detalhes sobre as assinaturas de anel na Bytecoin, vejamos os algoritmos convencionais de assinatura digital em uso hoje.

Buscando a próxima moeda 100x?
Confira nossas sugestões de Pre-Sales para investir agora

A assinatura digital é um sistema criptográfico de chave pública. Em tal sistema, Maria tem uma chave privada x (que apenas ela conhece), além de uma chave pública P = Bˣ (que todos conhecem). B é o parâmetro público de um sistema criptográfico que é escolhido de antemão e do conhecimento de todos. Como a criptografia envolvida nas assinaturas digitais utiliza números muito grandes (1000…00 – 77 zeros ou mais), é praticamente impossível atacar por força bruta uma chave privada, conhecendo apenas P e B. Além disso, não existe um algoritmo eficiente para se pesquisar o chamado logaritmo discreto (x é um logaritmo de P para a base B) – pelo menos é o que se acredita hoje.

Maria pode usar a chave privada para criar uma assinatura e todos podem usar a chave pública para verificá-la. A assinatura prova que Maria, e apenas Maria, a criou. Portanto, essa condição é verdadeira contanto que a chave privada seja mantida em segredo.

ElGamal

O esquema de ElGamal de 1985 (Taher Elgamal) é o antecessor dos algoritmos de assinatura digital modernos. Na base de sua fórmula

Publicidade

Bʰ⁽ᴹ⁾ = Pᴿ * Rˢ, onde

h(M) – hash da mensagem sendo assinada,

R = Bᵏ,

Publicidade

k – número aleatório selecionado por Maria.

O par de números (R, s) constitui a assinatura que Maria criou para a verificação pública da mensagem.

Para que essa fórmula seja verdadeira, Maria precisa encontrar o valor correspondente s. Não é difícil, pois conhece todos os outros elementos da equação. Nós podemos substituir os valores para ter certeza:

Publicidade

Bʰ⁽ᴹ⁾ = Pᴿ * Rˢ

Bʰ⁽ᴹ⁾ = (Bˣ)ᴿ * (Bᵏ)ˢ

Bʰ⁽ᴹ⁾ = B⁽ˣᴿ⁾ * B⁽ᵏˢ⁾

Publicidade

Bʰ⁽ᴹ⁾ = B⁽ˣᴿ⁺ᵏˢ⁾

h(M) = xR+ks

s = (h(M)-xR)/k

Nós podemos ver que o valor s depende da chave privada x e da mensagem M, logo:

a) essa assinatura não funcionaria para uma mensagem M₂ diferente;

b) qualquer tentativa de forjar a assinatura sem a chave x equivale a um ataque de força bruta.

Schnorr

O esquema de ElGamal passou por algumas melhorias depois de 1985 (nós as omitiremos para fins de concisão). Em 1990, Claus Schnorr publicou sua versão de uma assinatura digital, que se baseia na equação Bˢ = R*Pʰ⁽ᴿᴹ⁾. Para criar uma assinatura (R,s), Maria precisa calcular s = x*h(R,M) – k.

Como se pode ver, os cálculos ficaram mais simples (por exemplo, não há necessidade de dividir números grandes). Além disso, o valor s pode ser visivelmente menor sem afetar a força criptográfica do algoritmo, de modo que o tamanho da assinatura diminui (formalmente falando, o valor s está contido em um pequeno subconjunto de um conjunto maior de números, mas o intruso ainda tem que lidar com o maior conjunto durante um ataque de força bruta). Entre outras coisas, os requisitos da função hash “h” se tornam menos rigorosos: não precisam ser resistentes a colisões – uma propriedade que é difícil de provar na prática.

Outra propriedade importante de uma assinatura Schnorr é a assinatura agregada. Se você tiver assinaturas (R₁,s₁) e (R₂,s₂) para uma mensagem M, então poderá transformá-las em uma assinatura (R₃,s₃) = (R₁*R₂, s₁+s₂). Mesmo se você tiver 10 assinaturas, elas serão transformadas em uma, o que acelera a verificação em 10 vezes. Essa propriedade é muito útil nas criptomoedas, quando as transações geralmente contêm várias assinaturas da mesma mensagem (a transação em si).

EC (DSA)

Por fim, 1991 viu o surgimento do DSA (do inglês: algoritmo de assinatura digital), que foi adotado com um padrão NIST alguns anos depois. Também se baseia no algoritmo ElGamal (a assinatura é (R, s) como antes), mas era tecnologicamente inferior:

R = Bʰ⁽ᴹ⁾/ˢ * P⁽ᴿ/ˢ⁾

Particularmente, as operações de divisão ainda eram necessárias, e a função hash tinha que ser resistente à colisão. Isso pode ter sido porque a assinatura Schnorr teve cobertura de patente até 2008 ou porque houve o envolvimento da NSA.

De uma forma ou de outra, o DSA é usado na maioria dos softwares hoje em dia, em particular, no Bitcoin e em suas bifurcações (para ser mais exato, ECDSA, contraparte do DSA em curvas elípticas). Não se pode dizer que essa assinatura seja fraca, mas há casos de uso indevido do DSA que tiveram consequências catastróficas (em termos de criptografia).

Por exemplo, o número k, escolhido por Maria, por acaso não pode ser aleatório: do contrário, qualquer um pode encontrar a chave secreta por meio da assinatura:

R = Bʰ⁽ᴹ⁾/ˢ * P⁽ᴿ/ˢ⁾

Bᵏ = Bʰ⁽ᴹ⁾/ˢ * Bˣᴿ/ˢ

Bᵏ = B⁽ʰ⁽ᴹ⁾/ˢ ⁺ ˣᴿ/ˢ⁾

k = h(M)/s + xR/s

x = (ks – h(M))/R

Mesmo que o mesmo valor k seja usado em duas assinaturas diferentes (R,s₁) и (R,s₂), a chave pode ser encontrada:

R = B⁽ʰ⁽ᴹ¹⁾/ˢ¹⁾ * B⁽ˣᴿ/ˢ¹⁾

R = B⁽ʰ⁽ᴹ²⁾/ˢ²⁾ * B⁽ˣᴿ/ˢ²⁾

h(M₁)/s₁ + x*R/s₁ = h(M₂)/s₂ + x*R/s₂

x*(R/s₁ – R/s₂) = h(M₂)/s₂ – h(M₁)/s₁

x = (h(M₂)/s₂ – h(M₁)/s₁) / (R/s₁ – R/s₂)

Foi através desse método que a chave do PlayStaytion 3 foi hackeada em 2010. Mal pode se dizer que seja um hackeamento, já que a Sony publicou os dados que foram usados para encontrar a chave, aplicando o algoritmo de forma incorreta.

Assinatura em anel

Todos os algoritmos de assinatura digital mencionados até agora têm uma propriedade comum: eles apontam o autor da assinatura de modo explícito (através de sua chave pública). A Bytecoin e outras moedas baseadas no CryptoNote utilizam uma assinatura em anel nas transações, que podem ser validadas não apenas por uma, mas por múltiplas chaves públicas, portanto, sem apontar para o autor.

Não vamos entrar em maiores detalhes sobre o algoritmo da assinatura em anel, você pode saber mais aqui. Vale a pena salientar que se baseia na fórmula de Schnorr Bˢᶦ = Rᵢ*Pʰ⁽ᴿᶦ,ᴹ⁾. Não existe apenas uma declaração, mas 2N delas (onde N é o número de chaves públicas no anel). A assinatura conta com um conjunto de 2N pares (Rᵢ, sᵢ), e a função hash é aplicada a todos esses elementos de uma só vez. Desta forma, pode-se afirmar que as assinaturas únicas em anel do CryptoNote são uma “extensão em anel” da assinatura Schnorr, com todas as suas vantagens.

É necessário salientar que mostramos equações para “números regulares”, mas, no momento, estes se baseiam em pontos de curvas elípticas. Todos os algoritmos mencionados têm implementações no mundo elíptico, usados em ação. No próximo artigo, falaremos por que as curvas elípticas são melhores do que os “números regulares” e por que algumas curvas são melhores que outras (é nesse ponto que as criptomoedas diferem).

*Esse texto foi elaborado pela equipe de desenvolvimento da Bytecoin.