Pebble Coding

ソフトウェアエンジニアによるIT関連技術の備忘録

ed25519におけるcofactor=8

こちらの記事 ed25519のpython実装を紐解く その2 暗号編キーペア生成からベリファイまで - 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

 F_{13}
 y^{3} = x^{2} + 4 の場合で、有理点の数が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の点が渡されたとしても、攻撃者に情報を与える余地はなくなります。
ただし、EdDSAの署名においてこの攻撃が可能なのかどうかは不明です。

参考:

What is an elliptic curve cofactor? - Cryptography Stack Exchange

Why are the lower 3 bits of curve25519/ed25519 secret keys cleared during creation? - Cryptography Stack Exchange

Small subgroup confinement attack - Wikipedia

SafeCurves: Twist security