あれば教えてください。
条件：(優先度順です)
どのようなx1,x2(x1!=x2)をとってもf(x1)==f(x2)にならない。（衝突しない）
g(y)=xとなる関数gがある。
seedの推測が困難。
f(x,seed)とseedを渡すと別系統の関数f2(x)になる。
計算量が少ない。
x,yは4byteのint
説明不十分な点があると思いますが
コメントにて補足しますので、よろしくお願いします。
No.1
3542
140
No.2
867
23pt
ということから，
これは，「最小完全ハッシュ関数」ということになると思います．
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というのは具体的なハッシュ関数の変更ということになると思いますが，これができるかどうかは調べていません．
また，逆関数というのも難しいことだと思います．
などでも色々とやっているようですが，結局すべてのハッシュ値を記録して総当りをやっているみたいですし．
ありがとうございます。
ハッシュ関数というものがそもそも逆関数を求めることが難しいものなのですよね？
ハッシュ関数ではない関数で、ないですかねえ。
乱数列とかが関係あるかなあと思い始めました。
No.3
1314393
22pt
コメントの内容を実装してみました。
言語の指定がなかったので、C(Borland C) で書いています。
DEFAULT_SEED の部分を変えれば、異なる結果になります。
90
81
#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 ) );
}
// １バイト目は偶数ビットと奇数ビットを入れ替え
t2 = ( ( 0x00000055 & t1 ) << 1 ) | ( ( 0x000000aa & t1 ) >> 1 ) ;
// ２バイト目は４ビットローテーション
t2 |= ( ( ( 0x00000f00 & t1 ) << 4 ) | ( ( 0x0000f000 & t1 ) >> 4 ) );
// ３バイト目はビット反転
t2 |= ( 0x00ff0000 & (~t1) );
// ４バイト目はそのまま
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;
// １バイト目は偶数ビットと奇数ビットを入れ替え
t1 = ( ( 0x00000055 & a ) << 1 ) | ( ( 0x000000aa & a ) >> 1 ) ;
// ２バイト目は４ビットローテーション
t1 |= ( ( ( 0x00000f00 & a ) << 4 ) | ( ( 0x0000f000 & a ) >> 4 ) );
// ３バイト目はビット反転
t1 |= ( 0x00ff0000 & (~a) );
// ４バイト目はそのまま
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 );
}
実行結果はこんな感じです。
０～４の実行結果
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
これを並べてみると１番左の部分が変わって
いっているので(7,f,3,b,5)簡単に規則性が推測できてしまうようです。
1bit変わっただけでハッシュ関数のように複数のbitに影響があるような関数はないでしょうか。
4byteから4byteを出力する最小完全ハッシュ関数を見つけてx=g(y)はテーブルを作って対応ですかねえ。4byte*4294967295=17G...になっちゃいますねえ。
No.4
1314393
22pt
既存の技術を探せばあるとは思いますが、先ほどのものを拡張してみました。
処理結果から
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
基本は先に提示したものですが、処理を繰り返すことで複雑にしています。
ビット演算による処理の利点は、逆関数は逆の順序で処理をしていけば作成できる点です。
一回の処理では推測できそうな場合でも、複数回処理を重ねることで結果を複雑にすることができます。
上記の結果は４種類の処理を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演算の組み合わせではこうはならないような気がしていたのですが、できているようですね。
なぜだろう。。。
よろしければなぜそうなったのか解説していただけませんか？
urekat
2007/08/08 18:12:57
Mook
wasisan
1
1
逆方向変換ができる
入力も出力も同じ長さ(4byte)
のハッシュがあればそれです。でもそれってハッシュっていうのかな。
bit反転、bitシフト、bit入替を組み合わせればそれなりになりそうですが、「推測が困難」の点がクリアできなさそうです。