Что такое шифрование и как им пользоваться

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

Есть что скрывать

«У меня нет никаких тайн, мне нечего скрывать», – часто можно услышать от пользователей, когда речь заходит о шифровании и других средствах защиты конфиденциальности. Обычно за этой фразой стоит нечто другое – «я считаю, что никто не потрудится лезть в мой телефон или компьютер, чтобы там найти что-то ценное». Но практика показывает, что это не так. Файл, сохраненный на рабочий стол компьютера или телефон, оставленный в гостиной, довольно быстро будет изучен кем-то из домочадцев. Все ли письма, фотографии и документы вы готовы показывать жене, брату, теще, детям? Возможно, там нет ничего криминального. Но готовы ли вы сообщить номер своей кредитной карты и ее PIN-код детям-подросткам? Отдать брату пароли от почты и социальных сетей?Демонстрировать

все семейные фото друзьям, которые пришли в гости и на пятнадцать минут сели за компьютер? Есть ли желание объяснять жене, что Элеонора – это начальник отдела смежников на работе, а встреча с ней завтра – это совещание с участием еще десяти человек?

Ваши фото, номера банковских карт и просто личная переписка интересуют всех: домочадцев, работодателей и, конечно, киберпреступников

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

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

Семь бед – один ответ 

Угроз, как мы видим, существует много, и от каждой из них можно придумать свой способ защиты: изолировать компьютер в запертой спальне, поставить PIN-код на включение смартфона и так далее. Но если защитить информацию не путем физической изоляции, а так, чтобы ее мог прочитать только владелец, результат будет более надежным и всеобъемлющим.  Абсолютно все перечисленные неурядицы – большие и малые – могли бы не случиться, если бы важная информация, предназначенная не для всех глаз, хранилась бы в зашифрованном виде.

Иногда вы сталкиваетесь с шифрованием, даже если не задумываетесь об этом, – например, заходя в Gmail или на сайт онлайн-б

Криптография и главные способы шифрования информации

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

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

ROT13 – еще один распространенный тип шифрования сообщений. В нём каждая буква алфавита сдвигается на 13 позиций, как показано на рисунке:

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

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

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

Конфиденциальность – данные не могут быть получены или прочитаны неавторизованными пользователями.

Целостность информации – уверенность в том, что информация 100% останется нетронутой и не будет изменена злоумышленником.

Доступность информации – получение доступа к данным, когда это необходимо.

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

Основные способы шифрования:

• Симметрично
• Асимметричное
• Хеширование
• Цифровая подпись

Прежде чем мы начнем разбираться в теме, ответим на простой вопрос: что именно подразумевается под «шифрованием»? Шифрование – преобразование информации в целях сокрытия от неавторизованных лиц, но в то же время с предоставлением авторизованным пользователям доступа к ней.

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

require 'openssl'
require 'pry'

data_to_encrypt = 'now you can read me!'

cipher = OpenSSL::Cipher.new('aes256')
cipher.encrypt

key = cipher.random_key
iv  = cipher.random_iv

data_to_encrypt = cipher.update(data_to_encrypt) + cipher.final

binding.pry
true

Вот что выведет программа:

Обратите внимание, что переменная data_to_encrypt, которая изначально была строкой “now you can read me!”, теперь куча непонятных символов. Обратим процесс, используя ключ, который изначально сохранили в переменной key.

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

Давайте рассмотрим и другие способы шифрования.

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

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

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

Но как понять, что открытый ключ сервера принадлежит именно этому серверу? Существует несколько способов решения этой проблемы. Наиболее распространенный метод (и тот, который используется в интернете) – использование инфраструктуры открытых ключей (PKI). В случае веб-сайтов существует Центр сертификации, у которого есть каталог всех сайтов, на которые были выданы сертификаты и открытые ключи. При подключении к веб-сайту его открытый ключ сначала проверяется центром сертификации.

Создадим пару открытого и закрытого ключей:

require 'openssl'
require 'pry'

data_to_encrypt = 'now you can read me!'

key = OpenSSL::PKey::RSA.new(2048)

binding.pry
true

Получится:

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

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

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

Создадим новую строку, хешируем её и сохраним результат в переменной:

require 'openssl'
require 'pry'

test = 'some data'

digest = Digest::SHA256.digest(test)

binding.pry
true

Снова хешируем строку и сравниваем её с той, что сохранили в переменной digest:

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

Чтобы показать, как выглядят разные строки похожих исходных данных, взгляните на это:

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

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

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

Оригинал

Шифрование — это… Что такое Шифрование?

Шифрова́ние — преобразование информации в целях сокрытия от неавторизованных лиц, с предоставлением, в это же время, авторизованным пользователям доступа к ней. Главным образом, шифрование служит задаче соблюдения конфиденциальности передаваемой информации. Важной особенностью любого алгоритма шифрования является использование ключа, который утверждает выбор конкретного преобразования из совокупности возможных для данного алгоритма.^[1][2]

Пользователи являются авторизованными, если они обладают определенным аутентичным ключом. Вся сложность и, собственно, задача шифрования состоит в том, как именно реализован этот процесс.^[1]

В целом, шифрование состоит из двух составляющих — зашифрование и расшифрование.

С помощью шифрования обеспечиваются три состояния безопасности информации:^[1]

• Конфиденциальность.

Шифрование используется для сокрытия информации от неавторизованных пользователей при передаче или при хранении.

Шифрование используется для предотвращения изменения информации при передаче или хранении.

• Идентифицируемость.

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

Для того чтобы прочитать зашифрованную информацию, принимающей стороне необходимы ключ и дешифратор(устройство реализующее алгоритм расшифровывания). Идея шифрования состоит в том, что злоумышленник, перехватив зашифрованные данные и не имея к ним ключа, не может ни прочитать, ни изменить передаваемую информацию. Кроме того, в современных криптосистемах(с открытым ключом) для шифрования, расшифрования данных могут использоваться разные ключи. Однако, с развитием криптоанализа, появились методики позволяющие дешифровать закрытый текст не имея ключа, они основаны на математическом анализе перехваченных данных.^[1][3]

Цели шифрования

Шифрование применяется для хранения важной информации в ненадёжных источниках и передачи её по незащищенным каналам связи. Такая передача данных представляет из себя два взаимно обратных процесса:

• Перед отправлением данных по линии связи или перед помещением на хранение они подвергаются зашифрованию.
• Для восстановления исходных данных из зашифрованных к ним применяется процедура расшифрования.

Шифрование изначально использовалось только для передачи конфиденциальной информации. Однако, впоследствии, шифровать информацию начали с целью ее хранения в ненадежных источниках. Шифрование информации с целью ее хранения применяется и сейчас, это позволяет избежать необходимости в физически защищенном хранилище.^[4][5]

Шифром называется пара алгоритмов, реализующих каждое из указанных преобразований. Эти алгоритмы применяются над данными с использованием ключа. Ключи для шифрования и для расшифровывания могут отличаться, а могут быть одинаковыми. Секретность второго(расшифровывающего) из них делает данные недоступными для несанкционированного ознакомления, а секретность первого(шифрующего) делает невозможным навязывание ложных данных. В первых методах шифрования использовались одинаковые ключи, однако в 1976 году были открыты алгоритмы с применением разных ключей. Сохранение этих ключей в секретности и правильное их разделение между адресатами является очень важной задачей с точки зрения сохранения конфиденциальности передаваемой информации. Эта задача исследуется в теории управления ключами(в некоторых источниках она упоминается как разделение секрета).^[3]

В настоящий момент существует огромное количество методов шифрования. Главным образом эти методы делятся, в зависимости от структуры используемых ключей, на симметричные методы и асимметричные методы. Кроме того методы шифрования могут обладать различной криптостойкостью и по разному обрабатывать входные данные — блочные шифры и поточные шифры. Всеми этими методами их созданием и анализом занимается наука криптография.^[6]

Зашифрование и расшифрование

Как было сказано, шифрование состоит из двух взаимно обратных процессов: зашифрование и расшифрование. Оба этих процесса на абстрактном уровне представимы математическими функциями, к которым предъявляются определенные требования. Математически, данные, используемые в шифровании, представимы в виде множеств над которыми построены данные функции. Иными словами, пусть существуют два множества, представляющее данные — , и ; и каждая из двух функций(шифрующая и расшифровывающая) является отображением одного из этих множеств в другое.^[6][7]

Шифрующая функция:

Расшифровывающая функция:

Элементы этих множеств — и являются аргументами соответствующих функций. Так же, в эти функции уже включено понятие ключа. То есть тот необходимый ключ для шифрования или расшифрования является частью функции. Это позволяет рассматривать процессы шифрования абстрактно, вне зависимости от структуры используемых ключей. Хотя, в общем случае, для каждой из этих функций аргументами являются данные и вводимый ключ.^[2]

Если для шифрования и расшифрования используется один и тот же ключ , то такой алгоритм относят к симметричным. Если же из ключа шифрования алгоритмически сложно получить ключ расшифрования, то алгоритм относят к асимметричным, то есть к алгоритмам с открытым ключом.^[8]

• Для применения в целях шифрования эти функции, в первую очередь, должны быть взаимно обратными.^[2]

• Важной характеристикой шифрующей функции является ее криптостойкость. Косвенной оценкой криптостойкости является оценка взаимной информации между открытым текстом и шифротекстом, которая должна стремиться к нулю.

Криптостойкость шифра

Криптографическая стойкость — способность криптографического шифра противостоять криптоанализу. То есть анализу направленному на изучение шифра, с целью его дешифрования. С целью изучения криптоустойчивости различных алгоритмов была создана специальная теория, изучающая типы шифров и их ключи, а также их стойкость. Основателем этой теории является Клод Шеннон. Криптостойкость шифра является его важнейшей характеристикой, которая отражает насколько успешно алгоритм решает задачу шифрования.^[9]

Любая система шифрования, кроме абсолютно криптостойких, может быть взломана простым перебором всех возможных в данном случае ключей. Но перебирать придется до тех пор, пока не отыщется тот единственный ключ, который и поможет расшифровать шифротекст. Выбор этого единственного ключа основан на способности отличить правильно расшифрованое сообщение. Зачастую, эта особенность является камнем преткновения при подборе ключа, так как, перебирая вручную, криптоаналитику, зачастую, достаточно просто отличить правильно расшифрованный текст, однако ручной перебор очень медленен. Если же, программа выполняет перебор, то это происходит быстрее, однако, ей сложно выделить правильный текст. Невозможность взлома полным перебором абсолютно криптостойкого шифра, так же, основана на способности отличить в расшифрованном сообщении именно то, которое было зашифровано в криптограмме. Перебирая все возможные ключи и применяя их к абсолютно стойкой системе, криптоаналитик получит множество всех возможных сообщений, которые можно было зашифровать(в нем могут содержаться и осмысленные сообщения). Кроме того, процесс полного перебора длительный и трудоемкий. О сложностях метода прямого перебора можно судить исходя из приведенной ниже таблицы.^[10]

Другой метод дешифровки основывается на анализе перехваченных сообщений. Этот метод имеет большое значение, так как перехват сообщений доступен злоумышленнику, если он обладает специальным оборудованием, а в отличие от достаточно мощного и дорогостоящего оборудования для решения задачи полного перебора, оборудование для перехвата сообщений более доступно. Например, перехват ван Эйка для ЭЛТ монитора осуществим с помощью обычной телевизионной антенны. Кроме того, существуют программы для перехвата сетевого трафика(снифферы), которые доступны и в бесплатных версиях.^[12][13][14]

При анализе передаваемых сообщений криптоустойчивость шифра оценивается из возможности получения дополнительной информации об исходном сообщении из перехваченного. Возможность получения этой информации является крайне важной характеристикой шифра, ведь эта информация, в конечном итоге, может позволить злоумышленнику дешифровать сообщение. В соответствии с этим, шифры делятся на абсолютно стойкие и достаточно стойкие.^[10][12]

Клод Шеннон впервые оценил количество подобной информации в зашифрованных сообщениях следующим образом^[10]

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

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

Через здесб обозначена вероятность того, что исходное сообщение есть при условии, что результат его зашифрования есть .

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

Эта величина всегда неотрицательна. Главным является то, насколько она положительна. Показателем здесь является то, насколько уменьшится неопределенность при получении соответствующего шифротекста, и не станет ли она таковой, что перехватив некоторое количество шифротекстов станет возможным расшифровка исходного сообщения.^[15]

Абсолютно стойкие системы

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

Таким образом злоумышленник не сможет извлечь никакой полезной информации об открытом тексте из перехваченного шифротекста. Шифр обладающий таким свойством называется абсолютно стойким.^[10]

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

• Ключ генерируется для каждого сообщения (каждый ключ используется один раз).
• Ключ статистически надёжен (то есть вероятности появления каждого из возможных символов равны, символы в ключевой последовательности независимы и случайны).
• Длина ключа равна или больше длины сообщения.

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

1. Шифрующая система должна создаваться с исключительно глубоким знанием структуры используемого языка передачи сообщений
2. Сложная структура естественных языков крайне сложна и для устранения избыточности передаваемой информации может потребоваться крайне сложное устройство.
3. Если в передаваемом сообщений возникает ошибка, то эта ошибка сильно разрастается на этапе кодирования и передачи, в связи со сложностью используемых устройств и алгоритмов.^[16]

Достаточно стойкие системы

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

Их криптостойкость зависит от того, какими вычислительными возможностями обладает криптоаналитик. Иными словами, шифротекст взламывается, если криптоаналитик обладает достаточными ресурсами, такими как время и количество перехваченных сообщений. Практическая стойкость таких систем основана на их вычислительной сложности и оценивается исключительно на определенный момент времени с двух позиций:^[17]

Добиться высокого уровня практической стойкости алгоритма можно двумя подходами:^[18]

1. Изучить методы, которыми пользуется злоумышленник и попытаться их изучить на используемой системе.
2. Составить шифр таким образом, что бы его сложность была эквивалентно сложности известной задачи, для решения которой требуется большой объем вычислительных работ.

Методы шифрования

Существующие методы шифрования можно разделить на две большие группы:^[6]

Также шифры могут отличаться структурой шифруемой информации. Они могут либо шифровать сразу весь текст, либо шифровать его по мере поступления. Таким образом существуют:^[6]

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

Блочный шифр можно превратить в поточный, разбивая входные данные на отдельные блоки и шифруя их по отдельности. Однако, блочные шифры являются более криптоустойчивыми по сравнению с поточными. Кроме того, блочные шифры работают зачастую быстрее и легко реализуемы посредством программного обеспечения. Поточные, же, шифры зачастую реализуются в аппаратном виде(в виде некой шифрующей аппаратуры), так как представление данных и их обработка в поточных шифрах очень близка к обработке данных и их передаче в аппаратуре. Там данные представляются именно потоком, чаще всего.^[6][19]

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

Симметричное шифрование

Симметричное шифрование

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

Симметричные, а конкретнее, алфавитные алгоритмы шифрования были одними из первых алгоритмов.^[20] Позднее было изобретено асимметричное шифрование, в котором ключи у собеседников разные.^[21]

Схема реализации

Задача. Есть два собеседника — Алиса и Боб, они хотят обмениваться конфиденциальной информацией.

• Генерация ключа.

Боб(или Алиса) выбирает ключ шифрования и алгоритм (функции шифрования и расшифрования), затем посылает эту информацию Алисе(Бобу).

• Шифрование и передача сообщения.

Алиса шифрует информацию с использованием полученного ключа .

И передает Бобу полученный шифротекст . То же самое делает Боб, если хочет отправить Алисе сообщение.

• Расшифрование сообщения.

Боб(Алиса), с помощью того же ключа , расшифровывает шифротекст .

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

Асимметричное шифрование (с открытым ключом)

Асимметричное шифрование

В системах с открытым ключом используются два ключа — открытый и закрытый, связанные определенным математическим образом друг с другом. Открытый ключ передаётся по открытому (то есть незащищённому, доступному для наблюдения) каналу и используется для шифрования сообщения и для проверки ЭЦП. Для расшифровки сообщения и для генерации ЭЦП используется секретный ключ.^[22]

Данная схема решает проблему симметричных схем, связанную с начальной передачей ключа другой стороне. Если в симметричных схемах злоумышленник перехватит ключ, то он сможет как «слушать», так и вносить правки в передаваемую информацию. В асимметричных системах другой стороне передается открытый ключ, который позволяет шифровать, но не расшифровывать информацию. Таким образом решается проблема симметричных систем, связанная с синхронизацией ключей.^[21]

Первыми исследователями, которые изобрели и раскрыли понятие шифрования с открытым кодом, были Уитфилд Диффи и Мартин Хеллман из Стэнфордского университета, и Ральф Меркле из Калифорнийского университета в Беркли. В 1976 году их работа «Новые направления в современной криптографии» открыла новую область в криптографии, теперь известную как криптография с открытым ключом.

Схема реализации

Задача. Есть два собеседника — Алиса и Боб, Алиса хочет передавать Бобу конфиденциальную информацию.

• Генерация ключевой пары.

Боб выбирает алгоритм и пару открытый, закрытый ключи — и посылает открытый ключ Алисе по открытому каналу.

• Шифрование и передача сообщения.

Алиса шифрует информацию с использованием открытого ключа Боба .

И передает Бобу полученный шифротекст .

• Расшифрование сообщения.

Боб, с помощью закрытого ключа , расшифровывает шифротекст .

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

Управление ключами

Основные угрозы ключам

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

Цели управления ключами

• Сохранение конфиденциальности закрытых ключей и передаваемой информации.
• Обеспечение надежности сгенерированых ключей.
• Предотвращение несанкционированного использования закрытых или открытых ключей, например использование ключа, срок действия которого истек.^[23][24][25]

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

Система генерации ключей обеспечивает составление криптоустойчивых ключей. Сам алгоритм генерации должен быть безопасным, так как значительная часть безопасности, предоставляемой шифрованием, заключена в защищенности ключа. Если выбор ключей доверить пользователям, то они с большей вероятностью выбирают ключи типа «Barney» нежели «*9(hH/A», просто потому что «Barney» проще запомнить. А такого рода ключи очень быстро подбираются методом вскрытия со словарем, и тут даже самый безопасный алгоритм не поможет. Кроме того, алгоритм генерации обеспечивает создание статистически независимых ключей нужной длины, используя наиболее криптоустойчивый алфавит.^[26]

Система контроля ключей служит для наиболее безопасной передачи ключей между собеседниками. Если передавать ключ шифрования по открытому каналу, который могут прослушивать, то злоумышленник легко перехватит ключ и все дальнейшее шифрование будет бессмысленным. Методы асимметричного шифрования решают эту проблему, используя разные ключи для зашифрования и расшифрования. Однако при таком подходе количество ключей растет с увеличением количества собеседников(каждый вынужден хранить свои закрытый и открытый ключи и открытые ключи всех собеседников). Кроме того, методы асимметричного шифрования не всегда доступны и осуществимы. В таких ситуациях используются разные методы по обеспечению безопасной доставки ключей, одни основаны на использовании для доставки ключей альтернативных каналов, считающихся безопасными. Другие, в согласии со стандартом X9.17, используют два типа ключей — ключи шифрования ключей и ключи шифрования данных. Третьи, разбивают передаваемый ключ на составные части и передают их по различным каналам. Так же, существуют различные комбинации перечисленных выше методов.^[27]

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

Правовые нормы

Развитие шифрования и его методов привело к их широчайшей распространенности. Сейчас, для конечного пользователя не составляет труда зашифровать раздел на жестком диске или переписку и установить защищенное соединение в интернет. В связи с тем, что шифрование и другие информационные технологии проникают в наш быт, растет число компьютерных преступлений. Зашифрованная информация, так или иначе, представляет собой объект защиты, который, в свою очередь, должен подвергаться правовому регулированию. Кроме того, подобные правовые нормы необходимы из-за того, что существует некоторое противоречие между стремлением правительств иметь доступ к информации(с целью обеспечения безопасности и для предотвращения преступлений), и стремлением граждан обеспечить высокий уровень охраны для своей действительно секретной информации. Для разрешения этой проблемы, прибегают к разным способам, это и возможный запрет на использование высокоэффективных методов шифрования, и требование передачи компетентным органам шифровальных ключей. Различия в правилах и ограничениях по шифрованию компьютерной информации могут создать определенные трудности в деловых международных контактах в плане обеспечения конфиденциальности их общения. В связи с этим, в любом государстве, поведение в отношении передачи и шифрования информации регулируется различными правовыми нормами.^[28]

Примечания

1. ↑ ^{1 2 3 4} Мэйволд, 2006, Глава 12.Шифрование
2. ↑ ^{1 2 3} Шнайер, 2002, с. 8
3. ↑ ^{1 2} Шнайер, 2002, с. 8-9
4. ↑ Шнайер, 2002, Введение
5. ↑ Жельников, 1996, Введение
6. ↑ ^{1 2 3 4 5} Шнайер, 2002, Глава 1. Основные понятия
7. ↑ Шеннон, 1963, с. 1-8
8. ↑ Шнайер, 2002, с. 9-10
9. ↑ Мао, 2005, с. 43-45
10. ↑ ^{1 2 3 4} Шеннон, 1963, Часть 2.Теоретическая секретность.
11. ↑ Шнайер, 2002, Таблица 7-1
12. ↑ ^{1 2} Мао, 2005, с. 45-48
13. ↑ Шеннон, 1963, с. 12
14. ↑ Wim van Eck Electromagnetic Radiation from Video Display Units: An Eavesdropping Risk? (англ.) // Computers & Security : журнал. — Elsevier Advanced Technology Publications, 1985. — В. 4. — Т. 4. — С. 269—286. — ISSN 01674048. — DOI:10.1016/0167-4048(85)90046-X
15. ↑ Шеннон, 1963, Часть 2.Теоретическая секретность, с. 23-27
16. ↑ Шеннон, 1963, Часть 2.Теоретическая секретность, с. 37
17. ↑ Шеннон, 1963, Части 2 и 3.
18. ↑ Шеннон, 1963, с. 39-40
19. ↑ Шнайер, 2002, Глава 9. Типы алгоритмов и криптографические режимы
20. ↑ Павел Исаев. Некоторые алгоритмы ручного шифрования (рус.) // КомпьютерПресс. — 2003. — В. 3.
21. ↑ ^{1 2} Уитфилд Диффи, Мартин Хеллман Новые направления в криптографии (англ.). — 1976.
22. ↑ Шнайер, 2002, Глава 1 и 19
23. ↑ ^{1 2 3} Шнайер, 2002, Глава 8
24. ↑ Алферов, 2002, с. 68-69
25. ↑ Мао, 2005, с. 61-62
26. ↑ Шнайер, 2002, Глава 8.1
27. ↑ Шнайер, 2002, Глава 8.3
28. ↑ Колесников Дмитрий Геннадьевич Защита информации в компьютерных системах (рус.).

Литература

• Венбо Мао Современная криптография. Теория и практика = Modern Cryptography: Theory and Practice. — М.: Вильямс, 2005. — 768 p. — 2000 экз. — ISBN 5-8459-0847-7

• А. П. Алферов, А. Ю. Зубов, А. С. Кузьмин, А. В. Черемушкин Основы Криптографии.. — Гелиос АРВ, 2002. — 480 с.

См. также

Ссылки

Введение в криптографию и шифрование, часть первая. Лекция в Яндексе

Чтобы сходу понимать материалы об инфраструктуре открытых ключей, сетевой безопасности и HTTPS, нужно знать основы криптографической теории. Один из самых быстрых способов изучить их — посмотреть или прочитать лекцию Владимира ivlad Иванова. Владимир — известный специалист по сетям и системам их защиты. Он долгое время работал в Яндексе, был одним из руководителей нашего департамента эксплуатации.

Мы впервые публикуем эту лекцию вместе с расшифровкой. Начнём с первой части. Под катом вы найдёте текст и часть слайдов.

---

Я когда-то читал в МГУ лекции по крипте, и они занимали у меня по полгода. Я попытаюсь вам всё рассказать за два с половиной часа. Никогда этого не делал. Вот и попробуем.

Кто понимает, что такое DES? AES? TLS? Биноминальное отображение?

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

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

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

Сегодня мы попробуем чуть-чуть поговорить про то, как вырабатываются ключи. В общем виде поговорим о том, как отправить защищенное сообщение, используя криптопримитивы, которые у нас есть, от одного пользователя другому.

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

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

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

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

Первый криптографический примитив — симметричные шифры.

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

Какие здесь важные нюансы? В большинстве распространенных алгоритмов симметричного шифрования, с которыми можно столкнуться, размер шифротекста всегда равен размеру открытого текста. Современные алгоритмы шифрования оперируют размерами ключей. Размер ключей измеряется в битах. Современный размер — от 128 до 256 бит для алгоритмов симметричного шифрования. Об остальном, в том числе о размере блока, мы поговорим позже.

Исторически, в условном IV веке до нашей эры, существовало два метода дизайна шифров: шифры подстановки и перестановки. Шифры подстановки — алгоритм, где в те времена заменяли одну букву сообщения на другую по какому-то принципу. Простой шифр подстановки — по таблице: берем таблицу, где написано, что А меняем на Я, Б на Ю и т. д. Дальше по этой таблице шифруем, по ней же дешифруем.

Как вы считаете, с точки зрения размера ключа насколько это сложный алгоритм? Сколько вариантов ключей существует? Порядок факториала длины алфавита. Мы берем таблицу. Как мы ее строим? Допустим, есть таблица на 26 символов. Букву А можем заменить на любой из них, букву Б — на любой из оставшихся 25, С — на любой из оставшихся 24… Получаем 26*25*24*… — то есть факториал от 26. Факториал размерности алфавита.

Если взять log₂26!, это будет очень много. Думаю, вы точно получите в районе 100 бит длины ключа, а то и поболее. Оказалось, что с точки зрения формального представления стойкости указанный алгоритм шифрования — довольно неплохой. 100 бит — приемлемо. При этом все, наверное, в детстве или юности, когда сталкивались с кодировками, видели, что такие алгоритмы дешифруются тривиально. Проблем с расшифровкой нет.

Долго существовали всякие алгоритмы подстановки в разных конструкциях. Одним из них, еще более примитивным, является шифр Цезаря, где таблица формируется не случайной перестановкой символов, а сдвигом на три символа: А меняется на D, B на Е и т. д. Понятно, что шифр Цезаря вместе со всеми его вариантами перебрать очень легко: в отличие от табличной подстановки, в ключе Цезаря всего 25 вариантов при 26 буквах в алфавите — не считая тривиального шифрования самого в себя. И его как раз можно перебрать полным перебором. Здесь есть некоторая сложность.

Почему шифр табличной подстановки такой простой? Откуда возникает проблема, при которой мы можем легко, даже не зная ничего про криптографию, расшифровать табличную подстановку? Дело в частотном анализе. Есть самые распространенные буквы — какая-нибудь И или Е. Их распространенность велика, гласные встречаются намного чаще, чем согласные, и существуют негативные пары, никогда не встречающиеся в естественных языках, — что-то вроде ЬЪ. Я даже давал студентам задание сделать автоматический дешифратор шифра подстановки, и, в принципе, многие справлялись.

В чем проблема? Надо статистику распределения букв исказить, чтобы распространенные буквы не так светились в зашифрованном тексте. Очевидный способ: давайте будем шифровать самые часто встречающиеся буквы не в один символ, а в пять разных, например. Если буква встречается в среднем в пять раз чаще, то давайте по очереди — сначала в первый символ будем зашифровывать, потом во второй, в третий и т. д. Далее у нас получится маппинг букв не 1 к 1, а, условно, 26 к 50. Статистика, таким образом, нарушится. Перед нами первый пример полиалфавитного шифра, который как-то работал. Однако с ним есть довольно много проблем, а главное, очень неудобно работать с таблицей.

Дальше придумали: давайте не будем шифровать такими таблицами, а попробуем брать шифр Цезаря и для каждой следующей буквы изменять сдвиг. Результат — шифр Виженера.

Берем в качестве ключа слово ВАСЯ. Берем сообщение МАША. Задействуем шифр Цезаря, но отсчитывая от этих букв. Например, В — третья буква в алфавите. Мы должны сдвинуть на три буквы соответствующую букву в открытом тексте. М сдвигается в П. А в А. Ш — на 16, перескочим букву А, получим, условно, Д. Я сдвинет А в Я. ПАДЯ.

Что удобно в получившемся шифре? Здесь было две одинаковых буквы, но в результате они зашифровались в разные. Это классно, потому что размывает статистику. Метод хорошо работал, пока где-то в XIX веке, буквально недавно на фоне истории криптографии, не придумали, как его ломать. Если посмотреть на сообщение из нескольких десятков слов, а ключ довольно короткий, то вся конструкция выглядит как несколько шифров Цезаря. Мы говорим: окей, давайте каждую четвертую букву — первую, пятую, девятую — рассматривать как шифр Цезаря. И поищем среди них статистические закономерности. Мы обязательно их найдем. Потом возьмем вторую, шестую, десятую и так далее. Опять найдем. Тем самым мы восстановим ключ. Единственная проблема — понять, какой он длины. Это не очень сложно, ну какой он может быть длины? Ну 4, ну 10 символов. Перебрать 6 вариантов от 4 до 10 не очень сложно. Простая атака — она была доступна и без компьютеров, просто за счет ручки и листа бумаги.

Как из этой штуки сделать невзламываемый шифр? Взять ключ размера текста. Персонаж по имени Клод Шэннон в ХХ веке, в 1946 году, написал классическую первую работу по криптографии как по разделу математики, где сформулировал теорему. Длина ключа равна длине сообщения — он использовал XOR вместо сложения по модулю, равному длине алфавита, но в данной ситуации это не очень принципиально. Ключ сгенерирован случайным образом, является последовательностью случайных бит, и на выходе тоже получится случайная последовательность бит. Теорема: если у нас есть такой ключ, то подобная конструкция является абсолютно стойкой. Доказательство не очень сложное, но сейчас не буду про него говорить.

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

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

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

Помимо шифров подстановки, были еще шифры перестановки. С ними тоже все довольно просто. Берем сообщение ВАСЯИ, записываем его в блок какой-то длины, например в ДИДОМ, и считываем результат так же.

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

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

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

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

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

Из этой истории есть одно занятное исключение — шифроблокноты. Речь идет о настоящей шпионской истории про настоящий шпионаж. Некие люди, которым нужна абсолютно устойчивая коммуникация, генерируют случайные числа — например, буквальным бросанием кубика или буквальным выниманием шаров из барабана, как в лото. Создают два листа, где печатают эти случайные числа. Один лист отдают получателю, а второй оставляют у отправителя. При желании пообщаться они используют этот поток случайных чисел в качестве ключевого потока. Нет, история взята не из совсем далекого прошлого. У меня есть настоящий радиоперехват от 15 октября 2014 года: 7 2 6, 7 2 6, 7 2 6. Это позывной. 4 8 3, 4 8 3, 4 8 3. Это номер шифроблокнота. 5 0, 5 0, 5 0. Это количество слов. 8 4 4 7 9 8 4 4 7 9 2 0 5 1 4 2 0 5 1 4 и т. д. 50 таких числовых групп. Не знаю где, где-то не в России сидел какой-нибудь человек с ручкой и карандашом у обычного радиоприемника и записывал эти цифры. Записав их, он достал похожую штуку, сложил их по модулю 10 и получил свое сообщение. Другими словами, это реально работает, и подобное сообщение нельзя взломать. Если действительно были сгенерированы хорошие случайные числа и он впоследстии сжег бумажку с ключом, то осуществить взлом нельзя никак, совсем.

Но тут есть довольно много проблем. Первая — как нагенерировать по-настоящему хорошие случайные числа. Мир вокруг нас детерминирован, и если мы говорим про компьютеры, они детерминированы полностью.

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

Самый исторически распространенный алгоритм подобного рода называется RC4. Он был разработан Роном Ривестом лет 25 назад и активно использовался очень долго, был самым распространенным алгоритмом для TLS, всех его различных вариантов, включая HTTPS. Но в последнее время RC4 начал показывать свой возраст. Для него существует некоторое количество атак. Он активно используется в WEP. Была одна хорошая лекция Антона, история, которая показывает: плохое применение пристойного даже по нынешним меркам алгоритма шифрования приводит к тому, что компрометируется вся система.

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

Большое достоинство RC4 — в том, что он целиком внутрибайтовый, а значит, его программная реализация работает довольно быстро — сильно быстрее, в разы, если не в десятки раз быстрее, чем сравнимый и существовавший примерно в одно время с ним шифр DES. Поэтому RC4 и получил такое распространение. Он долго был коммерческим секретом компании RSA, но потом, где-то в районе 90-х годов, некие люди анонимно опубликовали исходники его устройства в списке рассылки cypherpunks. В результате возникло много драмы, были крики, мол, как же так, какие-то неприличные люди украли интеллектуальную собственность компании RSA и опубликовали ее. RSA начала грозить всем патентами, всевозможными юридическими преследованиями. Чтобы их избежать, все реализации алгоритма, которые находятся в опенсорсе, называются не RC4, а ARC4 или ARCFOUR. А — alleged. Речь идет о шифре, который на всех тестовых кейсах совпадает с RC4, но технически вроде как им не является.

Если вы конфигурируете какой-нибудь SSH или OpenSSL, вы в нем не найдете упоминания RC4, а найдете ARC4 или что-то подобное. Несложная конструкция, он уже старенький, на него сейчас есть атаки, и он не очень рекомендуется к использованию.

Было несколько попыток его заменить. Наверное, на мой предвзятый взгляд самым успешным стал шифр Salsa20 и несколько его последователей от широко известного в узких кругах персонажа Дэна Берштайна. Линуксоидам он обычно известен как автор qmail.

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

Salsa20 устроен так, чтобы он всегда выполнялся за константное одинаковое время. Внутри он состоит всего из трех примитивов: это сдвиг на константное время, а также сложение по модулю 2 и по модулю 32, 32-битных слов. Скорость Salsa20 еще выше, чем у RC4. Он пока что не получил такого широкого распространения в общепринятой криптографии — у нас нет cipher suite для TLS, использующих Salsa20, — но все равно потихоньку становится мейнстримом. Указанный шифр стал одним из победителей конкурса eSTREAM по выбору лучшего поточного шифра. Их там было четыре, и Salsa — один из них. Он потихоньку начинает появляться во всяких опенсорс-продуктах. Возможно, скоро — может, через пару лет — появятся даже cipher suite в TLS с Salsa20. Мне он очень нравится.

На него имеется некоторое количество криптоанализа, есть даже атаки. Снаружи он выглядит как поточный, генерируя на основе ключа последовательность почти произвольной длины, 2⁶⁴. Зато внутри он работает как блочный. В алгоритме есть место, куда можно подставить номер блока, и он выдаст указанный блок.

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

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

В Salsa указанная проблема решена, поскольку в нем на вход поступает в том числе и номер блока, который надо сгенерировать. Дальше к номеру блока 20 раз применяется алгоритм. 20 раундов — и мы получаем 512 бит выходного потока.

Самая успешная атака — в 8 раундов. Сам он 256-битный, а сложность атаки в 8 раундов — 250 или 251 бит. Считается, что он очень устойчивый, хороший. Публичный криптоанализ на него есть. Несмотря на всю одиозность личности Берштайна в этом аспекте, мне кажется, что штука хорошая и у нее большее будущее.

Исторически поточных шифров было много. Они первые не только в коммерческом шифровании, но и в военном. Там использовалось то, что называлось линейными регистрами сдвига.

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

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

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

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

Размер блока в современных шифрах — как правило, 128 бит. Бывают разные вариации, но как правило, речь идет про 128 или 256 бит, не больше и не меньше. Размер ключа — точно такой же, как для поточных алгоритмов: 128 или 256 бит в современных реализациях, от и до.

Из всех широко распространенных блочных шифров сейчас можно назвать два — DES и AES. DES очень старый шифр, ровесник RC4. У DES сейчас размер блока — 64 бита, а размер ключа — 56 бит. Создан он был в компании IBM под именем Люцифер. Когда в IBM его дизайном занимался Хорст Фейстель, они предложили выбрать 128 бит в качестве размера блока. А размер ключа был изменяемый, от 124 до 192 бит.

Когда DES начал проходит стандартизацию, его подали на проверку в том числе и в АНБ. Оттуда он вернулся с уменьшенным до 64 бит размером блока и уменьшенным до 56 бит размером ключа.

20 лет назад вся эта история наделала много шума. Все говорили — наверняка они туда встроили закладку, ужасно, подобрали такой размер блока, чтобы получить возможность атаковать. Однако большое достоинство DES в том, что это первый шифр, который был стандартизован и стал тогда основой коммерческой криптографии.

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

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

У нее есть несколько интересных достоинств. Первое важное достоинство: функция F может быть любой. Она не должна обладать свойствами обратимости, она может и не быть линейной или нелинейной. Все равно шифр остается симметричным.

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

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

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

Раунд тоже выглядит довольно несложно — он состоит всего из двух-трех операций. Первая операция: размер попавшегося полублока становится равен 32 бита, полубок проходит функцию расширения, на вход попадает 32 бита. Дальше мы по специальной несекретной таблице немного добавляем к 32 битам, превращая их в 48: некоторые биты дублируются и переставляются, такая гребеночка.

Потом мы его ксорим с раундовым ключом, размер которого — тоже 48 бит, и получаем 48-битное значение.
Затем оно попадает в набор функций, которые называются S-боксы и преобразуют каждый бит входа в четыре бита выхода. Следовательно, на выходе мы из 48 бит снова получаем 32 бита.

И наконец, окончательная перестановка P. Она опять перемешивает 32 бита между собой. Все очень несложно, раундовая функция максимально простая.

Самое интересное ее свойство заключается в указанных S-боксах: задумано очень сложное превращение 6 бит в 4. Если посмотреть на всю конструкцию, видно, что она состоит из XOR и пары перестановок. Если бы S-боксы были простыми, весь DES фактически представлял бы собой некоторый набор линейных преобразований. Его можно было бы представить как матрицу, на которую мы умножаем наш открытый текст, получая шифротекст. И тогда атака на DES была бы тривиальной: требовалось бы просто подобрать матрицу.

Вся нелинейность сосредоточена в S-боксах, подобранных специальным образом. Существуют разные анекдоты о том, как именно они подбирались. В частности, примерно через 10 лет после того, как DES был опубликован и стандартизован, криптографы нашли новый тип атак — дифференциальный криптоанализ. Суть атаки очень простая: мы делаем мелкие изменения в открытом тексте — меняя, к примеру, значение одного бита с 0 на 1 — и смотрим, что происходит с шифротекстом. Выяснилось, что в идеальном шифре изменение одного бита с 0 на 1 должно приводить к изменению ровно половины бит шифротекста. Выяснилось, что DES, хоть он и был сделан перед тем, как открыли дифференциальный криптоанализ, оказался устойчивым к этому типу атак. В итоге в свое время возникла очередная волна паранойи: мол, АНБ еще за 10 лет до открытых криптографов знало про существование дифференциального криптоанализа, и вы представляете себе, что оно может знать сейчас.

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

56 бит сейчас уже можно просто перебрать на кластере машин общего назначения — может, даже на одном. И это плохо. Что можно предпринять?

Просто сдвинуть размер ключа нельзя: вся конструкция завязана на его длину. Triple DES. Очевидный ответ был таким: давайте мы будем шифровать наш блок несколько раз, устроим несколько последовательных шифрований. И здесь всё не слишком тривиально.

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

Окей, 56 бит. Давайте возьмем два — k1 и k2. 56 + 56 = 112 бит. 112 бит даже по нынешним меркам — вполне приемлемая длина ключа. Можно считать нормальным всё, что превышает 100 бит. Так почему нельзя использовать два шифрования, 112 бит?

Одно шифрование DES состоит из 16 раундов. Сеть применяется 16 раз. Изменения слева направо происходят 16 раз. И он — не группа. Есть доказательство того, что не существует такого ключа k3, которым мы могли бы расшифровать текст, последовательно зашифрованный выбранными нами ключами k1 и k2.

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

Эффективная стойкость алгоритма — не 112 бит, а 57, если у нас достаточно памяти. Нужно довольно много памяти, но тем не менее. Поэтому решили — так работать нельзя, давайте будем шифровать три раза: k1, k2, k3. Конструкция называется Triple DES. Технически она может быть устроена по-разному. Поскольку в DES шифрование и дешифрование — одно и то же, реальные алгоритмы иногда выглядят так: зашифровать, расшифровать и снова расшифровать — чтобы выполнять операции в аппаратных реализациях было проще.

Наша обратная реализация Triple DES превратится в аппаратную реализацию DES. Это может быть очень удобно в разных ситуациях для задачи обратной совместимости.

Где применялся DES? Вообще везде. Его до сих пор иногда можно пронаблюдать для TLS, существуют cipher suite для TLS, использующие Triple DES и DES. Но там он активно отмирает, поскольку речь идет про софт. Софт легко апдейтится.

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

Однажды DES стал показывать свой возраст, с ним стало тяжело, и люди решили придумать нечто поновее. Американская контора по стандартизации, которая называется NIST, сказала: давайте проведем конкурс и выберем новый классный шифр. Им стал AES.

DES расшифровывается как digital encrypted standard. AES — advanced encrypted standard. Размер блока в AES — 128 бит, а не 64. Это важно с точки зрения криптографии. Размер ключа у AES — 128, 192 или 256 бит. В AES не используется сеть Фейстеля, но он тоже многораундовый, в нем тоже несколько раз повторяются относительно примитивные операции. Для 128 бит используется 10 раундов, для 256 — 14.

Сейчас покажу, как устроен каждый раунд. Первый и последний раунды чуть отличаются от стандартной схемы — тому есть причины.

Как и в DES, в каждом раунде AES есть свои раундовые ключи. Все они генерируются из ключа шифрования для алгоритма. В этом месте AES работает так же, как DES. Берется 128-битный ключ, из него генерируется 10 подключей для 10 раундов. Каждый подключ, как и в DES, применяется на каждом конкретном раунде.

Каждый раунд состоит из четырех довольно простых операций. Первый раунд — подстановка по специальной таблице.

В AES мы строим байтовую матрицу размером 4 на 4. Каждый элемент матрицы — байт. Всего получается 16 байт или 128 бит. Они и составляют блок AES целиком.

Вторая операция — побайтовый сдвиг.

Устроен он несложно, примитивно. Мы берем матрицу 4 на 4. Первый ряд остается без изменений, второй ряд сдвигается на 1 байт влево, третий — на 2 байта, четвертый — на 3, циклично.

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

Четвертая, вновь очень простая операция — XOR каждого байта в каждой колонке с соответствующим байтом ключа. Получается результат.

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

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

Мы повторяем 4 описанных шага 10 раз, и на выходе из 128-битного блока снова получаем 128-битный блок.

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

Производители современных процессоров, Intel и AMD, уже разработали ассемблерные инструкции для реализации AES внутри чипа, потому что стандарт довольно несложный. Как итог — AES еще быстрее. Если через DES на современной машинке мы можем зашифровать, например, 1-2 гигабита, то 10-гигабитный AES-шифратор находится рядом и коммерчески доступен обычным компаниям.

Блочный алгоритм шифрует блок в блок. Он берет блок на 128 или 64 бита и превращает его в блок на 128 или 64 бита.

А что мы будем делать, если потребуется больше, чем 16 байт?

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

Да, очевидно, побьем всё на блоки по 16 байт и зашифруем. Такое шифрование называется ECB — electronic code boot, когда каждый из блоков по 16 байт в случае AES или по 8 байт в случае DES шифруется независимо.

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

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

Надо бы как-нибудь исхитриться и сделать так, чтобы результат на выходе все время получался разным, в зависимости от местонахождения блока — несмотря на то, что на вход подаются одинаковые блоки шифротекста. Первым способом решения стал режим CBC.

Мы не только берем ключ и открытый текст, но и генерируем случайное число, которое не является секретным. Оно размером с блок. Называется оно инициализационным вектором.

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

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

Однако у CBC есть несколько проблем.

О размере блока. Представьте: мы начали шифровать и, допустим, у нас DES. Если бы DES был идеальным алгоритмом шифрования, выход DES выглядел бы как равномерно распределенные случайные числа длиной 64 бита. Какова вероятность, что в выборке из равномерно распределенных случайных чисел длиной 64 бита два числа совпадут для одной операции? 1/(2⁶⁴). А если мы сравниваем три числа? Давайте пока прервемся.

Назначение и структура алгоритмов шифрования

Шифрование является наиболее широко используемым криптографическим методом сохранения конфиденциальности информации, он защищает данные от несанкционированного ознакомления с ними. Для начала рассмотрим основные методы криптографической защиты информации. Словом, криптография — наука о защите информации с использованием математических методов. Существует и наука, противоположная криптографии и посвященная методам вскрытия защищенной информации — криптоанализ. Совокупность криптографии и криптоанализа принято называть криптологией. Криптографические методы могут быть классифицированы различным образом, но наиболее часто они подразделяются в зависимости от количества ключей, используемых в соответствующих криптоалгоритмах (см. рис. 1):

1. Бесключевые, в которых не используются какие-либо ключи.
2. Одноключевые — в них используется некий дополнительный ключевой параметр — обычно это секретный ключ.
3. Двухключевые, использующие в своих вычислениях два ключа: секретный и открытый.

Рис. 1. Криптоалгоритмы

Обзор криптографических методов

Шифрование является основным методом защиты; рассмотрим его подробно далее.

Стоит сказать несколько слов и об остальных криптографических методах:

1. Электронная подпись используется для подтверждения целостности и авторства данных. Целостность данных означает, что данные не были случайно или преднамеренно изменены при их хранении или передаче.
   Алгоритмы электронной подписи используют два вида ключей:
   • секретный ключ используется для вычисления электронной подписи;
   • открытый ключ используется для ее проверки.
   При использовании криптографически сильного алгоритма электронной подписи и при грамотном хранении и использовании секретного ключа (то есть при невозможности использования ключа никем, кроме его владельца) никто другой не в состоянии вычислить верную электронную подпись какого-либо электронного документа.
2. Аутентификация позволяет проверить, что пользователь (или удаленный компьютер) действительно является тем, за кого он себя выдает. Простейшей схемой аутентификации является парольная — в качестве секретного элемента в ней используется пароль, который предъявляется пользователем при его проверке. Такая схема доказано является слабой, если для ее усиления не применяются специальные административно-технические меры. А на основе шифрования или хэширования (см. ниже) можно построить действительно сильные схемы аутентификации пользователей.
3. Существуют различные методы криптографического контрольного суммирования:
   • ключевое и бесключевое хэширование;
   • вычисление имитоприставок;
   • использование кодов аутентификации сообщений.
   Фактически, все эти методы различным образом из данных произвольного размера с использованием секретного ключа или без него вычисляют некую контрольную сумму фиксированного размера, однозначно соответствующую исходным данным.
   Такое криптографическое контрольное суммирование широко используется в различных методах защиты информации, например:
   • для подтверждения целостности любых данных в тех случаях, когда использование электронной подписи невозможно (например, из-за большой ресурсоемкости) или является избыточным;
   • в самих схемах электронной подписи — «подписывается» обычно хэш данных, а не все данные целиком;
   • в различных схемах аутентификации пользователей.
4. Генераторы случайных и псевдослучайных чисел позволяют создавать последовательности случайных чисел, которые широко используются в криптографии, в частности:
   • случайные числа необходимы для генерации секретных ключей, которые, в идеале, должны быть абсолютно случайными;
   • случайные числа применяются во многих алгоритмах электронной подписи;
   • случайные числа используются во многих схемах аутентификации.
   Не всегда возможно получение абсолютно случайных чисел — для этого необходимо наличие качественных аппаратных генераторов. Однако, на основе алгоритмов симметричного шифрования можно построить качественные генераторы псевдослучайных чисел.

Шифрование

Шифрование информации — это преобразование открытой информации в зашифрованную (которая чаще всего называется шифртекстом или криптограммой), и наоборот. Первая часть этого процесса называется зашифрованием, вторая — расшифрованием.

Можно представить зашифрование в виде следующей формулы:

С = E_k1(M),

где:
M (message) — открытая информация,
С (cipher text) — полученный в результате зашифрования шифртекст,
E (encryption) — функция зашифрования, выполняющая криптографические преобразования над M,
k1 (key) — параметр функции E, называемый ключом зашифрования.

В стандарте ГОСТ 28147-89 (стандарт определяет отечественный алгоритм симметричного шифрования) понятие ключ определено следующим образом: «Конкретное секретное состояние некоторых параметров алгоритма криптографического преобразования, обеспечивающее выбор одного преобразования из совокупности всевозможных для данного алгоритма преобразований».

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

Аналогичным образом можно представить и расшифрование:

M’ = D_k2(C),

где:
M’— сообщение, полученное в результате расшифрования,
D (decryption) — функция расшифрования; так же, как и функция зашифрования, выполняет криптографические преобразования над шифртекстом,
k2 — ключ расшифрования.

Для получения в результате расшифрования корректного открытого текста (то есть того самого, который был ранее зашифрован: M’ = M), необходимо одновременное выполнение следующих условий:

1. Функция расшифрования должна соответствовать функции зашифрования.
2. Ключ расшифрования должен соответствовать ключу зашифрования.

При отсутствии верного ключа k2 получить исходное сообщение M’ = M с помощью правильной функции D невозможно. Под словом «невозможно» в данном случае обычно понимается невозможность вычисления за реальное время при существующих вычислительных ресурсах.

Алгоритмы шифрования можно разделить на две категории (см. рис. 1):

1. Алгоритмы симметричного шифрования.
2. Алгоритмы асимметричного шифрования.

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

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

k1 = a^k2 mod p,

где a и p — параметры алгоритма шифрования, имеющие достаточно большую размерность.

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

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

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

Симметричное шифрование бывает двух видов:

• Блочное шифрование — информация разбивается на блоки фиксированной длины (например, 64 или 128 бит), после чего эти блоки поочередно шифруются. Причем, в различных алгоритмах шифрования или даже в разных режимах работы одного и того же алгоритма блоки могут шифроваться независимо друг от друга или «со сцеплением» — когда результат зашифрования текущего блока данных зависит от значения предыдущего блока или от результата зашифрования предыдущего блока.
• Поточное шифрование — необходимо, прежде всего, в тех случаях, когда информацию невозможно разбить на блоки — скажем, некий поток данных, каждый символ которых должен быть зашифрован и отправлен куда-либо, не дожидаясь остальных данных, достаточных для формирования блока. Поэтому алгоритмы поточного шифрования шифруют данные побитно или посимвольно. Хотя стоит сказать, что некоторые классификации не разделяют блочное и поточное шифрование, считая, что поточное шифрование — это шифрование блоков единичной длины.

Рассмотрим, как выглядят изнутри алгоритмы блочного симметричного шифрования.Структура алгоритмов шифрования

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

1. Алгоритмы на основе сети Фейстеля.

   Сеть Фейстеля подразумевает разбиение обрабатываемого блока данных на несколько субблоков (чаще всего — на два), один из которых обрабатывается некоей функцией f() и накладывается на один или несколько остальных субблоков. На рис. 2 приведена наиболее часто встречающаяся структура алгоритмов на основе сети Фейстеля.
   

   Рис. 2. Структура алгоритмов на основе сети Фейстеля.

   Дополнительный аргумент функции f(), обозначенный на рис. 2 как Ki, называется ключом раунда. Ключ раунда является результатом обработки ключа шифрования процедурой расширения ключа, задача которой — получение необходимого количества ключей Ki из исходного ключа шифрования относительно небольшого размера (в настоящее время достаточным для ключа симметричного шифрования считается размер 128 бит). В простейших случаях процедура расширения ключа просто разбивает ключ на несколько фрагментов, которые поочередно используются в раундах шифрования; существенно чаще процедура расширения ключа является достаточно сложной, а ключи Ki зависят от значений большинства бит исходного ключа шифрования.

   Наложение обработанного субблока на необработанный чаще всего выполняется с помощью логической операции «исключающее или» — XOR (как показано на рис. 2). Достаточно часто вместо XOR здесь используется сложение по модулю 2ⁿ, где n — размер субблока в битах. После наложения субблоки меняются местами, то есть в следующем раунде алгоритма обрабатывается уже другой субблок данных.

   Такая структура алгоритмов шифрования получила свое название по имени Хорста Фейстеля (Horst Feistel) — одного из разработчиков алгоритма шифрования Lucifer и разработанного на его основе алгоритма DES (Data Encryption Standard) — бывшего (но до сих пор широко используемого) стандарта шифрования США. Оба этих алгоритма имеют структуру, аналогичную показанной на рис. 2. Среди других алгоритмов, основанных на сети Фейстеля, можно привести в пример отечественный стандарт шифрования ГОСТ 28147-89, а также другие весьма известные алгоритмы: RC5, Blowfish, TEA, CAST-128 и т.д.

   На сети Фейстеля основано большинство современных алгоритмов шифрования — благодаря множеству преимуществ подобной структуры, среди которых стоит отметить следующие:

   • Алгоритмы на основе сети Фейстеля могут быть сконструированы таким образом, что для зашифрования и расшифрования могут использоваться один и тот же код алгоритма — разница между этими операциями может состоять лишь в порядке применения ключей Ki; такое свойство алгоритма наиболее полезно при его аппаратной реализации или на платформах с ограниченными ресурсами; в качестве примера такого алгоритма можно привести ГОСТ 28147-89.

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

   Существует и более сложная структура сети Фейстеля, пример которой приведен на рис. 3.
   

   Рис. 3. Структура сети Фейстеля.

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

3. Алгоритмы на основе подстановочно-перестановочных сетей (SP-сеть — Substitution-permutation network).

   В отличие от сети Фейстеля, SP-сети обрабатывают за один раунд целиком шифруемый блок. Обработка данных сводится, в основном, к заменам (когда, например, фрагмент входного значения заменяется другим фрагментом в соответствии с таблицей замен, которая может зависеть от значения ключа Ki) и перестановкам, зависящим от ключа Ki (упрощенная схема показана на рис. 4).
   

   Рис. 4. Подстановочно-перестановочная сеть.

   Впрочем, такие операции характерны и для других видов алгоритмов шифрования, поэтому, на мой взгляд, название «подстановочно-перестановочная сеть» является достаточно условным.

   SP-сети распространены существенно реже, чем сети Фейстеля; в качестве примера SP-сетей можно привести алгоритмы Serpent или SAFER+.

4. Алгоритмы со структурой «квадрат» (Square).

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

   Структура алгоритма получила свое название от алгоритма Square, который был разработан в 1996 году Винсентом Риджменом (Vincent Rijmen) и Джоан Деймен (Joan Daemen) — будущими авторами алгоритма Rijndael, ставшего новым стандартом шифрования США AES после победы на открытом конкурсе. Алгоритм Rijndael также имеет Square-подобную структуру; также в качестве примера можно привести алгоритмы Shark (более ранняя разработка Риджмена и Деймен) и Crypton. Недостатком алгоритмов со структурой «квадрат» является их недостаточная изученность, что не помешало алгоритму Rijndael стать новым стандартом США.
   

   Рис. 5. Алгоритм Rijndael.

   На рис. 5 приведен пример операции над блоком данных, выполняемой алгоритмом Rijndael.

5. Алгоритмы с нестандартной структурой, то есть те алгоритмы, которые невозможно причислить ни к одному из перечисленных типов. Ясно, что изобретательность может быть безгранична, поэтому классифицировать все возможные варианты алгоритмов шифрования представляется сложным. В качестве примера алгоритма с нестандартной структурой можно привести уникальный по своей структуре алгоритм FROG, в каждом раунде которого по достаточно сложным правилам выполняется модификация двух байт шифруемых данных (см. рис. 6).
   

   Рис. 6. Модификация двух байт шифруемых данных.

   Строгие границы между описанными выше структурами не определены, поэтому достаточно часто встречаются алгоритмы, причисляемые различными экспертами к разным типам структур. Например, алгоритм CAST-256 относится его автором к SP-сети, а многими экспертами называется расширенной сетью Фейстеля. Другой пример — алгоритм HPC, называемый его автором сетью Фейстеля, но относимый экспертами к алгоритмам с нестандартной структурой.

Элементарные шифры на понятном языке / Habr

Привет, Хабр!

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

Прежде всего, разберемся в терминологии.

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

Исходное сообщение – это, собственно, то, что мы хотим зашифровать. Классический пример — текст.

Шифрованное сообщение – это сообщение, прошедшее процесс шифрования.

Шифр — это сам алгоритм, по которому мы преобразовываем сообщение.

Ключ — это компонент, на основе которого можно произвести шифрование или дешифрование.

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

Теперь, когда мы говорим на более-менее одном языке, разберем простые шифры.

Самый-самый простой шифр. Его суть – переворот алфавита с ног на голову.

Например, есть у нас алфавит, который полностью соответствует обычной латинице.

a b c d e f g h i j k l m n o p q r s t u v w x y z

Для реализации шифра Атбаша просто инвертируем его. «А» станет «Z», «B» превратится в «Y» и наоборот. На выходе получим такую картину:

И теперь пишем нужное сообшение на исходном алфавите и алфавите шифра

Исходное сообщение: I love habr
Зашифрованное: r olev szyi

Тут добавляется еще один параметр — примитивный ключ в виде числа от 1 до 25 (для латиницы). На практике, ключ будет от 4 до 10.

Опять же, для наглядности, возьмем латиницу

a b c d e f g h i j k l m n o p q r s t u v w x y z

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

Например, ключ у нас будет 4 и смещение вправо.

Исходный алфавит: a b c d e f g h i j k l m n o p q r s t u v w x y z
Зашифрованный: w x y z a b c d e f g h i j k l m n o p q r s t u v

Пробуем написать сообщение:

hello world

Шифруем его и получаем следующий несвязный текст:

dahhk sknhz

• Шифр Вернама (XOR-шифр)

Простейший шифр на основе бинарной логики, который обладает абсолютной криптографической стойкостью. Без знания ключа, расшифровать его невозможно (доказано Клодом Шенноном).

Исходный алфавит — все та же латиница.

Сообщение разбиваем на отдельные символы и каждый символ представляем в бинарном виде.
Классики криптографии предлагают пятизначный код бодо для каждой буквы. Мы же попробуем изменить этот шифр для кодирования в 8 бит/символ на примере ASCII-таблицы. Каждую букву представим в виде бинарного кода.

Теперь вспомним курс электроники и элемент «Исключающее ИЛИ», также известный как XOR.

XOR принимает сигналы (0 или 1 каждый), проводит над ними логическую операцию и выдает один сигнал, исходя из входных значений.

Если все сигналы равны между собой (0-0 или 1-1 или 0-0-0 и т.д.), то на выходе получаем 0.
Если сигналы не равны (0-1 или 1-0 или 1-0-0 и т.д.), то на выходе получаем 1.

Теперь для шифровки сообщения, введем сам текст для шифровки и ключ такой же длины. Переведем каждую букву в ее бинарный код и выполним формулу сообщение XOR ключ

Например:

сообщение: LONDON
ключ: SYSTEM

Переведем их в бинарный код и выполним XOR:

01001100 01001111 01001110 01000100 01001111 01001110
01010011 01011001 01010011 01010100 01000101 01001101
_______________________________________________________
00011111 00010110 00011101 00010000 00001010 00000011

В данном конкретном примере на месте результирующих символов мы увидим только пустое место, ведь все символы попали в первые 32 служебных символа. Однако, если перевести полученный результат в числа, то получим следующую картину:

31 22 29 16 10 3. 

С виду — совершенно несвязный набор чисел, но мы-то знаем.

• Шифр кодового слова

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

Например, возьмем для разнообразия, кириллический алфавит.

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

Придумаем кодовое слово. Например, «Лукоморье». Выдернем из него все повторяющиеся символы. На выходе получаем слово «Лукомрье».

Теперь вписываем данное слово в начале алфавита, а остальные символы оставляем без изменений.

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

И теперь запишем любое сообщение и зашифруем его.

"Златая цепь на дубе том"

Получим в итоге следующий нечитаемый бред:

"Адлпля хриы жл мсур пиё"

• Шифр Плейфера

Классический шифр Плейфера предполагает в основе матрицу 5х5, заполненную символами латинского алфавита (i и j пишутся в одну клетку), кодовое слово и дальнейшую манипуляцию над ними.

Пусть кодовое слово у нас будет «HELLO».

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

Теперь возьмем любое сообщение. Например, «I LOVE HABR AND GITHUB».

Разобьем его на биграммы, т.е. на пары символов, не учитывая пробелы.

IL OV EH AB RA ND GI TH UB.

Если бы сообщение было из нечетного количества символов, или в биграмме были бы два одинаковых символа (LL, например), то на место недостающего или повторившегося символа ставится символ X.

Шифрование выполняется по нескольким несложным правилам:

1) Если символы биграммы находятся в матрице на одной строке — смещаем их вправо на одну позицию. Если символ был крайним в ряду — он становится первым.

Например, EH становится LE.

2) Если символы биграммы находятся в одном столбце, то они смещаются на одну позицию вниз. Если символ находился в самом низу столбца, то он принимает значение самого верхнего.

Например, если бы у нас была биграмма LX, то она стала бы DL.

3) Если символы не находятся ни на одной строке, ни на одном столбце, то строим прямоугольник, где наши символы — края диагонали. И меняем углы местами.

Например, биграмма RA.

По этим правилам, шифруем все сообщение.

IL OV EH AB RA ND GI TH UB.
KO HY LE HG EU MF BP QO QG

Если убрать пробелы, то получим следующее зашифрованное сообщение:

KOHYLEHGEUMFBPQOQG

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

Спасибо за внимание.

Статья: Что такое шифрование и зачем нужно шифрование в интернете?

Зачем нужно шифрование?

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

Что же такое шифрование?

Чтобы передать информацию (записку) по каналу, которому ты не доверяешь (через Лёшу), люди придумали шифрование. Шифровать можно по-разному. Например, вы с Сашей договорились, что вы будете в записке заменять каждую букву А на Б, Б на В, В на Г и так далее, и «Настя позвала меня на др!» превратится в «Обтуа рпигбмб нёоа об ес!».  Леша точно ничего не поймет, а Саше нужно просто взять эту белиберду и сделать все наоборот – А заменить на Я, Б – на А.

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

Но замок можно взломать!

Правильно. Тот алгоритм шифрования, о котором мы рассказали (кстати, он называется шифром Цезаря), очень слабый, и если Леша захочет, он сможет его взломать. В современном мире для шифрования используются гораздо более стойкие алгоритмы. Когда говорят, что алгоритм стойкий, имеют в виду, что взломать его можно, но для этого компьютеру, например, потребуется миллион лет. Круто, правда?

И причем здесь интернет?

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

Как понять, защищен ли я?

Давай рассмотрим для примера Wi-Fi. Если ты можешь присоединиться к сети без пароля (открытый Wi-Fi), то Леша, если он достаточно умен, сможет читать все пакеты (кусочки информации), которыми ты обмениваешься с Сашей. Это все равно, что просто передавать записку – тебе нужно ее дополнительно зашифровать.

Если пароль нужен, то это сеть с шифрованием. Легко ли ее взломать? Открой настройки интернета и посмотри, какой применяется протокол. Если используется WPA2 (достаточно надежный современный протокол), а пароль к сети сложный – можно быть относительно спокойным. Если же, например, используется WEP или WPA-TKIP – устаревшие протоколы, давно признанные ненадежными, – то такую сеть легко взломать, и доверять ей не стоит.

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

Очень нужен интернет, а есть только открытая Wi-Fi сеть. Что делать?

Если ты хочешь просто почитать новости или посмотреть мемы, наверное, ничего страшного не случится. Но если ты передаешь важные данные – нужна дополнительная защита. Ее можно получить, например, установив приложение для VPN – оно дополнительно шифрует все, что ты отправляешь и принимаешь по сети и отправляет на VPN-сервер за пределами Wi-Fi-сети, который расшифровывает данные и переправляет дальше. Кроме того, VPN скрывает от сайтов в интернете, где ты находишься – сайтам кажется, что ты находишься там, где расположен VPN-сервер, который может быть, например, в Австралии или Гонконге.

Когда я сижу в интернете, у меня в браузере рядом с сайтом зеленый замок. Что это значит?

Это значит, что обмен информацией между тобой и сайтом дополнительно зашифрован с помощью протокола SSL/TLS, а какая-то авторитетная организация (называемая центром сертификации) подтверждает, что этот сайт – тот, за кого он себя выдает. Ссылка на сайты, которые используют дополнительное шифрование, начинается с https://, а не http://. Если тебе нужно ввести на сайте какие-то важные данные (фамилия/имя/дата рождения, номер паспорта, платежные данные), а он не использует HTTPS – лучше от использования этого сайта отказаться.

Обрати внимание на сайты с красным замком (обычно браузер на них ругается вот так). Это может означать, что сайт неправильно настроил HTTPS, а может, что кто-то пытается перехватить и украсть твои данные. Такими сайтами пользоваться нельзя!

Значит, сайты с зеленым замком безопасны?

Совсем нет. Это значит, что они те, кем они представились центру сертификации, а передача данных с твоего телефона или компьютера на них защищена. Представим, что есть хакерский сайт instogram.com (обрати внимание на опечатку!), который крадет пароли от настоящего инстаграма, если тебе не посчастливилось попробовать на нем залогиниться. У него вполне может быть зеленый замок – значит, какой-то другой злоумышленник не сможет перехватить информацию, которую ты там ввел, а центр сертификации подтверждает, что это и правда поддельный instogram. Вне зависимости от шифрования не вводи данные на сайтах и в приложениях, которым не доверяешь!

Доверие – это важно?

Да. Представь, что ты делишься с Сашей ключом шифрования и передаешь ей записку, а она оказывается ее сестрой-близнецом, которая об этой записке не должна была узнать. Ты должен доверять человеку, которому отправляешь записку. То же касается, например, Wi-Fi-сетей – даже если она использует шифрование, данные шифруются только между твоим устройством и роутером. Если у тебя нет оснований доверять сети (на самом деле, это касается любого публичного Wi-Fi), нужно быть осторожным: вдруг это злой роутер, который расшифровывает и сохраняет все, что ты передаешь по сети? Тогда шифрование самой Wi-Fi сети не поможет – тебе нужна дополнительная защита, например, VPN-приложение. Но и VPN должен быть такой, которому ты доверяешь, ведь он получает контроль над твоим трафиком. Так что скачивать первое попавшееся приложение из Google Play не стоит. У «Лаборатории Касперского» есть свой VPN с бесплатным трафиком – вполне подойдет, если ты нечасто передаешь важные вещи по открытым сетям.

Подводя итог

1) Шифрование – отличный способ защитить информацию при передаче так, чтобы она не попала не в те руки.

2) Пользуясь Wi-Fi, следует избегать открытых сетей. А на домашнем роутере настрой WPA2 и установи сильный пароль.

3) В публичных сетях используй VPN.

4) Не оставляй важные данные на сайтах, которые не используют HTTPS или используют его неправильно.

5) Использование сайтом HTTPS (зеленый замок) – не показатель, что сайт безопасен. Использование HTTPS значит только то, что сайт использует шифрование.