Геометрическая криптография

Геометрическая криптография — теоретические криптографические методы, в которых сообщения и шифротексты представлены в виде геометрических величин: углов, отрезков, а вычисления проводятся с помощью циркуля и линейки. Основана на сложности решения определенного класса геометрических задач, например, трисекции угла. Геометрическая криптография не имеет практического применения, но её предлагается использовать в педагогических целях, чтобы наглядно продемонстрировать принципы криптографии такие, как протокол с нулевым разглашением информации. Идея геометрической криптографии, а именно: идентификации с помощью трисекции угла, была предложена в неопубликованной работе в 1997 году. Является примером криптографии в нестандартной модели вычислений.

Аксиоматика

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

Простейшие операции, осуществимые с помощью циркуля и линейки на плоскости:Шаблон:Sfn

• Через две данные точки $A$ и $B$ можно провести прямую $AB$, притом единственную.
• Две различные перескающиеся прямые имеют точку пересечения, притом единственную.
• Пусть $A$ и $B$ различные точки, то всегда существуют различные точки $C_1,C_2,C_3$, несовпадающие с точками $A$ и $B$, удовлетворящие следующим условиям:

1. $C_1\in AB$
2. $C_2\in$ прямой $AB,$ $B\in A{C}_2$
3. $C_3\in ̸AB$

• Пусть $AB$ — отрезок, $CD$ — луч. Тогда существует точка $E\in CD$, такая что $AB$ и $CE$ конгруэнтны.
• Имея окружность и пересекающую её прямую, можно получить точки их пересечения.

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

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

• Возможно выбрать точку принадлежащую единичному кругу.

Трисекция угла

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

Протокол идентификации

Алиса (доказывающая сторона) должна подтвердить свою личность Бобу (проверяющей стороне).

Инициализация: Алиса случайным образом генерирует угол $\mathrm{\angle }{X}_A$, публикует угол в три раза больший $\mathrm{\angle }{Y}_A=3\mathrm{\angle }{X}_A$. При этом Алиса может быть уверена, что угол $\mathrm{\angle }{X}_A$ известен только ей.

Протокол:

1. Алиса передает Бобу угол $\mathrm{\angle }R=3\mathrm{\angle }K$, где угол $\mathrm{\angle }K$ выбран случайно.
2. Боб бросает монетку и сообщает Алисе результат.
3. Если выпадает "орел", Алиса передает Бобу угол $\mathrm{\angle }K$, и Боб проверяет, что $\mathrm{\angle }R=3\mathrm{\angle }K$. В противном случае, Алиса передает Бобу угол$\mathrm{\angle }L=\mathrm{\angle }K+\mathrm{\angle }{X}_A$, Боб проверяет, что $3\mathrm{\angle }L=\mathrm{\angle }R+\mathrm{\angle }{Y}_A$.

Описанная выше последовательность шагов повторяется $t$ раз независимо. Боб подтверждает личность Алисы тогда и только тогда, когда все $t$ итераций протокола завершились корректно. Постороннее лицо, не знающее ключ $\mathrm{\angle }{X}_A$, не может построить оба угла $\mathrm{\angle }L,\mathrm{\angle }K$, иначе это значило бы, что возможно построить угол $\mathrm{\angle }{X}_A=\mathrm{\angle }L-\mathrm{\angle }K$.

После успешного выполнения операций можно утверждать с вероятностью $P(t)=1-2^{-t}$, что доказывающая сторона знает ключ $\mathrm{\angle }{X}_A$.

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

Доказательство:

Пространство событий с точки зрения Боба состоит из исходов двух типов: $(\mathrm{\angle }R,0,\mathrm{\angle }K),$ $(\mathrm{\angle }R,1,\mathrm{\angle }L)$.

Для имитации первого случая Бобу достаточно взять случайный угол $\mathrm{\angle }K$ и угол $\mathrm{\angle }R=3\mathrm{\angle }K$. Случайно выбирая угол $\mathrm{\angle }L$ и выражая $\mathrm{\angle }R$ из соотношения $3\mathrm{\angle }L=\mathrm{\angle }R+\mathrm{\angle }{Y}_A$, Боб может имитировать второй случай.

Таким образом Боб может полностью имитировать свое взаимодействие с Алисой, а значит не получает никакой информации о ключе $\mathrm{\angle }{X}_A$.

Протокол аутентификации

Протокол идентификации может быть преобразован в протокол аутентификации. Пусть $m$ - сообщение, которое Алиса хочет аутентифицировать:

Инициализация: Для данного протокола Алисе необходимы два ключа $\mathrm{\angle }{X}_{A1},\mathrm{\angle }{X}_{A2}$. Публикуются углы $\mathrm{\angle }{Y}_{A1}=3\mathrm{\angle }{X}_{A1},$$\mathrm{\angle }{Y}_{A2}=3\mathrm{\angle }{X}_{A2}$. Для аутентификации сообщения $m$ Алиса доказывает Бобу, что ей известен угол $\mathrm{\angle }Z=m\mathrm{\angle }{X}_{A1}+\mathrm{\angle }{X}_{A2}$ , используя описанный ранее протокол идентификации.

Протокол:

1. Алиса передает Бобу угол $\mathrm{\angle }R=3\mathrm{\angle }K$, где угол $\mathrm{\angle }K$ выбирается случайно.
2. Боб кидает монетку и сообщает Алисе о результате в виде $b\in \{0,1\}$.
3. Алиса отправляет Бобу угол $\mathrm{\angle }L=\mathrm{\angle }K+b(m\mathrm{\angle }{X}_{A1}+\mathrm{\angle }{X}_{A2})$. Боб проверяет, что $3\mathrm{\angle }L=\mathrm{\angle }R+b(m\mathrm{\angle }{Y}_{A1}+\mathrm{\angle }{Y}_{A2})$.

Литература

• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Статья