人力検索はてな
モバイル版を表示しています。PC版はこちら
i-mobile

以下のような条件を満たす関数y=f(x)はありますか?
あれば教えてください。

条件:(優先度順です)
どのようなx1,x2(x1!=x2)をとってもf(x1)==f(x2)にならない。(衝突しない)
g(y)=xとなる関数gがある。
seedの推測が困難。
f(x,seed)とseedを渡すと別系統の関数f2(x)になる。
計算量が少ない。
x,yは4byteのint

説明不十分な点があると思いますが
コメントにて補足しますので、よろしくお願いします。



●質問者: urekat
●カテゴリ:コンピュータ 科学・統計資料
✍キーワード:SEED X1 コメント 系統 計算
○ 状態 :終了
└ 回答数 : 4/4件

▽最新の回答へ

1 ● KUROX
●23ポイント

ハッシュ関数の系統?

http://ja.wikipedia.org/wiki/%E3%83%8F%E3%83%83%E3%82%B7%E3%83%A...

◎質問者からの返答

逆方向変換ができる

入力も出力も同じ長さ(4byte)

のハッシュがあればそれです。でもそれってハッシュっていうのかな。

bit反転、bitシフト、bit入替を組み合わせればそれなりになりそうですが、「推測が困難」の点がクリアできなさそうです。


2 ● wasisan
●23ポイント

ということから,

これは,「最小完全ハッシュ関数」ということになると思います.

Perfect hash function - Wikipedia, the free encyclopedia:

http://en.wikipedia.org/wiki/Perfect_hash_function

より定義.

A minimal perfect hash function is a perfect hash function that maps n keys to n consecutive integers -- usually [0..n-1] or [1..n].

完全ハッシュ関数を求めるためのツールとしては

http://burtleburtle.net/bob/hash/perfect.html

などがあるようです.

質問にあるSeedというのは具体的なハッシュ関数の変更ということになると思いますが,これができるかどうかは調べていません.

また,逆関数というのも難しいことだと思います.

http://ja.doukaku.org/36/

などでも色々とやっているようですが,結局すべてのハッシュ値を記録して総当りをやっているみたいですし.

◎質問者からの返答

ありがとうございます。

ハッシュ関数というものがそもそも逆関数を求めることが難しいものなのですよね?

ハッシュ関数ではない関数で、ないですかねえ。

乱数列とかが関係あるかなあと思い始めました。


3 ● Mook
●22ポイント

コメントの内容を実装してみました。


言語の指定がなかったので、C(Borland C) で書いています。

DEFAULT_SEED の部分を変えれば、異なる結果になります。

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

#define DEFAULT_SEED 0x7d4a6b1c

static unsigned int funcF( unsigned int a, unsigned int s );
static unsigned int funcG( unsigned int a, unsigned int s );

void main( void ) {
 unsigned int sData;
 unsigned int rData;
 int i;


// 0 ? 4 を変換した結果
 for( i=0 ; i<5 ; i++ ) {
 printf("x = 0x%08x(%u)\n", i, i );
 rData = funcF( i, DEFAULT_SEED );
 printf("f(x) = 0x%08x(%u)\n", rData, rData );
 rData = funcG( rData, DEFAULT_SEED );
 printf("g(f(x)) = 0x%08x(%u)\n\n",rData, rData );
 }

// 乱数での変換を5回実行
 srand((unsigned)time(NULL));
 for( i=0 ; i<5 ; i++ ) {
 sData = (unsigned int)(rand()<<16 ) | (unsigned int)rand();
 printf("x = 0x%08x(%u)\n", sData, sData );
 rData = funcF( sData, DEFAULT_SEED );
 printf("f(x) = 0x%08x(%u)\n", rData, rData );
 rData = funcG( rData, DEFAULT_SEED );
 printf("g(f(x)) = 0x%08x(%u)\n\n",rData, rData );
 }
}

// バイトごとに異なる演算をする関数
static unsigned int funcF( unsigned int a, unsigned int s ){
 unsigned int t1 = 0;
 unsigned int t2;
 unsigned int i;

// 下位ビットと上位ビットを入れ替え
 for( i=0 ; i<16 ; i++ ) {
 t1 |= ( ( ( 0x00000001 << i ) & a ) << ( 31 - i * 2 ) );
 t1 |= ( ( ( 0x80000000 >> i ) & a ) >> ( 31 - i * 2 ) );
 }

// 1バイト目は偶数ビットと奇数ビットを入れ替え
 t2 = ( ( 0x00000055 & t1 ) << 1 ) | ( ( 0x000000aa & t1 ) >> 1 ) ;

// 2バイト目は4ビットローテーション
 t2 |= ( ( ( 0x00000f00 & t1 ) << 4 ) | ( ( 0x0000f000 & t1 ) >> 4 ) );

// 3バイト目はビット反転
 t2 |= ( 0x00ff0000 & (~t1) );

// 4バイト目はそのまま
 t2 |= 0xff000000 & t1;

// シードと XOR
 return ( t2 ^ s );
}

// 逆関数
static unsigned int funcG( unsigned int a, unsigned int s ){
 unsigned int t1;
 unsigned int t2 = 0;
 unsigned int i;

// シードと XOR:逆関数は最初に
 a ^= s; 

// 1バイト目は偶数ビットと奇数ビットを入れ替え
 t1 = ( ( 0x00000055 & a ) << 1 ) | ( ( 0x000000aa & a ) >> 1 ) ;

// 2バイト目は4ビットローテーション
 t1 |= ( ( ( 0x00000f00 & a ) << 4 ) | ( ( 0x0000f000 & a ) >> 4 ) );

// 3バイト目はビット反転
 t1 |= ( 0x00ff0000 & (~a) );

// 4バイト目はそのまま
 t1 |= 0xff000000 & a;

// 下位ビットと上位ビットを入れ替え
 for( i=0 ; i<16 ; i++ ) {
 t2 |= ( ( ( 0x00000001 << i ) & t1 ) << ( 31 - i * 2 ) );
 t2 |= ( ( ( 0x80000000 >> i ) & t1 ) >> ( 31 - i * 2 ) );
 }

 return ( t2 );
}

実行結果はこんな感じです。

0?4の実行結果

x = 0x00000000(0)
f(x) = 0x7db56b1c(2109041436)
g(f(x)) = 0x00000000(0)

x = 0x00000001(1)
f(x) = 0xfdb56b1c(4256525084)
g(f(x)) = 0x00000001(1)

x = 0x00000002(2)
f(x) = 0x3db56b1c(1035299612)
g(f(x)) = 0x00000002(2)

x = 0x00000003(3)
f(x) = 0xbdb56b1c(3182783260)
g(f(x)) = 0x00000003(3)

x = 0x00000004(4)
f(x) = 0x5db56b1c(1572170524)
g(f(x)) = 0x00000004(4)

乱数の実行結果

x = 0x47db1fa5(1205542821)
f(x) = 0xd84dd6cd(3628979917)
g(f(x)) = 0x47db1fa5(1205542821)

x = 0x14f00564(351274340)
f(x) = 0x5b159b08(1528142600)
g(f(x)) = 0x14f00564(351274340)

x = 0x1a211913(438376723)
f(x) = 0xb52d23b8(3039634360)
g(f(x)) = 0x1a211913(438376723)

x = 0x67e24672(1742882418)
f(x) = 0x33d71fc5(869736389)
g(f(x)) = 0x67e24672(1742882418)

x = 0x375f07b0(928974768)
f(x) = 0x7055c4c0(1884669120)
g(f(x)) = 0x375f07b0(928974768)

ご参考までに

◎質問者からの返答

ありがとうございます。

f(0) = 0x7db56b1c

f(1) = 0xfdb56b1c

f(2) = 0x3db56b1c

f(3) = 0xbdb56b1c

f(4) = 0x5db56b1c

これを並べてみると1番左の部分が変わって

いっているので(7,f,3,b,5)簡単に規則性が推測できてしまうようです。

1bit変わっただけでハッシュ関数のように複数のbitに影響があるような関数はないでしょうか。


4byteから4byteを出力する最小完全ハッシュ関数を見つけてx=g(y)はテーブルを作って対応ですかねえ。4byte*4294967295=17G...になっちゃいますねえ。


4 ● Mook
●22ポイント

既存の技術を探せばあるとは思いますが、先ほどのものを拡張してみました。


処理結果から

x = 0x00000000 f(x) = 0xc98343e2 g(f(x)= 0x00000000
x = 0x00000001 f(x) = 0xa90aad48 g(f(x)= 0x00000001
x = 0x00000002 f(x) = 0x730c6693 g(f(x)= 0x00000002
x = 0x00000003 f(x) = 0x6208ed84 g(f(x)= 0x00000003
x = 0x00000004 f(x) = 0xd9956c6c g(f(x)= 0x00000004
x = 0x00000005 f(x) = 0xef21ae66 g(f(x)= 0x00000005
x = 0x00000006 f(x) = 0x1ff4ca42 g(f(x)= 0x00000006
x = 0x00000007 f(x) = 0x86e84b88 g(f(x)= 0x00000007
x = 0x00000008 f(x) = 0x630f437b g(f(x)= 0x00000008
x = 0x00000009 f(x) = 0x9b183488 g(f(x)= 0x00000009

基本は先に提示したものですが、処理を繰り返すことで複雑にしています。

ビット演算による処理の利点は、逆関数は逆の順序で処理をしていけば作成できる点です。


一回の処理では推測できそうな場合でも、複数回処理を重ねることで結果を複雑にすることができます。

上記の結果は4種類の処理を100回繰り返したものです。


ソースは下記の通りです。

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

#define DEFAULT_SEED 0x7d4a6b1c
#define TO_RIGHT 1
#define TO_LEFT 2

static unsigned int funcFF( unsigned int a, unsigned int s );
static unsigned int funcGG( unsigned int a, unsigned int s );
static unsigned int funcF( unsigned int a, unsigned int s );
static unsigned int funcG( unsigned int a, unsigned int s );
static unsigned int bitops( unsigned int a );
static unsigned int bitreverse( unsigned int a );
static unsigned int bitrotation( unsigned int a, int order );

//-------------------------------------------------------------
void main( void ) {
//-------------------------------------------------------------
 unsigned int sData;
 unsigned int rData;
 int i;

// 0 ? 10 を変換した結果
 for( i=0 ; i<10 ; i++ ) {
 sData = funcFF( i, DEFAULT_SEED, 100 );
 rData = funcGG( sData, DEFAULT_SEED, 100 );
 printf("x = 0x%08x f(x) = 0x%08x g(f(x)= 0x%08x\n", i, sData, rData );
 }
}

//-------------------------------------------------------------
// funcF を n 回実行
//-------------------------------------------------------------
static unsigned int funcFF( unsigned int a, unsigned int s, int n ){
//-------------------------------------------------------------
 unsigned int t;
 int i;
 t = a;
 for( i=0 ; i<n ; i++ ) {
 t = funcF( t, s );
 }
 return ( t );
}

//-------------------------------------------------------------
// funcFF の逆関数
//-------------------------------------------------------------
static unsigned int funcGG( unsigned int a, unsigned int s, int n ){
//-------------------------------------------------------------
 unsigned int t;
 int i;
 t = a;
 for( i=0 ; i<n ; i++ ) {
 t = funcG( t, s );
 }
 return ( t );
}

//-------------------------------------------------------------
// バイトごとに異なる演算をする関数
//-------------------------------------------------------------
static unsigned int funcF( unsigned int a, unsigned int s ){
//-------------------------------------------------------------
 unsigned int t;
 t = bitreverse( a );
 t ^= s;
 t = bitops( t );
 t = bitrotation( t, TO_RIGHT );
 return ( t );
}

//-------------------------------------------------------------
// 逆関数
//-------------------------------------------------------------
static unsigned int funcG( unsigned int a, unsigned int s ){
//-------------------------------------------------------------
 unsigned int t;
 t = bitrotation( a, TO_LEFT );
 t = bitops( t );
 t ^= s;
 t = bitreverse( t );
 return ( t );
}

//-------------------------------------------------------------
// バイトごとに処理をする
//-------------------------------------------------------------
static unsigned int bitops( unsigned int a ) {
//-------------------------------------------------------------
 unsigned int t;
 t = ( ( 0x00000055 & a ) << 1 ) | ( ( 0x000000aa & a ) >> 1 ) ; // 1st Byte :偶数ビットと奇数ビットを入れ替え
 t |= ( ( ( 0x00000f00 & a ) << 4 ) | ( ( 0x0000f000 & a ) >> 4 ) ); // 2nd Byte :4ビットローテーション
 t |= ( 0x00ff0000 & (~a) ); // 3rd Byte :ビット反転
 t |= 0xff000000 & a; // 4th Byte :そのまま
 return( t );
}

//-------------------------------------------------------------
// 下位ビットと上位ビットを入れ替え
//-------------------------------------------------------------
static unsigned int bitreverse( unsigned int a ) {
//-------------------------------------------------------------
 unsigned int t = 0;
 int i;
 for( i=0 ; i<16 ; i++ ) {
 t |= ( ( ( 0x00000001 << i ) & a ) << ( 31 - i * 2 ) );
 t |= ( ( ( 0x80000000 >> i ) & a ) >> ( 31 - i * 2 ) );
 }
 return( t );
}

//-------------------------------------------------------------
// ローテーション
//-------------------------------------------------------------
static unsigned int bitrotation( unsigned int a, int order ) {
//-------------------------------------------------------------
 unsigned int t;
 int i;

 t = a;
 for( i=0 ; i<32 ; i++ ) {
 if( ( 0x00000001 << i ) & a ) {
 if ( order == TO_LEFT ) {
 t = ( t << 1 ) | ( ( t & 0x80000000 ) ? 0x00000001 : 0L );
 } else {
 t = ( t >> 1 ) | ( ( t & 0x00000001 ) ? 0x80000000 : 0L );
 }
 }
 }
 return( t );
}
◎質問者からの返答

ありがとうございます!

1bitの変化で複数bitが変化していますね。

単純なbit演算の組み合わせではこうはならないような気がしていたのですが、できているようですね。

なぜだろう。。。

よろしければなぜそうなったのか解説していただけませんか?

関連質問


●質問をもっと探す●



0.人力検索はてなトップ
8.このページを友達に紹介
9.このページの先頭へ
対応機種一覧
お問い合わせ
ヘルプ/お知らせ
ログイン
無料ユーザー登録
はてなトップ