> Cet article présentera le principe d'implémentation et la scalabilité de l'algorithme de signature numérique basé sur les courbes elliptiques Ed25519.
Écrit par : Ah Wei
Ed25519 est un algorithme de signature numérique basé sur une courbe elliptique, efficace, sécurisé et largement utilisé. Il est utilisé dans TLS 1.3, SSH, Tor, ZCash, WhatsApp et Signal. Cet article explique principalement les points suivants :
Introduire un peu de connaissances en théorie des groupes, le but est de permettre à chacun d'avoir une intuition sur le principe d'Ed25519 et son problème de scalabilité. Pour une compréhension plus approfondie, vous devez vous référer à d'autres matériaux;
Expliquer l'implémentation de ed25519 pour la version 1.0.1 de la bibliothèque de rouille ed25519-dalek ;
Expliquez l'extensibilité de la bibliothèque.
Révision de l'essentiel des mathématiques
Définition et propriétés des groupes
La théorie des groupes est le contenu de la recherche en algèbre abstraite, mais certaines idées d'algèbre abstraite sont très familières aux programmeurs. L'héritage orienté objet en est un bon exemple. Nous savons tous qu'une fois que les sous-classes héritent de la classe parent, elles peuvent utiliser les méthodes définies dans la classe parent. L'algèbre abstraite peut être comprise comme définissant certaines propriétés pour une structure de données abstraite, et les théorèmes dérivés de ces propriétés sont vrais pour toutes les sous-classes.
En utilisant la métaphore tout à l'heure, voyons comment la structure de données du groupe est définie.
Un groupe se compose d'une opération (désignée par n'importe quelle opération binaire) et de quelques éléments, satisfaisant les propriétés suivantes :
De nombreux théorèmes intéressants peuvent en découler :
Pour donner quelques exemples :
Les entiers ..., −2, −1, 0, 1, 2, ... et l'addition forment un groupe car ils satisfont les quatre propriétés ci-dessus
Les entiers et la multiplication ne sont pas des groupes car ils ne satisfont pas la réversibilité, 4 x 1/4 = 1, mais 1/4 n'est pas un entier
La terminologie de la théorie des groupes est résumée
Théorème de Lagrange
Introduisons maintenant un théorème très intéressant, la dérivation de ce théorème se trouve dans la vidéo citée à la fin de l'article.
** "L'ordre du groupe est divisible par l'ordre du sous-groupe."**
Pourquoi ce théorème est-il intéressant, non seulement parce que son processus de preuve relie beaucoup de connaissances qui viennent d'être introduites, mais aussi à cause des conclusions suivantes :
** "Si l'ordre d'un groupe est un nombre premier, alors selon le théorème de Lagrange, l'ordre du sous-groupe doit être ou. Tous les éléments du groupe sont des générateurs sauf
Implémentation de Ed25519
Parlons maintenant d'Ed25519, qui est l'un des algorithmes EdDSA. EdDSA a 11 paramètres (la sélection spécifique de ces paramètres a un grand impact sur la sécurité et les performances de l'algorithme. Pour la sélection spécifique de Ed25519, veuillez vous référer au lien (
De plus, il convient de mentionner que cet algorithme utilise une courbe elliptique appelée Curve25519 (. Pour la courbe elliptique, nous avons seulement besoin de savoir qu'il y a beaucoup, beaucoup de points dessus, et l'ajout de ces points peut obtenir de nouveaux points. Le de nouveaux points sont toujours sur la courbe. Ces points et cette addition peuvent former un groupe. Notez que l'addition de courbe elliptique (est spécialement définie.
On est d'accord sur la notation suivante :
C'est un algorithme interactif, mais peu importe, il existe une astuce appelée l'heuristique Fiat - Shamir (elle peut convertir n'importe quel algorithme interactif en un algorithme non interactif. Finalement, nous utiliserons un algorithme non interactif.
L'algorithme de signature numérique nous donnera l'API suivante :
Mise en œuvre de KeyGen
Sortez une clé privée et une clé publique :
Générer aléatoirement une graine (cette graine a 32 octets. Nous utilisons un générateur de nombres aléatoires cryptographiquement sécurisé fourni avec le système.
Développez la graine tout à l'heure à 64 octets (c'est-à-dire xseed dans la figure. Les 32 octets inférieurs de xseed sont notre clé privée (alias a). Les 32 octets supérieurs sont appelés nonce, qui seront utilisés plus tard Dans celui-ci, sa fonction est similaire à celle de domaine sperator.
Utilisez la clé privée pour générer la clé publique (la clé publique est un point sur la courbe elliptique. Plus précisément, nous utilisons le point de base de la courbe elliptique pour effectuer la multiplication de la courbe elliptique afin d'obtenir la clé publique. Le scalaire dans la multiplication est obtenu en associant la clé privée Faites un hachage pour l'obtenir.
Ici, vous pouvez mentionner la technique Fiat Shamir mentionnée précédemment, en fait, il vous suffit de remplacer tous les nombres aléatoires fournis par Verifier par le résultat d'une fonction de hachage. Voir les commentaires du code pour plus de détails.
r = Scalar::from_hash(h); // r est un nombre aléatoire dans notre algorithme interactif, mais ici nous utilisons un hachage.
R = (&r * &constantes::ED25519_BASEPOINT_TABLE).compress(); // R = [r] B
h = Sha512::nouveau();
h.update(R.as_bytes());
h.update(public_key.as_bytes());
h.update(&message);
k = Scalaire ::from_hash(h); // h = Sha512(R || A || M)
s = &(&k * &self.key) + &r; // s = r + h * a, h est à l'origine un nombre aléatoire
SignatureInterne { R, s }.into()
}
Implémentation de Vérifier
impl Vérificateur pour CléPublique {
#[allow(non_snake_case)]
fn vérifier(
&soi,
message: & [u8] ,
signature: &ed25519::Signature
) -> Résultat<(), SignatureError>
{
let signature = InternalSignature::try_from(signature) ? ;
soit mut h : Sha512 = Sha512::new();
Soit R : EdwardsPoint ;
soit k : scalaire ;
soit moins_A : EdwardsPoint = -self.1 ;
h.update(signature.R.as_bytes());
h.update(self.as_bytes());
h.update(&message);
k = Scalar::from_hash(h); // Le calcul de h est le même que dans le signe, h=Sha512(R||A||M)
R = EdwardsPoint::time_double_scalar_mul_basepoint(&k, &(moins_A), &signature.s); // R' = [s] B- [h] UN
if R.compress() == signature.R { // Si R'==R, alors le résultat de la vérification est vrai.
D'accord(())
} autre {
Err(InternalError::VerifyError.into())
}
}
}
code adresse (
Problèmes d'évolutivité
Il y a de nombreux endroits auxquels il faut prêter attention dans la mise en œuvre et l'utilisation des algorithmes cryptographiques. Lorsque nous disons qu'un algorithme de signature numérique est sécurisé, cela signifie généralement que même si l'attaquant peut obtenir la signature de n'importe quel message (Chosen Message Attack), l'attaquant ne peut toujours pas falsifier la signature. Ed25519 satisfait cette propriété, mais cela ne signifie pas que Ed25519 est absolument sûr. Il est également mentionné dans l'article d'origine que le problème d'évolutivité est acceptable, et l'algorithme d'origine a ce problème.
De cette manière, à la fois la signature nouvellement construite et l'ancienne signature peuvent être vérifiées avec succès. Le problème de malléabilité nous indique que la signature n'est pas déterministe par rapport au message et à la clé publique. Lorsque l'algorithme de signature a un problème de malléabilité et que le code suppose que la signature est déterministe, il y a probablement des failles.
Selon la norme (en fait, il n'y a pas de problème d'évolutivité. Parce que dans le processus de vérification, nous vérifierons s'il est inférieur à, si le résultat de la vérification n'est pas vrai, la vérification échoue. Mais la norme (apparaît plus tard que le papier (Ainsi, dans l'environnement réel, il existe encore des implémentations d'Ed25519 qui ont des problèmes d'évolutivité et nécessitent des implémentations que nous examinons.
Résumer
Merci
*Merci à Safeheron, l'un des principaux fournisseurs de services d'auto-conservation d'actifs numériques, pour ses conseils techniques professionnels. *
> Références
> [1] .
> [2] .
> [3] .
> [4] .
> [5] . Des chercheurs utilisent la théorie des groupes pour accélérer les algorithmes — Introduction aux groupes
Voir l'original
Le contenu est fourni à titre de référence uniquement, il ne s'agit pas d'une sollicitation ou d'une offre. Aucun conseil en investissement, fiscalité ou juridique n'est fourni. Consultez l'Avertissement pour plus de détails sur les risques.
Discuter du principe de mise en œuvre et de l'évolutivité d'Ed25519
> Cet article présentera le principe d'implémentation et la scalabilité de l'algorithme de signature numérique basé sur les courbes elliptiques Ed25519.
Écrit par : Ah Wei
Ed25519 est un algorithme de signature numérique basé sur une courbe elliptique, efficace, sécurisé et largement utilisé. Il est utilisé dans TLS 1.3, SSH, Tor, ZCash, WhatsApp et Signal. Cet article explique principalement les points suivants :
Révision de l'essentiel des mathématiques
Définition et propriétés des groupes
La théorie des groupes est le contenu de la recherche en algèbre abstraite, mais certaines idées d'algèbre abstraite sont très familières aux programmeurs. L'héritage orienté objet en est un bon exemple. Nous savons tous qu'une fois que les sous-classes héritent de la classe parent, elles peuvent utiliser les méthodes définies dans la classe parent. L'algèbre abstraite peut être comprise comme définissant certaines propriétés pour une structure de données abstraite, et les théorèmes dérivés de ces propriétés sont vrais pour toutes les sous-classes.
En utilisant la métaphore tout à l'heure, voyons comment la structure de données du groupe est définie.
Un groupe se compose d'une opération (désignée par n'importe quelle opération binaire) et de quelques éléments, satisfaisant les propriétés suivantes :
De nombreux théorèmes intéressants peuvent en découler :
Pour donner quelques exemples :
La terminologie de la théorie des groupes est résumée
Théorème de Lagrange
Introduisons maintenant un théorème très intéressant, la dérivation de ce théorème se trouve dans la vidéo citée à la fin de l'article.
** "L'ordre du groupe est divisible par l'ordre du sous-groupe."**
Pourquoi ce théorème est-il intéressant, non seulement parce que son processus de preuve relie beaucoup de connaissances qui viennent d'être introduites, mais aussi à cause des conclusions suivantes :
** "Si l'ordre d'un groupe est un nombre premier, alors selon le théorème de Lagrange, l'ordre du sous-groupe doit être ou. Tous les éléments du groupe sont des générateurs sauf
Implémentation de Ed25519
Parlons maintenant d'Ed25519, qui est l'un des algorithmes EdDSA. EdDSA a 11 paramètres (la sélection spécifique de ces paramètres a un grand impact sur la sécurité et les performances de l'algorithme. Pour la sélection spécifique de Ed25519, veuillez vous référer au lien (
De plus, il convient de mentionner que cet algorithme utilise une courbe elliptique appelée Curve25519 (. Pour la courbe elliptique, nous avons seulement besoin de savoir qu'il y a beaucoup, beaucoup de points dessus, et l'ajout de ces points peut obtenir de nouveaux points. Le de nouveaux points sont toujours sur la courbe. Ces points et cette addition peuvent former un groupe. Notez que l'addition de courbe elliptique (est spécialement définie.
On est d'accord sur la notation suivante :
C'est un algorithme interactif, mais peu importe, il existe une astuce appelée l'heuristique Fiat - Shamir (elle peut convertir n'importe quel algorithme interactif en un algorithme non interactif. Finalement, nous utiliserons un algorithme non interactif.
L'algorithme de signature numérique nous donnera l'API suivante :
Mise en œuvre de KeyGen
Sortez une clé privée et une clé publique :
pub fn générer (csprng : &mut T) -> SecretKeywhere
T : CryptoRng + RngCore,
{
let mut sk : SecretKey = SecretKey([0u8; 32]);
csprng.fill_bytes(&mut sk.0);
sk
}
pub struct ExpandedSecretKey { // xseed pub(crate) key : Scalar, // a
pub(caisse) nonce : [u8 ; 32], // non
}
fn from(secret_key: &'a SecretKey) -> ExpandedSecretKey {
soit mut h : Sha512 = Sha512::default();
laissez mut hacher : [u8 ; 64] = [0u8 ; 64] ;
laissez mut plus bas : [u8; 32] = [0u8 ; 32] ;
laissez mut supérieur : [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]);
// Cette étape est pince
inférieur [0] &= 248;
inférieur [31] &= 63;
inférieur [31] |= 64 ;
ExpandedSecretKey{ key : Scalar ::from_bits(inférieur), nonce : supérieur, }
}
pub struct ExpandedSecretKey { // xseed pub(crate) key : Scalar, // a
pub(caisse) nonce : [u8 ; 32], // non
}
fn from(secret_key: &'a SecretKey) -> ExpandedSecretKey {
soit mut h : Sha512 = Sha512::default();
laissez mut hacher : [u8 ; 64] = [0u8 ; 64] ;
laissez mut plus bas : [u8; 32] = [0u8 ; 32] ;
laissez mut supérieur : [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]);
// Cette étape est pince
inférieur [0] &= 248;
inférieur [31] &= 63;
inférieur [31] |= 64 ;
ExpandedSecretKey{ key : Scalar ::from_bits(inférieur), nonce : supérieur, }
}
Mise en œuvre du signe
Ici, vous pouvez mentionner la technique Fiat Shamir mentionnée précédemment, en fait, il vous suffit de remplacer tous les nombres aléatoires fournis par Verifier par le résultat d'une fonction de hachage. Voir les commentaires du code pour plus de détails.
signe pub fn (&self, message : & [u8] , public_key : &PublicKey) -> ed25519::Signature {
soit mut h : Sha512 = Sha512::new();
Soit R : CompressedEdwardsY ;
soit r : Scalaire ;
soit s : Scalaire ;
soit k : scalaire ;
h.update(&self.nonce);
h.update(&message);
r = Scalar::from_hash(h); // r est un nombre aléatoire dans notre algorithme interactif, mais ici nous utilisons un hachage.
R = (&r * &constantes::ED25519_BASEPOINT_TABLE).compress(); // R = [r] B
h = Sha512::nouveau();
h.update(R.as_bytes());
h.update(public_key.as_bytes());
h.update(&message);
k = Scalaire ::from_hash(h); // h = Sha512(R || A || M)
s = &(&k * &self.key) + &r; // s = r + h * a, h est à l'origine un nombre aléatoire
SignatureInterne { R, s }.into()
}
Implémentation de Vérifier
impl Vérificateur pour CléPublique {
#[allow(non_snake_case)]
fn vérifier(
&soi,
message: & [u8] ,
signature: &ed25519::Signature
) -> Résultat<(), SignatureError>
{
let signature = InternalSignature::try_from(signature) ? ;
soit mut h : Sha512 = Sha512::new();
Soit R : EdwardsPoint ;
soit k : scalaire ;
soit moins_A : EdwardsPoint = -self.1 ;
h.update(signature.R.as_bytes());
h.update(self.as_bytes());
h.update(&message);
k = Scalar::from_hash(h); // Le calcul de h est le même que dans le signe, h=Sha512(R||A||M)
R = EdwardsPoint::time_double_scalar_mul_basepoint(&k, &(moins_A), &signature.s); // R' = [s] B- [h] UN
if R.compress() == signature.R { // Si R'==R, alors le résultat de la vérification est vrai.
D'accord(())
} autre {
Err(InternalError::VerifyError.into())
}
}
}
code adresse (
Problèmes d'évolutivité
Il y a de nombreux endroits auxquels il faut prêter attention dans la mise en œuvre et l'utilisation des algorithmes cryptographiques. Lorsque nous disons qu'un algorithme de signature numérique est sécurisé, cela signifie généralement que même si l'attaquant peut obtenir la signature de n'importe quel message (Chosen Message Attack), l'attaquant ne peut toujours pas falsifier la signature. Ed25519 satisfait cette propriété, mais cela ne signifie pas que Ed25519 est absolument sûr. Il est également mentionné dans l'article d'origine que le problème d'évolutivité est acceptable, et l'algorithme d'origine a ce problème.
De cette manière, à la fois la signature nouvellement construite et l'ancienne signature peuvent être vérifiées avec succès. Le problème de malléabilité nous indique que la signature n'est pas déterministe par rapport au message et à la clé publique. Lorsque l'algorithme de signature a un problème de malléabilité et que le code suppose que la signature est déterministe, il y a probablement des failles.
Selon la norme (en fait, il n'y a pas de problème d'évolutivité. Parce que dans le processus de vérification, nous vérifierons s'il est inférieur à, si le résultat de la vérification n'est pas vrai, la vérification échoue. Mais la norme (apparaît plus tard que le papier (Ainsi, dans l'environnement réel, il existe encore des implémentations d'Ed25519 qui ont des problèmes d'évolutivité et nécessitent des implémentations que nous examinons.
Résumer
Merci
*Merci à Safeheron, l'un des principaux fournisseurs de services d'auto-conservation d'actifs numériques, pour ses conseils techniques professionnels. *
> Références
> [1] .
> [2] .
> [3] .
> [4] .
> [5] . Des chercheurs utilisent la théorie des groupes pour accélérer les algorithmes — Introduction aux groupes