Математическая основа криптографических систем с открытым ключом

Системы шифрования с симметричным ключом имеют существенный недостаток. Если ключ и сообщение эквивалентны по длине, то возникает вопрос,не проще ли отправить сообщение по секретной почте. Был разработан математический аппарат для шифрования с открытым распределением ключей. Идея метода основана на использовании односторонних математических функций. Это такие функции, когда по аргументу х легко вычислить f(x), когда известно f(x) , то х найти сложно.

1. Выбираем одностороннюю математическую функцию такую, что по х-f(x) легко найти, а f(x) по x сложно. Функцию f(x) объявляем открытой.

2. Находится такая подзадача для этой односторонней функции, для которой значения х по f(x) определяется легко

3. Значения открытого ключа (f(x)) перемешиваются так, чтобы для криптоаналитика она выглядела труднорешимой. Для легального получения используем способ приведения к легкой подзадаче

Показательным примером являются «рюкзачные» криптосистемы.

А=(a₁,a₂,a_n) a_i – целые положительные числа

Нам известно k

Задача состоит в том, чтобы среди элементов вектора A_i выбрать такие суммы, которые будут равняться k=∑ a_i , i=n

Например

k=3231

А(43,129,215,473,903,302,561,1165,697,1523)

Методом перебора определяем 129+473+903+561+1165=3231

В=(0,1,0,1,1,1,0,1,1,0,0) A*B=k S_m=k₁, k₂…k_m

Под задачей имеющей однозначное обратное решение понимается сверхрастущий вектор (каждый последующий элемент больше суммы всех предыдущих). Для сверхрастущего вектора и рюкзака k существует однозначный алгоритм нахождения столбца В. Такого, что А*В=k

Рюкзачные криптосистемы

Проблема рюкзака" (или "ранца") может быть сформулирована следующим образом. Пусть задано множество натуральных чисел А = (a₁, а₂,..., а_n) и натуральное число k. Требуется установить, имеется ли такое подмножество множества А, сумма элементов которого была бы равна S.

Данная проблема получила свое название в связи с тем, что поставленная задача может быть переформулирована также в следующем виде. Имеется набор предметов с известными весами и рюкзак, который может выдержать вес, не превышающий заданной величины. Можно ли выбрать набор предметов для погрузки в рюкзак так, чтобы они в точности имели максимально возможный вес.

Идея построения системы шифрования на основе проблемы рюкзака заключается в выделении некоторого подкласса задач об укладке рюкзака. Параметры подкласса определяют секретный ключ, а параметры модифицированной задачи – открытый ключ. В качестве легко решаемой задачи. Меркль и М. Хеллман в 1978 г. предложили задачу об укладке "супервозрастающего" рюкзака.

А=(a₁,a₂,a_n) a_i – целые положительные числа

Нам известно k

Задача состоит в том, чтобы среди элементов вектора A_i выбрать такие суммы, которые будут равняться k=∑ a_i , i=n

Например

k=3231

А(43,129,215,473,903,302,561,1165,697,1523)

Методом перебора определяем 129+473+903+561+1165=3231

В=(0,1,0,1,1,1,0,1,1,0,0) A*B=k S_m=k₁, k₂…k_m

Алгоритмы шифрования рюкзачной криптосистемы.

1. Строим сверхрастущий вектор. Размеры сверх растущего вектора равны количеству бит для кодирования каждого символа исходного сообщения.

2. Переходим от сверхрастущего вектора А к вектору В. Для того найдем секретные коэффициенты m и t таким образом, что

1) m>суммы всех элементов вектора А