Pebble Coding

プログラマーの作業メモ

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の場合)

前回、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,…のように自…

安全素数

pが素数であり、2p+1=qも素数である場合、qを安全素数(safe prime)と呼ぶ。 安全という名前は暗号理論に由来する。 https://en.wikipedia.org/wiki/Safe_prime https://ja.wikipedia.org/wiki/安全素数

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

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

swift3 IntegerArithmaticプロトコル

IntegerArithmeticプロトコルを実装するには、以下8つの関数を定義する必要がある。 最初の2つはComparableである。 static func ==(lhs: M, rhs: M) -> Bool static func <(lhs: M, rhs: M) -> Bool static func addWithOverflow(_ lhs: M, _ rhs: M) -> (…

swift3 Comparableプロトロル

Comparableプロトコルを作るには、 static func <(lhs: Even, rhs: Even) -> Bool static func ==(lhs: Even, rhs: Even) -> Bool の2つを実装すればよい。 struct M : Comparable { var val:Int static func <(lhs: M, rhs: M) -> Bool { return lhs.val <…

swift3 Collectionプロトコル

Collectionプロトコルを作るには、 startIndexプロパティ,endIndexプロパティ,subscript,index(after:) の4つを実装する必要がある。 Collection - Swift Standard Library | Apple Developer Documentation ここでは奇数を返すコレクションOddを作ってみた…

swift3 Sequenceプロトコル

Sequenceプロトコルの例 ここでは1以上の奇数を順番に返すものを作ってみた。ちなみにIntの範囲を超えるとクラッシュするが気にしないでもらいたい。(^ ^) struct Odd : Sequence, IteratorProtocol { typealias Element = Int private var v:Element = 1 pu…

swift preconditionとassertの違い

swiftにはassertさせる関数がいっぱいあって困ります。 1) assert() let ary = [1, 2, 3] let i = 3 assert(i < ary.count) print("\(ary[i])") assertion failed: file /develop/aaa/aaa/ViewController.swift, line 18 2) precondition() let ary = [1, 2,…

swfit 負数の除法

swift,C,Javaとruby, python,perlでは、 負数を割り算や剰余に使った場合、結果が異なる。 python 剰余 7 % 3 -> 1 7 % -3 -> -2 -7 % 3 -> 2 -7 & -3 -> -1 swift 剰余 7 % 3 -> 1 7 % -3 -> 1 -7 % 3 -> -1 -7 % -3 -> -1 python 商 7 / 2 -> 3 7 / -2 -> …

ios10.3 ファイルパス問題

環境 ios10.3.1 Xcode 8.3.2 guard let path:String = NSSearchPathForDirectoriesInDomains(.documentDirectory, .userDomainMask, true).first else { return } let filename0 = path + "/" + "a.txt" if let fp0 = fopen(filename0, "wb") { print("fp0 \…

macOSにSPTKをインストール

macOS 10.12.4 xgrを動かすのに必要なのでconfigure前に入れておきます。 $ brew cask install quartz あとは、 SPTK-3.10.tar.gzをDLし、 $ configure $ make $ make install したら完了です。 参考 SPTKの使い方 (1) インストール・波形描画・音声再生 - …

C++11 unique_ptrとshared_ptr

unique_ptrは所有者が1人以下のポインタとして利用する。 実装にatomic関数は用いられていないためコピーや破棄はスレッドセーフではないが、それによるオーバーヘッドは存在しない。 shared_ptrは所有者が2人以上のポインタとして利用する。 いったん値を設…

C++最適化手法

メモリ使用量が増えてもよいので速度を優先させたい場合の最適化方法を考えます。 計算した値をキャッシュし計算回数を減らす 同じ値の設定処理を何度も行わない 関数の戻り値では、構造体の値を返す代わりに構造体のconst参照を返す クラスの不要な関数を削…