S>Где я прокололся?
Честно говоря разбираться лень, но знаю точно что если вы не математик с уклоном в криптографию то лучше свои криптоалгоритмы не сочинять, а использовать то что сочинили математики.

Здравствуйте, Shmj, Вы писали:

S> Где я прокололся?
Не понял как ты гарантируешь, что сгенерённые таким образом значения будут уникальны. Использование хеша однозначно говорит о том, что могут быть коллизии.

S>>Кратко. Человеку нужно генерить униальные ID-шки в формате XX000000, где XX -- две буквы латинского алфавита, 0 -- число от 0 до 9. Главное условие -- чтобы проклятые конкуренты не могли по номеру ID-ки вычислить сколько всего клиентов в базе. Конкуренты могут делать фейковые записи с целью получить n ID-ов, идущих подряд.
C>Самое тупое — взять список всех ID, перемешать их и сохранить в файл. Это будет порядка пары гигабайт (всего 676 миллионов вариантов).
Если что это тоже по сути шифрование, такая себе разновидность "одноразового блокнота".

Здравствуйте, ·, Вы писали:

S>>>Как с помощью гения инженерной мысли и 5-10 строчек на псевдокоде избавить человека от большого и старшного BigData?
O>>последовательные номера + сильное шифрование, не?
·>По-моему не прокатит. Для сильного шифрования нужен большой блок (32 байта или более). А у него пространство значений всего около 3 байт.
Нет, не нужно. Старый добрый RC5 прекрасно работает с блоками по 32 бита — его защищённость зависит от длины ключа, которая для RC5 может быть от 64 бит до 128 бит.

То есть, мы можем взять обычный int32 и получить зашифрованный int32. Причём шифрование будет невзламываемым разумными мерами. Есть некоторые related-text атаки из-за малого размера шифртекста, но они будут требовать знать достаточно большой кусок ключевого пространства и не дадут сильного выигрыша.

Далее останется только сузить int32 до 676 миллионов. Самый простой подход — https://en.wikipedia.org/wiki/Format-preserving_encryption#FPE_from_cycle_walking

# x - чистое значение счётчика, 0<X<676000000
CycleWalkingFPE(x)
{
   if encrypt(x) < 676000000
     return encrypt(x)
   else 
     return CycleWalkingFPE(encrypt(x))
}

Тот же самый код и для расшифровки.

Ну и генерация нового ID сводится к взятию следующего значения. Я недавно переключил пару систем в Амазоне на такой подход

Здравствуйте, ononim, Вы писали:

S>>Где я прокололся?
O>Честно говоря разбираться лень, но знаю точно что если вы не математик с уклоном в криптографию то лучше свои криптоалгоритмы не сочинять, а использовать то что сочинили математики.

Нет уж, в этюдах давайте разберемся

Здравствуйте, ·, Вы писали:

S>> Где я прокололся?
·>Не понял как ты гарантируешь, что сгенерённые таким образом значения будут уникальны. Использование хеша однозначно говорит о том, что могут быть коллизии.

Уникальность хеша не требуется -- он используется только как ключ для операции XOR.

Здравствуйте, Cyberax, Вы писали:

C>Более интересное решение — использовать "Format Preserving Encryption". Стандартов на него пока нет, но вручную достаточно легко реализуется "cycle-walking". Делаем счётчик в 32 бита, затем берём RC5 с размером блока в 32 бита, шифруем значение и делаем cycle-walking пока оно не поместится в 676 миллионов (в среднем 8 шагов, ерунда).

А как вам мой алгоритм: http://rsdn.org/forum/etude/6740933.1

Автор: Shmj
Дата: 29.03.17

?

Здравствуйте, Shmj, Вы писали:

C>>Более интересное решение — использовать "Format Preserving Encryption". Стандартов на него пока нет, но вручную достаточно легко реализуется "cycle-walking". Делаем счётчик в 32 бита, затем берём RC5 с размером блока в 32 бита, шифруем значение и делаем cycle-walking пока оно не поместится в 676 миллионов (в среднем 8 шагов, ерунда).
S>А как вам мой алгоритм: http://rsdn.org/forum/etude/6740933.1

Автор: Shmj
Дата: 29.03.17

S>?
Поздравляю, вы изобрели сеть Фейстеля с HMAC в качестве раундовой функции

Это вполне разумный подход: https://en.wikipedia.org/wiki/Format-preserving_encryption#FPE_from_a_Feistel_network

Насчёт стойкости, двух раундов может быть недостаточно, так что я тупо добавил бы ещё несколько раундов туда (просто повторять процесс несколько раз). Ну и 22 бита — это немного не по условию задачи, так как не покрывает всего ключевого пространства (29 бит — наиболее близкое значение).

S>>>Где я прокололся?
O>>Честно говоря разбираться лень, но знаю точно что если вы не математик с уклоном в криптографию то лучше свои криптоалгоритмы не сочинять, а использовать то что сочинили математики.
S>Нет уж, в этюдах давайте разберемся
Ну поскольку добрые люди ваш метод идентифицировали

Автор: Cyberax
Дата: 30.03.17

, то вот вам новое чтиво, на предмет known plain text атак на него

Здравствуйте, Cyberax, Вы писали:

C>Ну и 22 бита — это немного не по условию задачи, так как не покрывает всего ключевого пространства (29 бит — наиболее близкое значение).

Ага, 29.

100000 * 26 * 26 = 101000 01001010 11110001 00000000

Но идея та же...

Здравствуйте, Pzz, Вы писали:

Pzz>В-третьих, когда большая часть значений уже использована, каждое следущее с очень большой вероятностью будет дублем, и найти следущее уникальное значение будет все сложнее и сложнее.

Когда мы используем более половины возможных кодов, мы сразу можем заменить базу использованных на базу ещё не использованных...

S>Ага, 29.

понимаю как они считали. На земле ~10 миллиардов людей, log₂ (10⁹) ≈ 29

хотя log₂ (100000 * 26 * 26) ≈ 26

Здравствуйте, Shmj, Вы писали:

S>Кратко. Человеку нужно генерить униальные ID-шки в формате XX000000, где XX -- две буквы латинского алфавита, 0 -- число от 0 до 9. Главное условие -- чтобы проклятые конкуренты не могли по номеру ID-ки вычислить сколько всего клиентов в базе.

Запихать время в ИД?

Здравствуйте, Shmj, Вы писали:

S>Где я прокололся?

Очень похоже на

Т.е. делим шифруемые данные пополам (l, r), (l ^ f(r), r) и переставляем местами: (r, l ^ f(r))
f — криптографическая функция, не обязательно обратимая.
Для стойкой функции f достаточно трех итераций. Работает и для битовых данных, и для десятичных данных.
В качестве f можно взять HMAC и обрезать результат до нужного размера.