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

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

$\mathrm{\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]$. Очевидно, что при подобных распределениях членов последовательности условие сверхвозрастаемости будет выполняться, так как нижняя граница каждого отрезка в точности равна увеличенной на единицу сумме всех правых границ предыдущих отрезковШаблон:Sfn. Для примера построим таким способом несколько сверхвозрастающих последовательностей при $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\ge 1$ — случайно выбранные числа, то остальные элементы сверхвозрастающей последовательности можно найти из неравенстваШаблон:Sfn:

$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$)Шаблон:Sfn.

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

1. Последовательность удовлетворяет условию сверхвозрастаемости при $s_1<s_2,a\le b$.
2. Последовательность не является сверхвозрастающей при $a>b$.
3. При $s_1>s_2,a\le b$ последовательность начинает удовлетворять условию сверхвозрастаемости после нескольких итераций.
4. При $s_1<s_2,T=\frac{a}{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^{\text{'}}{\}}_1^N$ с помощью набора $\{1,2,2^2,...,2^{N-1}\}$. Для реализации необходимо применить к $\{s_n{\}}_1^N$ набор следующих операцийШаблон:Sfn:

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

$\dots$

$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^{\text{'}}{\}}_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$Шаблон:Sfn.

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

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

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

$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 году. Уникальность схемы состоит в том, что она не только является многосторонней, но и реализует структуру последовательного доступа по уровням. В алгоритме используется схема Шамира, а точнее генерация долей секрета, за которой следует фаза восстановления секретаШаблон:Sfn.

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

Генерация долей секрета Шаблон:Sfn

Шаг 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. В результате получаем новую последовательность: $s{t}^{\text{'}}=\{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}^{\text{'}},s_{l-2}^{\text{'}},s_{l-3}^{\text{'}},...,s_3^{\text{'}},s_2^{\text{'}},s_1^{\text{'}}\}$.

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

Шаг 1.6. Вычисляем сумму $u=bagsum(s{t}^{\text{'}},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\le i\le 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)$.

Фаза восстановления секретаШаблон:Sfn

Шаг 2.1. Как минимум, $t_i$ участников восстанавливают секрет на уровне $i$ и получают долю $w_i$ для $1\le i\le l-1$.

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

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

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

Литература

• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья

Ссылки

• Superincreasing sequences