Нейронная криптография

Нейронная криптография — это раздел криптографии, посвященный анализу применения стохастических алгоритмов, особенно алгоритмов искусственных нейронных сетей , для использования в шифровании и криптоанализе .

Определение

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

Идеи взаимного обучения, самообучения и стохастического поведения нейронных сетей и подобных алгоритмов могут быть использованы для различных аспектов криптографии, таких как криптография с открытым ключом , решение проблемы распределения ключей с использованием взаимной синхронизации нейронных сетей, хеширования или генерации псевдо- случайные числа .

Другая идея — способность нейронной сети разделять пространство на нелинейные части с помощью «смещения». Это дает разные вероятности активации нейронной сети или нет. Это очень полезно в случае криптоанализа.

Для обозначения одной и той же области исследований используются два названия: нейрокриптография и нейронная криптография.

Первую известную работу по этой теме можно отнести к 1995 году, когда была написана магистерская диссертация по информационным технологиям.

Приложения

В 1995 году Себастьен Дурленс применил нейронные сети для криптоанализа DES , позволив сетям научиться инвертировать S-таблицы DES. предвзятость в DES, изученная Ади Шамиром Подчеркивается с помощью дифференциального криптоанализа. Эксперимент показывает, что можно найти около 50% битов ключа, что позволяет найти полный ключ за короткое время. Аппаратное применение с несколькими микроконтроллерами было предложено из-за простой реализации многослойных нейронных сетей в аппаратном обеспечении.

Один из примеров протокола с открытым ключом приведен Халилом Шихабом. Он описывает схему дешифрования и создание открытого ключа, основанные на нейронной сети обратного распространения ошибки . Схема шифрования и процесс создания закрытого ключа основаны на булевой алгебре. Преимущество этого метода заключается в небольших сложностях по времени и памяти. Недостатком является свойство алгоритмов обратного распространения ошибки: из-за огромных обучающих выборок фаза обучения нейронной сети очень длительная. Поэтому использование этого протокола пока носит лишь теоретический характер.

Протокол обмена нейронными ключами

Наиболее используемым протоколом обмена ключами между двумя сторонами A и B на практике является протокол обмена ключами Диффи-Хеллмана . Нейронный обмен ключами, основанный на синхронизации двух машин проверки четности дерева, должен стать безопасной заменой этому методу. Синхронизация этих двух машин аналогична синхронизации двух хаотических осцилляторов в хаотических коммуникациях .

Машина проверки четности деревьев

Машина проверки четности деревьев

Машина проверки четности дерева — это особый тип многослойной нейронной сети прямого распространения .

Он состоит из одного выходного нейрона, K скрытых нейронов и K × N входных нейронов. Входные данные в сеть принимают три значения:

$x_{ij}\in \left\{-1,0,+1\right\}$

Веса между входными и скрытыми нейронами принимают значения:

$w_{ij}\in \left\{-L,...,0,...,+L\right\}$

Выходное значение каждого скрытого нейрона рассчитывается как сумма всех произведений входных нейронов и этих весов:

$\sigma _{i}=\operatorname {sgn}(\sum _{j=1}^{N}w_{ij}x_{ij})$

Signum — простая функция, возвращающая −1,0 или 1:

$\operatorname {sgn}(x)={\begin{cases}-1&{\text{if }}x<0,\\0&{\text{if }}x=0,\\1&{\text{if }}x>0.\end{cases}}$

Если скалярное произведение равно 0, выход скрытого нейрона отображается в -1, чтобы обеспечить двоичное выходное значение. Выходные данные нейронной сети затем вычисляются как умножение всех значений, создаваемых скрытыми элементами:

$\tau =\prod _{i=1}^{K}\sigma _{i}$

Выход машины проверки четности дерева является двоичным.

Протокол

Каждая сторона ( A и B ) использует свою собственную машину проверки четности дерева. Синхронизация машин проверки четности дерева достигается на этих этапах.

1. Инициализировать случайные значения веса
2. Выполняйте эти шаги до тех пор, пока не будет достигнута полная синхронизация.
   1. Сгенерируйте случайный входной вектор X
   2. Вычислить значения скрытых нейронов
   3. Вычислите значение выходного нейрона
   4. Сравните значения обеих машин проверки четности дерева.
      1. Выходные данные те же: к весам применяется одно из подходящих правил обучения.
      2. Выходы разные: перейдите к 2.1.

После достижения полной синхронизации (веса w _ij обеих машин проверки четности дерева одинаковы) A и B могут использовать свои веса в качестве ключей.
Этот метод известен как двунаправленное обучение.
Одно из следующих правил обучения можно использовать для синхронизации:

• Правило обучения Хеббиана:

$w_{i}^{+}=g(w_{i}+\sigma _{i}x_{i}\Theta (\sigma _{i}\tau )\Theta (\tau ^{A}\tau ^{B}))$

• Антихеббианское правило обучения:

$w_{i}^{+}=g(w_{i}-\sigma _{i}x_{i}\Theta (\sigma _{i}\tau )\Theta (\tau ^{A}\tau ^{B}))$

• Случайное блуждание:

$w_{i}^{+}=g(w_{i}+x_{i}\Theta (\sigma _{i}\tau )\Theta (\tau ^{A}\tau ^{B}))$

Где:

$\Theta (a,b)=0$ если $a\neq b$ в противном случае $\Theta (a,b)=1$

И:

$g(x)$ это функция , которая сохраняет $w_{i}$ в диапазоне $\{-L,-L+1,...,0,...,L-1,L\}$

Атаки и безопасность этого протокола

При каждой атаке считается, что злоумышленник Е может подслушивать сообщения между сторонами А и Б , но не имеет возможности изменить их.

Грубая сила

Чтобы осуществить атаку методом перебора, злоумышленник должен проверить все возможные ключи (все возможные значения весов wij). С помощью K скрытых нейронов, K × N входных нейронов и границы весов L это дает (2L+1) ^КН возможности. Например, конфигурация K = 3, L = 3 и N = 100 дает нам 3*10. ²⁵³ ключевые возможности, делающие атаку невозможной при нынешних компьютерных возможностях.

Обучение с помощью собственной машины проверки четности деревьев

Одну из базовых атак может осуществить злоумышленник, владеющий той же машиной проверки четности дерева, что и A и B. стороны Он хочет синхронизировать свою машину проверки четности деревьев с этими двумя сторонами. На каждом этапе возможны три ситуации:

1. Выход(A) ≠ Выход(B): Ни одна из сторон не обновляет свои веса.
2. Выход(A) = Выход(B) = Выход(E): все три стороны обновляют веса в своих машинах проверки четности дерева.
3. Выход(A) = Выход(B) ≠ Выход(E): стороны A и B обновляют свои машины проверки четности дерева, но злоумышленник не может этого сделать. чем синхронизация сторон А и Б. Из-за этой ситуации его обучение происходит медленнее ,

Доказано, что синхронизация двух сторон происходит быстрее, чем изучение злоумышленника. Его можно улучшить за счет увеличения синаптической глубины L нейронной сети. Это обеспечивает этому протоколу достаточную безопасность, и злоумышленник может узнать ключ лишь с небольшой вероятностью.

Другие атаки

Для традиционных криптографических систем мы можем повысить безопасность протокола, увеличив длину ключа. В случае нейронной криптографии мы улучшаем ее за счет увеличения синаптической глубины L нейронных сетей. Изменение этого параметра увеличивает стоимость успешной атаки в геометрической прогрессии, в то время как усилия пользователей растут полиномиально. Следовательно, взлом безопасности нейронного обмена ключами относится к классу сложности NP.

Александр Климов, Антон Митягин и Ади Шамир говорят, что исходную схему нейронной синхронизации можно взломать как минимум тремя различными атаками — геометрическим, вероятностным анализом и использованием генетических алгоритмов. Несмотря на то, что эта конкретная реализация небезопасна, идеи, лежащие в основе хаотической синхронизации, потенциально могут привести к безопасной реализации.

Машина перестановочной четности

Машина проверки четности перестановок представляет собой двоичный вариант машины проверки четности дерева.

Он состоит из одного входного слоя, одного скрытого слоя и одного выходного слоя. Количество нейронов в выходном слое зависит от количества скрытых единиц K. Каждый скрытый нейрон имеет N двоичных входных нейронов:

$x_{ij}\in \left\{0,1\right\}$

Веса между входными и скрытыми нейронами также являются двоичными:

$w_{ij}\in \left\{0,1\right\}$

Выходное значение каждого скрытого нейрона рассчитывается как сумма всех исключающих дизъюнкций (исключающих или) входных нейронов и этих весов:

$\sigma _{i}=\theta _{N}(\sum _{j=1}^{N}w_{ij}\oplus x_{ij})$

(⊕ означает исключающее ИЛИ).

Функция $\theta _{N}(x)$ — пороговая функция, которая возвращает 0 или 1:

$\theta _{N}(x)={\begin{cases}0&{\text{if }}x\leq N/2,\\1&{\text{if }}x>N/2.\end{cases}}$

Выходные данные нейронной сети с двумя или более скрытыми нейронами могут быть вычислены как исключительные значения, созданные скрытыми элементами:

$\tau =\bigoplus _{i=1}^{K}\sigma _{i}$

Возможны и другие конфигурации выходного слоя для K>2.

Эта машина оказалась достаточно устойчивой к некоторым атакам. поэтому его можно использовать в качестве криптографического средства, но было показано, что он уязвим для вероятностной атаки.

Защита от квантовых компьютеров

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

Протокол обмена нейронными ключами не основан на какой-либо теории чисел. Он основан на различии между однонаправленной и двунаправленной синхронизацией нейронных сетей. Следовательно, что-то вроде нейронного протокола обмена ключами может привести к созданию потенциально более быстрых схем обмена ключами.

См. также

• Нейронная сеть
• Стохастическая нейронная сеть
• Алгоритм Шора

Ссылки

• Нейрокриптография 1995 г. — первое определение нейрокриптографии (нейронная криптография AI), примененное к криптоанализу DES, Себастьяном Дурленсом, Франция.
• Нейронная криптография — описание одного из видов нейронной криптографии в Вюрцбургском университете , Германия.
• Кинзель, В.; Кантер, И. (2002). «Нейронная криптография». Материалы 9-й Международной конференции по нейронной обработке информации . ИКОНИП '02. стр. 1351–1354. arXiv : cond-mat/0208453 . дои : 10.1109/ICONIP.2002.1202841 . - Одна из ведущих работ, в которой представлена ​​концепция использования синхронизированных нейронных сетей для создания системы аутентификации с открытым ключом.
• Ли, Ли-Хуа; Линь, Луон-Чанг; Хван, Минь-Шян (ноябрь 2001 г.). «Схема удаленной аутентификации по паролю для многосерверной архитектуры с использованием нейронных сетей». Транзакции IEEE в нейронных сетях . 12 (6): 1498–1504. дои : 10.1109/72.963786 . ISSN   1045-9227 . ПМИД   18249979 . - Возможное практическое применение нейронной криптографии.
• Климов, Александр; Митягин Антон; Шамир, Ади (2002). «Анализ нейронной криптографии» (PDF) . Достижения криптологии . АЗИАКРИПТ 2002. LNCS . Том. 2501. С. 288–298. дои : 10.1007/3-540-36178-2_18 . ISSN   0302-9743 . Проверено 15 ноября 2017 г. - Анализ нейронной криптографии в целом и сосредоточение внимания на слабостях и возможных атаках с использованием синхронизированных нейронных сетей.
• Нейронная синхронизация и криптография - Андреас Руттор. Кандидатская диссертация, Баварский университет Юлиуса Максимилиана, Вюрцбург, 2006 г.
• Руттор, Андреас; Кинзель, Вольфганг; Нее, Ривка; Кантер, Идо (март 2006 г.). «Генетическая атака на нейронную криптографию». Физический обзор E . 73 (3): 036121. arXiv : cond-mat/0512022 . Бибкод : 2006PhRvE..73c6121R . дои : 10.1103/PhysRevE.73.036121 . ISSN   1539-3755 . ПМИД   16605612 . S2CID   27786815 .
• Халил Шихаб (2006). «Нейронная сеть обратного распространения ошибки для безопасности компьютерных сетей» (PDF) . Журнал компьютерных наук 2 : 710–715. Архивировано из оригинала (PDF) 12 июля 2007 г.