Генерация (очень) большая неповторяющаяся целочисленная последовательность без предварительного перетасовки

Question

фона

У меня есть простой медиа-клиент/сервер, я написал, и я хочу, чтобы генерировать неочевидное значение времени я посылаю с каждым команды от клиента к серверу. Временные метки будут иметь справедливый бит данных (nano-second resolution, даже если это не совсем верно, из-за ограничений выборки таймера в современных операционных системах) и т. Д.

Что я пытаюсь сделать (на Linux, в C), состоит в том, чтобы генерировать взаимно однозначную последовательность n-битовых значений (предположим, что данные хранятся в 128-битных элементах массива-на-int) без перекрывающихся/сталкивающихся значений. Затем я принимал псевдослучайное значение 128 бит/номер в качестве «соли», применял его к отметке времени, а затем начинал отправлять команды на сервер, увеличивая предварительно соленое/предварительно хешированное значение.

Причина, по которой размер временной метки настолько велик, поскольку временная метка может потребоваться для очень большой продолжительности времени.

---

Вопрос

Как я мог выполнить такую ​​последовательность (не сталкивающийся) с начальным значением соли?The best approach that sounds along the lines of my goal is from this post, which notes:

Если вариант 1 не "случайный" достаточно для вас, используйте CRC-32 хэш сказал глобальной (32-бит) счетчик. Существует 1-к-1 сопоставление (биекция) между N-разрядными целыми числами и их CRC-N, поэтому уникальность будет по-прежнему гарантирована.

Однако, я не знаю:

• Если можно (эффективно) быть продлен до 128-битовых данных.
• Если какое-либо дополнение к умножению на соль, чтобы обеспечить начальное семя для последовательности, это нарушит его или приведет к столкновениям.

---

Последующая деятельность

Я понимаю, что я мог бы использовать 128bit случайную хэш из libssl или что-то подобное, но я хочу, удаленный сервер, используя то же значение соли, чтобы иметь возможность конвертировать хешированные временные метки возвращаются к их истинным значениям.

спасибо.

Answer 1

Вы можете использовать линейный конгруэнтный генератор . При правильных параметрах гарантируется получение неповторяющихся последовательностей [уникальных] последовательностей с полным периодом (т. Е. Никаких столкновений).

Это то, что random(3) использует в TYPE_0 режиме. Я адаптировал его для полного диапазона unsigned int, и семена могут быть любыми unsigned int (см. Мой пример кода ниже).

Я считаю, что он может быть расширен до 64 или 128 бит. Я бы посмотрел на: https://en.wikipedia.org/wiki/Linear_congruential_generator, чтобы узнать о ограничениях параметров для предотвращения столкновений и хорошей случайности.

Следуя рекомендациям по вики-странице, вы можете создать тот, который может принимать любое значение 128 бит в качестве семени и не будет повторяться до тех пор, пока не будут созданы все возможные 128-разрядные номера.

Возможно, вам понадобится написать программу для создания подходящих пар параметров, а затем проверить их на «лучшую» случайность. Это будет одноразовая операция.

Как только вы их получите, просто включите эти параметры в свое уравнение в своем фактическом приложении.

---

Вот код моего, что я играл с тем, когда я искал что-то подобное:

// _prngstd -- get random number 
static inline u32 
_prngstd(prng_p prng) 
{ 
    long rhs; 
    u32 lhs; 

    // NOTE: random is faster and has a _long_ period, but it _only_ produces 
    // positive integers but jrand48 produces positive _and_ negative 
#if 0 
    rhs = jrand48(btc->btc_seed); 
    lhs = rhs; 
#endif 

    // this has collisions 
#if 0 
    rhs = rand(); 
    PRNG_FLIP; 
#endif 

    // this has collisions because it defaults to TYPE_3 
#if 0 
    rhs = random(); 
    PRNG_FLIP; 
#endif 

    // this is random in TYPE_0 (linear congruential) mode 
#if 0 
    prng->prng_state = ((prng->prng_state * 1103515245) + 12345) & 0x7fffffff; 
    rhs = prng->prng_state; 
    PRNG_FLIP; 
#endif 

    // this is random in TYPE_0 (linear congruential) mode with the mask 
    // removed to get full range numbers 
    // this does _not_ produce overlaps 
#if 1 
    prng->prng_state = ((prng->prng_state * 1103515245) + 12345); 
    rhs = prng->prng_state; 
    lhs = rhs; 
#endif 

    return lhs; 
} 

Answer 2

Короткий ответ - это шифрование. С набором из 128-битных значений они передают их в AES и получают другой набор из 128-битных значений. Поскольку шифрование является обратимым, выходы гарантируют уникальный для уникальных входов с фиксированным ключом.

Шифрование - это обратимое взаимно однозначное сопоставление входных значений с выходными значениями, каждый набор является полной перестановкой другой.

Поскольку вы, по-видимому, не повторяете свои входы, то, скорее всего, будет режим ECB, если вы не нуждаетесь в большей степени безопасности. Режим ECB уязвим, если используется многократно с идентичными входами, что, похоже, не здесь.

Для входов короче 128 бит, затем используйте фиксированный метод заполнения, чтобы сделать их правильной длиной. До тех пор, пока уникальность входов не будет затронута, тогда отступы могут быть достаточно гибкими. Нулевого заполнения, на обоих концах (или в начале внутренних полей) вполне может быть достаточно.

Я не знаю ваших подробных требований, поэтому не стесняйтесь изменять мой совет.

Answer 3

Где-то между линейными конгруэнтными генераторами и функциями шифрования существует хэш, которые могут преобразовывать линейные счетчики в допустимые псевдослучайные числа.

Если у вас есть 128-битные целочисленные типы (например, __int128 в GCC при построении для 64-битной цели) или готовы реализовать такие длинные перемножения вручную, то вы можете расширить их на конструкцию используется в SplitMix64. Я сделал довольно поверхностный поиск и подошел со следующими параметрами:

uint128_t mix(uint128_t x) { 
    uint128_t m0 = (uint128_t)0xecfb1b9bc1f0564f << 64 
       | 0xc68dd22b9302d18d; 
    uint128_t m1 = (uint128_t)0x4a4cf0348b717188 << 64 
       | 0xe2aead7d60f8a0df; 
    x ^= x >> 59; 
    x *= m0; 
    x ^= x >> 60; 
    x *= m1; 
    x ^= x >> 84; 
    return x; 
} 

и обратное:

uint128_t unmix(uint128_t x) { 
    uint128_t im0 = (uint128_t)0x367ce11aef44b547 << 64 
        | 0x424b0c012b51d945; 
    uint128_t im1 = (uint128_t)0xef0323293e8f059d << 64 
        | 0x351690f213b31b1f; 
    x ^= x >> 84; 
    x *= im1; 
    x ^= x >> 60^x >> (2 * 60); 
    x *= im0; 
    x ^= x >> 59^x >> (2 * 59); 
    return x; 
} 

Я не уверен, если вы хотели только случайную последовательность, или путь к запутать произвольную метку времени (так как вы сказали, что вы хотели, чтобы расшифровать значения они должны быть более интересными, чем линейный счетчик), но один получает от других достаточно просто:

uint128_t encode(uint128_t time, uint128_t salt) { 
    return mix((time + 1) * salt); 
} 

uint128_t generate(uint128_t salt) { 
    static uint128_t t = 0; 
    return encode(t++, salt); 
} 

static uint128_t inv(uint128_t d) { 
    uint128_t i = d; 

    while (i * d != 1) { 
     i *= 2 - i * d; 
    } 
    return i; 
} 

uint128_t decode(uint128_t etime, uint128_t salt) { 
    return unmix(etime) * inv(salt) - 1; 
} 

Обратите внимание, что salt выбирает одну из 2-х разрядов не повторяющихся 128-битных значений (мы теряем один бит, потому что salt должен быть нечетным), но есть (2)! возможные последовательности, которые могли быть сгенерированы.В другом месте я смотрю на расширение параметризации, чтобы можно было посещать больше этих последовательностей, но я начал работать с вышеупомянутым методом для увеличения случайности последовательности, чтобы скрыть любые проблемы, когда параметры могли выбирать не так-случайные (но доказуемо отличные) последовательности.

Очевидно, что uint128_t не является стандартным типом, поэтому мой ответ не является C, но для выполнения арифметической работы вы можете использовать библиотеку bignumber или расширение компилятора. Для ясности я полагался на расширение компилятора. Все операции основаны на C-подобном неподписанном поведении переполнения (принимают младшие разряды результата произвольной точности).