2.3.1.2. Метод укладки (упаковки) рюкзака (ранца)
Реализацией задачи об укладке рюкзака является криптоалгоритм Мер-кле и Хелмана. Рассмотрим этот криптоалгоритм на примере. Пусть задан набор чисел
(а,,а2,...ап) = А.
Задачей является нахождение таких чисел а|5 если это возможно, сумма которых равна числу к. В простейшем случае это число к указывает размер рюкзака, а каждое из чисел а. указывает размер предмета, который может быть упакован в рюкзак. Задачей является нахождение такого набора предметов, чтобы рюкзак был полностью заполнен.
В качестве примера возьмем число к=3231 и набор из 10 целых чисел а^...,
аю:
43, 129, 215, 473, 903, 302, 561, 1165, 697, 1523.
Заметим, что число k получается при сложении только некоторых чисел а:
Рис. 5.28. Метод укладки рюкзака
3231 = 129+ 473 + 903 + 561 + 1165
Таким образом, сложив эти числа, мы нашли решение, то есть заполнили рюкзак. Ситуация наглядно проиллюстрирована на рис. 5.28.
В принципе решение всегда может быть найдено полным перебором подмножеств А и проверкой, какая из сумм равна числу к. В нашем случае это означает перебор 210=1024 подмножеств (включая при этом и пустое множество). Это вполне осуществимо.
Но что будет, если существует несколько сотен чисел а/? В нашем примере п=10, чтобы не усложнять положение и расчеты. В реальных условиях пример будет иметь, скажем, 300 чисел а.. Суть здесь в том, что неизвестны алгоритмы, имеющие существенно меньшую сложность по сравнению с полным перебором. Поиск правильного решения среди 2300 подмножеств не поддается обработке.
- Введение
- Часть I основные понятия и положения защиты информации в компьютерных системах
- 1 Предмет и объект защиты
- 1.1. Предмет защиты
- 3. Ценность информации изменяется во времени.
- 4. Информация покупается и продается.
- 5. Сложность объективной оценки количества информации.
- 1.2. Объект защиты информации
- 2 Криптографические системы защиты информации
- 2.1. Одноключевые криптографические системы
- 2.1.1. Блочные шифры
- 2.1.2. Шифры простой перестановки
- 2.1.3. Шифры сложной перестановки
- 2.1.4. Шифры замены (подстановки)
- 2.1.5. Одноалфавитные шифры.
- 2.1.6. Многоалфавитные шифры
- 2.2. Составные шифры
- 2.2.1. Шифры поточного (потокового) шифрования
- 2.2.1.1. Синхронные поточные шифры
- 2.2.1.2. Самосинхронизирующиеся поточные шифры
- 2.2.1.3. Комбинированные шифры
- 2.3. Двухключевые криптографические системы
- 2.3.1. Криптографические системы с открытым ключом
- 2.3.1.1. Метод возведения в степень
- 2.3.1.2. Метод укладки (упаковки) рюкзака (ранца)
- 2.3.1.3. Кодовые конструкции
- 2.4. Составные криптографические системы
- 2.5. Надежность использования криптосистем
- 3 Симметричные криптосистемы и блочные шифры
- 3.1 Определение блочного шифра
- 3.2. Принцип итерирования
- 3.3. Конструкция Фейстеля
- 3.4. Режимы шифрования блочных шифров
- 3.4 Стандарты блочного шифрования
- 3.4.1 Федеральный стандарт сша — des
- 3.4.2. Стандарт России — гост 28147-89
- 3.5 Атаки на блочные шифры
- 3.5.1 Дифференциальный криптоанализ
- 3.5.2. Дифференциальный криптоанализ на основе отказов устройства
- 3.6.3. Линейный криптоанализ
- 4.6.4.Силовая атака на основе распределенных вычислений
- 4.7. Другие известные блочные шифры
- 4 Угрозы безопасности информации в компьютерных системах
- 4.1. Случайные угрозы
- 2.2. Преднамеренные угрозы
- 2.2.2. Несанкционированный доступ к информации
- Направления обеспечения информационной безопасности
- Постулаты безопасности
- 3.1. Правовая защита
- Раздел «Предмет договора»
- Раздел «Порядок приема и увольнения рабочих и служащих»
- Раздел «Основные обязанности администрации»
- 3.2 Организационная защита
- 3.3. Инженерно-техническая защита
- 3.3.1. Общне положения
- 3.3.2. Физические средства защиты
- Охранные системы
- Охранное телевидение
- Запирающие устройства
- 3.3.3. Аппаратные средства защиты
- 3.3.4. Программные средства защиты
- Основные направления использования программной защиты
- Защита информации от несанкционированного доступа
- Защита от копирования
- Защита информации от разрушения
- 3.3.5. Криптографические средства защиты
- Технология шифрования речи
- 4 Способы защиты информации
- 4.1. Общие положения
- 4.2. Характеристика защитных действий
- Защита информации от утечки
- 5.1. Общие положения
- 5.2. Защита информации от утечки по визуально-оптическим каналам
- 5.2.1. Общие положения
- 5.2.2. Средства и способы защиты
- 5.3. Защита информации от утечки по акустическим каналам
- 5.3.1. Общие положения
- 5.3.2. Способы и средства защиты
- 5.4. Защита информации от утечки по электромагнитным каналам
- 5.4.1. Защита утечки за счет микрофонного эффекта
- 5.4.2. Защита от утечки за счёт электромагнитного излучения
- 5.4.3. Защита от утечки за счет паразитной генерации
- 5.4.4. Защита от утечки по цепям питания
- 5.4.5. Защита от утечки по цепям заземления
- 5.4.6. Защита от утечки за счет взаимного влияния проводов и линий связи
- 5.4.7. Защита от утечки за счет высокочастотного навязывании
- 5.4.8. Защита от утечки в волоконно-оптических линиях и системах связи
- 5.5. Защита информации от утечки по материально-вещественным каналам
- 6.1. Способы несанкционированного доступа
- 6.2. Технические средства несанкционированного доступа к информации
- Контроль и прослушивание телефонных каналов связи
- Непосредственное подключение к телефонной линии
- Подкуп персонала атс
- Прослушивание через электромагнитный звонок
- Перехват компьютерной информации, несанкционированное внедрение в базы данных
- 6.З. Защита от наблюдения и фотографирования
- 6.4 Защита от подслушивания
- 6.4.1. Противодействие подслушиванию посредством микрофонных систем
- Некоторые характеристики микрофонов
- Противодействие радиосистемам акустического подслушивания
- Общие характеристики современных радиозакладок
- Содержание введение
- Часть I основные понятия и положения защиты информации в компьютерных системах
- Угрозы безопасности информации в компьютер-ных системах
- Направления обеспечения информационной без-опасности
- 4. Способы защиты информации
- Противодействие несанкционированному досту-пу к источникам конфиденциальной информации