Este artículo presentará el principio de implementación y la escalabilidad del algoritmo de firma digital basado en curva elíptica Ed25519.

Escrito por: Ah Wei

Ed25519 es un algoritmo de firma digital basado en curva elíptica, eficiente, seguro y ampliamente utilizado. Se utiliza en TLS 1.3, SSH, Tor, ZCash, WhatsApp y Signal. Este artículo explica principalmente los siguientes puntos:

1. Introducir un poco de conocimiento de la teoría de grupos, el propósito es que todos tengan una intuición sobre el principio de Ed25519 y su problema de escalabilidad. Para una comprensión más profunda, debe consultar otros materiales;
2. Explicar la implementación de ed25519 para la versión 1.0.1 de la biblioteca de óxido ed25519-dalek;
3. Explique la extensibilidad de la biblioteca.

Revisión de fundamentos matemáticos

Definición y propiedades de los grupos

La teoría de grupos es el contenido de la investigación del álgebra abstracta, pero algunas ideas del álgebra abstracta son muy familiares para los programadores. La herencia en orientación a objetos es un buen ejemplo.Todos sabemos que después de que las subclases heredan la clase principal, pueden usar los métodos definidos en la clase principal. El álgebra abstracta puede entenderse como la definición de algunas propiedades para una estructura de datos abstracta, y los teoremas derivados de estas propiedades son válidos para todas las subclases.

Usando la metáfora de ahora, veamos cómo se define la estructura de datos del grupo.

Un grupo consta de una operación (denotada por cualquier operación binaria) y algunos elementos, que satisfacen las siguientes propiedades:

Muchos teoremas interesantes se pueden derivar de esto:

Para dar algunos ejemplos:

• Los enteros …, −2, −1, 0, 1, 2, … y la suma son un grupo porque cumplen las cuatro propiedades anteriores
• Los números enteros y la multiplicación no son grupos porque no satisfacen la reversibilidad, 4 x 1/4 = 1, pero 1/4 no es un número entero

Terminología de la teoría de grupos recortada

Teorema de Lagrange

Ahora presente un teorema muy interesante, la derivación de este teorema se encuentra en el video citado al final del artículo.

** “El orden del grupo es divisible por el orden del subgrupo”.**

¿Por qué es interesante este teorema, no solo porque su proceso de prueba conecta mucho conocimiento recién introducido, sino también por las siguientes conclusiones?

**“Si el orden de un grupo es un número primo, entonces de acuerdo con el teorema de Lagrange, el orden del subgrupo debe ser o.Todos los elementos del grupo son generadores excepto

Implementación de Ed25519

Ahora hablemos de Ed25519, que es uno de los algoritmos EdDSA. EdDSA tiene 11 parámetros (la selección específica de estos parámetros tiene un gran impacto en la seguridad y el rendimiento del algoritmo. Para la selección específica de Ed25519, consulte el enlace (

Además, vale la pena mencionar que este algoritmo usa una curva elíptica llamada Curve25519 (. Para la curva elíptica, solo necesitamos saber que hay muchos, muchos puntos en ella, y la suma de estos puntos puede generar nuevos puntos. El El nuevo punto todavía está en la curva. Estos puntos y esta suma pueden formar un grupo. Tenga en cuenta que la suma de la curva elíptica (está especialmente definida.

Estamos de acuerdo con la siguiente notación:

Este es un algoritmo interactivo, pero no importa, hay un truco llamado la heurística Fiat - Shamir (Puede convertir cualquier algoritmo interactivo en un algoritmo no interactivo. Eventualmente usaremos un algoritmo no interactivo.

El algoritmo de firma digital nos dará la siguiente API:

Implementación KeyGen

Salida de una clave privada y una clave pública:

1. Genere aleatoriamente una semilla (esta semilla tiene 32 bytes. Usamos un generador de números aleatorios criptográficamente seguro que viene con el sistema.

publicar fn generar (csprng: &mut T) -> SecretKeywhere

T: CriptoRng + RngCore,

{

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

csprng.fill_bytes(&mut sk.0);

sk

}

2. Expanda la semilla justo ahora a 64 bytes (es decir, xseed en la figura. Los 32 bytes bajos de xseed son nuestra clave privada (también conocida como a). Los 32 bytes altos se llaman nonce, que se usarán más adelante en él, su función es similar al dominio sperator.

pub struct ExpandedSecretKey { // xseed pub (caja) clave: Escalar, // a

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

}

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

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

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

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

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

h.update(secreto_clave.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 paso es abrazadera

más bajo [0] &= 248;

más bajo [31] &= 63;

más bajo [31] |= 64;

ExpandedSecretKey{ clave: Escalar::de_bits(inferior), nonce: superior, }

}

3. Use la clave privada para generar la clave pública (la clave pública es un punto en la curva elíptica. Específicamente, usamos el punto base de la curva elíptica para realizar la multiplicación de la curva elíptica para obtener la clave pública. El escalar en la multiplicación se obtiene emparejando la clave privada Haz un hash para obtenerla.

pub struct ExpandedSecretKey { // xseed pub (caja) clave: Escalar, // a

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

}

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

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

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

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

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

h.update(secreto_clave.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 paso es abrazadera

más bajo [0] &= 248;

más bajo [31] &= 63;

más bajo [31] |= 64;

ExpandedSecretKey{ clave: Escalar::de_bits(inferior), nonce: superior, }

}

Implementación de Sign

Aquí puede mencionar la técnica Fiat Shamir mencionada anteriormente, de hecho, solo necesita reemplazar todos los números aleatorios proporcionados por Verifier con el resultado de una función hash. Vea los comentarios del código para más detalles.

pub fn sign(&self, mensaje: & [u8] , public_key: &PublicKey) -> ed25519::Firma {

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

sea R: CompressedEdwardsY;

sea r: escalar;

sea s: escalar;

sea k: escalar;

h.update(&self.nonce);

h.update(&mensaje);

r = Scalar::from_hash(h); // r es un número aleatorio en nuestro algoritmo interactivo, pero aquí usamos un hash.

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

h = Sha512::nuevo();

h.update(R.as_bytes());

h.update(public_key.as_bytes());

h.update(&mensaje);

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

s = &(&k * &self.key) + &r; // s = r + h * a, h es originalmente un número aleatorio

Firmainterna { R, s }.into()

}

Implementación de Verificar

Verificador impled25519::Signature para clave pública {

#[permitir(no_serpiente_caso)]

fn verificar (

&ser,

mensaje: & [u8] ,

firma: &ed25519::Firma

) -> Resultado<(), SignatureError>

{

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

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

sea R: EdwardsPoint;

sea k: escalar;

let minus_A: EdwardsPoint = -self.1;

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

h.update(self.as_bytes());

h.update(&mensaje);

k = Scalar::from_hash(h); // El cálculo de h es el mismo que en 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() == firma.R { // Si R’==R, entonces el resultado de la verificación es verdadero.

De acuerdo(())

} demás {

Err(ErrorInterno::VerificarError.into())

}

}

}

código dirección (

Problemas de escalabilidad

Hay muchos lugares a los que prestar atención en la implementación y el uso de algoritmos criptográficos. Cuando decimos que un algoritmo de firma digital es seguro, generalmente significa que incluso si el atacante puede obtener la firma de cualquier mensaje (ataque de mensaje elegido), el atacante aún no puede falsificar la firma. Ed25519 satisface esta propiedad, pero eso no significa que Ed25519 sea absolutamente seguro. También se menciona en el documento original que el problema de escalabilidad es aceptable y el algoritmo original tiene este problema.

De esta forma, tanto la firma recién construida como la firma antigua pueden verificarse con éxito. El problema de maleabilidad nos dice que la firma no es determinista en relación con el mensaje y la clave pública. Cuando el algoritmo de firma tiene un problema de maleabilidad y el código asume que la firma es determinista, es probable que haya lagunas.

De acuerdo con el estándar (de hecho, no hay problema de escalabilidad. Porque en el proceso de verificación, verificaremos si es menor que, si el resultado de la verificación no es cierto, la verificación falla. Pero el estándar (aparece más tarde que el papel (Entonces, en el entorno real, todavía hay implementaciones de Ed25519 que tienen problemas de escalabilidad y requieren implementaciones que examinamos.

Resumir

Gracias

*Gracias a Safeheron, un proveedor líder de servicios integrales de autocustodia de activos digitales, por brindar asesoramiento técnico profesional. *

Referencias

[1] .

[2] .

[3] .

[4] .

[5] . Los investigadores utilizan la teoría de grupos para acelerar los algoritmos: introducción a los grupos