Génération de code promo

Question

Je voudrais générer des codes promo , par exemple, AYB4ZZ2. Cependant, je tiens également à être en mesure de marquer les coupons et de limiter leur nombre, disons - N. L'approche naïve serait quelque chose comme "générer N uniques des codes alphanumériques, de les mettre en base de données et effectuer une db de recherche sur chaque coupon de fonctionnement."

Cependant, aussi loin que je me rends compte, on peut également tenter de trouver une fonction MakeCoupon(n), qui convertit le nombre donné dans un coupon-comme chaîne de longueur prédéterminée.

Comme je le comprends, MakeCoupon doit remplir les exigences suivantes:

• Être bijective. C'est l'inverse MakeNumber(coupon) devraient être effectivement calculable.

• Sortie pour MakeCoupon(n) doit être composé de caractères alphanumériques et devrait avoir des petites et constante de la longueur de sorte qu'il pourrait être appelé lisible par l'homme. E. g. SHA1 digérer ne passerait pas à cette exigence.

• Pratique de l'unicité. Les résultats de l' MakeCoupon(n) pour tous les naturels n <= N devrait être totalement unique ou dans les mêmes termes que, par exemple, MD5 est unique (avec la même extrêmement faible probabilité de collision).

• (celui-ci est difficile à définir) Il ne doit pas être évident pour énumérer tous les autres coupons à partir d'un seul code promo, disons - MakeCoupon(n) et MakeCoupon(n + 1) devrait visuellement différents.

  E. g. MakeCoupon(n), , qui se contente de sorties n complétée par des zéros, échouera à cette exigence, car 000001 et 000002 ne sont pas réellement différents "visuellement".

Q:

N'importe quelle fonction ou un générateur de fonctions, qui capable de réaliser les exigences suivantes, qui existent? Mes tentatives de recherche seulement de m'entrainer à l' [CPAN] CouponCode, mais il ne permet pas de satisfaire à l'exigence de la fonction correspondante étant bijective.

Answer 1

Fondamentalement, vous pouvez diviser votre opération dans les parties:

1. En quelque sorte, "crypter" votre nombre n, de sorte que deux numéros consécutifs de la production (très) différents résultats
2. Construire votre "lisible" code à partir du résultat de l'étape 1

Pour l'étape 1 je vous suggère d'utiliser un simple algorithme de chiffrement par bloc (par exemple, un chiffrement Feistel avec une ronde en fonction de votre choix). Voir également cette question.

Algorithmes de chiffrement Feistel le travail en plusieurs tours. Au cours de chaque cycle, certaines ronde fonction est appliquée à la moitié de l'entrée, le résultat est xored avec l'autre moitié et les deux moitiés sont échangées. La bonne chose à propos de Feistel algorithmes est que la fonction round n'a pas à être deux sens (de l'entrée à la fonction round est maintenue inchangée après chaque ronde, de sorte que le résultat de la fonction round peut être reconstruit au cours de déchiffrement). Par conséquent, vous pouvez choisir ce que fou opération(s) que vous aimez :). Aussi Feistel sont les algorithmes symétriques, ce qui répond à votre première exigence.

Un petit exemple en 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));
}

(À noter qu'après le dernier tour, il n'y a pas d'échange, dans le code de l'échange est tout simplement annulée dans la construction de la suite)

En dehors de l'accomplissement de vos conditions 3 et 4 (la fonction est totale, donc, pour les différentes entrées, vous obtenez différentes sorties et l'entrée est "totalement brouillés", selon votre définition informelle), il est aussi son propre inverse (donc implicitement l'accomplissement de l'exigence 1), c'est à dire crypt(crypt(x))==x pour chaque x dans le domaine d'entrée (0..2^30-1 dans cette mise en œuvre). Aussi il est bon marché en termes d'exigences de performance.

Pour l'étape 2 juste coder le résultat à une base de votre choix. Par exemple, pour coder un 30-nombre de bits, vous pouvez utiliser 6 "chiffres" d'un alphabet de 32 caractères (donc vous pouvez encoder 6*5=30 bits).

Un exemple pour cette étape en 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;
}

Pour les entrées 0 - 9 présente les rendements suivants coupon codes

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

Notez que cette approche a deux différents interne "secrets": d'Abord, la fonction round avec le nombre de tours d'occasion et de seconde, l'alphabet que vous utilisez pour l'encodage de l'encyrpted résultat. Mais aussi à noter que la mise en œuvre n'est en aucune façon sécurisée dans un cryptographiques majeures de sens!

Notez également, que la fonction est un total bijective fonction, dans le sens, que tout un code de 6 caractères (avec les caractères de l'alphabet) permet d'obtenir un numéro unique. Pour empêcher quiconque de pénétrer dans n'importe code, vous devez définir une sorte de restrictions sur le nombre d'entrée. E. g. seul problème des coupons pour la première 10.000 numéros. Ensuite, la probabilité d'un hasard de code promo valide serait 10000/2^30=0.00001 (il faudrait près de 50000 tente de trouver un bon code promo). Si vous avez besoin de plus de "sécurité", vous pouvez simplement augmenter la taille en bits/coupon code longueur (voir ci-dessous).

EDIT: Changement de code promo longueur

La modification de la longueur de la code promo nécessite quelques calculs: La première (chiffrement) étape ne fonctionne que sur une chaîne de bits avec le même nombre de bits (ce qui est nécessaire pour le chiffrement Feistel de travail).

Dans la deuxième étape, le nombre de bits qui peuvent être codées à l'aide d'un alphabet donné dépend de la "taille" de choisi de l'alphabet et de la longueur du code de coupon. Cette "entropie", donné en bits, est, en général, n'est pas un nombre entier, et encore moins un même nombre entier. Par exemple:

5-digit code à l'aide d'un de 30 caractères de l'alphabet résultats au 30^5 codes possibles qui signifie ld(30^5)=24.53 bits/code promo.

Pour un code à quatre chiffres, il y a une solution simple: étant Donné un de 32 Caractères de l'alphabet, vous pouvez encoder *ld(32^4)=5*4=20* Bits. De sorte que vous pouvez simplement mettre la BITCOUNT - 20 et modifier l' for boucle dans la deuxième partie du code à exécuter jusqu' 4 (au lieu de 6)

La génération d'un code à cinq chiffres est un peu plus compliqué et somhow "affaiblit" l'algorithme: Vous pouvez définir l' BITCOUNT à 24 et tout simplement de générer un 5 chiffres code à partir d'un alphabet de 30 caractères (enlever les deux personnages de l' ALPHABET chaîne et de laisser l' for boucle de courir jusqu' 5).

Mais cela ne génère pas possible de 5 chiffres-codes: avec 24 bits, vous ne pouvez obtenir de 16777216 valeurs possibles de cryptage de la scène, les 5 chiffres de codes pourrait coder 24,300,000 possible nombres, de sorte que certains codes ne sera jamais produite. Plus précisément, la dernière position du code, ils ne contiennent certains caractères de l'alphabet. Ceci peut être vu comme un inconvénient, car il se rétrécit vers le bas l'ensemble des codes valides de façon évidente.

Lors du décodage d'un code promo, vous devez exécuter l' codeFromCoupon de la fonction et de vérifier ensuite, si le bit 25 de la suite est définie. Ce serait la marque d'un code non valide que vous pouvez rejeter immédiatement. Notez que, dans la pratique, cela peut même être un avantage, car elle permet une vérification rapide (par exemple sur le côté client) de la validité d'un code sans donner tous les éléments internes de l'algorithme.

Si le bit 25 n'est pas ensemble vous vous appelez l' crypt fonction et obtenir le numéro d'origine.

Answer 2

Si je peut obtenir retenu pour cette réponse, je sens que j'ai besoin pour y répondre, j'espère vraiment que vous entendez ce que je dis car il provient d'un lot d'une expérience douloureuse.

Alors que cette tâche est très exigeants, et les ingénieurs logiciels ont tendance à remettre en question leurs intelect contre la résolution de problèmes, j'ai besoin de vous fournir une orientation sur ce, si je peut. Il n'y a pas de magasin de vente au détail dans le monde, qui a toute sorte de succès de toute façon, ça ne se garde pas très bon suivi de chaque entité qui est généré; à partir de chaque élément de l'inventaire pour chaque coupon ou carte-cadeau, ils envoient ces portes. C'est juste de ne pas être un bon intendant si vous êtes, parce que c'est pas si les gens vont vous tromper, c'est le moment, et donc si vous avez tout à fait possible de l'élément dans votre arsenal, vous serez prêt.

Maintenant, nous allons parler sur le processus par lequel le coupon est utilisé dans votre scénario.

Lorsque le client rachète le coupon, il va y avoir une sorte de système d'ENCAISSEMENT avant droit? Et qui peut même être une entreprise en ligne, où ils sont alors en mesure de simplement entrer leur code de coupon contre un registre où la caissière scanne un code-barres à droite (je suppose que c'est ce que nous avons affaire ici)? Et maintenant, en tant que vendeur, vous êtes en train de dire que si vous avez un coupon valide le code, je vais vous donner une sorte de rabais et parce que notre objectif était de générer des codes promo qui ont été réversible nous n'avons pas besoin d'une base de données pour vérifier que le code, il suffit d'inverser le droit! Je veux dire, c'est que des maths à droite? Eh bien, oui et non.

Oui, vous avez raison, c'est juste des maths. En fait, c'est aussi le problème, car ainsi est la fissuration SSL. Mais, je vais supposer que nous réalisons tous les calculs utilisés dans le protocole SSL est un peu plus complexe que ce que, utilisé ici, et la clé est considérablement plus grande.

Il ne vous incombera, ni est-il sage pour vous d'essayer et de venir avec une sorte de régime que vous êtes tout simplement sûr que personne ne se soucie assez pour casser, surtout quand il s'agit de l'argent. Vous faites de votre vie très difficile d'essayer de résoudre un problème que vous ne devriez pas essayer de résoudre parce que vous devez vous protéger de ceux utilisant le coupon codes.

Par conséquent, ce problème est inutilement compliqué et pourrait être résolu comme ça.

// 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. Créer un coupon de table qui a une auto-incrémentation de la clé.
2. Insérer dans la table et obtenir l'auto-incrémentation touche retour.
3. Base64 encode que les id dans un code de coupon.
4. Tronquer une chaîne si vous le souhaitez.
5. Magasin de cette chaîne dans la base de données avec le coupon venez d'insérer.

Answer 3

Ce que vous voulez est appelé le Format de la préservation de chiffrement.

Sans perte de généralité, par l'encodage en base 36, nous pouvons supposer que nous parlons d'entiers en 0..M-1 plutôt que des chaînes de symboles. M devrait probablement être une puissance de 2.

Après le choix d'une clé secrète et en précisant M, FPE vous donne un pseudo-permutation aléatoire de 0..M-1 encrypt avec son 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;
}

Si votre FPE est sécurisé, ce système est sécurisé: aucun attaquant peut générer d'autres codes promo avec une probabilité supérieure à O(N/M) compte tenu de la connaissance d'arbitraire, de nombreux coupons, même s'il parvient à deviner le nombre associé à chaque coupon de ce qu'il sait.

C'est encore un domaine relativement nouveau, donc il y a peu de mises en œuvre de tels systèmes de cryptage. Cette crypto.SE question ne mentionne Botan, une bibliothèque C++ avec Perl/Python bindings, mais pas de C#.

Mot de prudence: outre le fait qu'il n'y a pas bien acceptée des normes pour la FPE, cependant, on doit envisager la possibilité d'un bug dans la mise en œuvre. Si il y a beaucoup d'argent sur la ligne, vous avez besoin de peser ce risque à l'encontre de la relativement faible avantage d'éviter une base de données.

Answer 4

Vous pouvez utiliser une base de 36 système de nombre. Supposons que vous voulez 6 caractères dans le coupen de sortie.

le pseudo-code pour MakeCoupon

MakeCoupon(n) {

Avoir un tableau d'octets de taille fixe, disons 6. Initialiser toutes les valeurs à 0. convertir le nombre en base 36 et stocke les "chiffres" dans un tableau (en utilisant la division entière et mod des opérations) Maintenant, pour chaque "chiffre" trouver le code ascii correspondant en supposant que le chiffres à partir de 0..9,A..Z Avec cette convension de sortie six chiffres comme une chaîne de caractères.

}

Maintenant, le calcul du nombre de retour à l'inverse de cette opération.

Ce serait de travailler avec de très grands nombres (35^6) avec 6 caractères autorisés.

Answer 5

• Choisissez une fonction chiffrement c. Il y a quelques exigences sur c, mais pour l'instant laissez-nous prendre en SHA1.

• choisissez une clé secrète k.

Le code de votre coupon fonction génératrice pourrait être, pour nombre n:

• concaténer n et k "n"+"k" (ce qui est connu comme le salage dans la gestion de mot de passe)
• calculer c("n"+"k")
• le résultat de SHA1 est 160bits, les encoder (par exemple avec base64) comme une chaîne de caractères ASCII
• si le résultat est trop long (comme vous l'avez dit, c'est le cas pour SHA1), le tronquer pour ne garder que les 10 premières lettres et le nom de cette chaîne de caractères s
• votre code promo est printf "%09d%s" n s, c'est à dire l'enchaînement des zéros n et le tronc de hachage s.

Oui, c'est facile à deviner n le nombre de code promo (mais voir ci-dessous). Mais il est difficile de générer un autre code valide.

Vos exigences sont remplies:

1. Pour calculer l'inverse de la fonction, il suffit de lire les 9 premiers chiffres du code
2. La longueur est toujours 19 (9 chiffres de n, plus de 10 lettres de hachage)
3. Il est unique, car les 9 premiers chiffres sont uniques. Les 10 derniers caractères sont trop, avec une forte probabilité.
4. Il n'est pas évident pour générer le hachage, même si l'on devine que vous avez utilisé SHA1.

Quelques commentaires:

• Si vous êtes inquiet que la lecture de n est trop évident, vous pouvez dissimuler à la légère, comme l'encodage base64, et de l'alternance dans le code les caractères de l' n et s.
• Je suis en supposant que vous n'aurez pas besoin de plus d'un milliard de codes, ainsi que l'impression de n sur 9 chiffres, mais vous pouvez bien sûr ajuster les paramètres 9 et 10, à votre convenance coupon code de longueur.
• SHA1 est seulement une option, vous pouvez utiliser une autre fonction chiffrement comme le chiffrement à clé privée, mais vous devez vérifier que cette fonction reste forte quand tronquée et quand le texte clair est fourni.
• Ce n'est pas optimal dans le code de la longueur, mais a l'avantage de la simplicité et largement disponibles dans les bibliothèques.