C# 优惠券代码生成

Coupon code generation

提问by Yippie-Ki-Yay

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 Nunique alphanumeric codes, put them into database and perform a db search on every coupon operation."

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

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

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

As far as I understand, MakeCouponshould fullfill the following requirements:

据我了解，MakeCoupon应满足以下要求：

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

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

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

• (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.

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

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

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

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

• （这个很难定义）如何从单个优惠券代码中枚举所有剩余的优惠券应该不是很明显 - 假设MakeCoupon(n)并且MakeCoupon(n + 1)应该在视觉上有所不同。

  例如MakeCoupon(n),，简单地n用零填充的输出将无法满足此要求，因为实际上000001并000002没有“视觉上”不同。

Q:

问：

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.

是否存在满足以下要求的函数或函数发生器？我的搜索尝试只会让我找到[CPAN]CouponCode，但它并不能满足相应函数是双射的要求。

采纳答案by MartinStettner

Basically you can split your operation into to parts:

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

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. 以某种方式“加密”您的初始数字n，以便两个连续的数字产生（非常）不同的结果
2. 根据第 1 步的结果构建“人类可读”的代码

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

对于第 1 步，我建议使用简单的分组密码（例如，具有您选择的轮函数的Feistel 密码）。另请参阅此问题。

Feistel ciphers work in several rounds. During each round, some round functionis 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.

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

A short example in C#

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)

（请注意，在最后一轮之后没有交换，在代码中交换只是在结果的构造中撤消）

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))==xfor each xin the input domain (0..2^30-1in this implementation). Also it's cheap in terms of performance requirements.

除了满足您的要求 3 和 4（函数是total，因此对于不同的输入，您会得到不同的输出，并且根据您的非正式定义，输入是“完全加扰的”）它也是它自己的逆（因此隐含地满足要求 1），即crypt(crypt(x))==x对于x输入域中的每个（0..2^30-1在此实现中）。就性能要求而言，它也很便宜。

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).

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

An example for this step in C#:

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;
}

For inputs 0 - 9 this yields the following coupon codes

对于输入 0 - 9 这会产生以下优惠券代码

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!

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

Also note, that the shown function is a total bijectivefunction, 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).

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

EDIT: Change Coupon code length

编辑：更改优惠券代码长度

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).

更改生成的优惠券代码的长度需要一些数学运算：第一个（加密）步骤仅适用于偶数位的位串（这是 Feistel 密码工作所必需的）。

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:

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

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

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

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 BITCOUNTto 20 and change the forloop in the second part of the code to run until 4(instead of 6)

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

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

生成一个五位数的代码有点棘手，并且会“削弱”算法：您可以将 设置BITCOUNT为 24，然后从 30 个字符的字母表中生成一个 5 位数的代码（从ALPHABET字符串中删除两个字符并让for循环运行直到5）。

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.

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

When decoding a coupon code, you'll first have to run the codeFromCouponfunction 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.

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

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

如果第 25 位未设置，您将调用该crypt函数并获取原始数字。

回答by PermanentGuest

You can use a base-36 number system. Assume that you want 6 characters in the coupen output.

您可以使用 base-36 数字系统。假设您需要 coupen 输出中的 6 个字符。

pseudo code for MakeCoupon

MakeCoupon 的伪代码

MakeCoupon(n) {

MakeCoupon(n) {

Have an byte array of fixed size, say 6. Initialize all the values to 0. convert the number to base - 36 and store the 'digits' in an array (using integer division and mod operations) Now, for each 'digit' find the corresponding ascii code assuming the digits to start from 0..9,A..Z With this convension output six digits as a string.

有一个固定大小的字节数组，比如 6。将所有值初始化为 0。将数字转换为基数 - 36 并将“数字”存储在一个数组中（使用整数除法和模运算）现在，对于每个“数字”查找假设数字从 0..9,A..Z 开始的相应 ascii 代码使用此转换输出六位数字作为字符串。

}

}

Now the calculating the number back is the reverse of this operation.

现在计算返回的数字与此操作相反。

This would work with very large numbers (35^6) with 6 allowed characters.

这适用于具有 6 个允许字符的非常大的数字 (35^6)。

回答by jrouquie

• Choose a cryptographic function c. There are a few requirements on c, but for now let us take SHA1.

• choose a secret key k.

• 选择加密函数c。对 c 有一些要求，但现在让我们采用 SHA1。

• 选择一个密钥k。

Your coupon code generating function could be, for number n:

您的优惠券代码生成功能可能是 number n：

• concatenate n and k as "n"+"k"(this is known as salting in password management)
• compute c("n"+"k")
• the result of SHA1 is 160bits, encode them (for instance with base64) as an ASCII string
• if the result is too long (as you said it is the case for SHA1), truncate it to keep only the first 10 letters and name this string s
• your coupon code is printf "%09d%s" n s, i.e. the concatenation of zero-padded nand the truncated hash s.

• 将 n 和 k 连接为"n"+"k"（这在密码管理中称为加盐）
• 计算 c("n"+"k")
• SHA1 的结果是 160 位，将它们编码（例如使用 base64）作为 ASCII 字符串
• 如果结果太长（正如您所说的 SHA1 的情况），将其截断以仅保留前 10 个字母并命名此字符串 s
• 您的优惠券代码是printf "%09d%s" n s，即零填充n和截断哈希的串联s。

Yes, it is trivial to guess nthe number of the coupon code (but see below). But it is hard to generate another valid code.

是的，猜测n优惠券代码的数量是微不足道的（但见下文）。但是很难生成另一个有效的代码。

Your requirements are satisfied:

您的要求得到满足：

1. To compute the reverse function, just read the first 9 digits of the code
2. The length is always 19 (9 digits of n, plus 10 letters of hash)
3. It is unique, since the first 9 digits are unique. The last 10 chars are too, with high probability.
4. It is not obvious how to generate the hash, even if one guesses that you used SHA1.

1. 要计算反向函数，只需读取代码的前 9 位
2. 长度始终为 19（n 的 9 位数字，加上哈希的 10 个字母）
3. 它是唯一的，因为前 9 位数字是唯一的。最后10个字符也是，概率很高。
4. 即使有人猜测您使用了 SHA1，也不清楚如何生成哈希。

Some comments:

一些评论：

• If you're worried that reading nis too obvious, you can obfuscate it lightly, like base64 encoding, and alternating in the code the characters of nand s.
• I am assuming that you won't need more than a billion codes, thus the printing of n on 9 digits, but you can of course adjust the parameters 9 and 10 to your desired coupon code length.
• SHA1 is just an option, you could use another cryptographic function like private key encryption, but you need to check that this function remains strong when truncated and when the clear text is provided.
• This is not optimal in code length, but has the advantage of simplicity and widely available libraries.

• 如果你担心，阅读n是太明显了，你可以轻轻地混淆它，像base64编码，并交替在代码中的人物n和s。
• 我假设您不需要超过 10 亿个代码，因此在 9 位数字上打印 n，但您当然可以将参数 9 和 10 调整为所需的优惠券代码长度。
• SHA1 只是一种选择，您可以使用另一种加密功能，如私钥加密，但您需要检查该功能在被截断和提供明文时是否仍然强大。
• 这在代码长度上不是最优的，但具有简单和广泛可用的库的优点。

回答by Generic Human

What you want is called Format-preserving encryption.

你想要的是Format-preserving encryption。

Without loss of generality, by encoding in base 36 we can assume that we are talking about integers in 0..M-1rather than strings of symbols. Mshould probably be a power of 2.

不失一般性，通过以 base 36 编码，我们可以假设我们谈论的是整数 in0..M-1而不是符号字符串。M应该是 2 的幂。

After choosing a secret key and specifying M, FPE gives you a pseudo-random permutation of 0..M-1encryptalong with its inverse decrypt.

选择一个密钥并指定 后M，FPE 会为您提供 的伪随机排列0..M-1encrypt及其逆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;
}

If your FPE is secure, this scheme is secure: no attacker can generate other coupon codes with probability higher than O(N/M) given knowledge of arbitrarily many coupons, even if he manages to guess the number associated with each coupon that he knows.

如果您的 FPE 是安全的，则该方案是安全的：在已知任意数量的优惠券的情况下，没有攻击者能够以高于 O(N/M) 的概率生成其他优惠券代码，即使他设法猜测与他知道的每个优惠券关联的编号.

This is still a relatively new field, so there are few implementations of such encryption schemes. This crypto.SE questiononly mentions Botan, a C++ library with Perl/Python bindings, but not C#.

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

Word of caution: in addition to the fact that there are no well-accepted standards for FPE yet, you must consider the possibility of a bug in the implementation. If there is a lot of money on the line, you need to weigh that risk against the relatively small benefit of avoiding a database.

警告：除了 FPE 还没有公认的标准这一事实之外，您还必须考虑实现中存在错误的可能性。如果在线上有很多钱，您需要权衡这种风险与避免使用数据库的相对较小的好处。

回答by Mike Perrenoud

Though I may get docked for this answer I feel like I need to respond - I really hope that you hear what I'm saying as it comes from a lot of painful experience.

虽然我可能会因为这个答案而被停职，但我觉得我需要做出回应——我真的希望你能听到我在说什么，因为它来自很多痛苦的经历。

While this task is veryacademically challenging, and software engineers tend to challenge their intelect vs. solving problems, I need to provide you with some direction on this if I may. There is no retail store in the world, that has any kind of success anyway, that doesn't keep very good track of each and every entitythat is generated; from each piece of inventory to every single coupon or gift card they send out those doors. It's just not being a good steward if you are, because it's not if people are going to cheat you, it's when, and so if you have every possible item in your arsenal you'll be ready.

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

Now, let's talk about the process by which the coupon is used in your scenario.

现在，让我们谈谈在您的场景中使用优惠券的过程。

When the customer redeems the coupon there is going to be some kind of POS system in front right? And that may even be an online business where they are then able to just enter their coupon code vs. a register where the cashier scans a barcode right (I'm assuming that's what we're dealing with here)? And so now, as the vendor, you're saying that if you have a valid coupon code I'm going to give you some kind of discount andbecause our goal was to generate coupon codes that were reversable we don't need a database to verify that code, we can just reverse it right! I mean it's just math right? Well, yes and no.

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

Yes, you're right, it's just math. In fact, that's also the problem because so is cracking SSL. But, I'm going to assume that we all realize the math used in SSL is just a bit more complex than anything used here andthe key is substantiallylarger.

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

It does not behoove you, nor is it wise for you to try and come up with some kind of scheme that you're just sure nobody cares enough to break, especially when it comes to money. You are making your life very difficult trying to solve a problem you really shouldn't be trying to solve because you need to be protecting yourself from those using the coupon codes.

您不应该这样做，您尝试提出某种您确定没有人愿意破坏的计划也是不明智的，尤其是在金钱方面。你试图解决一个你真的不应该尝试解决的问题让你的生活变得非常困难，因为你需要保护自己免受使用优惠券代码的人的伤害。

Therefore, this problem is unnecessarily complicated and could be solved like this.

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

// 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. Create a coupon table that has an auto-incrementing key.
2. Insert into that table and get the auto-incrementing key back.
3. Base64 encode that id into a coupon code.
4. Truncate that string if you want.
5. Store that string back in the database with the coupon just inserted.

1. 创建一个具有自动递增键的优惠券表。
2. 插入该表并取回自动递增键。
3. Base64 将该 ID 编码为优惠券代码。
4. 如果需要，请截断该字符串。
5. 将该字符串与刚刚插入的优惠券一起存储在数据库中。