| Симметричные шифры. | |
|
|
| |
|
КРИПТОЛОГИЯ И ЕЕ ОСНОВНЫЕ ПОНЯТИЯ
Наука, занимающаяся вопросами безопасной связи (т.е посредством зашифрованных
сообщений называется Криптологией (kryptos - тайный, logos - наука). Она в свою
очередь разделяется на два направления криптографию и криптоанализ.
Криптография - наука о создании безопасных методов связи, о создании стойких (устойчивых к взлому) шифров. Она занимается поиском математических методов преобразования информации.
Криптоанализ - данный раздел посвящен исследованию возможности чтения сообщений без знания ключей, т.е. связана непосредственно со взломом шифров. Люди, занимающиеся криптоанализом и исследованием шифров, называются криптоаналитиками.
Шифр - совокупность обратимых преобразований множества открытых текстов (т.е. исходного сообщения) на множество зашифрованных текстов, проводимых с целью их защиты. Конкретный вид преобразования определяется с помощью ключа шифрования.
Определим еще несколько понятий, которые необходимо усвоить, чтобы чувствовать себя уверенно.
Во-первых, зашифрование - процесс применения шифра к открытому тексту.
Во-вторых, расшифрование - процесс обратного применения шифра к зашифрованному
тексту.
И в третьих, дешифрование - попытка прочесть зашифрованный текст без знания
ключа, т.е. взлом шифротекста или шифра.
Здесь следует подчеркнуть разницу между расшифрованием и дешифрованием. Первое
действие проводится законным пользователем, знающим ключ, а второе - криптоаналитиком
или мощным хакером.
Криптографическая система - семейство преобразований шифра и совокупность ключей
(т.е алгоритм + ключи). Само по себе описание алгоритма не является криптосистемой.
Только дополненное схемами распределения и управления ключами оно становится
системой. Примеры алгоритмов - описания DES, ГОСТ28.147-89. Дополненые алгоритмами
выработки ключей, они превращаются в криптосиситемы. Как правило, описание алгоритма
шифрования уже включает в себя все необходимые части.
Современные криптосистемы классифицируют следующим образом:
Криптосистемы могут обеспечивать не только секретность передаваемых сообщений, но и их аутентичность (подлинность), а также подтверждение подлинности пользователя.
Симметричные криптосистемы (с секретным ключом - secret key systems) - данные криптосистемы построены на основе сохранения в тайне ключа шифрования. Процессы зашифрования и расшифрования используют один и тот же ключ. Секретность ключа является постулатом. Основная проблема при применении симметричных криптосистем для связи заключается в сложности передачи обоим сторонам секретного ключа. Однако данные системы обладают высоким быстродействием. Раскрытие ключа злоумышленником грозит раскрытием только той информации, что была зашифрована на этом ключе. Американский и Российский стандарты шифрования DES и ГОСТ28.147-89, кандидаты на AES - все эти алгоритмы являются представителями симметричных криптосистем.
Асимметричные криптосистемы (системы открытого шифрования - о.ш., с открытым ключом и т.д.- public key systems) - смысл данных криптосистем состоит в том, что для зашифрования и расшифрования используются разные преобразования. Одно из них - зашифрование - является абсолютно открытым для всех. Друго же - расшифрование - остается секретным. Таким образом, любой, кто хочет что-либо зашифровать, пользуется открытым преобразованием. Но расшифровать и прочитать это сможет лишь тот, кто владеет секретным преобразованием. В настоящий момент во многих асимметричных криптосистемах вид преобразования определяется ключом. Т.е у пользователя есть два ключа - секретный и открытый. Открытый ключ публикуется в общедоступном месте, и каждый, кто захочет послать сообщение этому пользователю - зашифровывает текст открытым ключом. Расшифровать сможет только упомянутый пользователь с секретным ключом. Таким образом, пропадает проблема передачи секретного ключа (как у симметричных систем). Однако, несмотря на все свои преимущества, эти криптосистемы достаточно трудоемки и медлительны. Стойкость асимметричных криптосистем базируется, в основном, на алгоритмической трудности решить за приемлимое время какую-либо задачу. Если злоумышленнику удастся построить такой алгоритм, то дискредетирована будет вся система и все сообщения, зашифрованые с помощью этой системы. В этом состоит главная опасность асимметричных криптосистем в отличие от симметричных. Примеры - системы о.ш. RSA, система о.ш. Рабина и т.д.
Одно из основных правил криптографии (если рассматривать ее коммерческое применение, т.к. на государственном уровне все несколько иначе) можно выразить следующим образом: взлом шифра с целью прочесть закрытую информацию должен обойтись злоумышленнику гораздо дороже, чем эта информация стоит на самом деле.
Постулатом для симметричных криптосистем является секретность ключа. Симметричные
криптосхемы в настоящее время принято подразделять на блочные и поточные.
Блочные криптосистемы разбивают текст сообщения (файла, документа и т.д.) на отдельные блоки и затем осуществляют преобразование этих блоков с использованием ключа.
Поточные криптосистемы работают несколько иначе. На основе ключа системы вырабатывается некая последовательность - так называемая выходная гамма, которая затем накладывается на текст сообщения. Таким образом, преобразование текста осуществляется как бы потоком по мере выработки гаммы. Как правило, используются для нужд военных, шифрования в средствах связи и т.д.
Однако не следует считать это разделение закостенелым. Так, например, при использовании некоторых ухищрений получают из блочного шифра - поточный и наоборот (см. БЛОЧНЫЕ ШИФРЫ). А, например, блочный шифр с размером выходного блока 8 бит (один символ) можно считать поточным.
Общую схему связи в случае симметричных криптосистем можно изобразить следующим образом:
где М - открытый текст, К - секретный ключ, передаваемый по закрытому каналу, Ек(М) - операция зашифрования, а Dk(M) - операция расшифрования. Возникает вопрос - почему нельзя передавать данные сразу по закрытому каналу, ведь используется же он для передачи ключа? Ответ прост. Как правило, закрытый канал имеет очень высокую защищенность, но в то же время и очень низкую пропускную способность, т.е. работает на очень низких скоростях. Гораздо проще передать по нему маленький ключ, чем мегабайты информации. Или же в качестве закрытого канала используется курьерская доставка, обмен секретным ключом при встрече и т.д.
Блочные шифры оперируют с блоками открытого текста. К ним предъявляются следующие требования:
достаточная криптостойкость;
простота процедур зашифрования и расшифрования;
приемлимая надежность.
Под криптостойкостью понимают время, необходимое для раскрытия шифра при использовании
наилучшего метода криптоанализа. Надежность - доля информации, дешифруемая при
помощи какого-то криптоаналитического алгоритма.
Само преобразование шифра должно использовать следующие принципы (по К. Шеннону):
Рассеивание (diffusion) - т.е изменение любого знака открытого текста или ключа
влияет на большое число знаков шифротекста, что скрывает статистические свойства
открытого текста;
Перемешивание (confusion) - использование преобразований, затрудняющих получение
статистических зависимостей между шифротектстом и открытым текстом.
Практически все современные блочные шифры являются композиционными - т.е состоят
из композиции простых преобразований или F=F1oF2oF3oF4o..oFn, где F - преобразование
шифра, Fi - простое преобразование, называемое также i-ым циклом шифрования.
Само по себе преобразование может и не обеспечивать нужных свойств, но их цепочка
позволяет получить необходимый результат. Например, стандарт DES состоит из
16 циклов. В иностранной литературе такие шифры часто называют послойными (layered).
Если же используется одно и то же преобразование, т.е. Fi постоянно для "i,
то такой композиционный шифр называют итерационным шифром.
Наибольшую популярность имеют шифры, устроенные по принципу "шифра Фейстеля
(Файстеля - Feistel)" (петли Фейстеля, сети Файстеля), т.е в которых:
входной блок для каждого преобразования разбивается на две половины: p=(l,r),
где l - левая, a r - правая;
используется преобразование вида Fi (l,r )=(r,l Д fi (r)), где fi - зависящая
от ключа Ki функция, а Д - операция XOR или некая другая.
Функция fi называется цикловой функцией, а ключ Ki, используемый для получения
функции fi называется цикловым ключом. Как можно заметить, с цикловой функцией
складывается только левая половина, а правая остается неизменной. Затем обе
половины меняются местами. Это преобразование прокручивается несколько раз (несколько
циклов) и выходом шифра является получившаяся в конце пара (l,r) Графически
все выглядит следующим образом:
В качестве функции fi выступает некая комбинация перестановок, подстановок,
сдвигов, добавлений ключа и прочих преобразований. Так, при использовании подстановок
информация проходит через специальные блоки, называемые S-блоками (S-боксами,
S-boxes), в которых значение группы битов заменяется на другое значение. По
такому принципу (с небольшими отличиями) построены многие алгоритмы: DES, FEAL,
серия LOKI и т.д.
В других алгоритмах используются несколько иные принципы. Так, например, алгоритмы, построенные по SP-принципу (SP-сети) осуществляют преобразование, пропуская блок через последовательность подстановок (Substitutions) и перстановок (Permutations). Отсюда и название - SP-сети, т.е. сети "подстановок-перстановок". Примером такого алгоритма является очень перспективная разработка Rijndael. Возможно применение в алгоритмах и каких-либо новых конструкций, но как правило, они несут в себе оперделенные ошибки (пример - FROG, HPC). Но все перечисленные алгоритмы являются композиционными. Саму идею построения криптографически стойкой системы путем последовательного применения относительно простых криптографических преобразований была высказана Шенноном (идея многократного шифрования).
Размеры блоков в каждом алгоритме свои. DES использует блоки по 64 бита (две половинки по 32 бита), LOKI97 - 128 бит. При размере выходных блоков до 8 бит шифр можно считать поточным.
Получение цикловых ключей.
Ключ имеет фиксированную длину. Однако при прокрутке хотя бы 8 циклов шифрования с размером блока, скажем, 128 бит даже при простом прибавлении посредством XOR потребуется 8*128=1024 бита ключа, поскольку нельзя добавлять в каждом цикле одно и то же значение - это ослабляет шифр. Посему для получения последовательности ключевых бит придумывают специальный алгоритм выработки цикловых ключей (ключевое расписание - key schedule). В результате работы этого алгоритма из исходных бит ключа шифрования получается массив бит определенной длины, из которого по определенным правилам составляются цикловые ключи. Каждый шифр имеет свой алгоритм выработки цикловых ключей.
Чтобы использовать алгоритмы блочного шифрования для различных криптографических задач существует несколько режимов их работы. Наиболее часто встречающимися в практике являются следующие режимы:
электронная кодовая книга - ECB (Electronic Code Book);
сцепление блоков шифротекста - CBC (Cipher Block Chaining);
обратная связь по шифротектсту - CFB (Cipher Feed Back);
обратная связь по выходу - OFB (Output Feed Back);
Обозначим применение шифра к блоку открытого текста как Ek(M)=C, где k - ключ,
M - блок открытого текста, а C - получающийся шифротекст.
Электронная Кодовая Книга (ECB)
Исходный текст разбивается на блоки, равные размеру блока шифра. Затем с каждый блок шифруют независимо от других с использованием одного ключа шифрования. Графически это выглядит так:
Непосредственно этот режим применяется для шифрования небольших объемов информации, размером не более одного блока или для шифрования ключей. Это связано с тем, что одинаковые блоки открытого текста преобразуются в одинаковые блоки шифротекста, что может дать взломщику (криптоаналитику) определенную информацию о содержании сообщения. К тому же, если он предполагает наличие определенных слов в сообщении (например, слово "Здравствуйте" в начале сообщения или "До свидания" в конце), то получается, что он обладает как фрагментом открытого текста, так и соответствующего шифротекста, что может сильно облегчить задачу нахождения ключа.
Основным достоинством этого режима является простота реализации.
Сцепление блоков шифротекста (CBC)
Один из наиболее часто применимых режимов шифрования для обработки больших количеств информации. Исходный текст разбивается на блоки, а затем обрабатывается по следующей схеме:
Первый блок складывается побитно по модулю 2 (XOR) с неким значением IV - начальным
вектором (Init Vector), который выбирается независимо перед началом шифрования.
Полученное значение шифруется.
Полученный в результате блок шифротекста отправляется получателю и одновременно
служит начальным вектором IV для следующего блока открытого текста.
Расшифрование осуществляется в обратном порядке. Графически схема выглядит следующим
образом:
В виде формулы, преобразование в режиме CBC можно представить как Ci=Ek(MiЕCi-1), где i - номер соответствующего блока. Из-за использования такого сцепления блоков шифротекста с открытым текстом пропадают указанные выше недостатки режима ECB, поскольку каждый последующий блок зависит от всех предыдущих. Если во время передачи один из блоков шифротекста исказится (передастся с ошибкой), то получатель сможет корректно расшифровать последующие блоки сообщения. Проблемы возникнут только с этим "бракованным" и следующим блоками. Одним из важных свойств этого режима является "распространение ошибки" - изменение блока открытого текста меняет все последующие блоки шифротекста. Поскольку последний блок шифротекста зависит от всех блоков открытого текста, то его можно использовать для контроля целостности и аутентичности (проверки подлинности) сообщения. Его называют кодом аутентификации сообщения (MAC - Message Authentication Code). Он может защитить как от случайных, так и преднамеренных изменений в сообщениях.
Обратная связь по шифротексту (CFB)
Режим может использоваться для получения из поточного шифра из блочного. Размер блока в данном режиме меньше либо равен размеру блока шифра. Схема данного режима:
IV представляет собой сдвиговый регистр. Вначале IV заполняется неким значением,
которое называется синхропосылкой, не является секретным и передается перед
сеансом связи получателю.
Значение IV шифруется.
Берутся первые k бит зашифрованного значения IV и складываются (XOR) с k битами
открытого текста Ю получается блок шифротекста из k бит.
Значение IV сдвигается на k битов влево, а вместо него становится значение ш.т.
Затем опять 2 пункт и т.д до конца.
Расшифрование аналогично.
Особенностью данного режима является распространение ошибки на весь последующий текст. Рекомендованные значения k: 1 =< k =< 8.
Применяется как правило для шифрования потоков информации типа оцифрованной речи, видео.
Обратная связь по выходу (OFB)
Данный режим примечателен тем, что позволяет получать поточный шифр в его классическом виде (см ПОТОЧНЫЕ ШИФРЫ), в отличии от режима CFB, в котором присутствует связь с шифротекстом. Принцип работы схож с принципом работы режима CFB, но сдвиговый регистр IV заполняется не битами шифротекста, а битами, выходящими из под усечения. Вот его схема:
Расшифрование осуществляется аналогично. Т.е. для любого блока длины k операция зашифрования выглядит следующим образом: Ci=MiЕGi, где Gi - результат зашифрования некоторого вектора, являющегося заполнением сдвигового регистра. Главное свойство шифра - единичные ошибки не распространяются, т.к заполнение сдвигового регистра осуществляется не зависимо от шифротекста.
Область применения: потоки видео, аудио или данных, для которых необходимо обеспечить оперативную доставку. Широко используется у военных наряду с поточными шифрами.
Аутентификация сообщений с помощью блочных шифров.
Настал черёд ещё нескольких определений:
Аутентификация (authentication) - проверка подлинности чего(или кого-)-либо.
Может быть аутентификация пользователя, сообщения и т.д. Необходимо отличать
ее от следующего понятия:
Идентификация (identification) - некое описательное представление какого-то субьекта. Так, если кто-то заявляет, что он - Вася Иванов, то он идентифицирует себя как "Вася Иванов". Но проверить, так ли это на самом деле (провести аутентификацию) мы можем только при помощи его паспорта.
Итак, как же можно проверить подлинность сообщения с помощью блочного шифра? Довольно просто.
Отправитель А хочет отправить некое сообщение (a1,..,at ). Он зашифровывает
его на секретном ключе, который знает только он и получатель, в режиме CBC или
CFB это сообщение, а затем из получившегося шифротекста берет последний блок
bt из к бит (при этом к должно быть достаточно большим).
Отправитель А посылает сообщение (a1, .. , at , bt ) получателю в открытом виде
или зашифровав его на другом ключе.
Получатель В, получив сообщение, (a1, .. , at , bt ), зашифровывает (a1,..,at
) в том же режиме, что и А (должна быть договоренность) на том же секретном
ключе (который знает только он и А).
Сравнивая полученный результат с bt он удостоверяется, что сообщение отправил
А, что оно не было подделано на узле связи (в случае передачи в открытом виде).
В данной схеме bt является кодом аутентификации сообщения (МАС). Для российского
стандарта шифрования процесс получения кода аутентификации называется работой
в режиме имитовставки.
Некоторые комментарии:
Режим шифрования должен быть обязательно с распространением ошибок (т.е CBC или CFB). Необходимо использовать шифр с достаточной длиной блока, а то может появиться ситуация, когда из-за небольшого числа используемых бит для аутентификации возможно подменить исходное сообщение и при знании ключа получить тот же самый результат. Также очевидно, что схема опирается на то, что оба абонента имеют один и тот же секретный ключ, который получили заранее.
Шифрование в поточных шифрах осуществляется на основе сложения некоторой ключевой последовательности (гаммы) с открытым текстом сообщения. Сложение осуществляется познаково посредством XOR. Уравнение зашифрования выглядит следующим образом:
ci = mi Е ki для i=1,2,3...
где ci - знак шифротекста, mi - знак открытого текста, ki - знак ключевой последовательности. Расшифрование выглядит так:
mi = ci Е ki для i=1,2,3...
В качестве знаков могут выступать как отдельные биты, так и символы (байты). Таким образом, поточные шифры подходят для шифрования непрерывных потоков данных - голоса, видео и т.д. В общем виде схему шифра можно изобразить следующим образом:
Можно сказать, что шифрование осуществляется наложением гаммы(шифрование гаммированием).
А сама гамма является ключом шифрования. Но иметь ключ, равный по размеру шифруемым
данным представляется проблематичным. Поэтому поточные шифры и вырабатывают
выходную гамму на основе некоторого секретного ключа небольшого размера, а значит
основной задачей поточных шифров является выработка некоторой последовательности
(выходной гаммы) для шифрования. Т.е. выходная гамма является ключевым потоком
для сообщения. Поточные шифры классифицируют следующим образом:
синхронные;
самосинхронизирующиеся (асинхронные).
Шифр вырабатывает гамму на основе секретного ключа, она складывается с открытым текстом и результат посылается другому абоненту и расшифровывается аналогично. Блок, вырабатывающий гамму называется генератором гаммы или псевдослучайным генератором (гаммы) - PRG(Pseudo Random Generator). Любой блочный шифр в режиме OFB представляет собой синхронный поточный шифр.
Очевидно, что на вырабатываемую последовательность накладываются требования. Ведь если в ней есть большие последовательности нулей, то получается, что в линию при передаче передается текст сообщения с открытом виде. Или если последовательность из единиц - тот же эффект (т.к. ничто не мешает противнику попробовать "протянуть" несколько подряд идущих единиц в качестве гаммы для перехваченного сообщения. Результат - кусок открытого текста у противника). Поэтому наилучшей гаммой является случайная последовательность. Однако нельзя независимо друг от друга сгенерировать 2 одинаковые случайные последовательности.
Генераторы гаммы вырабатывают так называемые псевдослучайные последовательности, которые зависят от ключа шифрования, но тем не менее по своим характеристикам сходны со случайными. Задача ставится таким образом, чтобы при наличии определнного количества битов последовательности нельзя было предсказать следующие биты. Помимо этого 1 и 0 на входе должны быть равновероятны (т.е. вероятность появления 1 = вер-ти появления 0 = 0.5). Для достижения этого последовательности исследуются статистическими тестами.
Вообще, генерирование непредсказуемых псевдослучайных последовательностей является одной из важных криптографических задач на сегодняшний день (и проблем). Придумано множество генераторов, статистических тестов. Исследование псевдослучайных последовательностей мы рассмотрим далее.
Синхронные поточные шифры обладают следующими свойствами:
требования по синхронизации. При использовании синхронных поточных шифров получатель
и отправитель должны быть синхронизированы - т.е. вырабатывать одинаковые значения
ключевого потока для соответствующих знаков передаваемого потока данных. Если
синхронизация нарушится (например, вследствие потери знака при передаче), процесс
расшифрования не даст корректного результата.
отсутствие размножения ошибок. Изменение знака шифртекста при передаче не вызывает
ошбок при расшифровании других знаков шифртекста.
свойство активной атаки. Как следствие первого свойства, любая вставка или удаление
символа в шифртекст активным противником приводит к нарушению синхронизации
и обнаруживается получателем, расшифровывающим сообщение. Как следствие второго
свойства, активный противник может изменять символы шифртекста и эти изменения
приведут к соответствующим изменениям в открытом тексте, получаемом при расшифровании.
Посему необходимы дополнительные механизмы, позволяющие предотвратить это.
Рассмотрим одну из атак на такие шифры.
O1O2O3... - знаки открытого текста.
К1К2К3... - знаки ключевой последовательности.
С1С2С3... - знаки шифротекста, полученные следующим образом:
Допустим, что при повторном шифровании на том же ключе произошла вставка одного знака O':
Криптоаналитик противника перехватил обе последовательности C1C2C3C4 и C1C'2C'3C'4. Составив затем уравнения: К2 =C'2 Е O'; O2=C2 Е К2; К3=C'3 Е O2; O3=C3ЕК3 и т.д., и подобрав значение одного знака O' он сможет прочитать сообщение после этого знака. Поскольку в результате исследований у него будет фрагмент ключевой последовательности (гаммы), то он может попытаться восстановить всю гамму и получить сообщение целиком (если вэтом есть необходимость, конечно). Отсюда можно сделать вывод, что нельзя дважды использовать один и тот же ключ.
Хотя описание атаки носит гипотетический характер, тем не менее она очень и очень реальна, Ведь в качестве вставленного знака с таким же успехом может выступать и последовательность знаков. В этом случае подбираться будет последний знак вставленной последовательности. Представим себе ситуацию шифрования 2 файлов одним ключом, причем файлы имеют одинаковый заголовок и, скажем, середину (довольно реальная ситуация!!!). Проведя описанную атаку, криптоаналитик получит либо полностью исходные файлы, либо их фрагменты, что может иметь непоправимые последствия.
Даже если 2 абсолютно различных текста шифруются на одном ключе, противник может вычислить сумму знаков шифртекстов Ci1Е Ci2 =Oi1Е Кi Е Кi Е Oi2=Oi1Е Oi2, где Ci1- i-ый знак первого шифртекста, Ci2 - i-ый знак второго, Oi1 и Oi2 - знаки открытых текстов соответственно.
Сумма открытых текстов отнюдь не случайна и противник сможет восстановить 2 сообщения.
Самосинхронизирующиеся поточные шифры
- каждый знак ключевого потока определяется фиксированным числом предшествующих знаков шифротекста. Схематично это можно изобразить так:
Данному типу шифров соответствуют блочные шифры, работающие в режиме CFB.
Самосинхронизирующиеся поточные шифры обладают следующими свойствами:
самосинхронизация. Самосинхронизация существует при удалении или вставке некоторых
знаков шифртекста, поскольку процесс расшифрования зависит от некоторого фиксированного
числа предшествующих знаков шифртектста. Это означает, что в случае удаления
знака из шифртекста сначала будут ошибки при расшифровании, а затем все станет
хорошо и ошибок не будет.
ограниченное размножение ошибок. Предположим, что состояние шифра зависит от
t предидущих знаков шифртекста. Если во время передачи один знак шифротекста
был изменен или удален/вставлен, то при расшифровке будет искажено не более
t знаков, после которых пойдет опять нормальный текст.
свойство активной атаки. Из второго свойства следует, что любое изменение знаков
шифртекста активным противником приведет к тому, что несколько знаков шифротекста
расшифруются неправильно и это с большей (по сравнению с синхронными шифрами)
веротностью будет замечено со стороны получателя, расшифровывающего сообщение.
Однако в случае вставки или удаления знаков шифртекста (по св-ву 1) это намного
труднее обнаружить (по сравнению с синхронными шифрами - там получается рассинхронизация).
Поэтому необходимы дополнительные механизмы для контроля этой ситуации.
рассеивание статистики открытого текста. Поскольку каждый знак открытого текста
влияет на весь последующий шифртекст, статистические свойства открытого текста
(ведь он далеко не случаен) не сохраняются в шифртексте.
Для исследования свойств поточных шифров очень часто используется теория конечных
автоматов.
Список использованной литературы:
Основные понятия для начинающих - http://stophack.ru/crypto/basic.html
Симметричные криптосистемы - http://citforum.pomorsu.ru/security/belyaev_book/its2000_27.shtml
Симметричные криптосистемы - http://www.crime-research.ru/library/Crypto03.html