Матрешки и теория хаоса позволили ученым ЛЭТИ разработать систему для оценки линейности источников сигналов
Исследователи предложили использовать фрактальную математическую функцию для создания алгоритма генерации случайных чисел. С его помощью, в частности, можно провести специальные тесты сигналов и узнать, можно ли описать источник сигнала как линейную систему.
В науке часто возникает вопрос, каким математическим аппаратом лучше описать ту или иную систему, будь то система регуляции сердечного ритма или глобальный климатический осциллятор. Первый выбор, который делает исследователь в поиске математического описания – использовать линейную или нелинейную модель. Чтобы объяснить разницу между линейными и нелинейными системами, приведем пример. Допустим, нам нужно выбрать класс модели, описывающей какой-либо музыкальный инструмент. Тест на линейность в этом случае будет такой: если тихий и громкий звук этого инструмента по тембру одинаковы, значит, этот инструмент хорошо описывается линейной математической моделью, иначе – нелинейной. Согласно этому критерию, для скрипки или флейты можно использовать линейные модели, а для барабана или тарелки – нелинейные модели.
Но иногда бывает очень трудно сказать, какой класс моделей лучше описывает источник конкретного сигнала, поскольку мы не имеем к этому источнику непосредственного доступа, а сам сигнал зашумлен. В этом случае помогает суррогатное тестирование. Оно заключается в том, что особая программа синтезирует множество суррогатных сигналов, т.е. напоминающих по какой-то характеристике изучаемый сигнал, и дальше применяется специальный статистический тест.
Например, исходный сигнал подвергается преобразованию Фурье, т.е. раскладывается на сумму синусоидальных волн. Затем синтезируется множество суррогатных сигналов, которые отличаются во временной области, но амплитуды волн в их преобразовании Фурье такие же, как у исходного сигнала. Если статистический тест не сможет отличить суррогатные сигналы от исходного сигнала, то источник исходного сигнала можно описывать линейной моделью.
Ясно, что на результаты суррогатного тестирования влияет качество генератора случайных (правильнее говорить – псевдослучайных) чисел, которые используются для синтеза суррогатных сигналов. На больших выборках генератор псевдослучайных чисел должен давать такие же безупречно случайные на вид числа, как и те, что используются в криптографии. К сожалению, в современных компиляторах и средах разработки обычно используются устаревшие алгоритмы, что может делать результаты суррогатного тестирования неверными. В то же время существенным недостатком многих современных криптографических генераторов псевдослучайных чисел является громоздкость применяемых в них алгоритмов. Поэтому уже два десятилетия исследователи по всему миру изучают возможность применения в генераторах псевдослучайных чисел хаотических отображений – очень компактных рекуррентных формул, буквально в одну строчку кода. Получаемые с помощью них псевдослучайные числа могут обладать всеми признаками истинно случайных чисел.
Пример такого отображения – отображение «тент». Пусть число, которые мы подаем на вход, равно x. Отображение “тент” сопоставляет этому числу новое значение x, равное минимуму из двух значений 2x и 2-2x. Здесь цифра 2 – это параметр, при котором x в точности отображается на отрезок от 0 до 1. Если взять произвольное иррациональное значение x на этом отрезке, например, корень из двух пополам, и применить к нему отображение “тент”, то х каждый раз будет принимать новое уникальное значение до тех пор, пока будут позволять ограничения представления чисел в компьютере. Любой значащий бит представления этого числа будет псевдослучайным двоичным числом. Отображение «тент» получило свое название из-за вида графика (похож на треугольник). Если по оси x отложить текущее значение переменной х, а по оси y – ее новое значение, то получится равнобедренный треугольник, напоминающий тент или армейскую палатку.
Однако, очень часто диапазон параметров, при которых генерируемые хаотическими отображениями числа близки к истинно случайным, как в нашем примере, у хаотических отображений очень мал. Это делает невозможным их безопасное применение в криптосистемах. Кроме того, хаотические генераторы случайных чисел склонны к тому, что называется «вырождение хаоса» – через большое число итераций они внезапно начинают давать периодическую последовательность, и числа перестают быть похожи на случайные. Обе эти проблемы разные научные коллективы пытаются решить, применяя множество дополнительных ухищрений, что сводит на нет всю элегантность идеи применения хаотических отображений.
«Мы подумали, а почему бы не использовать в отображении «тент» вместо обычных функций, таких как y = 2x, фрактальные функции? Идея сработала, и полученное фрактальное отображение «тент» обладает как математической простотой, так и способностью порождать псевдослучайные числа, неотличимые от истинно случайных чисел. Хотя современные компьютеры могут выполнять сложные алгоритмы генерирования псевдослучайных последовательностей без особых проблем, поиск более простых алгоритмов для маломощных встраиваемых систем - актуальная задача», – говорит руководитель проекта, старший научный сотрудник Молодежного НИИ СПбГЭТУ «ЛЭТИ» Копец Екатерина Евгеньевна.
Фрактал – это математическая модель для описания множества, состоящего из самоподобных элементов, а фрактальная функция – это функция, график которой является фракталом. Например, знаменитая русская деревянная игрушка «матрешка» представляет собой набор из вложенных друг в друга самоподобных кукол все меньшего размера. Самые большие матрешки вмещают последовательность из более чем полусотни матрешек, и если бы не физические ограничения, то матрешек было бы бесконечное количество. Именно такой принцип ученые применили для модификации отображения «тент». Если изначально функция напоминала обычную палатку, то теперь это как бы уходящая вдаль бесконечная последовательность все более узких палаток.
«Мы взяли только один из возможных вариантов фрактальной функции, но их можно предложить сколь угодно много. По сути, мы ступаем на terra incognita в области хаотических систем, и перед нами открывается огромное поле для дальнейших исследований», – комментирует один из соавторов, старший научный сотрудник Молодежного НИИ СПбГЭТУ «ЛЭТИ» Каримов Артур Искандарович.
На основе фрактального отображения «тент» был написан генератор случайных чисел. Набор стандартных тестов, принятых в криптографии, показал пригодность предложенного генератора в задачах шифрования, а значит, он подходит и для суррогатного тестирования. С помощью разработанного генератора случайных ученые протестировали биологические сигналы – щелчки кашалота, которые используются для гидролокации. Хотя по звуку можно предположить, что щелчки кашалота напоминают удар барабана, тесты показали их линейность, а значит, с физической точки зрения они ближе к звуку флейты.
Результаты исследования опубликованы в научном журнале Fractal and Fractional. Проект поддержан грантом Российского научного фонда (№23-71-01084).