混淆ID

Question

混淆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等等.虽然数据库存储的令牌可以很容易地完成工作,我很好奇是否有一些简单的数学可用于此.

我不清楚的一个重要要求是结果看起来应该是"随机的",也就是说,给定一个序列x,x+1,...,x+n,F(x),F(x+1)...F(x+n)不应该形成任何类型的进展.

Answer 1

Evg*_*uev 39

使用2或3种简单方法的组合对其进行模糊处理:

XOR
洗牌个别位
转换为模块化表示(D.Knuth,第2卷,第4.3.2章)
选择32(或64)个重叠的子集和每个子集中的XOR位(子集的奇偶校验位)
用可变长度的数字系统和随机数字表示它
选择一对奇数整数x,y它们是彼此的乘法逆(模2 ³²),然后乘以x混淆并乘以y恢复,所有乘法都是模2 ³²(来源:"乘法反转的实际用法"由Eric Lippert)

可变长度数字系统方法本身不符合您的"进展"要求.它总是产生短的算术进展.但是当与其他方法结合使用时,它会产生很好的效果.

模块化表示方法也是如此.

以下是其中3种方法的C++代码示例.随机比特示例可以使用一些不同的掩模和距离以使其更加不可预测.其他两个例子对小数字很有用(只是为了给出这个想法).应该扩展它们以正确地混淆所有整数值.

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

Run Code Online (Sandbox Code Playgroud)

@ thg435我使用C++而不是伪代码.不想给出未经考验的例子. (3认同)

Answer 2

ros*_*sum 9

您希望转换是可逆的,而不是显而易见的.这听起来像是一个加密,它在给定范围内取一个数字,并在同一范围内产生不同的数字.如果您的范围是64位数,则使用DES.如果您的范围是128位数,则使用AES.如果你想要一个不同的范围,那么你最好的选择可能是Hasty Pudding密码,它设计用于处理不同的块大小和数字范围,不适合整块,如100,000到999,999.

Answer 3

IAm*_*NaN 6

在安全性方面,混淆不够.

但是,如果你试图阻止随意的旁观者,我建议结合使用两种方法:

通过xor将它们组合在一起的私钥
在应用密钥之前和之后将位旋转一定量

这是一个例子(使用伪代码):

  def F(x)
    x = x XOR 31415927       # XOR x with a secret key
    x = rotl(x, 5)           # rotate the bits left 5 times
    x = x XOR 31415927       # XOR x with a secret key again
    x = rotr(x, 5)           # rotate the bits right 5 times
    x = x XOR 31415927       # XOR x with a secret key again
    return x                 # return the value
  end

Run Code Online (Sandbox Code Playgroud)

我还没有对它进行过测试,但我认为这是可逆的,应该是快速的,并且不容易梳理出这种方法.

更糟糕的是，很容易证明任何以恒定偏移量旋转的链和具有常数的异或可以压缩为仅一个旋转和一个异或。可以组合彼此之后的两个旋转（添加它们的偏移量），可以组合彼此之后的两个异或（异或与两个常数的异或），并且可以通过将相同的旋转应用到 rot/xor 对 xor/rot 对交换到 rot/xor异或中的常数。 (2认同)

Answer 4

mir*_*e2k 5

我发现这段特定的Python / PHP代码非常有用：

https://github.com/marekweb/opaque-id

Answer 5

mpe*_*pen 5

我使用这个线程中的一些想法编写了一些 JS 代码：

const BITS = 32n;
const MAX = 4294967295n;
const COPRIME = 65521n;
const INVERSE = 2166657316n;
const ROT = 6n;
const XOR1 = 10296065n; 
const XOR2 = 2426476569n;


function rotRight(n, bits, size) {
    const mask = (1n << bits) - 1n;
    // console.log('mask',mask.toString(2).padStart(Number(size),'0'));
    const left = n & mask;
    const right = n >> bits;
    return (left << (size - bits)) | right;
}

const pipe = fns => fns.reduce((f, g) => (...args) => g(f(...args)));

function build(...fns) {
    const enc = fns.map(f => Array.isArray(f) ? f[0] : f);
    const dec = fns.map(f => Array.isArray(f) ? f[1] : f).reverse();

    return [
        pipe(enc),
        pipe(dec),
    ]
}

[exports.encode, exports.decode] = build(
    [BigInt, Number],
    [i => (i * COPRIME) % MAX, i => (i * INVERSE) % MAX],
    x => x ^ XOR1,
    [x => rotRight(x, ROT, BITS), x => rotRight(x, BITS-ROT, BITS)],
    x => x ^ XOR2,
);

Run Code Online (Sandbox Code Playgroud)

它产生了一些不错的结果，例如：

1 1352888202n 1 'mdh37u'
2 480471946n 2 '7y26iy'
3 3634587530n 3 '1o3xtoq'
4 2225300362n 4 '10svwqy'
5 1084456843n 5 'hxno97'
6 212040587n 6 '3i8rkb'
7 3366156171n 7 '1jo4eq3'
8 3030610827n 8 '1e4cia3'
9 1889750920n 9 'v93x54'
10 1017334664n 10 'gtp0g8'
11 4171450248n 11 '1wzknm0'
12 2762163080n 12 '19oiqo8'
13 1621319561n 13 'qtai6h'
14 748903305n 14 'cdvlhl'
15 3903018889n 15 '1sjr8nd'
16 3567473545n 16 '1mzzc7d'
17 2426613641n 17 '144qr2h'
18 1554197390n 18 'ppbudq'
19 413345678n 19 '6u3fke'
20 3299025806n 20 '1ik5klq'
21 2158182286n 21 'zoxc3y'
22 1285766031n 22 'l9iff3'
23 144914319n 23 '2ea0lr'
24 4104336271n 24 '1vvm64v'
25 2963476367n 25 '1d0dkzz'
26 2091060108n 26 'ykyob0'
27 950208396n 27 'fpq9ho'
28 3835888524n 28 '1rfsej0'
29 2695045004n 29 '18kk618'
30 1822628749n 30 'u559cd'
31 681777037n 31 'b9wuj1'
32 346231693n 32 '5q4y31'

Run Code Online (Sandbox Code Playgroud)

测试：

  const {encode,decode} = require('./obfuscate')

  for(let i = 1; i <= 1000; ++i) {
        const j = encode(i);
        const k = decode(j);
        console.log(i, j, k, j.toString(36));
   }

Run Code Online (Sandbox Code Playgroud)

XOR1和XOR2只是 0 和之间的随机数MAX。MAX是2**32-1; 您应该将其设置为您认为最高的 ID。

COPRIME是一个与/互质的数字MAX。我认为质数本身与其他所有数字互质（除了它们自己的倍数）。

INVERSE是一个很难弄清楚的问题。这些博客文章没有给出直接答案，但WolframAlpha 可以为您找到答案。基本上，只需求解的方程(COPRIME * x) % MAX = 1即可x。

我创建该build函数是为了更轻松地创建这些编码/解码管道。您可以成对地向其提供任意数量的操作[encode, decode]。这些函数必须相等且相反。这些XOR功能是它们自己的补充，因此您不需要一对。

这是另一个有趣的内卷：

function mixHalves(n) {
    const mask = 2n**12n-1n;
    const right = n & mask;
    const left = n >> 12n;
    const mix = left ^ right;
    return (mix << 12n) | right;
}

Run Code Online (Sandbox Code Playgroud)

（假设 24 位整数——只需将数字更改为任何其他大小）

归档时间：	13 年，12 月前
查看次数：	19042 次
最近记录：	6 年，8 月前