c - 生成一组可以在不保留白名单的情况下进行验证的唯一 key

Question

我需要生成一组 10 字节的唯一 ID。这些集合可能非常大(即 10000 个值)，并由有限内存设备检查其有效性。所以有人在设备中输入其中一个 ID，设备应该能够辨别该 ID 是否真实(由我生成)。
基本方法是在设备内存中存储同一组 ID 并对照列表进行检查，但我不能使用所有内存。
我认为的第二种方法是使用 CRC 或散列函数:例如，启用 CRC 为 X 的所有 ID。这里的问题是我应该遍历所有可能的 ID 组合以找到提供正确 CRC 的 ID。
理想情况下，我想找到一个/两个这样工作的函数:

 uint8_t * generate_ID(uint16_t index);
 bool is_valid validate_key(uint8_t * ID);
 //optional
 uint16_t index find_index(uint8_t * ID);

 //example
 //generate id value from index 0
 uint8_t ID[10] = generate_ID(0)
 //id is now {0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f, 0x0e, 0x0d, 0x0c, 0x0b}

 bool is_valid = validate_key(ID);
 //is_valid is True
 uint16_t index = find_index(ID);
 //index is now 0
 ID[0] = 0xff; //change ID with random value
 is_valid = validate_key(ID);
 //is_valid is now False

 //BONUS: use also a "seed" value, so that I can differentiate through sets of ids:
 uint8_t * generate_ID(uint16_t index, uint16_t seed);
 bool is_valid validate_key(uint8_t * ID, uint16_t seed);

find_index() 是可选的，因为一旦我知道 key 有效，我就可以简单地遍历所有索引以找到匹配的索引。
基本上，generate_ID() 函数应该足够复杂，这样即使不知道相当数量的 ID 也不会轻易猜到它，但能够在马力有限的嵌入式 CPU (Cortex M0) 上计算

Answer 1

10 字节的 key 不足以保证任何安全。

您需要一个安全的散列函数，例如 SHA2-256，其输出长度为 32 字节。 SHA2 可以很容易地在大多数系统上实现。

您的 key 需要两部分:

[text + hash]

第一部分就像“用户名”，第二部分就像“密码”

您还需要一个“ key ”。此 key 是存储在您的软件中的字节数组。然后，您将“ key ”添加到您的“用户名”。查找结果字符串的 SHA2 哈希。现在您的输出是原始文本的长度 + 32 个字节的哈希值。

您可以将此 key 用作唯一的可验证 ID。

要测试 key 的真实性，请获取“用户名”部分并添加您的 key 。对该字符串进行 SHA2，结果应匹配“密码”

如果保密性和唯一性不是大问题，那么您可以使用输出为 16 字节的 MD5。将纯文本更改为二进制，这样它可以用更少的字节存储更多的信息，而你的最终 key 将只有 20 个字节。您可以再减少一点，但不建议减少到 10 个字节。

这是一个例子。我使用了此链接中的 SHA2 实现:
https://github.com/B-Con/crypto-algorithms(我不确定它是否适用于大端机器)

任何 SHA2 实现都应该有效。

void sha2(BYTE* dst, const BYTE* src, int len)
{
    SHA256_CTX ctx;
    sha256_init(&ctx);
    sha256_update(&ctx, (const BYTE*)src, len);
    sha256_final(&ctx, (BYTE*)dst);
}

void create_verifiable_id(const BYTE* source, BYTE *uid)
{
    BYTE hash[32];
    sha2(hash, source, ID_SIZE);

    //combine source + hash
    memcpy(uid, source, ID_SIZE);
    memcpy(uid + ID_SIZE, hash, 32);
}

int test_verfiable_id(const BYTE *uid)
{
    BYTE hash[32];
    sha2(hash, uid, ID_SIZE);

    //hash should match the second part of uid
    return memcmp(hash, uid + ID_SIZE, 32) == 0;
}

int main(void)
{
    //use a number from 0 to 0xFFFFFFFF, store in buf (4 bytes)
    //this is the "plain text" portion
    int number = 0x12345678;
    BYTE buf[ID_SIZE];
    for(int i = 0; i < sizeof(buf); i++)
    {
        buf[i] = number & 0xFF;
        number >>= 8;
    }

    //add sha2 to "plain text" to make verifiable id
    BYTE verifiable_id[32 + ID_SIZE];
    create_verifiable_id(buf, verifiable_id);

    printf("UID as hex string:\n");
    for(int i = 0; i < 32 + ID_SIZE; i++)
        printf("%02X", verifiable_id[i] & 0xFF);
    printf("\n");

    printf("Test (should succeed): %d\n", test_verfiable_id(verifiable_id));

    //change verifiable_id and test it again
    verifiable_id[0]++;
    printf("Test (should fail): %d\n", test_verfiable_id(verifiable_id));
    return 0;
}