Американский физик Уильям Гилпин разработал механизм хеширования информации с помощью системы хаотического перемешивания вязкой жидкости на основе попеременного включения двух вихревых мешалок. Запись информации производится с помощью переключения вихрей, а хеш-кодом служат данные о взаимном расположении частиц жидкости в системе, говорится в статье, опубликованной в Proceedings of the National Academy of Sciences.
Ученые и инженеры нередко обсуждают варианты использования гидродинамических устройств для обработки информации, но на практике такие технологии до сих применяются крайне редко. Несмотря на это, микрофлюидных аналогов простых вычислительных систем, способных совершать логические операции с помощью систем каналов, по которым течет жидкость, предлагалось не так мало (1, 2). В таких системах информацию может содержать не только скорость и направление потоков, но и, например, порядок фаз в многофазных вязких жидкостях или координаты движущихся в жидкости микронных частиц — в коллоидных растворах.
Уильям Гилпин (William Gilpin) из Стэнфордского университета предложил использовать гидродинамический подход не просто для записи информации, а в качестве метода ее хеширования. При хешировании происходит преобразование массива данных в битовую строку заданной длины. Для превращения начального сообщения в хеш-код используется известный алгоритм (хеш-функция), зная которую можно установить соответствие между начальной информацией и его кодом. Обычно такое кодирование используется для поиска ошибок и дубликатов в наборах данных, в системах хранения паролей и для разработки электронных подписей.
Гилпин предложил для получения хеш-функции использовать хаотическое перемешивание вязких жидкостей. При таком перемешивании изначально расположенные близко друг у другу частицы покоящейся жидкости можно с помощью заданного алгоритма разнести друг от друга на очень большое расстояние, чувствительность траекторий к начальному расстоянию при этом носит экспоненциальный характер.
С помощью численного моделирования физик изучил возможность использования в качестве системы хаотического перемешивания один из ее простейших вариантов, «мигающий вихрь». Это двумерная система, ограниченная круговыми нескользкими стенками, в которой создаются два вихревых потока, центры которых расположены на одном диаметре на расстоянии в полрадиуса от центра. Включаются источники вихрей попеременно, то есть в каждый момент времени работает только один из них. В такой хаотической системе траектории отдельных частиц жидкости можно найти аналитически без необходимости численного интегрирования.
Двоичные данные в такой системе ученый предлагает представлять как последовательность переключения вихрей: в начальном сообщении 0 соответствует одному включенному вихрю, а 1 — другому. Таким образом, например, сообщение 010101 будет соответствовать шести временным интервалам с чередующимися вихрями. Для хеширования этого сообщения Гилпин выбирал в начальной конфигурации системы несколько частиц жидкости, расположенных вдоль спирали Фибоначчи, нумеровал их и следил за их взаимным расположением относительно горизонтальной оси на каждой из итераций. В качестве хеш-кода ученый предложил использовать финальное расположение этих частиц после всех итераций. То есть, если хеш-код имеет длину 5, то он будет иметь вид, например 34512, в котором цифры соответствуют изначальной нумерации частиц.
Сложность такого кода полностью определяется количеством изначально выбранных частиц N, а количество возможных вариантов при этом задается числом перестановок (то есть N!). По словам ученого, добиться уровня безопасности, аналогичного современным алгоритмам хеширования, можно с использованием примерно 58 частиц, однако в современных экспериментальных реализациях такого хаотического миксера, возможное количество различимых частиц может быть немного меньше, в первую очередь из-за ограничений, связанных с диффузией частиц.
Поскольку двумерная карта перемещений всех частиц жидкости относительно их начального положения полностью определяется параметрами системы (в первую очередь скоростью вращения вихрей), то эту информацию ученый предлагает использовать в качестве открытого ключа для хеширования.
Предложенный принцип ученый проверил на применимость с точки зрения современных требований к хеш-функциям. Важными показателями качества хеш-функции служат степень различия хеш-кодов двух изначально очень близких массивов данных (например отличающихся всего на один символ) и низкая вероятность возникновения «коллизий», при которых двум разным массивам данных соответствует один и тот же хеш-код. Анализ последовательностей различной длины, полученных с помощью предложенной схемы показал, что обоим этим требованиям такой подход удовлетворяет.
По словам исследователя, он не ожидал, что предложенный алгоритм будет работать так хорошо. При этом Гилпину удалось показать, что добиться воспроизводимости работы системы можно даже в современных микрофлюидных системах с учетом возможной диффузии частиц (для этого предлагается использовать очень вязкие жидкости с числом Рейнольдса около 0,001 и размером частиц менее 10 микрометров). Тем не менее, пока для такой системы существует предел для максимальной длины начального сообщения. По словам ученого, полученные им данные можно также использовать, например, для анализа океанских хаотических течений исходя из взаимного расположения буев.
Это далеко не первый пример, когда для разработки алгоритма хеширования используются необычные системы. Например, недавно американские ученые в качестве хеш-функции использовали алгоритм работы обонятельной системы фруктовой дрозофилы, основанного на поиске сходств.
Александр Дубов