Pebble Coding

プログラマーの作業メモ

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

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

python で有限体Fpでの楕円曲線上の有理点の群構造を調べる

ここでは、有限体 (p=5) 楕円曲線 (a=0,b=1,c=1) の有理点をpythonで調べています。 有理点の数は9です。(無限遠点を含む) 無限遠点はOと出力しています。 加法公式を用いて、有理点{P1, P1, ... P8}を2倍,3倍,...,9倍した点も示しています。 この計算の途中…

macOS 10.12 jupyer notebook でグラフを描画する(Fpにおける楕円曲線の解の個数)

matplotlibをインストールします。 ~$ pip install matplotlib %matplotlib inline import numpy as np import matplotlib.pyplot as plt # 乱数を生成 x = np.random.rand(100) y = np.random.rand(100) # 散布図を描画 plt.scatter(x, y) plt.show() うま…

B-smooth と B-power-smooth

B-smooth と B-power-smooth の概念を押さえておきます。 B-smooth 任意の自然数Nを素因数に分解すると次の形になります。 ここで、はk番目の素数 {2, 3, 5, 7, 11, …}を表します。 は0以上の整数です。 ここで最も大きい素数として、 NをB-smoothであるとい…

ポラードのp-1因数分解法

大きな合成数を素因数分解(factorization in prime numbers)するアルゴリズムの一つにポラードのp-1法があります。 ポラードの法とは別モノなので混同しないようにしましょう。 因数分解したい合成数をnとします。 合成数nが のように分解される時、素数pを…

体の標数(characteristic)

体Kにおいて、n個の1の和 1+1+…+1 が0となるような整数が存在するとき、その最小値を体Kの標数といい、ch(K)と表します。 いくつ加えても0にならない時は標数が0と定めます。 標数は0か素数です。 有理数体Qの標数は0です。 有限体の標数はpです。

体の拡大

拡大体 体とは大雑把に言って、加法と乗法に対して演算が閉じている数の集合のことを指します。 有理数Q, 実数体R, 複素数体Cは全て加法と乗法において演算が閉じているので体と呼べます。 これらは数の集合としては数の存在の密度が高すぎますね。 整数Zと…

メモリ破壊系バグの潰し方 その2

前回 C/C++/ObjC メモリ破壊系バグのつぶし方 その1 - Pebble Coding の続きです。 ヒープアロケートしていない領域に書き込む 初期化していないポインタに対して、ヒープアロケートせずデータを書き込もうとしています。 #include <stdio.h> #include <string.h> typedef struc</string.h></stdio.h>…

巡回群

巡回群とはただ一つの元だけを使い、繰り返し演算することにより、全ての元を生成できる群のことである。

約数記号

整数 a が 整数 b を割り切るとき と書きます。 例: 整数 a が整数 b を割り切らないとき と書きます。 例: であるとき、b は a の倍数であり、a は b の約数であるといいます。

macOS sierra 10.12 で Jupyter Notebook を立ち上げるまで

macOS sierra 10.12 に Jupiter Notebook をインストールする。 ~$ brew install python ~$ brew link python ~$ python --version Python 2.7.10 ~$ which python /usr/bin/python ~$ ls -l /usr/bin/python -rwxr-xr-x 1 root wheel 66576 4 29 08:36 /usr…

Hasse-Weilの定理(楕円関数限定版)

Hasse-Weilの定理を楕円関数に限定した形で書くと、 Cが有限体 上定義された非特異な楕円曲線であるとき、 C上の に座標を持つ点の数をと定義すると、 不等式だが、任意の楕円曲線に関するものだというのがすごい。 これを実感するために、pをくらいの数とす…

Mordellの定理(位数2の有理点をもつ曲線の場合)

Cを で与えられる3次曲線とする。ここでa,bは整数。 このとき曲線上の有理点のなす群C(Q)は有限生成アーベル群である。 解(x,y)が無限個、有限個どちらの場合でも、有限個の元から出発し、群演算によって、全ての元を作り出せるといっている。

有限アーベル群と有限生成アーベル群

有限アーベル群と有限生成アーベル群の違いを直感的に説明する。 アーベル群の正確な定義は述べないが、一つの演算(加法や乗法と呼ぶ)が定義された数の集合としておく。 有限アーベル群とは元の数が有限であるアーベル群である。 例えば、加法として2つの整…

Nagell-Lutzの定理

Nagell-Lutzの定理 を整数係数a,b,cを持つ非特異3次曲線とする。 P=(x,y)を有限位数の有理点とする時 x,yは整数である。 これは、整数ではない有理点が存在するときは、無限位数となるということも同時に示している。 例えば、 (a=0, b=0, c=2)の場合を考え…

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

EdDSAのWiki EdDSA - Wikipedia EdDSAアルゴリズムのRFC 8032 RFC 8032 - Edwards-Curve Digital Signature Algorithm (EdDSA) Ed25519のpythonによるサンプル実装、主要論文のリンク https://ed25519.cr.yp.to/software.html SUPERCOPによる様々な暗号のC言…

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

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

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

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

ビットコイン購入までの道のり その(1)

私がビットコインを入手した経緯は2015年に Bountysource というソフトウェアを作成したり、バグを直したりして報酬を得るサイトでバグを直したことによる報酬をビットコインで受け取ったことでした。2015年当時はUS DollorとBitCoinのどちらかが選べました…

素数を高い確率で高速に判定するミラーラビン判定法

与えられた数が素数かどうかを高い確率で高速に判定するアルゴリズムとしてミラーラビン(Miller-Rabin)判定法があります。 暗号の実装で素数が必要な時にこの判定法が使われることが多いようです。 厳密に素数かどうかを判定する方法として、試行割算法(Tria…

mod pでの平方剰余を計算する(p mod 8 = 5の場合)を実装する

少し前でp mod8 = 5の場合のmod p での平方剰余の計算方法を示しました mod pでの平方剰余を計算する(p mod 8 = 5の場合) - Pebble Coding が、swiftで実装しておきます。 の解は存在すると仮定しておきます。 func quadraticResidue(_ a:Int, _ p:Int) -> I…

mod p での平方剰余を計算する(p mod 4 = 3の場合)

前回 mod pでの平方剰余を計算する(p mod 8 = 5の場合) - Pebble Coding p mod 8 = 5の時の平方剰余を計算しましたが、今回は、 p mod 4 = 3の時の平方剰余を計算してみましょう。 この場合も簡単に計算が可能です。 前回と同じように の解は存在することを…

mod pでの平方剰余を計算する(p mod 8 = 5の場合)

pをある程度限定した素数とした時の平方剰余を計算してみます。 整数論の世界では実数の世界でのルートという言葉は使わないようです。 いくつかの整数論の定理を利用しますので、事前に明示しておきます。 これらの定理は超有名なので、整数論の本に必ず載…

lets encryptでエラーが出ていたので修正

lets encrypt で https 化していたサイトがあと1ヶ月で切れますよメールがきて、どうやら自動更新に失敗していると気がつく。 /root/letsencrypt/letsencrypt-auto certonly --webroot --webroot-path /home/onsenlife/public -d onsenlife.info --renew-by…

mod p の世界では、割り算をべき乗計算に置き換えられる

フェルマーの小定理でpを素数とすると、mod pの世界では、割り算をべき乗に置き換えられます。 pを3以上の素数としておきます。 フェルマーの小定理 で、pは3以上なので、 と書けます。これは mod p においては、乗算に対して、bの逆元が であることを示して…

オイラーの φ 関数 とフェルマーの小定理

1以上の整数であるmで割った余りの値を同一とみなす演算の世界では元の数はm-1個である。 gcd(a, m) = 1である数aの総数をオイラーの関数と呼ぶ。 小さい方からどのような数なのかみておく。 1: {1} -> 1 2: {1} -> 1 3: {1, 2} -> 1 4: {1, 3} -> 2 (2は除…

高速指数計算法 mod m バージョン

前回書き下した再帰を用いた高速指数計算関数をmod mバージョンにして、7を一般化した数bにしてみよう。 するとこうなる。関数名はpowからexpmodに置き換えた。 func expmod(b:Int, e:Int, m:Int) -> Int { if e == 0 { return 1 } let s = expmod(e/2) % m …

高速指数計算法アルゴリズム

ある数の大きなべき数を計算を行う際にできるだけ少ない計算量で行うための方法として、高速指数計算法というものがある。 例えば、 を計算したいとする。ここで のように2の累乗の足し算に分解する。 そして、 を計算する。 この分解をプログラムで行う場合…

curve25519とed25519の同等性

curve25519とは、 のことであり、 ed25519とは、 のことである。 これは単純な変数の置き換えで同等性が示せる。 ただし、ed25519の方が加法定義で場合分けをする必要がなく、扱いやすい。 とし、 とする。 を代入して計算すると、 となる。 xをで置き換える…

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

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