Криптография – это наука, которая разрабатывает и изучает методы защиты информации от злоумышленника, опирающаяся на преобразование исходных данных. Ее история насчитывает несколько тысяч лет. Сначала тексты зашифровывали путем замены исходного текста другим через замену букв другими буквами или символами. Затем появились полиалфавитные шифры и цифровые коды. С середины 40-х годов XX века – с работ Клода Шеннона – криптографические методы приобрели строгое математическое описание. С середины 70-х годов XX века получила развитие гражданская криптография, та самая, которую мы применяем в повседневной жизни.
В России криптография началась при Иване Грозном, более основательно криптографическую службу поставил Петр I, в Посольской канцелярии было специальное цифирное отделение, в котором разрабатывали цифири (цифири - русское название шифров). Следующий этап развития – середина XVIII века, правление Елизаветы Петровны, - появляются так называемые «черные кабинеты» - специальные помещения при почтовых отделениях, в которых вскрывалась почта, интересовавшая правительство, и дешифровывалась. Российские «черные кабинеты» появились позже, чем в Европе, но они очень успешно развивались, и к концу XIX века были уже очень сильными. Криптографические успехи были и во время Отечественной войны 1812 года – переписка Наполеона была дешифрована нашими криптографами. В первую мировую войну наша шифровальная служба пришла в некий упадок вместе с государством: в ход вошли новые технические средства, но все было еще не достаточно разработано, не согласовано, часто одна армия не могла связаться с другой. В советский период был создан спецотдел при ВЧК в 1921 году, его возглавил Глеб Иванович Бокий – ближайший соратник В. И. Ленина. Он руководил криптографической службой до 1937 года, в это время были успехи: в России дешифровали немецкий дипломатический код, читалась японская и турецкая переписка. О том, что было во время Второй мировой войны и после, есть только обрывочные сведения.
- Но это все военная криптография, - поясняет старший научный сотрудник лаборатории дискретного анализа Института математики СО РАН им. С. Л. Соболева кандидат физико-математических наук Наталья Николаевна Токарева. – Существует еще гражданская криптография, та, которой мы пользуемся каждый день, например, совершая покупки в Интернете, отправляя электронные сообщения, разговаривая по сотовому телефону. Она появилась в XX веке: на Западе это направление развивается примерно с 1960-х годов, в России открыто ей стали заниматься только с середины 1990-х годов.
Важный виток в развитии криптографии – 1976 год, когда двое американских криптографов, Уитфилд Диффи и Мартин Хеллман, предложили первую криптосистему с открытым ключом.
Ключ или целая связка ключей?
Вся криптография делится на симметричную криптографию (с закрытым ключом) и ассиметричную (с открытым ключом). Ключ – это секретная информация, которая используется алгоритмом для шифрования или расшифровывания сообщения. В современных системах для больших объемов информации используется ключ, который гораздо короче, чем длина сообщения. Конечно, такие системы не могут быть абсолютно надежными. Абсолютно стойкой система является только тогда, когда длина сообщения равна длине ключа. Такой системой, например, пользовались советские дипломаты во время Второй мировой войны, она называлась «одноразовый блокнот». Но она, конечно, непрактична, потому что когда шифруются огромные объемы информации, о таких ключах договариваться просто невозможно.
До 1976 года все методы относились к симметричной криптографии: то есть если два абонента хотят установить между собой секретный канал связи, то они заранее договариваются о ключе, который известен только им двоим.
В ассиметричной криптографии для того, чтобы установить секретный канал связи, им не нужно договариваться о ключе. Н. Н. Токарева объясняет:
- Здесь нашла свое применение математическая теория сложных задач: для таких задач неизвестно полиномиального (работающего за разумное время) алгоритма решения. Методы криптографии с открытым ключом работают следующим образом: строится функция, которая вычисляется легко, а обращается (то есть восстанавливаются числа, от которых эта функция была вычислена) очень трудно: для решения необходимо огромное количество времени. Но это возможно сделать, если вы знаете некоторую дополнительную информацию, часто ее называют «лазейкой». Например, вы хотите принимать секретные сообщения от меня, вы заводите себе два ключа: публичный ключ – описание вот этой самой функции, как шифровать, и другой – секретный ключ, известный только вам – это та самая «лазейка». И ваш публичный ключ вы сообщаете всем. Я вижу ваш публичный ключ, зашифровываю сообщение и посылаю результат вам. Вы, так как у вас есть «лазейка», можете обратить функцию и восстановить сообщение. А злоумышленник не может этого сделать, потому что «лазейки» не знает, и ему нужны, условно говоря, миллионы лет, чтобы справиться с подобной задачей. На этом принципе строятся многие криптосистемы с открытым ключом.
Например, криптосистема RSA, основанная на задаче факторизации числа (т.е. разложении его на простые множители). Надо отметить, что симметричная криптография не перестала существовать, она стала использоваться еще активней. У криптосистем с открытым ключом два больших минуса: они медленные - шифрование занимает много времени, и они не вполне надежны. Пока не найден алгоритм, находящий за разумное время решение сложной задачи, лежащей в их основе. Но никто не исключает, что через некоторое время ситуация может измениться. Поэтому чаще всего криптосистемы с открытым ключом используются для установления общего секретного ключа между абонентами. После этого используются методы симметричного шифрования.
Моя твоя не понимает
У каждой страны есть свои стандарты шифрования. Первый появился в США, он назывался DES (Data Encryption Standard), он вошел во многие программные системы и был стандартом до 1998 года. Он был отменен из-за малой длины ключа – всего 56 битов. Используя серьезные вычислительные мощности, можно этот ключ перебрать и взломать шифр просто в лоб. В России в это время появился свой стандарт, он называется ГОСТ 28147-89 и он до сих пор является стандартом. У него большой ключ – 256 битов и очень хорошая аппаратная реализация. Нынешний стандарт США - AES (Advanced Encryption Standard).
- В 2001 году в Америке был объявлен конкурс на выбор нового стандарта шифрования, - рассказывает Н. Токарева, - в нем участвовали компании из разных стран. Победил бельгийский шифр Rijndael, который стал называться AES. Сейчас проходит конкурс на хэш-функцию, он называется SHA 3. Хэш-функция – это некое преобразование, которое сокращает объем информации, условно говоря, вы подаете 1000 бит на вход, а на выходе получаете 64 бита. Зачем это нужно? Например, вы заходите на какой-то сайт под своим логином и паролем. Чтобы все пароли и логины не хранились на сервере, к ним применяется хэш-функция и хранится уже результат ее применения. Это защита для информации, чтобы, например, администратор, имеющий доступ к серверу, не смог посмотреть ваш пароль. Но в любой момент можно проверить, что это вы, вычислив хэш-функцию от введенных данных.
Стальная дверь
Для того, чтобы понять, насколько стойкий шифр разработан, криптографы применяют несколько методов анализа. В симметричной криптографии широко используются два: линейный и дифференциальный. Линейный метод анализа основан на том, что мы пытаемся заменить сложную математическую функцию, которая используется для преобразования, какой-то простой линейной функцией. Естественно, при этом получается не исходный шифр, а его приближение, причем иногда достаточно удачное.
Н. Токарева объясняет работу этого метода:
- Например, вам удалось построить для шифра линейное приближение, которое можно представить в виде следующего уравнения: несколько битов входного блока в сумме с некоторыми битами выходного блока равны одному биту ключа. Пусть это соотношение выполняется с вероятностью больше, чем ½. Теперь предположим, что ключ вам не известен, но вы имеете доступ к шифросистеме и можете набрать статистику: что подается на вход и что при этом получается на выходе. Собрав статистику, вы для каждой пары вход-выход можете вычислить значение левой части уравнения. Если больше чем для половины пар это значение оказалось равным, например, нулю, то мы предполагаем, что и правая часть этого уравнения (т.е. неизвестный нам бит ключ) равна нулю. Так мы «угадываем» один бит ключа.
Дифференциальный метод криптоанализа основан на исследовании разностей входных блоков, которые подвергаются шифрованию.
- Например, если вы подаете на вход два блока, которые отличаются в некоторых фиксированных битах, и затем анализируете, насколько отличаются соответствующие им выходные блоки, то иногда можете обнаружить такую деталь. При фиксированной разности входных блоков некоторые разности на выходе не встречаются, а какие-то встречаются чаще, чем должны бы. Подобные «отклонения от нормы» сразу используются криптоаналитиками.
В 2002 году Николас Куртуа (Nicolas Courtois) предложил идею алгебраического криптоанализа. Она состоит в том, что действие шифра описывается в виде сложной системы алгебраических уравнений. Как правило, она избыточна, содержит миллионы уравнений, но ее иногда можно решить.
- Пока непонятно, в каких случаях этот метод срабатывает, а в каких – нет, - комментирует Н. Токарева. – Однако, если он сработал, то даже казавшийся стойким шифр просто рушится.
Но даже если применение вышеописанных методов показало надежность шифра, никто не может гарантировать, что криптосистема, построенная с его использованием, не будет взломана. Американский криптограф Брюс Шнайер приводит такую аналогию: Что такое криптография? – Это стальная дверь, но очень многое зависит от того, куда вы ее ставите. Вы можете поставить ее, например, в палатку. Смысла нет ломиться в эту дверь, когда можно зайти через стенку.
- Большая проблема прикладной криптографии – ее реализация, - говорит Н. Токарева. - Метод может быть очень стойким, но если есть изъяны в реализации, эта стойкость может быть сведена на нет. Например, все мы пользуемся сотовой связью со стандартом GSM. Система безопасности GSM базируется на трех алгоритмах: А3, А5, А8. А5 – это собственно шифр, у него есть две модификации: обе взламываются, в том числе из-за слабости в реализации. Иногда не нужно даже взламывать. Информация шифруется только на одном этапе своей передачи, а на другом может идти в открытую.
Юлия Позднякова
Фото: sga-help.ru, livejournal.ru, net-vzlomy.3dn.ru
