Главная > Разное > Введение в криптографию
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

2. Немного теории

Что надо знать перед написанием программы шифрования

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

информации. А где начинают задумываться о защите информации — там неизбежно вспоминают о криптографии.

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

Не секрет, что каждый, кто хоть немного поработал на компьютере, не раз задумывался о защите своих файлов. Неважно от кого. Просто каждый из нас не любит, когда в его делах кто-то копается. А при работе с персональным компьютером (ПК) постоянно возникает ситуация, когда он находится в безраздельной власти, в общем-то, посторонних вам людей. К соблазну попробовать зашифровать файлы, директории или диски постоянно подталкивают нас и многочисленные программы со встроенными функциями шифрования: нортоновский Diskreet, Secretdisk, различные архиваторы, редакторы и т. д. Поэтому без преувеличения можно сказать, что с криптографией сталкивался каждый пользователь ПК.

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

Дело не в примерах, а в сути дела. А суть в том, что без криптографии решить задачи сохранения ваших тайн практически невозможно. Не будем тратить время на доказательство этого тезиса. Интуитивно это понимают все, хотя у непрофессионалов и возникает иногда некоторое чувство внутреннего сопротивления.

Итак, вы поняли, что вам надо воспользоваться какой-либо программой для шифрования. И вот здесь-то сразу появляются непреодолимые трудности. То, что они непреодолимые, вы понимаете чуть позднее. Для того, чтобы выбрать для себя нужную программу, надо научиться оценивать ее качество и уметь сравнивать такие программы между собой. А вот здесь-то никаких критериев вам никто и никогда не расскажет, да и в книгах вы ничего путного не прочитаете. А верить продавцу с его навязчивой и крикливой рекламой в данном случае полностью абсурдно, так как продавцом может оказаться ваш конкурент со всеми вытекающими отсюда последствиями. Верить можно только той программе, которую вы написали сами. Если вы с этим не согласны, значит у вас еще все впереди. Ваши иллюзии еще не скоро рассеются.

Итак, приступим к написанию программы шифрования файлов. Поначалу создание такой программы кажется вполне доступной задачей, с которой может справиться любой человек, изучивший какой-нибудь язык программирования. Нет ничего проще. Вы выбираете самый надежный из известных вам алгоритм шифрования, например описанный в ГОСТ 28147, садитесь за компьютер, и через некоторое время у вас появляется работающая программа. Хотя она работает не очень быстро и интерфейс у нее не очень удобный, она вас вполне устраивает и вы ей полностью доверяете, поскольку это ваша программа.

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

Какой алгоритм выбрать?

Мы разговаривали со многими криптографами, и все они начинали с объяснения, что такое шифр Цезаря. Он прост и удобен в обращении, но имеет один существенный недостаток — раскрыть его может каждый школьник. Поэтому не будем на нем останавливаться и сразу перейдем к шифру Виженера, либо Вернама, либо любому другому, в котором шифрование сводится к наложению одной последовательности на другую. Как признают все криптографы, при одноразовом использовании такого типа шифров дешифровать сообщение невозможно.

Простейший способ построить программу шифрования — реализовать генератор случайной последовательности, знаки которой можно последовательно складывать со знаками исходного сообщения. Для наложения, конечно, нужна не любая последовательность, а именно случайная. Что это такое? На первый взгляд нет проблем. Различных генераторов известно великое множество. Какой из них выбрать? Ответ очевиден — тот, который вырабатывает последовательность, наиболее близкую к случайной.

А теперь попробуйте дать определение случайной последовательности. Для эксперимента попросите кого-нибудь это сделать, и он наверняка скажет вам, что это такая последовательность, в которой каждый элемент случайно, независимо от других элементов и равновероятно может принимать каждое из возможных значений, или что-нибудь вроде «это последовательность, являющаяся реализацией схемы независимых испытаний», или — «полученная в результате выборки из множества всех последовательностей с равномерным распределением».

Недостаток использования такого рода определений для целей криптографии становится очевидным при взгляде на последовательность

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

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

Таким образом, наша случайная последовательность должна быть не просто получена по той или иной вероятностной схеме, но еще и быть похожей на случайную (ведь никому не придет в голову назвать первую из этих последовательностей случайной). Но кто может ответить, что значит «похожей»? На что похожа, например, последовательность

Попробуйте отличить ее от случайной последовательности. Вместе с тем, специалист по теории чисел скажет, что это десятичное представление простого числа . А теперь подумайте, как эта последовательность будет выглядеть в двоичной записи.

Каковы возможные критерии похожести? Легко сформулировать условия похожести одной последовательности на другую. Но как сформулировать, что значит «последовательность похожа на случайную последовательность»? Эта проблема не имеет однозначного ответа. Есть много подходов к определению понятия «похожести», но каждый из них страдает односторонностью. Поэтому от выбранного вами подхода во многом зависит качество шифрования.

Удобно ли носить большую связку ключей?

Перед вами программа для шифрования. Что является секретным в этой программе? Сама программа? Исходный текст? Описание алгоритма? Ответ, безусловно, зависит от условий ее применения. Конечно, лучше всего сделать так, чтобы ваш конкурент не имел ни того, ни другого, ни третьего. Поэтому обычно подобные программы защищают и от копирования, и от дизассемблирования, и от работы под отладчиком и т. д. Если она защищена грамотным специалистом, то пройдет

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

Что еще представляет интерес для вашего конкурента? Закрытая программой информация? От нее никто не откажется, но она мало что дает. Если алгоритм шифрования выбран надежный, то закрытая информация не представляет секрета, так как она непосредственно предназначена для хранения и передачи в открытом виде. Поэтому при отсутствии следов не уничтоженной открытой информации можно быть спокойным.

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

Но как вводить ключ в программу и где хранить ключи? Если программу использовать интенсивно, то ключей нужно очень много. Где их брать и как заменять один на другой?

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

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

В 1976 году американские математики Диффи и Хеллман предложили перейти к системам с открытым ключом. Давайте издадим книгу

справочник с открытыми ключами всех корреспондентов и поместим ее на общедоступном сервере. Это полностью снимет проблему с хранением большого числа ключей.

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

Более того, плодотворность идеи выразилась в проявлении большого интереса к ней у значительной части крупных математиков. Ведь для реализации такой системы нужны были труднорешаемые математические задачи. А кто, кроме самих математиков, может придумать такие задачи!

Посмотрим, например, как организуется выработка ключей в широко распространенном протоколе SSH (Secure Shell). Данный протокол обеспечивает аутентификацию и закрытие коммуникаций при взаимодействии UNIX машин. Для выработки ключей в нем используется протокол, являющийся модификацией хорошо известного протокола обмена ключами, предложенного Диффи и Хеллманом. Пусть большое простое число и Пусть число, имеющее порядок равный по модулю Оно является образующим элементом мультипликативной группы порядка Помимо операции возведения в степень в протоколе используются алгоритмы вычисления функции хеширования SHA (secure hash algorithm) и цифровой подписи DSS (digital signature standard), принятые в США в качестве стандартов. Протокол состоит в следующем (см. [6]).

1. Клиент С генерирует случайное число вычисляет значение и отправляет сообщение серверу

2. Сервер S генерирует случайное число вычисляет значение вычисляет значение ключа вычисляет проверочное значение (здесь hash - функция хеширования на основе алгоритма SHA, V - некоторая строка, содержащая идентифицирующую информацию о клиенте и сервере, открытый ключ сервера), вычисляет значение цифровой подписи под на своем секретном ключе в соответствии с алгоритмом DSS, а затем отправляет сообщение клиенту С.

3. Клиент С проверяет, действительно ли является ключом сервера. Если да, то вычисляет значение ключа проверяет правильность значения вектора Наконец, проверяет подпись под этим значением. В этом протоколе простое число строится из известного каждому школьнику числа по формуле

и равно

Его шестнадцатиричная запись имеет «менее случайный» вид

Данное число построено Ричардом Шреппелем из университета штата Аризона, а его свойства описаны в работе [7].

В качестве образующего элемента для этого простого числа взято число Возведение в степень такого числа выполняется достаточно быстро, так как умножение на 2 — это простой сдвиг двоичной записи числа в сторону старших разрядов.

49783156431138-я попытка

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

чем запустить на исполнение программу, подумаем, сколько времени она может работать.

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

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

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

где число различных упорядочений множества из ключей, у которых истинный ключ стоит на месте с номером Так как легко подсчитать, что то наша сумма равна

Итак, в среднем придется перебрать чуть больше половины всех ключей.

Теперь вернемся от математики к суровой действительности. Пусть вы написали великолепную программу, которая проверяет за одну

секунду один миллион вариантов ключа. Тогда за час программа переберет ключей, за сутки ключей, а за год — более 30000000000000. Короче, для перебора ключей шифратора

DES вашей программе потребуется в среднем чуть более 1500 лет. Вдохновляющий результат, не правда ли? А теперь подсчитайте, сколько лет потребуется вашей программе для нахождения неизвестного ключа у отечественного алгоритма шифрования ГОСТ 28147, в котором число ключей равно 2256.

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

А теперь перейдем к решению практических вопросов.

<< Предыдущий параграф Следующий параграф >>
Оглавление