Было время, среди ученых ходила мода ругать природу за неоптимальные решения и массу применяемых «костылей». Один физик XIX века даже вошел историю с высказыванием в том духе, что господь бог – плохой оптик, и за конструкцию человеческого глаза он и гроша бы ему (богу) не дал. Потом его именем даже институт в Москве назвали, но уже не за это.
Так вот, он был неправ (хотя без слепого пятна можно было бы и обойтись). Сейчас наука то и дело подсматривает у живых организмов отдельные принципы и приемы. Да, они не всегда энергетически эффективны, часто область их применения узка, зато проверены миллионами лет выживания. И вот что интересно – даже в такой безжизненной области, как криптография, находится применение тому, что придумала когда-то жизнь. Конечно, животные не шифруют передаваемую информацию, так что напрямую тут ничего не украсть. We need to go deeper, как выразился известный оскароносец.
Поговаривают, что появление полноценных квантовых компьютеров все ближе, ближе и конец шифрования в том виде, в котором мы его знаем и любим. Разведслужбы в предвкушении потирают руки, криптографы мечутся в поисках криптографической «серебряной пули», а журналисты чуть ли не каждую неделю выпускают сенсации о том, что кто-то уже создал квантовый компьютер и все наши маленькие секреты уже не секреты.
Все это напоминает истерию вокруг «ошибки 2000-го года», под которую были выделены и освоены приличные деньги по всему миру, разве что, шума поменьше, ибо не всякий обыватель осознает важность конфиденциальности данных, а вот то, что ровно в полночь 2000 года будто бы вырубятся бортовые компьютеры авиалайнеров, кого угодно напугает.
Тем не менее, польза есть и от квантового хайпа. Пока визионеры балуются квантовым отжигом и пытаются найти задачи, для решения которых это имеет смысл, криптографы разрабатывают новые стойкие алгоритмы шифрования. Их пытливый взор обратился к квазибиологическим вычислительным методам. На самом деле тема не новая, и разрабатывается не один десяток лет, но обещает стать очень актуальной, если получит должное развитие.
Любая биологическая система решает какие-то свои задачи, будь то поиск пищи, приспособление к изменяющимся условиям внешней среды, противодействие агрессии и так далее. Это можно представить в виде вычислительной модели – относительно грубой, в силу того, что человечество изучило жизнь не слишком глубоко. И есть ряд задач, в том числе криптографических и криптоаналитических, для решения которых эти модели оказываются чрезвычайно эффективны. Да-да, речь о нейронных сетях, я уверен, все их узнали. Но не только о них.
Нейронные сети
Если сформулировать кратко, искусственная нейронная сеть – очень-очень грубая и в корне неверная модель . Состоит из множества взаимосвязанных нейронов, каждый может получать несколько сигналов от других нейронов и передавать один выходной сигнал. Каждая межнейронная связь имеет свой вес, который может изменяться в процессе обучения сети. Видов нейросетей, начиная с перцептрона 1957 года, придумано множество, различаются они передаточной функцией нейрона, топологией соединений нейронов и способами обучения – определения весов связей.
В криптографии нейронные сети можно применить для обмена ключами, а это чуть ли не самый важный этап конфиденциальной передачи информации. Протокол Диффи-Хеллмана основан на теории чисел, и его стойкости хватит лишь до тех пор, пока у атакующего не обнаружится квантовый компьютер. А вот нейронный алгоритм работает иначе. В его основе лежат многоуровневые перцептроны, находящиеся на двух концах незащищенного канала связи.
Закрытый ключ каждой стороны представлен в виде начальных весов связей перцептрона.
Инициатор отправляет своему визави начальный поток данных, и этот поток подается на входы перцептронов обоих сторон. Данные с выходов перцептронов стороны отправляют друг другу, затем сравнивают полученные потоки и модифицируют веса связей, далее процедура повторяется. Таким образом перцептроны обучают друг друга (синхронизируются), а после достижения полной синхронизации веса связей обоих перцептронов становятся одинаковы – сеансовый ключ сгенерирован. Этот ключ есть у обеих сторон, но при этом он нигде и ни в каком виде не передавался.
Если в такой схеме применить простой одноуровневый перцептрон, как на картинке, то третья сторона сможет рассчитать начальные веса из начального потока данных и выходного потока нейросети. Поэтому применяются многоуровневые перцептроны со скрытыми слоями – в этом случае никто извне не может вычислить, какие именно веса модифицированы в каждой итерации. На картинке ниже приведен пример нейросети с множеством входов, одним скрытым слоем, и одним выходом – так называемая древовидная машина четности.
При стохастическом обучении веса изменяются псевдослучайно, а затем отбрасываются те изменения, что ухудшают результат – то есть даже с одними и теми же закрытыми ключами и одним и тем же начальным потоком (рандомным или не рандомным), сеансовый ключ будет каждый раз разным. Атака на такой протокол чрезвычайно сложна: третья сторона, прослушивающая канал, не сможет полностью синхронизироваться, не зная закрытого ключа одной из сторон. А этот ключ можно сделать очень длинным без значительного падения производительности перцептрона. И все же стойкость нейронного алгоритма обмена ключами пока обсуждается, не исключено, что еще будут разработаны эффективные на практике атаки на него.
Перцептроны можно использовать не только для генерации ключа – в синхронизированном виде они вполне пригодны и для шифрования-дешифрования данных. Есть, правда, нюанс: нейросети склонны вносить искажения в обрабатываемые данные, то есть поверх потребуется нахлобучить протокол коррекции ошибок. AES и другие традиционные симметричные алгоритмы этого недостатка лишены.
Генетические алгоритмы
Эти алгоритмы также неплохо изучены. Они построены на принципах эволюции, постулируемых неодарвинизмом. Берем множество начальных значений (особь), собираем из множества разных особей популяцию, при помощи фитнес-функции отсекаем худших особе, создаем из лучших особей потомство путем рекомбинации значений с добавлением мутаций (случайных коррекций значений), и так по кругу. Фитнес-функция играет роль агрессивной внешней среды, ее значение определяет близость особи к желаемому решению. Через какое-то количество итераций у нас будет особь, достаточно близкая к решению задачи. Все, как в жизни.
Что же касается применения в криптографии, то ГА полезны в разработке примитивов – булевых функций и S-блоков. Это важнейшие элементы блочных и поточных шифров, без них шифр может быть взломан с помощью статистического анализа при сравнении открытого текста и шифротекста. Причем если их создавать рандомно, то они будут неоптимальны и могут ослаблять алгоритм против определенных методов криптоанализа. Поэтому разработчики шифров конструируют примитивы вручную, и в этом процессе есть что-то весьма адское для самих разработчиков.
Вот тут-то генетические алгоритмы очень в тему, так как фактически это задача поиска экстремумов по нескольким критериям: сбалансированность, высокая нелинейность, низкая автокорреляция, высокая алгебраическая степень. За N M попыток скрещивания ежа с ужом и проверок потомков на гибкость и колючесть получается функция, хорошо удовлетворяющая всем критериям. Естественно, все зависит от фитнес-функции, которая определяет, насколько нам важен каждый критерий.
Помимо этого, есть у криптографов идеи использования генетических алгоритмов непосредственно для симметричного шифрования без применения булевой функции. Суть в итеративном шифровании каждого блока данных с разными изначальными псевдослучайными последовательностями. Блоки в итоге эволюционируют до полного отсутствия статистической корреляции шифротекста с исходным текстом. При этом процесс шифрования замедляется пропорционально числу итераций (поколений).
Искусственные иммунные системы
Относительно новая область, основанная на известных механизмах работы иммунной системы живых организмов. В общем виде это система элементов, которые должны соответствовать цели (опознавать антигены), не ухудшать результат (не атаковать клетки собственного организма).
Есть несколько алгоритмов, похожих, кстати, на генетические. Так, в алгоритме клональной селекции отбираются те клетки, которые лучше всего реагируют на антигены, при этом вместо создания потомства, как в ГА, удачные клетки клонируются с добавлением мутаций. Чем клетка лучше, тем больше ее копий производится, и тем меньше мутаций вносится. Дальше популяция клеток снова проверяется на реакцию на антиген (на соответствие фитнес-функции), снова отбираются лучшие и т.д.
В алгоритме иммунной сети принцип несколько другой. Клетки образуют сеть, при этом каждая клетка, реагирующая как на антиген, так и на соседние клетки, стимулируется (то есть клонируется и мутирует), а клетка, на которую реагируют соседние клетки – подавляется. В отсутствие антигенов сеть избавляется от наихудших клеток и стабилизируется, а в присутствии антигена лучшие клетки начинают множиться, уничтожая менее качественных соседей.
Искусственные иммунные сети чаще всего используются примерно так же, как и естественные, то есть для обнаружения вредоносного вторжения в систему. Что же касается применения в криптографии, то иммунные алгоритмы имеют потенциал в тех же областях, где и нейронные сети и генетические алгоритмы, так как родственны им.
Disclaimer: Данная колонка отражает лишь частное мнение ее автора. Оно может совпадать с позицией компании «Лаборатория Касперского», а может и не совпадать. Тут уж как повезет.
Автор: «Лаборатория Касперского»
