> Este artigo apresentará o princípio de implementação e escalabilidade do algoritmo de assinatura digital baseado em curva elíptica Ed25519.

Escrito por: Ah Wei

Ed25519 é um algoritmo de assinatura digital baseado em curva elíptica, que é eficiente, seguro e amplamente utilizado. É usado em TLS 1.3, SSH, Tor, ZCash, WhatsApp e Signal. Este artigo explica principalmente os seguintes pontos:

1. Introduza um pouco de conhecimento da teoria de grupos, o objetivo é permitir que todos tenham uma intuição sobre o princípio do Ed25519 e seu problema de escalabilidade. Para uma compreensão mais profunda, você precisa consultar outros materiais;
2. Explique a implementação de ed25519 para a versão 1.0.1 da biblioteca de ferrugem ed25519-dalek;
3. Explique a extensibilidade da biblioteca.

Revisão de fundamentos de matemática

Definição e propriedades de grupos

A teoria de grupos é o conteúdo da pesquisa em álgebra abstrata, mas algumas ideias de álgebra abstrata são muito familiares aos programadores. A herança em orientação a objetos é um bom exemplo.Todos sabemos que depois que as subclasses herdam a classe pai, elas podem usar os métodos definidos na classe pai. A álgebra abstrata pode ser entendida como a definição de algumas propriedades para uma estrutura de dados abstrata, e os teoremas derivados dessas propriedades são verdadeiros para todas as subclasses.

Usando a metáfora agora, vamos ver como a estrutura de dados do grupo é definida.

Um grupo consiste em uma operação (denotada por qualquer operação binária) e alguns elementos, satisfazendo as seguintes propriedades:

Muitos teoremas interessantes podem ser derivados disso:

Para dar alguns exemplos:

• Os inteiros ..., −2, −1, 0, 1, 2, ... e a adição são um grupo porque satisfazem as quatro propriedades acima
• Inteiros e multiplicação não são grupos porque não satisfazem a reversibilidade, 4 x 1/4 = 1, mas 1/4 não é um número inteiro

Terminologia da Teoria de Grupo Recortada

Teorema de Lagrange

Agora apresente um teorema bem interessante, a derivação desse teorema está no vídeo citado no final do artigo.

** "A ordem do grupo é divisível pela ordem do subgrupo."**

Por que esse teorema é interessante, não apenas porque seu processo de prova conecta muitos conhecimentos recém-introduzidos, mas também pelas seguintes conclusões:

**“Se a ordem de um grupo é um número primo, então, de acordo com o teorema de Lagrange, a ordem do subgrupo deve ser ou. Todos os elementos do grupo são geradores, exceto

Implementação do Ed25519

Agora vamos falar sobre Ed25519, que é um dos algoritmos EdDSA. O EdDSA possui 11 parâmetros (a seleção específica desses parâmetros tem um grande impacto na segurança e no desempenho do algoritmo. Para a seleção específica do Ed25519, consulte o link (

Além disso, vale ressaltar que este algoritmo utiliza uma curva elíptica chamada Curve25519 (. Para a curva elíptica, basta sabermos que existem muitos, muitos pontos nela, e a soma desses pontos pode gerar novos pontos. O o novo ponto ainda está na curva. Esses pontos e essa adição podem formar um grupo. Observe que a adição da curva elíptica (é especialmente definida.

Concordamos com a seguinte notação:

Este é um algoritmo interativo, mas não importa, existe um truque chamado heurística Fiat - Shamir (Ele pode converter qualquer algoritmo interativo em um algoritmo não interativo. Eventualmente, usaremos um algoritmo não interativo.

O algoritmo de assinatura digital nos dará a seguinte API:

Implementação KeyGen

Gere uma chave privada e uma chave pública:

1. Gere aleatoriamente uma semente (essa semente tem 32 bytes. Usamos um gerador de números aleatórios criptograficamente seguro que vem com o sistema.

pub fn gerar (csprng: &mut T) -> SecretKeywhere

T: CryptoRng + RngCore,

{

let mut sk: SecretKey = SecretKey([0u8; 32]);

csprng.fill_bytes(&mut sk.0);

sk

}

2. Expanda a semente agora para 64 bytes (ou seja, xseed na figura. Os 32 bytes baixos de xseed são nossa chave privada (também conhecida como a). Os 32 bytes altos são chamados de nonce, que serão usados posteriormente nele, sua função é semelhante ao sperator de domínio.

pub struct ExpandedSecretKey { // xseed pub(crate) key: Scalar, // a

pub(caixa) nonce: [u8; 32], // nonce

}

fn from(secret_key: &'a SecretKey) -> ExpandedSecretKey {

let mut h: Sha512 = Sha512::default();

deixe mut hash: [u8; 64] = [0u8; 64];

deixe mut mais baixo: [u8; 32] = [0u8; 32];

let mut upper: [u8; 32] = [0u8; 32];

h.update(secret_key.as_bytes());

hash.copy_from_slice(h.finalize().as_slice());

lower.copy_from_slice(&hash[00..32]);

upper.copy_from_slice(&hash[32..64]);

// Este passo é clamp

mais baixo [0] &= 248;

mais baixo [31] &= 63;

mais baixo [31] |= 64;

ExpandedSecretKey{ key: Scalar::from_bits(inferior), nonce: superior, }

}

3. Use a chave privada para gerar a chave pública (a chave pública é um ponto na curva elíptica. Especificamente, usamos o ponto base da curva elíptica para realizar a multiplicação da curva elíptica para obter a chave pública. O escalar na multiplicação é obtido emparelhando a chave privada Faça um hash para obtê-lo.

pub struct ExpandedSecretKey { // xseed pub(crate) key: Scalar, // a

pub(caixa) nonce: [u8; 32], // nonce

}

fn from(secret_key: &'a SecretKey) -> ExpandedSecretKey {

let mut h: Sha512 = Sha512::default();

deixe mut hash: [u8; 64] = [0u8; 64];

deixe mut mais baixo: [u8; 32] = [0u8; 32];

let mut upper: [u8; 32] = [0u8; 32];

h.update(secret_key.as_bytes());

hash.copy_from_slice(h.finalize().as_slice());

lower.copy_from_slice(&hash[00..32]);

upper.copy_from_slice(&hash[32..64]);

// Este passo é clamp

mais baixo [0] &= 248;

mais baixo [31] &= 63;

mais baixo [31] |= 64;

ExpandedSecretKey{ key: Scalar::from_bits(inferior), nonce: superior, }

}

Implementação do sinal

Aqui você pode mencionar a técnica Fiat Shamir mencionada anteriormente.Na verdade, você só precisa substituir todos os números aleatórios fornecidos pelo Verifier pelo resultado de uma função hash. Consulte os comentários do código para obter detalhes.

pub fn sign(&auto, mensagem: & [u8] , public_key: &PublicKey) -> ed25519::Assinatura {

let mut h: Sha512 = Sha512::new();

let R: CompressedEdwardsY;

seja r: Escalar;

seja s: Escalar;

seja k: escalar;

h.update(&self.nonce);

h.update(&mensagem);

r = Scalar::from_hash(h); // r é um número aleatório em nosso algoritmo interativo, mas aqui usamos um hash.

R = (&r * &constantes::ED25519_BASEPOINT_TABLE).compress(); // R = [r] B

h = Sha512::novo();

h.update(R.as_bytes());

h.update(public_key.as_bytes());

h.update(&mensagem);

k = Escalar::de_hash(h); // h = Sha512(R || A || M)

s = &(&k * &self.key) + &r; // s = r + h * a, h é originalmente um número aleatório

Assinatura interna { R, s }.into()

}

Implementação do Verify

impl Verificador para PublicKey {

#[allow(non_snake_case)]

fn verificar(

&auto,

mensagem: & [u8] ,

assinatura: &ed25519::Assinatura

) -> Resultado<(), SignatureError>

{

let signature = InternalSignature::try_from(signature)?;

let mut h: Sha512 = Sha512::new();

deixe R: EdwardsPoint;

seja k: Escalar;

deixe menos_A: EdwardsPoint = -self.1;

h.update(assinatura.R.as_bytes());

h.update(self.as_bytes());

h.update(&mensagem);

k = Scalar::from_hash(h); // O cálculo de h é o mesmo que em sign, h=Sha512(R||A||M)

R = EdwardsPoint::time_double_scalar_mul_basepoint(&k, &(menos_A), &signature.s); // R' = [s] B- [h] A

if R.compress() == signature.R { // Se R'==R, então o resultado da verificação é verdadeiro.

OK(())

} outro {

Err(InternalError::VerifyError.into())

}

}

}

código endereço (

Problemas de escalabilidade

Há muitos lugares para prestar atenção na implementação e uso de algoritmos criptográficos. Quando dizemos que um algoritmo de assinatura digital é seguro, geralmente significa que, mesmo que o invasor consiga obter a assinatura de qualquer mensagem (Chosen Message Attack), o invasor ainda não pode falsificar a assinatura. Ed25519 satisfaz esta propriedade, mas não significa que Ed25519 seja absolutamente seguro. Também é mencionado no artigo original que o problema de escalabilidade é aceitável, e o algoritmo original tem esse problema.

Desta forma, tanto a assinatura recém-construída quanto a assinatura antiga podem ser verificadas com sucesso. O problema de maleabilidade nos diz que a assinatura não é determinística em relação à mensagem e à chave pública.Quando o algoritmo de assinatura tem um problema de maleabilidade e o código assume que a assinatura é determinística, é provável que haja brechas.

De acordo com o padrão (na verdade, não há problema de escalabilidade. Porque no processo de verificação, vamos verificar se é menor que, se o resultado da verificação não for verdadeiro, a verificação falha. Mas o padrão (aparece depois do papel (portanto, no ambiente real, ainda existem implementações do Ed25519 que apresentam problemas de escalabilidade e requerem implementações que examinamos.

Resumir

Obrigado

*Agradecimentos à Safeheron, uma provedora líder de serviços de autocustódia de ativos digitais, por fornecer consultoria técnica profissional. *

> Referências

> [1] .

> [2] .

> [3] .

> [4] .

> [5] . Pesquisadores usam a teoria de grupos para acelerar algoritmos - Introdução aos grupos