Тема 1 Изучение современных методов сжатия информации без потерь Сжа́тие да́нных
Криптостойкость шифра[править | править код]
жүктеу/скачать 237 Kb.
|
Прикладная теория информации - 579551
- Бұл бет үшін навигация:
- Достаточно стойкие системы
Криптостойкость шифра[править | править код]Основная статья: Криптографическая стойкость Криптографическая стойкость — свойство криптографического шифра противостоять криптоанализу, то есть анализу, направленному на изучение шифра с целью его дешифрования. Для изучения криптоустойчивости различных алгоритмов была создана специальная теория, рассматривающая типы шифров и их ключи, а также их стойкость. Основателем этой теории является Клод Шеннон. Криптостойкость шифра есть его важнейшая характеристика, которая отражает то, насколько успешно алгоритм решает задачу шифрования[9]. Любая система шифрования, кроме абсолютно криптостойких, может быть взломана простым перебором всех возможных в данном случае ключей. Но перебирать придётся до тех пор, пока не отыщется тот единственный ключ, который и поможет расшифровать шифротекст. Выбор этого единственного ключа основан на возможности определения правильно расшифрованного сообщения. Зачастую эта особенность является камнем преткновения при подборе ключа, так как при переборе вручную криптоаналитику достаточно просто отличить правильно расшифрованный текст, однако ручной перебор очень медленен. Если же программа выполняет перебор, то это происходит быстрее, однако ей сложно выделить правильный текст. Невозможность взлома полным перебором абсолютно криптостойкого шифра так же основана на необходимости выделить в расшифрованном сообщении именно то, которое было зашифровано в криптограмме. Перебирая все возможные ключи и применяя их к абсолютно стойкой системе, криптоаналитик получит множество всех возможных сообщений, которые можно было зашифровать (в нём могут содержаться и осмысленные сообщения). Кроме того, процесс полного перебора также длителен и трудоёмок. Другой метод дешифровки основывается на анализе перехваченных сообщений. Этот метод имеет большое значение, так как перехват сообщений возможен, если злоумышленник обладает специальным оборудованием, которое, в отличие от достаточно мощного и дорогостоящего оборудования для решения задач методом полного перебора, более доступно. Например, перехват ван Эйка для ЭЛТ монитора осуществим с помощью обычной телевизионной антенны. Кроме того, существуют программы для перехвата сетевого трафика (снифферы), которые доступны и в бесплатных версиях[10][11][12]. При анализе передаваемых сообщений криптоустойчивость шифра оценивается из возможности получения дополнительной информации об исходном сообщении из перехваченного. Возможность получения этой информации является крайне важной характеристикой шифра, ведь эта информация в конечном итоге может позволить злоумышленнику дешифровать сообщение. В соответствии с этим шифры делятся на абсолютно стойкие и достаточно стойкие[13][10]. Клод Шеннон впервые оценил количество подобной информации в зашифрованных сообщениях следующим образом:[13] Пусть возможна отправка любого из сообщений {\displaystyle m_{1},m_{2},...,m_{n}}, то есть любого подмножества множества {\displaystyle M}. Эти сообщения могут быть отправлены с вероятностями {\displaystyle p_{1},p_{2},...,p_{n}} соответственно. Тогда мерой неопределенности сообщения может служить величина информационной энтропии:{\displaystyle H(M)=-\sum _{i=1}^{n}p_{i}\log _{2}p_{i}.}Пусть отправлено сообщение {\displaystyle m_{k}}, тогда его шифротекст {\displaystyle c_{k}}. После перехвата зашифрованного {\displaystyle c_{k}} эта величина становится условной неопределенностью — условием здесь является перехваченное шифрованное сообщение {\displaystyle c_{k}}. Необходимая условная энтропия задаётся следующей формулой: {\displaystyle H(M|c_{k})=-\sum _{i=1}^{n}p(m_{i}|c_{k})\log _{2}p(m_{i}|c_{k}).}Через {\displaystyle p(m_{i}|c_{k})} здесь обозначена вероятность того, что исходное сообщение есть {\displaystyle m_{i}} при условии, что результат его зашифрования есть {\displaystyle c_{k}}. Это позволяет ввести такую характеристику шифрующей функции (алгоритма) {\displaystyle E}, как количество информации об исходном тексте, которое злоумышленник может извлечь из перехваченного шифротекста. Необходимая характеристика является разностью между обычной и условной информационной неопределенностью:{\displaystyle I=H(M)-H(M|c_{k})} Эта величина, называемая взаимной информацией, всегда неотрицательна. Её значение есть показатель криптостойкости алгоритма. Взаимная информация показывает, насколько уменьшится неопределённость при получении соответствующего шифротекста и не станет ли она таковой, что при перехвате некоторого количества шифротекстов станет возможной расшифровка исходного сообщения[14].
Абсолютно стойкие системыОценка криптоустойчивости шифра, проведенная Шенноном, определяет фундаментальное требование к шифрующей функции {\displaystyle E}. Для наиболее криптоустойчивого шифра неопределённости (условная и безусловная) при перехвате сообщений должны быть равны для сколь угодно большого числа перехваченных шифротекстов.{\displaystyle {\mathcal {8}}c_{k}{\mathcal {2}}C:H(M|c_{k})=H(M)\Rightarrow I=0}Таким образом, злоумышленник не сможет извлечь никакой полезной информации об открытом тексте из перехваченного шифротекста. Шифр, обладающий таким свойством, называется абсолютно стойким[13]. Для соблюдения равенства энтропий Шеннон вывел требования к абсолютно стойким системам шифрования, касающиеся используемых ключей и их структуры. Ключ генерируется для каждого сообщения (каждый ключ используется один раз). Ключ статистически надёжен (то есть вероятности появления каждого из возможных символов равны, символы в ключевой последовательности независимы и случайны). Длина ключа равна или больше длины сообщения. Стойкость таких систем не зависит от того, какими возможностями обладает криптоаналитик. Однако практическое применение абсолютно стойких криптосистем ограничено соображениями стоимости таких систем и их удобства. Идеальные секретные системы обладают следующими недостатками: Шифрующая система должна создаваться с исключительно глубоким знанием структуры используемого языка передачи сообщений Сложная структура естественных языков крайне сложна, и для устранения избыточности передаваемой информации может потребоваться крайне сложное устройство. Если в передаваемом сообщений возникает ошибка, то эта ошибка сильно разрастается на этапе кодирования и передачи в связи со сложностью используемых устройств и алгоритмов[15]. Достаточно стойкие системыВ связи со сложностью применения абсолютно стойких систем, повсеместно более распространёнными являются так называемые достаточно стойкие системы. Эти системы не обеспечивают равенство энтропий и, как следствие, вместе с зашифрованным сообщением передают некоторую информацию об открытом тексте. {\displaystyle {\mathcal {9}}c_{k}{\mathcal {2}}C:H(M)>H(M|c_{k})\Rightarrow I>0}Их криптостойкость зависит от того, какими вычислительными возможностями обладает криптоаналитик. Иными словами, шифротекст взламывается, если криптоаналитик обладает достаточными ресурсами, такими как время и количество перехваченных сообщений. Практическая стойкость таких систем основана на их вычислительной сложности и оценивается исключительно на определённый момент времени с двух позиций[16]: вычислительная сложность полного перебора для данной системы известные на данный момент слабости (уязвимости) системы и их влияние на вычислительную сложность. Добиться высокого уровня практической стойкости алгоритма можно двумя подходами[17]: Изучить методы, которыми пользуется злоумышленник, и попытаться защитить используемую систему от них. Составить шифр таким образом, чтобы его сложность была эквивалентна сложности известной задачи, для решения которой требуется большой объём вычислительных работ. Список основной и дополнительной литературы: Основная: Грищенко В.И. Паньшин Б.Н. Информационная технология, вопросы развития и применения. - Киев: Наукова думка,-1986. - 268 с. Дмитриев В.И. Прикладная теория информации. - М.: Высшая школа, 1989.-319с. Мартин Дж. Вычислительные сети и распределенная обработка данных. Т. 1, Т. 2. Мл Финансы и статистика, 1986. Петров В.И. Информационные системы. - СПб.: Питер, 2002 .-688с. Сириденко С.С. Современные информационные технологии. - Мл Радио и связь, 1989. Советов Б.Я. Информационная технология: Учебник для вузов по специальности "Автоматизированные системы обработки информации и управления". - Мл Высшая школа, 1994.- 368 с. Цымбал В.П. Задачник по теории информации и кодированию. -Мл Высшая школа, 1976. - 276 с. Шаврин Ю.А. Информационные технологии: Учебное пособие: В 2 тт: Т.ПОсновы информатики и информационных технологий//Т.2: Офисная технология и информационные системы. Серия: Информатика. - Мл 2001. Цымбал В.П. Теория информации и кодированию. - Киев, Высшая школа, 1992. Дополнительная: Калымов В.В., Сенин А.И. Основы теории информации. Учебное пособие. – Мл МГТУ. 1992. П.Горяинов О.А., Хохлов Г.И. Элементы теории информации кодирования. Учебное пособие.-Мл МИРЭА.1985. Колесник В.Д., Полтырев Г.Ш. Курс теории информации. - М., Наука, 1982. Филипчук Е.В., Пахомов СВ. Теория информации и помехоустойчивое кодирование. Учебное пособие. - Мл МИФИ, 1989. Н.Данилевский Ю.Г., Пастухов И.А., Шабанов B.C. Информационная технология в промышленности. - Д.: Машиностроение, 1988. - 272 с. Галлагер Дж. Теория информации и надежная связь. - М„ Советское радио, 1974. Свириденко С.С. Информационные технологии в интеллектуальной деятельности. М: МНЭПУ.2001 -192с. жүктеу/скачать 237 Kb. Достарыңызбен бөлісу:
|