混淆ID [英] Obfuscating an ID

问题描述

我正在寻找一种将整数ID加密/模糊化为另一个整数的方法。更确切地说，我需要一个函数 int F（int x），这样

I'm looking for a way to encrypt/obfuscate an integer ID into another integer. More precisely, I need a function int F(int x), so that

• 
  < ，很容易找出x - 所以F不是哈希函数


• 给定x和F（x）很难/不可能找出F（y），像 x ^ 0x1234 将无法正常工作

• x<->F(x) is one-to-one correspondence (if x != y, F(x) != F(y))
• given F(x), it's easy to find out x - so F is not a hash function
• given x and F(x) it's hard/impossible to find out F(y), something like x ^ 0x1234 won't work

为了清楚起见，我不是在寻找强大的加密解决方案，它只是混淆。想象一下，像 example.com/profile/1 ， example.com/profile/2 等网址的网络应用程序个人资料本身并不秘密，但我想防止休闲的voyeurs一个接一个地查看/获取所有的个人资料，所以我宁愿把它们隐藏在一些像 example.com/profile/23423 ， example.com/profile/80980234 等。虽然数据库存储的令牌可以很容易地完成这个工作，但我很好奇，如果有一些简单的数学

For clarity, I'm not looking for a strong encryption solution, it's only obfuscation. Imagine a web application with urls like example.com/profile/1, example.com/profile/2 etc. The profiles themselves are not secret, but I'd like to prevent casual voyeurs to view/fetch all profiles one after another, so I'd rather hide them behind something like example.com/profile/23423, example.com/profile/80980234 etc. Although database-stored tokens can do the job quite easily, I'm curious if there's some simple math available for this.

我不清楚的一个重要要求是结果应该看起来是随机的，也就是给定一个序列 x ，x + 1，...，x + n ， F（x），F（x + 1）... F（x + n） $ c>不应该形成任何形式的进展。

One important requirement I wasn't clear about is that results should look "random", that is, given a sequence x,x+1,...,x+n , F(x),F(x+1)...F(x+n) shouldn't form a progression of any kind.

推荐答案

使用2或3种简单方法的组合进行混淆：

Obfuscate it with some combination of 2 or 3 simple methods:

• XOR


• shuffle个别位


• 转换为模块化表示（D.Knuth，Vol。2，Chapter 4.3.2）


• 选择32个（或64个）重叠的子集，每个子​​集中的XOR位（子集的奇偶校验位）


• 代表它在可变长度数字系统和随机数字中


• 选择一对奇数整数 x 和 y ，它们是彼此的乘法反转（模2 32 ），然后乘以 x 以模糊化并乘以$ $ c> y 恢复，所有乘法均为模2 32 （来源： Eric Lippert的乘法反转的实际用途）



• XOR
• shuffle individual bits
• convert to modular representation (D.Knuth, Vol. 2, Chapter 4.3.2)
• choose 32 (or 64) overlapping subsets of bits and XOR bits in each subset (parity bits of subsets)
• represent it in variable-length numberic system and shuffle digits
• choose a pair of odd integers x and y that are multiplicative inverses of each other (modulo 2³²), then multiply by x to obfuscate and multiply by y to restore, all multiplications are modulo 2³² (source: "A practical use of multiplicative inverses" by Eric Lippert)

可变长数字系统方法本身并不符合您的进度要求。它总是产生短的算术进程。但是，当与其他方法结合使用时，会给出很好的结果。

Variable-length numberic system method does not obey your "progression" requirement on its own. It always produces short arithmetic progressions. But when combined with some other method, it gives good results.

模块化表示法也是如此。

The same is true for the modular representation method.

这是这些方法中的3个C ++代码示例。随机播放比特示例可能使用一些不同的掩码和距离更难以预测。其他2个例子适用于小数字（只是给出想法）。它们应该被扩展到正确地模糊所有整数值。

Here is C++ code example for 3 of these methods. Shuffle bits example may use some different masks and distances to be more unpredictable. Other 2 examples are good for small numbers (just to give the idea). They should be extended to obfuscate all integer values properly.

// *** 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

这篇关于混淆ID的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！