小编典典

优惠券代码生成

algorithm

我想生成优惠券代码,例如AYB4ZZ2。但是,我也想能够标记已使用的优惠券并限制其全球数量N。天真的方法类似于
“生成N唯一的字母数字代码,将其放入数据库中,并对每个优惠券操作执行db搜索”。

但是,据我所知,我们还可以 尝试找到一个函数 MakeCoupon(n),该 函数
将给定的数字转换为具有预定义长度的类似优惠券的字符串。

据我了解,MakeCoupon应满足以下要求:

  • 是双射的。它的逆MakeNumber(coupon)应该是可有效计算的。

  • 的输出MakeCoupon(n)应为字母数字,并且应具有较小且 恒定的 长度-以便可以将其称为 人类可读的 。例如SHA1摘要将无法通过此要求。

  • 实用的独特性。MakeCoupon(n)每种自然结果的n <= N完全或唯一性都应与唯一性相同,例如MD5唯一性(具有相同的极小碰撞概率)。

  • (定义起来很棘手) 如何从一个优惠券代码中枚举所有剩余的优惠券应该不是很明显-可以说MakeCoupon(n)并且MakeCoupon(n + 1)应该在视觉上有所不同。

例如MakeCoupon(n),,仅输出n填充了零的输出将无法满足此要求,因为000001并且000002实际上并没有“视觉上的”差异。

问:

是否存在满足以下要求的函数或函数生成器?
我的搜索尝试仅将我引导至[CPAN]CouponCode,但没有满足相应功能为双射的要求。


阅读 2550

收藏
2020-07-28

共1个答案

小编典典

基本上,您可以将操作分为几部分:

  1. 以某种方式“加密”您的初始编号n,以便两个连续的编号产生(非常)不同的结果
  2. 从步骤1的结果构造您的“人类可读”代码

对于步骤1,我建议使用简单的分组密码(例如,具有您选择的舍入函数的Feistel密码)。

Feistel密码进行了数 回合 工作。在每个回合中,将一些 回合函数
应用于输入的一半,结果xor与另一半相乘,并且交换两半。关于Feistel密码的好处是,舍入函数不必是双向的(舍入函数的输入在每次舍入之后都保持不变,因此可以在解密过程中重建舍入函数的结果)。因此,您可以选择喜欢的任何疯狂操作:)。Feistel密码也是对称的,可以满足您的第一个要求。

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在此实现中)。就性能要求而言,它也很便宜。

对于步骤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为24,然后仅从30个字符的字母表中生成5位数字的代码(从ALPHABET字符串中删除两个字符并让for循环运行直到5)。

但这不会生成所有可能的5位代码:使用24位,您只能从加密阶段获得16,777,216个可能的值,这5位代码可以编码24,300,000个可能的数字,因此将永远不会生成某些可能的代码。更具体地说,代码的最后位置将永远不会包含字母的某些字符。这可以看作是一个缺点,因为它以明显的方式缩小了有效代码的范围。

解码优惠券代码时,首先必须运行该codeFromCoupon功能,然后检查结果的第25位是否已设置。这将标记为无效代码,您可以立即拒绝该代码。注意,实际上,这甚至可能是一个优势,因为它允许快速检查(例如,在客户端)代码的有效性,而无需放弃算法的所有内部功能。

如果未设置位25,则将调用该crypt函数并获取原始编号。

2020-07-28