53

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

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

据我了解,MakeCoupon应满足以下要求:

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

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

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

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

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

问:

是否存在满足以下要求的函数或函数生成器?我的搜索尝试只引导我到[CPAN]CouponCode,但它并没有满足相应函数是双射的要求。

4

5 回答 5

84

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

  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(函数是total,因此对于不同的输入,您会得到不同的输出,并且根据您的非正式定义,输入是“完全打乱的”)它也是它自己的逆(因此隐含地满足要求 1),即对于输入域中crypt(crypt(x))==x的每个(在此实现中)。就性能要求而言,它也很便宜。x0..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

请注意,这种方法有两个不同的内部“秘密”:第一,轮函数以及使用的轮数,第二,用于编码加密结果的字母表。但还要注意,所示的实现在密码学意义上绝不是安全的!

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

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

于 2012-08-01T09:20:04.590 回答
14

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

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

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

当客户兑换优惠券时,前面会有某种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. 将该字符串与刚刚插入的优惠券一起存储回数据库中。
于 2012-08-07T10:49:03.703 回答
5

您想要的称为Format-preserving encryption

不失一般性,通过以 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 还没有被广泛接受的标准这一事实之外,您还必须考虑实施中存在错误的可能性。如果有很多钱,您需要权衡这种风险与避免使用数据库的相对较小的好处。

于 2012-08-01T11:53:27.793 回答
3

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

MakeCoupon 的伪代码

MakeCoupon(n) {

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

}

现在计算后面的数字是这个操作的逆过程。

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

于 2012-07-29T11:31:50.410 回答
2
  • 选择一个加密函数c。对 c 有一些要求,但现在让我们使用 SHA1。

  • 选择一个密钥k

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

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

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

满足您的要求:

  1. 要计算反向函数,只需读取代码的前 9 位
  2. 长度始终为 19(n 的 9 位数字,加上哈希的 10 个字母)
  3. 它是唯一的,因为前 9 位数字是唯一的。最后 10 个字符也是,很有可能。
  4. 即使有人猜测您使用了 SHA1,如何生成散列也不明显。


一些评论:

  • 如果担心读起来n太明显,可以轻轻混淆一下,比如base64编码,在代码中交替使用nand的字符s
  • 我假设您不需要超过十亿个代码,因此将 n 打印为 9 位数字,但您当然可以将参数 9 和 10 调整为您想要的优惠券代码长度。
  • SHA1 只是一个选项,您可以使用其他加密功能,如私钥加密,但您需要检查此功能在截断和提供明文时是否保持强大。
  • 这在代码长度上不是最优的,但具有简单和广泛可用的库的优点。
于 2012-08-01T10:55:14.147 回答