以下のような条件を満たす関数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

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

回答の条件
  • 1人5回まで
  • 登録:2007/08/08 18:11:12
  • 終了:2007/08/15 18:15:03

回答(4件)

id:KUROX No.1

KUROX回答回数3542ベストアンサー獲得回数1402007/08/08 18:20:37

id:urekat

逆方向変換ができる

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

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

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

2007/08/08 18:25:41
id:wasisan No.2

wasisan回答回数86ベストアンサー獲得回数72007/08/08 19:55:13

ポイント23pt
  • 4byteから4byteの値に変換(⇔ 4294967296通りのキーを,0から4294967295の間の数にマップする)
  • 衝突がない

ということから,

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

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/

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

id:urekat

ありがとうございます。

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

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

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

2007/08/08 20:24:26
id:Mook No.3

Mook回答回数1312ベストアンサー獲得回数3912007/08/09 02:24:14

ポイント22pt

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


言語の指定がなかったので、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)

ご参考までに

id:urekat

ありがとうございます。

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...になっちゃいますねえ。

2007/08/09 09:34:48
id:Mook No.4

Mook回答回数1312ベストアンサー獲得回数3912007/08/09 12:02:37

ポイント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

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

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


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

上記の結果は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 );
}
id:urekat

ありがとうございます!

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

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

なぜだろう。。。

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

2007/08/09 12:59:03
  • id:urekat
    ん、bit演算、bitシフトでいいのか。。。
  • id:Mook
    seed の意味がわかりませんが、bit 反転するだけでも目的の関数として使えませんか?
  • id:urekat
    単なるbit反転よりは強いものがないかと思っています。
    ビット演算のみで構成された関数だとf(1)とf(0)を比較すれば1bit目はどこか簡単にわかってしまうので。同様に他のbitもわかってしまいます。あちゃー。
  • id:Mook
    適当なビット列を用意し、 XOR をかけてあげれば、少しはわかりづらくなりませんか。

    それで不満であったら、バイト単位で処理を加えてそれから、XORをかけたら?

    例えば、一バイト目は反転、2バイト目はローテーション、・・・のようにして最後に 上記のXOR とか。
  • id:wasisan
    上ではハッシュ関数のことを書いてしまいましたが,
    結局,求めているものは「暗号化と複合化」ということ
    になる気がします.Mookさんが言っている方法は

    バーナム暗号 - Wikipedia:
    http://ja.wikipedia.org/wiki/%E3%83%90%E3%83%BC%E3%83%8A%E3%83%A0%E6%9A%97%E5%8F%B7

    のことだと思います.

    この辺りについては私は詳しくないので,これで質問の回答は終わりとします.
  • id:urekat
    32bitのブロック暗号があればOKな気がしてきました。
    なければかわりに64bitで。
  • id:Mook
    2回目の回答のコメントに関して、補足です。

    今回のキーはローテーションと、処理の繰り返しです。
    今回の変更で bitrotation の関数を追加していますが、これはビット数だけ、全体をずらしています。
    これによって、元の数値変化が少なくとも、結果の数値全体が大きく変わります。

    ただ、1のビット数が同じ場合、それでも形が似てきてしまいますので、これを回避するために、処理を複数回(例では100回)繰り返しています。
    それによって、小さい変化を積み重ねて大きな変化にしています。
  • id:urekat
    なるほど「1になっているのbitの数」の分ずらすのですね。
    複合化するときも「1になっているのbitの数」は変わらないので
    逆方向にずらせば元に戻るのですね。
    ありがとうございます!!

この質問への反応(ブックマークコメント)

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません