Pebble Coding

プログラマーの作業メモ

体の標数(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を整…

edward曲線における加法

Edward曲線 において、曲線上の2つの点 の加算後の点を次のように定義する。 この点は代数計算によって、エドワード曲線上の点になることを確かめることができる。 が、計算は長く厄介なので、計算方法を記しておく。 を計算し、に等しくなることを示す方針…

エドワード曲線とツイストエドワード曲線の形

2007年のエドワードさんの論文(http://www.ams.org/journals/bull/2007-44-03/S0273-0979-07-01153-6/S0273-0979-07-01153-6.pdf) から、エドワード曲線と名付けられた がどのような形をしているのか見てみましょう。 まずはa=1.0 2本の直線になってしまいま…

楕円曲線の形

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

群、体、有限体の定義

群(group)の定義 ある要素の集まりに対して、一つの演算規則 f を決め、演算結果はまた要素の集まりの一つになっているとします。 a, b, c を要素とします。 1) 全ての要素に対して、結合法則が成り立つ f(f(a, b), c) = f(a, f(b, c)) 2) 全ての要素に対し…

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

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