优惠券code代 [英] Coupon code generation

问题描述

我想生成优惠券codeS，例如 AYB4ZZ2 。不过，我也希望能够标记所使用的优惠券，并限制其全球数，比方说 N 。天真的做法会是这样的生成 N 独特的字母数字codeS，把它们放进数据库，并执行每票操作数据库的搜索。

不过，据我知道，我们也可以试图找到一个函数 MakeCoupon（N），其中给定的数字转换成优惠券般的字符串，predefined长度。

据我了解， MakeCoupon 应fullfill下列要求：的

• 争取双射。这是逆 MakeNumber（优惠券）应该是有效的可计算的。

• 输出为 MakeCoupon（N）应是字母数字，应该有小和恒长度 - 因此它可以被称为人类可读的。例如。 SHA1 消化不会通过这个要求。

• 实践的独特性。 MakeCoupon结果（N），每自然 N'LT; = N 应在相同的条件完全独特的或独特的，例如， MD5 是唯一的（与同极小的碰撞概率）。

• （这是一个棘手定义）的应该不是很明显如何枚举所有剩余的优惠券从单一的优惠券code - 比方说 MakeCoupon（N）和 MakeCoupon（N + 1）应在视觉上有所不同。

    

  例如。 MakeCoupon（N），这只是输出 N 用零填充将失败这一要求，因为 000001 和 000002 实际上并没有区别视觉。

问：

是否有任何函数或函数发生器，它fullfills以下要求，存在吗？我的搜索尝试只会导致我到<一个href="http://search.cpan.org/dist/Algorithm-Coupon$c$c/lib/Algorithm/Coupon$c$c.pm"><$c$c>[CPAN]优惠券code，的，但它不fullfill相应的功能是双射的要求。

解决方案

基本上，你可以分割你的操作成零件：

1. 不知怎的，加密你最初的数 N ，使两个连续数收益率（非常）不同的结果
2. 从步骤1的结果构建你的人类可读的code

对于第1步我建议使用一个简单的分组密码（如： Feistel密码与循环函数你的选择）。另请参见这个问题。

的Feistel密码在多个的发工作的。在每一轮，一些循环函数的被施加到二分之一的输入，结果是异版与另一半与两半交换。有关的Feistel密码的好处是，该轮函数不能是双向的（输入到轮函数每一轮后保留修改，所以ROUND函数的结果可以解密过程中重建）。因此，你可以选择任何疯狂的运行（）你喜欢:)。同样的Feistel密码是对称的，它满足你一个要求。

一个简单的例子在C＃

  const int的位计数= 30;
const int的BITMASK =（1＆LT;＆LT;位计数/ 2） -  1;

静态UINT roundFunction（UINT号）{
  返回（（（数^ 47894）+ 25）＆其中;＆小于1）及BITMASK;
}

静态UINT隐窝（UINT号）{
  UINT左=号＆GT;＆GT; （比特计数/ 2）;
  UINT右=号＆放大器; BITMASK;
  为（中间体圆= 0;圆小于10 ++圆）{
    左=左^ roundFunction（右）;
    UINT TEMP =左;左=右;右=温度;
  }
  返回离开| （右其中;≤（比特计数/ 2））;
}
 

（注意，最后一轮没有交换，在code中的交换是在结果的建筑只是撤销后）

除了满足你的要求3和第4（该功能的总的，所以对于不同的输入您得到不同的输出和输入根据您的非正式的定义完全加密），这也是它的自己的反面（因而隐含满足要求1），即的crypt（隐窝（X））== X 每个 X 在输入域（ 0..2 ^ 30-1在此实施）。另外它的价格便宜在性能方面的要求。

对于第2步只是连接$ C C的结果为您选择的一些基本$。例如，为EN $ C $在约30位的数字，你可以用6个字符（这样你就可以连接code 6 * 5 = 30位）。

一个字母的数字

这一步在C＃中的一个例子：

 常量字符串ALPHABET =AG8FOLE2WVTCPY5ZH3NIUDBXSMQK7946;
静态字符串券code（UINT号）{
  StringBuilder的B =新的StringBuilder（）;
  的for（int i = 0; I＆LT; 6，+ I）{
    在b.append（ALPHABET [（int）的数目及（（1＆其中;小于5）-1）]）;
    数=号＆GT;＆GT; 5;
  }
  返回b.ToString（）;
}
静态UINT codeFromCoupon（字符串优惠券）{
  UINT N = 0;
  的for（int i = 0; I＆LT; 6，+ I）
    N = N | （（（UINT）ALPHABET.IndexOf（券[I]））≤;≤（5 * i））的;
  返回N;
}
 

有关输入0 - 9这将产生以下的优惠券codeS

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

请注意，这种方法有两个不同的内部的秘密：第一，全面的功能以及采用回合数;第二，你使用的编码encyrpted结果字母表。还要注意，该所示的实施不以任何方式在密码学意义上的安全！

还要注意，示出的是一个功能的总的双射的功能，在这个意义上，每一个可能的6个字符的code（带字符你的字母表的）将产生一个唯一的数字。要进入只是一些随机code prevent任何人，你应该定义一些输入数量restictions的。例如。仅发出优待券用于第一10.000号码。然后，一些随机的优惠券code的概率是有效的将是二分之万^ 30 = 0.00001（这将需要大约50000试图找到正确的券code）。如果你需要更多的安全，你可以增加位大小/优惠券code长度（见下文）。

编辑：更改优惠券code长度

改变所产生的优惠券code的长度需要一些数学：第一个（加密）工序只适用于位串与偶位计算（这是必需的Feistel密码工作）

。

在第二步骤中，利用给定的字母位，可以是连接$ C $光盘的数目取决于所选择字母表中的大小和优惠券code中的长度。这个熵，以位定，是在一般的，而不是一个整数，远不如偶数整数。例如：

使用30个字母结果的5位code在30 ^ 5个可能的codeS，这意味着的 LD（30 ^ 5）= 24.53 的比特/优惠券code

有关一个四位数code，有一个简单的解决方案：给定一个32个字母就可以连接code * LD（32 ^ 4）= 5 * 4 = 20 *位。所以，你可以设置位计数 20，改变为循环中的code中的第二部分运行到 4 （而不是 6 ）

生成一个五位数字code是有点棘手和somhow削弱的算法：您可以设置位计数 24，只是生成5-从30个字符的字母数字code（从 ALPHABET 字符串，删除两个字符，让为循环运行到 5 ）。

不过，这并不会产生所有可能的5 digit- codeS：与24位你只能得到16777216可能值从加密阶段，5位codeS可以连接code 24300000可能的数字，所以一些可能的codeS永远不会发生。更具体而言，的code中的最后位置将永远包含字母表中的某些字符。这可以看作是一个缺点，因为它缩小了组有效codeS的一个明显的方式。

在解码优惠券code，你首先必须运行 codeFromCoupon 函数，然后检查，如果结果的第25位被设置。这将标志着一个无效的code，你可以立即拒绝。需要注意的是，在实践中，这可能甚至是有利的，因为它允许快速检查的code中的有效性（例如，在客户端侧），而不放弃的算法的所有内部

如果第25位没有设置，你会调用地穴功能，让原来的号码。

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

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.

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

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

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

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

• (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 n padded with zeroes would fail this requirement, because 000001 and 000002 don't actually differ "visually".

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.

解决方案

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

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

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)

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.

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

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

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!

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

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

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.53 bits/Coupon code.

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)

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

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.

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.

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

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