Математические основы криптологии и криптографические методы и средс

ники. Протоколы предназначены прежде всего для защиты от нече­ стных действий партнеров.

Первая задача (соответственно, самая распространенная задача из сферы защиты) - защита передаваемой по каналам связи или хра­ нимой в компьютерной системе информации - исторически самая первая и до сих пор наиболее важная. Настоящая криптография {strong cryptography) должна обеспечивать такой уровень секретно­ сти, чтобы можно было надежно защитить критическую информа­ цию от дешифровки крупными организациями - такими как мафия, транснациональные корпорации и крупные государства. Настоящая криптография в прошлом использовалась лишь в военных целях. Од­ нако сейчас, со становлением информационного общества, она ста­ новится центральным инструментом для обеспечения конфиденци­ альности.

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

В силу присущей методам криптографии специфики большой интерес представляет множество целых чисел и различные алгеб­ раические структуры на его базе. Поэтому основное внимание бу­ дет уделено работе с целыми числами. В первой главе введены базовые определения и понятия теории множеств, рассмотрено понятие «отображение» и определены бинарные отношения. Рас­ смотрены такие алгебраические понятия, как группы, кольца и по­ ля, на множестве целых чисел. Также рассмотрены методы no­

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

1.МАТЕМАТИЧЕСКИЕ ОСНОВЫ КРИПТОЛОГИИ

1.1.АЛГЕБРАИЧЕСКИЕ МОДЕЛИ СИСТЕМ ШИФРОВАНИЯ

1.1.1.Элементы криптографии

Представьте, что вам надо отправить сообщение адресату. Вы хотите, чтобы никто, кроме адресата, не смог прочитать отправлен­ ную информацию. Однако всегда есть вероятность, что кто-либо вскроет конверт или перехватит электронное послание.

В криптографической терминологии исходное послание имену­ ют открытым текстом {plaintext или cleartext). Изменение исходного текста так, чтобы скрыть от прочих его содержание, называют шиф­ рованием {encryption). Шифрованное сообщение называют шифротекстом {ciphertext). Процесс, при котором из шифротекста извлека­ ется открытый текст, называют дешифровкой {decryption). Обычно в процессе шифровки и дешифровки используется некий ключ {key), и алгоритм обеспечивает то, что дешифрование можно выполнить, лишь зная этот ключ.

Криптография - это наука о том, как обеспечить секретность со­ общения. Криптоанализ - наука о том, как вскрыть шифрованное со­ общение, т.е. как извлечь открытый текст, не зная ключа. Крипто­ графией занимаются криптографы, а криптоанализом занимаются криптоаналитики.

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

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

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

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

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

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

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

Разрабатываются электронная почта и системы электронного перевода платежей {Electronic Funds Transfer - EFT) для замены их нынешних эквивалентов, а подтверждение кредита по телефону уже стало реальностью. В результате этого возрастает интерес к крипто­ графии как у частных лиц, так и у коммерческих организаций. Нача­ ли появляться новые статьи, а Национальное бюро стандартов (NBS) приняло криптографическую систему в качестве государственного стандарта шифрования {Data Encryption Standards - DES) для защиты несекретной, но предназначенной только для служебного пользова­ ния информации.

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

Метод шифровки/дешифровки называют шифром. Некоторые алгоритмы шифрования основаны на том, что сам метод шифрования (алгоритм) является секретным. Ныне такие методы представляют лишь исторический интерес и не имеют практического значения. Все современные алгоритмы используют ключ для управления шифров­ кой и дешифровкой; сообщение может быть успешно дешифровано, только если известен ключ. Ключ, используемый для дешифровки, может не совпадать с ключом, используемым для шифрования, одна­ ко в большинстве алгоритмов ключи совпадают.

Алгоритмы с использованием ключа делятся на два класса: симметричные (или алгоритмы с секретным ключом) и асимметрич­ ные (или алгоритмы с открытым ключом). Разница в том, что сим­ метричные алгоритмы используют один и тот же ключ для шифрова­ ния и для дешифрования (или же ключ для дешифровки просто вычисляется по ключу шифровки). В то время как асимметрические алгоритмы используют разные ключи, и ключ для дешифровки не может быть вычислен по ключу шифровки.

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

Ассиметричные шифры (также именуемые алгоритмами с от­ крытым ключом, и ли - в более общем плане - криптографией с от­ крытым ключом) допускают, чтобы открытый ключ был доступен всем (скажем, опубликован в Интернете). Это позволяет любому шифровать сообщение. Однако дешифровать это сообщение сможет только нужный человек (тот, кто владеет ключом дешифровки). Ключ для шифрования называют открытым ключом, а ключ для де­ шифрования - закрытым или секретным ключом.

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

Известны различные подходы к классификации методов крипто­ графического преобразования информации. По виду воздействия на исходную информацию эти методы подразделяют на четыре группы: кодирование, стеганография, сжатие-расширение, шифрованиедешифрование (рис. 1).

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

Рис. 1. Классификация криптографических методов и средств предотвращения угроз ИБ

Сжатие-расширение информации может быть отнесено к мето­ дам криптографического преобразования информации с определен­ ными оговорками. Целью сжатия является сокращение объема ин­ формации. В то же время сжатая информация не может быть прочи­ тана или использована без обратного преобразования. Учитывая дос­ тупность средств сжатия и обратного преобразования, эти методы нельзя рассматривать как надежные средства криптографического преобразования информации. Даже если держать в секрете алгорит­ мы, то они могут быть сравнительно легко раскрыты статистически­ ми методами обработки. Поэтому сжатые файлы конфиденциальной информации подвергаются последующему шифрованию. Для .сокра­ щения времени целесообразно совмещать процесс сжатия и шифро­ вания информации.

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

Существует несколько методов скрытой передачи информации. Одним из них является простой метод скрытия файлов при работе в операционной системе MS DOS. За текстовым открытым файлом записывается скрытый двоичный файл, объем которого намного меньше текстового файла. В конце текстового файла помещается метка EOF (комбинация клавиш Ctrl и Z). При обращении к этому текстовому файлу стандартными средствами ОС считывание пре­ кращается по достижении метки EOF, и скрытый файл остается не­ доступен. Для двоичных файлов никаких меток в конце файла не предусмотрено. Конец такого файла определяется при обработке ат­ рибутов, в которых хранится длина файла в байтах. Доступ к скры­ тому файлу может быть получен, если файл открыть как двоичный.

Скрытый файл может быть зашифрован. Бели кто-то случайно обна­ ружит скрытый файл, то зашифрованная информация будет воспри­ нята как сбой в работе системы.

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

Основным видом криптографического преобразования инфор­ мации в КС является шифрование или дешифрование. Под шифрова­ нием понимается преобразование открытой информации в зашифро­ ванную информацию (шифртекст) или обратное преобразование за­ шифрованной информации в открытую. Процесс преобразования от­ крытой информации в закрытую получил название зашифрование, а обратный процесс - расшифрование.

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

зования ЭВМ как для зашифрования/расшифрования информации, так и для атак на шифр. Атака на шифр (криптоанализ) - это процесс расшифрования закрытой информации без знания ключа и, возможно, при отсутствии сведений об алгоритме шифрования.

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

Многие качественные криптографические алгоритмы широко доступны - в книжном магазине, библиотеке, патентном бюро или в Интернете. К широко известным симметричным алгоритмам отно­ сятся DES и IDEA, наверное, самым лучшим асимметричным алго­ ритмом является RSA.

Теоретически любой шифровальный алгоритм с использованием ключа может быть вскрыт методом перебора всех значений ключа. Если ключ подбирается методом грубой силы, требуемая мощность компьютера растет экспоненциально с увеличением длины ключа. Ключ длиной в 32 бита требует 232 (около 109) шагов. Такая задача под силу любому дилетанту и решается на домашнем компьютере. Системы с 40-битным ключом (например, экспортный американский вариант алгоритма RC4) требуют 240 шагов-такие компьютерные мощности имеются в большинстве университетов и даже в неболь­ ших компаниях. Системы с 56-битными ключами (DES) требуют для вскрытия заметных усилий, однако могут быть легко вскрыты с по­ мощью специальной аппаратуры. Стоимость такой аппаратуры зна­ чительна, но доступна для мафии, крупных компаний и правительств. Ключи длиной 64 бита в настоящий момент доступны для вскрытия преступными организациями, крупными компаниями и небольшими государствами. Ключи длиной 128 бит, вероятно, останутся недос­ тупными для вскрытия методом грубой силы в обозримом будущем. Можно использовать и более длинные ключи. В пределе нетрудно добиться того, чтобы энергия, требуемая для вскрытия (считая, что