> この記事では、楕円曲線ベースの電子署名アルゴリズム Ed25519 の実装原理と拡張性を紹介します。**作者: アー・ウェイ**Ed25519 は、効率的で安全で広く使用されている楕円曲線に基づくデジタル署名アルゴリズムです。 TLS 1.3、SSH、Tor、ZCash、WhatsApp、Signal で使用されます。この記事では主に次の点について説明します。1. 群理論の知識を少し紹介します。目的は、誰もが Ed25519 の原理とそのスケーラビリティ問題について直感的に理解できるようにすることです。より深く理解するには、他の資料を参照する必要があります。2. Rust ライブラリ ed25519-dalek のバージョン 1.0.1 の ed25519 の実装について説明します。3. ライブラリの拡張性について説明します。## 数学の必需品のレビュー### **グループの定義とプロパティ**群理論は抽象代数の研究の内容ですが、抽象代数のいくつかの考え方はプログラマにとって非常によく知られています。オブジェクト指向における継承がその良い例であり、サブクラスが親クラスを継承すると、親クラスで定義されたメソッドを使用できることは誰もが知っています。抽象代数は、抽象データ構造のいくつかのプロパティを定義するものとして理解でき、これらのプロパティから導出される定理はすべてのサブクラスに当てはまります。先ほどの比喩を使用して、グループのデータ構造がどのように定義されるかを見てみましょう。グループは、次のプロパティを満たす操作 (任意の二項演算で示される) といくつかの要素で構成されます。ここから、多くの興味深い定理を導き出すことができます。いくつかの例を挙げると、次のようになります。* 整数 ...、−2、−1、0、1、2、…、および加算は、上記の 4 つの性質を満たすため、グループになります。※整数と乗算は可逆性、4×1/4=1を満たさないため群ではありませんが、1/4は整数ではありません### **群理論の用語の省略**### **ラグランジュ定理**ここで、非常に興味深い定理を紹介します。この定理の導出は、記事の最後に引用されているビデオにあります。** 「グループの順序はサブグループの順序で割り切れます。」**この定理がなぜ興味深いかというと、その証明プロセスが今紹介した多くの知識と結びついているからだけでなく、次の結論があるからでもあります。**「群の次数が素数の場合、ラグランジュの定理によれば、部分群の次数は or でなければなりません。群内のすべての要素は、次を除く生成子です。## Ed25519 の実装ここで、EdDSA アルゴリズムの 1 つである Ed25519 について説明します。 EdDSA には 11 個のパラメータがあります (これらのパラメータの特定の選択は、アルゴリズムのセキュリティとパフォーマンスに大きな影響を与えます。Ed25519 の特定の選択については、リンク (さらに、このアルゴリズムでは Curve25519 (. 楕円曲線については、その上に非常に多くの点があり、これらの点を追加すると新しい点が得られることを知っていれば十分です。新しい点はまだ曲線上にあります。これらの点とこの加算によりグループを形成できます。楕円曲線の加算 (特別に定義されている) に注意してください。私たちは次の表記に同意します。これは対話型アルゴリズムですが、問題ではありません。Fiat - Shamir ヒューリスティックと呼ばれるトリックがあります (対話型アルゴリズムを非対話型アルゴリズムに変換できます。最終的には非対話型アルゴリズムを使用します)。デジタル署名アルゴリズムにより、次の API が提供されます。### **KeyGen の実装**秘密鍵と公開鍵を出力します。1. シードをランダムに生成します (このシードは 32 バイトです。システムに付属する暗号的に安全な乱数生成器を使用します。pub fn 生成<T>(csprng: &mut T) -> SecretKeywhereT：CryptoRng + RngCore、{let mut sk: SecretKey = SecretKey([0u8; 32]);csprng.fill\_bytes(&mut sk.0);スク}2. 先ほどのシードを 64 バイトに拡張します (つまり、図の xseed です。xseed の下位 32 バイトは秘密キー (別名 a) です。上位 32 バイトは nonce と呼ばれ、後で使用されます。その機能はドメインスペレーターと似ています。pub struct ExpandedSecretKey { // xseed pub(crate) キー: スカラー, // apub(crate) nonce: [u8; 32], // ノンス}fn from(secret\_key: &'a SecretKey) -> ExpandedSecretKey {let mut h: Sha512 = Sha512::default();mut ハッシュにします: [u8; 64] = [0u8; 64];mut を低くしましょう: [u8; 32] = [0u8; 32];mut を上位にします: [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]);// このステップはクランプです低い [0] &= 248;低い [31] &= 63;低い [31] |= 64;ExpandedSecretKey{ キー: スカラー::from\_bits(下位)、ノンス: 上位、}}3. 秘密鍵を使用して公開鍵を生成します (公開鍵は楕円曲線上の点です。具体的には、楕円曲線の基点を使用して楕円曲線乗算を実行し、公開鍵を取得します。乗算のスカラー秘密キーをペアリングすることで取得されます。ハッシュを実行して取得します。pub struct ExpandedSecretKey { // xseed pub(crate) キー: スカラー, // apub(crate) nonce: [u8; 32], // ノンス}fn from(secret\_key: &'a SecretKey) -> ExpandedSecretKey {let mut h: Sha512 = Sha512::default();mut ハッシュにします: [u8; 64] = [0u8; 64];mut を低くしましょう: [u8; 32] = [0u8; 32];mut を上位にします: [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]);// このステップはクランプです低い [0] &= 248;低い [31] &= 63;低い [31] |= 64;ExpandedSecretKey{ キー: スカラー::from\_bits(下位)、ノンス: 上位、}}### サインの実装ここで、前述の Fiat Shamir 手法について言及できますが、実際には、Verifier によって提供されたすべての乱数をハッシュ関数の結果に置き換えるだけで済みます。詳細については、コードのコメントを参照してください。pub fn signed(&self, メッセージ: & [u8] 、 public\_key: &PublicKey) -> ed25519::Signature {let mut h: Sha512 = Sha512::new();R: CompressedEdwardsY とします。r: スカラーとします。let s: スカラー;k: スカラーとする。h.update(&self.nonce);h.update(&メッセージ);r = Scalar::from\_hash(h); // r は対話型アルゴリズムでは乱数ですが、ここではハッシュを使用します。R = (&r \* &constants::ED25519\_BASEPOINT\_TABLE).compress(); // R = [r] Bh = Sha512::new();h.update(R.as\_bytes());h.update(public\_key.as\_bytes());h.update(&メッセージ);k = スカラー::from\_hash(h); // h = Sha512(R || A || M)s = &(&k \* &self.key) + &r; // s = r + h \* a, h は元々乱数InternalSignature { R, s }.into()}### ベリファイの実装impl 検証者<ed25519::Signature>公開鍵の場合 {#[許可(非\_ヘビ\_ケース)]fn 検証(＆自己、メッセージ： ＆ [u8] 、署名: &ed25519::署名) -> 結果<()、署名エラー>{署名 = InternalSignature::try\_from(signature)?; にします。let mut h: Sha512 = Sha512::new();R: エドワーズポイントとしましょう。k: スカラーとする。let minus\_A: EdwardsPoint = -self.1;h.update(signature.R.as\_bytes());h.update(self.as\_bytes());h.update(&メッセージ);k = Scalar::from\_hash(h); // h の計算は符号の場合と同じです、h=Sha512(R||A||M)R = EdwardsPoint::time\_double\_scalar\_mul\_basepoint(&k, &(minus\_A), &signature.s); // R' = [s] B - [h] あif R.compress() ==signature.R { // R'==R の場合、検証結果は true です。Ok（（））} それ以外 {Err(内部エラー::VerifyError.into())}}}*コードアドレス(*## スケーラビリティの問題暗号アルゴリズムの実装と使用には注意すべき点が数多くあります。デジタル署名アルゴリズムが安全であると言うとき、それは一般に、攻撃者が任意のメッセージの署名を取得できたとしても (Chosen Message Attack)、攻撃者は署名を偽造できないことを意味します。 Ed25519 はこの特性を満たしていますが、Ed25519 が絶対に安全であることを意味するものではありません。元の論文でもスケーラビリティの問題は許容されると述べられていますが、元のアルゴリズムにはこの問題があります。このようにして、新しく構築された署名と古い署名の両方を正常に検証できます。展性の問題は、署名がメッセージと公開鍵に対して決定的ではないことを示しています。署名アルゴリズムに展性の問題があり、コードが署名が決定的であると想定している場合、抜け穴が存在する可能性があります。規格によると（実際にはスケーラビリティに問題はありません。検証の過程で以下かどうかをチェックするので、チェック結果が真でない場合は検証は失敗します。ただし、規格（論文よりも後に出てきます） (そのため、実際の環境では、スケーラビリティの問題があり、調査する実装が必要な Ed25519 の実装がまだ存在します。# **要約*****ありがとう****専門的な技術アドバイスを提供してくださった、大手ワンストップデジタル資産セルフカストディサービスプロバイダーである Safeheron に感謝します。 *> **参考資料**> [1] 。> [2] 。> [3] 。> [4] 。> [5] 。研究者は群理論を使用してアルゴリズムを高速化 — 群の紹介
Ed25519 の実装原理とスケーラビリティについて説明する
> この記事では、楕円曲線ベースの電子署名アルゴリズム Ed25519 の実装原理と拡張性を紹介します。
作者: アー・ウェイ
Ed25519 は、効率的で安全で広く使用されている楕円曲線に基づくデジタル署名アルゴリズムです。 TLS 1.3、SSH、Tor、ZCash、WhatsApp、Signal で使用されます。この記事では主に次の点について説明します。
数学の必需品のレビュー
グループの定義とプロパティ
群理論は抽象代数の研究の内容ですが、抽象代数のいくつかの考え方はプログラマにとって非常によく知られています。オブジェクト指向における継承がその良い例であり、サブクラスが親クラスを継承すると、親クラスで定義されたメソッドを使用できることは誰もが知っています。抽象代数は、抽象データ構造のいくつかのプロパティを定義するものとして理解でき、これらのプロパティから導出される定理はすべてのサブクラスに当てはまります。
先ほどの比喩を使用して、グループのデータ構造がどのように定義されるかを見てみましょう。
グループは、次のプロパティを満たす操作 (任意の二項演算で示される) といくつかの要素で構成されます。
ここから、多くの興味深い定理を導き出すことができます。
いくつかの例を挙げると、次のようになります。
群理論の用語の省略
ラグランジュ定理
ここで、非常に興味深い定理を紹介します。この定理の導出は、記事の最後に引用されているビデオにあります。
** 「グループの順序はサブグループの順序で割り切れます。」**
この定理がなぜ興味深いかというと、その証明プロセスが今紹介した多くの知識と結びついているからだけでなく、次の結論があるからでもあります。
**「群の次数が素数の場合、ラグランジュの定理によれば、部分群の次数は or でなければなりません。群内のすべての要素は、次を除く生成子です。
Ed25519 の実装
ここで、EdDSA アルゴリズムの 1 つである Ed25519 について説明します。 EdDSA には 11 個のパラメータがあります (これらのパラメータの特定の選択は、アルゴリズムのセキュリティとパフォーマンスに大きな影響を与えます。Ed25519 の特定の選択については、リンク (
さらに、このアルゴリズムでは Curve25519 (. 楕円曲線については、その上に非常に多くの点があり、これらの点を追加すると新しい点が得られることを知っていれば十分です。新しい点はまだ曲線上にあります。これらの点とこの加算によりグループを形成できます。楕円曲線の加算 (特別に定義されている) に注意してください。
私たちは次の表記に同意します。
これは対話型アルゴリズムですが、問題ではありません。Fiat - Shamir ヒューリスティックと呼ばれるトリックがあります (対話型アルゴリズムを非対話型アルゴリズムに変換できます。最終的には非対話型アルゴリズムを使用します)。
デジタル署名アルゴリズムにより、次の API が提供されます。
KeyGen の実装
秘密鍵と公開鍵を出力します。
pub fn 生成(csprng: &mut T) -> SecretKeywhere
T：CryptoRng + RngCore、
{
let mut sk: SecretKey = SecretKey([0u8; 32]);
csprng.fill_bytes(&mut sk.0);
スク
}
pub struct ExpandedSecretKey { // xseed pub(crate) キー: スカラー, // a
pub(crate) nonce: [u8; 32], // ノンス
}
fn from(secret_key: &'a SecretKey) -> ExpandedSecretKey {
let mut h: Sha512 = Sha512::default();
mut ハッシュにします: [u8; 64] = [0u8; 64];
mut を低くしましょう: [u8; 32] = [0u8; 32];
mut を上位にします: [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]);
// このステップはクランプです
低い [0] &= 248;
低い [31] &= 63;
低い [31] |= 64;
ExpandedSecretKey{ キー: スカラー::from_bits(下位)、ノンス: 上位、}
}
pub struct ExpandedSecretKey { // xseed pub(crate) キー: スカラー, // a
pub(crate) nonce: [u8; 32], // ノンス
}
fn from(secret_key: &'a SecretKey) -> ExpandedSecretKey {
let mut h: Sha512 = Sha512::default();
mut ハッシュにします: [u8; 64] = [0u8; 64];
mut を低くしましょう: [u8; 32] = [0u8; 32];
mut を上位にします: [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]);
// このステップはクランプです
低い [0] &= 248;
低い [31] &= 63;
低い [31] |= 64;
ExpandedSecretKey{ キー: スカラー::from_bits(下位)、ノンス: 上位、}
}
サインの実装
ここで、前述の Fiat Shamir 手法について言及できますが、実際には、Verifier によって提供されたすべての乱数をハッシュ関数の結果に置き換えるだけで済みます。詳細については、コードのコメントを参照してください。
pub fn signed(&self, メッセージ: & [u8] 、 public_key: &PublicKey) -> ed25519::Signature {
let mut h: Sha512 = Sha512::new();
R: CompressedEdwardsY とします。
r: スカラーとします。
let s: スカラー;
k: スカラーとする。
h.update(&self.nonce);
h.update(&メッセージ);
r = Scalar::from_hash(h); // r は対話型アルゴリズムでは乱数ですが、ここではハッシュを使用します。
R = (&r * &constants::ED25519_BASEPOINT_TABLE).compress(); // R = [r] B
h = Sha512::new();
h.update(R.as_bytes());
h.update(public_key.as_bytes());
h.update(&メッセージ);
k = スカラー::from_hash(h); // h = Sha512(R || A || M)
s = &(&k * &self.key) + &r; // s = r + h * a, h は元々乱数
InternalSignature { R, s }.into()
}
ベリファイの実装
impl 検証者公開鍵の場合 {
#[許可(非_ヘビ_ケース)]
fn 検証(
＆自己、
メッセージ： ＆ [u8] 、
署名: &ed25519::署名
) -> 結果<()、署名エラー>
{
署名 = InternalSignature::try_from(signature)?; にします。
let mut h: Sha512 = Sha512::new();
R: エドワーズポイントとしましょう。
k: スカラーとする。
let minus_A: EdwardsPoint = -self.1;
h.update(signature.R.as_bytes());
h.update(self.as_bytes());
h.update(&メッセージ);
k = Scalar::from_hash(h); // h の計算は符号の場合と同じです、h=Sha512(R||A||M)
R = EdwardsPoint::time_double_scalar_mul_basepoint(&k, &(minus_A), &signature.s); // R' = [s] B - [h] あ
if R.compress() ==signature.R { // R'==R の場合、検証結果は true です。
Ok（（））
} それ以外 {
Err(内部エラー::VerifyError.into())
}
}
}
コードアドレス(
スケーラビリティの問題
暗号アルゴリズムの実装と使用には注意すべき点が数多くあります。デジタル署名アルゴリズムが安全であると言うとき、それは一般に、攻撃者が任意のメッセージの署名を取得できたとしても (Chosen Message Attack)、攻撃者は署名を偽造できないことを意味します。 Ed25519 はこの特性を満たしていますが、Ed25519 が絶対に安全であることを意味するものではありません。元の論文でもスケーラビリティの問題は許容されると述べられていますが、元のアルゴリズムにはこの問題があります。
このようにして、新しく構築された署名と古い署名の両方を正常に検証できます。展性の問題は、署名がメッセージと公開鍵に対して決定的ではないことを示しています。署名アルゴリズムに展性の問題があり、コードが署名が決定的であると想定している場合、抜け穴が存在する可能性があります。
規格によると（実際にはスケーラビリティに問題はありません。検証の過程で以下かどうかをチェックするので、チェック結果が真でない場合は検証は失敗します。ただし、規格（論文よりも後に出てきます） (そのため、実際の環境では、スケーラビリティの問題があり、調査する実装が必要な Ed25519 の実装がまだ存在します。
要約
ありがとう
*専門的な技術アドバイスを提供してくださった、大手ワンストップデジタル資産セルフカストディサービスプロバイダーである Safeheron に感謝します。 *
> 参考資料
> [1] 。
> [2] 。
> [3] 。
> [4] 。
> [5] 。研究者は群理論を使用してアルゴリズムを高速化 — 群の紹介