Кратко. Человеку нужно генерить униальные ID-шки в формате XX000000, где XX -- две буквы латинского алфавита, 0 -- число от 0 до 9. Главное условие -- чтобы проклятые конкуренты не могли по номеру ID-ки вычислить сколько всего клиентов в базе. Конкуренты могут делать фейковые записи с целью получить n ID-ов, идущих подряд.
Для человека задача показалась мега-сложной, что даже пришлось привлечь этот страшный BigData, которого ни друг ни враг в лицо не знает. Т.е. перебрал все возможные варианты, перемешал, сохранил в одну большую мега=таблицу на 20 гиг а потом долго оптимизировал базу, чтобы быстро выбирать эти ID-ки.
Как с помощью гения инженерной мысли и 5-10 строчек на псевдокоде избавить человека от большого и старшного BigData?
Re: Избавить человека от BigData с помощью 5 строчек кода
S>Как с помощью гения инженерной мысли и 5-10 строчек на псевдокоде избавить человека от большого и старшного BigData?
последовательные номера + сильное шифрование, не?
Как много веселых ребят, и все делают велосипед...
Re[2]: Избавить человека от BigData с помощью 5 строчек кода
Здравствуйте, ononim, Вы писали:
O>последовательные номера + сильное шифрование, не?
Надо ещё проверить, что не совпало ни с одним из предыдущих. А если совпало — перегенерить и снова проверять. Если почти все логины заняты — это может быть долго. Чуть быстрее — хранить в массиве все уже розданные логины в упорядоченном виде, после шифрования брать остаток от деления на количество свободных логинов, бинарным поиском находить, в какой из промежутков новый логин попал, и вычислять, чему он теперь равен. После этого нужно его вставить в этот упорядоченный массив, но это стоит столько же, сколько стоит один раз проверить на совпадение перебором. Если O(m) недопустимо, то хранить розданные логины в бинарном сбалансированном дереве с порядковой статистикой (количество узлов со значениями меньше текущего), тогда всё обойдётся в O(log(m)), с константой порядка шести 32-битных элементов на запись. Надо быть готовым, что конкуренты забьют почти все номера, то есть держать файл на примерно 16 гигов. Опять же, если они сразу забьют все номера кроме последнего, то они будут точно знать, чему равен этот последний
Вот только какой смысл? Тогда не получится написать в резюме, что работал с BigData.
Re[3]: Избавить человека от BigData с помощью 5 строчек кода
O>>последовательные номера + сильное шифрование, не? C>Надо ещё проверить, что не совпало ни с одним из предыдущих. А если совпало — перегенерить и снова проверять.
Шифрование != хэширование. Проверять ничего не нужно. Достаточно последовательного инкремента исходных данных. Это конечно если считать что никогда не наступит переполнения и изымания/реюзания предыдущих ид-шников, в таком случае придется таки скатиться к БД.
Как много веселых ребят, и все делают велосипед...
Здравствуйте, ononim, Вы писали:
O>>>последовательные номера + сильное шифрование, не? C>>Надо ещё проверить, что не совпало ни с одним из предыдущих. А если совпало — перегенерить и снова проверять. O>Шифрование != хэширование. Проверять ничего не нужно. Достаточно последовательного инкремента исходных данных. Это конечно если считать что никогда не наступит переполнения и изымания/реюзания предыдущих ид-шников, в таком случае придется таки скатиться к БД.
вот у нас счётчик заюзаных, хороший рандом, чтобы выход в диапазоне [0..счётчик-1], и один линейный проход по битмапке, который из выхода рандома получает реальный новый ключ.
а с шифрованием бы не связывался, потому что что будешь делать, если ключ утёк.
AG>XX000000 AG>26*26*1000000 = 676000000 ключей AG>676000000 / 8 = 84 500 000 байт битмапка заюзаных.
Ну битмапка с моей колокольни — частный случай БД.
AG>а с шифрованием бы не связывался, потому что что будешь делать, если ключ утёк.
Ну вероятность утекания ключа в данном случае я бы оценил примерно так же как вероятность утекания сведений, которые с его помощью можно спереть — то есть количество клиентов. Так что это не релевантная проблема.
AG>вот у нас счётчик заюзаных, хороший рандом, чтобы выход в диапазоне [0..счётчик-1], и один линейный проход по битмапке, который из выхода рандома получает реальный новый ключ.
А по поводу защиты от мегахакеров, которым прям так хочется знать сколько у вас клиентов и все на этом, думаю что стойкость данной системы при использовании любого рандома упрется в криптостойкость этого самого рандома.
Как много веселых ребят, и все делают велосипед...
Re[2]: Избавить человека от BigData с помощью 5 строчек кода
Здравствуйте, ononim, Вы писали:
S>>Как с помощью гения инженерной мысли и 5-10 строчек на псевдокоде избавить человека от большого и старшного BigData? O>последовательные номера + сильное шифрование, не?
По-моему не прокатит. Для сильного шифрования нужен большой блок (32 байта или более). А у него пространство значений всего около 3 байт. Т.е. по нескольким последовательным значениям будет реально взломать ключ и угадывать следующие.
Самый жизнеспособный вариант — выбирать случайно, проверять на дупликат (выбор по хеш-таблице) — и повторять, если уже использован.
В случае когда количество занятых логинов будет велико, т.е. выберется почти всё пространство — количество повторов может сильно возрасти — проще всего увеличить количество значений. Если это невозможно расширить — создать и перемешать табличку оставшихся логинов, она будет небольшой на том этапе, по крайней мере значительно меньше, чем остальная база пользователей.
Можно держать пул (можно даже распределённый) свободных логинов, если требуется переживать пиковые нагрузки.
но это не зря, хотя, может быть, невзначай
гÅрмония мира не знает границ — сейчас мы будем пить чай
Re[5]: Избавить человека от BigData с помощью 5 строчек кода
Alexander G, Вы писали:
AG>676000000 / 8 = 84 500 000 байт битмапка заюзаных.
Это просто "повезло" с требованием. А завтра понадобится формат XXX0000000X для номеров заказов и битмапка ВНЕЗАПНО станет терабайтной.
но это не зря, хотя, может быть, невзначай
гÅрмония мира не знает границ — сейчас мы будем пить чай
Re[3]: Избавить человека от BigData с помощью 5 строчек кода
S>>>Как с помощью гения инженерной мысли и 5-10 строчек на псевдокоде избавить человека от большого и старшного BigData? O>>последовательные номера + сильное шифрование, не? ·>По-моему не прокатит. Для сильного шифрования нужен большой блок (32 байта или более). А у него пространство значений всего около 3 байт. Т.е. по нескольким последовательным значениям будет реально взломать ключ и угадывать следующие.
Ну надо порыть криптоалгоритмы который из них шифрует с очень маленьким блоком и при этом стоек к known plain text attack. Можно начать с чтения этого.
Как много веселых ребят, и все делают велосипед...
Re[4]: Избавить человека от BigData с помощью 5 строчек кода
Здравствуйте, ononim, Вы писали:
S>>>>Как с помощью гения инженерной мысли и 5-10 строчек на псевдокоде избавить человека от большого и старшного BigData? O>>>последовательные номера + сильное шифрование, не? O>·>По-моему не прокатит. Для сильного шифрования нужен большой блок (32 байта или более). А у него пространство значений всего около 3 байт. Т.е. по нескольким последовательным значениям будет реально взломать ключ и угадывать следующие. O>Ну надо порыть криптоалгоритмы который из них шифрует с очень маленьким блоком и при этом стоек к known plain text attack. Можно начать с чтения этого.
Да, ты прав. Возможно.
Но я бы в данном случае всё равно бы такое не использовал, т.к. есть три проблемы — придётся обеспечивать хранение секрета, невозможно этот секрет менять позже, невозможно расширять пространство значений при необходимости.
но это не зря, хотя, может быть, невзначай
гÅрмония мира не знает границ — сейчас мы будем пить чай
Re: Избавить человека от BigData с помощью 5 строчек кода
Взять GIUD (если кому мало — два), зашифровать случайным ключом (третьим GIUD-ом), взять средние n байт, преобразовать в нужный формат, проверить на дубли. Всё.
Re[4]: Избавить человека от BigData с помощью 5 строчек кода
Здравствуйте, ononim, Вы писали:
O>Шифрование != хэширование. Проверять ничего не нужно. Достаточно последовательного инкремента исходных данных. Это конечно если считать что никогда не наступит переполнения и изымания/реюзания предыдущих ид-шников, в таком случае придется таки скатиться к БД.
Не совсем. К примеру, у нас есть шифр с 64-битными блоками. Ну, например, DES. Если кормить его счетчиком, получим псевдослучайную последовательность чисел в диапазоне от 0 до 18446744073709551615 без повторов. А нам, к примеру, надо от 0 до 9999999. Следовательно, DES не очень-то подходит, слишком много неподходящих ответов он будет выдавать.
Заметим, что если отрезать от DES'а лишние биты, то последовательность остается псевдослучайной, но теряется гарантия неповторяемости.
Я бы взял шифр с длинной блока N такой, что 2^N-1 не меньше верхней границы диапазона, в который надо попасть, а 2^(N-1) — 1 уже меньше. Кормил бы его счетчиком и отбрасывал неподходящие значения — их не больше половины, потому что мы так выбрали размер блока.
Вопрос в том, где взять шифр с нужной (произвольной) длинной блока. Я думаю, этот вопрос имеет ответ, но этим пришлось бы заниматься.
Re[4]: Избавить человека от BigData с помощью 5 строчек кода
Здравствуйте, ononim, Вы писали:
O>Ну надо порыть криптоалгоритмы который из них шифрует с очень маленьким блоком и при этом стоек к known plain text attack. Можно начать с чтения этого.
В принципе, в этой статье сказано, как сгенерировать кусок псевдослучайной перестановки из N чисел, без необходимости хранить в памяти все N чисел, и при этом за разумное время.
Они делают из этого блочный шифр, но в принципе, статья содержит именно что решение задачи, поставленной в начале этой дискуссии.
Внимательно статью читать лень.
Re[2]: Избавить человека от BigData с помощью 5 строчек кода
Здравствуйте, wildwind, Вы писали:
W>Взять GIUD (если кому мало — два), зашифровать случайным ключом (третьим GIUD-ом), взять средние n байт, преобразовать в нужный формат, проверить на дубли. Всё.
Во-первых, эта конструкция с тремя GUIDами ничем не лучше, чем просто нагенерить нужное количество бит от криптографического генератора случайных чисел. На самом деле, даже хуже, потому что она может и не выдать всех возможных вариантов выходного значения.
Во-вторых, проверка на дубли может оказаться дорогим удовольствием.
В-третьих, когда большая часть значений уже использована, каждое следущее с очень большой вероятностью будет дублем, и найти следущее уникальное значение будет все сложнее и сложнее.
Re: Избавить человека от BigData с помощью 5 строчек кода
Здравствуйте, Shmj, Вы писали:
S>Как с помощью гения инженерной мысли и 5-10 строчек на псевдокоде избавить человека от большого и старшного BigData?
Эээ, а с каких пор жалкие 700 миллионов стало бигдатой? Я думал, что детская бигдата начинается с 700 миллиардов, объемы данных — петабайты, и это еще хорошо и оптимально упакованные данные.
А тут, если особо не заморачиваться. Тупо рандом из диапазона и складывание результата в массив булевых переменных не прокатит? Под массив из 700 миллионов булевых нужно 87 мегабайт, объем детский. Если n раз рандом (допустим N = 100) не получился плюс инкрементом от рандома (пусть еще n раз) всегда попадаем на уже сгенерированный номер, значит мы диапазон довольно неплохо забили. Это случится наверно лет через 100 . Через 100 лет, если вдруг понадобится далее, пробегаем по всему массиву линейно и там, где остались пустые — перекладываем индексы уже в массив от целых индексов в первом массиве. Линейно прогон этих жалких 87 мегабайт будет занимать доли секунды, и это 1 раз только нужно будет делать. Далее массив на 97 мегабайт освобождаем, он уже не нужен, и просто последовательно выбираем элементы из оставшегося массива.
Re[3]: Избавить человека от BigData с помощью 5 строчек кода
Здравствуйте, Pzz, Вы писали:
Pzz>Во-первых, эта конструкция с тремя GUIDами ничем не лучше, чем просто нагенерить нужное количество бит от криптографического генератора случайных чисел. На самом деле, даже хуже, потому что она может и не выдать всех возможных вариантов выходного значения.
У нас не стоит задача получить все возможные варианты.
Pzz>Во-вторых, проверка на дубли может оказаться дорогим удовольствием.
С чего бы?
Pzz>В-третьих, когда большая часть значений уже использована, каждое следущее с очень большой вероятностью будет дублем, и найти следущее уникальное значение будет все сложнее и сложнее.
Если проект доживет до этой стадии, длину ID можно расширить. Можно заранее.
Re[4]: Избавить человека от BigData с помощью 5 строчек кода
Здравствуйте, ononim, Вы писали:
O>Ну надо порыть криптоалгоритмы который из них шифрует с очень маленьким блоком и при этом стоек к known plain text attack. Можно начать с чтения этого.
Ну а если попытаться без экзотических алгоритмов, по простому.
Предлагаю такой алгоритм.
Имеем:
1. Секретный ключ для HMAC SHA1 (без разницы, можно и MD5).
2. Номера пользователей в базе по порядку, наверх отдаем криптопреобразование.
Делаем:
1. Номер пользователя представляем в виде 16+6=22 бит. Это с запасом.
2. Условно делим 22 бита на 2 группы по 11 бит.
Для шифрования:
1. Делаем HMAC правой части (от правых 11 бит) с секретным ключом. Получаем ХЕШ 1. Хеш 1 пользователь получить не сможет, так как у него нет секретного ключа.
2. Накладываем XOR-ом получившийся ХЕШ 1 на левые 11 бит.
3. Делаем HMAC левых 11 бит (которые уже XOR-нутые) с секретным ключом. Получаем ХЕШ 2. Т.к. у пользователя нет секретного ключа, то он не может сделать обратное преобразование.
4. Накладываем XOR-ом ХЕШ 2 на правые 11 бит.
Обратная бадяга:
1. Делаем ХЕШ 2 из левых 11 бит (HMAC с ключом).
2. Опять XOR-ом накладываем на правую часть.
3. Делаем HMAC правой части, это хеш 1.
4. Накладываем XOR-ом на левую часть.
Есть вероятность что после XOR-а число будет чуть больше чем требуется (но менее чем на 1 бит). С этим можно что-то сделать (типа по модулю значение взять), но хотелось бы улышать другое:
Здравствуйте, Shmj, Вы писали:
S>Кратко. Человеку нужно генерить униальные ID-шки в формате XX000000, где XX -- две буквы латинского алфавита, 0 -- число от 0 до 9. Главное условие -- чтобы проклятые конкуренты не могли по номеру ID-ки вычислить сколько всего клиентов в базе. Конкуренты могут делать фейковые записи с целью получить n ID-ов, идущих подряд.
Самое тупое — взять список всех ID, перемешать их и сохранить в файл. Это будет порядка пары гигабайт (всего 676 миллионов вариантов).
Более интересное решение — использовать "Format Preserving Encryption". Стандартов на него пока нет, но вручную достаточно легко реализуется "cycle-walking". Делаем счётчик в 32 бита, затем берём RC5 с размером блока в 32 бита, шифруем значение и делаем cycle-walking пока оно не поместится в 676 миллионов (в среднем 8 шагов, ерунда).
Телемаркет.
В качестве бонуса, алгоритм реверсируемый — можно взять зашифрованный ID и получить исходное значение счётчика.
