Реферат Лекции по Информационной безопасности
Работа добавлена на сайт bukvasha.net: 2015-10-28Поможем написать учебную работу
Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
от 25%
Подписываем
договор
Лекции по дисциплине «ИНФОРМАЦИОННАЯ БЕЗОПАСНОСТЬ»
Понятие защищенной системы. Определение. Свойства.
Защищенная система – это система обработки информации, в состав которой включен тот или иной набор средств защиты. Однако это представление не полное, т.к. наличие средств защиты является лишь необходимым условием и не может рассматриваться в качестве критерия защищенной системы, т.к. безопасность не является абсолютной характеристикой и может рассматриваться только относительно некоторой среды, в кот. действуют угрозы.
Поэтому более полное представление о защищенной системе:
Защищенная система обработки информации для определенных условий эксплуатации обеспечивает безопасность, конфиденциальность и целостность обрабатываемой информации и поддерживает свою работоспособность в условиях воздействия на нее любого множества угроз.
Защищенная система содержит достаточные условия безопасности и является качественной характеристикой информации. Поэтому создание средств защиты…..?
Свойства защищенной системы:
1) Защищенная система обр. шиф. для автоматизации процесса обработки информации, включая все аспекты этого процесса, связанные с обеспечением безопасности обрабатываемой информации.
2) Противодействие угрозам безопасности. Свойство обеспечения собственной безопасности присуще всем высокоорганизованным системам как естественного, так и искусственного происхождения и означает способность функционирования в условиях действия факторов, стремящихся нарушить работу системы.
Эти факторы являются угрозой безопасности. 3 вида угроз:
а) угрозы конфиденциальности информации
б) угрозы целостности информации
в) угрозы отказа в обслуживании
Угроза может носить как случайный (объективный) характер, так и целенаправленный (субъективный).
Противодействие объективным угрозам – обеспечение надежности функционирования систем. Противодействие субъективным угрозам – представляет собой основную задачу безопасности. Необходимо учитывать как традиционные, так и новые способы нападения.
Большинство проблем информационной безопасности связано с отстранением человека от непосредственной работы с носителем информации, а также с высокой гибкостью мощных компьютерных технологий, универсальность которых позволяет применять их как в целях защиты, так и нападения.
При таких технологиях пользователь отстраняется от процесса и все полномочия передаются программе, которая обладает некоторой свободой в своих действиях и совсем не обязательно делает то, что приказывает ей пользователь.
Таким образом, возник принципиально новый вид угроз, так называемые троянские кони – это программы, которые обладают деструктивными функциями, маскируя их под полезные функции.
Таким образом, чтобы быть защищенной, компьютерная система должна противостоять многочисленным и разнообразным угрозам безопасности действующим в производстве современных информационных технологий (ИТ).
3) Соответствие стандартам безопасности информационных систем (ИС).
Защищенная система должна соответствовать сложившимся требованям и представлениям. Любой системный обработчик информации. Также необходимо обеспечить возможность сопоставления параметров и характеристик защищенных систем для того, чтобы их можно было сравнивать между собой.
Для этого были разработаны стандарты информационной безопасности в виде соответствующих критериев и требований, регламентирующих подходы к информационной безопасности.
Эти документы определяют понятие защищенной системы (ЗС) посредством стандартизации требований и критериев безопасности.
Образована шкала оценки степени защищенности автоматизированных систем обработки информации.
Наличие таких стандартов позволяет согласовывать подходы различных участников процесса создания защищенной системы и качественно определить уровень безопасности.
Важно заметить, что все критерии носят исключительно необходимый характер безопасности.
Свойства защищенной системы информационной безопасности:
Под защищенной системой обработки информации предполагается понимать систему, которая обладает тремя свойствами:
1) осуществляет автоматизацию некоторого процесса обработки, конфидециальность информации, включая все аспекты этого процесса, связанные с обеспечением безопасности обрабатываемой информации.
2) успешно противостоит угрозам безопасности, действующим в определенной среде.
3) Система соответствует требованиям и критериям стандартов информационной безопасности.
На основе перечисленных свойств сформулируем задачи для создания защищенной системы обработки информации.
1) В ходе автоматизации процесса обработки конфиденциальной информации реализовать все аспекты этого процесса связанные с обеспечением безопасности обрабатываемой информации.
2) Обеспечить противодействие угрозам безопасности, действующим в среде эксплуатации защищенной системы.
3) Реализовать необходимые требования соответствующих стандартов информационной безопасноит.
Методы создания безопасных систем обработки информации.
Любая обработки конфиденциальной информации должна строиться с учетом заведенного порядка работы с документами на каждом предприятии, поэтому порядок работы с документами включает в себя во-первых схему информационных потоков внутри организаций, во-вторых правида управления этими потоками.
Таким образом если основная задача внедрения ИТ – это автоматизировать процесс обработки информации, то частная задача автоматизации процесса обработки конфиденциальной информации – обеспечить адекватную реализацию компьютерной системе схемы конфиденциальных информационных потоков и правил управления ими, существовавших до компьютерной эры.
Решение этой задачи осуществляется за счет определенных действий:
1) определение формального механизма адекватно выражающего заданную схему информационных потоков и правила управления ими.
2) Построение модели безопасности отражающей заданный порядок обработки информации и формальное докозательство ее безопасности.
3) Реализация системы обработки информации в соответствии с предложенной моделью
4) Докозательство адекватности допустимых в автоматизированной системе потоков информации и правил управления доступом.
В ходе осуществления этой последовательности действий возникли следующие проблемы:
1) Схема информационных потоков и правила управления ими могут быть не полными или использовать трудно формулируемые концепции.
2) Схема информационных потоков носит статистических (случайный) характер и определяет разделение информационных потоков только в штатном режиме работы. Такие аспекты, как добавление и удаление компонентов в систему обычно остаются за рамками этой схемы и правил, так как эти операции плохо формализуются.
3) В результате автоматизации в компьютерной системе появляются новые объекты (служебные файлы, другие ресурсы), которые не соответствуют никаким объектам в реальном мире. Соответственно, они не присутствуют в схеме информационных потоков и не учитываются правилами управления этими потоками. Однако, очевидно, что контроль доступа к подобным объектам имеет ключевое значение.
4) В ходе реализации модели безопасности могут появиться не контролируемые потоки информации, поскольку в компьютере пользователь не может манипулировать информацией, а ею управляют стандартные программы, существующие сами по себе. Поэтому возможно возникновение ситуаций типа "троянских коней".
Обзор и сравнительный анализ стандартов информационной безопасности.
Безопасность является качественной характеристикой систем, и у каждой группы специалистов по безопасности имеется свой взгляд на безопасность и средства ее достижения. Следовательно, и о том, что должна представлять собой защищенная система.
Для согласования всех точек зрения на проблему защищенных систем разработаны стандарты информационной безопасности. Это документы, регламентирующие основные понятия и концепции информационной безопасности и в соответствии с этими докуметами ответ звучит так: защищенная система обработки информации – это система отвечающая тому или иному стандарту информационной безопасности, что дает объективную оценку каждой системе.
Основные понятия и определения
Политика безопасности – совокупность норм и правил, обеспечивающих эффективную защиту системы от заданного множества угроз.
Модель безопасности – формальное представление политики безопасности.
Дискреционное (произвольное) управление доступом – управление доступом, осуществляемое на основании заданного администратором множества разрешенных отношений доступа. (Например, в виде троек: объект, субъект, тип доступа).
Мандатное (нормативное) управление доступом – это управление доступом, основанное на совокупности правил доступа, определенных на множестве атрибутов безопасности субъектов и объектов.
Ядро безопасности – совокупность аппаратных, программных и специальных компонент, реализующих функции защиты и безопасности.
Идентификация – процесс распознавания сущностей путем присвоения им уникальных меток.
Аутентификация – проверка подлинности идентификаторов сущности с помощью различных методов.
Адекватность – показатель реально обеспечиваемого уровня безопасности, отражающий степень эффективности и надежности реализованных средств защиты и их соответствие поставленным задачам.
Квалификационный анализ или квалификация уровня безопасности – анализ с целью определения уровня защищенности вычислительной системы с целью определения ее уровня защищенности на основе критериев стандарта безопасности.
Квалификация уровня безопасности является конечным этапом технологического цикла создания защищенных систем и непосредственно предшествует процедуре сертификации.
Таксономия – наука о систематизации и классификации объектов и явлений, имеющих иерархическое строение.
В отличие от классификации, устанавливающей связи и отношения между объектами, таксономия основана на декомпозиции явлений и поэтапном уточнении свойств объекта.
Прямое взаимодейтсвие – принцип организации информационного взаимодействия (в основном между пользователем и системой), гарантирующий, что передаваемая информация не подвергалась перехвату или искажению.
Роль стандартов информационной безопасности
Многие потребители заказывая систему безопасности, не учитывают, что за всё надо платить (деньгами и временем на обработку информации) и кроме того требования безопасности накладывают ограничения на совместимость и ограничивают функциональные возможности вашей прежней системы.
Эксперты по квалификации и специалисты по сертификации рассматривают стандарты как инструмент, позволяющий им оценить уровень безопасности разработанной системы и предоставить потребителям возможность сделать обоснованный выбор. Производители в результате квалификации уровня безопасности получают необходимую объективную оценку возможностей своего продукта.
Таким образом, перед стандартами информационной безопасности стоит задача: примирить различные точки зрения, причем ущемление потребностей хотя бы одной из сторон приведет к невозможности взаимодействия и как следствие, невозможности создания защищенной системы.
Существуют стандарты:
1) Критерий безопасность компьютерных систем министерства обороны США.
2) Руководящие документы Гостехкомиссии России,
3) Европейские критерии безопасности информационных технологий.
4) Федеральные критерии безопасности информационных технологий США.
5) Канадские критерии безопасности компьютерных систем.
6) Разработаны Единые критерии безопасности информационных технологий США.
Есть 4 класса безопасности компьютерных систем.
Группы D (самый низкий уровень) и А (самый высокий уровень безопасности) содержат по 1 классу. Группа С – подклассы С1 и С2, а группа В – В1, В2, В3.
Каждый класс характеризуется различными наборами требований безопасности.
D – минимальная защита.
С – дистриционная защита. Характеризуется наличием произвольного управления доступом и регистрацией действий субъектов.
Класс С1 удовлетворяет требованиям разделения пользователей и информации и включает средства контроля и управления доступом.
Рассчитана на многопользовательские системы, в которых идет обработка данных одного уровня секретности.
С2 – управление доступом системы этого класса более избирательное управление доступом, чем в С1 за счет средств индивидуального контроля за действиями пользователей, регистрации, учета событий и выделения ресурсов.
В – основное требование этой группы – нормативное управление доступом с использованием меток безопасности, поддержка модели и политики безопасности, а также наличие сертификаций и функций для контролирования всех событий, происходящий в системе.
Класс В1 – защита с применением меток безопасности. Системы В1 должны соответствовать всем требованиям, предъявляемым к С2 и поддерживать определенную неформальную модель безопасности, маркировку данных и управление доступом.
В2 – структурированная защита системы. Должна поддерживать формально определенную и четко документированную модель безопасности, предусматривающую произвольное и нормативное управление доступом, которое распространяется по сравнению с классом В1 на все субъекты.
В2 должна осуществлять контроль скрытых каналов утечки информации и в системе домена безопасности выделены элементы, критичные с точки зрения безопасности.
В системе В2 домен безопасности усилены средствами аутентификации.
В3 – домены безопасности.
Для соответствия этому классу система должна поддерживать мониторинг взаимодействий, который контролирует все типы доступа себъектов к объектам.
Система домена безопасности структурирована с целью исключения из нее подсистем, не отвечающих за реализацию функций защиты, быть компактной и иметь хорошие средства для эффективного тестирования.
Свойства аудита должны включать механизмы оповещения администратора при возникновении событий опасных в плане безопасности.
Группа А – верифиционная защита. Характеризуется применением формальных методов верификации, корректности работы механизмов управления доступом (произвольного и нормативного) требуется дополнительная документация, демонстрирующая, что архитектура и реализация отвечают требованиям безопасности.
Класс А1 – формальная ферификация. Система А1 функционально эквивалентна системам В3, но при разработке А1 должны применяться формальные методы верификации, что позволяет с высокой уверенностью получить корректную реализацию функций защиты.
Процесс доказательства адекватности начинается на ранней стадии разработки с построения формальной модели и спецификаций высокого уровня.
Для обеспечения метода верификации система А1 должна содержать более мощные системы управления конфигурацией и защитную процедуру дистрибуции.
Европейские критерии безопасности ИТ.
Европейские критерии рассматривают следующие задачи средств безопасности:
1) Защита информации от несанкционированного доступа с целью обеспечения конфиденциальности.
2) Обеспечение целостност информации посредством защиты от ее несанкционированной модификации или уничтожения.
3) Обеспечение работоспособности систем с помощью противодействия угрозам в отказе и обслуживании.
Европой введено понятие адекватности в отличие от США
Адекватность включает в себя 2 аспекта: эффективность, отражающую соответствие средств безопасности решаемым задачам и корректность, характеризующую процесс их разработки и функционирования.
Эффективность определяется соответствием между задачами, поставленными передс средствами безопасности и реализованным набором функций защиты – их функциональной полнотой и согласованностью простотой использования, а также возможными последствиями использования злоумышленником слабых мест защиты.
А под корректностью понимается правильность и надежность реализаций функций безопасности.
Функциональный критерий.
В Европейских критериях средства безопасности рассматриваются на 3х уровнях.
На 1 уровне рассматриваются цели, которые преследует обеспечение безопасности.
2 уровень содержит спецификации функций защиты
3 уровень содержит реализующие их механизмы.
Спецификации функций защиты рассматриваются с точки зрения следующих требований:
1. Идентификация и аутентификация
2. Управление доступом
3. Подотчетность
4. Аудит
5. Повторное использование объектов.
6. Целостность информации.
7. Надежность обслуживания
8. Безопасность обмена данными
Требование безопасности обмена данными регламентирует работу средств, обеспечивающих безопасность данных, передаваемых по каналам связи и включают в себя следующие разделы:
1) аутентификация
2) управление доступом
3) конфиденциальность данных
4) целостность данных
5) невозможность отказаться от совершенных действий.
Набор функций безопасности распределен по 10 классам:
5 классов F-C1, F-C2, F-B1, F-B2, F-B3
Класс F-IN предназначен для систем с высшими требованиями в обеспечение целостности, что важно для систем баз данных.
Здесь различаются следующие виды доступа:
– чтение/запись
– добавление/удаление
– создание, переименование и выполнение объектов
F-AV характеризуется повышенными требованиями к обеспечению работоспособности. Это важно для систем управления технологическими процессами.
Система должна восстанавливаться после отказа отдельного аппаратного компонента таким образом, чтобы все критически важные функцие постоянно оставались доступными. В таком же режиме должна происходить и замена компонент системы.
Не зависимо от уровня загрузки должно гарантироваться определенное время реакции системы на внешние события.
F-DI – этот класс ориентирован на распределенные системы обработки информации. Перед началом обмена и при получении данных стороны должны иметь возможность провести идентификацию участников взаимодействий и проверить ее подлинность. Должны использоваться средства контроля и исправления ошибок, т.е. при пересылке данных должны обнаруживаться все случайные или намеренные искажения адресной и пользовательской информации.
Знание алгоритма обнаружения искажений не должно позволять злоумышленнику производить нелегальную модификацию передаваемых данных.
Должны обнаруживаться попытки повторной передачи ранее переданных сообщений.
FDC. Этот класс уделяет особое внимание и конфиденциальности передаваемой информации. Информация по каналу связи должна передаваться в шифрованном виде, ключи должны храниться в защищенных от несанкционированного доступа местах.
F-DX предъявляет повышенные требования к целостности и конфиденциальности информации.
Это объединение классов F-DI и F-DS с дополнительными возможностями шифорования и защиты от анализа трафика.
Д.б. ограничивает доступ к ранее переданной информации, которая может способствовать проведению криптоанализа.
Руководящие документы Гостехкомитета (ГТХ) России
Основные положения:
Существует 5 руководящих документов, посвязенных вопросам защиты от несанкционированного доступа к информации.
Важнейшие из них:
- Концепция защиты средств вычислительной техники от несанкционированного доступа к информации
- Средства вычислительной техники. Защита от несанкционированного доступа к информации. Показатели защищенности от несанкционированного доступа к информации.
- Автоматическое управление системы. Защита от несанкционированного доступа к информации, классификация автоматизированных систем и требования по защите информации.
Идейной основой всех документов является 1-ый документ, содержащий систему взглядов Техгоскомитета на проблемы информационной безопасности.
С точки зрения разработчиков основная задача – обеспечение защиты от несанкционированного доступа.
Определенный уклон в сторону поддержания секретности объясняется тем, что эти документы были разработаны в расчете на применение в информационных системах Министерства Обороны и спецслужб.
Руководящие документы Гостехкомитета предлагают 2 группы критериев безопасности:
1) показатели защищенности средств вычислительной техники (СВТ) от несанкционированного доступа.
2) критерии защищенности автоматизированных систем обработки данных.
Первая группа позволяет оценить степень защищенности только по одному из параметров, отдельно поставляемых потребителю компонент вычислительных средств.
Вторая расчитана на полнофункциональные системы обработки данных.
Показатели защищенности средств вычислительной техники от несанкционированного доступа
Этот документ устанавливает классификацию СВТ по уровню защищенности от НСД на базе перечня показателей защищенности и совокупности их требований.
Под средствами вычислительной техники понимается совокупность программных и технических элементов систем обработки данных, способных функционировать самостоятельно или в составе других систем.
Эти показатели содержат требования защищенности и применяются к общесистемным программным средствам и операционным системам (с учетом архитектуры ЭВМ).
Конкретные перечни показателей определяют классы защищенности средств вычислительной техники и описываются совокупностью требований. Установлено 7 классов защищенности средств вычислительной техники (низший – 7 класс).
Требования к защищенности автоматизированных систем. Эти требования являются составной частью систем защищенности обработки информации. В отличие от остальных стандартов отсутствует раздел, содержащий требования по обеспечению работоспособности системы, но присутствует раздел, посвященный криптографическим средствам. Другие стандарты информационной безопасности не осдержат упоминания о криптографии, так как рассматривают её в качестве механизма защиты реализующего требования аутентификации, контроля целостности. Исключение: стандарт "Единый критерий".
Классы защищенности автоматизированных систем.
Документы Гостехкомитета устанавливают 10 классов защищенности автоматизированной системы (АС) от несанкционированного доступа, каждый из которых характеризуется совокупностью требований к средствам защиты.
Классы подразделяются на 3 группы. Группы определяются на основе следующих критериев:
- наличие в автоматизированной системе информации различного уровня конфиденциальности;
- уровень полномочий пользователей автоматизированной системы на доступ к конфиденциальной информации;
- режим обработки данных в автоматизированной сисиеме (коллективный или индивидуальный).
В пределах каждой группы соблюдается иерархия классов защищенности автоматизированной системы.
Класс, соответствующий высшей степени защищенности для данной группы обозначается так: №А (№ - номер группы 1..3). Следующий класс №Б, …
3-я группа включает автоматизированные системы, в которых работает один пользователь, допущенный ко всей информации автоматизированной системы, размещенной на носителях одного уровня конфиденциальности. Эта группа имеет 2 подкласса: 3А и 3Б.
2-я группа включает автоматизированные системы, в которых пользователи имеют одинаковые полномочия доступа ко всей2 информации, обрабатываемой или хранимой в автоматизированной системе на носителях различного уровня. 2 класса: 2Б и 2А.
1-я группа включает многопользовательские АС, в которых одновременно обрабатывается или хранится информация разных уровней конфиденциальности. Не все пользователи имеют равные права доступа. Группа содержит 5 классов: 1А, Б, В, Г, Д.
К недостаткам этого стандарта можно отнести отсутствие требований к защите от угроз работоспособности, ориентацию на противодейтсвие несанкционированному доступу и отсутствие требований адекватности реализаций политики безопасности.
Политика безопасности трактуется исключительно как поддержание режима секретности и отсутствие несанкционированного доступа. Из-за этого средства защиты ориентируются исключительно на противодействие внешним угрозам.
Криптография – это искусство проектирования и взлома секретных систем.
Взлом – криптографический анализ (криптоанализ). Специалисты по криптоанализу – криптоаналитики (аналитики).
Кодирование – способ представления информации. Информация здесь не несет тайного характера, а просто нужно передать преобразование информации.
Шифры замены и перестановки.
Появились задолго до изобретения компьютера, получили широкое распространение алгоритмы, которые выполняли либо замену одних букв на другие, либо переставляли буквы друг с другом, или делали одновременно и то, и другое.
Шифром замены называется алгоритм шифрования, который производит замену каждой буквы открытого текста на какой-то символ открытого текста. Получатель сообщения расшифровывает его путем обратной замены.
В классической криптографии раличают 4 разновидности шифров замены:
1) простая замена (одноалфавитный шифр): каждая буква открытого текста заменяется на один и тот же символ шифрованного текста.
2) омофонная замена. Аналогична простой замене, но с отличием: каждой букве открытого текста ставится в соответствие несколько символов шифротекста.
3) блочная замена – шифрование открытого текста производится блоками и например, блоку, состоящему из 3-х символов будет соответствовать блок, состоящий из 3х других символов.
4) многоалфавитная замена. Состоит из нескольких шифров простой замены, например могут использоваться 5 шифров простой замены, а какой конкретно из них применяется для шифрования данной буквы открытого текста зависит от ее положения в тексте.
Примером шифра простой замены служит программаROT13 (bunix). Эта программа циклически сдвигает каждую букву латинского алфавита на 13 позиций вправо, чтобы восстановить исходный текст, нужно эту программу применить дважды. P=(ROT13(P)) (в английском алфавите 26 букв).
Все упомянутые шифры замены легко взламываются с использованием компьютеров, поскольку замена не достаточно хорошо маскирует стандартные частоты встречаемости букв в открытом тексте.
В шифре перестановки буквы открытого текста не замещаются на другие, а меняется сам порядок их следования. Например, в шифре послание может записываться как строки определенной матрицы, а читаться по столбцам.
Хотя в современных криптосистемах эти алгоритмы используются, но их применение ограничено и рассмотренные ранее шифры замены получили более широкое распространение.
Одноразовый блокнот – особый вид шифрования (каждая буква может переходить в каждую). Шифр одноразового блокнота – абсолютно не вскрываемый способ шифрования, он представляет собой очень длинную последовательность случайных букв, расписанную на листах бумаги, которые скреплены между собой в блокнот.
После шифрования блокнот уничтожается, а получатель, владеющий копией, восстанавливает текст путем сложения шифра текста и букв из одноразового блокнота.
При отсутствии сведений об одноразовом блокноте, перехваченному шифрованному сообщению с одинаковой вероятностью соответствует произвольный открытый текст той же длины, что и сообщение.
Недостаток: последовательность букв одноразового блокнота должна быть действительно случайной, а не псевдослучайной, поскольку любая атака на этот шифр будет в первую очередь направлена против метода генерации содержимого блокнота.
Дважды блокнотом пользоваться нельзя.
Роторные машины были изобретены в 20е годы. Состояли из клавиатуры для ввода текста и набора роторов – вращающихся колес, каждое из которых реализовывало простую замену. При этом выходные контакты одноо ротора присоединялись к входным контактам следующего за ним, тогда, если на клавиатурей 4ой роторной машины нажималась А, то 1ый ротор мог ее превратить в Ф, 2ой – в К, 3-ий…
После этого роторы поворачивались,и следующий раз замена была иной. Для суложнения ситуации роторы вращались с разной скоростью.
М – шифруемое сообщение, К – ключ, В – шифрованное сообщение.
Шифрование и дешифровка выполняются одной и той же программой. Алгоритм обладает слабой стойкостью, но Агенство Национальной Безопасности одобрило его использование в цифровых сотовых телефонах американских производителей для засекречивания речевых переговоров. Он также часто встречается в различных коммерческих программных продуктах и шифруя таким способом, удается быстро зашифровать информацию от несведущего человека, но специалист её быстро взломает. И делается это следующим образом: пусть текст будет написан на английском языке.
1) Необходимо определить длину ключа. Для этого шифрованный текст последовательно складывается по модулю 2 со своей копией, сдвинутой на различное число байтов. И в полученном векторе n отсчитывается число совпадающих компонентов. Когда величина сдвига кратна длине ключа, это число совпадений превысит 6% от общей длины исследуемого шифрованного текста. Если не кратно, то совпадений будет меньше, чем 0,4%. Проанализировав полученные данные, можно сделать обоснованный вывод о длине ключа.
2) Затем надо сложить шифрованный текст по модулю 2 со своей копией, сдвинутой на величину длины ключа. Эта операция анулирует ключ и оставит в наличии открытый текст сообщения, сложенный по модулю 2 со своей копией, сдвинутой на величину длины ключа.
Потоков
ые шифры. Пусть А и В – алгоритмы открытого и шифрованного текста, ключ – это инъективное (взаимно одноименное) отображение из А в В. Ключ называется фиксированным, если это отображение одно и то же для каждого элемента из А. В противном случае ключ называется переменным.
f – отображение каждого элемента и з А, как элемента В.
Отображение а ®(a×n+k)mod m кольца Zm в себя. m – длина алфавита (26 для латиницы)
Z+3 = С.
При фиксированных n и k из множества Zm и при условии, что наибольший общий делитель между m и n равен единице называется модулярным шифром.
m =
Одноалфавитные подстановки используют только 1 ключ, и их можно легко взломать, наблюдая частоту распределения символов в шифрованном тексте, поскольку имеются таблицы различных частот букв в различных языках
0) a – 7,3 1) b – 0,9 2) c – 3,0 3) d – 4,4 4) e – 1,3 5) f – 2,8
6) g – 1,6 7) h – 3,5 8) i – 7,4 9) j – 0,2 10) k – 0,3 11) l – 3,5
12) m – 2,5 13) n – 7,8 14) o – 7,4 15) p – 2,7 16) q – 0,3 17) r – 7,7
18) s – 6,3 19) t – 9,3 20) u – 2,7 21) v – 1,3 22) w – 1,6 23) x – 0,5
24) y – 1,9 25) z – 0,1
Кроме того, можно анализировать диаграфы сочетаний встречания пар букв. Есть тоже харакреные пары.
Одноалфавитный шифр может быть усилен, если используем многоалфавитный шифр подстановки, скрывающий частоты букв за счет кратных подстановок. В этом случае при шифровании используется более одного алфавита, и ключ включает указание, какая подстановка должна использоваться для каждого символа. Эти шифры называются шифрма Вижинера.
Многоалфавитный шифр подстановки с периодом р состоит из Р шифровальных алфавитов Bi и отображений fi, определяемых ключом.
Ключ – это чаще всего слово (предложение) K=K1, K2 ... Kp и отображение получается следующим образом: fi(a)=(a+Ki)mod m. Открытое сообщение зашифровывается как f1(a1) f2(a2) ... fn(an). Если n больше длины люча, будет повторное использование ключа.
Для шифрования может использоваться квадрат Вижинера.
для шифрования Плэйфера
j выбрасываем, чтобы получить полный квадрат
Вижинер:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 |
| a | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z |
| b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z | a |
| c | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z | a | b |
| d | e | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z | a | b | c |
| e | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z | a | b | c | d |
| f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z | a | b | c | d | e |
| g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z | a | b | c | d | e | f |
| h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z | a | b | c | d | e | f | g |
| i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z | a | b | c | d | e | f | g | h |
| j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z | a | b | c | d | e | f | g | h | i |
| k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z | a | b | c | d | e | f | g | h | i | j |
| l | m | n | o | p | q | r | s | t | u | v | w | x | y | z | a | b | c | d | e | f | g | h | i | j | k |
| m | n | o | p | q | r | s | t | u | v | w | x | y | z | a | b | c | d | e | f | g | h | i | j | k | l |
| n | o | p | q | r | s | t | u | v | w | x | y | z | a | b | c | d | e | f | g | h | i | j | k | l | m |
| o | p | q | r | s | t | u | v | w | x | y | z | a | b | c | d | e | f | g | h | i | j | k | l | m | n |
| p | q | r | s | t | u | v | w | x | y | z | a | b | c | d | e | f | g | h | i | j | k | l | m | n | o |
| q | r | s | t | u | v | w | x | y | z | a | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p |
| r | s | t | u | v | w | x | y | z | a | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | q |
| s | t | u | v | w | x | y | z | a | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r |
| t | u | v | w | x | y | z | a | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r | s |
| u | v | w | x | y | z | a | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t |
| v | w | x | y | z | a | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u |
| w | x | y | z | a | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v |
| x | y | z | a | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w |
| y | z | a | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x |
| z | a | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y |
Процедура дешифровки выглядит следующим образом: число, соответствующее iой буквы открытого текста получается прибавлением по модулю m (26) числа, соотвутствующего i-ой по модулю "р" букве ключа.
Шифры вижинера считались невзламываемыми, но в XIX в. прусский офицер нашел простой теоретико-числовой метод поиска длины ключа. В многоалфавитных шифрах также, как в шифре Цезаря, применяется сдвиг, но длина сдвига меняется обычно периодически. Изменение сдвигов выравнивает частоты букв, делая невозможным анализ частот букв, но характеристические частоты сохраняются в последовательнстях зашифрованного сообщения, соответствующих повторениям в ключевой последовательности.
Если удается определить длину периода ключа, то можно определить буквы с помощью частотного анализа. Период ключа может быть обнаружен поиском повторяющихся блоков в шифрованном текста. Часть из них носит случайный характер, но основная масса получается из соответствия между повторяемыми словами или подсловами в открытом тексте и повторами в последовательности ключа. Когда это имеет место, расстояние между повторами будет кратным периоду ключа
Другим вариантом многоалфавитных подстановочных шифров являются шифры с автоматическим выбором ключа, когда само сообщение (открытый или шифрованный текст) используется в качестве ключа.
Для запуска шифра используется короткий затравочный ключ (обычно 1 буква), этот ключ предложен Кордано.
: с – константа, n и m – взаимно простые.
Второй способ шифрования с автоматическим выбором ключа испльзует в качестве ключа шифрованный текст
.
Шифр бегущего ключа Вижинера использует в качестве ключа неповторяющийся текст. Первоначально эти шифры считались невзламываемыми, но в конце XIX в. было найдено общее решение для многоалфавитных подстановок без ограничений на тип или длину ключа. Наиболее значительный вариант шифра Вижинера был предложен в 1918 году американским инженером.
Сообщение тогда передавалось с использованием двоичного кода и было предложено прибавлять по модулю 2 случайные последовательности точек и пробелов так, чтобы вся частотная информация, корреляция между символами, периодичность и т.п. терялись.
Главный недостаток этой процедуры состоит в том, что она требует обмена огромным количеством ключей заблаговременно (один символ ключа на каждый символ сообщения).
Сначала предполагалось использовать или короткий ключ или линейную комбинацию коротких ключей, но оба подхода оказались уязвимыми.
Естественным выводом из анализа предлагаемых алгоритмов для абсолютно невзламываемых шифров является вывод об использовании шифра одноразовых блокнотов.
Таким образом, сохранность информации возрастает при длижении от шифра Цезаря к шифру одноразового блокнота и одновременно возрастает длина ключа. В невзламываемой системе все сообщения равновероятностны, только тогда шифр неразрешим.
Следующим подходом к шифрованию является разработка полиграфовых систем – это блочные шифры, рассматривающие одновременно группы символов открытого текста.
Блочные шифры разрабатывались с целью помешать криптоанализу по частотному подходу и для ручного шифрования обычно используются диаграфовые методы.
Вернемся к матрице. Шифрование можно осуществлять, сдвигая символ в любом направлении на любое количество позиций. Из сочетания различных сдвигов складывается многоалфавитный шифр.
Также можно записать весь алфавит в вершинах 4 кубов, и осуществлять сдвиги внутри этих кубов.
Шифр Хилла.
Хилл выяснил, что все современные криптосистемы могут быть сформулированы в единой модели линейных преобразований пространства сообщений.
Пусть К есть матрица размера n´n. a и d – n-мерные вектора из множества Zm (целые). Шифр Хилла – это отображение
(T - транспонир).
Однозначное тогда и только тогда, когда НОД между детерминантом матрицы К и числом m =1. Все операции выполняются по модулю m.
Для шифрования открытый текст подразделяется на блоки по n символов, каждая буква заменяется соответствующим кей излементом из множества Zm, затем образуем транспонированные вектор-столбцы и применяем данное линейное преобразование к каждому блоку
.
В этом контексте используются матрицы инволюций К, являющиеся своими обратными, т.е. К2mod26=I è det(K)=±1
Пытаясь определить матрицы инволюций, когда размерность n=2, а m=26 и если взять, что определитель =±1. При определителе 1 матриц 2´2 есть 8, -1 – 736.
При этом всё равно криптограмма может быть дешифрована даже если неизвестно ни одного слова min длины из открытого текста.
Определяются и пробуются все матрицы инволюций, но для больших значений n этим методом проб и ошибок достичь результата уже невозможно.
Заменяя постоянную матрицу K матрицей с переменными элементами, получаем разновидность предложенной Хиллом схемы.
В оценках надежности любой системы необходимо предполагать худший случай, а именно, противник может иметь доступ к любой информации кроме шифра и, соответственно, рассматриваются такие случай:
1) анализ только шифрованного текста
2) анализ известного открытого текста, т.е. противник имеет несколько пар открытый текст-шифрованный текст, с которыми он может работать.
3) анализ выбранного открытого текста. В этом случае противник может передавать системе неограниченные порции открытоого текста и может наблюдать соответствующий шифрованный текст.
Поэтому только система одноразового блокнота безоговорочно надежна, что означает, что независимо от применяемых вычислительных мощностей вскрыть систему не удастся.
Математические проблемы могут быть разделены на 2 основные категории: разрешимые и неразрешимые проблемы. Неразрешимая проблема – проблема останова "машины Тьюринга" – некоторая гипотетическая машина.
Эта проблема эквивалентна следующей проблеме: цирюльник бреет всех, кто не бреется сам, бреет ли он себя? Если бреет, то не бреет, а если не бреет, то бреет.
Разрешимые проблемы могут быть подразделены на следующие ситуации:
1) Труднодоказуемые проблемы, имеющие лишь экспоненциальное время счета (решения) O(2n)
2) P-проблема, которая имеет полиномиальное время решения O(nk)<O(2n)
3) NP-проблема, для которой известны только экспоненциальные алгоритмы, но не доказано, что алгоритма с полиномиальным временем не существует.
Воспользовавшись идеями современной криптографии, рассмотрим блочные шифры, действующие на группы битов и проанализируем работу электронных устройств.
Рассмотрим случай, когда мы имеем только 3 бита, с помощью которых можно представить всего 8 объектов. Устройство называется ящиком подстановки или S-ящиком.
Устройство подстановки состоит из 2х переключателей. Первый преобразует последовательность 3х битов в соответствующее ей значение по основанию 8. Подавая таким образом энергию на любую из 8 выходящих линий, эти 8 линий могут быть соединены со вторым переключателем любим из 8! способов.
Роль второго переключателя состоит в том, что он должен преобразовать вход, представляемый одной цифрой по основанию 8 снова в 3х битный выходной сигнал.
Предположим, что мы увеличим число входных битов с 3х до 5, т.5. можно представлять сразу все буквы русского либо латинского алфивита, тогда существует уже 32! возможностей конфигураций в соединении этих 2х переключателей.
Однако получающийся шифр всё еще остается слабым, т.к. он анализируется по частоте символов. Проблема состоит в том, что несмотря на большое количество возможных конфигураций, имеется только 32 возможных входа и выхода.
Ясно, что одно устройство со многими входами и выхоами само является Р-ящиком (ящиком перестановок) и Р-ящик имеет 8 входов и 8 выходов. S-ящик 0 это нелинейное устройство, а Р-ящик – линейное.
Чтобы улучшить эту схему, мы должны внести так называемые системы шифропроизведений, комбинируя P и S-ящики.
Впервые системы шифропроизведений были предложены Шеноном. Они состоят из слоев P и S-ящиков.
Предположим, что Р-ящики имеют 15 входов/выходов. За ними следует 5 S-ящиков и операции в системе шифров-произведений выполняются при условии, что вход состоит из 14 нулей и одной единицы. Первый ящик Р передает единственную единицу некоторому S-ящику, который являясь нелинейным устройством, может из одной единицы сделать до 3х единиц на своем выходе, затем эти единицы подаются на следующий Р-ящик, который перетасовывает их и подает на следующие S-ящики, и процесс повторяется. В конце выход содержит сбалансированное число нулей и единиц. Такой принцип реализован в системе IBM-"Люцифер", где Р ящики иеют по 64 или 128 входов, а S-ящики – по 4. Цель разработчика состоит в том, чтобы сделать для противника как можно более сложной задачу проследить обратный путь и таким образом восстановить ключи перестановок на S и Р ящиках.
Система "Люцифер" является блочным шифром высокой пробы, однако в настоящее время она не считается достаточно надежной. В 1977 году национальное бюро стандартов выпустило стандарт шифрования данных DES. DES – блочный шифр, разработанный фирмой IBM на основе S-P ящиков. Шифрование осуществляется блоками по 64 бита и проводится за 16 отдельных этапов, хотя с точки зрения сложности DES выглядит надежным, но размер ключа 48 бит подвергается критике. Дело в том, что 56-битный ключ взламывается путем анализа известного открытого текста с использованием больших, но реальных вычислительных ресурсов (256 ключей).
Основные идеи цифровой подписи
Односторонней функцией с ловушкой называется функция Fk, которая производит отображение Х в У в зависимости от параметра К и обладает 3 свойствами: FK:XàY
1) При любом К существует полиномиальный алгоритм вычисления значений FK(X)
2) При неизвестном К не существует полиномиального алгоритма инвертирования фукции FK
3) При известном К существует полиномиальный алгоритм инвертирования FK
В совреенной криптографии используется понятие числового поля и конечного поля. Рассмотрим основные свойства операций сложения и умножения на множестве действительных чисел.
Поле – числовое множество, на котором выполнимы определенные действия + и
´.
Аксиомы поля:
(1) Для любых 3х элементов a,b,cÎF a+(b+c)=(a+b)+c
(2) В множестве F есть такой элемент 0, что для каждого aÎF a+0=0+a=a
(3) Для каждого элемента аÎF существует противоположный элемент х, такой, что а+х=х+а=0
(4) Для каждых 2х элементов a,bÎF a+b=b+a
(5) Для каждых 3х элементов a,b,cÎF a×(b×c)=(a×b)×c
(6) Во множестве F есть элемент 1¹0, такой, что для любого aÎF 1×a=a×1=a
(7) Для каждого aÎF¹0 существует обратный элмент х, такой, что а×х=х×а=1
(8) Для каждых 2х элементов a,bÎF a×b=b×a
(9) Для любых 3х элементов a,b,cÎF a(b+c)=ab+ac
Полем называется множество F с двумя отображениями (операциями), каждая из которых сопоставляет любой паре элементов из F однозначно определенный третий элемент из F, и эти отображения (+, ´) удовлетворяют девяти аксиомам, рассмотренным выше.
Для криптографии особенно важными являются конечные поля, поле же множества действительных чисел бесконечно.
Сконструируем конечное поле. Пусть Р – простое число. Рассмотрим множество чисел: {0, 1, 2, ... P-1}. На этом поле применимы операции + и ´ по модулю Р.
Функция Эйлера j(n) – количество неотрицательных целых чисел, меньших n и взаимно простых с n [n=15 1,2,3,4,5,6,7,8,9,10,11,12,13,14 /8: j(15)=8.
15=3×5 j(15)=15×(1-
)×(1-
) j(n)=n×(1-
)×(1-
)...]
Теорема Ферма:
Пусть р – простое число, а а– число взаимно простое с р, тогда ар-1º1 mod p
Теорема Эйлера: Пусть a и n – взаимно простые числа, тогда аj(n)º1 mod n
Ассиметричные криптосистемы
Система
RSA.
Получатель вычисляет следующие величины:
p и q – два больших простых числа, которые держатся в секрете, Е – случайное целое число. n=p×q – открытое число. Это помещается в справочник для переписки. Е также помещается в открытый каталог и используется для шифрования сообщений. Е обладает одним свойством: НОД(Е,j(n)
)=1.
D – тайное число. Целое, используемое получателем для дешифровки. D выбирается как мультипликативное обратного числа E по модулю j(n): (D×E)
mod
j(n)=1.
Эта мультипликативная обратная существует, когда:
Теорема: Пусть А принадлежит множеству Zm (целые), тогда А имеет мультипликативный обратный по модулю n элемент в том и только том случае, когда НОД (gcd) a и n =1.
Итак, М – сообщение; n и Е – открытый ключ шифрования; p, q и D – секретные ключи дешифровки.
Отправитель знает М и каждый желающий знает открытый ключ n и Е.
Сообщение М преобразуется в цифровую форму. Если число n достаточно большое, то шифровать можно целыми строками (n–1>M). Длинное сообщение разбивается на блоки, и длина блока такова, что его числовое значение не превосходит n. Отправитель берет каждый блок в сообщении Мi (каждый блок – некоторое большое число) и шифрует следующим образом:
. Это попадает в канал связи. Получатель, получивший сообщение Ci вычисляет 
, так как 
.
Если шифровать по одной букве, то частотность букв сохраняется, поэтому сообщение шифруется блоками, для этого p и q должны быть достаточно большими. D и Е не имеет смысла брать большими, поскольку они не влияют на дешифровку.
Идеи цифровой подписи
Чтобы знать, от кого точно поступает сообщение, существуют некоторые хитрости. В системах наличествуют датчики, которые фиксируют определенные действия, но при этом эти датчики могут менять злоумышленники, поэтому датчики должны посылать авторизированный сигнал (подтверждение личности). Для этого требуется цифровая подпись. Если посылается письмо, можно зашифровать какую-то фразу определенным образом, и она будет являться признаком того, что это именно вы написали это письмо.
Отправитель: ЕА, DА, nА, pАqА
Получатель: ЕВ, DВ, nВ, pВqВ
Сообщение М, к нему применяется DА, DА(М) – это шифруем ЕВ(DА(М)) и это отправляется.
Получатель своим тайным шифром дешиврует и получает DВ(ЕВ(DА(М)))=DА(М), понимает, от кого это сообщение, применяет ЕА. Если получается нормальное сообщение М, значит сообщение действительно зашифровал именно тот отправитель.
Второй способ шифрования с автоматическим выбором ключа испльзует в качестве ключа шифрованный текст
Шифр бегущего ключа Вижинера использует в качестве ключа неповторяющийся текст. Первоначально эти шифры считались невзламываемыми, но в конце XIX в. было найдено общее решение для многоалфавитных подстановок без ограничений на тип или длину ключа. Наиболее значительный вариант шифра Вижинера был предложен в 1918 году американским инженером.
Сообщение тогда передавалось с использованием двоичного кода и было предложено прибавлять по модулю 2 случайные последовательности точек и пробелов так, чтобы вся частотная информация, корреляция между символами, периодичность и т.п. терялись.
Главный недостаток этой процедуры состоит в том, что она требует обмена огромным количеством ключей заблаговременно (один символ ключа на каждый символ сообщения).
Сначала предполагалось использовать или короткий ключ или линейную комбинацию коротких ключей, но оба подхода оказались уязвимыми.
Естественным выводом из анализа предлагаемых алгоритмов для абсолютно невзламываемых шифров является вывод об использовании шифра одноразовых блокнотов.
Таким образом, сохранность информации возрастает при длижении от шифра Цезаря к шифру одноразового блокнота и одновременно возрастает длина ключа. В невзламываемой системе все сообщения равновероятностны, только тогда шифр неразрешим.
Следующим подходом к шифрованию является разработка полиграфовых систем – это блочные шифры, рассматривающие одновременно группы символов открытого текста.
Вернемся к матрице. Шифрование можно осуществлять, сдвигая символ в любом направлении на любое количество позиций. Из сочетания различных сдвигов складывается многоалфавитный шифр.
Также можно записать весь алфавит в вершинах 4 кубов, и осуществлять сдвиги внутри этих кубов.
Шифр Хилла.
Хилл выяснил, что все современные криптосистемы могут быть сформулированы в единой модели линейных преобразований пространства сообщений.
Пусть К есть матрица размера n´n. a и d – n-мерные вектора из множества Zm (целые). Шифр Хилла – это отображение
Однозначное тогда и только тогда, когда НОД между детерминантом матрицы К и числом m =1. Все операции выполняются по модулю m.
Для шифрования открытый текст подразделяется на блоки по n символов, каждая буква заменяется соответствующим кей излементом из множества Zm, затем образуем транспонированные вектор-столбцы и применяем данное линейное преобразование к каждому блоку
В этом контексте используются матрицы инволюций К, являющиеся своими обратными, т.е. К2mod26=I è det(K)=±1
Пытаясь определить матрицы инволюций, когда размерность n=2, а m=26 и если взять, что определитель =±1. При определителе 1 матриц 2´2 есть 8, -1 – 736.
При этом всё равно криптограмма может быть дешифрована даже если неизвестно ни одного слова min длины из открытого текста.
Определяются и пробуются все матрицы инволюций, но для больших значений n этим методом проб и ошибок достичь результата уже невозможно.
Заменяя постоянную матрицу K матрицей с переменными элементами, получаем разновидность предложенной Хиллом схемы.
В оценках надежности любой системы необходимо предполагать худший случай, а именно, противник может иметь доступ к любой информации кроме шифра и, соответственно, рассматриваются такие случай:
1) анализ только шифрованного текста
2) анализ известного открытого текста, т.е. противник имеет несколько пар открытый текст-шифрованный текст, с которыми он может работать.
3) анализ выбранного открытого текста. В этом случае противник может передавать системе неограниченные порции открытоого текста и может наблюдать соответствующий шифрованный текст.
Поэтому только система одноразового блокнота безоговорочно надежна, что означает, что независимо от применяемых вычислительных мощностей вскрыть систему не удастся.
Математические проблемы могут быть разделены на 2 основные категории: разрешимые и неразрешимые проблемы. Неразрешимая проблема – проблема останова "машины Тьюринга" – некоторая гипотетическая машина.
Эта проблема эквивалентна следующей проблеме: цирюльник бреет всех, кто не бреется сам, бреет ли он себя? Если бреет, то не бреет, а если не бреет, то бреет.
Разрешимые проблемы могут быть подразделены на следующие ситуации:
1) Труднодоказуемые проблемы, имеющие лишь экспоненциальное время счета (решения) O(2n)
2) P-проблема, которая имеет полиномиальное время решения O(nk)<O(2n)
3) NP-проблема, для которой известны только экспоненциальные алгоритмы, но не доказано, что алгоритма с полиномиальным временем не существует.
Воспользовавшись идеями современной криптографии, рассмотрим блочные шифры, действующие на группы битов и проанализируем работу электронных устройств.
Рассмотрим случай, когда мы имеем только 3 бита, с помощью которых можно представить всего 8 объектов. Устройство называется ящиком подстановки или S-ящиком.
Роль второго переключателя состоит в том, что он должен преобразовать вход, представляемый одной цифрой по основанию 8 снова в 3х битный выходной сигнал.
Предположим, что мы увеличим число входных битов с 3х до 5, т.5. можно представлять сразу все буквы русского либо латинского алфивита, тогда существует уже 32! возможностей конфигураций в соединении этих 2х переключателей.
Однако получающийся шифр всё еще остается слабым, т.к. он анализируется по частоте символов. Проблема состоит в том, что несмотря на большое количество возможных конфигураций, имеется только 32 возможных входа и выхода.
Ясно, что одно устройство со многими входами и выхоами само является Р-ящиком (ящиком перестановок) и Р-ящик имеет 8 входов и 8 выходов. S-ящик 0 это нелинейное устройство, а Р-ящик – линейное.
Чтобы улучшить эту схему, мы должны внести так называемые системы шифропроизведений, комбинируя P и S-ящики.
Предположим, что Р-ящики имеют 15 входов/выходов. За ними следует 5 S-ящиков и операции в системе шифров-произведений выполняются при условии, что вход состоит из 14 нулей и одной единицы. Первый ящик Р передает единственную единицу некоторому S-ящику, который являясь нелинейным устройством, может из одной единицы сделать до 3х единиц на своем выходе, затем эти единицы подаются на следующий Р-ящик, который перетасовывает их и подает на следующие S-ящики, и процесс повторяется. В конце выход содержит сбалансированное число нулей и единиц. Такой принцип реализован в системе IBM-"Люцифер", где Р ящики иеют по 64 или 128 входов, а S-ящики – по 4. Цель разработчика состоит в том, чтобы сделать для противника как можно более сложной задачу проследить обратный путь и таким образом восстановить ключи перестановок на S и Р ящиках.
Система "Люцифер" является блочным шифром высокой пробы, однако в настоящее время она не считается достаточно надежной. В 1977 году национальное бюро стандартов выпустило стандарт шифрования данных DES. DES – блочный шифр, разработанный фирмой IBM на основе S-P ящиков. Шифрование осуществляется блоками по 64 бита и проводится за 16 отдельных этапов, хотя с точки зрения сложности DES выглядит надежным, но размер ключа 48 бит подвергается критике. Дело в том, что 56-битный ключ взламывается путем анализа известного открытого текста с использованием больших, но реальных вычислительных ресурсов (256 ключей).
Основные идеи цифровой подписи
Односторонней функцией с ловушкой называется функция Fk, которая производит отображение Х в У в зависимости от параметра К и обладает 3 свойствами: FK:XàY
1) При любом К существует полиномиальный алгоритм вычисления значений FK(X)
2) При неизвестном К не существует полиномиального алгоритма инвертирования фукции FK
3) При известном К существует полиномиальный алгоритм инвертирования FK
В совреенной криптографии используется понятие числового поля и конечного поля. Рассмотрим основные свойства операций сложения и умножения на множестве действительных чисел.
Поле – числовое множество, на котором выполнимы определенные действия + и
´.
Аксиомы поля:
(1) Для любых 3х элементов a,b,cÎF a+(b+c)=(a+b)+c
(2) В множестве F есть такой элемент 0, что для каждого aÎF a+0=0+a=a
(3) Для каждого элемента аÎF существует противоположный элемент х, такой, что а+х=х+а=0
(4) Для каждых 2х элементов a,bÎF a+b=b+a
(5) Для каждых 3х элементов a,b,cÎF a×(b×c)=(a×b)×c
(6) Во множестве F есть элемент 1¹0, такой, что для любого aÎF 1×a=a×1=a
(7) Для каждого aÎF¹0 существует обратный элмент х, такой, что а×х=х×а=1
(8) Для каждых 2х элементов a,bÎF a×b=b×a
(9) Для любых 3х элементов a,b,cÎF a(b+c)=ab+ac
Полем называется множество F с двумя отображениями (операциями), каждая из которых сопоставляет любой паре элементов из F однозначно определенный третий элемент из F, и эти отображения (+, ´) удовлетворяют девяти аксиомам, рассмотренным выше.
Для криптографии особенно важными являются конечные поля, поле же множества действительных чисел бесконечно.
Сконструируем конечное поле. Пусть Р – простое число. Рассмотрим множество чисел: {0, 1, 2, ... P-1}. На этом поле применимы операции + и ´ по модулю Р.
Функция Эйлера j(n) – количество неотрицательных целых чисел, меньших n и взаимно простых с n [n=15 1,2,
15=3×5 j(15)=15×(1-
Теорема Ферма:
Пусть р – простое число, а а– число взаимно простое с р, тогда ар-1º1 mod p
Теорема Эйлера: Пусть a и n – взаимно простые числа, тогда аj(n)º1 mod n
Ассиметричные криптосистемы
Система
RSA.
Получатель вычисляет следующие величины:
p и q – два больших простых числа, которые держатся в секрете, Е – случайное целое число. n=p×q – открытое число. Это помещается в справочник для переписки. Е также помещается в открытый каталог и используется для шифрования сообщений. Е обладает одним свойством: НОД(Е,j(n)
)=1.
mod
j(n)=1.
Эта мультипликативная обратная существует, когда:
Теорема: Пусть А принадлежит множеству Zm (целые), тогда А имеет мультипликативный обратный по модулю n элемент в том и только том случае, когда НОД (gcd) a и n =1.
Итак, М – сообщение; n и Е – открытый ключ шифрования; p, q и D – секретные ключи дешифровки.
Отправитель знает М и каждый желающий знает открытый ключ n и Е.
Сообщение М преобразуется в цифровую форму. Если число n достаточно большое, то шифровать можно целыми строками (n–1>M). Длинное сообщение разбивается на блоки, и длина блока такова, что его числовое значение не превосходит n. Отправитель берет каждый блок в сообщении Мi (каждый блок – некоторое большое число) и шифрует следующим образом:
Если шифровать по одной букве, то частотность букв сохраняется, поэтому сообщение шифруется блоками, для этого p и q должны быть достаточно большими. D и Е не имеет смысла брать большими, поскольку они не влияют на дешифровку.
Идеи цифровой подписи
Чтобы знать, от кого точно поступает сообщение, существуют некоторые хитрости. В системах наличествуют датчики, которые фиксируют определенные действия, но при этом эти датчики могут менять злоумышленники, поэтому датчики должны посылать авторизированный сигнал (подтверждение личности). Для этого требуется цифровая подпись. Если посылается письмо, можно зашифровать какую-то фразу определенным образом, и она будет являться признаком того, что это именно вы написали это письмо.
Отправитель: ЕА, DА, nА, pАqА
Получатель: ЕВ, DВ, nВ, pВqВ
Сообщение М, к нему применяется DА, DА(М) – это шифруем ЕВ(DА(М)) и это отправляется.
Получатель своим тайным шифром дешиврует и получает DВ(ЕВ(DА(М)))=DА(М), понимает, от кого это сообщение, применяет ЕА. Если получается нормальное сообщение М, значит сообщение действительно зашифровал именно тот отправитель.
