Русская Википедия:Геометрическая криптография
Геометрическая криптография — теоретические криптографические методы, в которых сообщения и шифротексты представлены в виде геометрических величин: углов, отрезков, а вычисления проводятся с помощью циркуля и линейки. Основана на сложности решения определенного класса геометрических задач, например, трисекции угла. Геометрическая криптография не имеет практического применения, но её предлагается использовать в педагогических целях, чтобы наглядно продемонстрировать принципы криптографии такие, как протокол с нулевым разглашением информации. Идея геометрической криптографии, а именно: идентификации с помощью трисекции угла, была предложена в неопубликованной работе[1] в 1997 году. Является примером криптографии в нестандартной модели вычислений[2][3].
Аксиоматика
Современная теория вычислений построена на применении логических операций к последовательности бит. Невозможность решения проблемы трисекции угла может быть использована в качестве аналога проблемы остановки. В результате чего, можно построить теорию вычислений, основанную на других канонических понятиях[1].
Простейшие операции, осуществимые с помощью циркуля и линейки на плоскости:Шаблон:Sfn
- Через две данные точки <math>A</math> и <math>B</math> можно провести прямую <math>AB</math>, притом единственную.
- Две различные перескающиеся прямые имеют точку пересечения, притом единственную.
- Пусть <math>A</math> и <math>B</math> различные точки, то всегда существуют различные точки <math>C_1, C_2, C_3</math>, несовпадающие с точками <math>A</math> и <math>B</math>, удовлетворящие следующим условиям:
- <math>C_1 \in AB</math>
- <math>C_2 \in</math> прямой <math>AB,</math> <math>B \in AC_2</math>
- <math>C_3 \not\in AB</math>
- Пусть <math>AB</math> — отрезок, <math>CD</math> — луч. Тогда существует точка <math>E \in CD</math>, такая что <math>AB</math> и <math>CE</math> конгруэнтны.
- Имея окружность и пересекающую её прямую, можно получить точки их пересечения.
Имея данные операции, можно показать, что выполнимы более сложные задачи, такие как бисекция угла, построение перпендикуляра к прямой.
В криптографии необходимо уметь генерировать секрет, который не может быть получен посторонними лицами, то есть в данном случае восстановлен с помощью циркуля и линейки. Для этого требуется еще одна дополнительная аксиома:
- Возможно выбрать точку принадлежащую единичному кругу.
Трисекция угла
Трисекция угла с помощью циркуля и линейки является невыполнимой задачей. Обратная задача (построение угла в три раза большего, чем данный) является разрешимой при тех же условиях. Таким образом, трисекция угла представляет собой аналог односторонней функции в данной модели[1].
Протокол идентификации
Алиса (доказывающая сторона) должна подтвердить свою личность Бобу (проверяющей стороне)[1].
Инициализация: Алиса случайным образом генерирует угол <math>\angle X_A</math>, публикует угол в три раза больший <math>\angle Y_A = 3\angle X_A</math>. При этом Алиса может быть уверена, что угол <math>\angle X_A</math> известен только ей.
Протокол:
- Алиса передает Бобу угол <math>\angle R = 3\angle K</math>, где угол <math>\angle K</math> выбран случайно.
- Боб бросает монетку и сообщает Алисе результат.
- Если выпадает "орел", Алиса передает Бобу угол <math>\angle K</math>, и Боб проверяет, что <math>\angle R = 3\angle K</math>. В противном случае, Алиса передает Бобу угол<math>\angle L = \angle K + \angle X_A</math>, Боб проверяет, что <math>3 \angle L = \angle R + \angle Y_A</math>.
Описанная выше последовательность шагов повторяется <math>t</math> раз независимо. Боб подтверждает личность Алисы тогда и только тогда, когда все <math>t</math> итераций протокола завершились корректно. Постороннее лицо, не знающее ключ <math>\angle X_A</math>, не может построить оба угла <math>\angle L, \angle K</math>, иначе это значило бы, что возможно построить угол <math>\angle X_A = \angle L - \angle K</math>.
После успешного выполнения операций можно утверждать с вероятностью <math>P(t) = 1 - 2^{-t}</math>, что доказывающая сторона знает ключ <math>\angle X_A</math>.
Также можно показать, что данный протокол является протоколом с нулевым разглашением информации.
Доказательство:
Пространство событий с точки зрения Боба состоит из исходов двух типов: <math>(\angle R, 0, \angle K),</math> <math> (\angle R, 1, \angle L)</math>.
Для имитации первого случая Бобу достаточно взять случайный угол <math>\angle K</math> и угол <math>\angle R = 3\angle K</math>. Случайно выбирая угол <math>\angle L</math> и выражая <math>\angle R</math> из соотношения <math>3 \angle L = \angle R + \angle Y_A</math>, Боб может имитировать второй случай.
Таким образом Боб может полностью имитировать свое взаимодействие с Алисой, а значит не получает никакой информации о ключе <math>\angle X_A</math>.
Протокол аутентификации
Протокол идентификации может быть преобразован в протокол аутентификации[1]. Пусть <math>m</math> - сообщение, которое Алиса хочет аутентифицировать:
Инициализация: Для данного протокола Алисе необходимы два ключа <math>\angle X_{A1}, \angle X_{A2}</math>. Публикуются углы <math>\angle Y_{A1} = 3\angle X_{A1},</math><math> \angle Y_{A2} =3 \angle X_{A2}</math>. Для аутентификации сообщения <math>m</math> Алиса доказывает Бобу, что ей известен угол <math>\angle Z = m \angle X_{A1} +\angle X_{A2}</math> , используя описанный ранее протокол идентификации.
Протокол:
- Алиса передает Бобу угол <math>\angle R = 3\angle K</math>, где угол <math>\angle K</math> выбирается случайно.
- Боб кидает монетку и сообщает Алисе о результате в виде <math>b \in \{0, 1\}</math>.
- Алиса отправляет Бобу угол <math>\angle L = \angle K + b (m\angle X_{A1} + \angle X_{A2})</math>. Боб проверяет, что <math>3\angle L = \angle R + b (m\angle Y_{A1} + \angle Y_{A2})</math>.
Примечания
Литература
