混淆 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) 是一一对应的(如果 x != y, F(x) != F(y))
• 给定 F(x)，很容易找出 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 等 url 的 Web 应用程序.配置文件本身不是秘密，但我想要为了防止随意的偷窥者一个接一个地查看/获取所有配置文件，所以我宁愿将它们隐藏在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) 不应形成任何形式的级数.

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:

• 异或
• 打乱单个位
• 转换为模块化表示(D.Knuth，第 2 卷，第 4.3.2 章)
• 在每个子集中选择 32 个(或 64 个)重叠的比特子集和异或比特(子集的奇偶校验比特)
• 以可变长度的数字系统表示并随机排列数字
• 选择一对奇数x和y，它们是彼此乘法的倒数(模2³²)，然后乘以x 混淆并乘以 y 恢复，所有乘法都是模 2³²(来源: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++ 代码示例.Shuffle bits 示例可能会使用一些不同的掩码和距离来更加不可预测.其他 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屋！