优惠券代码生成

Question

我想生成优惠券代码,例如AYB4ZZ2.但是,我还希望能够标记使用过的优惠券并限制其全球数量N.天真的方法就是"生成N独特的字母数字代码,将它们放入数据库并在每个优惠券操作上执行数据库搜索".

但是,据我所知,我们还可以尝试找到一个函数 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,但它没有满足相应函数的双射要求.

Answer 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

注意,这种方法有两个不同的内部"秘密":第一,圆函数和使用的轮数,第二,你用来编码encyrpted结果的字母.但请注意,所显示的实现在加密意义上绝不安全!

另请注意,所显示的函数是一个完全双射函数,在某种意义上,每个可能的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)

生成一个五位数的代码有点棘手,而且somhow"弱化"算法:你可以设置BITCOUNT为24,只需从30个字符的字母表中生成一个5位数的代码(从ALPHABET字符串中删除两个字符并让for循环运行直到5).

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

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

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

Answer 2

虽然我可能会接受这个答案,但我觉得我需要回应 - 我真的希望你能听到我说的话,因为它来自很多痛苦的经历.

这个任务是非常学术挑战,工程师和软件工程师往往会挑战自己的INTELECT与解决问题,我需要,如果我可以给你提供一些方向这一点.世界上没有任何零售商店,无论如何都有任何成功,并不能很好地跟踪所生成的每一个实体 ; 从每件库存到他们发出的每张优惠券或礼品卡.如果你是这样的话,那就不是一个好的管家了,因为如果人们想要欺骗你,那就不是时候了,所以如果你在你的武器库中拥有所有可能的物品,你就会做好准备.

现在,我们来谈谈优惠券在您的场景中的使用过程.

当客户兑换优惠券时,前面会有某种POS系统吗？这甚至可能是一个在线业务,然后他们可以只输入他们的优惠券代码与收银员正确扫描条形码的寄存器(我假设这是我们在这里处理的)？所以现在,作为供应商,你说如果你有一个有效的优惠券代码,我会给你一些折扣,因为我们的目标是生成可逆的优惠券代码,我们不需要数据库为了验证代码,我们可以正确地反转它!我的意思是这只是数学吗？嗯,是的,不.

是的,你是对的,这只是数学.事实上,这也是问题,因为破解SSL也是如此.但是,我会认为我们都知道在SSL使用的数学只比这里使用的任何一个有点复杂和关键的是显着变大.

这对你来说并不是理所当然的,你也不应该尝试提出某种方案,你只能确定没有人愿意打破这种方案,特别是涉及金钱时.你正在努力解决一个你不应该试图解决的问题,因为你需要保护自己免受使用优惠券代码的人的影响.

因此,这个问题不必要地复杂化并且可以像这样解决.

// insert a record into the database for the coupon
// thus generating an auto-incrementing key
var id = [some code to insert into database and get back the key]

// base64 encode the resulting key value
var couponCode = Convert.ToBase64String(id);

// truncate the coupon code if you like

// update the database with the coupon code

1. 创建具有自动递增键的优惠券表.
2. 插入该表并返回自动递增键.
3. Base64将该ID编码为优惠券代码.
4. 如果需要,截断该字符串.
5. 使用刚刚插入的优惠券将该字符串存储回数据库中.

Answer 3

你想要的是称为格式保留加密.

不失一般性,通过在基数36中进行编码,我们可以假设我们在讨论的是整数,0..M-1而不是符号串.M应该是2的力量.

选择密钥并指定后M,FPE会为您提供伪随机排列0..M-1 encrypt及其反转decrypt.

string GenerateCoupon(int n) {
    Debug.Assert(0 <= n && n < N);
    return Base36.Encode(encrypt(n));
}

boolean IsCoupon(string code) {
    return decrypt(Base36.Decode(code)) < N;
}

如果你的FPE是安全的,这个方案是安全的:即使他设法猜出与他知道的每个优惠券相关的数字,攻击者也不能生成其他优惠券代码,其概率高于O(N/M). .

这仍然是一个相对较新的领域,因此很少有这种加密方案的实现.这个crypto.SE问题只提到了Botan,一个带有Perl/Python绑定的C++库,但不是C#.

注意事项:除了FPE尚未被广泛接受的标准这一事实外,您还必须考虑实施中存在错误的可能性.如果线路上有很多钱,你需要权衡这个风险与避免数据库相对较小的好处.