Криптосистема, построенная с использованием ДНК-криптографии и автомата Мили

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

Одним из перспективных направлений в современной криптографии является ДНК-криптография. Обычно под ДНК-криптографией подразумевают либо непосредственное использование цепочек ДНК для представления и передачи информации, для чего необходимо высокотехнологичное оборудование, либо использование в процессе шифрования алфавита из ДНК-нуклеотидов (A, T, C, G).

Актуальность криптосистем, в том или ином виде включающих в себя цепочки ДНК, также связана с активными исследованиями в области запоминающих устройств, использующих ДНК. Подобные устройства смогут хранить объем информации на несколько порядков больший (при более компактных размерах), чем позволяют современные технологии. Кроме того, срок службы подобных устройств хранения данных заметно выше.

В данной статье рассматривается криптографическая система [1], использующая ДНК-криптографию и автомат Мили.

Кратко про ДНК и автомат Мили

ДНК (Дезоксирибонуклеиновая кислота) — это макромолекула, состоящая из последовательности нуклеотидов. Нуклеотид определяется входящей в него базой (азотистым основанием), которых в ДНК может быть четыре вида: аденин (A), цитозин (С), гуанин (G) и тимин (T). Таким образом, в ДНК-криптографии для хранения данных можно использовать алфавит {A, T, C, G} вместо привычных 0 и 1, а само сообщение представляется в виде некоторой цепочки ДНК.

Автомат Мили — это конечный автомат, у которого элементы выходной последовательности зависят от текущего состояния автомата и текущего элемента входной последовательности. Автомат Мили задается совокупностью функций и множеств M = {S, X, Y, δ, λ}:

• S — множество состояний автомата: {1, 2, 3, 4};

• X — множество элементов входной последовательности: {A, T, C, G};

• Y — множество элементов выходной последовательности: {A, T, C, G};

• δ — функция переходов, которая отображает пару (состояние, вход) на следующее состояние;

• λ — функция выходов, которая отображает пару (состояние, вход) на элемент выходной последовательности.

Структура автомата Мили может быть полностью задана двумя таблицами: таблицей переходов (реализует функцию δ) и таблицей выходов (реализует функцию λ). В рассматриваемой схеме для каждой передачи случайным образом создается новый автомат Мили, который используется для преобразования одной цепочки ДНК в другую. Примеры указанных таблиц для рассматриваемой криптосистемы приведены ниже.

Рассматриваемая криптосистема

В криптосистеме взаимодействуют три объекта: генератор пары ключей (ГПК), отправитель (далее - Алиса) и получатель (далее - Боб). Рабочий цикл состоит из нескольких этапов и представлен на схеме. Разберем подробнее каждый из этапов.

1. Регистрация на сервере. Алиса и Боб запрашивают у ГПК пару ключей. ГПК создает две пары ключей и отсылает их, при этом открытый ключ Алисы отправляется Бобу и наоборот (этапы 1–4);

2. Установление сеанса. Боб посылает Алисе запрос на установление сеанса вместе с некоторой информацией: персональным номером (PN), email ID и MAC-адресом (этап 5). Алиса проверят подлинность отправителя при помощи запроса к серверу (этапы 6–7) и подтверждает установление сеанса (этап 8). После этого Боб может запрашивать данные (этап 9);

3. Генерация ключа. Алиса расшифровывает данные (PN, email ID, MAC), полученные от Боба, используя свой закрытый ключ и открытый ключ Боба, и на их основе генерирует сеансовый ключ: сначала происходит конкатенация полученных данных в одну строку, затем каждый символ заменяется своим значением из таблицы ASCII в двоичном 8-битном представлении (например, "0" → 48₁₀→ 00110000₂ ). Если полученная двоичная строка имеет длину менее 256 символов, то она дополняется нулями, в противном случае - отбрасываются последние биты;

4. Генерация автомата Мили. Алиса случайным образом генерирует таблицу переходов и таблицу выходов. Значения из таблиц записываются подряд в строчку, при этом символы {A, T, C, G} заменяются на {0, 1, 2, 3} соответственно. Каждое из 32 чисел (по 16 чисел из каждой таблицы) в строке заменяется на свое 8-битное двоичное представление согласно некоторой таблице перевода. Данная таблица формируется случайным образом так, чтобы двоичное представление чисел содержало одинаковое количество нулей и единиц, см.пример ниже. В результате описанных манипуляций получается 256- битное число. Затем каждые два бита снова преобразуются в сим- волы {A, T, C, G} согласно случайно выбранной строке (ее номер обозначим за R1) из таблицы кодировок для ДНК-базисов . Полу- ченная последовательность (назовем ее DNAMM, DNA Mealy machine) и число R1 далее будут переданы Бобу, чтобы он смог расшифровать сообщение.

5. Шифрование данных. Алиса переводит каждый символ своего сообщения в 8-битное двоичное представление согласно обычной ASCII таблице. Полученная двоичная строка разбивается на блоки по 256 бит. Затем, производится операция XOR (исключающее ИЛИ) между сеансовым ключом из пункта 3 и каждым блоком. После этого каждые два бита полученной строки преобразуются в символы {A, T, C, G} согласно случайно выбранной строке (ее номер обозначим за R2) из уже знакомой таблицы кодировок для ДНК-базисов. Полученную цепочку (назовем ее dnaD1) Алиса подает на вход автомата Мили, и на выходе получается новая цепочка dnaD2. Итоговый шифротекст получается записыванием в обратном порядке цепочки dnaD2. Например, если открытый текст содержит 100 символов, то после шифрования получится цепочка длины 400 с элементами из алфавита {A, T, C, G}.

6. Отправка данных. Алиса отправляет Бобу шифротекст, DNAMM, таблицу перевода символов {0, 1, 2, 3} в бинарный код и параметры R1 и R2, используя свой закрытый ключ и открытый ключ Боба (этап 10).

7. Расшифровка данных. Боб, используя свой закрытый ключ и открытый ключ Алисы, восстанавливает шифротекст, DNAMM, таблицу перевода и параметры R1 и R2. Сначала Боб переписывает шифротекст в обратной порядке, получая цепочку dnaD2. Затем, выполняя пункт 4 в обратном порядке, Боб восстанавливает структуру автомата Мили. Применяя правила из таблицы переходов в обратном порядке к цепочке dnaD2, Боб восстанавливает цепочку dnaD1. Далее, выполняя пункт 5 в обратном порядке, Боб восстанавливает исходное сообщение Алисы.

Анализ безопасности

Перейдем к рассмотрению устойчивости описанной системы к различным атакам.

1. Атака полным перебором. Поскольку при шифровании используется 256-битный сеансовый ключ, то для его подбора необходимо перебрать 2²⁵⁶ вариантов, что вычислительно невозможно;

2. Атаки на основе открытых текстов и шифротекстов, дифференциальный криптоанализ. В данных видах криптоанализа злоумышленник пытается по известным парам (открытый текст, шифротекст) угадать биты секретного ключа или расшифровать последующие сообщения. В рассматриваемой криптосистеме для шифрования сообщений используется сеансовый ключ, и для каждой передачи генерируется новый автомат Мили, за счет чего два похожих открытых текста преобразуются в два совершенно разных шифротекста, и наоборот — два похожих шифротекста при расшифровке преобразуются в совершенно разные открытые тексты. То есть криптосистема устойчива к подобным атакам.

3. Атака типа man-in-the-middle. В рассматриваемой криптосистеме все передачи между Алисой и Бобом шифруются с использованием открытых и закрытых ключей, за генерацию и рассылку которых отвечает ГПК. То есть считается, что третьи лица не имеют доступа к ключам, поэтому чтение или незаметное изменение каких-либо сообщений в канале между Алисой и Бобом невозможно.

4. Фишинг. В данном типе атак злоумышленник пытается получить персональную информацию получателя, которая далее может быть использована для чтения данных от отправителя. В рассматриваемой схеме Алиса и Боб должны предварительно пройти регистрацию на сервере (ГПК), и далее перед отправлением данных Алиса сначала проверяет подлинность полученных от Боба сведений при помощи сервера, поэтому несанкционированное получение персональной информации невозможно.

Также в работе [1] проводится анализ различных характеристик (время шифрования/расшифрования, время генерации сеансового ключа и т.д.) предложенной криптосистемы и сравнение их с характеристиками аналогичных схем, использующих ДНК-криптографию. Из наиболее интересных результатов стоит отметить следующие: частоту символов ДНК- базиса в шифротексте, когда открытый текст представляет из себя 100 одинаковых элементов ДНК-базиса и лавинный эффект. Из гистограмм видно, что все символы ДНК-базиса имеют примерно одинаковую частоту. Если теперь заменить один бит сеансового ключа, то наблюдается лавинный эффект, см. таблицу ниже.

Заключение

В данной статье была рассмотрена криптосистема, в которой при шифровании используются элементы ДНК-криптографии и автомат Мили. Также приведен анализ данной криптосистемы на устойчивость к различным криптоатакам.

С практической точки зрения рассмотренная схема является дополнением к классической асимметричной криптосистеме с выделенным объектом, осуществляющим управление ключами. Таким образом, описанная криптосистема может быть использована для повышения безопасности асимметричных криптосистем.

Список источников

1. Pavithran, Pramod, et al. "A novel cryptosystem based on DNA cryptography and randomly generated Mealy machine." Computers & Security 104 (2021): 102160.

2. Hopcroft, John E., Rajeev Motwani, and Jeffrey D. Ullman. "Introduction to automata theory, languages, and computation." Acm Sigact News 32.1 (2001): 60-65.

3. https://ru.wikipedia.org/?curid=10889&oldid=117159287

4. https://ru.wikipedia.org/?curid=7709336&oldid=106283042

5. https://ru.wikipedia.org/?curid=355613&oldid=116680835

6. https://ru.wikipedia.org/?curid=30212&oldid=117810591