Методы и средства защиты информации. Внимание!!! В книге могут встречаться существенные ошибки (в рисунках и формулах). Они не связаны ни со
 Скачать 4.86 Mb.
|
|
Глава 18. Криптографическая защита Рис . 18.3. Поток информации в криптографической системе , обеспечивающей секретность Отправитель генерирует открытый текст , или шифрованное сообщение Р , ко - торое должно быть передано получателю по незащищенному прослушиваемому каналу Для того чтобы перехватчик не смог узнать содержания сообщения Р , отправитель шифрует или кодирует его с помощью обратимого преобразования S k и получает криптограмму или шифрованный текст С = S k (P) Получатель , приняв сообщение С , дешифрирует или декодирует его с помощью обратного преобразования S k -1 и получает исходное сообщение S k -1 (C) = S k -1 [S k (P)] =P Преобразование S k выбирается из семейства криптографических преобразо - ваний , называемых криптографической , или общей , системой Параметр , выбирающий отдельное используемое преобразование , называет - ся ключом Общая система — это набор инструкций , аппаратурных средств и про - граммного обеспечения ЭВМ , с помощью которого можно зашифровать и рас - шифровать текст разными способами , один из которых выбирается с помощью конкретного ключа Говоря более формально , криптографическая система — это однопара - метрическое семейство (S k ) к ∈ K обратимых преобразований S k :Р → С из про - странства Р сообщений открытого текста в пространство С шифрованных сооб - щений Параметр , или ключ К , называется пространством ключей Обычно общая система рассматривается как общедоступная С одной сторо - ны , открытая для всех часть общей системы является предметом соглашения , а с другой стороны , это отражает очень важное правило техники защиты : защи - щенность системы не должна зависеть от секретности чего - либо такого , что нельзя быстро изменить в случае утечки секретной информации Обычно общая система является некоторой совокупностью аппаратуры и программ , которую можно изменить только со значительной затратой времени и средств , тогда как ключ представляет собой легко изменяемый объект Поскольку вся секретность сосредоточена в секретности ключа , то его надо передавать отправителю и получателю по защищенному каналу распростране - ния ключей , такому , как курьерская служба и т д Проблема имитостойкости Безусловная и теоретическая стойкость 371 Теперь рассмотрим схему прохождения потока информации в криптографи - ческой системе , обеспечивающей имитостойкость ( рис . 18.4). Рис . 18.4. Поток информации в криптографической системе , обеспечивающей имитостойкость При решении проблемы имитостойкости противник может не только видеть все криптограммы , передаваемые по каналу , но может также изменять их по своему желанию Законный получатель защищает себя от обмана , дешифрируя все полученные сообщения и принимая только те сообщения , которые зашиф - рованы правильным ключом Любая попытка со стороны перехватчика расшифровать криптограмму С для получения открытого текста Р или зашифровать свой текст Р' для получения приемлемой криптограммы С' без получения ключа должно быть полностью ис - ключено Если криптоанализ невозможен и криптоаналитик не может вывести Р и С или С' из Р' без предварительного получения ключа , то такая криптографиче - ская система является криптостойкой Безусловная и теоретическая стойкость Существует два принципиально разных метода обеспечения стойкости крип - тографических систем против криптоаналитического нападения В некоторых системах объем доступной криптоаналитику информации факти - чески недостаточен для того , чтобы найти преобразования и дешифрирования , причем данная ситуация не зависит от того , какие вычислительные мощности имеет криптоаналитик Система такого рода называется безусловно стойкой В том случае , когда перехваченный материал содержит достаточно инфор - мации для однозначного решения криптоаналитической задачи , нет никакой га - рантии , что это решение будет найдено криптоаналитиком , имеющим опреде - ленные вычислительные ресурсы Следовательно , цель разработчика крипто - графической системы состоит в том , чтобы уменьшить затраты на операции шифрования и дешифрирования , но чтобы в тоже время любая криптоаналити - ческая операция была слишком сложной и поэтому экономически невыгодной Иными словами , необходимо , чтобы задача криптоанализа , о которой известно , что она разрешима при конечном объеме вычислений , была бы столь громозд - 372 Глава 18. Криптографическая защита кой , что для ее решения не хватило бы физических вычислительных ресурсов всего мира Задачу такого объема называют вычислительно нереализуемой , а связанную с ней криптографическую систему — вычислительно стойкой В случае безусловно стойких систем их стойкость может быть доказана , но что касается теории вычислительной сложности , то при нынешнем уровне ее развития она не в состоянии продемонстрировать вычислительную нереализуе - мость любой криптографической задачи Поэтому в криптографии возникло и развивается направление , посвященное разработке формальных процессов проверки стойкости Такие процессы сводятся к криптоаналитическому нападе - нию на предлагаемые для проверки криптографические системы при условиях , благоприятных для криптоаналитика Единственной безусловно стойкой системой , находящейся в широком поль - зовании , является лента однократного использования , в которой открытый текст объединяется со случайным ключом такой же длины Обычно открытый текст представляет собой строку из n бит , которая объединяются со случайным ключом такой же длины с помощью сложения по модулю 2. Как видно из самого названия , этот ключ никогда больше не используется Даже если бы криптоаналитик попытался осуществить дешифрирование , ис - пользуя все 2 n возможных ключей , он просто увидел бы все 2 n возможных от - крытых текстов одинаковой длины Поскольку перехват криптограммы не позво - ляет криптоаналитику вывести какое - либо сообщение в виде открытого текста , то он не узнает ничего , кроме длины сообщения Клод Шеннон анализировал аб - солютную стойкость более подробно Если криптоаналитик располагает неогра - ниченным временем для вычислений , то он не связан рамками вычислительной эффективности и может провести полный криптоанализ , испытывая все возмож - ные ключи и сохраняя в качестве результата все осмысленные тексты В случае ленты однократного использования необходимо сохранить все осмысленные тексты , имеющие одинаковую с криптограммой длину , но в других безусловно стойких системах может быть меньшее количество осмысленных решений На - пример , криптограмма XMDA, полученная в результате простой подстановки го - дится для любого четырехбуквенного слова с неповторяющимися буквами По мере того как количество перехваченных текстов возрастает , может быть достигнута точка , в которой оказывается возможным получение однозначного решения Шеннон назвал это интервалом однозначности N 0 В случае ленты од - нократного использования этого никогда не случиться , и N 0 = ∞ , тогда как в слу - чае простого подстановочного шифра значение N 0 конечно Шеннон предложил модель для предсказания интервала однозначности шифра Полученные с по - мощью этой модели результаты согласуются с практикой В соответствии с этой моделью “ случайного шифра ” N 0 = H(K) D (18.7) Безусловная и теоретическая стойкость 373 где H(K) — энтропия ключа ( обычно это просто длина ключа , измеренная в би - тах , или log 2 от количества ключей ), D — избыточность языка , измеренная в би - тах на 1 знак . ( Например , в английском языке за буквой Q всегда следует буква U, которая является избыточной .) Качественно модель можно показать , перепи - сав (18.7) в виде требования для однозначности решения H(K) ≤ N 0 D (18.8) где H(K) характеризует количество неизвестных в двоичном представлении ключа , а N 0 D в широком смысле определяет количество уравнений , которые не - обходимо решить для нахождения ключа Когда количество уравнений меньше количества неизвестных , однозначное решение невозможно и система являет - ся безусловно стойкой Когда количество уравнений больше количества неиз - вестных , т е как в (18.8), однозначное решение возможно и система не являет - ся безусловно стойкой , хотя она все еще может быть вычислительно стойкой Несмотря на то , что в теории кодирования Шеннона ( т е в предположении , что криптоаналитик располагает неограниченными ресурсами ) обычно рассмат - ривается нападение при наличии только шифрованного текста , но иногда ис - пользуются и комбинации шифрованного и открытого текста , что повышает из - быточность Уравнение (18.7) показывает ценность снятия данных , производимого перед шифрованием Согласно Фридмэну , почти любая криптограмма из 25 букв и более , полу - ченная подстановкой , может быть раскрыта Поскольку криптоаналитик распо - лагает ограниченными вычислительными возможностями , он не может пере - пробовать все 26! ≈ 4.10 26 ключей и должен полагаться на субоптимальные ме - тоды , такие как частотный анализ Таким образом , можно сказать , что N 0 = 25 знаков В случае ленты однократного использования H(K) = ∞ , откуда , согласно (7), N 0 = ∞ После простой подстановки получаем H(K) = log 2 (26!) = 88,4 бит , поэто - му для вычисления N 0 принято находить D Каждый знак мог бы переносить мак - симум log 2 (26) = 4,7 бит информации , если бы все комбинации были возможны Но поскольку правила правописания и грамматики запрещают использование большинства комбинаций , то в среднем каждый знак переносит всего лишь 1,5 бит информации Оставшиеся 3,2 бит оказываются избыточными , откуда D = 3,2 бит / знак Таким образом , уравнение (18.7) представляет величину N 0 = 28 зна - ков , что хорошо согласуется с практикой Например , если перехвачено сообщение длиной в 1000 знаков и известна не - которая последовательность из 100 знаков открытого текста , то общая избыточ - ность составит не 3200 бит , а ( 900 знаков ) × ( 3,2 бит / знак ) + ( 100 знаков ) × ( 4,7 бит / знак ) = 3350 бит Сжатие данных устраняет избыточность , увеличивая тем самым интервал однозначности Избыточная информация может быть добавлена после дешиф - 374 Глава 18. Криптографическая защита рирования Совершенное сжатие данных устранило бы всю избыточность и при - вело бы к N 0 = ∞ при любой длине ключа , но это довольно дорогое мероприятие Важным подготовительным этапом для проверки стойкости шифра является продумывание различных предполагаемых возможностей , с помощью которых противник может вскрыть шифр Появление таких возможностей у противника обычно не зависит от собственно используемого криптографического метода , а является следствием некоторой внешней подсказки , наличие которой сущест - венно влияет на стойкость шифра Поэтому оценки стойкости шифра всегда со - держат те предположения о противнике , в условиях которых эти оценки получе - ны Прежде всего , обычно считается , что противник знает сам шифр и имеет воз - можность его предварительного изучения Противник также знает некоторые ха - рактеристики открытых текстов ( защищаемой информации ), например , общую те - матику сообщений , их стиль , некоторые стандарты , форматы и т д Приведем три примера специфических возможностей противника : • противник может перехватывать все шифрованные сообщения , но не имеет соответствующих им открытых текстов ; • противник может перехватывать все шифрованные сообщения и добывать соответствующие им открытые тексты ; • противник имеет доступ к шифру ( но не к ключам !) и поэтому может зашиф - ровать любую информацию На протяжении многих веков среди специалистов не утихали споры о стойко - сти шифров и о возможности построения абсолютно стойкого шифра “ Отец кибернетики ” Норберт Винер отмечал : “ Любой шифр может быть вскрыт , если только в этом есть настоятельная необходимость и информация , которую предполагается получить , стоит затраченных средств , усилий и вре - мени …” Поэтому у пользователя остается единственный путь — получение практиче - ских оценок стойкости Этот путь состоит из следующих этапов 1. Понять и четко сформулировать , от какого противника необходимо защищать информацию Следует уяснить , что именно противник знает или может узнать о системе шифра , какие силы и средства он сможет применить для его вскрытия 2. Мысленно стать в положение противника и попытаться с его позиций вскрыть шифр , т е разработать различные алгоритмы вскрытия шифра , обеспечивая при этом в максимальной мере моделирование сил , средств и возможностей противника 3. Наилучший из разработанных алгоритмов использовать для практической оценки стойкости шифра Следует упомянуть о двух простейших методах вскрытия шифра : случайного угадывания ключа ( он срабатывает с малой вероятностью , но является самую Анализ основных криптографических методов ЗИ 375 низкую вычислительную сложность ) и перебора всех подряд ключей вплоть до нахождения истинного ( он срабатывает всегда , но имеет самую высокую вычис - лительную сложность ). Анализ основных криптографических методов ЗИ Иногда криптографические методы ЗИ разделяют на три группы : методы подстановки , методы перестановки и аддитивные методы Методы пе - рестановки и подстановки характеризуются хорошими ключами , а их надежность связана со сложным алгоритмом преобразования При аддитивных методах пользуются простыми алгоритмами преобразования , обеспечивая надежность с помощью ключей большого объема Иногда говорят о блочных методах , имея в виду первые две группы , в кото - рых алгоритм работает сразу над большим блоком информации , и о потоко - вых методах , где шифрование происходит знак за знаком Однако при исполь - зовании аддитивных методов преобразование может осуществляться сразу над целым машинным словом и метод приобретает признаки блочного Шифрование методом подстановки ( замены ) В этом , наиболее простом , методе символы шифруемого текста заменяются другими символами , взятыми из одного ( моноалфавитная подстановка ) или не - скольких ( полиалфавитная подстановка ) алфавитов Самой простой разновид - ностей является прямая замена , когда буквы шифруемого текста заменяются другими буквами того же самого или некоторого другого алфавита Если объем зашифрованного текста большой , то частоты появления букв в зашифрованном тексте будут ближе к частотам появления букв в алфавите ( того языка , на котором написан текст ) и расшифровка будет очень простой Поэтому простую замену в настоящее время используют редко и в тех случа - ях , когда шифруемый текст короток Для повышения стойкости шифра используют так называемые полиалфавит - ные подстановки , в которых для замены символов исходного текста используют - ся символы нескольких алфавитов Существует несколько разновидностей по - лиалфавитной подстановки , наиболее известными из которых являются одно - ( обыкновенная и монофоническая ) и многоконтурная При полиалфавитной одноконтурной обыкновенной подстановке для заме - ны символов исходного текста используется несколько алфавитов , причем сме - на алфавитов осуществляется последовательно и циклически , т е первый сим - вол заменяется соответствующим символом первого алфавита , второй — сим - волом второго алфавита и т д до тех пор , пока не будут использованы все выбранные алфавиты После этого использование алфавитов повторяется В качестве примера рассмотрим шифрование с помощью таблицы Виженера Таблица Виженера представляет собой матрицу с n 2 элементами , где n — коли - |