Сверхвозрастающая последовательность

Сверхвозрастающей называется последовательность, каждый член которой больше суммы всех предыдущих членов. Более формально, последовательность положительных целых чисел $s_{1},s_{2},\dots$ — сверхвозрастающая, если выполнено условие:

$\forall n>1\ :\ s_{n}>\sum _{j=1}^{n-1}s_{j}$

Данный класс последовательностей широко используется в ранцевой криптосистеме Меркля-Хеллмана.

Например, $\{1,3,6,13,27,52\}$ является сверхвозрастающей, а $\{1,3,4,9,15,25\}$ — нет.

Способы построения сверхвозрастающей последовательности

Пусть перед нами стоит задача построить сверхвозрастающую последовательность $\{s_{n}\}_{1}^{N}$ для некоторого количества объектов $N$. Элемент $s_{1}$ выбирается случайным образом из равномерного распределения натуральных чисел по такому отрезку: $[1,2^{N}]$. Следующий элемент $s_{2}$ выбирается равномерно из отрезка $[1\cdot 2^{N}+1,2\cdot 2^{N}]$, идущий за ним член последовательности выбирается из отрезка $[3\cdot 2^{N}+1,4\cdot 2^{N}]$, элемент $s_{n}$ случайным образом выбирается из отрезка $[(2^{n-1}-1)\cdot 2^{N}+1,2^{n-1}\cdot 2^{N}]$. Очевидно, что при подобных распределениях членов последовательности условие сверхвозрастаемости будет выполняться, так как нижняя граница каждого отрезка в точности равна увеличенной на единицу сумме всех правых границ предыдущих отрезков. Для примера построим таким способом несколько сверхвозрастающих последовательностей при $N=5$:

n	Отрезок	Пример 1	Пример 2	Пример 3
1	$[1,32]$	5	10	32
2	$[33,64]$	56	49	64
3	$[97,128]$	98	113	97
4	$[225,256]$	225	225	225
5	$[481,512]$	481	510	493

Построение со случайно выбранным шагом

Если $h,s_{1}\geq 1$ — случайно выбранные числа, то остальные элементы сверхвозрастающей последовательности можно найти из неравенства:

$s_{n}>h+\sum _{j=1}^{n-1}s_{j}$

Пусть $h=10$, $s_{1}=9$. Тогда, для примера, последовательность $\{9,20,52,100,192\}$ удовлетворяет условию и является сверхвозрастающей.

Построение на основе последовательности Фибоначчи

Основная статья: Числа Фибоначчи

Каждый элемент последовательности Фибоначчи удовлетворяет соотношению: $u_{n+1}=u_{n}+u_{n-1}$, нулевой и первый члены которого: $u_{0}=0,u_{1}=1$. Из этого видно, что первые члены последовательности Фибоначчи: $\{0,1,1,2,3,5,8,13,21,34,55,89,...\}$. Иногда можно столкнуться с обобщенной последовательностью Фибоначчи. Это последовательность, члены которой выполняют условие уравнения: $u_{n+1}=a\cdot u_{n}+b\cdot u_{n-1}$. То есть обобщённая последовательность получается из классической путем изменения первых двух членов последовательности Фибоначчи и сохраняет принцип образования следующих членов. Для построения сверхвозрастающей последовательности используется форма именно обобщённой последовательности Фибоначчи. Для того, чтобы вычислить любой член сверхвозрастающей последовательности $\{s_{n}\}_{1}^{N}$, необходимо выбрать четыре элемента: два начальных ($s_{1}$ и $s_{2}$) и два положительных множителя ($a$ и $b$).

Получаем следующие случаи:

1. Последовательность удовлетворяет условию сверхвозрастаемости при $s_{1}<s_{2},a\leq b$.
2. Последовательность не является сверхвозрастающей при $a>b$.
3. При $s_{1}>s_{2},a\leq b$ последовательность начинает удовлетворять условию сверхвозрастаемости после нескольких итераций.
4. При $s_{1}<s_{2},T={a \over b}<0.669$ последовательность остаётся сверхвозрастающей.

Для примера возьмём $s_{1}=2,s_{2}=3,a=5,b=7$. Первые элементы полученной сверхвозрастающей последовательности: $\{2,3,5\cdot 3+7\cdot 2,5\cdot 29+7\cdot 3,5\cdot 166+7\cdot 29\}=\{2,3,29,166\}$.

Построение по имеющейся сверхвозрастающей последовательности

Условию сверхроста удовлетворяет ряд степеней числа $2$ . Зная сверхвозрастающую последовательность $\{s_{n}\}_{1}^{N}$, можно построить новую $\{s_{n}^{'}\}_{1}^{N}$ с помощью набора $\{1,2,2^{2},...,2^{N-1}\}$. Для реализации необходимо применить к $\{s_{n}\}_{1}^{N}$ набор следующих операций:

$n=1:\{s_{1}+1,s_{2}+1,s_{3}+2,...,s_{N-1}+2^{N-3},s_{N}+2^{N-2}}\$

$\ldots$

$n=k:\{s_{1},s_{2},s_{3},...,s_{k}+1,s_{k+1}+1,...,s_{N-1}+2^{N-k-2},s_{N}+2^{N-k-1}}\$

$...$

$n=N-1:\{s_{1},s_{2},s_{3},...,s_{N-1}+1,s_{N}+1}\$

$n=N:\{s_{1},s_{2},s_{3},...,s_{N-1},s_{N}+1}\$

Подробный пример для выбранной сверхвозрастающей последовательности $\{3,6,13,27,52,105\}$:

	$s_{1}$	$s_{2}$	$s_{3}$	$s_{4}$	$s_{5}$	$s_{6}$
	$3$	$6$	$13$	$27$	$52$	$105$
$n=1$	$3+1=4$	$6+1=7$	$13+2=15$	$27+2^{2}=31$	$52+2^{3}=60$	$105+2^{4}=121$
$n=2$	$4$	$7+1=8$	$15+1=16$	$31+2=33$	$60+2^{2}=64$	$121+2^{3}=129$
$n=3$	$4$	$8$	$16+1=17$	$33+1=34$	$64+2=66$	$129+2^{2}=133$
$n=4$	$4$	$8$	$17$	$34+1=35$	$66+1=67$	$133+2=135$
$n=5$	$4$	$8$	$17$	$35$	$67+1=68$	$135+1=136$
$n=6$	$4$	$8$	$17$	$35$	$68$	$136+1=137$

Получили новую сверхвозрастающую последовательность $\{s_{n}^{'}\}_{1}^{N}=\{4,8,17,35,68,137\}$.

Использование сверхвозрастающей последовательности в криптографии

Сверхвозрастающие рюкзаки

Основная статья: Задача о рюкзаке в криптографии

Криптосистема Меркла-Хеллмана основан на «задаче о рюкзаке» — алгоритме шифрования с открытым ключом — описанном ниже. Задача выглядит следующим образом: задана последовательность $\{a_{n}\}_{1}^{N}$ неповторяющихся положительных целых чисел. Пусть число $k$ также принадлежит множеству натуральных чисел. Если такое возможно, необходимо найти набор псевдослучайной двоичной последовательности $\{b_{n}\}_{1}^{N}$, чтобы выполнялось условие: $k=b_{1}a_{1}+b_{2}a_{2}+...+b_{n}a_{n}$.

Пусть $\{a_{n}\}_{1}^{N}$ — сверхвозрастающая последовательность. В таком случае мы сталкиваемся с «лёгкой» проблемой рюкзака, которую не составляет труда решить. Для этого $k$ сравнивается с элементом $a_{n}$. Если $k\geq a_{n}$, то $b_{n}=1$, значение $k$ уменьшается на $a_{n}$ и происходит переход к члену последовательности $a_{n-1}$. Действие повторяется, пока процесс не закончится. Если в итоге $k=0$, то решение задачи найдено в виде последовательности $\{b_{n}\}_{1}^{N}$, в противном случае — его не существует.

Если последовательность $\{a_{n}\}_{1}^{N}$ не сверхвозрастающая (или нормальная), то рюкзаки представляют собой «трудную» проблему, решить которую можно только перебором всех возможных вариантов.

Закрытый ключ в алгоритме Меркла-Хеллмана — это последовательность весов проблемы сверхвозрастающего рюкзака, в свою очередь открытый ключ — это последовательность весов проблемы нормального рюкзака с тем же решением. Существует способ преобразования проблемы сверхвозрастающего рюкзака в проблему нормального рюкзака посредством модульной арифметики. Для того, чтобы получить нормальную последовательность рюкзака, будем использовать сверхвозрастающую последовательность рюкзака. Для примера возьмём последовательность чисел: $\{2,3,7,13,27,61\}$, и умножим по модулю $m$ каждый элемент этой последовательности на число $n$. На $m$ накладывается условие: значение модуля должно быть больше суммы всех элементов последовательности, например, $m=115$. А множитель $n$ должен быть взаимно простым числом с модулем, например, $n=31$. В таком случае нормальной последовательностью рюкзака будет:

$2\cdot 31mod115=62;$

$3\cdot 31mod115=93;$

$7\cdot 31mod115=102;$

$13\cdot 31mod115=58;$

$27\cdot 31mod115=32;$

$61\cdot 31mod115=51.$

Получаем нормальную последовательность чисел: $\{62,93,102,58,32,51\}$. Сверхвозрастающая последовательность рюкзака является закрытым ключом, а нормальная последовательность рюкзака — открытым.

Схема многостороннего разделение секрета

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

Приведём алгоритм реализации схемы многостороннего разделения секрета.

Генерация долей секрета

Шаг 1.1. Выбирается секрет $s\in \mathbb {Z} _{p}-\{0\}$, где $p$ — некоторое простое число, которое известное всем сторонам и задаёт конечное поле размера $p$. Пусть $p=2^{l-1}$, где $l$ — количество участников, между которыми нужно разделить секрет $s$.

Шаг 1.2. Преобразуем секрет $s$ в $(l-1)$-битную псевдослучайную двоичную систему счисления и сформируем последовательность $st=\{s_{l-1},s_{l-2},s_{l-3},...,s_{3},s_{2},s_{1}\}$.

Шаг 1.3. Составим двоичную последовательность длиной $l-1$ из случайно подобранных элементов: $\{e_{l-1},e_{l-2},e_{l-3},...,e_{3},e_{2},e_{1}\}$.

Шаг 1.4. Используем операцию исключающее «ИЛИ» между элементами последовательностей из Шага 1.2 и Шага 1.3. В результате получаем новую последовательность: $st^{'}=\{s_{l-1}\oplus e_{l-1},s_{l-2}\oplus e_{l-2},s_{l-3}\oplus e_{l-3},...,s_{3}\oplus e_{3},s_{2}\oplus e_{2},s_{1}\oplus e_{1}\}=\{s_{l-1}^{'},s_{l-2}^{'},s_{l-3}^{'},...,s_{3}^{'},s_{2}^{'},s_{1}^{'}\}$.

Шаг 1.5. Построим сверхвозрастающую последовательность случайных чисел длиной $l-1$: $w=\{w_{l-1},w_{l-2},w_{l-3},...,w_{3},w_{2},w_{1}\}$.

Шаг 1.6. Вычисляем сумму $u=bagsum(st^{'},w)$, которая будет известна всем участникам. Псевдокод функции:

   Function bugsum(a, b);
   Input: $a=\{a_{1},...,a_{r}}\$ и $b=\{b_{1},...,b_{r}\}$.
   Output: sum.
   sum$\leftarrow 0$;
   for i $\in$ r do
        sum $\leftarrow$ sum $+$ $a_{i}\times b_{i}$;
   end
   return sum;

Шаг 1.7. Выбираем простое число $q$, которое будет объявлено всем участникам, и такое, что: $w_{1}+w_{2}+w_{3}+...+w_{l-1}<q$ и $\max(n_{i})$ для $1\leq i\leq l$, где $i-$число уровней, а $n_{i}-$общее количество участников на уровне $i$.

Шаг 1.8. Распределяем $w_{i}$ среди всех участников уровня $i$ с помощью $(t_{i},n_{i})$, где $t_{i}<n_{i}$определяет степень многочлена $F(x)$ схемы Шамира на уровне $i$. Далее необходимо перевести в десятичную систему элементы последовательности Шага 1.3 и также распределить их по уровню $l$ с помощью $(t_{l},n_{l})$.

Фаза восстановления секрета

Шаг 2.1. Как минимум, $t_{i}$ участников восстанавливают секрет на уровне $i$ и получают долю $w_{i}$ для $1\leq i\leq l-1$.

Шаг 2.2. На первом уровне проверяется, действительно ли выполняется $u\geq w_{1}$ для суммы, полученной на Шаге 1.6. Если неравенство верно, первый уровень выводит $1$ и отправляет на второй уровень новое значение суммы: $u_{1,2}^{'}=u-w_{1}$. В противном случае он выводит $0$ и отправляет на следующий уровень $u_{1,2}^{'}=u$ и добавляет свой выходной бит $0$ в пустую последовательность $st^{''}$. Необходимо пройти все уровни, постепенно заполняя последовательность $st^{''}$.

Шаг 2.3. На уровне $l$ выполняется восстановление секрета и заполнение последовательности $\{e_{l-1}^{'},e_{l-2}^{'},e_{l-3}^{'},...,e_{3}^{'},e_{2}^{'},e_{1}^{'}\}$. Повторяем вычисления, которые проводились на Шаге 1.4 с операцией исключающее «ИЛИ»: $st=\{e_{l-1}^{'}\oplus s_{l-1}^{'},e_{l-2}^{'}\oplus s_{l-2}^{'},e_{l-3}^{'}\oplus s_{l-3}^{'},...,e_{3}^{'}\oplus s_{3}^{'},e_{2}^{'}\oplus s_{2}^{'},e_{1}^{'}\oplus s_{1}^{'}\}$.

Шаг 2.4. Наконец, получили секретную двоичную последовательность, которую можно преобразовать в десятичную, чтобы получить секрет $s$.

Литература

• Bruce Schneier. Applied Cryptography: Protocols, Algorithms, and Source Code in C. — 1993. — С. 463—465. — ISBN 978-0471117094.
• Merkle R.C. and Hellman M.E. Trapdoor knapsack. — 1978. — С. 525—526.
• Salomaa A. Public-Key Cryptography. — 1995.
• A. Merzouga, A. Ali-Pachab, N. Hadj-Saidb, H. Ali-Pachab. Production of a Super-Increasing Sequence based on the Fibonaci Sequence. — 2019.
• P. Harsha, P. Chanakya, and Vadlamudi China Venkaiah. A Reusable Multipartite Secret Sharing Scheme Based on Superincreasing Sequence. — 2017.
• A. Basit, P. Chanakya, V. Ch. Venkaiah and S. Abdul Moiz. New multi-secret sharing scheme based on superincreasing sequence for level-ordered access structure. — 2020.
• Мурин Д. М. О порядке роста числа инъективных и сверхрастущих рюкзачных векторов. — 2011.

Ссылки

• Superincreasing sequences