基于有限域可逆仿射的数字ID生成方案

把一个递增序列映射为一个相同空间的乱序序列,用于乱序ID生成

基于RSA算法的性质:

  1. RSA算法涉及三个参数,n、e1、e2,其中,n是两个大质数p、q的积。
  2. 根据欧拉函数,求得 rn=(p-1)(q-1)。
  3. e1和e2是一对相关的值,e1可以任意取,但要求e1与rn互质,再选择e2,要求e1e2 ≡1(mod rn)。(模反元素e2存在,当且仅当e1与rn互质)
A=B^e1 mod n 
B=A^e2 mod n

B即为加密前的数据,A为加密后的数据,A和B是双射的,也即B通过RSA的加密算法得到唯一的A,A通过RSA解密算法获得唯一的B

例:
要求生成一个6位数字的乱序ID,则n为小于等于999999的数,这个数要求尽量接近999999,且可以分解成两个质数之积。查质数表可以找到两个质数分别为p=757, q=1321,可以使 n=999997,为保证e1与(p-1)*(q-1)(rn=997920)互质,可以取 e1=13, 11, 7 等,不要取太大的值,否则计算pow(a,e1)数值较大,CPU性能和精度不好控制,同时 pow(a,e1)% n与循环 e1-1a=(a*a0)%n的结果是一样的,后者的实现不会产生大数。
可以得到公式:A = pow(B,13) % 999997

此外,可以根据扩展欧几里得算法可以计算模反元素e2

如果不要求逆运算,可以进行简单的ID散列处理:
f(x) = (ax + b) % R, 其中a可以取一个比较大的素数,b随便找个,R是输出的id范围。

sentry = pow(10, 7)
if uid < sentry:
    uid = (uid * 2654435769) % sentry 

数学原理:

欧拉函数:
任意给定一个正整数,在小于等于n的正整数中有多少个数与n构成互质关系,这个数即为欧拉函数r。当n是质数时,r= n-1,因为质数与小于它的每一个数都构成互质关系。当n可以分解为两个互质整数p,q之积时,r=(p-1)(q-1)。

欧拉定理:
如果两个正整数a,b互质,则b的欧拉函数r保证下面等式成立:

a^r≡1(mod b) (1)

当b是质数时,r= b-1,所以欧拉定理可以改写成

a^(b-1)≡1(mod b) (2)

这个公式就是欧拉定理的特例,也就是费马小定理。

模反元素:
如果两个正整数a和n互质,那么一定可以找到一个整数b,使得 a * b≡1 (mod n),此时我们称整数b为a的模反元素。通过欧拉定理得到 a^r=aa^(r-1) ≡1 (mod n),显然a^(r-1)即为模范元素b。


转载请注明来源,欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 using1174@foxmail.com

文章标题: 基于有限域可逆仿射的数字ID生成方案

文章字数: 693

本文作者: Jun

发布时间: 2021-04-14, 21:13:51

最后更新: 2021-04-14, 22:32:30

原始链接: http://yoursite.com/2021/04/14/基于有限域可逆仿射的数字ID生成方案/

版权声明: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

目录
×

喜欢就点赞,疼爱就打赏