Генерация одного и того же случайного уникального числа каждый раз для данного числа - PullRequest
Новая
       28

Генерация одного и того же случайного уникального числа каждый раз для данного числа

2 голосов
/ 26 марта 2019

У нас есть набор групп, и каждая группа будет иметь миллиарды записей. Каждая группа будет уникально идентифицирована по идентификатору, а каждая запись в группе будет уникально идентифицирована по идентификатору. Комбинируя эти два идентификатора (concat (groupid, recordid)), мы можем идентифицировать записи по группам.

Теперь мы пытаемся изменить эти идентификаторы (объединенные) значения, в наших отчетах мы не хотим делиться прямыми идентификаторами с клиентами, которых мы поддерживаем, скорее мы хотим преобразовать идентификаторы в некоторые другие uniqueid и поделиться что с клиентами, так что им будет трудно идентифицировать группу.

Мы попытались сгенерировать для этого значения хэша (хэширования hmac256), но это не сработало для наших клиентов, поскольку значительно увеличило их хранилище. Если текущий идентификатор имеет длину 20 цифр, и генерирование хэша в 45 символов не работает. Поэтому ищем лучший вариант для генерации уникального значения из 20 цифр / строк или, по крайней мере, 25 цифр / строк, которые не будут иметь коллизий.

Ищем некоторые материалы по этому вопросу.

Мы попытались сгенерировать для этого значения хэша (хэширования hmac256), но это не сработало для наших клиентов, поскольку значительно увеличило их хранилище. Если текущий идентификатор имеет длину 20 цифр, а генерирование хэша в 45 символов не работает.

Пример: идентификатор_группы = 910612349078 RecordId = 6234091234

для двух вышеуказанных значений уникальный идентификатор, который система генерирует на сегодняшний день, будет выглядеть следующим образом: uniqueId = 9106123490786234091234 (concat (groupId, recordId))

Ожидаемое поведение для уникального идентификатора будет случайным / хеш-значением: newUniqueId = некоторый хэш или случайное число

1 Ответ

1 голос
/ 26 марта 2019

Я бы попробовал использовать приличную быструю безопасную хэш-функцию - ChaCha20 .

ChaCha20 создает псевдослучайные блоки по 64 байта каждый, которые XOR-данные с данными для шифрования или дешифрования.Требуется 256-битный ключ и 64-битный одноразовый номер.Предполагая, что все ваши идентификаторы вписываются в 64-битные (в конце концов, 20 цифр довольно близки к 2 64 -1, что составляет 18 446 744 073 709 551 615), задайте свой ключ, используйте идентификатор группы в качестве одноразового номера и зашифруйте свой идентификатор записи XORing ChaCha20вывод с ним.

Вы не упомянули платформу, поэтому нет кода, но есть множество хороших реализаций в C / C ++ / Go / Rust /...

UPDATE

Вы можете попробовать использовать ChaCha20 в качестве блочного шифра в режиме счетчика.Тогда вы должны ввести ключ, 64-битный идентификатор группы в качестве одноразового номера и 64-битный идентификатор записи в качестве счетчика.Вывод будет 64-битным блоком, который вы отправляете клиентам.

Хорошо, я поиграл с реализацией Monocypher (ссылка внизу страницы ChaCha20) и для ее использования в качестве блочного шифра, как предложено выше.Пока это выглядит хорошо для меня - разные groupId / recordId дают отчетливо разные зашифрованные значения.Код на C ++, компилируется с LLVM 8 и MSVC ++ 19.2.Я положил весь проект на Github здесь . 

uint64_t scramble(const uint64_t groupId,
                  const uint64_t recordId,
                  const char*    text_key = nullptr)
{
    uint8_t key[32] = {0x1c, 0x92, 0x40, 0xa5, 0xeb, 0x55, 0xd3, 0x8a,
                       0xf3, 0x33, 0x88, 0x86, 0x04, 0xf6, 0xb5, 0xf0,
                       0x47, 0x39, 0x17, 0xc1, 0x40, 0x2b, 0x80, 0x09,
                       0x9d, 0xca, 0x5c, 0xbc, 0x20, 0x70, 0x75, 0xc0}; // same key as in example 3 below
    if (text_key != nullptr) {
        hex2byte(text_key, key);
    }

    const uint8_t* nonce = reinterpret_cast<const uint8_t*>(&groupId); // nonce would be our group id
    crypto_chacha_ctx ctx;
    crypto_chacha20_init(&ctx, key, nonce); // initialize ChaCha20

    crypto_chacha20_set_ctr(&ctx, recordId); // block counter is our record Id

    uint64_t input = 0x0000000000000000; // Just get the block out. Chacha will make random block and XOR it with input text.
                                         // XOR with zeroes preserve Chacha block.
                                         // Or 0xFFFFFFFFFFFFFFFF to get it iverted
    uint64_t output;
    crypto_chacha20_encrypt(&ctx,
                            reinterpret_cast<uint8_t*>(&output),
                            reinterpret_cast<const uint8_t*>(&input),
                            sizeof(input));

    return output;
}


int main()
{
    // Test values from http://tools.ietf.org/html/draft-nir-cfrg-chacha20-poly1305-04#appendix-A.2
    srand(123); //Test results will be consistent
    test_ietf_chacha20("0000000000000000000000000000000000000000000000000000000000000000", "0000000000000000", "00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000", "76b8e0ada0f13d90405d6ae55386bd28bdd219b8a08ded1aa836efcc8b770dc7da41597c5157488d7724e03fb8d84a376a43b8f41518a11cc387b669b2ee6586", 0, 1);
    test_ietf_chacha20("0000000000000000000000000000000000000000000000000000000000000001", "0000000000000002", "416e79207375626d697373696f6e20746f20746865204945544620696e74656e6465642062792074686520436f6e7472696275746f7220666f72207075626c69636174696f6e20617320616c6c206f722070617274206f6620616e204945544620496e7465726e65742d4472616674206f722052464320616e6420616e792073746174656d656e74206d6164652077697468696e2074686520636f6e74657874206f6620616e204945544620616374697669747920697320636f6e7369646572656420616e20224945544620436f6e747269627574696f6e222e20537563682073746174656d656e747320696e636c756465206f72616c2073746174656d656e747320696e20494554462073657373696f6e732c2061732077656c6c206173207772697474656e20616e6420656c656374726f6e696320636f6d6d756e69636174696f6e73206d61646520617420616e792074696d65206f7220706c6163652c207768696368206172652061646472657373656420746f", "a3fbf07df3fa2fde4f376ca23e82737041605d9f4f4f57bd8cff2c1d4b7955ec2a97948bd3722915c8f3d337f7d370050e9e96d647b7c39f56e031ca5eb6250d4042e02785ececfa4b4bb5e8ead0440e20b6e8db09d881a7c6132f420e52795042bdfa7773d8a9051447b3291ce1411c680465552aa6c405b7764d5e87bea85ad00f8449ed8f72d0d662ab052691ca66424bc86d2df80ea41f43abf937d3259dc4b2d0dfb48a6c9139ddd7f76966e928e635553ba76c5c879d7b35d49eb2e62b0871cdac638939e25e8a1e0ef9d5280fa8ca328b351c3c765989cbcf3daa8b6ccc3aaf9f3979c92b3720fc88dc95ed84a1be059c6499b9fda236e7e818b04b0bc39c1e876b193bfe5569753f88128cc08aaa9b63d1a16f80ef2554d7189c411f5869ca52c5b83fa36ff216b9c1d30062bebcfd2dc5bce0911934fda79a86f6e698ced759c3ff9b6477338f3da4f9cd8514ea9982ccafb341b2384dd902f3d1ab7ac61dd29c6f21ba5b862f3730e37cfdc4fd806c22f221", 1, 2);
    test_ietf_chacha20("1c9240a5eb55d38af333888604f6b5f0473917c1402b80099dca5cbc207075c0", "0000000000000002", "2754776173206272696c6c69672c20616e642074686520736c6974687920746f7665730a446964206779726520616e642067696d626c6520696e2074686520776162653a0a416c6c206d696d737920776572652074686520626f726f676f7665732c0a416e6420746865206d6f6d65207261746873206f757467726162652e", "62e6347f95ed87a45ffae7426f27a1df5fb69110044c0d73118effa95b01e5cf166d3df2d721caf9b21e5fb14c616871fd84c54f9d65b283196c7fe4f60553ebf39c6402c42234e32a356b3e764312a61a5532055716ead6962568f87d3f3f7704c6a8d1bcd1bf4d50d6154b6da731b187b58dfd728afa36757a797ac188d1", 42, 3);
    std::cout << '\n';

    uint64_t scrambled{0ULL};

    scrambled = scramble(10, 12345);
    std::cout << "0x" << std::hex << scrambled << '\n';
    scrambled = scramble(100, 12345);
    std::cout << "0x" << std::hex << scrambled << '\n';
    scrambled = scramble(11, 12345); // group id differ by 1
    std::cout << "0x" << std::hex << scrambled << '\n';
    scrambled = scramble(10, 12346); // record id differ by 1
    std::cout << "0x" << std::hex << scrambled << '\n';
    scrambled = scramble(0, 0);
    std::cout << "0x" << std::hex << scrambled << '\n';
    scrambled = scramble(0, 1);
    std::cout << "0x" << std::hex << scrambled << '\n';
    scrambled = scramble(1, 0);
    std::cout << "0x" << std::hex << scrambled << '\n';

    return 0;
}

Вывод из последних 7 строк 

0x6321d1e43d4ab340
0x7dd7e1cfab075076
0x1e8483e0081fa6ee
0xb6084d3151900667
0x7794b6c405fbf46
0x115ddf32dffd75df
0x87a199dff4e4326a

ОБНОВЛЕНИЕ II

Извините, я сделалопечатка, которая, вероятно, ввела вас в заблуждение (размер блока указан как 64 бита, когда он равен 64 байтам, исправлен сейчас).

Да, размер блока составляет 64 байт (на самом деле 16 uint32_t из 32 бит).И ChaCha20 способен производить 2 64 таких блоков.Таким образом, вы могли бы сделать ваш входной размер, скажем, 12 байтов, и выходные данные будут первыми 12 байтами блока.Пожалуйста, проверьте код обновления в репо.Я перевернул печать блока 12 байтов, чтобы показать, что он такой же, как и раньше (порядковый номер).Вы можете поставить любой зашифрованный размер до 64.

...