Амелин Р.В.

Информационная безопасность

электронный учебник

Модуль 1

Модуль 2

Модуль 3

Модуль 4

Глава 4. Введение в криптографию. Симметричное шифрование

4.1. Основные понятия криптографии

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

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

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

Криптографическое преобразование информации — преобразование информации с использованием одного из криптографических алгоритмов.

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

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

4.2. Шифрование

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

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

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

1. Симметричное (традиционнное шифрование).
2. Шифрование с открытым ключом.

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

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

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

M' = E(M, K)

M = D(M', K),

где Е — функция шифрования (encrypt), а D — функция дешифрования (decrypt), обе используют ключ K в качестве одного из параметров.

Исторически симметричное шифрование появилось первым. Более того, до середины XX века это была единственная разновидность шифрования. Симметричные алгоритмы широко применяются и в настоящее время.

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

Все алгоритмы симметричного шифрования можно разделить на три класса:

1. Подстановочные алгоритмы.
2. Перестановочные алгоритмы.
3. Алгоритмы, использующие и подстановку и перестановку (к этому классу относятся практически все современные алгоритмы, разработанные для защиты информации в ЭВМ).

4.4. Подстановочные алгоритмы

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

Рассмотрим конкретные примеры.

1. Шифр Цезаря

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

Рис. 1. Пример шифрования по Цезарю

Особенностью шифра Цезаря, как несложно заметить, является отсутствие ключа. Часло 3 в данном случае ключом не является, поскольку не выбирается отправителем сообщения, а используется для сдвига по алфавиту постоянно. Во времена Юлия Цезаря это не было слабостью шифра (поскольку сама идея сокрытия информации путем преобразования текста была незнакомой его противникам), но в настоящее время первым правилом криптографии является следующее допущение:

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

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

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

Так, например, в 2007 году в результате утечки информации оказались обнародованы алгоритмы, используемые в популярной технологии KeeLoq — системы охраны, применяемой в противоугонных средствах автомобильной защиты. После исследования, проведенного независимыми экспертами, оказалось, что при сравнительно скромных затратах времени и вычислительных ресурсов (два дня работы компьютеров общей ценой около 10 000 евро) злоумышленники могут вскрыть сначала секретный ключ какой-либо конкретной машины, а на его основе — но теперь уже за секунды — цифровой ключ любого другого автомобиля этой же компании. Двумя годами раньше аналогичный скандал возник с системой электронного голосования, использовавшейся в США, исходные коды которой оказались случайно выложенными в общий доступ на сайте компании. Исследование показало уязвимость системы к целому спектру популярных атак

Рассмотрим вариацию шифра Цезаря, при которой число 3 является не жестко заданным, а выбирается произвольно, согласно договоренности между отправителем и получателем сообщения. В этом случае шифр Цезаря становится полноценным шифром с ключом K (потенциально неизвестном противнику).

Однако легко заметить, что в качестве ключа могут быть выбраны лишь числа в диапазоне от 1 до 32 (для русского алфавита). Действительно, шифр является циклическим: Я + 1 = А, но и Я + 34 = А. То есть, число 34, выбранное в качестве ключа, будет эквивалентно ключу 1, ключ 35 — ключу 2 и т.д. Противнику ничего не стоит перебрать все 32 возможных ключа и обнаружить нужный. При этом необязательно даже расшифровывать весь текст сообщения: после опробования ключа на первом же десятке символов станет понятно, получаем ли мы бессмысленный набор символов (следовательно, ключ не подходит), или что-то, похожее на настоящий текст.

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

2. Моноалфавитный шифр (шифр простой замены)

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

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

Рис. 2. Пример шифрования текста шифром простой замены

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

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

Все естественные языки имеют характерное частотное распределение символов. Например, буква «О» - встречается в русском языке чаще других, а буква «Ф» — самая редкая (см. табл. 1).

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

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

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

3. Шифр Гронсфельда

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

Рис. 3. Пример шифрования текста шифром Гронсфельда

Данный шифр (описанный Жюль Верном в романе «Жангада») относится к семейству многоалфавитных шифров (или шифров сложной замены). В многоалфавитном шифре 1-й символ открытого текста шифруется с помощью моноалфавитного шифра, ключом к которому является перестановка K₁, 2-й символ — ключом K₂ и т.д., n-й символ — ключом K_n, а n+1-й — снова ключом K₁, где n — количество используемых алфивитов (или шифров простой замены). В приведенном примере n=3.

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

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

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

Эта проблема исчезает в модификации шифра Гронфельда, где в качестве ключа выступает не цифровая, а буквенная последовательность. Порядковый номер буквы открытого текста складывается с записанной под ней буквой ключа и получается порядковый номер буквы зашифрованного текста (который берется по модулю мощности алфавита, т.е. Г + Э = 4 + 31 = 35; 35 mod 33 = 2 = Б; Г + Э = Б).

Рис. 4. Модифицированный шифр Гронсфельда

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

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

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

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

4. Многобуквенные шифры

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

Шифр предназначен для английского алфавита. Ключом является кодовая фраза, которая записывается в первые ячейки квадратной решетки 5x5 (повторяющиеся буквы пропускаются). Затем квадрат в алфавитном порядке заполняется буквами, которые не вошли в кодовую фразу. I и J считаются одной буквой.

Заполним решетку с ключевым словом MONARCHY.

Рис. 5. Кодовая решетка для шифра Плейфейера

Исходный текст разбивается на биграммы. При этом если две одинаковые буквы открытого текста при разбиении образуют одну биграмму, между ними вставляется символ X. Т.е. вместо BALLOON шифруем BALXLOON.

Если буквы биграммы стоят в одной строке (столбце), они заменяются их правыми (нижними) соседями с учетом циклического сдвига. В нашем примере OR шифруется как NM, а OP — как HV.

Если буквы биграммы оказываются в разных строках и столбцах, то каждая из пары букв заменяется буквой, находящейся на пересечении ее строки и столбца, в котором находится вторая буква. Например, BE шифруется как CI, а OS — как AP.

Слово INFORMATION будет зашифровано как GAPHMORSFAAW.

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

Другой интересный пример многобуквенного шифра — шифр Хилла. Он представляет собой систему из m линейных уравнений с m коэффициентами. Шифр заменяет каждые m букв открытого текста на m букв зашифрованного текста. Например, при m = 3 имеем систему уравнений (где n — мощность алфавита):

c₁ = (k₁₁p₁ + k₁₂p₂ + k₁₃p₃) mod n

c₂ = (k₂₁p₁ + k₂₂p₂ + k₂₃p₃) mod n

c₃ = (k₃₁p₁ + k₃₂p₂ + k₃₃p₃) mod n

Ключом шифрования будет являться матрица коэффициентов K, а само шифрование можно представить как произведение вектора, составленного из порядковых номеров букв открытого текста (первая буква имеет номер 0) на ключевую матрицу K:

Для расшифровки зашифрованный текст необходимо умножить на матрицу, обратную к K (K^-1).

Шифр Хилла также хорошо скрывает частоту символов исходного сообщения, но уязвим к криптоанализу с известным открытым текстом. Поскольку система линейная, противнику понадобится n² пар «открытый текст — зашифрованный текст», чтобы вычислить ключевую матрицу. Однако наиболее эффективный метод криптоанализа для данного шифра — криптоанализ с избранным открытым текстом, когда противник имеет возможность получать зашифрованные образцы специально подобранного им открытого текста.

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

Посмотрите, что будет представлять из себя зашифрованный текст, если зашифровать последовательность "БАА" ( p1 = 1, p2 = 0, p3 = 0).

5. Одноразовый блокнот

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

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

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

4.5. Перестановочные алгоритмы

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

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

Рис. 6. Простейший перестановочный шифр.

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

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

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

Рис. 7. Пример шифрования с помощью решетки Флейберга

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

4.6. Современные алгоритмы симметричного шифрования

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

Шифр Файстеля создавался как пример практической реализации идеи Клода Шеннона: надежный алгоритм шифрования должен удовлетворять двум свойствам: диффузии и коффузии.

Диффузия — каждый бит открытого текста должен влиять на каждый бит зашифрованного текста. Суть диффузии заключается в рассеянии статистических характеристик открытого текста внутри шифрованного текста.

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

Рассмотрим структуру шифра Файстеля.

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

На вход алгоритма шифрования подается блок открытого текста, имеющий четную длину 2l и ключ K. Блок разделяется на две равные части — правую R₀ и левую L₀. Далее эти части проходят m раундов обработки, после чего снова объединяются в зашифрованный текст.

Каждый i-й раунд состоит в генерации подключа K_i (на основе общего ключа K) и применении к блоку R_i некоторого зависящего от ключа преобразования F. Результат складывается с блоком L_i с помощью операции XOR (исключающее или) и получается блок R_i+1. Блок R_i без изменений берется в качестве блока L_i+1.

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

Рис. 8. Схема i-го раунда шифрования шифра Файстеля

Различные алгоритмы, использующие структуру шифра Файстеля могут отличться следующими параметрами [2]:

• Длина ключа. Чем длиннее ключ, предусмотренный алгоритмом, тем сложнее осуществить перебор. Сейчас надежной считается длина ключа не менее 1024 бита.
• Размер блока. Чем выше размер блока, тем больше надежность шифра, но скорость операций шифрования/дешифрования при этом снижается.
• Число раундов обработки. С каждым новым раундом обработки надежность шифра повышается.
• Функция раунда F — чем она сложнее, тем труднее криптоанализ шифра.
• Алгоритм вычисления промежуточных ключей K_i.

Алгоритм DES

Долгое время самым популярным алгоритмом симметричного шифрования являлся DES (Data Encrypting Standart), принятый в 1977 году. Этот алгоритм базируется на структуре шифра Файстеля с размером блока 64 бита и 56-битным ключом.

Функция раунда F использует набор из восьми так называемых S-матриц. Каждая матрица состоит из 4 строк, причем каждая строка представляет собой перестановку чисел от 0 до 15 (соответственно, 16 столбцов). Матрицы жестко заданы7. Каждая матрица получает на вход шесть бит и выдает четырехбитовый результат. Первый и последний бит входного значения задают строку матрицы, а четыре остальных — столбец. Двоично представление числа, находящегося на их пересечении, и будет результатом преобразования. Собственно же преобразование F заключается в следующем:

1. 32-битовый блок Ri расширяется до 48 битов с помощью специальной таблицы путем дублирования некоторых 16 битов.
2. Полученный результат складывается с 48-битным подключом Ki операцией XOR.
3. Результат сложения разбивается на 8 шестибитовых блоков и каждый из них преобразуется с помощью соответствующей S-матрицы.
4. Получившийся в итоге 32-битный блок подвергается жестко заданной в алгоритме перестановке.

Долгое время DES являлся федеральным стандартом шифрования США. Этот алгоритм показывает хороший лавинный эффект (изменение одного бита открытого текста или ключа приводит к изменению многих битов зашифрованного текста) и успешно противостоял многолетним попыткам взлома. Однако длина ключа в 56 битов при возросшей производительности ЭВМ сделала шифр потенциально уязвимым к перебору ключей, поэтому в 1997 году был объявлен конкурс на новый алгоритм, который должен был стать криптостандартом на ближайшие 10-20 лет.

Алгоритм AES

Победитель конкурса был определен в 2000 году — им стал бельгийский шифр RIJNDAEL, который был переименован в AES (Advanced Encryption Standard). Он является нетрадиционным блочным шифром, поскольку не использует сеть Фейштеля. Каждый блок входных данных представляется в виде двумерного массива байт ( 4х4, 4х6 или 4х8 в зависимости от размера блока, которая может варьироваться). В зависимости от размера блока и длины ключа алгоритм содержит от 10 до 14 раундов, в каждом из которых проводится ряд преобразований — либо над независимыми столбцами, либо над независимыми строками, либо вообще над отдельными байтами в таблице.

Среди других современных алгоритмов симметричного шифрования следует назвать шифры IDEA, Blowfish, RC5, CAST-128.

4.7. Режимы функционирования блочных шифров

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

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

1. Режим электронной шифровальной книги (ECB). Наиболее простой и естественный способ. Текст разбивается на блоки и каждый блок шифруется с одним и тем же ключом. Основной недостаток подхода заключается в том, что одинаковые блоки будут одинаково зашифровано, что снижает защиту в случае больших объемов шифруемой информации.
2. Режим сцепления шифрованных блоков (CBC). Каждый блок открытого текста перед шифрованием объединяется с помощью операции XOR с предыдущим блоком зашифрованного текста. Первый блок объединяется с некоторым заранее заданным инициализационным вектором. В результате одинаковые блоки открытого текста в зашифрованном виде будут различаться.
3. Режим шифрованной обратной связи (CFB). Похож на предыдущий, но основное назначение состоит в том, чтобы превратить блочный шифр (например, DES с длиной блока 64 бита) в потоковый, т.е. шифрующий по одному символу (размером, например, j = 8 бит). Идея заключается в том, что изначально 64-битовый буфер заполняется значением инициализационного вектора (известного отправителю и получателю), которое шифруется ключом K. Из полученного результата выбираются старшие (левые) j бит, которые объединяются с помощью XOR с первым символом открытого текста. Получаем первый зашифрованный символ. Далее содержимое буфера сдвигается на j бит влево, а в самый младшие (правые) j бит записывается зашифрованный символ. Система готова к шифрованию следующего символа.
4. Режим обратной связи по выходу (OFB). Аналогичен предыдущему, но в младшие j бит буфера после сдвига помещается не зашифрованный символ, а j сташих бит результата шифрования (т.е. до их объединения с символом открытого текста). Такой режим более устойчив к помехам (сбой при передаче одного символа зашифрованного текста не будет влиять на результаты дешифрования других символов).

4.8. Скремблеры

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

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

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

Пусть необходимо зашифровать сообщение 00111 скремблером 101 с ключом 011. Вычисляется сумма по модулю 2 первого и третьего бита ключа: 0 1 = 1. Этот бит становится новым первым битом ключа, а последний бит ключа (1) становится битом шифрующей последовательности. Вычисляем первый бит зашифрованного текста: 1 0 = 1. Далее повторям процесс, но уже с ключом 101. Шифрование всего сообщения показано на рисунке.

Рис. 9. Скремблирование последовательности 00111 скремблером 101 с ключом 011

4.9. Основные разновидности криптоанализа симметричных шифров

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

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

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

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

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

Статистический криптоанализ. Основан на подсчете частоты встречаемости отдельных символов (или групп символов) в зашифрованном тексте. Подходит для взлома симметричных подстановочных алгоритмов.

Дифференциальный криптоанализ. Разновидность анализа с избранным открытым текстом. Используется при взломе современных симметричных алгоритмов шифрования, в которых текст последовательно проходит несколько раундов преобразований (в частности, известен алгоритм дифференциального криптоанализа шифра DES). Метод основан на прослеживании изменения схожести между двумя текстами. Выбирается пара незашифрованных текстов с определенным отличием (X), после чего анализируются отличия, получившиеся после шифрования одним раундом алгоритма, и определяются вероятности различных ключей. Если для многих пар входных значений, имеющих одно и то же отличие Х, при использовании одного и того же подключа одинаковыми (Y) оказываются и отличия соответствующих выходных значений, то можно говорить, что Х влечет Y с определенной вероятностью. Эта вероятность и присваивается данному подключу раунда. Затем выбирается подключ с наибольшей вероятностью. Процесс повторяется для всех раундов. Цель — определить таким образом все подключи данного ключа (сам ключ при этом может остаться неизвестным).

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

4.10. Проблемы симметричных алгоритмов

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

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

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

Кроме того, возникает проблема управления большим количеством ключей, поскольку отдельный ключ необходим для каждой пары «отправитель-получатель». Если группа из n человек желает обмениваться конфиденциальными сообщениями, понадобится O(n²) ключей (n-1 ключ каждому). Если же группа будет использовать один общий ключ, то его компрометация (утечка) у одного члена скомпрометирует переписку всей группы.

Эти проблемы и привели к появлению в середине XX века приницпиально нового класса алгоритмов шифрования — асимметричные алгоритмы (алгоритмы с открытым ключом).

назад | оглавление | вперед