礼品卡编码算法

密钥空间比实际使用的代码数量大得多,因此随机冲突也极不可能发生(不过,由于生日悖论,可能不太可能完全忽略它们,至少如果您希望代码相当短的话),检查现有代码并在发生冲突时重新生成代码是一种完全可行的策略。

不 出版。然后以你喜欢的任何可逆方式对这对(R,H)进行字母数字编码。如果您喜欢MD5*或SHA之类的算法,但位计数太高,那么只需获取标准哈希算法的M个最低有效位。

你可以很容易地验证:解码字母数字编码,这样你就可以看到R和H。然后计算H'=hash(R+S)并验证H=H'。

编辑: R可以是递增的序列号,也可以是随机数,或者其他什么,只要确保每个值使用不超过一次即可。

*在有人说“MD5坏了”之前,让我提醒您,MD5的已知弱点是碰撞攻击,以及 preimage attacks . 此外,通过使用未发布的秘密salt值,攻击者无法测试您的安全机制,除非他/她能够猜出salt值。如果您感到偏执,请选择两个salt值Sprefix和Ssuffix,并计算连接三元组(Sprefix、R、Ssuffix)的散列。

一些随机数生成器有一个有趣的特性:正确使用它们不会在很长时间内生成重复数。他们生产一种叫做 full cycle .

添加一种将数字映射到字符的智能方法,您就可以获得代码。

我会说使用“完美散列”- http://en.wikipedia.org/wiki/Perfect_hash_function 加上一个4位数的随机数。。。

因此,每次只需增加凭证代码,然后将其散列,添加一个4位随机数,我还会在末尾添加一个校验位(正如Alix Axel所建议的)。

这将是非常安全的,没有冲突-例如,如果有人制定了你的哈希算法,他们还必须猜测最后的4位代码。。。

Programming Pearls

这本书表明,如果你 m 值小于的随机数 n ,生成数字并丢弃重复项的简单方法将生成不超过 2m m < n / 2

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

显然,如果你担心人们猜测价值,你会想要 n / 2 .

甚至还有一种基于集合的算法可以生成 N 每个值的可能性相同,没有重复项,并且保证不会产生超过 M 随机数:

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

我读了整篇评论,发现很多人在其他地方用非常聪明和复杂的手段来保护自己。对我的算法进行猜测的几率是2600000分之一

• 我选择了一个由4个数字组成的salt前缀
• 那么主代码是9个可互换的数字
• 然后使用这种格式 sprefix +random_numbers+ssuffix
• 我会立即将格式散列到数据库中
• 而后缀和前缀应该改变一旦你非常打印9(362880)次。

理想情况下,最好的方法是选择一个足够长的序列,以便您可以安全地假设是否会有任何重复。请注意,也许与直觉相反,这种情况发生的频率比您想象的要高,因为 Birthday problem

例如,对于8个字符,您有1785793904896个可能的组合,但如果您仅生成1573415张凭证,则您有50%的机会复制凭证。

所以,这完全取决于您想要生成的代码数量,以及您所熟悉的代码的最大长度。如果要生成多个,并且希望保持简短,则应保存以前生成的,并对照数据库检查重复项。

这是所有其他答案中最好的部分的总结。:)

您需要生成以下礼品卡号:

• 无用的

随机数是不可用的,但不一定是唯一的。各种算法产生的数字是唯一的,但可以猜测(该算法可以反向工程)。我不知道有哪种算法能同时提供这两种属性,而且由于需要对抗逆向工程,它属于密码学领域。当然,非专家不应该尝试设计密码系统。

幸运的是,您不必从同一个算法中获得这两个属性。您的礼品卡代码可以由两部分组成:一部分是唯一的(使用 linear congruential generator

我认为最好的办法是安德烈亚斯建议的。但我的回答是关于一个有趣的相关讨论。

您希望生成一系列数字,这些数字一起构成S={1,…,MAX}的排列。一种方法是将循环群的元素取到S上。例如,数字 R = {x modulo p, x^2 modulo p, x^3 modulo p, ..., x^(p-1) modulo p} 在上面形成一个循环群 {1, ..., p-1} 假如 p 是一个素数和 x P

你想要一个“难以破解”的序列。足够难破解序列的生成器称为伪随机生成器(当然,您可能不需要) 难以破解)。例如,中元素的最后一位 R 以上,提供 P 是保密的(我说的对吗?)。但是Andreas的答案已经使用了(伪)随机数源,因此不能称为伪随机发生器。

如果你对伪随机发生器感兴趣,它们将在Knuth的著名著作第2卷中详细讨论。

基于 Jason Orendoff's answer ,我提出了一个生成礼品卡代码的算法。 基本上,它有两个40位的数字:一个用来保证它是唯一的,另一个用来保证它很难猜测。

• 40位随机数部分足以容纳1英寸 2^40 成功的机会 猜测;
• 34.8 years 唯一性(假设我们每毫秒生成一张礼品卡)

然后使用以下命令将总的80位序列转换为16个字符的字符串: 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);
    }
}

有效的方法是简单地利用创造的时间对你有利。比如说,一年的最后两位数,两位数的月份,两位数的日子,两位数的小时,两位数的分钟,两位数的秒,然后把秒计算到,比如说,微秒。如果需要进一步混淆,请对其进行预扰频(例如MYmdshhdMmYs而不是YYMMddhmmss)。然后更改基数(可能是五进制),以避免任何进一步的猜测尝试。 这有两大好处:

反对意见可能是“等等!这是17位数字(yymmdhhmmss.sssss),但如果将其带到更大的基数,则会使其减小。以36为基数,使用10个数字和26个字母,意味着一个11位数的代码将涵盖所有可能性。如果大写和小写不可互换,则可以将数据压缩到10位,而不会出现任何问题。

• 校验和=应用 Verhoeff Luhn 基于ID的算法
• 凭证=基数将生成的校验和从基数10转换为基数36

另见相关SO问题: Ideas to create a small (<10 digits), not (very) secure “hash”

其次,使用从MD5中提取位的加密哈希非常简单。 为了让事情更具可读性,我想到了以下想法:获取一个单词列表,并使用一些键来索引一个单词列表。我的单词列表大约有100000个单词,所以每个单词大约有16位,这对于四个单词来说是一个64位的键空间。结果通常可读性很强。

神风队最新官邸的吐痰

(我的单词列表向更大的键空间倾斜;如果你想要较短的短语,你的单词就更少了。)