3. МИСЗКИ. Криптографические способы защиты информации2. Криптография2.1. Классификация криптоалгоритмовВ зависимости от наличия либо отсутствия ключа кодирующие алгоритмы делятся на тайнопись и криптографию. В зависимости от соответствия ключей шифрования и дешифрования – на симметричные и асимметричные. В зависимости от типа используемых преобразований – на подстановочные и перестановочные. В зависимости от размера шифруемого блока – на потоковые и блочные шифры. Основной схемой классификации всех криптоалгоритмов является следующая:Тайнопись.Отправитель и получатель производят над сообщением преобразования, известные только им двоим. Сторонним лицам неизвестен сам алгоритм шифрования. Некоторые специалисты считают, что тайнопись не является криптографией вообще, и автор находит это совершенно справедливым. Криптография с ключом.Алгоритм воздействия на передаваемые данные известен всем сторонним лицам, но он зависит от некоторого параметра – "ключа", которым обладают только отправитель и получатель.Симметричные криптоалгоритмы.Для зашифровки и расшифровки сообщения используется один и тот же блок информации (ключ). Асимметричные криптоалгоритмы.Алгоритм таков, что для зашифровки сообщения используется один ("открытый") ключ, известный всем желающим, а для расшифровки – другой ("закрытый"), существующий только у получателя. В зависимости от характера воздействий, производимых над данными, алгоритмы подразделяются на: Перестановочные Блоки информации (байты, биты, более крупные единицы) не изменяются сами по себе, но изменяется их порядок следования, что делает информацию недоступной стороннему наблюдателю. Подстановочные Сами блоки информации изменяются по законам криптоалгоритма. Подавляющее большинство современных алгоритмов принадлежит этой группе. В зависимости от размера блока информации криптоалгоритмы делятся на: Потоковые шифры. Единицей кодирования является один бит. Результат кодирования не зависит от прошедшего ранее входного потока. Схема применяется в системах передачи потоков информации, то есть в тех случаях, когда передача информации начинается и заканчивается в произвольные моменты времени и может случайно прерываться. Наиболее распространенными предствателями поточных шифров являются скремблеры. Блочные шифры. Единицей кодирования является блок из нескольких байтов (в настоящее время 4-32). Результат кодирования зависит от всех исходных байтов этого блока. Схема применяется при пакетной передаче информации и кодировании файлов.2.2. Симметричные криптоалгоритмыСимметричные криптоалгоритмы выполняют преобразование небольшого (1 бит либо 32-128 бит) блока данных в зависимости от ключа таким образом, что прочесть исходное сообщение можно только зная этот секретный ключ. 2.2.1. СкремблерыСкремблерами называются программные или аппаратные реализации алгоритма, позволяющего шифровать побитно непрерывные потоки информации. Сам скремблер представляет из себя набор бит, изменяющихся на каждом шаге по определенному алгоритму. После выполнения каждого очередного шага на его выходе появляется шифрующий бит – либо 0, либо 1, который накладывается на текущий бит информационного потока операцией XOR. Суть скремблирования заключается в побитном изменении проходящего через систему потока данных. Практически единственной операцией, используемой в скремблерах является XOR – "побитное исключающее ИЛИ". Параллельно прохождению информационного потока в скремблере по определенному правилу генерируется поток бит – кодирующий поток. Как прямое, так и обратное шифрование осуществляется наложением по XOR кодирующей последовательности на исходную.Генерация кодирующей последовательности бит производится циклически из небольшого начального объема информации – ключа по следующему алгоритму. Из текущего набора бит выбираются значения определенных разрядов и складываются по XOR между собой. Все разряды сдвигаются на 1 бит, а только что полученное значение ("0" или "1") помещается в освободившийся самый младший разряд. Значение, находившееся в самом старшем разряде до сдвига, добавляется в кодирующую последовательность, становясь очередным ее битом (см. рис.1).Рис.1.Из теории передачи данных криптография заимствовала для записи подобных схем двоичную систему записи. По ней изображенный на рисунке скремблер записывается комбинацией "100112" – единицы соответствуют разрядам, с которых снимаются биты для формирования обратной связи. Рассмотрим пример кодирования информационной последовательности 0101112 скремблером 1012 с начальным ключом 1102.скремблер код.бит инф.бит рез-т 1 1 0 _ \ \ \_ 1 1 1 _ \_ \ \ \_ 0 XOR 0 = 0 0 1 1 _ \_ \ \ \_ 1 XOR 1 = 0 1 0 1 \_ \ \ 1 XOR 0 = 1и т.д.2.2.2. Блочные шифрыБлочные шифры шифруют целые блоки информации (от 4 до 32 байт) как единое целое – это значительно увеличивает стойкость преобразований к атаке полным перебором и позволяет использовать различные математические и алгоритмические преобразования. 2.2.2.1. Общие сведения о блочных шифрах Характерной особенностью блочных криптоалгоритмов является тот факт, что в ходе своей работы они производят преобразование блока входной информации фиксированной длины и получают результирующий блок того же объема, но недоступный для прочтения сторонним лицам, не владеющим ключом. Таким образом, схему работы блочного шифра можно описать функциями Z=EnCrypt(X,Key) и X=DeCrypt(Z,Key)Ключ Key является параметром блочного криптоалгоритма и представляет собой некоторый блок двоичной информации фиксированного размера. Исходный (X) и зашифрованный (Z) блоки данных также имеют фиксированную разрядность, равную между собой, но необязательно равную длине ключа.2.3. Симметричные криптосистемыСимметричные криптосистемы являются полноценными программами, которые могут на основе симметричных криптоалгоритмов кодировать и декодировать файлы произвольной длины. Криптосистемы устраняют целый класс "потенциальных уязвимостей" систем, использующих симметричные криптоалгоритмы. 2.3.1. Функции криптосистемКраткое описание того, для чего все же предназначены криптосистемы. Все исследования, которые мы проводили на предыдущих лекциях, касались только криптоалгоритмов, то есть методов преобразования небольшого блока данных (от 4 до 32 байт) в закодированный вид в зависимости от заданного двоичного ключа. Криптоалгоритмы несомненно являются "сердцем" криптографических систем, но, как мы сейчас увидим, их непосредственное применение без каких-либо модификаций для кодирования больших объемов данных на самом деле не очень приемлимо. Все недостатки непосредственного применения криптоалгоритмов устраняются в криптосистемах. Криптосистема – это завершенная комплексная модель, способная производить двусторонние криптопреобразования над данными произвольного объема и подтверждать время отправки сообщения, обладающая механизмом преобразования паролей и ключей и системой транспортного кодирования. Таким образом, криптосистема выполняет три основные функции: усиление защищенности данных, облегчение работы с криптоалгоритмом со стороны человека обеспечение совместимости потока данных с другим программным обеспечением. Конкретная программная реализация криптосистемы называется криптопакетом.2.3.3.2. Генераторы случайных и псевдослучайных последовательностейГенераторы случайных последовательностей играют большую роль в современной криптографии. В том случае, когда генерируемая последовательность основана только на состоянии ЭВМ, она называется псевдослучайной. Действительно случайными являются только некоторые физические процессы и человеческий фактор. Самая большая проблема всех методов рандомизации сообщений – это порождение действительно случайной последовательности бит. Дело в том, что генераторы случайных последовательностей, используемые для общих целей, например, в языках программирования, являются на самом деле псевдослучайными генераторами. Дело в том, что в принципе существует конечное, а не бесконечное множество состояний ЭВМ, и, как бы сложно не формировалось в алгоритме число, оно все равно имеет относительно немного бит информационной насыщенности. 2.3.4. АрхивацияАрхивация (сжатие данных) – есть процесс представления информации в ином виде (перекодирования) с потенциальным уменьшением объема, требуемого для ее хранения. Существует множество классов различных алгоритмов сжатия данных, каждый из которых ориентирован на свою область применения.2.3.4.1. Общие принципы архивации. Классификация методовСуществуют две большие группы алгоритмов архивации : сжатие без потерь биективно перекодирует информацию по другим законам, то есть возможно абсолютно идентичное ее восстановление; сжатие с потерями необратимо удаляет из информации некоторые сведения, оказывающие наименьшее влияние на смысл сообщения. Существует два основных метода архивации без потерь: алгоритм Хаффмана (англ. Huffman), ориентированный на сжатие последовательностей байт, не связанных между собой, алгоритм Лемпеля-Зива (англ. Lempel, Ziv), ориентированный на сжатие любых видов текстов, то есть использующий факт неоднократного повторения "слов" – последовательностей байт. Практически все популярные программы архивации без потерь (ARJ, RAR, ZIP и т.п.) используют объединение этих двух методов – алгоритм LZH.2.3.4.2. Алгоритм ХаффманаАлгоритм сжатия ориентирован на неосмысленные последовательности символов какого-либо алфавита. Необходимым условием для сжатия является различная вероятность появления этих символов (и чем различие в вероятности ощутимее, тем больше степень сжатия). Алгоритм основан на том факте, что некоторые символы из стандартного 256-символьного набора в произвольном тексте могут встречаться чаще среднего периода повтора, а другие, соответственно, – реже. Следовательно, если для записи распространенных символов использовать короткие последовательности бит, длиной меньше 8, а для записи редких символов – длинные, то суммарный объем файла уменьшится. 2.3.4.3. Алгоритм Лемпеля-ЗиваА этот алгоритм сжатия основан наоборот на корреляциях между расположенными рядом символами алфавита (словами, управляющими последовательностями, заголовками файлов фиксированной структуры)Классический алгоритм Лемпеля-Зива – LZ77, названный так по году своего опубликования, предельно прост. Он формулируется следующим образом : "если в прошедшем ранее выходном потоке уже встречалась подобная последовательность байт, причем запись о ее длине и смещении от текущей позиции короче чем сама эта последовательность, то в выходной файл записывается ссылка (смещение, длина), а не сама последовательность". Так фраза "КОЛОКОЛ_ОКОЛО_КОЛОКОЛЬНИ" закодируется как "КОЛО(-4,3)_(-5,4)О_(-14,7)ЬНИ". 2.3.5. Хеширование паролейХеш-функцией называется такое математическое или алгоритмическое преобразование заданного блока данных, которое обладает следующими свойствами: хеш-функция имеет бесконечную область определения, хеш-функция имеет конечную область значений, она необратима, изменение входного потока информации на один бит меняет около половины всех бит выходного потока, то есть результата хеш-функции. 2.4. Асимметричные криптоалгоритмыВ асимметричных криптоалгоритмах для зашифровывания сообщения используется один ключ, а для расшифровки другой. Ключ шифрования известен всем, но выполняемое преобразование необратимо, поэтому зашифрованный текст не может прочесть никто, кроме получателя – именно он один знает второй (закрытый) ключ. 2.4.2. Алгоритм RSAАлгорит RSA является классикой асимметричной криптографии. В нем в качестве необратимого преобразования отправки используется возведение целых чисел в большие степени по модулю. Алгоритм RSA стоит у истоков асимметричной криптографии. Он был предложен тремя исседователями-математиками Рональдом Ривестом (R.Rivest) , Ади Шамиром (A.Shamir) и Леонардом Адльманом (L.Adleman) в 1977-78 годах. Первым этапом любого асимметричного алгоритма является создание пары ключей : открытого и закрытого и распространение открытого ключа "по всему миру". Для алгоритма RSA этап создания ключей состоит из следующих операций :Выбираются два простых (!) числа p и q Вычисляется их произведение n(=p*q) Выбирается произвольное число e (eМетодом Евклида решается в целых числах (!) уравнение e*d+(p-1)(q-1)*y=1. Здесь неизвестными являются переменные d и y – метод Евклида как раз и находит множество пар (d,y), каждая из которых является решением уравнения в целых числах. Два числа (e,n) – публикуются как открытый ключ. 2.4.3. Технологии цифровых подписейАсимметричная криптография, как оказалось, позволяет очень красиво решать и задачу аутентификации автора сообщения – простым изменением порядка использования открытого и закрытого ключей. Как оказалось, теория асимметричного шифрования позволяет очень красиво решать еще одну проблему информационной безопасности – проверку подлинности автора сообщения. Для решения этой проблемы с помощью симметричной криптографии была разработана очень трудоемкая и сложная схема. В то же время с помощью, например, того же алгоритма RSA создать алгоритм проверки подлинности автора и неизменности сообщения чрезвычайно просто. Предположим, что нам нужно передать какой-либо текст, не обязательно секретный, но важно то, чтобы в него при передаче по незащищенному каналу не были внесены изменения. К таким текстам обычно относятся различные распоряжения, справки, и тому подобная документация, не представляющая секрета. Вычислим от нашего текста какую-либо хеш-функцию – это будет число, которое более или менее уникально характеризует данный текст. В принципе, можно найти другой текст, который дает то же самое значение хеш-функции, но изменить в нашем тексте десять-двадцать байт так, чтобы текст остался полностью осмысленным, да еще и изменился в выгодную нам сторону (например, уменьшил сумму к оплате в два раза) – чрезвычайно сложно. Именно для устранения этой возможности хеш-функции создают такими же сложными как и криптоалгоритмы – если текст с таким же значением хеш-функции можно будет подобрать только методом полного перебора, а множество значений будет составлять как и для блочных шифров 232–2128 возможных вариантов, то для поиска подобного текста злоумышленнику "потребуются" те же самые миллионы лет. 2.5. Асимметричные криптосистемыПоскольку асимметричные криптоалгоритмы очень медленны, в реальных системах используются быстрые надежные симметричные криптоалгоритмы по схеме с ключом сеанса. А вот сам ключ сеанса кодируется асимметричным криптоалгоритмом с помощью открытого ключа получателя. Подобная система обладает всеми свойствами асимметричного криптоалгоритма и очень высоким быстродействием.