Schnorr é um esquema de assinatura digital baseado no problema matemático de logaritmo discreto. Foi proposta por Claus Schnorr em 1989, sendo uma alternativa segura e eficiente ao sistema de assinado digital DSA (Digital Signature Algorithm).
O esquema de assinatura Schnorr tem algumas vantagens notáveis sobre outras técnicas de assinatura, como a menor complexidade computacional e a possibilidade de agregar assinaturas (ou seja, combinar várias assinaturas em uma só), o que é muito útil em sistemas como o Bitcoin.
A criptografia Schnorr utiliza conceitos de grupos cíclicos e a dificuldade do problema do logaritmo discreto. Vamos entender os passos principais desse algoritmo.
O primeiro passo em um esquema de assinatura Schnorr é definir um grupo cíclico ( G ) de ordem ( q ), onde ( q ) é um número primo grande. Dentro desse grupo, há um gerador ( g ), tal que qualquer elemento ( g^k ) (onde ( k ) é um número inteiro) é um elemento do grupo.
- ( q ): ordem do grupo (número primo)
- ( g ): gerador do grupo
Para simplificação, supomos que temos um campo ( \mathbb{Z}_q ) (os inteiros módulo ( q )).
- Chave privada (( x )): Um número secreto escolhido aleatoriamente pelo usuário.
- Chave pública (( y )): Calculada como ( y = g^x \mod q ).
Assim, a chave pública é uma representação do valor da chave privada no grupo cíclico ( G ).
A geração de uma assinatura Schnorr envolve três etapas principais:
-
Escolha de um número aleatório: O signatário escolhe um número aleatório ( k ) tal que ( 0 \leq k < q ).
-
Cálculo do compromisso: O signatário calcula um compromisso ( r ) como: [ r = g^k \mod q ] Aqui, ( r ) é um valor que "compromete" o signatário a um valor sem revelar o valor de ( k ).
-
Cálculo do desafio: O signatário então calcula o desafio ( e ), que é um hash do compromisso ( r ) concatenado com a mensagem ( m ) a ser assinada. Este passo assegura a integridade da assinatura: [ e = H(r || m) ] onde ( H ) é uma função hash criptográfica segura (como SHA-256).
-
Cálculo da resposta: Finalmente, o signatário calcula a resposta ( s ) como: [ s = k - e \cdot x \mod q ] onde ( x ) é a chave privada e ( e ) é o desafio calculado anteriormente.
A assinatura final é o par de valores ( (r, s) ).
A verificação de uma assinatura Schnorr envolve o seguinte processo:
-
Cálculo do compromisso: O verificador recebe a assinatura ( (r, s) ) e a mensagem ( m ). Em seguida, calcula: [ r' = g^s \cdot y^e \mod q ] onde ( y ) é a chave pública do signatário e ( e ) é o desafio calculado como: [ e = H(r' || m) ]
-
Comparação do compromisso: Se ( r' ) for igual ao ( r ) enviado na assinatura, então a assinatura é válida, caso contrário, é inválida.
Ou seja, a verificação verifica se o compromisso ( r ) e a resposta ( s ) são consistentes com a chave pública ( y ) e a mensagem ( m ).