Генерация ключей
4037
16
Уважаемые форумчане!

Подскажите, пожалуйста, идею для генерации последовательности уникальных числовых ключей, то есть, отображения исходной натуральной последовательности на некоторую другую. Условия:

1. Исходные числовые величины сравнительно небольшие, в пределах одной-нескольких тысяч.
2. Получаемые числа должны быть в пределах 5-6 десятичных цифр.
3. Генерируемая последовательность должна быть по видимости хаотичной - по ключам не должно быть с ходу понятно, какое из них получилось из бОльшего, а какое из меньшего исходного значения.
4. Простой алгоритм прямой проверки (без перебора предшествующих значений), является ли ключ правильным, а также получения по ключу исходного индекса.

Навскидку пришедший в голову вариант: в соответствии с правилами кода Хэмминга к 11 разрядам исходного значения добавить еще 4 разряда избыточности, а затем некоторая манипуляция, связанная с перестановкой разрядов. Если так, то в каком порядке лучше переставлять разряды? Или есть другие идеи?
Спасибо.
wowik_2
Не проще использовать стандартный генератор случайных величин а потом просто добавлять избыточность? Смысл в перестановке?
Неместный
Рассматривал и такую возможность. Но генератор случайных чисел потребовал бы тогда перебора всех предшествующих значений для проверки правильности. А если ключ неправильный - сколько раз его крутить? К тому же, полагаться на конкретный ГСЧ тоже неохота. К примеру, в Дельфях он один, в .NET - другой. В смысле, дают разные последовательности. А вдруг я захочу этот алгоритм перенести куда-то в другое место?
wowik_2
Ну куда уж проще, получаешь системное время, выделяешь милисекунды. Куда уж случайнее?
Как вариант (которым, кстати, я сам пользуюсь). Генерируешь штук несколько случайных чисел, из них получаешь пару первых последовательностей, комбинируя практически от балды (уж как переставишь, сложишь, умножишь, так и получится). Далее по определенным правилам из них же получаешь вторую пару 5-символьных последовательностей. Проверка валидности - по первой последовательности восстанавливаешь исходные числа, генерируешь "ответную" вторую пару и сравниваешь.
wowik_2
4. Простой алгоритм прямой проверки (без перебора предшествующих значений), является ли ключ правильным,
Я это не понимаю
Picaro
Я как раз имел в виду, что не хочу использовать ГСЧ. То есть, последовательность должна быть хаотичной только по виду. Пусть она подчиняется определенным правилам, лишь бы они не были очевидными. Кроме того, по предъявленному ключу надо достаточно просто восстановить исходный индекс, то есть, не просто проверить, что ключ правильный, но и в каком месте списка он располагается.
KSergey
Я это не понимаю
Это значит, что, выполнив достаточно простую последовательность арифметико-логических действий (не превышающую фиксированного их количества, не зависящего от значения), можно было бы проверить, правильный ключ или нет. А заодно и вычислить исходный индекс.
wowik_2
последовательность должна быть хаотичной только по виду
Если вы думаете, что все знают только про плюс и минус и сравнивать умеют числа только на больше-меньше, а про перестановку битов не знают - то вы заблуждаетесь:улыб:Я это к чему - "неочевидность" в десятичном выражении вовсе не означает, что заинтересовавшиеся люди (если такие вдруг будут) тут же не переведут это в двоичный вид, где все станет очевидно.

В общем добавляйте контрольную сумму и переставляйте биты - вот и все решение.

Добавлять или нет случ. чсло - не важно, и вот почему.
Для вас это добавляемое число - да, случайное.
Но посмотрим на эту ситуации с точки зрения хацкера. Берет он индекс и ключ (раскопать под отладчиком при наличии ключа и софтины, его кушающей, не сложно) и смотрит: как же из индекса получить ключ? путем несложных умозаключений (или прочитав алгоритм обратной операции) приходит к выводу: ага, приписали число 5, посчитали и приписали контрольную сумму, потом перемешали биты - и вуаля.
Нафик 5? почему 5? ну потому, что когда генерировали эту пару - выпало 5. 5 - это вполне случайное число, однако если в этом алгоритме заменить случ. число на любую константу - он будет давать вполне подходящие по функциональности числа! что, собственно, хацкеру и надо: получить алгоритм с итоговым результатом (функционально) не отличающимися от генерации "праивльным" алгоритмом, а вовсе не восстановить истинный алгоритм. Что он и получит.

Так что ГСЧ тут бесполезен.
KSergey
Требования безопасности тут нет. Вообще. Скорее, способ сделать "умный вид":миг:- типа, мы тоже не лыком шиты, и личные ключи могём делать. :ха-ха!: Ну и некая подстраховка от ошибок.
В общем, идея такая - клиенту выдается числовой токен. Он его может передать другому потенциальному клиенту, и когда тот его предъявляет, он и владелец токена получают некий бонус. То есть, некое подобие акции "приведи друга". Выдавать токены в порядке натурального ряда не очень хочется - тогда сразу будет видно, какой клиент обслуживается раньше. А при видмой хаотичности таких ассоциаций не возникает (чисто психологический момент!). В то же время не хочется, чтобы, приходя, кто-то называл номер "от балды". И не хочется заморачиваться с требующими временнЫх затрат поисками в заготовленной базе СЧ.
К тому же, подготовка этой базы не так очевидна, как кажется на первый взгляд: массовые ГСЧ дают последовательность из 2^31 - 1 или 2^32 - 1 неповторяющихся значений. Это значит, что при отсечении до 16 разрадов будут повторы. Где гарантия, что в любой навскидку взятой последовательности из 1000 псевдослучайных целых чисел не будет двух одинаковых? Значит, при генерации нужен какой-то контроль наличия очередного значения в базе. Все, конечно, решается элементарно, но тут скорее вопрос вкуса - ну не люблю я алгоритмов с квадратичной временнОй зависимостью, если в конкретных условиях можно обойтись линейной или константной.:миг:
Поэтому вопрос изначально ставился так (извините, если в исходной формулировке это прозвучало недостатоточно отчетливо): требуется обратимое преобразование на множестве натуральных чисел, которое переводит натуральный ряд в натуральную последовательность, которая похожа на случайную (на самом деле она, разумеется, детерминированная, но правило ее вычисления не очевидно для неискушенного человека). Ну и плюс к тому некая защита от ошибок за счет избыточности.
В общем, как-то так.
wowik_2
В такой постановке ответ давно дан.
Замахивание на 2^32-1 продаж позабавило.
Зачем вообще вы смотрите на ДСЧ - все равно не понять.
wowik_2
Берём последовательность из N натуральных чисел, например, при N = 5 имеем 1, 2, 3, 4, 5.

Перемешиваем её случайным образом, например, 3, 1, 5, 2, 4 и запоминаем в массиве "Ключи".

В массиве "Индексы" записываем индексы ключей (пусть индекс начинается с 1), причём в качестве индекса этого массива выступает ключ. Получим: 2, 4, 1, 5, 3.

Таким образом, имеем:
3, 1, 5, 2, 4 - Ключи
2, 4, 1, 5, 3 - Индексы

Ключи выдаются по порядку из массива "Ключи". По массиву "Индексы", используя ключ в качестве индекса, находятся порядковые номера ключей.
Паря
Ладно, все ясно. Не могу донести суть задачи, значит, сам ее до конца не понял. Буду думать дальше. Всем спасибо! :respect:
wowik_2
Я, вообще то, предложил возможное решение вот этой задачи:
В общем, идея такая - клиенту выдается числовой токен. Он его может передать другому потенциальному клиенту, и когда тот его предъявляет, он и владелец токена получают некий бонус. То есть, некое подобие акции "приведи друга". Выдавать токены в порядке натурального ряда не очень хочется - тогда сразу будет видно, какой клиент обслуживается раньше. А при видмой хаотичности таких ассоциаций не возникает (чисто психологический момент!). В то же время не хочется, чтобы, приходя, кто-то называл номер "от балды". И не хочется заморачиваться с требующими временнЫх затрат поисками в заготовленной базе СЧ.
Ну, нет, так нет. :спок:
wowik_2
Ладно, все ясно. Не могу донести суть задачи, значит, сам ее до конца не понял. Буду думать дальше. Всем спасибо! :respect:
Ххе.. а мне задачка понравилась...
Она на самом деле проще чем теория множеств... И поиск функции, которая отражает одно множество в другое однозначно.

Во вложении моя поделка. Даже распределение получилось нормальным.
Можно поиграться коэффициентами в желтых полях.

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

Правда вылезла багофича - оригинальные порядковые номера не должны быть кратны 16. Связано с лидирующими нулями. Правда, при некоторых параметрах вылазят другие артефакты. Глубоко не копал...

Ну, в общем можно поиграться значениями...
an_onim
Спасибо, идея интересная. Обязательно посмотрю поподробнее. :respect:
an_onim
Посмотрел. Багофича связана с тем, что Ехсель при преобразовании в 16-ричную строку по умолчанию отбрасывает ведущие нули. Поскольку при реальном преобразовании я вряд ли буду преобразовывать в текстовую запись и обратно, а скорее, манипулировать с битами непосредственно в двоичном представлении, эта проблема снимается. Еще раз спасибо за идею!
wowik_2
идея интересная. Обязательно посмотрю
Все еще верите в "математические фокусы"?