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

Системы шифрования с симметричным ключом имеют существенный недостаток. Если ключ и сообщение эквивалентны по длине, то возникает вопрос,не проще ли отправить сообщение по секретной почте. Был разработан математический аппарат для шифрования с открытым распределением ключей. Идея метода основана на использовании односторонних математических функций. Это такие функции, когда по аргументу х легко вычислить 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

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

 

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

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

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

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

2) а₁*t>m

3. НОД (m,t)=1

4. b_i=a_i*t mod m

5. Шифруем сообщение. B-открытый ключ для шифрования

W=(w₁,w₂,…w_n) – исходный текст (w_i – битовая маска символа)

6. k=B*W = k₁, k₂, …k_n

7. Передадим в открытый канал k и открытый ключ B.

8. Для расшифровки сообщения будем пользоваться открытым ключом B и m и t, известными только легальному получателю