优惠券码生成

Question

我想生成优惠券代码，例如AYB4ZZ2。但是，我也希望能够标记使用过的优惠券并限制它们的全局数量，比如N。天真的方法可能是“生成N唯一的字母数字代码，将它们放入数据库，并对每个优惠券操作执行db搜索”。

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

据我所知，MakeCoupon应该完全满足以下要求：

• 要有目标。它的逆MakeNumber(coupon)应该是有效的计算。
• MakeCoupon(n)的输出应该是字母数字的，并且应该具有较小的和常量的长度--因此可以称为人类可读的。例如，SHA1摘要不能满足这个要求。
• 实际独特性。MakeCoupon(n)对于每个自然n <= N的结果应该是完全唯一的或唯一的，例如，MD5是唯一的(具有相同的极小的碰撞概率)。
• (这个很难定义)如何从单个优惠券代码中枚举所有剩余的优惠券并不是显而易见的--比方说MakeCoupon(n)和MakeCoupon(n + 1)在视觉上应该有所不同。 例如，简单地输出带有零的MakeCoupon(n),将不能满足这一要求，因为000001和000002实际上并没有“视觉”上的区别。

问：

是否存在任何满足以下要求的函数或函数生成器？我的搜索尝试只引导我找到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 (此实现中的0..2^30-1)。而且，它在性能要求方面也很便宜。

对于第二步，只需将结果编码到您选择的某个基础上即可。例如，要对一个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

注意，这种方法有两个不同的内部“秘密”：第一，循环函数以及使用的轮数；第二，用于编码加密结果的字母表。但是也要注意，所显示的实现在密码意义上是绝对不安全的！

另外，请注意，显示的函数是一个完全双射函数，从这个意义上说，每一个可能的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位。这将标记无效代码，您可以立即拒绝该代码。注意，在实践中，这甚至可能是一个优势，因为它允许快速检查代码的有效性(例如在客户端)，而不泄露算法的所有内部信息。

如果没有设置bit 25，您将调用crypt函数并获得原始编号。

Answer 2

虽然我可能会因为这个答案而陷入困境，但我觉得我需要回应--我真的希望你能听到我说的话，因为它来自于很多痛苦的经历。

虽然这个任务在非常具有学术挑战性，软件工程师倾向于挑战他们的智力而不是解决问题()，但如果可能的话，我需要为您提供一些指导。世界上没有一家零售店能取得任何成功，无法很好地跟踪每一家生产的实体；从每一种库存到每一张优惠券或礼品卡，它们都会发出这些门。如果你是个好管家，那不是因为人们要欺骗你，而是时间，所以如果你有所有可能的东西，你就会做好准备。

现在，让我们讨论一下在您的场景中使用优惠券的过程。

当顾客赎回优惠券时，前面会有某种POS系统，对吗？这甚至可能是一个在线业务，他们可以输入优惠券代码而不是收银员扫描条形码的寄存器，对吧，(我想这就是我们要处理的)？现在，作为供应商，你是说如果你有一个有效的优惠券代码，我会给你一些折扣和，因为我们的目标是生成可逆转的优惠券代码--我们不需要数据库来验证这些代码，我们就可以把它颠倒过来！我是说，这只是数学，对吗？，是的，不是的，

是的，你说得对，这只是数学。事实上，这也是问题所在，因为破解SSL也是如此。但是，我将假设我们都意识到SSL中使用的数学比这里使用的任何东西都要复杂一些--关键是substantially更大。

它不适合你，也不明智，你尝试想出某种计划，你只是确信没有人足够关心打破，特别是当涉及到money。你让你的生活变得非常困难，试图解决一个你真的不应该试图解决的问题，因为你需要保护自己不受那些使用优惠券代码的人的影响。

因此，这个问题不必要地复杂，是可以这样解决的。

// 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问题只提到了博坦，一个带有Perl/Python绑定的C++库，而没有提到C#。

警告:除了还没有被广泛接受的FPE标准之外，您还必须考虑在实现中出现错误的可能性。如果存在大量资金，您需要权衡风险与避免数据库的相对较小的好处。