Pebble Coding

プログラマーの作業メモ

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

前回からの続きです。 暗号化は の式によって行い、 復号化は の式によって行います。 これがうまく動作する仕組みを知るにはどうやって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 での平方剰余の計算方法を示しましたが、swiftで実装しておきます。 の解は存在すると仮定しておきます。 func quadraticResidue(_ a:Int, _ p:Int) -> Int { assert(p % 8 == 5) let x = expmod(a, (p+3)/8, p) if (x * x …

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暗号に関する文章を読んでいてもその数学的な原理がさっぱり理解できなかったのですが、色々読んでいるうちになんとなく分かってきましたので、メモしておきます。 のとき、 である。 で gcd(e, n) = 1 ならば である。 合同式の意味とよく使う6つの性質…

エドワード曲線における加法

エドワード曲線 において、曲線上の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) 全ての要素に対し…

離散対数問題とは

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参照を返す クラスの不要な関数を削…

swift 循環参照

swift 循環参照の一例を挙げます。 iOSのソースを例にとります。 ViewController.swift import UIKit class ViewController: UIViewController { override func viewDidLoad() { super.viewDidLoad() let model = Model() model.action() } } Model.swift im…

iOS/MacOSXのvDSP関数、多すぎてなかなか見つけられないのをなんとかする(応答編)

複素数を扱うためにvDSP.hで定義された構造体 typedef struct DSPComplex { float real; float imag; } DSPComplex; typedef struct DSPSplitComplex { float * __nonnull realp; float * __nonnull imagp; } DSPSplitComplex; 1次元高速フーリエ変換 vDSP_c…

Rx メモ

RxSwiftとRxCocoaの区別がわかりづらいのでメモ。 RxCocoaはUIKit,NSFoundationなどに特化したiOS/macOS環境特有の機能。 RxSwift combileLatest 仕様:複数の変数のいずれかが変更された場合にそれぞれの最新の値をまとめて受け取る 使い道:2つのUITextField…

android studio 2.3でideavimを有効にする

Android Studio - 「Preferences」- 「Plugins」 で「IdeaVim」をインストールし、有効にします。

Android Studio2.3 から外部エディタvimを開く(macOS)

Android Studio2.3で開いているファイルを行番号を指定し外部エディタvimで開く方法です。 macOSの場合です。 1) Android Studio - Preferences - Tools - External Tools に gvim を登録します。 内部console画面が開かないように Open console のチェック…

C# Microsoft純正ライブラリでJSONをdeserializeする

C#

C#でJSONをserialize/deserializeする方法として、Microsoftが提供するライブラリを使う場合、2種類の方法がある。 1) DataContractJsonSerializer Namespace: System.Runtime.Serialization.Json AssemblySystem.Runtime.Serialization 2) JavaScriptSeria…

オライリー 英語版原書を読むのに役立つ英単語40

n. 名詞 adj. 形容詞 v.i. 自動詞 v.t. 他動詞 adv. 副詞 variable n. 変数 definition n. 定義 deduction n. 推論 explicit adj. 明示的な implicit adj. 暗黙の distinguish v.t. 区別する prefer v.t. ~の方がよい declare v.t. ~を宣言する exception n.…

RxSwift 超入門その3

class GeolocationViewController: ViewController { @IBOutlet weak private var noGeolocationView: UIView! @IBOutlet weak private var button: UIButton! @IBOutlet weak private var button2: UIButton! @IBOutlet weak var label: UILabel! override …

RxSwift 超入門その2

let minimalUsernameLength = 5 let minimalPasswordLength = 5 class SimpleValidationViewController : ViewController { @IBOutlet weak var usernameOutlet: UITextField! @IBOutlet weak var usernameValidOutlet: UILabel! @IBOutlet weak var passwor…

RxSwift 超入門その1

0)環境: Xcode8.2.1 1) 新規iOSプロジェクトaaaを作成する。 2) aaaフォルダに新規ファイルPackage.swiftを以下の内容で作成する。 import PackageDescription let package = Package( name: "dummy", targets: [], dependencies: [ .Package(url: "https://…

Go POSTによるJSONパラメータをデコードする際の注意

go

まずはソースをみて頂こう。 type User struct { name string } func q(w http.ResponseWriter, r *http.Request){ decoder := json.NewDecoder(r.Body) var user User err := decoder.Decode(&user) if err != nil { panic(err) } fmt.Println(user) } エラ…

go言語 ネストしたJSONをリテラルで初期化する

go

go root := map[string]interface{}{ "alpha": map[string]interface{}{ "beta": []map[string]interface{}{ map[string]interface{}{ "gamma": "val1", "delta": []map[string]interface{}{ map[string]interface{}{ "epsilon": "val2", }, }, }, }, }, } r…

curl コマンドオプション

-i レスポンスヘッダの表示 -s サイレントモード -H カスタムヘッダ指定 -X コマンド指定 -d HTTP POST データ JSONをPOSTするときのサンプル curl -i -H "Content-Type: application/json" -d '{"name":"foo"}' http://localhost:3000/contents

Windowsでgo環境を作る場合の備忘録

go

Windowsにgoをインストールする場合 ここ https://golang.org/dl/ にあるインストーラー go1.8.windows-amd64.msi をダウンロードして実行する GOROOTはC:\go\ となる。 GOPATHは未設定の状態となるので、デフォルトでは %USERPROFILE%\go となる。 goのソー…

Missing Push Notification Entitlement (未解決)

iOSアプリのバイナリをiTunesConnectにUploadしたときたまにAppleから Missing Push Notification Entitlement のメールが来たり来なかったりするんだが、どうしたもんか。 アプリではPushNotificationは使っていないが、FireBaseフレームワーク内で使ってい…

SIMD組み込み関数が多すぎるので一覧にしておく

大量の計算を常に行うような場合、C言語の速度をさらに上げるには、CPUのSIMD命令に置き換えられる組み込み関数を使う方法がある。 ただし、これもvDSPと同じで量が多くまた見やすい一覧がないので作ってみる。 なお、独断と偏見で使いそうもないものは一覧…

swift Arrayでwhereを使う

swiftはモダンな言語なので、C言語風の書き方は極力排除されている。 Arrayでwhereがついているメソッドを使い条件式を表すクロージャを指定して結果を取得するケースは多い。 public struct Array<Element> : RandomAccessCollection, MutableCollection { // 条件を</element>…

make_moonsで生成されるものを見てみる(scikit-learn)

macOSXにpipをインストールする sudo easy_install pip scikit-learnをインストールする sudo pip install scikit-learn make_moonsでデータを生成してみる bash-3.2$ python >>> from sklearn import datasets, linear_model >>> datasets.make_moons(10, n…

swiftでwavファイル書き込みしてみる

以前はAudioToolKitにあるAudioFileCreateWithURLを使っていましたが、 ここでは試しにiOS8,macOS10.10で追加されたAVFoundationにあるAVAudioFileを使ってみます。 まず、AVAudioFileのクラス定義をみてみます。 open class AVAudioFile : NSObject { publi…