我想生成优惠券代码,例如AYB4ZZ2。但是,我也想能够标记已使用的优惠券并限制其全球数量N。天真的方法类似于 “生成N唯一的字母数字代码,将其放入数据库中,并对每个优惠券操作执行db搜索”。
AYB4ZZ2
N
但是,据我所知,我们还可以 尝试找到一个函数 MakeCoupon(n),该 函数 将给定的数字转换为具有预定义长度的类似优惠券的字符串。
MakeCoupon(n)
据我了解,MakeCoupon应满足以下要求:
MakeCoupon
是双射的。它的逆MakeNumber(coupon)应该是可有效计算的。
MakeNumber(coupon)
的输出MakeCoupon(n)应为字母数字,并且应具有较小且 恒定的 长度-以便可以将其称为 人类可读的 。例如SHA1摘要将无法通过此要求。
SHA1
实用的独特性。MakeCoupon(n)每种自然结果的n <= N完全或唯一性都应与唯一性相同,例如MD5唯一性(具有相同的极小碰撞概率)。
n <= N
MD5
(定义起来很棘手) 如何从一个优惠券代码中枚举所有剩余的优惠券应该不是很明显-可以说MakeCoupon(n)并且MakeCoupon(n + 1)应该在视觉上有所不同。
MakeCoupon(n + 1)
例如MakeCoupon(n),,仅输出n填充了零的输出将无法满足此要求,因为000001并且000002实际上并没有“视觉上的”差异。
MakeCoupon(n),
n
000001
000002
是否存在满足以下要求的函数或函数生成器? 我的搜索尝试仅将我引导至[CPAN]CouponCode,但没有满足相应功能为双射的要求。
[CPAN]
基本上,您可以将操作分为几部分:
对于步骤1,我建议使用简单的分组密码(例如,具有您选择的舍入函数的Feistel密码)。
Feistel密码进行了数 回合 工作。在每个回合中,将一些 回合函数 应用于输入的一半,结果xor与另一半相乘,并且交换两半。关于Feistel密码的好处是,舍入函数不必是双向的(舍入函数的输入在每次舍入之后都保持不变,因此可以在解密过程中重建舍入函数的结果)。因此,您可以选择喜欢的任何疯狂操作:)。Feistel密码也是对称的,可以满足您的第一个要求。
xor
C#中的简短示例
const int BITCOUNT = 30; const int BITMASK = (1 << BITCOUNT/2) - 1; static uint roundFunction(uint number) { return (((number ^ 47894) + 25) << 1) & BITMASK; } static uint crypt(uint number) { uint left = number >> (BITCOUNT/2); uint right = number & BITMASK; for (int round = 0; round < 10; ++round) { left = left ^ roundFunction(right); uint temp = left; left = right; right = temp; } return left | (right << (BITCOUNT/2)); }
(请注意,在最后一轮之后没有交换,在代码中,交换只是在结果构造中撤消了)
除了满足您的需求3和4(函数是 合计的 ,因此对于不同的输入,您将获得不同的输出,并且根据您的非正式定义,输入“完全加扰”)也是它自己的逆(因此隐含地满足要求1),即crypt(crypt(x))==x对于x输入域中的每个域(0..2^30-1在此实现中)。就性能要求而言,它也很便宜。
crypt(crypt(x))==x
x
0..2^30-1
对于步骤2,只需将结果编码为您选择的基础即可。例如,要编码30位数字,可以使用32个字母的字母表中的6个“数字”(因此,可以编码6 * 5 = 30位)。
C#中此步骤的示例:
const string ALPHABET= "AG8FOLE2WVTCPY5ZH3NIUDBXSMQK7946"; static string couponCode(uint number) { StringBuilder b = new StringBuilder(); for (int i=0; i<6; ++i) { b.Append(ALPHABET[(int)number&((1 << 5)-1)]); number = number >> 5; } return b.ToString(); } static uint codeFromCoupon(string coupon) { uint n = 0; for (int i = 0; i < 6; ++i) n = n | (((uint)ALPHABET.IndexOf(coupon[i])) << (5 * i)); return n; }
对于输入0-9,将产生以下优惠券代码
0 => 5VZNKB 1 => HL766Z 2 => TMGSEY 3 => P28L4W 4 => EM5EWD 5 => WIACCZ 6 => 8DEPDA 7 => OQE33A 8 => 4SEQ5A 9 => AVAXS5
请注意,此方法有两个不同的内部“秘密”:首先是round函数以及所用的回合数,其次是用于对加密结果进行编码的字母。还请注意,从密码学的角度来看,所示的实现绝不是安全的!
还要注意,从某种意义上说,所示函数是一个 整体双射 函数,每个可能的6个字符的代码(字母之外的字符)都会产生一个唯一的数字。为防止任何人仅输入一些随机代码,应在输入数字上定义某种限制。例如,只发行前10.000个号码的优惠券。然后,一些随机优惠券代码有效的概率将为10000/2 ^ 30 = 0.00001(这将需要大约50000次尝试才能找到正确的优惠券代码)。如果您需要更多的“安全性”,则可以增加位大小/优惠券代码长度(请参见下文)。
编辑:更改优惠券代码长度
更改最终优惠券代码的长度需要一些数学运算:第一步(加密)仅适用于具有偶数计数的位字符串(这对于Feistel密码有效)。
在第二步中,可以使用给定字母编码的位数取决于所选字母的“大小”和优惠券代码的长度。通常,以比特为单位的“熵”不是整数,远小于偶数。例如:
使用30个字符的字母的5位代码产生30 ^ 5个可能的代码,这意味着 ld(30 ^ 5)= 24.53 位/优惠券代码。
对于四位数代码,有一个简单的解决方案:给定32个字符的字母,您可以编码 ld(32 ^ 4)= 5 * 4 = 20 位。因此,您只需将设置BITCOUNT为20并更改for 代码第二部分中的循环即可运行,直到4(而不是6)
BITCOUNT
for
4
6
生成五位数字的代码有点棘手,并且会“弱化”算法:您可以将设置BITCOUNT为24,然后仅从30个字符的字母表中生成5位数字的代码(从ALPHABET字符串中删除两个字符并让for循环运行直到5)。
ALPHABET
5
但这不会生成所有可能的5位代码:使用24位,您只能从加密阶段获得16,777,216个可能的值,这5位代码可以编码24,300,000个可能的数字,因此将永远不会生成某些可能的代码。更具体地说,代码的最后位置将永远不会包含字母的某些字符。这可以看作是一个缺点,因为它以明显的方式缩小了有效代码的范围。
解码优惠券代码时,首先必须运行该codeFromCoupon功能,然后检查结果的第25位是否已设置。这将标记为无效代码,您可以立即拒绝该代码。注意,实际上,这甚至可能是一个优势,因为它允许快速检查(例如,在客户端)代码的有效性,而无需放弃算法的所有内部功能。
codeFromCoupon
如果未设置位25,则将调用该crypt函数并获取原始编号。
crypt