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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle \ldots }$

${\displaystyle 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}}\}$

${\displaystyle ...}$

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

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

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

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

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

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

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

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

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

${\displaystyle 2\cdot 31mod115=62;}$

${\displaystyle 3\cdot 31mod115=93;}$

${\displaystyle 7\cdot 31mod115=102;}$

${\displaystyle 13\cdot 31mod115=58;}$

${\displaystyle 27\cdot 31mod115=32;}$

${\displaystyle 61\cdot 31mod115=51.}$

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

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

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

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

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

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

Шаг 1.4. Используем операцию исключающее «ИЛИ» между элементами последовательностей из Шага 1.2 и Шага 1.3. В результате получаем новую последовательность: ${\displaystyle 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. Построим сверхвозрастающую последовательность случайных чисел длиной ${\displaystyle l-1}$: ${\displaystyle w=\{w_{l-1},w_{l-2},w_{l-3},...,w_{3},w_{2},w_{1}\}}$.

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

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

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

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

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

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

Шаг 2.3. На уровне ${\displaystyle l}$ выполняется восстановление секрета и заполнение последовательности ${\displaystyle \{e_{l-1}^{'},e_{l-2}^{'},e_{l-3}^{'},...,e_{3}^{'},e_{2}^{'},e_{1}^{'}\}}$. Повторяем вычисления, которые проводились на Шаге 1.4 с операцией исключающее «ИЛИ»: ${\displaystyle 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. Наконец, получили секретную двоичную последовательность, которую можно преобразовать в десятичную, чтобы получить секрет ${\displaystyle 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