Algorytm kodów kart podarunkowych

Użyj N-bitowego numeru seryjnego R, połączonego z M-bitowym skrótem H konkatenowanej pary (R, S), gdzie S jest jakąś tajemną "solą" s, którą publikujesz , A nie. Następnie Zakoduj parę (R,H) alfanumerycznie w dowolny odwracalny sposób. Jeśli lubisz algorytmy takie jak MD5* lub SHA, ale liczba bitów jest zbyt wysoka, po prostu weź najmniej znaczące bity standardowego algorytmu haszującego.

Możesz łatwo zweryfikować: odkoduj kodowanie alfanumeryczne, aby zobaczyć R i H. następnie Oblicz H'= hash (R+S) i sprawdzić, czy H = H'.

Edit: R może być zwiększającym się numerem seryjnym lub losowym lub czymkolwiek, po prostu upewnij się, że używasz każdej wartości nie więcej niż raz.

* zanim ktoś powie "MD5 jest zepsute", przypomnę, że znanymi słabościami MD5 są ataki kolizyjne, a nie preimage attacks . Ponadto, używając niepublikowanej, tajnej wartości salt, odmawiasz atakującemu możliwości przetestowania mechanizmu bezpieczeństwa, chyba że on / ona odgadnie salt wartość. Jeśli masz paranoję, wybierz dwie wartości soli Sprefix i Ssuffix i Oblicz hash połączonej potrójnej (Sprefix, R,Ssuffix).

Niektóre generatory liczb losowych mają interesującą właściwość: używane prawo nie generują zduplikowanych liczb przez długi czas. Produkują coś, co nazywa się pełny cykl . Użyj jednego z opisanych tam algorytmów, a będziesz miał wiele unikalnych liczb,

Dodaj inteligentny sposób mapowania cyfr do znaków, a otrzymasz kody.

Powiedziałbym, aby użyć "perfect hash" - http://en.wikipedia.org/wiki/Perfect_hash_function w połączeniu z 4-cyfrową liczbą losową...

Więc po prostu zwiększ swój kod kuponu za każdym razem, a następnie hash go, dodaj 4 cyfrę losową, a ja również dodać cyfrę kontrolną na końcu (jak zasugerował Alix Axel).

Byłoby to bardzo bezpieczne bez kolizji - na przykład, gdyby ktoś opracował Twój algorytm haszujący, musiałby również odgadnąć 4-cyfrowy Kod na końcu...

Programming Pearls ma kilka przykładów algorytmów do generowania zestawów liczb losowych, powinieneś go przeczytać, jeśli jesteś zainteresowany tego rodzaju problemem.

Książka pokazuje, że jeśli wygenerujesz m liczby losowe o wartości mniejszej niż n, proste podejście do generowania liczb i wyrzucania duplikatów wygeneruje nie więcej niż 2m Liczby losowe, Jeśli m < n / 2. Tutaj jest, w C++:

void gensets(int m, int n)
{
    set<int> S;
    set<int>::iterator i;
    while (S.size() < m) {
        int t = bigrand() % n;
        S.insert(t);
    }
    for (i = S.begin(); i != S.end(); ++i)
        cout << *i << "\n";
}

Oczywiście, jeśli martwisz się, że ludzie zgadują wartości, chcesz, aby m było znacznie mniej niż n / 2.

Istnieje nawet algorytm oparty na zestawie, który generuje m liczby losowe mniejsze niż n, przy czym każda wartość jest równie prawdopodobna, bez duplikatów i gwarancji, że nie wygeneruje więcej niż m liczby losowe:

void genfloyd(int m, int n)
{
    set<int> S;
    set<int>::iterator i;
    for (int j = n-m; j < n; j++) {
        int t = bigrand() % (j+1);
        if (S.find(t) == S.end())
            S.insert(t); // t not in S
        else
            S.insert(j); // t in S
    }
    for (i = S.begin(); i != S.end(); ++i)
        cout << *i << "\n";
}

Kolejność liczb nie jest jednak przypadkowa, więc prawdopodobnie nie jest to dobry wybór dla Ciebie.

Na inne pytanie też odpowiedziałam: p

Najlepszym sposobem jest wygenerowanie jednego znaku alfanumerycznego na raz, losowo, dopóki nie będzie ich 8. To będzie twój voucher.

Najlepiej byłoby wybrać sekwencję wystarczająco długą, aby można było bezpiecznie założyć, czy będą jakieś duplikaty. Zauważ, że, być może wbrew intuicji, dzieje się to częściej niż myślisz z powodu problemu urodzinowego .

Na przykład z 8 znakami można masz 1785793904896 możliwych kombinacji, ale jeśli wygenerujesz tylko 1,573,415 kuponów, będziesz miał 50% szans na duplikat.

Więc wszystko zależy od tego, ile chcesz wygenerować i maksymalnej długości kodu, z którym ci wygodnie. Jeśli generujesz wiele i chcesz, aby było to krótkie, powinieneś zapisać te, które wcześniej wygenerowałeś, i sprawdzić w bazie danych pod kątem duplikatów.

to jest podsumowanie najlepszych fragmentów wszystkich innych odpowiedzi. :)

Musisz wygenerować numery kart podarunkowych, które są:

• unique
• unguessable

Liczby losowe są nie do odgadnięcia, ale niekoniecznie unikalne. Liczby wytwarzane przez różne algorytmy są unikalne, ale możliwe do odgadnięcia (algorytm może być odwrócony). Nie znam jednego algorytmu, który daje obie właściwości, a ze względu na konieczność przeciwstawienia się inżynierii odwrotnej, spada w dziedzinie kryptografii. Nie-eksperci, oczywiście, nie powinni próbować projektować kryptosystemów.

Na szczęście nie musisz pobierać obu właściwości z tego samego algorytmu. Twoje kody kart podarunkowych mogą składać się z dwóch części: części, która jest unikalna (generowana za pomocą liniowego generatora kongruencyjnego, być może, lub arytmetyki modulo, a nawet po prostu liczby całkowitej, które zwiększasz za każdym razem) i części, która jest nie do wykrycia (tylko losowe liczby).

Przeczytałem cały komentarz i dowiedziałem się, że wiele osób w innych, aby chronić, używa bardzo sprytnych i wyrafinowanych środków. szanse na zgadnięcie mojego algorytmu wynoszą 1/2600000 wszystko, co musisz zrobić, to zmienić przedrostek salt przyrostek salt po każdym pokoleniu

• wybrałem przedrostek 4 cyfr
• i przyrostek 4 liczb
• wtedy głównym kodem jest 9 liczb wymiennych
• Następnie użyj tego formatu sprefix +random_numbers+ssuffix
• będę hashować format przechowywania to do bazy danych natychmiast
• zapytanie może pomóc usunąć podobne kody
• A przyrostek i prefiks należy zmienić po wydrukowaniu 9! (362880) times.

Myślę, że najlepszym wyjściem jest to, co zasugerował Andreas. Ale moja odpowiedź jest o ciekawej dyskusji związanej.

Chcesz wygenerować ciąg liczb, które razem tworzą permutację S = {1, ..., MAX}. Na przykład liczby R = {x modulo p, x^2 modulo p, x^3 modulo p, ..., x^(p-1) modulo p} tworzą grupę cykliczną nad {1, ..., p-1}, pod warunkiem, że p jest liczbą pierwszą, a x jest koprime do p. Więc jeśli wybierzesz MAX jako liczbę pierwszą, użyjesz tej sekwencji.

Bazując na odpowiedzi Jasona Orendoffa, stworzyłem algorytm generowania kodów kart podarunkowych. Zasadniczo, ma dwie 40-bitowe liczby: jeden z nich, aby zapewnić, że jest unikalny, a drugi, aby zapewnić, że jest trudny do odgadnięcia.

• 40-bitowa część liczb losowych wystarcza na 1 w 2^40 szanse na zgadywanie;
• 40-bitowa część numeru sekwencyjnego wystarcza na 34,8 roku o unikalności (zakładając, że generujemy jedną kartę podarunkową na Państwo)

Całkowita 80-bitowa sekwencja jest następnie konwertowana na 16-znakowy ciąg za pomocą Base32 .

import java.security.SecureRandom;
import java.util.Random;
import java.util.concurrent.atomic.AtomicLong;

import org.apache.commons.codec.binary.Base32;

public class GiftCardUtil {

    private AtomicLong sequence;
    private Random random;

    public GiftCardUtil() {
        // 1325383200000L == 1 Jan 2012
        sequence = new AtomicLong(System.currentTimeMillis() - 1325383200000L);
        random = new SecureRandom();
    }

    public String generateCode() {
        System.out.println(sequence.get());
        byte[] id = new byte[10];
        longTo5ByteArray(sequence.incrementAndGet(), id);
        byte[] rnd = new byte[5];
        random.nextBytes(rnd);
        System.arraycopy(rnd, 0, id, 5, 5);
        return new Base32().encodeAsString(id);
    }

    private void longTo5ByteArray(long l, byte[] b) {
        b[0] = (byte) (l >>> 32);
        b[1] = (byte) (l >>> 24);
        b[2] = (byte) (l >>> 16);
        b[3] = (byte) (l >>> 8);
        b[4] = (byte) (l >>> 0);
    }
}

To, co może działać skutecznie, to po prostu wykorzystanie czasu tworzenia na swoją korzyść. Powiedzmy, ostatnie dwie cyfry roku, dwucyfrowy miesiąc, Dwucyfrowy dzień, dwucyfrowa godzina, dwucyfrowa minuta, dwucyfrowa sekunda, a następnie przenieś sekundy do, powiedzmy, mikrosekundy. Jeśli pożądane jest dalsze zaciemnianie, należy je wstępnie rozszyfrować (np. MYmdshhdMmYs zamiast YYMMddhmmss). Następnie zmień bazę (na pentadecymalną, być może), aby odwrócić dalsze próby zgadywania. Próchnica ta ma dwa główne korzyści: 1-Użycie daty, w tym roku, zniszczy wszelkie duplikacje, ponieważ ten sam czas nie minie dwa razy. Dopiero po stu latach jest jakieś ryzyko. Jedynym problemem jest potencjalnie posiadanie dwóch utworzonych na tej samej mikrosekundzie, dla którego byłoby prostym zadaniem, aby uniemożliwić tworzenie więcej niż jednego na raz. Milisekundowe opóźnienie rozwiązałoby problem.

2-zgadywanie będzie bardzo trudne. Nie tylko jest zastanawianie się, jaka podstawa i kolejność cyfr (i liter!) są w będzie to trudne zadanie, ale wyjście na mikrosekundę sprawia, że sekwencja w dużej mierze nie ma znaczenia. Nie wspominając o tym, jak trudno byłoby klientowi zrozumieć, w jaki sposób mikrosekunda kupiła i jak ich zegar pasuje do twojego.

Sprzeciw może brzmieć "czekaj! To jest 17 cyfr (YYMMDDhhmmss.sssss), ale wyprowadzony później do większej bazy zmniejszyłby ją. Przejście do bazy 36, używając 10 cyfr i 26 liter, oznacza, że 11-cyfrowy Kod obejmowałby każdą możliwość. If uppercase małe litery nie są wymienne, dane można skompresować do celu 10 cyfr z zerowymi problemami.

Oto choć:

• ID = każdy voucher ma unikalny (auto-incrementowany?) ID
• suma kontrolna = zastosuj N iteracji algorytmu Verhoeff lub Luhn NA ID
• VOUCHER = base Przelicz wygenerowaną sumę kontrolną z bazy 10 na bazę 36

Zobacz też to podobne pytanie: pomysły, aby utworzyć mały (.

Jednym z prostych sposobów na zwiększenie bezpieczeństwa tej metody jest użycie nie jest automatycznie zwiększana wartość ID, jedną z opcji może być użycie ID jako ostatnich 6 lub 7 cyfr znacznika czasu Uniksa i obliczenie sumy kontrolnej.

Popieram użycie kryptograficznego hasha-pobieranie bitów z MD5 jest bardzo proste. Aby wszystko było czytelne, wpadłem na następujący pomysł: weź listę słów i użyj bitów klucza, aby indeksować listę słów. Moja lista słów to około 100 000 słów, więc około 16 bitów na słowo, co dla czterech słów daje 64-bitową przestrzeń keyspace. Wyniki są zwykle dość czytelne.

Na przykład podpis kryptograficzny poprzedniego akapitu to

Kamikaze 's freshet mansion' s wykrztuśne

(Moja lista słów jest pochylona w kierunku większej przestrzeni klawiszy; jeśli chcesz krótszych fraz, masz mniej słów.)

Jeśli masz pod ręką bibliotekę MD5, ta strategia jest bardzo łatwa do wdrożenia-robię to w około 40 liniach Lua.