Шифрование на основе рюкзачной системы

1.

Шифрование на основе
рюкзачной системы
НИКИТЕНКО В.К., 4ПМ
Г. МАЙКОП, 2023

2.

История
Задач о рюкзаке в криптографии — это
задача, на основе которой американские
криптографы Ральф Меркл и Мартин
Хеллман разработали первый алгоритм
шифрования с открытым ключом. Он
носит название криптосистема МерклаХеллмана.
Для шифрования сообщений
использовалось решение задачи о рюкзаке.

3.

Шифрование с открытым ключом
Один ключ сообщает вам, как зашифровать сообщение, и он является
«общедоступным», поэтому любой может его использовать.
Другой ключ позволяет расшифровать сообщение. Этот код дешифрования
хранится в секрете, поэтому только человек, знающий ключ, может расшифровать
сообщение.

4.

Формулировка
задачи о
рюкзаке
Задан набор (рюкзачный вектор) A = (a0,
a1, ..., an ) — это упорядоченный набор из
n (n > 2) различных натуральных чисел ai.
Пусть есть число k — целое и
положительное. Задачей является
нахождение такого набора ai, чтобы в
сумме они давали ровно k.

5.

Почему задача о "рюкзаке"?
В самом простом случае k обозначает размер (вместительность)
рюкзака, а каждое из чисел ai указывает размер (вес) предмета,
который может быть упакован в рюкзак. Задачей является
нахождение такого набора предметов, чтобы рюкзак был полностью
заполнен.

6.

Почему задача о
"рюкзаке"?
Например, у вас есть набор гирь 1, 6, 8, 15
и 24, вам нужно упаковать рюкзак весом
30.

7.

Мультипликативный способ шифрования
Шифр сообщения получается, если возвести элементы данного рюкзачного вектора в
степень соответствующих им бит шифруемого сообщения и далее перемножить все
результаты, то есть если A = (2, 3, 5), а сообщение (100), то шифром будет число 21 *
30 * 50 = 2.

8.

Аддитивный способ шифрования
Шифр сообщения получается, если умножить элементы данного рюкзачного вектора
на соответствующие им биты шифруемого сообщения и далее просуммировать все
результаты, то есть если A = (2,3,5), а сообщение (100), то шифром будет число 2 * 1
+ 3 * 0 + 5 * 0 = 2.

9.

Пример шифрования
Для шифрования открытого текста в двоичном представлении его разбивают на
блоки длины n. Считается, что единица указывает на наличие предмета в рюкзаке,
а ноль на его отсутствие.

10.

"Легкая" проблема
Для сверхрастущих* векторов Α задача о рюкзаке легко решаема, т.е. рюкзак собрать
несложно.
*Рюкзачный вектор A = (a0, a1, ..., an ) называется сверхрастущим, если каждый член последовательности больше
суммы предыдущих.

11.

Алгоритм решения
"легкой" проблемы
Общий вес ранца сравнить с наибольшим весом в
последовательности.
Если общий вес меньше числа, значит, в рюкзаке его
нет. Если общий вес больше числа, он в рюкзаке.
Вычесть число из общей суммы и сравните со
следующим по величине числом.
Повторить (1)-(2) пока общая сумма не достигнет нуля.
Если сумма не достигает нуля, то решения нет.

12.

"Трудная" проблема
Создатель криптосистемы выбирает такую систему A, t, m, B, что
вектор A является сверхрастущим, а B получается из A
модульным умножением относительно m и t, где m > max A, t –
целое, не имеет общих множителей с m. Вектор B раскрывается
как ключ зашифpования и двоичные блоки длины n посылаются
к проектировщику как числа, полученные с помощью вектора B.

13.

Пример решения задачи
Возьмём сверхрастущую последовательность A - например, {1, 2, 4, 10, 20, 40}.
Модуль m должен быть больше суммы всех чисел в последовательности, например
110. Множитель t не должен иметь общих делителей с модулем - выберем 31.

14.

Пример

15.

Пример

16.

Пример

17.

Спасибо за
внимание!