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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

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

Например, является сверхвозрастающей, а  — нет.

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

Пусть перед нами стоит задача построить сверхвозрастающую последовательность для некоторого количества объектов . Элемент выбирается случайным образом из равномерного распределения натуральных чисел по такому отрезку: . Следующий элемент выбирается равномерно из отрезка , идущий за ним член последовательности выбирается из отрезка , элемент случайным образом выбирается из отрезка . Очевидно, что при подобных распределениях членов последовательности условие сверхвозрастаемости будет выполняться, так как нижняя граница каждого отрезка в точности равна увеличенной на единицу сумме всех правых границ предыдущих отрезков[3]. Для примера построим таким способом несколько сверхвозрастающих последовательностей при :

n Отрезок Пример 1 Пример 2 Пример 3
1 5 10 32
2 56 49 64
3 98 113 97
4 225 225 225
5 481 510 493

Построение со случайно выбранным шагом[править | править код]

Если  — случайно выбранные числа, то остальные элементы сверхвозрастающей последовательности можно найти из неравенста[4]:

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

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

Каждый элемент последовательности Фибоначчи удовлетворяет соотношению: , нулевой и первый члены которого: . Из этого видно, что первые члены последовательности Фибоначчи: . Иногда можно столкнуться с обобщенной последовательностью Фибоначчи. Это последовательность, члены которой выполняют условие уравнения: . То есть обобщённая последовательность получается из классической путем изменения первых двух членов последовательности Фибоначчи и сохраняет принцип образования следующих членов. Для построения сверхвозрастающей последовательности используется форма именно обобщённой последовательности Фибоначчи. Для того, чтобы вычислить любой член сверхвозрастающей последовательности , необходимо выбрать четыре элемента: два начальных ( и ) и два положительных множителя ( и )[5].

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

  1. Последовательность удовлетворяет условию сверхвозрастаемости при .
  2. Последовательность не является сверхвозрастающей при .
  3. При последовательность начинает удовлетворять условию сверхвозрастаемости после нескольких итераций.
  4. При последовательность остаётся сверхвозрастающей.

Для примера возьмём . Первые элементы полученной сверхвозрастающей последовательности: .

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

Условию сверхроста удовлетворяет ряд степеней числа . Зная сверхвозрастающую последовательность , можно построить новую с помощью набора . Для реализации необходимо применить к набор следующих операций[6]:

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

Получили новую сверхвозрастающую последовательность .

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

Сверхвозрастающие рюкзаки[править | править код]

Криптосистема Меркла-Хеллмана основан на «задаче о рюкзаке» — алгоритме шифрования с открытым ключом — описанном ниже. Задача выглядит следующим образом: задана последовательность неповторяющихся положительных целых чисел. Пусть число также принадлежит множеству натуральных чисел. Если такое возможно, необходимо найти набор псевдослучайной двоичной последовательности , чтобы выполнялось условие: [2].

Пусть  — сверхвозрастающая последовательность. В таком случае мы сталкиваемся с «лёгкой» проблемой рюкзака, которую не составляет труда решить. Для этого сравнивается с элементом . Если , то , значение уменьшается на и происходит переход к члену последовательности . Действие повторяется, пока процесс не закончится. Если в итоге , то решение задачи найдено в виде последовательности , в противном случае — его не существует[2].

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

Закрытый ключ в алгоритме Меркла-Хеллмана — это последовательность весов проблемы сверхвозрастающего рюкзака, в свою очередь открытый ключ — это последовательность весов проблемы нормального рюкзака с тем же решением. Существует способ преобразования проблемы сверхвозрастающего рюкзака в проблему нормального рюкзака посредством модульной арифметики. Для того, чтобы получить нормальную последовательность рюкзака, будем использовать сверхвозрастающую последовательность рюкзака. Для примера возьмём последовательность чисел: , и умножим по модулю каждый элемент этой последовательности на число . На накладывается условие: значение модуля должно быть больше суммы всех элементов последовательности, например, . А множитель должен быть взаимно простым числом с модулем, например, . В таком случае нормальной последовательностью рюкзака будет[2]:

Получаем нормальную последовательность чисел: . Сверхвозрастающая последовательность рюкзака является закрытым ключом, а нормальная последовательность рюкзака — открытым.

Схема многостороннего разделение секрета[править | править код]

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

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

Генерация долей секрета [8][править | править код]

Шаг 1.1. Выбирается секрет , где  — некоторое простое число, которое известное всем сторонам и задаёт конечное поле размера . Пусть , где  — количество участников, между которыми нужно разделить секрет .

Шаг 1.2. Преобразуем секрет в -битную псевдослучайную двоичную систему счисления и сформируем последовательность .

Шаг 1.3. Составим двоичную последовательность длиной из случайно подобранных элементов: .

Шаг 1.4. Используем операцию исключающее «ИЛИ» между элементами последовательностей из Шага 1.2 и Шага 1.3. В результате получаем новую последовательность: .

Шаг 1.5. Построим сверхвозрастающую последовательность случайных чисел длиной : .

Шаг 1.6. Вычисляем сумму , которая будет известна всем участникам. Псевдокод функции:

   Function bugsum(a, b);
   Input:  и .
   Output: sum.
   sum;
   for i  r do
        sum  sum  ;
   end
   return sum;

Шаг 1.7. Выбираем простое число , которое будет объявлено всем участникам, и такое, что: и для , где число уровней, а общее количество участников на уровне .

Шаг 1.8. Распределяем среди всех участников уровня с помощью , где определяет степень многочлена схемы Шамира на уровне . Далее необходимо перевести в десятичную систему элементы последовательности Шага 1.3 и также распределить их по уровню с помощью .

Фаза восстановления секрета[8][править | править код]

Шаг 2.1. Как минимум, участников восстанавливают секрет на уровне и получают долю для .

Шаг 2.2. На первом уровне проверяется, действительно ли выполняется для суммы, полученной на Шаге 1.6. Если неравенство верно, первый уровень выводит и отправляет на второй уровень новое значение суммы: . В противном случае он выводит и отправляет на следующий уровень и добавляет свой выходной бит в пустую последовательность . Необходимо пройти все уровни, постепенно заполняя последовательность .

Шаг 2.3. На уровне выполняется восстановление секрета и заполнение последовательности . Повторяем вычисления, которые проводились на Шаге 1.4 с операцией исключающее «ИЛИ»: .

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

Примечания[править | править код]

  1. Richard A. Mollin, An Introduction to Cryptography (Discrete Mathematical & Applications), Chapman & Hall/CRC; 1 edition (August 10, 2000), ISBN 1-58488-127-5
  2. 1 2 3 4 Schneier, 1993.
  3. Merkle, Hellman, 1978.
  4. Salomaa, 1995.
  5. Merzouga, Ali-Pachab, Hadj-Saidb, Ali-Pachab, 2019.
  6. Мурин, 2011.
  7. Basit, Chanakya, Venkaiah, Abdul Moiz, 2020.
  8. 1 2 Harsha, Chanakya, Vadlamudi China Venkaiah, 2017.

Литература[править | править код]

Ссылки[править | править код]