こちらの記事 ed25519のpython実装を紐解く その２ 暗号編キーペア生成からベリファイまで - Pebble Coding
で、ed25519の署名のロジックを検証しました。
8の倍数を使う意味が分かった気がしたので、それについて書きます。
結論からいうと、small subgroup attack という攻撃を防ぐためです。
ed25519のおさらいをしておくと、有理点の数#Eは素数Lを使って8Lです。
有理点の加法は群をなしますが、この群の位数が#Eです。
群論におけるラグランジュの定理
「群 G の部分群の位数は、 G の位数の約数になる」
によって、この群の部分群の位数は、#Eの約数になるので、
2、4、8、L、2L、4L、8L(=#E)のいずれかになります。
また、「群 G の元の位数は、群 G の位数の約数になる」という群の性質から、
任意の有理点の位数は2、4、8、L、2L、4L、8Lのいずれかであることが言えます。
以下の事実を抑えておきます。
「ed25519の任意の有理点を8倍した場合、その点は無限遠点であるか、そうでない場合は、その点の位数はLである。」
この事実により、有理点を8倍しておけば、その位数がLであることが保証されます。
この定理の証明はラグランジュの定理だけを使ってできます。
具体例を上げます。
こちらの記事の最後の例を使います。
python で有限体Fpでの楕円曲線上の有理点の群構造を調べる - Pebble Coding
の場合で、有理点の数が21、
位数3の点がP1, P2の2つ(無限遠点Oを加えて3つの元が部分群を成します)、
位数7の点がP11, P12, P13, P14, P17, P18 の6つ(無限遠点Oを加えて7つの元が部分群を成します)、
位数21の点がP3, P4, P5, P6, P7, P8, P9, P10, P15, P16, P19, P20 の12個、
あります。
位数3の点は3倍すると、Oになっていることが分かります。
位数7の点は部分群を成しているので、3倍しても、位数7の点のままであることが分かります。
位数21の点は3倍すると、位数7の点になっていることが分かります。
参考リンクにはDH鍵交換の場合のアタック方法が書いてありますが、使用する公開鍵を8の倍数にしておけば、
位数8の点が渡されたとしても、攻撃者に情報を与える余地はなくなります。
参考:
What is an elliptic curve cofactor? - Cryptography Stack Exchange
