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

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

Аксиоматика

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

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

• Через две данные точки A {displaystyle A} и B {displaystyle B} можно провести прямую A B {displaystyle AB} , притом единственную.
• Две различные перескающиеся прямые имеют точку пересечения, притом единственную.
• Пусть A {displaystyle A} и B {displaystyle B} различные точки, то всегда существуют различные точки C 1 , C 2 , C 3 {displaystyle C_{1},C_{2},C_{3}} , несовпадающие с точками A {displaystyle A} и B {displaystyle B} , удовлетворящие следующим условиям:

• Пусть A B {displaystyle AB} — отрезок, C D {displaystyle CD} — луч. Тогда существует точка E ∈ C D {displaystyle Ein CD} , такая что A B {displaystyle AB} и C E {displaystyle CE} конгруэнтны.
• Имея окружность и пересекающую её прямую, можно получить точки их пересечения.

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

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

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

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

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

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

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

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

Протокол:

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

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

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

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

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

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

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

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

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

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

Протокол: