暗号
ECDSA署名とECSchnorr署名の概略メモです。 群や体の演算など、些細な部分は省略し、核となるロジックだけを記載しています。 楕円曲線上の点は大文字、スカラー値は小文字で表現します。 点Aのx,y座標はと表現します。 ECDSA署名 <共有情報> G:ベースポイン…
楕円曲線の点の２倍公式を楕円曲線を簡単にして計算してみよう。 楕円関数の加法公式 - Pebble Coding で計算を簡単にするためa=0とする。2倍公式を得るにはP=Qとすれば良い。 すると、 が得られる。 3倍公式、4倍公式を求めていくと、xの有理式の次数が上が…
上の楕円曲線 の有理点個数の求め方です。 ここではSchoofアルゴリズムの理解を目的とし、少しづつ理解を進めます。 まず使うのはHasseの定理です。 Hasse-Weilの定理(楕円関数限定版) - Pebble Coding 有理点の数を#Eで表すと、 が成り立つのでaを求めれば…
DLP問題を解くアルゴリズムの一つとしてBabyStep GiantStep法があります。 www.pebblewind.com DLP問題とは、対称群の位数nに対して、生成元をg、群のある元をaとして、 を満たすxを求める問題です。 ここで、解はただ一つのみ必ず存在することは前提としま…
楕円曲線に限定した Hasse の定理 上の任意の楕円曲線の有理点の個数 の範囲は以下となる。 補題 楕円曲線 E () に含まれる点Pで、 となる m が Hasse の定理により定まる曲線の位数の区間 に唯一存在する時、 となる。 この補題は Hasse の定理から導かれま…
256bit(=32バイト)の暗号化はどの程度強固なのかというのを説明したYouTubeの動画が面白かったのでリンクを貼っておきます。 www.youtube.com 内容としては、まず、8つの大きさに分解します。 それぞれ、M1, M2, M3, ..., M8と表すことにします。 そして、 …
一つ前の記事では署名のリカバリーIDについて書きました。 Ethereum の署名とBitcoin の署名 - Pebble Coding が、いまいち分からんと思うので、実感するため、小さい例で考えてみます。 曲線はsecp256k1と同じ、 を使いますが、法素数は31=pを使います。 こ…
ECDSA(Elliptic Curve Digital Signature Algorithm)の概要です。 要点だけをまとめ、異例のチェックや楕円曲線上の点であるかどうかなどの細かな点は省きます。 正確な仕様は以下です。 AMERICAN NATIONAL STANDARD X9.62-1998 Public Key Cryptography For…
の素体上の有理点の数を調べます。 楕円曲線Eの有理点の数を#Eと書きます。 素数pを3で割って2余る場合は、有理点の数は無限遠点を含み、#E= p + 1 であることが知られています。 の場合の、有理点の数をpythonで調べた結果がこちらです。 p, p mod 3, #E 2,…
楕円関数 の形式の加法公式をメモしておきます。 アフィン座標での加算公式 1) PとQが同一点の場合。 2) の場合 これをアフィン座標(affine coordinate)と呼びます。 素体 上の割り算は掛け算に比べて10倍〜50倍くらいの計算量なので、 割り算の回数を減らす…
一つ前の記事 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…
前回 RSA暗号化方式を紐解く その(1) - Pebble Coding からの続きです。 暗号化は の式によって行い、 復号化は の式によって行います。 これがうまく動作する仕組みを知るにはどうやってe, d, nを選ぶかということを知る必要があります。 理論の根幹をなす…
感覚をつかむため、まずは実際の数値での例を見てみましょう。 RSAの秘密鍵、公開鍵のペアを16bitの長さで生成してみました。 16bitを指定するとmodulusの大きさが16bitになります。 modulus:29353 秘密鍵 exponentE:65537 秘密鍵(通常65537固定なのであまり…
RSA暗号に関する文章を読んでいてもその数学的な原理がさっぱり理解できなかったのですが、 色々読んでいるうちになんとなく分かってきましたので、メモしておきます。 まずモジュラー演算記号(mod)を覚えましょう。 これは整数aを整数nで割った余りとbを整…
楕円曲線の一般的な形は以下のように表せます。 暗号理論に用いる楕円曲線は特異でない形のものだけを扱います。 特異でない形のものは２つのパターンに分けられます。 1) yが0の時のxの値が３つある場合 2) yが0の時のxの値が１つだけしかない場合 それぞれ…
RSA暗号の安全性が大きな数の因数分解の計算量の多さに元にしているのと同様、 楕円関数暗号の安全性は大きな数の離散対数の計算量の多さを元にしています。 離散対数問題(DLP)をここで解説してみます。 p : 素数 これは説明不要ですね。 2,3,5,7,11,...のよ…
iOSでRSAを使ってメッセージを暗号化してみます。 SwiftRSA https://github.com/TakeScoop/SwiftyRSA というライブラリを利用します。 RSAの実装は、AppleのSecurity.Frameworkが利用されています。 macOS版はサポートされていないようです。 サンプルiOSア…
