Pebble Coding

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

暗号

素体の等分点の群構造を調べる その1

楕円曲線Eにおいてとなる点Pの集まりを等分点(torsion point)と呼びます。 左辺は点をn倍することを表し、右辺は無限遠点を表します。 python で有限体Fpでの楕円曲線上の有理点の群構造を調べる - Pebble Coding 以前使ったpythonスクリプトをちょっといじ…

楕円曲線の点の2倍公式

楕円曲線の点の2倍公式を楕円曲線を簡単にして計算してみよう。 楕円関数の加法公式 - Pebble Coding で計算を簡単にするためa=0とする。2倍公式を得るにはP=Qとすれば良い。 すると、 が得られる。 3倍公式、4倍公式を求めていくと、xの有理式の次数が上が…

楕円曲線の有理点の数の求め方 schoof アルゴリズムその1

上の楕円曲線 の有理点個数の求め方です。 ここではSchoofアルゴリズムの理解を目的とし、少しづつ理解を進みます。 まず使うのはHasseの定理です。 Hasse-Weilの定理(楕円関数限定版) - Pebble Coding 有理点の数を#Eで表すと、 が成り立ちます。 tはある範…

BabyStep GiantStep法(BSGS法)

DLP問題を解くアルゴリズムの一つとしてBabyStep GiantStep法があります。 www.pebblewind.com DLP問題とは、対称群の位数nに対して、生成元をg、群のある元をaとして、 を満たすxを求める問題です。 ここで、解はただ一つのみ必ず存在することは前提としま…

Hasseの定理から導き出される補題

楕円曲線に限定した Hasse の定理 上の任意の楕円曲線の有理点の個数 の範囲は以下となる。 補題 楕円曲線 E () に含まれる点Pで、 となる m が Hasse の定理により定まる曲線の位数の区間 に唯一存在する時、 となる。 この補題は Hasse の定理から導かれま…

256bitの暗号化はどの程度強固なのか

256bit(=32バイト)の暗号化はどの程度強固なのかというのを説明したYouTubeの動画が面白かったのでリンクを貼っておきます。 www.youtube.com 内容としては、まず、8つの大きさに分解します。 それぞれ、M1, M2, M3, ..., M8と表すことにします。 そして、 …

リカバリーIDについて小さな例を用いて実感する

一つ前の記事では署名のリカバリーIDについて書きました。 Ethereum の署名とBitcoin の署名 - Pebble Coding が、いまいち分からんと思うので、実感するため、小さい例で考えてみます。 曲線はsecp256k1と同じ、 を使いますが、法素数は31=pを使います。 こ…

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…

RSA暗号化方式を紐解く その(2)

前回 RSA暗号化方式を紐解く その(1) - Pebble Coding からの続きです。 暗号化は の式によって行い、 復号化は の式によって行います。 これがうまく動作する仕組みを知るにはどうやってe, d, nを選ぶかということを知る必要があります。 理論の根幹をなす…

RSA暗号化方式を紐解く その(1)

感覚をつかむため、まずは実際の数値での例を見てみましょう。 RSAの秘密鍵、公開鍵のペアを16bitの長さで生成してみました。 16bitを指定するとmodulusの大きさが16bitになります。 modulus:29353 秘密鍵 exponentE:65537 秘密鍵(通常65537固定なのであまり…

RSA暗号の原理を理解するための数学知識

RSA暗号に関する文章を読んでいてもその数学的な原理がさっぱり理解できなかったのですが、 色々読んでいるうちになんとなく分かってきましたので、メモしておきます。 まずモジュラー演算記号(mod)を覚えましょう。 これは整数aを整数nで割った余りとbを整…

楕円曲線の形

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

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

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

iOSでRSAを使いメッセージを暗号化してみる(SwiftyRSA)

iOSでRSAを使ってメッセージを暗号化してみます。 SwiftRSA https://github.com/TakeScoop/SwiftyRSA というライブラリを利用します。 RSAの実装は、AppleのSecurity.Frameworkが利用されています。 macOS版はサポートされていないようです。 サンプルiOSア…

プライバシーポリシー

お問い合わせ

スポンサーリンク