Системы шифрования. Криптография. Общие понятия.

Системы шифрования. Криптография. Общие понятия.Введение В последнее время все больше внимания уделяют обеспечению безопасности коммуникаций, хранения данных, конфиденциальности доступа к данным и подобным аспектам. Предлагаются многочисленные решения, как на аппаратном уровне, так и на уровне программного обеспечения. Отметим, что использование шифрования данных отнюдь не гарантирует конфиденциальности этих данных. Простейшим примером является перехват (зашифрованного!) сообщения, определение блока/блоков, соответствующих времени отсылки, и использование затем этого же зашифрованного сообщения, но с другим временем отсылки. Этот прием может быть использован для фальсификации сообщений между банками, например для перевода сумм денег на счет злоумышленника. Для решения такого рода проблем можно привести несколько вариантов: настройка безопасности сети пересылки данных, например, брандмауэры (firewalls) и партнерские сети (VPN — Virtual Private Networks); использование специальных протоколов для передачи данных на уровне программного обеспечения. Криптография лишь предоставляет алгоритмы и некоторые приемы для аутентификации клиента и шифрования информации. В то время как обеспечение безопасности в целом, как правило, связано с гораздо более общими проблемами. Например, по статистике в тысячи раз чаще происходит так называемый «отказ системы в обслуживании» (DoS attacks — Denial of Service attacks), чем реальный взлом системы и считывание несанкционированных данных. Здесь мы уделим основное внимание вопросу конфиденциальности удаленного доступа к данным и пересылке данных. Поскольку различные криптографические алгоритмы являются основой для построения систем, то сначала мы приведем описание наиболее интересных и показательных из них. Мы начнем с описания алгоритмов симметричного шифрования (AES, IDEA, RC4, RC5, Blowfish, Twofish) и остановимся, для примера, на алгоритме DES, затем расскажем о различных алгоритмах шифрования с открытым ключом (RSA, El Gamal, Merkle-Helmann). Далее перейдем к алгоритмам цифровой подписи (DSS), цифрового конверта и дайджест-алгоритмам (MD5, SHA-1), использующимся на практике. Терминология Все криптографические системы, вне зависимости от их сложности, имеют следующие составные части: — (исходное) сообщение — то, что мы хотим защитить от несанкционированного чтения/использования. В качестве сообщения может выступать как произвольный текст, так и программное обеспечение, различная медиаинформация; — зашифрованное сообщение — это сообщение, измененное с целью скрыть его исходный смысл и сделать его «нечитаемым». Процесс преобразования сообщения в зашифрованное сообщение называется шифрованием, обратный процесс — дешифрованием; — криптографический алгоритм — некий математический алгоритм, используемый для шифрования исходного сообщения и наоборот (дешифрования этого сообщения); — ключ — информация, используемая криптографическим алгоритмом для шифрования и/или дешифрования. Эта информация, как правило, является секретной и априори считается, что лишь человек, обладающий ей, может при декодировании получить исходное сообщение. Зашифрованное сообщение может быть «взломано», то есть прочитано без знания ключа, несколькими способами. Один из них — криптоанализ, основная идея которого состоит в анализе зашифрованного сообщения и поиске в нем различных особенностей, например, повторяющихся частей (шаблонов). Другим вариантом является подбор ключа для дешифрования до тех пор, пока в результате дешифрования не получится «читаемое» сообщение. Симметричное шифрование Наиболее известными и распространенными криптографическими алгоритмами являются так называемые симметричные алгоритмы, в которых один и тот же ключ используется для шифрования и дешифрования сообщений (и именно поэтому они так называются [3]). Главным недостатком систем с такими алгоритмами является тот факт, что обе стороны, обменивающиеся информацией, должны договориться об использовании одного и того же ключа, а также хранить его в тайне от остальных. Дело в том, что, во-первых, при обмене информацией с множеством сторон необходимо запоминать, где какой ключ используется, а, во-вторых, ключ не может быть передан через обычные открытые средства связи из-за опасности его перехвата. Среди наиболее известных и распространенных алгоритмов можно выделить DES (Data Encryption Standard) (1), AES (Advanced Encryption Standard) (2), RC2, RC4, RC5 (3), IDEA (International Data Encryption Algorithm) (4)и Blowfish (5). Многие из использующихся алгоритмов опираются на два очень простых приема: подстановка и перестановка. Подстановочные шифры разгадываются легко при накоплении достаточной статистики появления отдельных букв. Так, очень эффективный и вычислительно простой метод кодировки получается при побитовом сложении кодируемого текста с псевдослучайной последовательностью битов. Пусть имеется последовательность битов ai, полученная в последовательности независимых случайных испытаний, где 0 и 1 появляются равновероятно, или любой другой последовательности с похожими свойствами. Пусть bi — последовательность битов, составляющая передаваемый текст. Образуем последовательность сi, где сi = ai XOR bi, которая и посылается адресату. Если последовательность ai ему известна, то, применяя ту же операцию, он легко получит исходный текст (6). Другим семейством простейших криптографических алгоритмов являются перестановочные шифры. Основная идея заключается в изменении порядка чтения символов передаваемого текста. Так, типичный пример — «шифры–решетки», очень популярные в письменной переписке в Средневековье. Суть их заключается в том, что обе стороны обладают своеобразным листом-решеткой, в котором сделаны прорези достаточных размеров для написания одной или нескольких букв. Для создания зашифрованного сообщения первая сторона накладывает решетку на лист бумаги и пишет нужный текст в прорезях. Когда не остается свободного места, решетка сдвигается, тем самым закрывая уже написанный текст и открывая новое пространство. Далее, после того как убирают решетку, все освободившееся пространство заполняется произвольными символами. Для прочтения этого сообщения необходимо наложить ту же решетку и точно так же сдвигать ее в нужном направлении. В этом примере ключом являются решетка и направление сдвига решетки. Поэтому, очевидно, данный алгоритм является алгоритмом симметричного шифрования. Описанные выше перестановочные и подстановочные шифры достаточно легко «взломать», то есть подобрать нужный ключ или же применить различные приемы криптоанализа. Однако на их основе можно сформировать достаточно сложные и «стойкие» шифры. Например, алгоритм DES, который оперирует входными данными из блоков по 64 бита. Мы опишем один из шагов алгоритма DES, чтобы проиллюстрировать, что ничего кроме подстановки и перестановки не используется. ПРИМЕР. Один из шагов алгоритма DES: — входной блок данных делится пополам на левую (L’) и правую (R’) части. После этого формируется выходной массив так, что его левая часть (L’’) представлена правой частью (R’) входного, из 32-битного слова R’ с помощью битовых перестановок формируется 48-битовое слово; — производим побитовое сложение (операция XOR) полученного 48-битовое слова с 48 битовым раундовым ключом. Раундовые ключи получаются из исходного ключа путем отбрасывания 8 бит; — результирующее 48-битовое слово разбивается на 8 6-битовых групп, каждая 6-битовая группа, при помощи некоторой операции «свертки» (операции S-box [1]), заменяется на 4-битовую группу. Из полученных 4-битовых групп получается 32-битовое слово; — Полученное слово побитово складывается (XOR-ится) с L’, в результате получается (R’’). Можно убедиться, что проведенные операции могут быть обращены, и расшифровывание осуществляется за число операций, линейно зависящее от размера блока. После нескольких таких «перемешиваний» можно считать, что каждый бит выходного зашифрованного блока зависит от каждого бита исходного сообщения. Шифрование с открытым ключом В 70-х годах прошлого столетия появился новый тип криптографических алгоритмов — алгоритмы шифрования с открытым ключом (или асимметричное шифрование). В таких системах все ключи «живут» парами: один используется для шифрования, другой для дешифрования. И что самое интересное — зашифрованное сообщение не может быть дешифровано без знания второго ключа, даже если знать ключ, который использовался для шифрования. Таким образом, у каждой стороны в криптографической системе с открытым ключом имеется два ключа — открытый или публичный (public), для открытого распространения, и секретный (private) ключ, который знает только его владелец. Для того чтобы A послал зашифрованное сообщение стороне B, необходимо использовать открытый ключ B потому, что лишь B обладает секретным ключом для дешифрования этого сообщения. Одним из наиболее популярных алгоритмов шифрования с открытым ключом является алгоритм RSA, названный по именам его авторов (7). Этот алгоритм основан на некоторых результатах теории чисел, а именно на факте трудоемкости разложения больших чисел на простые сомножители. Мы не будем останавливаться здесь на деталях, поскольку этот алгоритм достаточно популярен, и его описание можно найти в многочисленных источниках. В отличие от множества алгоритмов симметричного шифрования существует лишь несколько алгоритмов шифрования с открытым ключом: — RSA. Этот алгоритм был запатентован компанией RSA Security Inc. и использовал ключи с длинами от 512 бит, срок патента истек в 2000 году, так что можно ожидать большое распространение этого алгоритма в различных программных продуктах; — El Gamal также получил свое название по имени своего автора Тахира Эль-Гамаля (Taher ElGamal) и использует ключи с длинами от 512 бит до 1024 бит. Этот алгоритм, в отличие от RSA, не был запатентован, но его использование было ограничено в силу различных причин законодательного порядка (; — Алгоритм Меркл-Хелманна — очень красивый, с математической точки зрения, алгоритм. Основная идея состоит в том, что формируются две задачи о рюкзаке (или, иногда принято говорить, ранце) — общая, которая выступает в качестве открытого ключа, и так называемая «простая» задача о рюкзаке, которую может получить лишь обладатель секретного ключа. Таким образом, для того чтобы дешифровать сообщение без знания секретного ключа, необходимо решить общую задачу о рюкзаке, которая является NP-сложной (9). Обладатель секретного ключа решает задачу о «простом» рюкзаке за линейное время. К сожалению, выяснилось, что класс задач о рюкзаке, который используется в качестве открытого ключа, имеет некоторые специфичные особенности, которые значительно снижают сложность решения этой задачи. Цифровая подпись Описанный подход в криптографических системах с открытым ключом можно «обратить» и получить не менее удобную и полезную систему аутентификации пользователя, называемую цифровой подписью. Механизм очень прост — необходимо придумать произвольную фразу, например, «Меня зовут Сергей Кузнецов», и затем зашифровать ее с использованием секретного ключа. Полученное зашифрованное сообщение является цифровой подписью и, как правило, отсылается вместе с исходным сообщением. Каждый может удостовериться, что получил сообщение от того, чья цифровая подпись прикреплена, простым дешифрованием с использованием публичного ключа. На практике протоколы цифровой подписи, безусловно, сложнее, и они опираются на еще один тип криптографических алгоритмов — дайджесты (digest), о которых речь пойдет далее. Цифровой конверт Основной недостаток систем шифрования с открытым ключом — их низкая скорость. Самая «быстрая» реализация алгоритма RSA в тысячи раз медленнее любого стандартного алгоритма симметричного шифрования. Поэтому для шифрования длинных сообщений или же в системах реального времени предпочитают использовать симметричное шифрование. На практике используются оба типа алгоритмов, скомбинированные таким образом, чтобы скрыть их недостатки. Такая схема называется цифровым конвертом (Digital Envelope). Основная идея состоит в следующем: — сначала генерируется ключ, который будет использован для симметричного шифрования. Такой ключ называется ключом сессии, или сессионным ключом, поскольку он создается для каждой сессии пересылки сообщений заново и не может быть использован после нее; — исходное сообщение шифруется с использованием ключа сессии; — ключ сессии шифруется с помощью публичного ключа получателя, полученное сообщение и называется цифровым конвертом; — зашифрованное сообщение и цифровой конверт посылаются по нужному адресу. Получатель должен сначала дешифровать цифровой конверт с помощью своего секретного ключа. И уже затем с помощью ключа сессии он дешифрует само сообщение и все последующие сообщения в рамках этой сессии. Дайджесты С помощью различных криптографических алгоритмов можно пересылать секретную информацию по открытым каналам связи, но как можно быть уверенным, что сообщение не изменится в процессе передачи? Как можно понять, было ли сообщение модифицировано в процессе пересылки или нет, поскольку само зашифрованное сообщение «не читаемо»? На все эти вопросы помогут ответить так называемые цифровые дайджесты. Алгоритмы-дайджесты в некотором роде похожи на алгоритмы шифрования тем, что тоже получают на входе обыкновенное «читаемое» сообщение и на выходе дают некоторый «нечитаемый» набор байтов. Однако эти дайджесты необратимы, то есть процедуру их дешифрования произвести нельзя. На выходе работы алгоритмов-дайджестов получают короткие (фиксированной длины) дайджест-сообщения (также называемые хэшами (hash)), которые, как правило, намного короче исходного сообщения. Дайджест-сообщения выступают в роли своеобразных «контрольных сумм» сообщения, поскольку если в исходном сообщении изменить хотя бы один бит, то дайджест измененной информации будет кардинально отличаться от исходного. Именно поэтому эти алгоритмы используются при передаче информации в качестве индикатора правильности принятой информации. Например, в стандарте цифровой подписи DSS (Digital Signature Standard) используется следующий механизм: — получают дайджест исходного сообщения; — зашифровывают дайджест с помощью секретного ключа отправителя («подписывают дайджест»); — посылают «подписанный дайджест» и исходное сообщение получателю. Таким образом, достигаются две цели: во-первых, получатель может удостовериться, что полученное сообщение не претерпело изменений в процессе передачи. Для этого нужно дешифровать «подписанный дайджест» с помощью публичного ключа отправителя, получить дайджест полученного сообщения и сравнить эти два дайджеста. Совпадение означает, что исходное сообщение не изменено и получено именно от того лица, чей публичный ключ использовался для дешифрования, тем самым подтверждая подлинность отправителя информации (10). Наиболее известными дайджест-алгоритмами являются MD5, который генерирует 128-битный дайджест, и SHA (Secure Hash Algorithm) для генерации 160-битного дайджеста (http://csrc.nist.gov/encryption/tkhash.html). Почему важна длина ключей По ходу этого изложения мы часто упоминали, что важна длина ключа используемого при шифровании или дешифровании. Действительно, очевиден тот факт, что если в криптографической системе будет «легко» угадать ключ (как в симметрическом шифровании, так и в системах с открытым ключом), то она не может быть использована для передачи действительно конфиденциальной информации. Приведем немного статистики на примере алгоритмов DES и AES. Как раз здесь будет видно, почему был осуществлен переход от «устаревшего» алгоритма к новому. Существуют AES-ключи трех длин: 128 бит, 192 бита и 256 бит. Это, в свою очередь, означает, что при полном переборе нужно будет попробовать 3,4X1038 128-битных ключей, 6,2X1057 192-битных и 1,1X1077 256-битных ключей. Для сравнения, DES-ключи имеют длину 56 бит, а значит, возможных ключей существует в 1021 раз меньше чем 128-битных AES-ключей. Что же значат все эти «страшные» цифры для нормального человека? Предположим, есть устройство способное «взломать» алгоритм DES за 1 секунду (то есть перебрать 255 возможных ключей в секунду) (11). Тогда время, необходимое для «взлома» 128-битного AES-ключа, будет приблизительно равно 149 триллионам лет работы данной машины. В следующей статье будет рассмотрен вопрос о применении различных криптографических систем на практике. Основное внимание мы уделим протоколам передачи конфиденциальной информации в различных ситуациях — поскольку не существует универсальных протоколов «на все случаи жизни», то для каждой отдельной модели разрабатывается свой подход. (1) Был разработан фирмой IBM и утвержден правительством США в 1977 как официальный стандарт. (2) Стандарт, принятый совсем недавно для официальной замены DES. Оригинальное название этого алгоритма — Rindael, по имени его автора. Дело в том, что мощность современных компьютеров растет, и повышается вероятность «взлома». Немного статистики о сравнении этих двух алгоритмов можно найти ниже. Подробнее можно узнать на интернет-сайте http://csrc.nist.gov/encryption/aes/. (3) Блочные шифры с ключом переменной длины, созданные Роном Ривестом для RSA Data Security Inc. (http://www.rsasecurity.com/) (4) Этот алгоритм был разработан для простого воплощения как программно, так и аппаратно; безопасность IDEA основывается на использовании трех несовместимых типов арифметических операций над 16-битными словами. IDEA очень распространен в Европе и используется в популярной программе шифрования электронных писем PGP (Pretty Good Privacy). (5) Алгоритм Blowfish был создан Брюсом Шнаейром (Bruce Schneier), автором известной книги «Прикладная криптография» в 1993 году, и существенно быстрее DES (http://www.counterpane.com/blowfish.html). Модифицированная версия этого алгоритма Twofish (http://www.counterpane.com/twofish.html) принимала участие в конкурсе на звание AES, но, как уже было сказано, проиграла алгоритму Rijndael. (6) Также очень интересным примером является так называемый код Морзе. Суть в том, что каждую букву текста представляют в виде азбуки Морзе. Далее, учитывая, что в азбуке Морзе используются лишь три символа, то вся полученная последовательность делится на группы по три и далее, каждый полученный трехсимвольный блок интерпретируется как отдельный символ в зашифрованном тексте. Этот пример хорошо подходит для латинского алфавита, поскольку там ровно 26 букв, а комбинаций из трех символов всего 27 [1]. (7) Ron L. Rivest, Adi Shamir, Leonard Adleman. ( Дело в том, что авторы другого алгоритма анонимного шифрования Диффи-Хеллмана, подали в суд на Эль-Гамаля за нарушение прав патента. Однако срок патента алгоритма Диффи-Хеллмана истек в апреле 1997 года, и конфликт сам собой затих. (9) NP–сложные задачи (10) Существуют различные более сложные методы использования дайджестов, например, в протоколе SSL (Secure Socket Layer) ключевым моментом является процедура аутентификации сообщений MAC (Message Authenticity Check), которая вычисляет данному сообщению M удостоверяющий код MAC(M) по формуле: MAC(M) = digest(secret + digest(key + M)), где digest — функция-дайджест, key — ключ, используемый для симметричного шифрования. (11) На самом деле, лишь в конце 90–х годов появились специальные компьютеры для подбора ключей DES. На этих машинах время подбора измеряется несколькими часами. copyright - Computerra region (Сергей Кузнецов)