Tag Archives

66 Articles
RSA暗号の解説に出てくる数値の逆数のmod

RSA暗号の解説に出てくる数値の逆数のmod

RSA暗号に紹介には、必ず次のような式がでてきます。

これ
inv_1
今日は、この式について解説します。
といっても・・・すみません。言い訳になりますが、
数学科出身ではなく、間違ったこというかもしれません。
それをふまえていただいて・・・解説させていただきます。

まず、m = (p – 1)(q – 1) とすると、式は次のようになります。
inv_2
さて、この式、意味が分かりますでしょうか。
ここで、mod mというのは、mで割った余りとなります。
つまり、式通りの意味を考えると x-1 =(1/x) を計算して、
m で割った余りが y となります。

しかし、よく考えてください。
言い忘れていましたが、x, y, m とも整数なのです。
x が整数の時点で、 x-1 =(1/x) という式を計算すると、
小数点付きの数値となり、小数点付きの数値に対して、
整数 m で割る?というよく分からないことが起きます。

じつは、これは逆数とはいってもモジュラ逆数と呼ばれるものなのです。
つまり、(1/x)みたいなことをしてはいけないのです。たぶん?

さて、モジュラ逆数となると、
上記のこれまでの式は一体どういう意味なのか。
実は、次のような意味になります。
inv_3
x と y を掛け算して、m で割った後の余りが 1 となります。

つまり、これまでの式は、
上記の計算結果を満たすような y を求める式なのです。

例題と行きましょう。
x = 3, m = 10 としたときの y は一体いくつでしょうか。
inv_4
これの y を求めてみましょう。

・・・

求める過程は、モジュラ逆数の紹介にある
拡張ユークリッド互除法最大公約数など、
いくつか値を求める必要がありまして、
ここでは省略します。

そして、答えを求めると y = 7 が導かれます。

実際に計算してみると・・・
inv_5
余りが 1 となり、ぴったりとなります。

なお、Java などでは、
この y の値を BigInteger の modInverse メソッドで計算することが可能です。

	public static void main(String[] args) {
		System.out.println(new BigInteger("3").modInverse(new BigInteger("10")));
	}
指定した秒数で区切るツール Simple Wave Splitter

指定した秒数で区切るツール Simple Wave Splitter

Simple Wave Splitter

wavファイルを指定した秒数で区切るツールを公開しました。
JRE がインストールされた環境で利用できます。

デフォルトは、10秒+モノラルになっています。
sws_sc_1_1

使い方

1. 一番上の「ここにファイルをドラッグ&ドロップ」に、wavをドラッグ&ドロップします。うまくいくとファイル名が記入されます。
※wavファイルは、CD音質(44100Hz, 16bit, 2ch)がいいです。それ以外はテストしてません。
2. 「出力ファイル名」というのは、雰囲気が分かる人は設定してください。デフォルトのままでいいと思います。
3. 「区切りたい秒数」は単位は「秒」で秒数を指定してください。小数点も可能です。区切るときはこの秒数「以下」になります。
4. 出力ファイルはモノラルがいい方は、「出力ファイルをモノラル化」にチェック
5. 「カット開始」で、wavファイルがあるディレクトリに、カットされたファイルが作られます。

 

おまけとして、技術がたくさん詰まった素晴らしいプレイヤーで「試曲」ができます。

スーパーかっこいいビジュアライザーと、ハイクオリティなエフェクターを体感セヨ!
sws_sc_1_2

直接ダウンロード
他にこれまで作ったスバラシイソフトとかはこちら


裏話(技術ポイント)
・ビジュアライザーはソフトウェアレンダリングで実装してます!
・リバーブは反射音を自動作成後に、FFTで畳み込みの実装することで超高品質なリバーブを実現!

Eclipseから実行可能JAR作成とProGuardの難読化の一連の流れ

Eclipseから実行可能JAR作成とProGuardの難読化の一連の流れ

Eclipseを使ってJavaアプリケーションを作成して、
それを公開用のjarファイル作成までの流れを簡単に説明します。

まずは、単純に実行可能のJARファイルの作成方法です。

1. Eclipse で「ファイル(F)」→「エクスポート(O)…」を選択する。
2. 「Java」→「実行可能 JAR ファイル」を選んで「次へ(N) >」を選択する。
3. 「起動構成(L):」の中から、出力したい実行ファイルを選択します。(普段デバッグで利用している起動構成です)
4. 「エクスポート先(D):」に、出力先のファイルを指定します。
5. 「完了(F)」を押せば作成が行えます。

次は、ProGuardを使って、JARファイルをコンパクトにします。
具体的には、内部にある使用していないクラスを削除したり、
使用しているクラスの名前、メソッド名などを短い文字にします。

1. Windows環境なら「\proguardX.X.X\bin\proguardgui.bat」を実行すると起動します。
2. 「Input/Output」を開きます
3. 上の欄で「Add input…」で対象の実行可能JARファイルを選択します。
4. 上の欄で「Add output…」で出力したいファイル名を設定します。
5. 下の欄で「Add…」で使用しているライブラリを設定します。
6. 「rt.jar」は最初から設定されていますが「jce.jar」とかはないので必要に応じて追加。
pro_1
7. 「Shrinking」を開きます。
8. 「Keep」の「Applications」の欄に、今回の「main」が書いてあるクラスの名前を書きます。
これを書くことで、これ以外に「main」が書いてあるクラスとそれに関する処理を除去できます。
pro_2
9. あとは「Next」を選んでいけば、処理が行われて実行JARファイルが作成されます。

最後に、作成した「jarファイル」を7zipなどで開き、
使用していない画像ファイルとか設定ファイルを削除すれば、完成です。

指定した範囲の乱数を作成したい(後編)

みなさん、こんにちは。
今日は、昨日の続き、「指定した範囲の乱数を作りたい」を続きに話していきたいと思います。
というか、解答編みたいな感じです。

指定した範囲の乱数を作成したい(前編)
指定した範囲の乱数を作成したい(後編)←いまここっ!
指定した範囲の乱数を作成したい(実戦編)

それでは、ちょっとおさらいをしながら進めていきます。
今回は、3ビット(0, 1, 2, 3, 4, 5, 6, 7 の計8種類の数値)の
一様分布の値を出力する乱数生成器random8()を利用して、
0~2の3種類の数字を出力してみましょう。

この3ビットの乱数生成器random8()の性能を表にまとめます。

乱数値01234567
確率1/81/81/81/81/81/81/81/8

それでは、前回と同じように3で割った余りを使用します。
y = random8() mod 3

乱数に対して、3で割った余りを求めて

乱数値01234567
y (3で割った余り)01201201

確率をまとめると、

y012
確率3/83/82/8

やはり、前回の2ビット乱数発生器と同様にだめでした。
まあ、ただ2ビットの乱数発生器に比べて誤差は減っています。
乱数発生器のビット数が大きいほど誤差は少なくなるようですね。

さて、では3ビットの乱数生成器では、
当確率で、0から2の数字を出力することができないのでしょうか。
いいえ、出来ます。

気付いている人も多いかと思いますが、
毎回、問題になっているのは「はみ出している」部分なのです。
「はみ出している」というのは、下記の黄色の箇所です。

乱数値01234567
y (3で割った余り)01201201

つまり、3ビットの乱数生成器で0~7の値が出力されるが、
そのうち6か、7が出た場合は、
もう1度、3ビットの乱数生成器で出力するのです。

もちろん、計算コストが上がります。
例えば、3ビットの乱数生成器では

乱数0~56~7
確率6/82/8
利用するしない

それぞれの数字を出力する確率は上記のようになり、
6~7という数字が、2/8の確率で出力され、
もう1度計算する必要が出てくるのです。
しかも、次の乱数も、6~7なら、また乱数作成の計算が必要です((+_+))

さて、次はアルゴリズムの話に移ります。
出力された値が、6~7かどうかはどのように判断したらいいでしょうか。
上記のように、「0~7の8種出力する乱数から、0~2までの3種類の乱数が欲しい!」
と決め打ちされているならば簡単ですが、
乱数のビット数、いくつ未満の数字が欲しいか、いくつもの場合が考えられます。
でも、色々な場合とか考えると、大変なので、やっぱり簡単な乱数で勉強しましょう。

とりあえず、次の表を見てください。

乱数値 a01234567
b=a mod301201201
c = a – b00033366
d = c + 333366699
e = d > 8falsefalsefalsefalsefalsefalsetruetrue

ピーン(^o^)っときませんか?
上の表に出てきている
3は、必要な乱数の種類、0~2までの3種類の3です。
8は、3ビットの乱数発生器の性能、2の3乗の8です。
もうお分かり頂けたと思います。

ちょっと、C言語で上記の考え方で、乱数を作ってみましょう。
C言語では、乱数をrand()で出力するのですが、
この出力する範囲は「0~RAND_MAX」となり、「RAND_MAX + 1」種類の数字を出力します。

int TRUE = 1;
unsigned long n = 3; // 欲しい乱数の種類
unsigned long y = 0; // 出力値
unsigned long random = 0;
while(TRUE) {
   random = rand();
   y = random % n;
   if( ( random - y + n ) > (RAND_MAX + 1) ) {
	  continue;
   }
   break;
}

まあ、とりあえず説明にあったような流れで、無理やり書いて、
上記のようなコードになりました。
do文を利用するともっとすっきり書けます。

実は1つだけ落とし穴があります。
それは、RAND_MAXの値が非常に大きい場合や、
( random – y + n )の値が実は巨大な数字の場合です。
signed long などで計算している場合は、負の値になってしまいますし
unsigned longを使用していたとしても、オーバーフローして、小さな値になってしまう可能性があります。

例として、「signed short」16ビットの正負の範囲を表す整数値を使用しており
さらに、RAND_MAX は 0x7fff の場合、RAND_MAX + 1 は -32768 となり負になってしまいます。
そのため、IF文の結果が思った結果と異なる場合があります。
アルゴリズム自体は分かったと思いますので、
上記の点だけ注意して、値がおかしくならないように設計して下さい。

さて、最後なのですが、
JavaScriptのように、0以上、1未満の数字を出力する
Math.random()しかない場合は、どうすればいいでしょうか。
この時も、前編で話したように同様の問題を抱えています。

この場合も、一度整数に戻すしかありません。
疑似乱数は、通常ビット単位で作成されます。
(これまでで話したように、任意の数までの乱数を作るのは面倒だからです。)
そのため、Math.random() を作成している元となる乱数も
元々は、あるビット長の整数を元にしていると思われます。
この場合は、Math.floor(Math.random() * 0x8000) とすれば、
0から32768未満の整数値を、均等な確率で出力します。
あとは、この整数値を利用して、上のC言語で説明したように作成すれば
しっかりとした乱数が作成できます。

ちなみに、Javaの場合は、RandomクラスnextInt(n)を使用すれば、問題ありません。
さすがJavaです。速度も速いですし。
とりあえず、「指定した範囲の乱数を作成したい」はここで終わりです。

話は、少し変わりますが乱数は作成する方法がたくさん考案されてます。
疑似乱数の質とか考えると、よく利用される線形合同法はマズいです。
利用する目的にもよると思いますが、
乱数の種類などを勉強しておくといいかもしれません。
メルセンヌ・ツイスタは、日本人が開発したもので、乱数の質が高いです。
(ただ、MTは、簡単に自分の手で実装できないのがデメリットがあります><)

続きは、HSPを使ったより実践的な話です。
指定した範囲の乱数を作成したい(実戦編)

指定した範囲の乱数を作成したい(前編)

みなさん。
指定した範囲の乱数を作りたい場合は、どうしているでしょうか。
今日は、指定した範囲の乱数生成の小ネタを紹介します。

指定した範囲の乱数を作成したい(前編)←いまここっ!
指定した範囲の乱数を作成したい(後編)
指定した範囲の乱数を作成したい(実戦編)

さて、例えばサイコロを作りたいと思います。
サイコロの目は1~6ですね。

そして乱数生成器が用意されていると思います。
この乱数生成器は、4バイト=32ビットの一様分布する整数値が出力されるもので、
random32()と関数を呼び出せば、出力されるものとします。
( random32() は、C言語の乱数 rand()と似たような関数だと思ってください。 )

どのような、コードを思い浮かべるでしょうか。
恐らく最も簡単なコードは、次のようなコードです。

サイコロの目 = random32() mod 6 + 1
(mod 6 は、6で割った余りの数とします)

はい。
たしかに、「random32() mod 6」で0~5の範囲の値を作成して、
1を足して、1~6の乱数が出ると思います。

今度は、実数の乱数生成器で、サイコロを作る話です。
この実数の乱数生成器は、64ビットのdouble型の実数を作成するもので
[0, 1) = {x | 0 ≤ x < 1} の乱数、つまり0以上、1未満の乱数を得ることができます。
randomf()と関数を呼び出せば、出力されるものとします。
( randomf() は、JavaScript の Math.random() と似たような関数だと思ってください。)

この場合も、どのような、コードを思い浮かべるでしょうか。
最も簡単なコードは、次のようなコードです。

サイコロの目 = floor(6 * randomf()) + 1
(floor() は、床関数です)

はい。
これも、たしかに、「6 * randomf()」で[0, 6)の乱数を作成して、
床関数で0~5の整数値にして、1を足すことで、1~6の乱数が出力されます。

簡単で、すぐに乱数が欲しいという目的であれば、これまでの話は正しいと思います。

ただし、知っている方も多いかと思いますが、
本当に本当に正確な乱数を欲しい場合は、問題があるコードなのです。
何が問題なのでしょうか。

まずは、整数の乱数を使用した場合です。

問題を分かりやすく考えるため誤差を大きくしましょう。
2ビットの乱数生成器(0~3までの4パターンの数字を出力する)random4()が用意されており、
ここから0~2まで、3パターンの数字を出力する乱数を作り出したいと思います。

この2ビットの乱数生成器の性能を表にまとめます。

乱数値0123
確率1/41/41/41/4

それでは、先ほど同じような考え方で
y = random4() mod 3
を計算してみるとどうでしょうか

乱数値0123
y (3で割った余り)0120

つまり、出力される0~2の値は、
「random4() mod 3」の計算で作成すると、
下記のように0が出る確率が高くなってしまうのです。

残念な乱数出力結果1

y012
確率2/41/41/4

今度は、実数の乱数生成器の話です。
「 floor(6 * randomf()) + 1」とサイコロを作成した場合、同じように偏りが生まれる問題があるのです。
浮動小数点型に限界があるのです。
一様乱数な0から1未満の浮動小数点を作成したとしても、仮数部のビット数分の種類しかないのです。
(ただ、出力値がdouble型ならば、
先ほどの、randomf()は、約2^52ビット=9007兆の数字のパターンを持っています。
これだけ大きければ実際は、問題はないと思います。)

分かりやすく考えるため、しょぼい乱数生成器を使用します。
2ビット整数の乱数生成器の話と同じように仮数部が、
2ビットの実数の乱数生成器randomf4()を使用して、0~3の整数を作ってみましょう。
(randomf4()は、0から1未満を生成するが、0.00 0.25 0.50 0.75の4パターンしか出力されない)

この仮数部2ビットの実数乱数生成器の性能を表にまとめます。

乱数値0/41/42/43/4
確率1/41/41/41/4

それでは、先ほど同じように
y = randomf4() * 3
z = floor(y)
を計算してみるとどうでしょうか

乱数値0/41/42/43/4
y (3倍した)0/43/46/49/4
z (床関数)0012

つまり、出力される0~2の値は、
「random4() % 3」の計算で作成すると、
0が出る確率が高くなってしまうのです。

残念な乱数出力結果2

y012
確率2/41/41/4

では、どうすればいいんじゃあって思うかもしれません。
まあ、普通に使用する分は、最初の話があったような方法で十分です。
ただし、使う人を選ばない乱数生成器を作成したいとか、
どのような乱数生成器の性能でも、しっかりした乱数を作りたいといった場合は、
工夫して上記の問題を解決する必要があります。

指定した範囲の乱数を作成したい(後編)へ続くッ!!!

%d人のブロガーが「いいね」をつけました。