Системы шифрования с симметричным ключом имеют существенный недостаток. Если ключ и сообщение эквивалентны по длине, то возникает вопрос,не проще ли отправить сообщение по секретной почте. Был разработан математический аппарат для шифрования с открытым распределением ключей. Идея метода основана на использовании односторонних математических функций. Это такие функции, когда по аргументу х легко вычислить f(x), когда известно f(x) , то х найти сложно.
1. Выбираем одностороннюю математическую функцию такую, что по х-f(x) легко найти, а f(x) по x сложно. Функцию f(x) объявляем открытой.
2. Находится такая подзадача для этой односторонней функции, для которой значения х по f(x) определяется легко
3. Значения открытого ключа (f(x)) перемешиваются так, чтобы для криптоаналитика она выглядела труднорешимой. Для легального получения используем способ приведения к легкой подзадаче
Показательным примером являются «рюкзачные» криптосистемы.
А=(a1,a2,an) ai – целые положительные числа
Нам известно k
Задача состоит в том, чтобы среди элементов вектора Ai выбрать такие суммы, которые будут равняться k=? ai , 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 Sm=k1, k2…km
Под задачей имеющей однозначное обратное решение понимается сверхрастущий вектор (каждый последующий элемент больше суммы всех предыдущих). Для сверхрастущего вектора и рюкзака k существует однозначный алгоритм нахождения столбца В. Такого, что А*В=k
Рюкзачные криптосистемы
Проблема рюкзака (или ранца) может быть сформулирована следующим образом. Пусть задано множество натуральных чисел А = (a1, а2,…, аn) и натуральное число k. Требуется установить, имеется ли такое подмножество множества А, сумма элементов которого была бы равна S.
Данная проблема получила свое название в связи с тем, что поставленная задача может быть переформулирована также в следующем виде. Имеется набор предметов с известными весами и рюкзак, который может выдержать вес, не превышающий заданной величины. Можно ли выбрать набор предметов для погрузки в рюкзак так, чтобы они в точности имели максимально возможный вес.
Идея построения системы шифрования на основе проблемы рюкзака заключается в выделении некоторого подкласса задач об укладке рюкзака. Параметры подкласса определяют секретный ключ, а параметры модифицированной задачи – открытый ключ. В качестве легко решаемой задачи. Меркль и М. Хеллман в 1978 г. предложили задачу об укладке супервозрастающего рюкзака.
А=(a1,a2,an) ai – целые положительные числа
Нам известно k
Задача состоит в том, чтобы среди элементов вектора Ai выбрать такие суммы, которые будут равняться k=? ai , 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 Sm=k1, k2…km
Под задачей имеющей однозначное обратное решение понимается сверхрастущий вектор (каждый последующий элемент больше суммы всех предыдущих). Для сверхрастущего вектора и рюкзака k существует однозначный алгоритм нахождения столбца В. Такого, что А*В=k
Алгоритмы шифрования рюкзачной криптосистемы.
1. Строим сверхрастущий вектор. Размеры сверх растущего вектора равны количеству бит для кодирования каждого символа исходного сообщения.
2. Переходим от сверхрастущего вектора А к вектору В. Для того найдем секретные коэффициенты m и t таким образом, что
1) mсуммы всех элементов вектора А
2) а1*tm
3. НОД (m,t)=1
4. bi=ai*t mod m
5. Шифруем сообщение. B-открытый ключ для шифрования
W=(w1,w2,…wn) – исходный текст (wi – битовая маска символа)
6. k=B*W = k1, k2, …kn
7. Передадим в открытый канал k и открытый ключ B.
8. Для расшифровки сообщения будем пользоваться открытым ключом B и m и t, известными только легальному получателю
Статьи к прочтению:
Защита информации. Криптография с открытым ключом, RSA
Похожие статьи:
-
Системы криптографической защиты данных с открытым ключом.
Основой асимметричной криптосистемы является асимметричный алгоритм шифрования. В алгоритмах с открытым ключом (также называемых асимметричными) для…
-
Стандартные методы шифрования и криптографические системы
Стандарт шифрования США DES (Data Encryption Standard – стандарт шифрования данных) относится к группе методов симметричного шифрования и действует с…