PHP-设计一个算法，如何将指定数字转换成另一个随机且唯一的整数？

Question

开发过程中遇到了一个问题，需要将指定的数字通过某种运算转换成另一个在系统中唯一的随机数，如：
输入：100
输出：12345678（仅为举例）

算法要求：
1、生成的数字在系统中唯一，即输入两个不同的数字不能产生相同的结果，当然，相同的输入对应相同的输出。
2、输入的数字和生成的数字大于0，且小于或等于2的32次方，即4294967296。
3、生成的数字需要有一定的随机性，即在输入的数字连续的情况下不能出现有规律的结果。如：分别输入100，101，102，不能输出12345678，12345679，12345680类似的结果。
4、在不知道输入数字的情况下，不容易被逆向工程。

先给出我自己的一些不成熟的尝试代码（PHP版本），权当抛砖引玉：

function gen_unique_id($num) {
$num = str_pad(decbin($num + 2147483648), 32, 0, STR_PAD_LEFT);
$num = substr($num, -3) . substr($num, 0, -3);
return bindec($num);
}

Answer 1

function getMcryptKey() {
return substr(md5('kill-all'),0,3); //这里key最长8位
}

//加密函数
function encrypt($encrypt) {
$iv=mcrypt_create_iv(mcrypt_get_iv_size(MCRYPT_DES,MCRYPT_MODE_ECB),MCRYPT_RAND);
$passcrypt=mcrypt_encrypt(MCRYPT_DES,getMcryptKey(),$encrypt,MCRYPT_MODE_ECB,$iv);
$encode=base64_encode($passcrypt);
return $encode;
}

//解密函数
function decrypt($decrypt) {
$decode=base64_decode($decrypt);
$iv=mcrypt_create_iv(mcrypt_get_iv_size(MCRYPT_DES,MCRYPT_MODE_ECB),MCRYPT_RAND);
$decrypted=mcrypt_decrypt(MCRYPT_DES,getMcryptKey(),$decode,MCRYPT_MODE_ECB,$iv);
return trim($decrypted);
}

试试这个吧。虽然产生的出来的类型是字符型的。其他的都满足

Answer 2

晓华的观点很正确。
要使不容易被逆向工程,对于应用程序(C/S模式)最简单的方法是加个加密壳。若不想加壳,
1.可以在代码中加入花指令(写成宏)。
2.捣乱OD和IDA分析的指令(例如int 2d指令,默认反汇编引擎会跳过其后的一条指令不做分析。还有就是使得数据与指令混淆,使得反汇编引擎不能很好的分析指令)。
3.加入反调试手段。
但是这些也可以被脱壳、反反调试以及去除花指令。这个需要很强的逆向功底了。
对于WEB程序,指令在服务端,不需要抵御逆向工程。需要注意的是客户端JS、VBS脚本可以被利用,以及关键算法协议要做加密,不然很容易被抓包分析。

“将指定数字转换成另一个随机且唯一的整数”，使用时间为种子的随机数，然后做散列。

Answer 3

我没做过加密，也对算法不熟悉。不过这个我有个想法不知道能不能行得通。基本做法为：
1. 即然为32位，那么换算成16进制也就是8位了。
2. 首先将16进制的数字以hash表的方式随机产生一一映射表[0,15].
3. 将一共有8位，那么跟第二步一样，随机生成一一映射表[0,8].
4. 先后将其两个hash表进行组合.即可以得到一个新的唯一数，下面举个假设例子来进行说明.
数字hash映射(0->7,1->a,2->1,3->6,4->8,5->2,6->f,7->c,8->0，9->e,a->9,b->3,c->b,d->5,e->4,f->d)
位置hash映射(0->7,1->3,2->6,3->5,4->0,5->2,6->1,7->4)
那么如整数:0x04 56 79 00 ->0x 0e c0 02 8f
总之我的想法就是通过多次简单的单一映射来解决这个问题。还有一点，如果是在java（不知道php有没有)中产生随机数时可以添加一个seed，那么如果在每次软件启动的时候随机产生前设置一个seed并对其进行保存的话，那么就能保证这数据能被反解了。当然这个seed又可以按照特定的方式加密。

Answer 4

md5转化，简单而有效

Answer 5

用进制算法，就比如你数字是100，取一个随机数64，那么只要将100看成是64进制下的数，并将100转换为10进制即可。甚至可以在取一个随机数将64进制下的100转换为这个随机数的进制，而且绝对不会重复，取一个或两个随机数即可达到目标。
如果要不容易被逆向的话，还可以多加几层，比如通过两次这样的转换后得到数N,取一个随机数a,然后再取一个随机数b,再取一个随机数c,将N进制转换为a的进制数n,再将n看成是b的进制转换为c的进制。
ps:建议最好从24个特定数里随机抽取16个数，以不同进制转换次序进行加密，这样出来的密钥就会像这样：****-****-****-****,如果需要给些特定用户看见，那就再用一个"密码本",用英文字母把数字掩盖。

这些随机数可以构成一个密钥，一般只要不知道加密方法以及密钥还有进制次序和其中的详细过程就无法破解其中的数字。

Answer 6

看要求是要做一个32bit到32bit的一一映射。直接用随机数打乱一个2^32个数的数表当对应表当然最安全了，几乎不可能被逆向（除非把全部2^32穷举一遍）。但是通常2^32这么大的表内存消耗是不可接受的。所以只能用一些退而求其次的办法。
最容易想到的就是2^32的表不能接受，2^8还是能接受的，做一个256个元素的字节映射表，然后分别把四个字节映射到另外的四个字节。但是用户会很容易发现字节到字节的对应关系，所以还需要进一步的组合。
这一步需要线性代数和布尔代数的知识。将32bit数看做一个32维向量，元素是0和1，将它乘上一个3232的布尔矩阵（全是0和1的矩阵），得到新的32维向量。运算时用以下规则：
a * b = a & b
a + b = a ^ b
即乘法用与来代替，加法用异或来代替。
可以证明如果3232的布尔矩阵是可逆的（行列式值为1），这个变换就是一一对应的。因为行列式值非0即1，所以基本上随机生成两个矩阵中就有一个是可逆的。计算行列式的算法和程序到处都有，任何一本数学教材上都有介绍（高斯消去法），也可以用matlab之类的工具，当作整数矩阵来算，算完之后看行列式值是奇数还是偶数就行。
将前一步映射变换后的结果乘上一个特定的可逆矩阵，得到的就是最终结果。因为两次映射都是一一映射，所以最终的映射关系也是一一映射；由于不知道映射表和矩阵（约有2^17种组合），逆向相当困难；当然随机性也是能保证的。
知道矩阵和变换表之后这种变换也可以很容易求逆，首先乘上变换矩阵的逆矩阵（求逆的算法到处都有），然后查反向的映射表对应回原来的数。

如果在第一步映射前乘上另一个可逆矩阵，组合数（可能）会增加到2^26此方量级，就更难被逆向了。如果对不同字节采用不同的映射表，或者分组映射的bit数不同（拆成3,4,4,3,4,5,4,5bit之类的），变化还可以更多。总体上是相当安全的。

要注意的是，单独用变换矩阵、或者映射过于简单（比如和某个数异或），会导致映射关系容易被破解，因为矩阵变换是一个线性变换，异或也是线性变换，这样总的对应关系就会变成线性的：
f(a ^ b) = f(a) ^ f(b)
这样逆向工程时不需要知道具体的参数，只需要分别计算出
2^0, 2^1, ..., 2^31对应的数，然后将对应的bit组合起来就能知道变换后的数值。

Answer 7

第4条也是很难满足的。
要求同样的输入返回同样的输出，但是输出的范围太小，只有0-4294967296，这个不论你怎么写，都很容易被逆向工程。

Answer 8

如果使用hash的话很容易被反向工程，如果你要让算法不那么容易反向工程，建议你使用不对称加密，找两个素数p，q，这两个素数相乘得到N，小于2的23次方。然后计算M=(p-1)*(q-1),找到和M的互质的一个数e，然后将要变换数X取它的e次方对N取模。这是个很有名的算法，要从结果算回去是不太可能的，然后你怕结果出现两个数相同的情况，你再hash一下就行了，一般情况下是不可能的。

Answer 9

那不是靠电脑伪随机么……可汗学院密码学入门看下或者写个x次幂取中间某几位的……
http://www.guokr.com/blog/327469/
RSA算法

Answer 10

我们来分析分析这个问题的几个条件：
第一条，规定了这个算法是确定性的算法，--随机不确定性的算法可以over了。
并且在Z+上对自身的1对1的满射，SHA、MD5这种算法不能严格保证这一点。
第二条，我去，直接给定范围了，这个范围其实还不太大。
综合上一条的意思就是，在这个有限的范围内，不管中间的算法是什么，
实际上都可以列出来一个表，两列，左边是这个范围的所有数，右边也是，
把左边的每一个画一个箭头到右边。

第三条规定这些箭头不能是局部或整体有序的，就是不能出现简单的重复模式。
根据拉姆齐理论，局部有序是必然存在、无法避免的。只能出现尽量少的局部有序。
最后一条是说知道这个算法（算法中存在未知的参数和其他干扰），也不容易通过密文得到原文。
这条是很难做到的，基本上来说，只要我知道算法，在这个有限的解空间，多试错几次，
一定能把未知的参数和干扰条件给算出来，从而破解算法。
只是未知参数和干扰的多少，影响破解的难度。
除非我连算法都不知道。

如果算法别人都不知道，那可靠点的算法就很多了，其中最没有技术含量可能也是最无法破解的就是：把这43亿数字，随机打乱，存到文件里。输入的几，就根据把这个数字当做offset去文件里读。

Answer 11

关于逆向工程不容易被解密，有一个方法就是加上混沌，也就是单向映射函数f(x)->y，并且当x的值变动较小的时候，y的值变化很大

Answer 12

简单的方法应该有不少,比如先随机取个32位的二进制数做异或(当然自己得记住),然后再这32个0和1做些置换操作,即把第5位的挪到第17位上,第17位的挪到第8位上之类的...

至于不容易被逆向,个人不太理解.如果是对方可以解析你的代码,那么只能是寄希望于这个方程你会解,对方不会解吧...这让我想起了用一元三次方程比赛的年代,在当下好像就太难了.

Answer 13

代码我就不给出了，我说一下大概思路
1.对输入数字进行hash运算，目的是产生可保证唯一性的hash数
2.对hash数做有规律的位运算，如取hash数的1，3，5，7位组合一个新的seed，根据这个seed把相应的2,4,6,8位做替换。（算法可以自己灵活控制）

这个算法比较简单，效率较高，并且具有一定的随机性，也不容易被逆向，适合目前你给出的要求

Answer 14

或许可以试试类似AES的算法？把32位整数的各个位放到块里然后做变换