close

Вход

Забыли?

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

?

Мультипликативная рюкзачная криптосистема.

код для вставкиСкачать
МАТЕМАТИКА
Вестн. Ом. ун-та. 2011. № 4. С. 23–25.
УДК 512.53
Т.Н. Шевляков
МУЛЬТИПЛИКАТИВНАЯ
РЮКЗАЧНАЯ КРИПТОСИСТЕМА
Представлен новый вариант криптосистемы, основанной на задаче о мультипликативном рюкзаке. Предложено свойство, обобщающее супервозрастание в случае
последовательности элементов из Ζ + n .
Ключевые слова: мультипликативный рюкзак, диагональное супервозрастание, рюкзачная криптосистема.
Задача о мультипликативном рюкзаке.
Под задачей о мультипликативном рюкзаке будем понимать следующее. Пусть дан набор весов
B = {b1 , b2 ,… bk }, bi ∈ Ζ + ,
и вес рюкзака
Π ∈ Ζ+ ,
где через обозначено Ζ + множество всех положительных целых чисел.
Необходимо найти такой вектор x = {x1 , x2 ,… xk }, xi ∈ {0,1} , что
k
k
Π = ∏ bixi .
i =1
Заметим, что эта задача является интерпретацией «Subset product
problem»:
«Дано конечное множество A ⊂ Ζ + и B ∈ Ζ + . Существует ли подмножество A' ⊂ A такое, что B =
a ?».
∏
a∈A'
«Subset product problem» является NP-трудной задачей [1].
Чтобы построить криптосистему, основанную на задаче о мультипликативном рюкзаке, необходимо выполнить следующие условия:
1) найти свойство P для набора весов B такое, что задача нахождения вектора x ∈ {0,1} будет простой.
k
2) найти преобразование ϕ , которое будет скрывать свойство P
для набора весов B .
Свойство P.
Воспользуемся идеей супервозрастающей последовательности.
Рассмотрим набор A = {α1 , α 2 ,…α k }, α i ∈ Ζ + n :
α1 = {α11 ,α12 ,α13 ,…α1n },
α 2 = {α 21 ,α 22 ,α 23 ,…α 2 n },
α k = {α k 1 ,α k 2 ,α k 3 ,…α kn },
© Т.Н. Шевляков, 2011
Т.Н. Шевляков
24
α5,2 = 6 > α1,2 + α 2,2 + α 3,2 + α 4,2 = 5
α ij ∈ Z + .
Пусть n ≥ k , и числа α ij удовлетворяют следующему свойству:
1
i =1
2
i =1
α 7,1 = 14 > α1,1 + α 2,1 + α 3,1 + α 4,1 + α5,1 + α 6,1 = 12
Для набора весов A , обладающего
свойством P, выполнено следующее
Свойство 1. Задача нахождения век-
α 2,2 > ∑αi ,2 ,
α 3,3 > ∑αi ,3 ,
α 6,3 = 21 > α1,3 + α 2,3 + α 4,3 + α5,3 = 19
(1)
тора x ∈ {0,1}
k
такого, что S =
k
∑ xα ,
i =1
k −1
α k ,k > ∑ α i ,k .
i =1
Если n < k , то разобьем набор A на
⎡k ⎤
r = ⎢ ⎥ + 1 поднаборов:
⎣n⎦
A1 = {α1 ,…, α n },
A2 = {α n +1 ,…, α 2 n },
Ar = {α ( r −1) n +1 ,…, α k },
n
α n +1,1 > ∑αi ,1 ,
i =1
rn
α ( r −1) n +1,1 > ∑αi ,1.
i =1
Таким образом, мощность каждого из
этих множеств меньше или равна n. Теперь на эти наборы можно перенести определенное выше свойство.
Определение 1. Назовем свойство P
диагональным супервозрастанием. Элементы, стоящие в левых частях неравенств (1), будем называть суперэлементами.
Пример 1.
простой.
Доказательство. Сразу оговоримся,
что решение задачи существует, необходимо только найти его. Заметим, что
∀α i ∃j : α i , j
является
супер-элементом.
Пусть σ = {i1 ,…, ik }, i j ∈ 1,2,…, n – набор индексов таких, что α1,i1 , α 2,i2 ,…, α k ,ik являются супер-элементами.
Поиск вектора x сформулируем в виде следующего алгоритма:
Вход: множество A , множество σ ,
вектор S
Выход: вектор x
Алгоритм:
Будем последовательно перебирать
все α j ∈ A , начиная с последнего. Если
α ji ≤ si ,
j
S ← S −α j, xj ←1,
то
j
Свойство доказано.
Свойство
2.
Для
α 7,1 = 14,α 7,2 = 14,α 7,3 = 5
α 2,2 = 2 > α1,2 = 1
α 3,3 = 5 > α1,3 + α 2,3 = 4
α 4,1 = 6 > α1,1 + α 2,1 + α 3,1 = 4
различных
x, y ∈ {0,1}
k
k
k
i =1
i =1
∑ xiαi ≠ ∑ yiαi .
Доказательство. Предположим противное. То есть
k
k
∑xα = ∑ yα ,
i
i =1
i
k
∑(x
α 3,1 = 1,α 3,2 = 1,α 3,3 = 5
α 6,1 = 1,α 6,2 = 1,α 6,3 = 21
иначе
x j ← 0 . Переходим к следующему α j −1.
α 2,1 = 2,α 2,2 = 2,α 2,3 = 1
α5,1 = 1,α5,2 = 6,α5,3 = 3
для
некоторого S = {s1 , s2 ,…, sn } ∈ Z + n , является
α1,1 = 1,α1,2 = 1, α1,3 = 3
α 4,1 = 6,α 4,2 = 1,α 4,3 = 7
i
i
i =1
i
i =1
i
− yi )α i = 0.
(2)
Сформируем три множества индексов: σ + , σ − , σ 0 таких что
∀i ∈ σ + ( xi − yi ) = 1,
∀i ∈ σ − ( xi − yi ) = −1,
∀i ∈ σ 0 ( xi − yi ) = 0.
Предположение (2) эквивалентно равенству
k
k
∑σ x α − ∑σ x α
i∈
i
+
i
i∈
i
−
i
= 0.
Мультипликативная рюкзачная криптосистема
25
Обозначим imax максимальный индекс
bi' = bπ ( i ) . {P, A, π } – закрытый ключ шиф-
среди σ − , σ + (пусть imax ∈ σ + ), тогда α imax ,s –
это супер-элемент. Из (3) следует, в частности, что
∑α
i∈σ +
i ,s
αi
max , s
αi
− ∑ α i ,s = 0,
+
max , s
i∈σ −
α
∑
σ
i∈ +
i ≠imax
=
i ,s
∑α
i∈σ −
− ∑ αi ,s = 0,
'
B
A ←⎯
⎯ B.
2. Пользователь А вычисляет вес рюк-
i∈σ −
i ,s
−
∑α
i∈σ +
i ≠imax
i ,s
<
∑α
i∈σ −
i ,s
<
∑α
i =1
i ,s
, (4)
{
}
Таким образом, B ' = bi1 , bi2 ,…, bik .
Описание криптосистемы
Рассмотрим задачу о мультипликативном рюкзаке. Есть набор весов
B = {b1 , b2 ,…, bk } ,
bi ∈ Z + . Справедливо
n
bi = ∏ p j ,
αij
(5)
j =1
где p j – простые числа, α ij ∈ Ν ∪ {0} .
Установка:
Выберем
n
k
Π = ∏ bi' mi .
i =1
3. Пользователь А передает вычисленный вес рюкзака пользователю В
Π
A ⎯⎯
→ B.
4. Пользователь В решает задачу о
мультипликативном рюкзаке, решением
которой является сообщение m.
k
k
i =1
i =1
Π = ∏ bi' xi = ∏ bi π
x
простых
чисел
P = { p1 , p2 ,…, pn } и набор из k векторов
A = {α1 , α 2 ,…, α k }, α i ∈ Z + n ,
обладающий
свойством диагонального супервозрастания. Построим набор весов B = {b1, b2 ,…, bk }
Выберем
перестановку
π : {1, 2,… , k } → {i1 , i2 ,…ik } . B = {b1' , b2' ,…, bk' },
'
−1 ( i )
.
Пусть yi = xπ −1 ( i ) . С одной стороны,
k
Π = ∏ piβi ,
i =1
а с другой –
k
k
n
i =1
i =1
∑ y jα ji
Π = ∏ biyi = ∏ pij =1
представление
(5).
зака Π. m = {m1 ,…, mk } ∈ {0,1} – сообщение.
k
imax −1
что противоречит определению суперэлемента.
Свойство доказано.
Свойство 3. Супервозрастание для
набора весов из Z является частным случаем диагонального супервозрастания.
Преобразование ϕ .
В качестве преобразования возьмем
перестановку
π : {1,2,…, k } → {i1 , i2 ,…ik } .
вида
рования. B ' – открытый ключ шифрования.
Передача сообщения:
1. Пользователь А запрашивает у
пользователя В открытый ключ:
.
Теперь пользователю В необходимо
решить задачу, описанную в (Свойстве 1).
B знает закрытый ключ шифрования и
все супер-элементы в множестве A. Поэтому он легко решает эту задачу, находя
таким образом сообщение m.
ЛИТЕРАТУРА
[1] Karp R. M. Reducibility Among Combinatorial
Problems // Complexity of Computer Computations (Ed. R. E. Miller and J.W. Thatcher). New
York : Plenum Press, 1972. Р. 85–103.
Документ
Категория
Без категории
Просмотров
5
Размер файла
539 Кб
Теги
криптосистем, рюкзачная, мультипликативный
1/--страниц
Пожаловаться на содержимое документа