Create coupon code

Question

I would like to generate coupon codes, for example. AYB4ZZ2 . However, I would also like to mark the marks of the used coupons and limit their global number, say N A naive approach would be something like "generate N unique alphanumeric codes, put them in a database and search for db with every coupon operation."

However, as I understand it, we can also try to find the MakeCoupon(n) function that converts a given number into a coupon string with a predetermined length.

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

• Be bijective. MakeNumber(coupon) inverse MakeNumber(coupon) should be efficiently computable.

• The output for MakeCoupon(n) must be alphanumeric and small in length and constant so that it can be called a human-readable person. For example. SHA1 digest will not forward this requirement.

• Practical uniqueness. The results of MakeCoupon(n) for each natural n <= N must be completely unique or unique in the same terms that, for example, MD5 is unique (with the same extremely low probability of collision).

• (this is difficult to determine). It should not be obvious how to list all the remaining coupons from the same coupon code - say, MakeCoupon(n) and MakeCoupon(n + 1) should be visually different.

  eg. MakeCoupon(n), which simply prints N filled with zeros, will not be able to fulfill this requirement, because 000001 and 000002 actually not visually different.

Q

Is there any generator of functions or functions that fulfills the following requirements? My search attempts lead me only to [CPAN] CouponCode , but this does not fully meet the bijective requirement of the corresponding function.

Answer 1

Basically, you can split the operation into parts:

• Somehow "encrypt" your starting number n , so two consecutive numbers give (very) different results
• Build your "readable" code from the result of step 1

For step 1, I would suggest using a simple block cipher (for example, a Feistel cipher with a round function of your choice). See also this question .

Feisty ciphers work in several rounds. During each round, one round function is applied to one half of the input signal, the result is xor ed with the other half, and the two halves are swapped. The best part of Feistel’s ciphers is that the round function should not be two-way (the entrance to the round function remains unchanged after each round, so the result of the cyclic function can be restored during decryption). Therefore, you can choose any crazy operation (s) that you like :). Feistel's ciphers are also symmetrical, which meets your first requirement.

A brief 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 replacement is simply canceled in the construction of the result)

In addition to fulfilling your requirements 3 and 4 (the function is common, so you get different outputs for different inputs, and the input is “completely scrambled” according to your informal definition), it is also its own inverse (thus implicitly fulfilling requirement 1), those. crypt(crypt(x))==x for each x in the input domain ( 0..2^30-1 in this implementation). It is also cheap in terms of performance requirements.

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

An example of 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 gives 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”: firstly, a round function along with the number of rounds used and the second alphabet that you use to encode a curved result. But also note that the shown implementation is in no way protected in a cryptographic sense!

Also note that the feature shown is a complete bijective function, in the sense that every possible 6-character code (with characters from your alphabet) will give a unique number. So that someone does not enter any random code, you must define some restrictions on the input number. For example. Only coupons are issued for the first 10,000 numbers. Then the probability that any random coupon code will be valid will be 10000/2 ^ 30 = 0.00001 (this will require about 50,000 attempts to find the correct coupon code). If you need more “security”, you can simply increase the bit size / coupon size (see below).

EDIT: change coupon code length

Changing the length of the resulting coupon code requires some mathematics: the first (encryption) step only works with a bit string with an even number of bits (this is necessary in order for the Feistel cipher to work).

In the second step, the number of bits that can be encoded using a given alphabet depends on the "size" of the selected alphabet and the length of the coupon code. This "entropy", given in bits, is, generally speaking, not an integer, but even more so an even integer. For example:

A 5-digit code using the 30-character alphabet gives 30 ^ 5 possible codes, which means ld (30 ^ 5) = 24.53 bits / coupon code.

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

Generating a five-digit code is a bit more complicated and somehow “weakens” the algorithm: you can set BITCOUNT to 24 and just generate a 5-digit code from an alphabet of 30 characters (remove two characters from ALPHABET and run the for loop to 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 step, 5-digit codes can 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 alphabetical characters. This can be considered a drawback, as it narrows the set of valid codes in an obvious way.

When decoding a coupon code, you first need to run the codeFromCoupon function, and then check if bit 25 of the result is set. That would mean a wrong code that you can immediately reject. Please note that in practice this can even be an advantage, since it allows you to quickly check (for example, on the client side) the correctness of the code without discarding all the internal functions of the algorithm.

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

Answer 2

Although I can be stiffened by this answer, I feel that I need to answer - I really hope that you will hear what I say, because this is due to many painful experiences.

While this task is very academically challenging, and software developers tend to challenge their intelect and problem solving , I need to give you some direction if I may. There is no retail store in the world that has any success in any case, which does not track every item that is generated very well; from every piece of inventory to every coupon or gift card they send these doors. It’s just not to be a good steward if you are, because it isn’t, if people are going to deceive you when, and if you have all the possible items in your arsenal, you will be ready.

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

When the customer redeems the coupon, will there be some kind of POS system in front right? And it could even be an online business where they can simply enter their coupon code against the register, where the cashier is scanning the bar code on the right (I assume we are dealing here) ? And now, as a seller, you say that if you have a valid coupon code, I’m going to give you some kind of discount and because our goal was to create coupon codes that were reversible, we don’t need a database to check this code we can just cancel it correctly! I mean, is that just math? Well, yes and no.

Yes, you're right, it's just math. In fact, this is also a problem because it is cracking SSL . But I'm going to assume that we all understand that the math used in SSL is a little more complicated than everything that is used here and . substantially . p>

This doesn’t apply to you, and it’s not good for you to try to come up with some kind of scheme that you are just sure that no one cares about breaking down, especially when it comes to money , you make your life very difficult trying to solve a problem that you really should not try to decide, because you need to protect yourself from those who use coupon codes.

Therefore, this problem is unnecessarily complex and can be solved in this way.

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

• Create a coupon table with an auto-increase key.
• Paste in this table and return the auto-increment key.
• Base64 encodes this identifier into a coupon code.
• Trim this line if you want.
• Save this line in the database with the coupon just inserted.

Answer 3

What you want is called Format-Encryption .

Without loss of generality, coding in base 36, we can assume that we are talking about integers in 0..M-1 , and not about character strings. M should probably be a power of 2.

After selecting the secret key and specifying M FPE gives a pseudo-random permutation of 0..M-1 encrypt along with its inverse 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 protected, this scheme is protected: no attacker can generate other coupon codes with a probability higher than O (N / M), given the knowledge of an arbitrarily large number of coupons, even if he manages to guess the number associated with each coupon that he knows .

This is still a relatively new field, so several such encryption schemes have been implemented. This crypto.SE question mentions Botan , a C ++ library with Perl / Python, but not C #.

Caution: in addition to the fact that there are no generally accepted standards for FPE, you must consider the possibility of errors in the implementation. If there is a lot of money on the line, you need to weigh this risk against the relatively small benefits of avoiding the database.

Answer 4

You can use the base system number 36. Suppose you want to get 6 characters in the output of coupen.

pseudo code for MakeCoupon

MakeCoupon (n) {

Have an array of bytes of fixed size, say 6. Initialize all values ​​to 0. convert the number to base - 36 and save the "digits" in the array (using operations with integer division and module) Now, for each "digit" find the corresponding ascii code, digits start with 0..9, A..Z With this outline print six digits as a string.

}

Now calculating the number back is the inverse operation.

This will work with very large numbers (35 ^ 6) with 6 valid characters.

Answer 5

• Select cryptographic function c . There are several requirements for c, but now let's take SHA1.

• select secret key k .

The coupon code generation function can be for number n :

• concatenate n and k as "n"+"k" (this is known as salting in password management)
• calculate c ("n" + "k")
• the result of SHA1 is 160 bits, encodes them (for example, with base64) as an ASCII string
• if the result is too long (as you said, this applies to SHA1), truncate it to save only the first 10 letters and name this string s
• your coupon code is printf "%09d%s" ns , that is, a concatenation with zero margin n and a truncated hash s .

Yes, it’s trivial to guess the n number of the coupon code (but see below). But it's hard to create another valid code.

Your requirements are met:

• To calculate the inverse function, just read the first 9 digits of the code
• Length is always 19 (9 digits from n, plus 10 letters of the hash)
• This is unique as the first 9 digits are unique. The last 10 characters are also very likely.
• It is not clear how to generate the hash, even assuming that you used SHA1.

Some comments:

• If you are worried that reading n too obvious, you can confuse it a bit, such as base64 encoding, and alternate n and s in the code.
• I assume that you do not need more than a billion codes, so print n by 9 digits, but you can, of course, set parameters 9 and 10 to the desired length of the coupon code.
• SHA1 is just an option, you can use another cryptographic function, such as private key encryption, but you need to check that this function remains strong when truncated and when clear text is provided.
• This is not optimal for the length of the code, but has the advantage of simplicity and widely available libraries.