Лекции.Орг


Поиск:




Категории:

Астрономия
Биология
География
Другие языки
Интернет
Информатика
История
Культура
Литература
Логика
Математика
Медицина
Механика
Охрана труда
Педагогика
Политика
Право
Психология
Религия
Риторика
Социология
Спорт
Строительство
Технология
Транспорт
Физика
Философия
Финансы
Химия
Экология
Экономика
Электроника

 

 

 

 


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




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

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, известными только легальному получателю

 





Поделиться с друзьями:


Дата добавления: 2017-02-25; Мы поможем в написании ваших работ!; просмотров: 588 | Нарушение авторских прав


Поиск на сайте:

Лучшие изречения:

Наука — это организованные знания, мудрость — это организованная жизнь. © Иммануил Кант
==> читать все изречения...

2308 - | 2104 -


© 2015-2025 lektsii.org - Контакты - Последнее добавление

Ген: 0.01 с.