优惠券代码生成 [英] Coupon code generation

问题描述

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

I would like to generate coupon codes , e.g. AYB4ZZ2. However, I would also like to be able to mark the used coupons and limit their global number, let's say N. The naive approach would be something like "generate N unique alphanumeric codes, put them into database and perform a db search on every coupon operation."

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

However, as far as I realize, we can also attempt to find a function MakeCoupon(n), which converts the given number into a coupon-like string with predefined length.

据我所知，MakeCoupon 应该满足以下要求:

As far as I understand, MakeCoupon should fullfill the following requirements:

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

• Be bijective. It's inverse MakeNumber(coupon) should be effectively computable.

MakeCoupon(n) 的输出应该是字母数字，并且长度应该很小并且恒定 - 这样它就可以被称为人类可读em>.例如.SHA1 摘要不会通过此要求.

Output for MakeCoupon(n) should be alphanumeric and should have small and constant length - so that it could be called human readable. E.g. SHA1 digest wouldn't pass this requirement.

实用的独特性.MakeCoupon(n) 对每个自然 n <= N 的结果应该是完全唯一的，或者在与例如 MD5 是唯一的(具有相同的极小碰撞概率).

Practical uniqueness. Results of MakeCoupon(n) for every natural n <= N should be totally unique or unique in the same terms as, for example, MD5 is unique (with the same extremely small collision probability).

(这个很难定义)如何从单个优惠券代码中枚举所有剩余的优惠券应该不是很明显 - 让我们说 MakeCoupon(n) 和 MakeCoupon(n + 1) 应该在视觉上有所不同.

(this one is tricky to define) It shouldn't be obvious how to enumerate all remaining coupons from a single coupon code - let's say MakeCoupon(n) and MakeCoupon(n + 1) should visually differ.

例如MakeCoupon(n), 仅输出用零填充的 n 将无法满足此要求，因为 000001 和 000002 不视觉上"实际上并没有什么不同.

E.g. MakeCoupon(n), which simply outputs n padded with zeroes would fail this requirement, because 000001 and 000002 don't actually differ "visually".

是否存在满足以下要求的任何函数或函数生成器?我的搜索尝试仅将我引导至 [CPAN] CouponCode， 但不满足对应函数为双射的要求.

Does any function or function generator, which fullfills the following requirements, exist? My search attempts only lead me to [CPAN] CouponCode, but it does not fullfill the requirement of the corresponding function being bijective.

推荐答案

基本上你可以把你的操作分成几个部分:

Basically you can split your operation into to parts:

1. 以某种方式加密"您的初始数字 n，以便两个连续的数字产生(非常)不同的结果
2. 根据第 1 步的结果构建人类可读"的代码

1. Somehow "encrypt" your initial number n, so that two consecutive numbers yield (very) different results
2. Construct your "human-readable" code from the result of step 1

对于第 1 步，我建议使用简单的分组密码(例如 Feistel 密码具有您选择的圆形功能).另请参阅此问题.

For step 1 I'd suggest to use a simple block cipher (e.g. a Feistel cipher with a round function of your choice). See also this question.

Feistel 密码在几个回合中起作用.在每一轮中，一些轮函数被应用于输入的一半，结果与另一半xor并交换两半.Feistel 密码的好处是轮函数不必是双向的(轮函数的输入在每一轮之后保持不变，因此轮函数的结果可以在解密期间重建).因此，您可以选择任何您喜欢的疯狂操作:).Feistel 密码也是对称的，满足您的第一个要求.

Feistel ciphers work in several rounds. During each round, some round function is applied to one half of the input, the result is xored with the other half and the two halves are swapped. The nice thing about Feistel ciphers is that the round function hasn't to be two-way (the input to the round function is retained unmodified after each round, so the result of the round function can be reconstructed during decryption). Therefore you can choose whatever crazy operation(s) you like :). Also Feistel ciphers are symmetric, which fulfills your first requirement.

C# 中的一个简短示例

A short example in 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));
}

(注意在最后一轮之后没有交换，在代码中交换只是在结果的构造中被撤销)

(Note that after the last round there is no swapping, in the code the swapping is simply undone in the construction of the result)

除了满足您的要求 3 和 4(功能是 total，因此对于不同的输入，您会得到不同的输出，并且根据您的非正式定义，输入是完全打乱的")它也是自己的逆(因此隐含地满足要求 1)，即 crypt(crypt(x))==x 对于输入域中的每个 x (0..2^30-1 在这个实现中).在性能要求方面也很便宜.

Apart from fulfilling your requirements 3 and 4 (the function is total, so for different inputs you get different outputs and the input is "totally scrambled" according to your informal definition) it is also it's own inverse (thus implicitely fulfilling requirement 1), i.e. crypt(crypt(x))==x for each x in the input domain (0..2^30-1 in this implementation). Also it's cheap in terms of performance requirements.

对于第 2 步，只需将结果编码为您选择的某个基数.例如，要编码 30 位数字，您可以使用 32 个字符的字母表中的 6 个数字"(因此您可以编码 6*5=30 位).

For step 2 just encode the result to some base of your choice. For instance, to encode a 30-bit number, you could use 6 "digits" of an alphabet of 32 characters (so you can encode 6*5=30 bits).

此步骤在 C# 中的示例:

An example for this step in 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 这会产生以下优惠券代码

For inputs 0 - 9 this yields the following coupon codes

0 => 5VZNKB
1 => HL766Z
2 => TMGSEY
3 => P28L4W
4 => EM5EWD
5 => WIACCZ
6 => 8DEPDA
7 => OQE33A
8 => 4SEQ5A
9 => AVAXS5

请注意，这种方法有两个不同的内部秘密":首先，轮函数以及使用的轮数，其次，用于编码加密结果的字母表.但还要注意，所示的实现在密码学意义上绝不是安全的！

Note, that this approach has two different internal "secrets": First, the round function together with the number of rounds used and second, the alphabet you use for encoding the encyrpted result. But also note, that the shown implementation is in no way secure in a cryptographical sense!

另请注意，显示的函数是一个全双射函数，从某种意义上说，每个可能的 6 字符代码(包含字母表之外的字符)都将产生一个唯一的数字.为了防止任何人只输入一些随机代码，您应该对输入数字定义某种限制.例如.只为前 10.000 个号码发行优惠券.那么，某个随机优惠券代码有效的概率为 10000/2^30=0.00001(需要大约 50000 次尝试才能找到正确的优惠券代码).如果您需要更多安全性"，您可以增加位大小/优惠券代码长度(见下文).

Also note, that the shown function is a total bijective function, in the sense, that every possible 6-character code (with characters out of your alphabet) will yield a unique number. To prevent anyone from entering just some random code, you should define some kind of restictions on the input number. E.g. only issue coupons for the first 10.000 numbers. Then, the probability of some random coupon code to be valid would be 10000/2^30=0.00001 (it would require about 50000 attempts to find a correct coupon code). If you need more "security", you can just increase the bit size/coupon code length (see below).

更改优惠券代码长度

更改生成的优惠券代码的长度需要一些数学计算:第一个(加密)步骤仅适用于偶数位数的位串(这是 Feistel 密码工作所必需的).

Changing the length of the resulting coupon code requires some math: The first (encrypting) step only works on a bit string with even bit count (this is required for the Feistel cipher to work).

在第二步中，可以使用给定字母表编码的位数取决于所选字母表的大小"和优惠券代码的长度.这个以比特为单位的熵"通常不是整数，更不是偶数.例如:

In the the second step, the number of bits that can be encoded using a given alphabet depends on the "size" of chosen alphabet and the length of the coupon code. This "entropy", given in bits, is, in general, not an integer number, far less an even integer number. For example:

使用 30 个字符的字母表的 5 位代码会产生 30^5 个可能的代码，这意味着 ld(30^5)=24.53 位/优惠券代码.

A 5-digit code using a 30 character alphabet results in 30^5 possible codes which means ld(30^5)=24.53 bits/Coupon code.

对于四位数代码，有一个简单的解决方案:给定一个 32 个字符的字母表，您可以编码 *ld(32^4)=5*4=20* 位.因此，您只需将 BITCOUNT 设置为 20 并更改代码第二部分中的 for 循环以运行直到 4(而不是 <代码>6)

For a four-digit code, there is a simple solution: Given a 32-Character alphabet you can encode *ld(32^4)=5*4=20* Bits. So you can just set the BITCOUNT to 20 and change the for loop in the second part of the code to run until 4 (instead of 6)

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

Generating a five-digit code is a bit trickier and somhow "weakens" the algorithm: You can set the BITCOUNT to 24 and just generate a 5-digit code from an alphabet of 30 characters (remove two characters from the ALPHABET string and let the for loop run until 5).

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

But this will not generate all possible 5-digit-codes: with 24 bits you can only get 16,777,216 possible values from the encryption stage, the 5 digit codes could encode 24,300,000 possible numbers, so some possible codes will never be generated. More specifically, the last position of the code will never contain some characters of the alphabet. This can be seen as a drawback, because it narrows down the set of valid codes in an obvious way.

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

When decoding a coupon code, you'll first have to run the codeFromCoupon function and then check, if bit 25 of the result is set. This would mark an invalid code that you can immediately reject. Note that, in practise, this might even be an advantage, since it allows a quick check (e.g. on the client side) of the validity of a code without giving away all internals of the algorithm.

如果第 25 位未设置，您将调用 crypt 函数并获取原始号码.

If bit 25 is not set you'll call the crypt function and get the original number.

这篇关于优惠券代码生成的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！