АЛЬТЕРНАТИВНЫЙ ПРОТОКОЛ ДИФФИ-ХЕЛЛМАНА

1. Введение.

Более 40 лет назад Уитфилд Диффи и Мартин Хеллман представили свою концепцию изменения парадигмы генерации ключей шифрования. Их алгоритм позволил двум сторонам создавать общий секретный ключ на основе открытых параметров друг друга, без необходимости обмена секретными параметрами. Степень защиты зависит от сложности решения проблемы Диффи-Хеллмана, то есть от сложности нахождения заданных целых чисел q, g, g^a mod q (и, возможно, g^b mod q), g^ab mod q.
Доказано, что эта проблема эквивалентна проблеме дискретного логарифмирования, то есть проблема нахождения наименьшего положительного целого значение a при заданных целых числх q, g и g^a mod q. Протокол Диффи-Хеллмана был улучшен путем добавления аутентификации (для борьбы с такими угрозами, как атака «Человек посередине») и впоследствии стал основой других, более совершенных алгоритмов, таких как протоколы Нидхема – Шрёдера и MQV. Развитие протокола Диффи – Хеллмана привело к созданию средств для включения трех сторон в генерацию сеансового ключа. Концепция шифрования с использованием протокола открытого ключа для генерации общего секрета была революционной, и это отражено во многой специальной литературе.

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

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

В статье рассматривается протокол согласования ключей шифрования, устойчивый к квантовым компьютерам. Это может быть определено, как указано в Алгоритме 1 в разделе 2 ниже. Для проверки действенности протокола достаточно проверить совпадение ключа, сгенерированного отправителем, и ключа, сгенерированного получателем. Прочие аспекты, такие как сложность вычислений, устойчивость против квантового компьютера, предложения о том, какие числа следует использовать для максимальной безопасности, какие параметры открыты или секретны, рассматриваются в Разделе 3. Возможные атаки на криптосистему и контрмеры по их предотвращению рассмотрены в разделе 4. Наконец, в качестве иллюстрации приводится пример в Разделе 5, а выводы кратко изложены в Разделе 6. Доказательства представлены в Приложении А.

2. Сущность протокола.

Начальный параметр – трансцендентное число, является общим для Алисы и Боба. Защита информации повышается при передаче x через закрытый канал, однако это не обязательно. Это число может, несмотря на свою трансцендентность, иметь конечное описание (как, например, e или √ 2 ). После этого Алиса вычисляет с некоторым заданным конечным числом знаков точности. Результат она отправляет Бобу через открытый канал связи, используя свой секретный параметр a. Боб использует свой секретный параметр b для определения , который он отправляет Алисе. Наконец, Алиса вычисляет , что совпадает с  Боба согласно теореме А1 в Приложении А.
Предлагаемый протокол для генерации общего секретного ключа кратко изложен в алгоритме.

Функция  обычно является генератором псевдослучайных чисел (где s – начальное число). B_n – это набор целых чисел { 2^{n − 1} , 2^{n − 1} + 1, …, 2 n – 1 } . Для определения операции (mod 1), см. определение А2 в Приложении А. Таким образом, устанавливается общий секретный ключ k, который может впоследствии использоваться для установления закрытой связи по незащищенному каналу с помощью симметричного шифра, например XOR или AES.

Алгоритм 1: Предлагаемый протокол согласования ключей.

вход: s
∈ Z, генерируемый из множества B_n

вывод: общий секрет k
∈ Q, состоящий из n двоичных цифр

Алиса:

    x ←F (s) ∈ R Q
Выбор: a выбирается из множества B_n a ← a_x mod 1
Обмен: отправляет Бобу a

Боб:

    x ←F (s ) ∈ R Q
Выбор: b выбирается равномерно на B n b ← b_х mod 1
Обмен: отправляет b Алисе

Алиса:

    если a = b, то
Начать сначала с шага “Выбор Алисы”

    иначе

        k ← ab mod 1

Боб:
если
a = b, то

        Начать сначала с шага “Выбор Боба” выше

    иначе

        k ← a’b mod 1 конец

Вывод k

Протокол в целом основан на функции C_х, которая должна обладать как свойством однонаправленности, так и свойством симметрии. Параметр х принадлежит пространству параметров S. Здесь S = R Q .

Первое свойство, свойство однонаправленности, означает, что при известном a, должно быть просто вычислить C_x(a) для любого x ∈ S, в то время как для любого x ∈ S и заданного c должно быть трудно (практически невозможно) вычислить a такое, что С_х(а) = с. Именно эта проблема далее называется проблемой факторизации по модулю 1 или M1FP. Предполагая, что используется двоичная арифметика, максимальное количество шагов C_x достигается за полиномиальное время (теорема А2) при решении проблемы факторизации по модулю 1.

Второе свойство – это свойство симметрии, которое значит, что

С_Сх(b)(а) = С_Сх(а)(b)

для всех x ∈ S в пространстве параметров и возможных значений a и b. Это свойство необходимо функции для создания протокола согласования шифрования. В данном случае эта функция является отображением С_х : Z → (0, 1), определяемым формулой С_х(a) = a_х mod 1. Свойство симметрии C_х определяется теоремой А1, сформулированной и доказанной в Приложении А.

3. Аспекты безопасности

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

1. Если трансцендентный параметр x распространяется по защищенному каналу, почему бы не использовать это число напрямую в качестве ключа шифрования?

2. Чем отличается использование конечных чисел с плавающей запятой (аппроксимированных с определенной точностью трансцендентных чисел) от метода, основанного на использовании больших целых чисел?

Что касается пункта 1, то, конечно, возможно использование трансцендентного x в качестве ключа шифрования. Проблема в данном случае заключается в надежности: если секретность этого параметра будет нарушена, то шифрованный канал будет полностью взломан, а информация перейдет к злоумышленнику. В этом протоколе прочие процедуры будет служить дополнительными уровнями безопасности. Тем не менее, эти «улучшения» также добавляют сложности криптографическим вычислениям, однако две дополнительные операции умножения и обмен числами по каналу связи – относительно небольшая плата в пользу безопасности.

Касаемо пункта 2, при выборе трансцендентного числа не указывается, сколько десятичных знаков будет использоваться для генерации конечного ключа. Многие программные пакеты позволяют достаточно быстро вычислить большое конечное число знаков трансцендентного числа. Однако длина чисел a и b, отправленных от Алисы Бобу, и наоборот по открытым каналам, говорит о том, сколько знаков используется в приближения числа с плавающей точкой. Более того, для окончательного результата (секретный ключ, общий для Алисы и Боба), состоящего из n цифр, который идентичен для обеих сторон, количество цифр в a и b должно быть не менее 2n + 1. С другой стороны, выигрыш в безопасности происходит за счет того, что количество цифр в a и b значительно больше количества знаков секретного ключа.

3.1. Один или два уровня безопасности

Если и начальное число s, и параметры a и b являются секретными, это обеспечивает два уровня безопасности. Данная версия алгоритма упоминается как «Версия 1». Использование такого протокола между сторонами, неизвестными друг другу, может быть неудобным из-за необходимости скрытого согласования начальных параметров. Поэтому для общения сторон при установлении защищенного соединения, начальные секретные параметры могут быть распределены заранее и использоваться позже по какой-либо схеме, чтобы получить дополнительный уровень безопасности, когда это необходимо.

В качестве альтернативы может быть реализован протокол одноуровневой безопасности, если исходное число будет открытым. Эта версия алгоритма упоминается как «Версия 2». В этом случае вся безопасность зависит от сложности решения проблемы факторизации по модулю 1 и секретности параметров a и b. Тем не менее, если трансцендентный x вычисляется с очень большим количеством десятичных знаков, для злоумышленника возникает дополнительная проблема, связанная с тем, что он не знает, сколько знаков точности трансцендентного числа необходимо для получения действующего ключа шифрования. Преимущество открытого начального параметра в том, что гораздо проще организовать первоначальный контакт сторон при обмене начальными параметрами по открытым каналам. Протокол, позволяющий открыто инициализировать начальный параметр s, необходим для успешного установления шифрованной связи для сторон, ранее не известных друг-другу.

3.2. Комментарии о начальном трансцендентном числе

При реализации данного протокола желательно, чтобы числа x = F(s) ∈ R Q были абсолютно разными для одинаковых s
∈ Z, используемых в разных сеансах связи, для того чтобы увеличить случайность последующих параметров.

То есть, если существует другой параметр t
∈ Z такой, что s НЕ РАВНО t, но s ≈ t, это не должно означать, что F(s) mod 1 ≈ F(t) mod 1. Точнее это свойство разрыва можно определить как

∃ ε > 0 ∀ δ > 0: (| s – t |> δ ∧ | F ( s ) – F ( t ) | < ε ) .
Данное свойство трансцендентного числа достигается использованем генератора случайных чисел при его выборе.

3.3. Выбор секретных целых чисел

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

4. Возможные атаки и контрмеры к ним.

Вне зависимости от того, является начальный параметр s секретным или нет, имеет место атака на протокол, представленная в Алгоритме 2 ниже. Предполагается, что функция F, отображающая трансцендентный параметр x из начального параметра s, известна злоумышленнику.

Случай, когда s является секретным, называется «Версией 1», а случай, когда s является открытым, называется «Версией 2». Перехватив a и b, Ева пытается подобрать параметр s ∈ B_n = { 2n − 1 , 2n − 1 + 1, …, 2n – 1 }, который мог бы инициализировать секретный параметр. Найдя предположительный подходящий параметр σ, соответствующий s, она находит θ соответствующее a∈B_n и b∈B_n .Затем она вычисляет θ = [α2nF(σ)], сравнивая θ с a и θ = [ β2n F(σ)], сравнивая это значение θ с b. При совпадении (θ = a или θ = b) раскрывается общий секрет k = θθ mod 1. По количеству знаков в a и b, она может сделать вывод, сколько знаков N составляет точность аппроксимации параметра с плавающей точкой x. Защита от этой атаки – наибольшая сложность вычислений.

Алгоритм 2: схематическое описание возможной атаки.
вход: a, b
∈ Q, перехваченные в открытом канале связи.

вывод: Десятичные числа k в
соответствии с условиями в алгоритме 1.

для σ ∈ B_n сделать:

    для θ ∈ B n do
θ = θ F ( σ ) mod 1

        если θ = a или θ = b, то

            k ← θθ mod 1

Вывод κ

Если начальный параметр s ∈ B_n также является общедоступным, Еве достаточно лишь подобрать a
∈ B_n и b ∈ B_n, что, очевидно, вычислительно проще. Это связано с исключением внешнего цикла for в алгоритме атаки 2, представленном выше.

Самая известная угроза протоколу Диффи – Хеллмана – это атака «человек посередине». Однако данная проблема протокола уже исправлена. Модификации данного алгоритма, такие как протокол MQV и алгоритм Нидхема – Шрёдера, устойчивы к этой атаке, так как используют процедуры аутентификации сторон.

4.1. Устойчивость к квантовому компьютеру

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

5. Пример

Предположим, что Алиса хочет отправить Бобу сообщение «I am Alice». Чтобы облегчить понимание алгоритма, в данном примере используется основание 10, хотя на практике, все числа представляются в двоичной или другой необходимой форме. Она преобразовывает сообщение «I am Alice» в открытый текст – последовательность трехзначных чисел ASCII:

M = 077032097109032065108105099101.

Затем для генерации ключа, Алиса считывает параметр s, объявленный публично или тайно, выбранный из множества D_n = { 10 n , 10 n + 1,. . . , 10 n + 1 – 1 } (где n должно быть не менее 1000 для достаточного уровня надежности в соответствии с существующими вычислительными возможностями). D_n соответствует десятичным числам, а B_n – двоичным числам. Этот исходный параметр подается в генератор псевдослучайных чисел, который возвращает действительное число x на (0, 1). Допустим, при s → log (s) mod 1 и s = 2 (для данного примера) Алиса получает

x = 0.693147180559945309417232121458 . . .

 

Затем она выбирает свой секретный параметр a из множества D_n (где значение n также должно быть не менее 1000 для надежности). Допустим, она выбирает n = 10, а параметр a = 9861328816 и вычисляет

a = a_x mod 1 =  6835352265.384943695140187286296328528834383488. . . mod 1

из которых первый 61 десятичный знак

0,3849436951401872862963285295789151385786568625756645191323560

она посылает Бобу (61 знак для получения 30 знаков в конечном ключе k). Боб, в свою очередь, выбирает свой секрет b = 6913952452 и вычисляет

b’ = b_x mod 1 = 4792386648.629320605031170717208921697772544736. . . mod 1

из которых первую 61 цифру

0,6293206050311707172089216982945490750864162655735586555442321

он отправляет Алисе. Затем, после проверки того, что a и b различны, начинается последний шаг генерации ключа. Алиса генерирует общий секрет:

k = ab mod 1 = =6205937416.896438371827726635679694849875824409871… mod 1 = =0,896438371827726635679694849875824409871. . .

Боб делает то же самое

k = ab mod 1= 2661482404.896438371827726635679694849875824409871642. . . mod 1 = 0,896438371827726635679694849875824409871642. . .

Затем Алиса шифрует свой открытый текст

m = 077032097109032065108105099101

например, с помощью алгоритма XOR на 30 десятичных цифрах ключа k

c = m ⊕ k = 697525738788675892280877652154

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

c ⊖ k = 077032097109032065108105099101

который легко преобразуется обратно в «I am Alice» с помощью таблицы ASCII.

6. Выводы

Помимо устойчивости к квантовым компьютерам, большое преимущество предложенного протокола, в отличие от методологии конечных полей Диффи – Хеллмана, заключается в использовании десятичной части трансцендентных чисел, а не больших конечных целых чисел. Использование трансцендентных чисел не дает по своей сути ограничений на количество цифр при вычислении, в отличие от целых чисел. В случае конечных полей секретные параметры ограничены порядком конечного поля q. Для нахождения ключа методом грубой силы необходимо лишь перебирать все числа меньшие q. Предлагаемый алгоритм накладывает определенные границы на числа a и b. Однако, криптоанализ по действующим в настоящее время алгоритмам Шора и Гровера не представляет угрозы для этого протокола.

Более того, по сравнению с классическим методом Диффи – Хеллмана для генерации общего секрета, преимущество данного протокола заключаются в том, что он изначально требует передачи меньшего числа параметров и размер ключа неизвестен. Проблема данного алгоритма в том, что он требует одинаковой трактовки трансцендентных чисел различными устройствами. Данное направление актуально для будущих исследований.

Приложение А

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

Определение A1. Целая часть от x ∈ R
[x] = max { z
∈ Z : z ≤ x } .

Тривиально, [х] = х , когда х ∈ Z . Для целой части действительного числа действуют следующие арифметические законы:

Лемма A1. Для всех х ∈ R и у ∈ Z , [х - у] = [х] – [y] .

Доказательство. Согласно определению А1

[x - y] = max { z ∈ Z : z ≤ x – y } = max { z ∈ Z : z + y ≤ x }

= max { z + y ∈ Z : z + y ≤ x } – y = [x] – [y]

Так как у = [у] , у ∈ Z .

 

Определение A2. Дробная часть вещественного числа х -
х mod 1 равна х mod 1 = х – [х] .

Для протокола согласования симметричного ключа шифрования используется односторонняя функция Cx, обладающая свойством симметрии

С_Сх(b)(а) = С_Сх(а)(b)

для всех возможных значений a, b. Отображение C_х обладает этим свойством для десятичной части числа.

Теорема A1. Для любого действительного числа x и целых чисел a, b

( a_х mod 1 ) b mod 1 = ( b_х mod 1 ) a mod 1

Доказательство. Для любого действительного числа x и целых чисел a, b согласно лемме А1,

( a_х mod 1 ) b mod 1 = ( a_х – [ a_х ]) b – [( a_х - [ a_х ]) b ] = a_х b – [ a_х ] b – [ a_х b - [ a_х ] b ]

= a_х b – [ ax ] b – [ a_х b ] + [[ a_х ] b ] = a_х b – [ a_х b ] = a_х b mod 1

Замена местами a и b выше дает ( b_х mod 1 ) a mod 1 = b_хa mod 1, из-за коммутативности действительных чисел.

Теорема A2. Полиномиальная сложность Алгоритма 1.

Доказательство. Операция, порождающая трансцендентный x ∈ R Q из начального числа s, не рассматривается как часть алгоритма, так как ее можно провести заранее. При использовании числа x в алгоритме с точностью N бит (как числа с плавающей точкой ∈ Q ) вычисление первого шага a = a_х mod 1 может быть выполнено за O(N log N loglogN) шагов. То же касается вычисления b = b_х mod 1. Наконец, генерация ключа k выполняется путем вычисления ab mod 1 и ab mod 1 соответственно, таким образом добавляя O( N log N loglog N) шагов расчета. В общей сложности, это означает, что вычисление, обратное «Алгоритму 1», выполняется за полиномиальное время.

Библиографический список

1. Diffie, W.; Hellman, M. New Directions in Cryptography. IEEE Trans. Inf. Theory 1976, 22, 644–655.
2. Gupta, D.; Biswas, G. On Securing Bi- and Tri-partite Session Key Agreement Protocol Using IBE Framework. Wirel. Pers. Commun. 2017, 96, 4505–4524.
3. Goldwasser, S. New Directions in Cryptography: Twenty Some Years Later. In Proceedings of the 38th Annual Symposium on Foundations of Computer Science, Miami Beach, FL, USA, 20–22 October 1997; pp. 314–324.
4. Shor, P. Polynomial-time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM J. Comput. 1997, 25, 1484–1509.
5. Hoffstein, J.; Pipher, J.; Silverman, J. NTRU: A Ring-based Public Key Cryptosystem. In Algorithmic Number Theory, Third International Symposium ANTS-III; Springer: Berlin/Heidelberg, Germany, 1998, pp. 267–288.
6. Hoffstein, J.; Pipher, J.; Silverman, J. NSS: An NTRU Lattice-based Signature Scheme. In Advance in Cryptology—EUROCRYPT 2001, International Conference on the Theory and Applications of Cryptographic Techniques; Springer: Berlin/Heidelberg, Germany, 2001; pp. 211–228.
7. Lei, X.; Liao, X. NTRU-KE: A Lattice-based Public Key Exchange Protocol. IACR Cryptol. ePrint Arch. 2013, 2013, 718.

---

Количество просмотров публикации: Please wait

Все статьи автора «Коршев Максим Александрович»