title-icon
Яндекс.Метрика

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

26.07.2022


Геометрическая криптография — теоретические криптографические методы, в которых сообщения и шифротексты представлены в виде геометрических величин: углов, отрезков, а вычисления проводятся с помощью циркуля и линейки. Основана на сложности решения определенного класса геометрических задач, например, трисекции угла. Геометрическая криптография не имеет практического применения, но её предлагается использовать в педагогических целях, чтобы наглядно продемонстрировать принципы криптографии такие, как протокол с нулевым разглашением информации. Идея геометрической криптографии, а именно: идентификации с помощью трисекции угла, была предложена в неопубликованной работе в 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} , удовлетворящие следующим условиям:
  • C 1 ∈ A B {displaystyle C_{1}in AB}
  • C 2 ∈ {displaystyle C_{2}in } прямой A B , {displaystyle AB,} B ∈ A C 2 {displaystyle Bin AC_{2}}
  • C 3 ∉ A B {displaystyle C_{3} ot in AB}
    • Пусть 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}} известен только ей.

    Протокол:

  • Алиса передает Бобу угол ∠ R = 3 ∠ K {displaystyle angle R=3angle K} , где угол ∠ K {displaystyle angle K} выбран случайно.
  • Боб бросает монетку и сообщает Алисе результат.
  • Если выпадает "орел", Алиса передает Бобу угол ∠ K {displaystyle angle K} , и Боб проверяет, что ∠ R = 3 ∠ K {displaystyle angle R=3angle K} . В противном случае, Алиса передает Бобу угол ∠ L = ∠ K + ∠ X A {displaystyle angle L=angle K+angle X_{A}} , Боб проверяет, что 3 ∠ L = ∠ R + ∠ Y A {displaystyle 3angle L=angle R+angle Y_{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}} , используя описанный ранее протокол идентификации.

    Протокол:

  • Алиса передает Бобу угол ∠ R = 3 ∠ K {displaystyle angle R=3angle K} , где угол ∠ K {displaystyle angle K} выбирается случайно.
  • Боб кидает монетку и сообщает Алисе о результате в виде b ∈ { 0 , 1 } {displaystyle bin {0,1}} .
  • Алиса отправляет Бобу угол ∠ L = ∠ K + b ( m ∠ X A 1 + ∠ X A 2 ) {displaystyle angle L=angle K+b(mangle X_{A1}+angle X_{A2})} . Боб проверяет, что 3 ∠ L = ∠ R + b ( m ∠ Y A 1 + ∠ Y A 2 ) {displaystyle 3angle L=angle R+b(mangle Y_{A1}+angle Y_{A2})} .