Сверх возрастающие рюкзаки

Если перечень масс предметов представляет собой сверх возрастающую последовательность, то такую проблему рюкзака легко решить. Сверх возрастающая последовательность – последовательность, каждый последующий элемент которой больше суммы всех предыдущих элементов. Чтобы решить, необходимо взять полный вес и сравнить его с самым большим числом последовательности, если полный вес меньше, чем это число, то его не кладут в рюкзак, если полный вес больше, либо равен числу, то оно кладется в рюкзак, а общая масса уменьшается на это число. После этих операций переходят к следующему элементу последовательности и так до последнего.

Пример:

Последовательность: 2, 3, 6, 13, 27, 52

S= 70

70> 52 => (берем 52)

70-52=18

18< 27=> (НЕ БЕРЕМ 27)

18> 13=> (берем 13)

18-13=5

5< 6=> (не берем 6)

И т.д. получаем: 2, 3, 6, 13, 27, 52= 1, 1, 0, 1, 0, 1

Алгоритм Меркла-Хелмена основан на этом свойстве. Закрытый ключ является последовательностью весов проблемы сверх возрастающего рюкзака. Открытый ключ – последовательность весов проблемы нормального рюкзака с тем же решением. Меркл и Хелмен с помощью модульной арифметики разработали способ преобразования проблемы сверх возрастающего рюкзака, в проблему нормального рюкзака.

Пример: Зашифрование и Расшифрование.

Этап 1. Создание открытого ключа из закрытого.

Чтобы получить нормальную последовательность рюкзака необходимо взять сверх возрастающую последовательность(например: 2, 3, 6, 13, 27, 52) и умножить по модулю m все значения на число n. Значения модуля должно быть больше суммы всех численных последовательностей(например m=105). Множитель n должен быть взаимно простым числом с модулем(например n=31).

2*31mod105=62

3*31mod105=93

6*31mod105=81

13*31mod105=88

27*31mod105=102

52*31mod105=37

K1: {62, 93, 81, 88, 102, 37}

Этап 2 Шифрование.

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

M=011000 110101 101110

C=174 280 333

Этап 3 Расшифрование.

Законный получатель сообщения C знает закрытый ключ K2, а так же значением m(105) и n(31), использованные для превращения ее в нормальную последовательность рюкзака. Для расшифрования сообщения получатель вначале должен определить значение (n^-1) такое, что (n*n^-1=1(mod105)).

31*n^-1=1(mod105)

31*n^-1=105*k+1(диафантовое уравнение, решаемое в целых числах)

Решается такое уравнение расширенным уравнением Эвклида:

31*n^-1=105*k+1

Прямой ход:

105=31*3+12

31=12*2+7

12=7*1+5

7=5*1+2

5=2*2+1

2=1*2+0

Обратный ход:

1=5-2*2=5-2*(7-5*1)= 5*3-7*2=(12-7*1)*3-7*2=12*3-7*5=12*3-(31-12*3)*5=12*13-31*5=(105-31*3)*13-31*5=105*13-31*44

N^-1=-44=61(mod105)

Значения шифр текста должны быть умножены на n^-1mod105

174*61(mod105)=9 в соответствии с закрытым ключом: 011000

280*61(mod105)=70 в соответствии с закрытым ключом: 110101

333*61(mod105)=48 в соответствии с закрытым ключом: 101110

Для последовательности из 6 элементов не трудно решить задачу рюкзака, даже если она не является сверх возрастающей. Реальные последовательности должны содержать не менее 250 элементов. Длина каждого элемента последовательности должна быть 200 и 400 битами, а длина модуля от 100 до 200 бит. Для получения значений практические реализации используют генератор случайных последовательностей.

Лекция №8

Сравнение симметричных и ассиметричных систем

Достоинства симметричных систем:

1. Скорость расчетов примерно на 3 порядка выше.

2. Относительная простота реализации за счет использования более простых операций.

3. Меньшая требуемая длинна ключа для сопоставимой стойкости.

4. Большая изученность за счет большего времени использования.

Недостатки симметричных систем:

1. Сложность управления ключами в большой сети пользователей, означает квадратичное возрастание числа пар ключей, которые необходимо генерировать, передавать и хранить в сети(количество ключей: N=(n*n-1)/2).

2. Сложность обмена секретными ключами. Для применения, необходимо решить проблему надежной передачи ключей каждому абоненту, так как нужен секретный канал, для передачи секретного ключа обеим сторонам.

Для компенсации недостатков симметричного шифрования, в настоящее время широко применяется комбинированная(гибридная) криптографическая система:

Существует 2 абонента A, B.

K1a(открытый ключ), K2a(закрытый секретный ключ), K(сеансовый ключ).

Сеансовый ключ – секретный симметричный случайный ключ, который используется только в пределах одного сеанса связи и после этого уничтожается.

1. Абонент A генерирует сеансовый ключ K.

2. Абонент A зашифровывает сеансовый ключ при помощи своего секретного ключа K2a и ассиметричного алгоритма(C=Ek2a(K)). Полученное сообщение он отправляет абоненту B(C=Ek2a(K)à B).

3. Абонент B расшифровывает послание при помощи того же алгоритма и открытого ключа абонента A(Dk1a(C)=K).

4. Теперь абоненты A и B могут отправлять друг другу секретные сообщения при помощи симметричного алгоритма и сеансового ключа K.

Методы защиты внешнего периметра

Под системой защиты внешнего периметра автоматизированной системы, обычно включается в себя 2 основных механизма:

1. Средства межсетевого экранирования.

2. Средства обнаружения вторжений.

Так как эти механизмы решают родственные задачи, они часто оформляются в рамках единого программного продукта.

Межсетевое экранирование

Межсетевой экран(МЭ(firewall/брандмауэр)) выполняет функции разграничения информационных потоков на границы защищаемой автоматизированной системы, это позволяет:

1. Повысить безопасность объектов внутренней среды за счет игнорирования не авторизованных запросов из внешней среды.

2. Контролировать информационные потоки из внутренней, во внешнюю среду.

3. Регистрировать процессы информационного обмена.

Контроль информационных потоков производится посредством фильтрации информации, т.е. анализом по совокупности критериев и принятия решения о распространении или не распространении ее в или из АС.

В зависимости от принципов функционирования выделяют несколько классов межсетевых экранов. Основным классификационным признаком является уровень модели OSI, на которой работает тот или иной межсетевой экран.

Классификация:

1. Фильтр-пакеты – межсетевой экран с фильтрацией пакетов представляет собой маршрутизатор или работающую на шлюзе программу, сконфигурируем мая таким образом, чтобы фильтровать входящие и исходящие сетевые пакеты с данными, этот тип межсетевых экранов работает на сетевом и транспортном уровне модели OSI. Он пропускает или отбраковывает пакеты в соответствии с информацией, содержащихся в заголовках пакетов. Пакеты ассоциируются с конкретным отправителем и получателем, а информация в них содержит:

1.1. IP адрес и порт отправителя.

1.2. IP адрес и порт получателя.

1.3. Информацию о приложении и протоколе.

2. Шлюзы сеансового уровня – данные межсетевые экраны работают на сеансовом уровне модели OSI, они следят за подтверждением связи между авторизованным клиентом и внешним узлом, и наоборот, определяя является ли запрашиваемый сеанс связи допустимым.

3. Шлюзы прикладного уровня – межсетевые экраны данного класса позволяют фильтровать отдельные виды команд или наборы данных в протоколах прикладного уровня(HTTP, Torrent и т.д.), для этого используются Proxy сервисы(программы специального назначения, управляющая трафиком через межсетевой экран для определенных высокоуровневых протоколов).

Схема использования прокси сервиса:

3.1. Без использования Proxy сервиса.

3.2. С использованием Proxy сервисами.

4. Межсетевые экраны экспертного уровня – межсетевые экраны, сочетающие в себе элементы всех трех предыдущих категорий, вместо Proxy сервисов, в таких экранах используются алгоритмы распознавания и обработки данных на уровне отдельных приложений.

Лекция №9

Системы обнаружения вторжений

Обнаружения вторжений представляет собой процесс выявления несанкционированного доступа или попыток несанкционированного доступа к ресурсам АС.

Система обнаружения вторжений(Intrusion Detection System(IDS)) в общем случае представляет собой программно-аппаратный комплекс, решающий данную задачу.

Сигнатура – совокупность событий или действий, характерные для данного типа угрозы безопасности.

1. Сенсор получает сетевой пакет.

2. Пакет передается ядру для анализа.

3. Проверяется совпадение сигнатуры.

4. Если совпадений нет, то от узла получается следующий пакет.

5. Если есть совпадение, то появляется предупреждающее сообщение.

6. Происходит вызов модуля ответного реагирования.

Ошибки первого и второго рода:

1. Ошибки первого рода, когда авторизованный субъект безопасности воспринимается системой безопасности, как нарушитель.

2. Ошибки второго рода, когда нарушитель воспринимается системой безопасности, как авторизованный субъект доступа.

Все системы, использующие сигнатуры для проверки доступа, подвержены ошибкам второго рода, в том числе антивирусы, работающие на антивирусной базе.

Функционирование системы IDS во многом аналогично межсетевому экрану. Сенсоры получают сетевой трафик, а ядро, путем сравнения полученного трафика, с записями имеющихся базами сигнатур, пытается выявить следы попыток несанкционированного доступа. Модуль ответного реагирования представляет собой дополнительный компонент, который может быть использован для оперативного блокирования угрозы, например, может быть сформированного новое правило для межсетевого экрана.

Существует две основных категории IDS:

1. IDS уровня сети. В таких системах сенсор функционирует на выделенном для этих целей хосте(узле), защищаемом сегменте сети. Обычно он работает в прослушивающем режиме, чтобы анализировать весь ходящий по сегменту сетевой трафик.

2. IDS уровня хоста. В случае, если сенсор функционирует на уровне хоста для анализа может быть использована следующая информация:

2.1. Записи стандартных средств. Протоколирование ОС.

2.2. Информация об использованных ресурсах.

2.3. Профили ожидаемого поведения пользователя.

Каждый из типов IDS имеет свои достоинства и недостатки.

IDS уровня сети не снижает общую производительность системы, а IDS уровня хоста более эффективно выявляет атаки и позволяет анализировать активность, связанную с отдельным хостом. На практике целесообразно применять оба этих типа.

Протоколирование и аудит

Подсистема протоколирования и аудита является обязательным компонентом любой АС. Протоколирование(регистрация) представляет собой механизм подотчетности системы обеспечения информационной безопасности, фиксирующая все события, относящиеся к информационной безопасности. Аудит – анализ протоколирования информации с целью оперативного выявления и предотвращения нарушений режима информационной безопасности.

Назначения механизма регистрации и аудита:

1. Обеспечение подотчетности пользователей и администратора.

2. Обеспечение возможности реконструкции последовательности событий(например при инцидентах).

3. Обнаружение попыток нарушения режима информационной безопасности.

4. Выявление технических проблем, напрямую не связанных с информационной безопасностью.

Протоколируемые данные заносятся в регистрационный журнал, который представляет собой хронологически-упорядоченную совокупность записи результатов деятельности субъектов АС, влияющих на режим информационной безопасности. Основными полями такого журнала являются следующие:

1. Временная метка.

2. Тип события.

3. Инициатор события.

4. Результат события.

Так, как системные журналы являются основными источниками информации для последующего аудита и выявления нарушения безопасности должен быть поставлен вопрос о защите их от не санкционированной модификации. Система протоколирования должна быть спроектирована таким образом, чтобы не один пользователь, включая администраторов, не мог произвольным образом изменять записи системных журналов.

Поскольку файлы журналов хранятся на том или ином носителе, рано или поздно может возникнуть проблема нехватки пространства на этом носителе, при этом реакция системы может быть различной, например:

1. Продолжить работу системы, без протоколирования.

2. Заблокировать систему до решения проблемы.

3. Автоматически удалять самые старые записи в системном журнале.

Первый вариант является наименее приемлемым с точки зрения безопасности.

Лекция №10
Построение системы защиты от угроз нарушения целостности информации

Основные принципы обеспечения целостности:

Большинство механизмов, реализующих защиту информации от угроз нарушения конфиденциальности, в той или иной степени обеспечивают сохранение целостности информации.

1. Корректность транзакции. Принцип требует обеспечения невозможности произвольной модификации данных пользователя. Данные могут модифицироваться исключительно таким образом, чтобы сохранялась их целостность.

2. Аутентификация пользователей. Изменение данных может осуществляться только аутентифицированными, для выполнения соответствующих действий, пользователями.

3. Минимизация привилегий. Процессы в автоматизированной системе должны быть наделены только теми привилегиями, которые минимально необходимы для их исполнения.

4. Разделение обязанностей. Для выполнения критических или необратимых операций требуется участие нескольких независимых пользователей. На практике разделение обязанностей обычно осуществляется, либо чисто организационными методами, либо с помощью криптографических схем разделения секрета.

Простейшая схема разделения секрета:

A, B – пользователи, между которыми необходимо разделить секрет.

M – в качестве секрета выступает информация.

Необходимо организовать разделение таким образом, чтобы не один из пользователей поодиночке не смог прочитать это сообщение.

Решается с помощью посредника(T – третий, независимый участник(лицо), которому полностью доверяют остальные пользователи).

А) Посредник генерирует случайное сообщение R той же длины, что и сообщение M.

Б) Посредник выполняет следующие действия: Двоично складывает сообщения R и M и получает сообщение S.

В) Посредник передает сообщение R пользователю A, а сообщение S пользователю В.

Г) Только решив оба прочитать сообщение, пользователи A и B могут это сделать: Сложить побитово сообщение R и сообщение S.

Пример: A1, A2, …, An

А) Посредник генерирует R1, R2, …, Rn-1.

Б) Производит сумму Ri(от 1 до n-1)+M=S.

В) R1-> A1, R2-> A2, …, Rn-1-> An-1, S-> A.

Г) M= sum Ri(от 1 до n-1)+S.

Недостаток: Если хотя бы один из участников откажется от протокола, сообщение будет невозможно прочитать.

5. Аудит произошедших событий. Данный принцип требует создания механизма подотчетности пользователей, позволяющего отследить моменты нарушения целостности информации.

6. Объективный контроль. Необходимо реализовать оперативное выделение только тех данных, контроль целостности которых является оправданным.

7. Управление передачей привилегий. Порядок передачи привилегий должен полностью соответствовать организационной структуре предприятия.

Структура системы защиты от угроз нарушения целостности(см. тетрадь).

Главным отличием от механизмов обеспечения конфиденциальности является криптографические методы.

При построении систем защиты от угроз нарушения целостности информации используются следующие криптографические механизмы:

1. Криптографические ХЭШ функции.

2. Электронный подписи.

3. Коды проверки подлинности.

Однонаправленные ХЭШ функции

Однонаправленные ХЭШ функции (h(M)), применяются к сообщению произвольной длинны M(прообраз длины), и возвращает длину H(результат) к фиксированной длине m. Длинна m результата H, называется, разрядностью ХЭШ функции и зависит только от алгоритма вычисления h.

Свойства однонаправленной ХЭШ функции:

1. Зная прообраз M легко вычислить результат H(M-> H).

2. Зная результат H практически невозможно получить исходное значение прообраза(H-х> M).

3. Свойство столкновений(коллизий). Зная сообщение M практически трудно найти другое сообщение M’, для которых: h(M)=h(M’) – это первое свойство коллизий(столкновений).

4. Практически трудно найти два случайных прообраза M и M’, для которых h(M)=h(M’) – это второе условие коллизий(коллизия второго уровня).

Согласно статистическому парадоксу “дней рождений”, более вероятными и опасными считаются коллизии 2 рода.

Парадокс “Дней рождений”: Ставятся два вопроса:

1. Сколько человек должны находиться в комнате, чтобы с вероятностью хотя бы 50% у вас был общий с ними день рождение, хотя бы с одним из них? (183 человека).

2. Сколько человек должны находиться в комнате, чтобы с вероятностью минимум 50% хотя бы у 2 из них был общий день рождение? (23 человека).

Лекция № 11

Следующий протокол показывает, каким образом можно использовать столкновения второго рода.

A, B абоненты, а так же арбитр(посредник-участвует во всех частях протокола, арбитр только в спорных моментах) T.

1. Абонент A готовит 2 версии контракта на продажу автомобиля(одну-выгодную для B и другую не выгодную для B)(M1, M2).

2. Абонент A вносит несколько незначительных изменений в каждый документ и вычисляет соответствующие ХЭШ функции(M1’, M2’). Например, если подписание документа осуществляется при помощи 64 Битной ХЭШ функции, а документ состоит из 32 строк, то можно делая или не делая пробел в каждой из строк получить (2^32) версий каждого документа.

3. Абонент A сравнивает ХЭШ значение для каждого изменения в каждом из 2 документов, разыскивая пару, для которой значение ХЭШ функций будут одинаковыми(h(M1’)=h(M2’)). Если используются 64х разрядные ХЭШ функции, то такая пара, как правило, будет найдена.

4. Абонент A получает подписанную абонентом B выгодную для него версию контракта.

5. Спустя некоторое время абонент A подменяет выгодную версию, на не выгодную версию. Теперь он может убедить арбитра T, что абонент B подписывал для него не выгодную версию контракта.

Вывод: Слишком короткие ХЭШ значения больше подвержены коллизиям второго рода. Необходимо использовать однонаправленные ХЭШ функции с большим числом разрядов(MD5(128), SHA1(256) и т.д.).

Идея функции сжатия

Однонаправленные ХЭШ функции строятся на идее функции сжатия, такая однонаправленная функция выдает значения фиксированной длинны n для прообраза произвольной, как правило большей длинны m.

Данная функция является блочной, для этого сообщение(прообраз) необходимо разделить на блоки одинаковой длинны.

Блоки(Mi)(см.телефон).

hi=f(Mi, hi-1)

h0=IV – инициализационный вектор.

ХЭШ значения вместе со следующим блоком сообщения становится следующим выходом функции сжатия. ХЭШ значения всего сообщения, является ХЭШ значение последнего блока.

Замечание: Функция сжатия так же строится с использованием лавинного эффекта(например: если поменять 1 бит прообраз, то в ХЭШ значении в среднем поменяется 50%бит – это необходимо для того, чтобы нельзя было определить зависимость между прообразом и результатом ХЭШ функции).

Применение

1. В процессе парольной аутентификации. Пароли в системе чаще всего хранятся в виде соответствующих ХЭШ значений.

2. При проверке целостности данных. Рассчитанная вновь контрольная сумма(ХЭШ значение) сравнивается с рассчитанной изначально. Равенство этих двух сумм говорит о неизменности данных за этот промежуток времени.

3. При использовании электронных подписей.

Контрольная сумма(CHECKSUM), FINGERPRINT(отпечаток пальца). Часто используются MD, MD2, MD4, MD5, SHA 1, 2, 3, ГОСТ Р 3411.94.

Коды проверки подлинности сообщений(MAC(Message Authentication Code))

Код проверки подлинности сообщения – зависящая от секретного ключа однонаправленная ХЭШ функция. Коды MAC обладают теми же свойствами, что и однонаправленные функции, кроме того, они зависят от секретного ключа. Только владелец идентичного ключа может проверить ХЭШ значения. Коды MAC полезны для обеспечения проверки подлинности без нарушения безопасности.

Пример: Коды MAC могут быть использованы для проверки подлинности файлов, которыми обмениваются пользователи. Так же, они могут быть использованы одним пользователем для проверки не изменились ли его файлы, например, в следствии действия вирусов. Если пользователь воспользуется простой ХЭШ функцией, то вирус может вычислить новое ХЭШ значение после заражения файла и изменить их. С кодами проверки вирус не сможет этого добиться, так как не знает секретный ключ.

Простейшим способом преобразовать однонаправленную ХЭШ функцию в код проверки, является шифрование ХЭШ значения к симметричному алгоритму(hk(M)=Ek(h(M))). Любой MAC код может быть преобразован в однонаправленную ХЭШ функцию с помощью раскрытия ключа.

Лекция №12

Электронные подписи(Digital Signature)(не полная лекция)

1. Подписанный документ нельзя изменить. Если, после подписания, документ был изменен, то цифровая подпись перестанет ему соответствовать, соответственно этот документ необходимо подписать заново.

2. От цифровой подписи невозможно отречься. Человек, подписавший документ не сможет впоследствии утверждать, что он этого не делал(отказ от авторства).

Подпись документа с помощью криптографии с открытым ключом

Существует 2 абонента A и B. У абонента Aесть открытый ключ K1a и закрытый ключ K2a. Абонент A подписывает документ, абонент B проверяет подпись.

1. Абонент A зашифровывает документ своим закрытым ключом, таким образом, подписывая его.

2. Абонент A посылает абоненту B подпись S и сообщение M.

3. Абоненту B известен открытый ключ абонента A, он расшифровывает подпись. В случае равенства, подпись будет верна.

Данный протокол обладает следующими недостатками:

1. Объем подписи S равен объему сообщения, что удваивает посылку.

2. Шифрование больших сообщений занимает много времени, т.к. алгоритмы с открытыми ключами работает медленно.

Подпись документа с помощью ассиметричных алгоритмов и однонаправленных ХЭШ функций

Абоненты A и B заранее договариваются об алгоритме шифрования и вычисления ХЭШ функции.

1. Абонент A вычисляет значение ХЭШ функции от документа.

2. Абонент A зашифровывает это значение своим закрытым ключом.

3. Абонент A посылает абоненту B сообщение и подпись.

4. Абонент B расшифровывает подпись при помощи открытого ключа абонента A.

5. Абонент B вычисляет значение ХЭШ функции от сообщения, затем он сравнивает полученное значение, в случае равенства подпись верна.

В данном протоколе нет защиты от подмены открытого ключа абонента A. Например, злоумышленник C может подменить это ключ в открытой базе, в этом случае, он может подписывать документы своим закрытым ключом, выдавая себя за абонента A. Данная проблема решается с помощью третьей доверенной стороны.

Управление открытыми ключами

Так, как открытый ключ доступен любому пользователю, то необходим механизм проверки того, что этот ключ принадлежит именно своему владельцу. Необходимо обеспечить доступ любого пользователя к подлинному открытому ключу любого другого пользователя, защитить эти ключи от подмены злоумышленником, а так же организовать отзыв ключа в случае его компрометации. Задача защиты ключей от подмены решается с помощью сертификатов. Сертификат позволяет удостоверить заключенное в нем данные о владельце и открытый ключ подписью какого либо доверенного лица. Существует система сертификата 2 типов:

1. Централизованные. Используется центры сертификации, поддерживаемые доверенными организациями. Центр сертификации формирует собственный закрытый ключ и свой сертификат. Формируют сертификаты в конечных пользователей и удостоверяют их аутентичность своей цифровой подписью. Так же центр производит отзыв истёкших и скомпрометированных сертификатов и ведет БД выданных и отозванных сертификатов.

2. Децентрализованные. Путем перекрестного подписания сертификатов знакомых и доверенных людей каждым пользователем создается так называемая “сеть доверия”.

Структура сертификатов(в России)

Перечень обязательных и не обязательных полей, которые могут присутствовать в сертификате, определяется стандартом и законодательством. Согласно законодательству России сертификат должен содержать следующие поля:

1. Уникальный регистрационный номер сертификата.

2. Даты и время начала и окончания срока действия сертификата.

3. ФИО владельца сертификата ключа подписи.

4. Открытый ключ.

5. Наименования и реквизиты центра сертификации.

6. Наименование криптографического алгоритма.

7. Информация об ограничении использования подписи.

Хранение закрытого ключа

Закрытый ключ является наиболее уязвимым компонентом всей системы цифровой подписи. Злоумышленник, укравший закрытый ключ пользователя может создать действительную цифровую подпись любого документа от имени этого пользователя, поэтому особое внимание необходимо уделять к способам хранения закрытого ключа. Пользователь может хранить свой закрытый ключ на собственном компьютере, однако, в этом случае защищенность ключа буде полностью зависеть от защищенности компьютера, что не всегда приемлемо.

Существует следующее устройство хранения закрытого ключа:

1. Дискета.

2. Смарт-карты.

3. Носителю USB.

4. Таблетки TouchMemory.

Кража или потеря одного из устройств, как правило, быстро замечается пользователем, и он отзывает свой сертификат из центра сертификации. Наиболее приемлемым из этих способов является использование Смарт-карты, она оснащена собственным процессором и памятью, подписываемый документ загружается в память карты, таким образом, закрытый ключ не копируется на другие носители.

В соответствии с Российским законодательством, ответственность за хранение закрытого ключа пользователь несет сам.