Xpoint
   [напомнить пароль]

Генерирование уникальных серийных кодов

Метки: [без меток]
2007-08-13 19:11:07 [обр] Rom McRitsky(0/441)[досье]

Есть задача: сгенерировать несколько десятков тысяч серийных номеров. Было принято решение генерировать 16-знаковые последовательности вида \d{4}-\d{4}-\d{4}-\d{4}. Генерировались без формулы, по рандому. Делалось это на PHP. Было замечено, что при использовании mt_rand повторы пошли где-то с 50-й тысячи. Чем дальше - тем больше.

Вопрос.

Насколько способ с генерированием при помощи mt_rand дыряв? Учитывая, что затравка произвольно меняется через каждые 10-20 итераций? Как сгенерировать N уникальных серийных номеров, чтобы, имея 5/10/100 реальных, невозможно было подобрать (сгенерировать) номера из того же множества? Наличие формулы для генерирования не нужно, т.к. номера будут храниться в онлайн-базе.

спустя 31 минуту [обр] dimagolov(0/3)[досье]
ИМХО задача стоит иначе. Есть часть которая несет номер (уникальный) и есть часть, которая несет хеш этого номера. При проверки номера на валидность просто берем и проверяем хеш. А про генерацию/получение уникальных ключей была тема тут
спустя 1 день 18 часов [обр] Rom McRitsky(0/441)[досье]
Повторюсь. В серийнике не нужно (в моем случае) хранить хеш. Т.к. это дополнительная дыра (зная алгоритм, можно генерировать серийники). Онлайн-сервис имеет возможность проверить валидность кода простым запросом к локальной базе.
спустя 16 часов [обр] dimagolov(0/3)[досье]

Rom McRitsky[досье], а что значит на PHP используя mt_rand и затравка произвольно меняется через каждые 10-20 итераций? неужели использование mt_srand()? если да, то именно в этом проблема должна быть.
ИМХО, тебе надо было делать просто так:

for ($i = 0; i$ < $SN_num; i++)
echo mt_rand(1000,9999).'-'.mt_rand(1000,9999).'-'.mt_rand(1000,9999).'-'.mt_rand(1000,9999);

C учетом того, что алгоритм имеет периодичность 2^19937-1, то конечно отдельные 4-х значные числа повторяться будут, но сама последовательность из 4-х повториться не должна.

спустя 15 часов [обр] Rom McRitsky(0/441)[досье]

Я понятия не имею, как работает mt_srand и насколько периодичность значений зависит (и предугадывается) в зависимости от завтравки. В целом функция выглядит где-то так:

function get_random() {
    if(mt_rand(0, 10)==5)
        mt_srand(make_seed()); 
    return sprintf("%04d-%04d-%04d-%04d", mt_rand(0, 9999),mt_rand(0, 9999),mt_rand(0, 9999),mt_rand(0, 9999));
}

Основной вопрос состоит в том, на сколько такой способ дыряв и раскрываем.

спустя 1 час 1 минуту [обр] dimagolov(0/3)[досье]
  1. уберите mt_srand, чтобы не получать повторов
  2. насколько дыряв?
всего у нас может быть 10^16 степени кодов. генерим 10^5 разных кодов, то есть вероятность случайного подбора 10^-11.
спустя 17 часов [обр] Даниэль Алиевский(1/125)[досье]

Извините, если я из-за незнания PHP или недостаточного вникания в тему чего-то не понимаю. Но как вообще можно генерировать уникальные, неподбираемые коды с помощью генератора псевдослучайных чисел, о чем к тому же Вы любезно рассказываете на публичном форуме? Ведь "уникальность" всей последовательности серийных кодов в таком случае строго равна уникальности стартового значения для датчика, которое, вероятно, берется из системного времени (типа числа миллисекунд от 1970 года), а таких стартовых значений существует очень и очень немного.

Я всегда почему-то думал, что любые секретные коды вроде серийных номеров можно генерировать только на основе истинно случайных чисел, получаемых из внешнего физического датчика или всякими хитроумными утилитами, анализирующими нестабильности тактового генератора и т.п. Как компромисс, когда безопасность волнует не очень сильно (противостоять спецслужбам не предполагается :)), я обычно беру для такой цели какой-нибудь zip-файл, известный только мне (заархивированное собрание моих любимых разработок), разбиваю его на части и вычисляю MD5 по его фрагментам. Подобрать такую последовательность можно, только зная мой "ключевой" файл.

спустя 8 часов [обр] Сергей Сирик(28/737)[досье]
Rom McRitsky[досье]
Алгоритмы генерации случайных чисел в большом количестве описаны в литературе ... много лет тому назад. Ничего особо сложного в них нету, чтобы нельзя было выбрать наиболее похожий и дописать свой генераторчик, под данную конкретную задачку. Если не найдет Гугль алгоритм - то можно для разнообразия сходить в какую-то научную билиотеку :)
спустя 1 год 1 месяц [обр] Антон Клесс(0/25)[досье]

Даниэль Алиевский[досье], можно сделать менее ресурсоемко: перепрошиваем HDD на раскрутку бинов и через (псевдо)случайное время чтение (псевдо)случайного сектора. Имеем salt.

Лучше использовать диск с bad-блоками.

спустя 17 дней [обр] Даниэль Алиевский(1/125)[досье]
Даже странно, что до сих пор компьютеры не оснащаются физическими датчиками для генерации истинно случайных чисел. По идее, при поточном производстве цена такому датчику - грош. Куда меньше стоимости разработки хитроумных и все равно ненадежных программных имитаторов.
спустя 2 дня 23 часа [обр] Алексей Полушин(0/231)[досье]
спустя 6 часов [обр] Thirteensmay(0/157)[досье]
Даниэль Алиевский[досье] Зато некоторые ОС уже давно оснащаются специальными дырами безопасности ;) А вот с физическими генераторами... ну в 2002 году покупал себе чисто ширпотребовскую матплату Epox для домашней машинки, при ближайшем рассмотрении документации оказалось что на плате есть такая специальная микросхема для генерации случайных чисел, но физически она была не распаяна... ;) Да вообще то в принципе оно мало кого колышет.
Powered by POEM™ Engine Copyright © 2002-2005