Pebble Coding

プログラマーの作業メモ

楕円曲線暗号

ECDSA(楕円曲線デジタル署名アルゴリズム)の概要

ECDSA(Elliptic Curve Digital Signature Algorithm)の概要です。 要点だけをまとめ、異例のチェックや楕円曲線上の点であるかどうかなどの細かな点は省きます。 正確な仕様は以下です。 AMERICAN NATIONAL STANDARD X9.62-1998 Public Key Cryptography For…

素体Fp上の楕円曲線 y^2 = x^3 + D の有理点の数

の素体上の有理点の数を調べます。 楕円曲線Eの有理点の数を#Eと書きます。 素数pを3で割って2余る場合は、有理点の数は無限遠点を含み、#E= p + 1 であることが知られています。 の場合の、有理点の数をpythonで調べた結果がこちらです。 p, p mod 3, #E 2,…

楕円関数の加法公式

楕円関数 の形式の加法公式をメモしておきます。 アフィン座標での加算公式 1) PとQが同一点の場合。 2) の場合 これをアフィン座標(affine coordinate)と呼びます。 素体 上の割り算は掛け算に比べて10倍〜50倍くらいの計算量なので、 割り算の回数を減らす…

楕円曲線上の離散対数問題(ECDLP)

一つ前の記事 python で有限体Fpでの楕円曲線上の有理点の群構造を調べる - Pebble Coding で有限体での楕円曲線の群構造をpythonを使って実験的に調べました。 分かったことは、 - 群の位数=群の元の個数=有理点の個数(無限遠点を含む)である。 - 群の位数…

楕円曲線暗号 情報リンクまとめ

ECDSA ( Elliptic Curve Digital Signature Algorithm )のWiki(日本語) 楕円曲線DSA - Wikipedia ECDSA のWiki(英語) Elliptic Curve Digital Signature Algorithm - Wikipedia EdDSA ( Edwards-Curve Digital Signature Algorithm ) のWiki EdDSA - Wikiped…

楕円曲線の形

楕円曲線の一般的な形は以下のように表せます。 暗号理論に用いる楕円曲線は特異でない形のものだけを扱います。 特異でない形のものは2つのパターンに分けられます。 1) yが0の時のxの値が3つある場合 2) yが0の時のxの値が1つだけしかない場合 それぞれ…

離散対数問題(Discrete Logarithm Problem)とは

RSA暗号の安全性が大きな数の因数分解の計算量の多さに元にしているのと同様、 楕円関数暗号の安全性は大きな数の離散対数の計算量の多さを元にしています。 離散対数問題をここで解説してみます。 p : 素数 これは説明不要ですね。 2,3,5,7,11,…のように自…