EdDSA署名アルゴリズム
秘密鍵と公開鍵を直接使用できるRSAとは異なり、ここでは、より複雑なスキームを使用して、追加のオブジェクトを入力する必要があります。 EdDSAは概念的にDSAアルゴリズムを実装し、曲線の場合に拡張します。 署名は数字のペア（R、S）です。EdDSAの場合、それぞれの長さは32バイトで、署名の長さの合計は64バイトです。 データ自体は署名されていませんが、そのハッシュです。 ハッシュ関数として、SHA512が使用されます。 次に、小さな文字は数字を示し、大文字では数字に基点Bを掛けることで得られる曲線上の対応する点を示します。
hを署名するメッセージのハッシュ、aを秘密鍵、Aを対応する公開鍵（A = a * B）とします。 乱数rを取得し、R = r * Bおよびs = r + h * aを計算します。 ペア（R、s）は署名になり、Rはy座標で表されます。
署名を検証するとき、受信者はAとhを知っているため、（R、s）の真実を検証する必要があります。 これを行うには、等式を確認します。s* B = R + h * A
確かに（r + h * a）* B = r * B + h * a * B = R + h * A
sは、生成されたポイントではなく、秘密鍵に基づいて直接計算されることに注意してください。これは、実装のエラーが即座に危険にさらされる可能性があるためです。 特に、rの選択の失敗。 これを回避するために、バーンスタインは、署名されたデータ自体と組み合わされた秘密鍵のハッシュの半分からハッシュとしてrを計算することを提案しますが、他の方法でrを選択してもアルゴリズムに干渉しません。つまり、署名値自体は異なりますが、検証の結果は同じになります バーンスタインが示唆するようにrを計算し、公式のI2Pでどのように行われるかを計算します。
効果的な乗算の実装
さらに計算するために、以前に使用されていない曲線パラメーターl =
l * B = 0など。
この等式からすぐに、ポイントの前にあるファクターの値がlを超えてはならないことがわかります。そうしないと、計算量が増加するだけです。 係数がlを超える場合、特に、hの値（64バイトのSHA512ハッシュ）を法とする必要があります。
これから、乗算演算の乗数は32バイトを超えず、最上位ビットは常にゼロになります。
式からわかるように、署名には1つの基点による乗算が必要であり、署名を検証するには、2つが1つは基点によるもので、もう1つは公開キーによるものです。
基点については、事前にさまざまな係数を乗算した結果を計算することは理にかなっています。 最も単純なのは、255ポイントのみのシリーズ（B、2 * B、4 * B、8 * B、...）であり、各ステップでの倍増操作を排除できます。 さらに進んで、2の累乗ではなく16の累乗で係数を展開し、係数の4ビットごとに計算されたポイントを配列から結果に追加できます。 これを行うには、32 * 2 * 16ポイントを計算して保存する必要がありますが、これは作業中に1回行われます。 したがって、Bの乗算は正確に64の加算に減少し、メッセージは迅速に署名されます。 これは、コードでどのように見えるかです。
EDDSAPoint res {zero, one}; for (int i = 0; i < 32; i++) { uint8_t x = e[i] & 0x0F; // 4 low bits if (x > 0) res = Sum (res, Bi16[i*2][x-1], ctx); x = e[i] >> 4; // 4 high bits if (x > 0) res = Sum (res, Bi16[i*2+1][x-1], ctx); }
ここで、Bi16は64x16ポイントの配列で、 eはリトルエンディアンの32バイトの乗数です。 16の累乗の代わりに、256の累乗の拡張を使用できます。これにより、ある程度の加速が得られると同時に、32 * 256ポイントを既に保存する必要があります。
署名を検証するには、公開鍵も乗算する必要があります。これはBを乗算した結果ですが、これは秘密鍵であるため、乗数はわかりません。 このメソッドを適用する場合、それらのそれぞれにそのような配列を保持する必要があり、I2Pには多くの公開キーがあります-netdbから各ノードに個別のキーがあり、その中には数千があり、不当なメモリ消費につながります。 したがって、他の楕円曲線に匹敵する作業速度を達成するには、加算操作を改善する必要があります。
同次座標での加算
前の記事で述べたように、最も遅い操作は加算ごとの除算です。これは、均一な座標に移動することで取り除くことができます。 実装はそれほど明白ではありませんが、楕円暗号のすべての実装はそこに配置されます。 点の2つの座標（x、y）の代わりに、共通分母を格納する3番目の座標が入力され、xおよびyの代わりにそれらの分子が格納されます。つまり、同次座標（X、Y、Z）から、真の座標は（X / Z、Y / Z ） さらに、4番目の座標T = X * Y / Zが入力されます。 加算結果の座標は、次の式で計算されます。
X =（X1 * Y2 + Y1 * X2）*（Z1 * Z2-d * T1 * T2）
Y =（Y1 * Y2 + X1 * X2）*（Z1 * Z2 + d * T1 * T2）
Z =（Z1 * Z2-d * T1 * T2）*（Z1 * Z2 + d * T1 * T2）
T =（Y1 * Y2 + X1 * X2）*（X1 * Y2 + Y1 * X2）
ご覧のとおり、加算と乗算の過程で時間をかけて累乗する操作は適用されなくなりました。
同種座標のもう1つの欠点は、2点を比較する複雑さです。X座標とY座標を直接比較することはできません。何らかの方法で共通の分母に持ってくる必要があり、追加の計算が必要です。 署名を検証するには、ポイントを比較する必要があります。
2つの曲線点の減算
署名s * B = R + h * Aを検証するための式を、R = s * Bh * Aの形式に書き換えます。
次に、署名のY座標からポイントのX座標を復元する代わりに、（s * Bh * A）からY座標を取得して、別のべき乗を保存し、ポイントの代わりに数値を比較できます。 この方法では、減算演算が必要です。これは、（-X、Y、Z、-T）として定義される加算と単項マイナスにより実装されます。 したがって、減算操作は加算と同じ速度で実行され、負の係数を使用した度数の拡張に使用でき、メモリサイズが2倍に削減されます。
EdDSAを使用したI2Pアドレス
EdDSAを使用したI2Pアドレスの長さは391バイトで、署名タイプコードは7です。これは、ドキュメントではEdDSA_SHA512_Ed25519として示されています。
秘密鍵と公開鍵の長さは32バイト、署名の長さは64バイト、最初の32バイトはy座標の形式のR、2番目の32バイトはsです。
すべての番号はリトルエンディアンに転送されます。
現在、EdDSAはRouterInfoの推奨署名タイプです。
したがって、2つの記事では、opensslライブラリの多数のコードを高速で処理し 、 i2pdで実際に使用するための、ライブラリの上のEdDSAの完全かつ透過的な実装について説明します 。