ДНК-криптография
ДНК-криптография (англ. DNA cryptography) – область криптографии, использующая молекулярную структуру дезоксирибонуклеиновой кислоты (ДНК) для вычислений и в качестве носителя зашифрованной информации.
ДНК-шифры, как правило, основаны на системе одноразовых блокнотов и являются криптографически устойчивыми. В то время, как большинство традиционных криптографических алгоритмов (RSA, DES, MD5) опираются на математические сложные для решения проблемы факторизации целых чисел или задачи дискретного логарифмирования, ДНК-шифры обеспечивают свою криптографическую устойчивость ещё и биологическими проблемами (например, сложностью полимеразной цепной реакции, гибридизацией ДНК).
Преимуществами ДНК-методов над традиционными также являются высокий параллелизм вычислений и значительная информационная ёмкость цепочек ДНК по сравнению с силиконовыми, оптическими или магнитными носителями информации (один грамм ДНК вмещает до терабайт информации). Тем не менее, для реализации большинства ДНК-криптографических алгоритмов необходима высокотехнологично оборудованная биомолекулярная лаборатория, а процесс шифрования требует больших вычислительных ресурсов и много времени по сравнению с традиционными методами, что не позволяет широко использовать ДНК-шифры в настоящее время.
Описание
ДНК-криптография является новым направлением в области защиты информации. Современные достижения в области молекулярной биологии и факт взлома популярных традиционных шифров (DES, MD5) обусловили потребность в поиске новых методов защиты данных, объединяющих биологические и криптографические методы для создания новых шифров.
Многие ДНК-криптографические методы основаны на сложности задачи гибридизации ДНК и схеме одноразовых блокнотов[1]. Рассмотрим подробнее данный метод шифрования:
Шифрование на основе двоичной индексации
Допустим, пользователь Алиса хочет отправить сообщение Μ пользователю по имени Боб. Для пересылки, требуется сгенерировать закрытый (приватный) ключ шифрования. Размер ключа зависит от длины открытого текста в битах. Открытый текст M переводится в ASCII-код, который затем конвертируется в двоичную запись M'. В качестве закрытого ключа шифрования K генерируется случайная последовательность одноцепочечной ДНК, де-факто являющаяся символьным блоком с символами из четырёх (A, T, C, G) ДНК-нуклеотидов. Длина ключа равняется количеству двоичных символов в M'. Ключ является секретным и пересылается между участниками переписки по защищённым каналам до начала беседы.
На этапе шифрования Алиса для каждого символа "1" из M' выбирает 10-нуклеотидную одноцепочечную ДНК из ключа K случайным образом и вычисляет Ватсон-комплиментарную последовательность этой цепочки (аналогично XOR-операции, но на биологическом уровне). Далее данной вычисленной последовательности длиной 10 символов (ДНК-нуклеотид) приписывается в конец число - индекс положения символа "1" в исходном сообщении M'. Таким образом, шифрованию подлежат только символы "1" исходного сообщения с запоминанием позиции этих символов в исходном сообщении, что позволяет значительно сэкономить временные и вычислительные ресурсы (не нужно заниматься шифрованием "нулей" битовой последовательности открытого текста). Символьные блоки длиной 10+N символов – последовательности 10 ДНК-нуклеотидов и N - количество символов в индексе символьного блока – образуют зашифрованное сообщение (шифротекст) С передаются по открытому каналу (биологический носитель, цифровой канал).
Для дешифрования Боб будет также использовать метод ДНК-гибридизации. Получив ключ К по защищённому соединению и пакет (часть шифротекста C) открытым способом, Боб смотрит на индекс пакета, записанный в его конце. Затем Боб начинает производить гибридизацию пакета с ключом – нужно расположить этот пакет под ключом в такой позиции, чтобы после трансляции получить "единицу" в нужном месте открытого сообщения. Боб пытается сдвигами производить спаривание пакета с ключом, начиная с позиции (индекс пакета * 10). Как только сдвиг оказывается достаточным, пакет оказывается Ватсон-комплиментарным части ключа К, Боб запоминает позицию и ставит единицу в этой позиции в открытом сообщении. Таким образом происходит расшифровка всего сообщения.
Шифр подстановкой
Другой подход в ДНК-криптографии, основанной на гибридизации ДНК использует для кодирования таблицу ДНК-нуклеотидов для каждого символа[2]. Так каждому символу исходного английского алфавита сопоставляется символьный блок из трёх ДНК-нуклеотидов. Результатом в ходе применения шифра подстановки является строка, содержащая символы алфавита ДНК (A, C, G, T). Для получения зашифрованного сообщения данная строка проходит XOR-подобную операцию с ключом шифрования.
При расшифровке зашифрованного сообщения, необходимо иметь ключ и специальный алфавит для дешифрования. Замена алфавита является открытым процессом, здесь алфавит (таблицу) можно интерпретировать, как открытый ключ. Секретный ключ же хранится в тайне и вручаются только адресату.
История
В 1994 г. Леонард Адльман из Университета Южной Калифорнии опубликовал статью, в которой впервые была описана идея использования биомолекулярных методов для решения задач, требовавших огромного количества вычислений и невозможных к решению на обычных компьютерах[3]. ДНК была впервые применена для выполнения компьютерных вычислений на молекулярном уровне.
В 1995 г. Ричард Лифтон из Университета Принcтона применил описанный подход для решения NP-полной задачи. В 1997 г. учёные Митсунори Огихара и Анимеш Рей предложили использовать данный метод для оценивания булевых цепей и описали принцип работы такой системы.
В 2002 г, исследователи из Научного институтa Вейцмана в Реховоте представили программируемую вычислительную систему, использующую энзимы и молекулы ДНК вместо силиконовых микрочипов. 28 апреля 2004 г. учёные (Ехуд Шапиро, Яков Бененсон и др.) объявили о создании ДНК компьютера с функциями ввода-вывода, теоретически способного помочь в диагнозе рака клеток и созданию лекарства против рака на этапе исследования.
В январе 2013 г.исследователям удалось сохранить изображение формата JPEG, коллекцию сонет Шекспира и аудиофайл с речью Мартина Лютера Кинга Младшего "У меня есть мечта" на цифровой ДНК-носитель. В Марте 2013 г. создан транскриптор (биологический аналог транзистора).
В августе 2016 г. система редактирования генов CRISPR была использована для сохранения GIF-изображения в ДНК живой бактерии.
Исследования в области ДНК-криптографии на данный момент находятся в начальном, зарождающемся состоянии и на данный момент предстоит решить ещё много проблем. Само понятие ДНК-криптографии берёт начало из проекта по информатике Вивиана Риска по ДНК-стеганографии, завоевавшего Юношескую Нобелевскую Премию в 2000 г [4]. Хотя многие исследователи работают в области ДНК-криптографии уже сейчас, единая теория и практическая реализация пока что трудно реализуемы.
На данный момент научные труды в области ДНК-криптография в основном опираются на использовании сложных биологических технологий и методик, таких как цепная реакция полимераза, ДНК-гибридизация, ДНК-синтез, ДНК-кодирование.
Достоинства и недостатки
ДНК-шифры работают по принципу одноразовых блокнотов и являются криптографически устойчивыми. Избирательное объединение четырёх нуклеотидных баз (A-T, G-C) образует большое поле возможностей для создания различных XOR-операций и позволяют создавать биологические структуры, отлично подходящие для выполнения вычислений. ДНК имеет большую информационную плотность – один грамм ДНК вмещает до терабайт информации, что превосходит ёмкости современных силиконовых, оптических и магнитных информационных носителей. Некоторые шифры допускают реализацию с применением методов параллельных вычислений, что значительно ускоряет процесс шифрования и делает его сравнимым по времени с традиционными криптографическими шифрами. В отличие от традиционных методов, взлом шифра требует решения как математических, так и биологических вычислительно сложных задач, а сам процесс требует наличие высокотехнологичного биомолекулярного оборудования. Тем не менее, у ДНК-шифров существуют и недостатки по сравнению с другими методами защиты данных. Практическая реализация ДНК-криптографии требует больше вычислительных ресурсов и значительно больше времени, чем для традиционных шифров. Также физическая реализация шифров подразумевает наличие высокотехнологичной биомолекулярной лаборатории, доступной каждому из участников "беседы". Также на данный момент нет единой теории по ДНК-криптографии, а практические реализации не доведены до промышленного уровня удобства использования.
- ↑ S. Pramanik, S. K. Setua. DNA cryptography // 2012 7th International Conference on Electrical and Computer Engineering. — 2012-12. — С. 551—554. — doi:10.1109/ICECE.2012.6471609.
- ↑ Er Ranu Soni. Innovative field of cryptography: DNA cryptography. — 2012-01-04. — Т. 2. — С. 161—179. — ISBN 9781921987021. — doi:10.5121/csit.2012.2115.
- ↑ L. M. Adleman. Molecular computation of solutions to combinatorial problems (англ.) // Science. — 1994-11-11. — Vol. 266, iss. 5187. — P. 1021—1024. — ISSN 1095-9203 0036-8075, 1095-9203. — doi:10.1126/science.7973651.
- ↑ Catherine Taylor Clelland, Viviana Risca, Carter Bancroft. Hiding messages in DNA microdots (англ.) // Nature. — 1999-07-01. — Vol. 399. — P. 533—534. — doi:10.1038/21092.