УСТОЙЧИВОСТЬ SMT-ПРОТОКОЛА К АТАКАМ ПРОТИВНИКА В МОДЕЛИ БЕЗОПАСНОСТИ ДОЛЕВА—ЯО
60 А. В. Александров
УДК 519.6
А. В. АЛЕКСАНДРОВ
УСТОЙЧИВОСТЬ SMT-ПРОТОКОЛА К АТАКАМ ПРОТИВНИКА В МОДЕЛИ БЕЗОПАСНОСТИ ДОЛЕВА—ЯО
Устанавливаются свойства конфиденциальности SMT-протокола (Secure Message Transmission Protocols) с общей памятью. Конфиденциальность понимается как устойчивость протокола передачи к атакам активного или пассивного противника в обобщенном канале связи, подчиненного модели безопасности Долева—Яо.
Ключевые слова: криптографические протоколы передачи, схема разделения секрета, модель безопасности Долева—Яо.
Введение. Практическая стойкость, которая лежит в основе современных криптосистем и криптографических протоколов, обеспечивает противодействие взлому закрытого текста или протокола передачи данных на время, большее времени сохранения конфиденциальности и жизни самого передаваемого документа. Возрастание вычислительной мощности компьютеров, появление новых видов криптографических атак на ключи шифрования и криптографические протоколы [1, 2] могут резко снизить порог практической стойкости современных криптографических средств. При создании практически стойких криптографических схем используется теория сложности алгоритмов и, в частности, так называемые односторонние функции. Доказательство существования односторонних функций опирается на не доказанную гипотезу о несовпадении классов алгоритмически P-сложных и NP-сложных задач: P ≠ NP .
В криптографии востребован конфиденциальный обмен, обладающий параметрами стойкости и надежности в абсолютном или почти абсолютном смысле. В работе К. Шеннона [3] решен вопрос о существовании абсолютно стойкого шифра, обеспечивающего противодействие пассивному противнику. Современные исследования по абсолютно или почти абсолютно секретной и надежной связи развиваются в рамках так называемых SMT-протоколов (Secure Message Transmissions Protocols) и обобщают результаты К. Шеннона по нескольким важным направлениям. На основе этого возникла современная модель безопасности Долева— Яо [4], в соответствии с которой возможность противостоять противнику в канале связи переносится на сетевой граф. Кроме того, противник помимо прослушивания трафика может производить быструю подмену сообщений в определенных ветвях графа. Последнее, в частности означает, что воздействие противника приравнивается к воздействию некоторого шума в обобщенном канале связи.
(n,n)-пороговые и (k,n)-пороговые схемы разделения секретного сообщения. Основным инструментом в SMT-протоколах выступают пороговые схемы разделения секретного сообщения (секрета), работающие в конечных полях. Схема предложенная А. Шамиром, представляет собой классическую (n,n)-пороговую схему разделения секрета, позволяющую вычислять доли секрета S для любых значений n. Схема разделения секрета Шамира использует многочлены степени n–1 над полем Галуа GFp:
pn−1(x) = an xn−1 + ... + a1x + S , an−1,…, a1 ∈ rand GFp .
(1)
Долей секрета Sharei (S) является упорядоченная пара: Sharei (S ) = (i, pn−1(i)), i ≠ 0 .
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2012. Т. 55, № 8
Устойчивость SMT-протокола к атакам противника
61
Теорема о полиномиальной интерполяции для многочленов (1) над полем GFp сохраняет свою силу, поэтому при наличии не менее n совокупностей попарно различных долей секрет
S восстанавливается по интерполяционной формуле Лагранжа:
∏pn−1 ( x)
=
n−1 i=1, j≠i
x xj
− xi − xi
,
pn−1(0) = S .
Можно показать, что при количестве долей секрета мощностью менее n значение S не только неопределенно, но и с равной вероятностью распределено по всему полю, так что любой элемент поля может приобрести значение S. Аналогичным образом, на основе многочленов над полем строятся (k,n)-пороговые схемы разделения секрета k>n. В работе [5] отмечено, что (k,n)-пороговые схемы разделения для k=3n+1 эквивалентны кодам Рида—Соломона, исправляющим ошибки в канале связи.
SMT-протоколы. Современные работы по SMT-протоколам обширны (см. обзоры [3, 4]). Свойства конфиденциальности SMT-протоколов с нулевой общей памятью и некоторыми дополнительными условиями на пути в канале связи, а также их криптоанализ приведены в [4].
В настоящей статье рассматривается протокол конфиденциального обмена с общей памятью между абонентами A и B. Абоненты расположены в вершинах ориентированного графа и связаны между собой, по крайней мере, n>1 непересекающимися путями. Такие графы называются графами высокого порядка связности. Степень активности противника в рамках модели Долева—Яо предполагается такой, что он может контролировать почти все каналы связи в режиме прослушивания и некоторую часть каналов — в режиме перехвата и быстрой замены проходящего трафика. Эти случаи различаем терминами „пассивный противник“ и „активный противник“ соответственно.
Основные определения. Пусть G(V , R) — ориентированный граф, с множеством вер-
шин V , включающим в себя элементы {A, B} и ребра R = {Γ1,..., Γn , q} , n>1 такие, что:
Γ1,..., Γn ⎯ ориентированы от A к B, q ⎯ ориентирован от B к A.
Все ребра попарно не пересекаются, за исключением своих концов в А и В, и их ориентация задает в графе направление передачи трафика в сети.
Передаваемый секрет S считаем элементом числового поля GFp (p — простое, достаточно большое число), S находится в A. Множество пересылки сообщений D = {d1...., dk ) назовем ис-
торией переписки между A и B. Это множество всех сообщений, которыми обмениваются A и B в рамках действия протокола. Случай пустого множества D не исключается.
Обозначим П(A,B,D,S) — протокол обмена сообщениями между A и B, в результате ко-
торого в точке B должно быть получено числовое значение S ∈ GFp . Во время работы всего
протокола П в графе G(V , R) действует k-активный противник P (k
УДК 519.6
А. В. АЛЕКСАНДРОВ
УСТОЙЧИВОСТЬ SMT-ПРОТОКОЛА К АТАКАМ ПРОТИВНИКА В МОДЕЛИ БЕЗОПАСНОСТИ ДОЛЕВА—ЯО
Устанавливаются свойства конфиденциальности SMT-протокола (Secure Message Transmission Protocols) с общей памятью. Конфиденциальность понимается как устойчивость протокола передачи к атакам активного или пассивного противника в обобщенном канале связи, подчиненного модели безопасности Долева—Яо.
Ключевые слова: криптографические протоколы передачи, схема разделения секрета, модель безопасности Долева—Яо.
Введение. Практическая стойкость, которая лежит в основе современных криптосистем и криптографических протоколов, обеспечивает противодействие взлому закрытого текста или протокола передачи данных на время, большее времени сохранения конфиденциальности и жизни самого передаваемого документа. Возрастание вычислительной мощности компьютеров, появление новых видов криптографических атак на ключи шифрования и криптографические протоколы [1, 2] могут резко снизить порог практической стойкости современных криптографических средств. При создании практически стойких криптографических схем используется теория сложности алгоритмов и, в частности, так называемые односторонние функции. Доказательство существования односторонних функций опирается на не доказанную гипотезу о несовпадении классов алгоритмически P-сложных и NP-сложных задач: P ≠ NP .
В криптографии востребован конфиденциальный обмен, обладающий параметрами стойкости и надежности в абсолютном или почти абсолютном смысле. В работе К. Шеннона [3] решен вопрос о существовании абсолютно стойкого шифра, обеспечивающего противодействие пассивному противнику. Современные исследования по абсолютно или почти абсолютно секретной и надежной связи развиваются в рамках так называемых SMT-протоколов (Secure Message Transmissions Protocols) и обобщают результаты К. Шеннона по нескольким важным направлениям. На основе этого возникла современная модель безопасности Долева— Яо [4], в соответствии с которой возможность противостоять противнику в канале связи переносится на сетевой граф. Кроме того, противник помимо прослушивания трафика может производить быструю подмену сообщений в определенных ветвях графа. Последнее, в частности означает, что воздействие противника приравнивается к воздействию некоторого шума в обобщенном канале связи.
(n,n)-пороговые и (k,n)-пороговые схемы разделения секретного сообщения. Основным инструментом в SMT-протоколах выступают пороговые схемы разделения секретного сообщения (секрета), работающие в конечных полях. Схема предложенная А. Шамиром, представляет собой классическую (n,n)-пороговую схему разделения секрета, позволяющую вычислять доли секрета S для любых значений n. Схема разделения секрета Шамира использует многочлены степени n–1 над полем Галуа GFp:
pn−1(x) = an xn−1 + ... + a1x + S , an−1,…, a1 ∈ rand GFp .
(1)
Долей секрета Sharei (S) является упорядоченная пара: Sharei (S ) = (i, pn−1(i)), i ≠ 0 .
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2012. Т. 55, № 8
Устойчивость SMT-протокола к атакам противника
61
Теорема о полиномиальной интерполяции для многочленов (1) над полем GFp сохраняет свою силу, поэтому при наличии не менее n совокупностей попарно различных долей секрет
S восстанавливается по интерполяционной формуле Лагранжа:
∏pn−1 ( x)
=
n−1 i=1, j≠i
x xj
− xi − xi
,
pn−1(0) = S .
Можно показать, что при количестве долей секрета мощностью менее n значение S не только неопределенно, но и с равной вероятностью распределено по всему полю, так что любой элемент поля может приобрести значение S. Аналогичным образом, на основе многочленов над полем строятся (k,n)-пороговые схемы разделения секрета k>n. В работе [5] отмечено, что (k,n)-пороговые схемы разделения для k=3n+1 эквивалентны кодам Рида—Соломона, исправляющим ошибки в канале связи.
SMT-протоколы. Современные работы по SMT-протоколам обширны (см. обзоры [3, 4]). Свойства конфиденциальности SMT-протоколов с нулевой общей памятью и некоторыми дополнительными условиями на пути в канале связи, а также их криптоанализ приведены в [4].
В настоящей статье рассматривается протокол конфиденциального обмена с общей памятью между абонентами A и B. Абоненты расположены в вершинах ориентированного графа и связаны между собой, по крайней мере, n>1 непересекающимися путями. Такие графы называются графами высокого порядка связности. Степень активности противника в рамках модели Долева—Яо предполагается такой, что он может контролировать почти все каналы связи в режиме прослушивания и некоторую часть каналов — в режиме перехвата и быстрой замены проходящего трафика. Эти случаи различаем терминами „пассивный противник“ и „активный противник“ соответственно.
Основные определения. Пусть G(V , R) — ориентированный граф, с множеством вер-
шин V , включающим в себя элементы {A, B} и ребра R = {Γ1,..., Γn , q} , n>1 такие, что:
Γ1,..., Γn ⎯ ориентированы от A к B, q ⎯ ориентирован от B к A.
Все ребра попарно не пересекаются, за исключением своих концов в А и В, и их ориентация задает в графе направление передачи трафика в сети.
Передаваемый секрет S считаем элементом числового поля GFp (p — простое, достаточно большое число), S находится в A. Множество пересылки сообщений D = {d1...., dk ) назовем ис-
торией переписки между A и B. Это множество всех сообщений, которыми обмениваются A и B в рамках действия протокола. Случай пустого множества D не исключается.
Обозначим П(A,B,D,S) — протокол обмена сообщениями между A и B, в результате ко-
торого в точке B должно быть получено числовое значение S ∈ GFp . Во время работы всего
протокола П в графе G(V , R) действует k-активный противник P (k