乱数の解読

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
へろす

乱数の解読

#1

投稿記事 by へろす » 3年前

乱数生成クラスを作ってみました。
これを利用し種のもとをパスワードとしてファイル暗号化プログラムを作ろうと思います。
パスワードを知らない人がファイルを復元する場合この乱数の規則性を調べるのだろうと思いますが
解読される危険性はどの程度あるのでしょうか?
一般に公開されている様な有名な暗号化ソフトと比べてどの程度の差があるのか興味があります。

環境:
windows 10 home
visual studio comunity 2015

理解度:
c, c++入門書が何とか理解できる程度。ネットに転がっているコードを見ても全く理解できません。

コード:

//****************** ファイル Random.h *********************************
#pragma once

#include<vector>

class StdRand {		// c言語のランダム関数と同様の働きをします。
	int x;
public:
	StdRand(int n);		// 引数に種を指定します。
	void setSeed(int n);	// 種を設定します。
	int get();			// 0 ~ 0x7FFF の乱数を返します。
};

/*
種を文字列から作成する乱数作成クラスを作成します。
文字列のわずかな違いにより全く異なる種を作るために
slide_to_left、str_to_randを使って配列を作成します。
*/
class BeterRand {
	std::vector<StdRand> mArray;
	int mIndex;
public:
	// 文字列を種として乱数配列を作成します
	BeterRand(const char *str);
	// char単位で左向きに1個分スライドします
	static void slide_to_left(char *str);
	// 文字列から乱数を作成します
	static int str_to_rand(const char *str);
	// 0 ~ 0x7FFF の乱数を出力します
	int get();
	// 0 ~ 0xFF の乱数を出力します
	int get_byte();
};
//****************** ファイル Random.h end *******************************


//****************** ファイル Random.cpp *********************************
#include<iostream>
#include<vector>
#include"Random.h"
using namespace std;

StdRand::StdRand(int n)
{
	x = n;
}
void StdRand::setSeed(int n)
{
	x = n;
}
int StdRand::get()
{
	x = 214013 * x + 2531011;
	return (x >> 16) & 0x7FFF;
}

BeterRand::BeterRand(const char *str)
{
	int length = strlen(str);
	char *newP = new char[length + 1];

	strcpy_s(newP, length + 1, str);
	for (int i = 0; i < length; i++) {
		mArray.push_back(str_to_rand(newP));
		slide_to_left(newP);
	}
	delete[]newP;

	mIndex = 0;
}
void BeterRand::slide_to_left(char *str)
{
	int length = strlen(str);
	char top_ch = *str;

	memmove(str, str + 1, length - 1);
	str[length - 1] = top_ch;
}
int BeterRand::str_to_rand(const char *str)
{
	if (!str) return 0;
	else if (!*str) return 0;

	StdRand rnd(*str);
	for (const char *p = str + 1; *p; p++) {
		rnd.setSeed(rnd.get() * 0x100 + *(unsigned char *)p);
	}
	return rnd.get();
}
int BeterRand::get()
{
	if (mArray.empty()) return 0;

	mIndex = mArray[mIndex].get() * mArray.size() / 0x8000;

	return mArray[mIndex].get();
}
int BeterRand::get_byte()
{
	return get() / 0x80;
}
//****************** ファイル Random.cpp end ******************************

YuO
記事: 942
登録日時: 9年前
住所: 東京都世田谷区

Re: 乱数の解読

#2

投稿記事 by YuO » 3年前

この疑似乱数系を,どのように暗号に利用するのでしょうか。
パスワードにするだけであれば,十分な長さと文字種を用意すれば,事実上の強度の違いは存在しないと思います。

暗号化処理において通常,疑似暗号で作成したソルトとパスワードをハッシュ関数に通す事によって実際の暗号鍵を作り出します。
# 結城浩「暗号技術入門 第3版」第11章
通常暗号のクラックには辞書攻撃が最初に行われますが,これは人が入力する可能性の高いパスワードを先に試す事によって解読の可能性を上げるためであって,パスワードが乱数によって生成されたのであれば,乱数自体の解析よりもパスワード自体の総当たりで解読する事になると思います。
# まぁ,乱数の周期が短くて種の種類が少ないなら,そちらから総当たりするかもしれませんが。
このため,十分に長いランダムなパスワードを生成できるのであれば,同様の長さ・文字種のパスワードを生成する別のパスワード生成器と性能差はそれほど存在しないと思われます。

白い変人

Re: 乱数の解読

#3

投稿記事 by 白い変人 » 3年前

まず、プログラムに触れる前に、確認したい点ですが、

>これを利用し種のもとをパスワードとしてファイル暗号化プログラムを作ろうと思います。

と言うのは、若干実装法が違うとしても、

例えば、

void 暗号化用関数(int *暗号化したいファイルのデータ,int *暗号鍵){
 for(int i=0;暗号化したいファイルのデータ!=EOF;i++) 暗号化したいファイルのデータ=暗号化したいファイルのデータ ^ 暗号鍵; //Cに倣って^はXOR
}

void main(void){
 暗号化用関数(int *暗号化したいファイルのデータ,int *質問者様の乱数生成アルゴリズムで生成された可変長の暗号鍵){
}

とでもして、使い捨てパッドでも実装するのでしたら理解出来るのですが、何の為にパスワードの為に強度の高い乱数を要求しているのかが個人的には不明でした。

もしかすると、暗号理論の基本的な所が理解出来ていない為に、無駄な努力をしているのではないかと言う心配はあります。


それで、乱数のロジックに触れますが、質問者様も自覚はあるのかもしれませんが、線形合同法を弄ってみて自分なりにステガノグラフィーを加えたという感じでしょうか?

世にある、解読される危険性が少ない、(上の人が提示している結城浩氏の著書の言葉で言うならば、予測不可能性が高い)乱数と言うものは、暗号アルゴリズムが盗まれたとしても、過去に生成された乱数列からこれから生成される乱数列を予測する為の計算量が非常に高い(指数関数以上に難しくなる)と言う事を特徴にしています。

線形合同法に関しては、生成速度は高速だが強度の高い暗号には向かないアルゴリズムであり、質問者様の施したステガノグラフィーも「暗号アルゴリズムが盗まれたとしても」の定義から、暗号理論的には無力なものに位置づけられます。


>解読される危険性はどの程度あるのでしょうか?

ですが、私の見解を述べると、解読対象となるデータの平文(暗号化される前のデータ)に解読者が想定可能なフォーマット(例えばASCII CODEと言うのも想定可能なフォーマットと言える)があった場合、耐性の弱い暗号アルゴリズムを使用したならば、ファイルのサイズが大きくなるほど、解読されるリスクは高まると言えるでしょう。

ただ、そこまでハッカーに狙われる様なデータを暗号化したいのなら、暗号アルゴリズムや予測不可能性の高い乱数に関しては、研究者から安全性が高い事を広く主張されているアルゴリズムをそのまま実装すれば良いと思います。


上の人の「暗号技術入門」は質問者様が目を通し理解すべき教科書だと思えますし、私からはそれに加え、サイモン・シン著の「暗号解読」も推奨致します。

ただ、私が上に挙げた暗号化の方法を実装した場合、速度は若干遅くなりますが、予測不可能性が非常に高い暗号技術用の乱数アルゴリズムを用意出来れば、暗号化プログラムは簡単に作れる上、保守性が高くなるというメリットはあるとは助言しておきます。

因みに、予測不可能性とは、ただ単に周期が長くて、種の範囲が大きい事だけが要件ではありませんので、まず、暗号理論について勉強される事をお勧め致します。

へろす

Re: 乱数の解読

#4

投稿記事 by へろす » 3年前

YuOさん 白い変人さんありがとうございます。
説明がうまくできなくて申し訳ありませんでした。
私の知識では返事を完全に理解できているとは言えないので変な返事になってしまうかもしれませんが使い方としてはまさに白い変人さんの例えの通りです。

>>何の為にパスワードの為に強度の高い乱数を要求しているのか
コンストラクタでいちいち乱数を使って種を決めていることでしょうか?
例えば引数strに”abcde”とした場合と”abcdd”とした場合種も似たようなものになってしまうのが気に入らないのでこのような結果になりました。

あるいは説明の不備でパスワードを作るための乱数生成クラスと思わせてしまったのでしょうか。白い変人さんの書いてくれたコードの暗号鍵; のためだけにBeterRandを作りました。

>>線形合同法を弄ってみて自分なりにステガノグラフィーを加えたという感じでしょうか?
ステガノグラフィーの意味がちょっと難しいのですが、ただの関数rand()よりはいいだろうという考えで作ってみました。

皆さん適切なアドバイスありがとうございます。これを手掛かりに詳しく調べてみようと思います。

返信

“C言語何でも質問掲示板” へ戻る