close

Вход

Забыли?

вход по аккаунту

?

Схемы построения двушагово односторонних функций.

код для вставкиСкачать
МАТЕМАТИКА
Вестн. Ом. ун-та. 2011. № 4. С. 15–18.
УДК 512.62
С.Ю. Ерофеев
СХЕМЫ ПОСТРОЕНИЯ ДВУШАГОВО
ОДНОСТОРОННИХ ФУНКЦИЙ
Предлагаются схемы построения двушагово односторонних функций на основе неразрешимости Диофантовой проблемы и сложности нахождения дискретного логарифма. Рассматриваются предпосылки криптостойкости предложенных схем.
Ключевые слова: односторонняя функция, дискретный логарифм, Диофантова проблема.
Введение
Односторонние функции являются неотъемлемой частью криптографических схем и протоколов. Теоретически их существование до
сих пор не доказано. В то же время односторонние функции являются
основным инструментом во многих разделах и приложениях криптографии, в частности, в протоколах аутентификации, электронных
подписях, алгоритмах генерации псевдослучайных последовательностей и т. п.
Определение. Односторонней называется функция, эффективно
вычисляемая за полиномиальное время на детерминированной машине Тьюринга, для которой не существует вероятностной машины Тьюринга, вычисляющей за полиномиальное время обратную к этой
функции, с более чем экспоненциально малой вероятностью.
Претендентами в односторонние функции являются: показательx
ная функция g : a
a в мультипликативных группах простых конечных полей, основанная на трудности вычисления дискретного логарифма; степенная функция по модулю, равному произведению двух
больших (секретных) простых чисел, f : x
x e mod n, n = pq . В работе
Л.А. Левина [1] приводится явное комбинаторное построение функции, которая является односторонней, если существует хотя бы одна
односторонняя функция.
Определение. Диофантовым называется многочлен P ( x1 ,..., xn ) с
целыми коэффициентами от коммутирующих переменных x1 ,..., xn .
Определение. Диофантовым называется уравнение вида
P( x1 ,..., xn ) = 0 .
Ю.В. Матиясевич доказал неразрешимость 10-й проблемы Гильберта. Он доказал, что не существует алгоритма, определяющего по
произвольному диофантову уравнению P( x1 ,..., xn ) = 0, обладает ли оно
решением в целых числах (см. [2 – 4]). Более того, он заметил, что существует фиксированный диофантов многочлен F ( x1 ,..., xn ) такой, что
не существует алгоритма нахождения решения уже в классе уравнений вида F ( x1 ,..., xn ) = c, где c ∈ Z .
Таким образом, можно определить функцию на основе неразрешимости Диофантовой проблемы, которая может рассматриваться в
качестве претендента на одностороннюю функцию.
© С.Ю. Ерофеев, 2011
С.Ю. Ерофеев
16
Цель данной статьи – предложить несколько схем построения двушагово односторонних функций на основе неразрешимости Диофантовой проблемы и трудности нахождения дискретного логарифма, а также рассмотреть предпосылки
криптостойкости предложенных схем.
Заметим, что предложенные схемы
могут быть основанием протоколов аутентификации, цифровой подписи и т. п.
1. Построение двушагово односторонних функций на основе неразрешимости Диофантовой проблемы
Пусть F ∈ Z [ x1 ,…, xn ] – диофантов многочлен. По любому диофантову многочлену
F определяется функция F : Z n → Z ,
F : ( a1 ,… an ) F (a1 ,…, an ).
(1)
1.1. Схема 1
По любому набору диофантовых многочленов F ∈ Z [ x1 ,…, xm ] , Pi ∈ Z [ x1 ,…, xn ]
(i = 1,…, m) определяется суперпозиция
H1 : ( Z n )m → Z , входным набором для которой является матрица размера m × n :
X = {xij }im=,1,n j =1 ∈ Z nm . Значение функции определяется следующим образом:
H1 ( X ) = F ( P1 ( x11 ,… x1n ),
P2 ( x21 ,… x2 n ),…, Pm ( xm1 ,… xmn )).
(2)
1.1.1. Предпосылки криптостойкости схемы 1
Ввиду неразрешимости диофантовой
проблемы, при правильном выборе многочленов Pi (i = 1,… m ), F , функция H1
может рассматриваться в качестве односторонней.
Тем не менее стоит отметить, что неудачный выбор диофантова многочлена F
совместно со слабостью некоторых Pi дает
возможность злоумышленнику восстановить часть входного набора функции H1.
1.2. Схема 2
Cхема 2 является модификацией схемы 1, в которой устранена возможность
восстановления части входного набора
односторонней функции вследствие частичной слабости многочлена F .
Аналогично схеме 1, по любому набору
диофантовых многочленов F ∈ Z [ x1 ,…, xm ] ,
Pi ∈ Z [ x1 ,…, xn ]
(i = 1,…, m )
определяется
функция H 2 : ( Z n ) m → Z . Значение функции определяется следующим алгоритмом.
На первом шаге вычисляются значения диофантовых многочленов Pi в точках xi1 ,..., xin и находится их двоичное
представление.
P1 ( x11 ,…, x1n ) = c1
P2 ( x21 ,…, x2 n ) = c2
,
(3)
ci = bi1 + 2bi 2 + …+ 2k −1 bik ,
bij ∈ {0,1}
Pm ( xm1 ,…, xmn ) = cm
где
i = 1,…, m; j = 1,…, k .
Для каждого значения ci соответствующие бинарные векторы могут иметь
разную длину, поэтому выполняется
стандартная процедура выравнивания.
Длина k равна максимальной длине бинарного вектора из найденных векторов
на данном шаге. Если для некоторого
c ∈ {c1 ,…, cm } длина бинарного вектора
меньше k , то вектор дополняется нулями
справа, такое представление однозначно.
Следующим шагом алгоритма является
вычисление входного набора функции F .
Для этого формируется строка чисел, полученных в (3): b11 , b21 ,…, bm1 , b12 ,…, bm 2 ,…,
b1k ,…bmk , которая разбивается на m подстрок по k элементов. Разбиение на подстроки происходит без каких-либо перестановок элементов строго по порядку
следования элементов в начальной строке.
Пусть bi = bi1 ,…bik – i -ая подстрока из
предложенного разбиения. Для каждой
такой подстроки вычисляется
hi = bi1 + 2bi2 + …+ 2k −1 bik (i = 1,…, m) . (4)
Односторонняя функция H 2 определяется как
(5)
H 2 ( X ) = F ( h1' ,…, hm' ) ,
'
'
где последовательность h1 , … , hm является
упорядоченной по возрастанию последовательностью h1 , … , hm .
1.2.1. Предпосылки криптостойкости схемы 2
Пусть для функции F , используемой
в (5), известны значения некоторых hi'
для
определенного
c , такого что
H 2 ( X ) = F ( h1' ,…, hm' ) = c . В отличие от схемы 1, где данной информации достаточно
для попытки нахождения части входного
набора X посредством атаки на соответ-
Схемы построения двушагово односторонних функций
ствующие многочлены
Pi , в данной схеме
такое невозможно.
Для того чтобы перейти к атаке на
многочлены Pi , необходимо преобразовать hi' в соответствующие ci системы
уравнений (3). По построению (4) очевидно, что для нахождения хотя бы одного
ci , для некоторого i , необходимо найти
полное решение уравнения (5).
Стоит заметить, что даже полное решение уравнения (5) недостаточно для
нахождения ci , так как последовательность h1' ,…, hm' является упорядоченной по
возрастанию
последовательностью
h1 ,…, hm . Первоначальный порядок следования
hi неизвестен, из чего следует не-
17
Схема 3 лишена данного недостатка,
теоретически, при выше упомянутых слабостях, можно найти вектор ( xi1 + c2 ,…, xin +
+ c( n mod i −1) +1 ) , но для восстановления вектора ( xi1 ,…, xin ) необходимо решение предыдущих уравнений Pj ( j = 1,…, i − 1) системы (6).
2. Построение двушагово односторонних функций на основе неразрешимости Диофантовой проблемы и
трудности нахождения дискретного
логарфима
Пусть F2r – поле, которое строится
как фактор-кольцо кольца многочленов
Z 2 [ x ] от одной переменной x с коэффициентом из простого поля Z 2 относительf ( x ) , где
обходимость анализа m ! возможных векторов ( c1 ,…, cm ) и соответственно поиск
но неразложимого многочлена
решений m ! систем вида (3) в худшем
случае, что, очевидно, является вычислительно трудной задачей.
x 8 + x 4 + x 3 + x + 1 для r = 8 .
1.3. Схема 3
Схема 3 отличается от схемы 2 системой диофантовых уравнений, использующейся на первом шаге алгоритма вычисления односторонней функции H 2 .
Система уравнений (3) заменяется на следующую систему:
P1 ( x11 ,…, x1n ) = c1
P2 ( x21 + c1 ,…, x2 n + c1 ) = c2
f ( x ) , например, может быть взят равным
2.1. Схема 4
По любому набору диофантовых многочленов Pi ∈ Z [ x1 ,…, xn ] (i = 1,…, m ) определяется функция H 4 : ( Z n ) m → Z с помощью следующего алгоритма.
На первом шаге алгоритма используется система диофантовых уравнений (3)
схемы
2
для
вычисления
вектора
( c1 ,…, cm ) .
m
(6)
Pi ( xi1 + c2 , xi 2 + c3 ,…, xin + c( n mod i −1) +1 ) =
= ci ∀i = 3… m
Все последующие шаги схемы 2 остаются без изменений, замена системы
уравнений не влияет на дальнейшее вычисление функции. Для удобства обозначим
полученную
функцию
как
n m
H3 : (Z ) → Z .
1.3.1. Предпосылки криптостойкости схемы 3
Некоторой слабостью схемы 2 является возможность выполнения атаки на
конкретный многочлен Pi , для нахождения части входного набора. Для этого необходимо рассмотреть m уравнений Pi
с всевозможными правыми частями
ci (i = 1,…, m) (см. 1.2.1).
Затем
вычисляется
∑ ci
g i =1 = b( x ) =
= b0 + b1 ⋅ x + b2 ⋅ x 2 + … + br −1 ⋅ x r −1 , , где g –
порождающий элемент поля F2r , b( x ) –
элемент поля F2r , которому ставится в
соответствие
(b0 , b1 ,…, br −1 ) .
бинарный
вектор
Значение функции H 4 от входного
набора X ∈ Z mn определяется так:
H 4 ( X ) = b0 + b1 ⋅ 2 + b2 ⋅ 22 + …+ br −1 ⋅ 2 r −1. (7)
2.1.1. Предпосылки криптостойкости схемы 4
Криптостойкость данной схемы основана на трудности нахождения дискретного логарифма и проблеме неразрешимости диофантовых уравнений.
Для нахождения входного набора X
необходимо найти решение уравнения
С.Ю. Ерофеев
18
m
∑ ci
g i =1 = b( x ) , то есть найти дискретный логарифм элемента b( x ) по основанию g ,
что является вычислительно трудной задачей.
В случае, если известно число
m
s = ∑ ci , восстановить вектор ( c1 ,…, cm )
i =1
возможно через полный перебор вариантов, что означает в худшем случае перебор
C ss+ m −1
( s + m − 1)!
=
векторов и решеs!⋅(m − 1)!
ние соответствующих систем вида (3).
2.2. Схема 5
Схема 5 отличается от схемы 4 системой диофантовых уравнений, использующихся
для
вычисления
вектора
( c1 ,…, cm ) , и способом вычисления вектора (b0 , b1 ,…, br −1 ) .
Вектор
следующим
(b0 , b1 ,…, br −1 )
выражением:
определяется
g cm = b( x ) =
= b0 + b1 ⋅ x + b2 ⋅ x 2 + … + br −1 ⋅ x r −1 , где cm получена из системы уравнений (6).
Значение функции ( H 5 ) схемы 5 вычисляется по формуле (7).
2.2.2. Предпосылки криптостойкости схемы 5
В данной схеме, в отличие от схемы 4,
при знании дискретного логарифма
cm невозможно проводить атаку на конкретный многочлен
Pi с целью нахожде-
ния части входного наборы функции H 5 .
Так
как
для
решения
уравнения
Pm ( xm1 + c2 , xm2 + c3,…, xmn + c(n mod m−1)+1 ) = cm необходимо полное решение системы (6).
ЛИТЕРАТУРА
[1] Левин Л. А. Односторонние функции // Проблемы передачи информации, 2003. Т. 39.
№ 1.
[2] Матиясевич Ю. В. Диофантовость перечислимых множеств // Докл. АН СССР. 1970.
Т. 191. № 2. С. 279–282.
[3] Матиясевич Ю. В. Диофантово представление перечислимых предикатов // Известия АН
СССР. Серия матем. 1971. Т. 35. С. 3–30.
[4] Davis M. Hilbert’s Tenth Problem is Unsolvable //
Amer. Math. Monthly. 1973. V. 80. № 3. С. 233–
270.
Документ
Категория
Без категории
Просмотров
4
Размер файла
509 Кб
Теги
построение, функции, двушагово, схема, односторонней
1/--страниц
Пожаловаться на содержимое документа