30. Криптосистемы с открытым ключом

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