This page may contain third-party content, which is provided for information purposes only (not representations/warranties) and should not be considered as an endorsement of its views by Gate, nor as financial or professional advice. See Disclaimer for details.
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 検証者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 に感謝します。 *