[解決済み] IDの難読化

質問

整数のIDを別の整数に暗号化/難読化する方法を探しています。より正確には、私は関数を必要とします int F(int x) という関数が必要です。

• x<->F(x) は一対一対応（x != yならF(x) != F(y))
• F(x)が与えられれば、xを見つけるのは簡単である - したがってFはハッシュ関数でない
• x と F(x) が与えられると、F(y) を見つけるのは難しい/不可能、といったところでしょうか。 x ^ 0x1234 ではうまくいきません。

分かりやすくするために、私は強力な暗号化ソリューションを求めているわけではなく、あくまで難読化なのです。以下のようなURLを持つWebアプリケーションを想像してみてください。 example.com/profile/1 , example.com/profile/2 などです。プロフィール自体は秘密ではありませんが、気軽にプロフィールを見たり取得したりするのを防ぎたいので、以下のようなもので隠したいです。 example.com/profile/23423 , example.com/profile/80980234 などです。データベースに格納されたトークンは非常に簡単に仕事をすることができますが、このために利用できる簡単な数学があるのかどうか気になります。

私が明確にしていなかった1つの重要な要件は、結果が "random"に見えるべきであるということです。 x,x+1,...,x+n , F(x),F(x+1)...F(x+n) は、いかなる種類の進行も形成してはいけません。

どのように解決するのですか？

2～3種類の簡単な方法を組み合わせて難読化する。

• XOR
• 個々のビットをシャッフルする
• モジュール表現に変換する (D.Knuth, Vol. 2, Chapter 4.3.2)
• 32（または64）ビットの重複するサブセットを選択し、各サブセットでビットをXOR（サブセットのパリティビット）する
• 可変長の数字システムでそれを表現し、数字をシャッフルする。
• 奇数整数の組を選ぶ x と y は，互いに乗法的な逆数である（モジュロ2 ³² を乗算します。 x を掛けて難読化し y で復元すると、すべての乗算はモジュロ 2 になります。 ³² (ソース Eric Lippert による "乗法的逆数の実用的な使用" 。 )

可変長整数システム方式は、それ自体では、あなたの要求する "progression"に従いません。それは常に短い算術進行を生成します。しかし、他の方法と組み合わせた場合は、良い結果が得られます。

モジュール表現法についても同じことが言えます。

これら3つの手法のC++コード例です。シャッフルビットの例では、より予測不可能にするために、いくつかの異なるマスクと距離を使用することができます。他の2つの例は小さい数字に適しています(アイデアを与えるだけです)。これらは、すべての整数値を適切に難読化するために拡張されるべきです。

// *** Numberic system base: (4, 3, 5) -> (5, 3, 4)
// In real life all the bases multiplied should be near 2^32
unsigned y = x/15 + ((x/5)%3)*4 + (x%5)*12; // obfuscate
unsigned z = y/12 + ((y/4)%3)*5 + (y%4)*15; // restore

// *** Shuffle bits (method used here is described in D.Knuth's vol.4a chapter 7.1.3)
const unsigned mask1 = 0x00550055; const unsigned d1 = 7;
const unsigned mask2 = 0x0000cccc; const unsigned d2 = 14;

// Obfuscate
unsigned t = (x ^ (x >> d1)) & mask1;
unsigned u = x ^ t ^ (t << d1);
t = (u ^ (u  >> d2)) & mask2;
y = u ^ t ^ (t << d2);

// Restore
t = (y ^ (y >> d2)) & mask2;
u = y ^ t ^ (t << d2);
t = (u ^ (u >> d1)) & mask1;
z = u ^ t ^ (t << d1);

// *** Subset parity
t = (x ^ (x >> 1)) & 0x44444444;
u = (x ^ (x << 2)) & 0xcccccccc;
y = ((x & 0x88888888) >> 3) | (t >> 1) | u; // obfuscate

t = ((y & 0x11111111) << 3) | (((y & 0x11111111) << 2) ^ ((y & 0x22222222) << 1));
z = t | ((t >> 2) ^ ((y >> 2) & 0x33333333)); // restore