Классическая криптография

ЛЕКЦИЯ 16. Классическая криптография.

1. Криптология, криптография и криптоанализ. Основные задачи криптографии. Понятия открытого текста, криптограммы, ключа и криптосистемы. Принцип Керкхгоффа. Приложения криптографии.

2. Вычислительно сложные задачи. Односторонние функции. Пример: электронная жеребьевка.

3. Понятия криптографического протокола и криптографического алгоритма. Корректность и полнота протокола.

4. Криптоанализ и основные виды атак. Подслушиватели (нарушители). Активный и пассивный, внутренний и внешний подслушиватели.

5. Стеганография и ее задачи.

6. Типы секретности сообщений (по Шеннону). Безусловно и условно стойкие шифры. Пример: код Вернама (одноразовый блокнот).

7. Распределение ключей.  Генерация ключей, их хранение и уничтожение.

8. Одноключевые (симметричные) методы шифрования. Рассеивание и перемешивание. Понятие о криптосистемах DES и ГОСТ 28147-89, их достоинства и недостатки. Основные проблемы симметричных протоколов. Аутентификация секретного ключа. Атаки раздельных миров.

Рекомендуемые материалы

9. Двухключевые (асимметричные) методы шифрования. Механизм распределения ключей по открытому каналу по У.Диффи и М.Хеллману. Понятие о криптосистемах RSA и Эль-Гамаля. Электронная подпись.

Исторически криптография (наука о создании секретной информации) возникла из потребности передачи секретной информации. Вместе с криптоанализом (наука о взламывании секретной информации) криптография составляет часть науки криптологии. Криптология в настоящее время является частью математики, кроме того, она имеет ряд важных приложений в информационных технологиях. Основой криптологии как науки послужила работа Шеннона “Теория связи в секретных системах” (1949г.).

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

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

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

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

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

Основные приложения современной криптографии:

1. Защита от несанкционированного чтения или обеспечение конфиденциальности информации.

2. Защита от навязываемых ложных сообщений (как умышленных, так и непреднамеренных).

3. Идентификация законных пользователей

4. Контроль целостности информации.

5. Аутинтификация информации - установление санкционированным получателем того факта, что полученное сообщение послано санкционированным отправителем.

6. Электронная подпись

7. Системы тайного электронного голосования.

8. Электронная жеребьевка.

9. Защита от отказа факта  приема сообщения.

10. Одновременное подписание контракта.

11. Защита документов от подделки.

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

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

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

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

II. Поскольку используемая функция является однонаправленной, то В не может по значению  определить . Поэтому он вынужден угадывать четность . Предположим, В выбирает “ - четное число” и сообщает ответ пользователю А.

III.  Пользователь А сообщает пользователю В число .

IV.  Пользователь В вычисляет значение  и если , то В убеждается, что его партнер действительно предоставил для проверки первоначально выбранное число.

Понятие криптографического протокола.

В критографии широко используются два термина - алгоритм и протокол; интуитивно смысл их понятен.

Под алгоритмом мы будем понимать набор команд, действий, инструкций, вычислений, которые необходимо выполнить для того, чтобы из исходных данных получить некий результат. Понятие “алгоритм”, в основном, используется в вычислительной математике и кибернетике. Алгоритм выполняется субъектом (вычислителем). В результате выполнения алгоритма могут возникать новые данные как результат преобразования исходных данных.

            Под протоколом будем понимать совокупность действий (инструкций, команд, вычислений, алгоритмов), выполняемых в заданной последовательности двумя или более субъектами с целью достижения некоего результата. Участвующие в протоколах субъекты (рабочая станция, программа ЭВМ, оператор, сервер, орган власти и т.д.) действуют по предписанным алгоритмам. Таким образом, алгоритм служит внутренним элементом протокола. Понятие “протокол”, в основном используется в системах связи (communications). Криптографические протоколы - это такие протоколы, которые используют криптографические преобразования данных. Для того, чтобы протокол приводил к желаемой цели, необходимо, чтобы выполнялись следующие требования:

n корректность протокола - совокупность действий, предусмотренных протоколом, должно обеспечить получение требуемого результата при всех возможных ситуациях;

n полнота и однозначность протокола - протокол должен конкретизировать действия каждого участника для всех возможных ситуаций;

n непротиворечивость - результаты, полученные различными участниками протокола, не должны быть противоречивыми;

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

Классификация основных типов подслушивателей и атак.

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

1. Криптоанализ на основе шифротекста (криптограммы).

2.  - на основе известного открытого текста и соответствующей ему криптограммы.

3.  - на основе выбранного открытого текста.

4.  - на основе выбранной криптограммы.

5.  - на основе адаптированного открытого текста.

6.  - на основе адаптированной криптограммы.

7.  - на основе аппаратных ошибок.

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

n прочитать криптограмму,

n взломать односторонние функции - т.е. вычислить значение аргумента по значению функции,

n выдать себя за другого субъекта,

n навязать ложные сообщения,

n расширить свои полномочия

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

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

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

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

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

Виды секретности сообщений (по К.Шеннону)

Шеннон рассматривал шифрование (кодирование) как отображение исходного сообщения в криптограмму - зашифрованное сообщение:

,                                                                                                (16.1)

где С - криптограмма (от coding), F_i - отображение, М - исходное сообщение (от message), i = индекс, соответствующий конкретному используемому ключу. Для однозначного декодирования сообщения отображение F_i должно иметь единственное обратное отображение, такое, что

,                                                                                                   (16.2)

где I - тождественное отображение:

.                                                                                              (16.3)

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

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

, ,  

Текущий шаг криптования  выражается следующим образом:

.

Например, будем использовать простой алфавит заглавных букв и некоторых знаков препинания:

Допустим, мы хотим зашифровать сообщение “КОД ВЕРНАМА”. Запишем его в верхней строке таблицы. Ниже укажем соответствующие численные символы из верхней таблицы. В третью строку поместим случайную выборку из сорока знаков от 00 до 39. В последней строке разместим результат суммирования символов второй и третьей строки по модулю 40:

Например, четвертый символ “пробел” в сообщении имеет числовой код “34”. Соответствующее случайное число, выпавшее на этот символ, оказалось “28”. Тгда 34 + 28 = 62 = 40 + 22, следовательно, остаток при суммировании по модулю “40” равен 22. Таким образом, шифрование и дешифрование по рассмотренному алгоритму можно записать в виде:

.                                                                                    (16.4)

.                                                                                    (16.5)

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

                                                              (16.6)

для всех возможных сообщений М. В нашем примере:

                                                                  (16.7)

где L = 40.  Выбранный нами источник ключа обеспечивает равную вероятность выбора любого ключа длины . В этом случае вероятность выбора данного ключа длины n составляет

.                                                                                         (16.8)

Отсюда следует, что для произвольных М и С выполняется условие

.                                                                           (16.9)

Напоминание (из Лекции 3). По определению взаимная информация  I(X:Y) есть мера того сколько информации содержат Х и Y друг о друге. Например, если Х и Y - независимые величины, то p(x,y) = p(x)p(y), так что I(X:Y) = 0. Соотношения между основными мерами классической информации показаны на рисунке. H(Y|X) есть мера того, сколько информации, в среднем, оставалось бы в Y при условии, что мы бы знали Х.

Тогда по Шеннону, криптосистема обладает абсолютной секретностью, если взаимная информация обращается в нуль:

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

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

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

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

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

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

Распределение ключей.

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

- генерацию ключей;

- распределение ключей;

- хранение ключей;

- уничтожение ключей.

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

Если подслушивателю становится известным ключ, то он получает все привилегии законного пользователя. Принципиальным при рассмотрении криптосистем является способ раскрытия ключа, основанный на криптоанализе. Под раскрытием ключа путем криптоанализа будем понимать определение ключа (включая его угадывание)[2]. Принципиально все криптосистемы подвержены атакам такого рода, они называются силовыми атаками и состоят в тотальном переборе по всему пространству ключей. Они являются наиболее слабыми; для их предотвращения требуется аккуратность в выборе длины ключа и процедур его генерации. В настоящее время безопасной считается длина ключа равная 80 битам (это число содержит около 10²⁰ десятичных знаков).

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

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

,                                                                                  (16.10)

где g_i - i-ый член порождаемой числовой последовательности; а, b, M и начальное порождающее число g_i- являются ключевыми параметрами.

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

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

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

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

ОДНОКЛЮЧЕВЫЕ (СИММЕТРИЧНЫЕ) МЕТОДЫ ШИФРОВАНИЯ.

Одним из методов криптования является замена символов исходного текста t на символы криптограммы с. Есть два способа: поточный и блочный. Поточный метод осуществлялся в коде Вернама, когда t_i поочередно заменяются на c_i по определенному алгоритму. Результат зависит от секретного ключа.

К блочным методам относится, например, известная система DES (decryption - encryption - standard), принятая в 1977г. в США. В ней используется многократное чередование перемешивающих и рассеивающих преобразований, не управляемых ключом, а также простых преобразований, управляемых ключом.

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

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

Алгоритм DES преобразует входную информацию блоками объемом 64 бит. Основные процедуры - подстановка и перестановка. Они реализуются разными блоками (S- и P-блоки). Например Р-блоки реализуются с помощью переплетения проводников. Эти операции - нелинейные, именно они предопределяют криптографическое закрытие данных. Долгое время принципы выбора таблиц перестановок держались в секрете, хотя и алгоритм и сами таблицы были открыты. В настоящее время компания IBM опубликовала и сами критерии выбора S-блоков. Они выбираются так, чтобы изменение одного бита на входе приводит к изменению по крайней мере двух битов на выходе - т.н. принцип размножения ошибок. Общая схема алгоритма DES состоит в следующем. 64-битовый блок открытого текста после начальной перестановки делится на две части по 32 бит каждая. Левую и правую половины обозначим L и R, соответственно. Затем выполняются 16 раундов шифрующих операций вида:

Здесь К_i - 48-битовый подключ, вырабатываемый по простым процедурам из 56-битового секретного ключа и используемый на i-ом раунде. Сущность алгоритма заложена в преобразованиях, которые выполняются для получения значения функции . Все детали таких преобразований считаются известными, за исключением секретного ключа К_i .

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

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

В Российском стандарте шифрования (ГОСТ СССР 28147-89) задействуется 64-битовый шифр, использующий 256-битовый секретный ключ, представленный в виде восьми 32-битовых подключа Q_j, где j = 0, 1,...7. В этой системе функция  задается операцией суммирования по модулю 2³², с помощью табличных подстановок, выполняемых над 4-битовыми подблоками и операцией циклического сдвига влево на 11 бит, выполняемой над 32-битовым подблоком. Таблицы подстановок служат дополнительным ключом и должны держаться в секрете. Этот долговременный ключ является общим для всех пользователей сети и поставляется в установленном порядке. Стойкость такой системы критически зависит от качества используемых таблиц подстановок. При правильном выборе даже если таблицы станут известны подслушивателю, стандарт обеспечивает высокую стойкость. Однако, критерии выбора таблиц, в отличие от американских, до сих пор не опубликованы. Заметим, что требование секретности таблиц подстановок не согласуется с общепринятым принципом Керкхгоффа, поскольку данные элементы относятся скорее к алгоритму шифрования, а не к легко сменяемому секретному ключу. Вообще, секретность алгоритма шифрования существенно затрудняет определение открытого текста по криптограмме. Однако этот элемент повышения стойкости криптограммы на практике используется редко, поскольку крайне трудно обеспечить секретность элементов криптосистемы, которые используются долгое время и известны широкому кругу пользователей. Отсюда - в практических криптосистемах нужно обеспечить сменяемость алгоритма шифрования.

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

Основным недостатком Российского стандарта является низкая скорость при программной реализации (как и для DES), что связано с использованием большого числа операций над 4-битовыми подблоками. Кроме того, чтобы изменение одного входного бита оказало влияние на каждый выходной бит в случае Российской криптосистемы требуется выполнить 8 раундов, а в криптосистеме DES - только 5.

К достоинствам относят

n 256-битовый секретный ключ, что делает бессмысленными атаки, основанные на переборе секретного ключа не только в настоящее время, но и в далеком будущем, если говорить о классических компьютерах).

n простая аппаратная реализация, связанная с хорошим расписанием использования ключа

n 32 цикла шифрующих операций обеспечивают высокую стойкость.

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

1. распределение ключей по защищенному каналу;

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

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

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

ДВУХКЛЮЧЕВЫЕ (АСИММЕТРИЧНЫЕ) МЕТОДЫ ШИФРОВАНИЯ.

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

Под односторонней функцией с секретом понимается семейство обратимых функций f_z с параметром z, таких, что для какого-то z можно найти некие алгоритмы E_z и D_z, позволяющие просто вычислить значение  для всех x из области определения, а также  для всех y их области значений, однако, практически для любых значений параметра z и практически для всех значений y из области значений f_z нахождение  вычислительно неосуществимо даже при известном E_z (т.е. требуется знание D_z).

В качестве односторонней функции У.Диффи и М.Хеллман предложили функцию дискретного возведения в степень

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

            Для очень больших модулей р (например, при к = 1024 бит)для данного х легко вычислить значение этой функции. Такая процедура называется дискретным возведением в степень. Обратной к функции дискретного возведения в степень является функция , которая ставит в соответствие заданному значению y такое значение х, для которого выполняется условие . Задача нахождения такого х называется дискретным логарифмированием. Дискретные логарифмы сложно вычисляются, когда число  содержит один большой простой множитель, например, когда оно представимо в виде , где  - простое число. Тогда трудоемкость дискретного логарифмирования равна примерно  умножений по модулю р.

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

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

Механизм распределения секретных ключей по открытому каналу состоит в следующем.

1. Каждый абонент выбирает случайный секретный ключ x и открытый ключ y, соответствующий выбранному секретному ключу, в соответствии с формулой:

.                                                                               (16.11)

Для любого значения x легко вычислить y, однако при размере числа p, равном 512 бит и выше, вычислительно неосуществимо выполнение дискретного логарифмирования. Значит, невозможно определить число x, для которого значение  равно заданному значению y.

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

2.1. Алиса берет из справочника открытый ключ Боба и, используя свой секретный ключ, вычисляет общий секретный ключ, пользуясь секретом - повторным возведением в степень с другим показателем.:

                                              (16.12)

где  и  - открытые ключи для Алисы (А) и Боба (В), а  - соответствующие секретные ключи. Общий секретный ключ Z_AB не нужно передавать по сети связи, поскольку Боб по известному из справочника открытому ключу Алисы аналогичным образом вычисляет его значение:

                                              (16.13)

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

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

Ещё посмотрите лекцию "Сбор эмпирических данных" по этой теме.

Итак, решение задачи дискретного логарифмирования существует, но оно вычислительно неосуществимо. Таким образом, стойкость метода Диффи-Хеллмана основана на сложности дискретного логарифмирования.

Наиболее популярные асимметричные схемы в настоящее время - это системы RSA (Ривест - Шамир - Адэльман) и Эль-Гамаля. Обе они используются для формирования электронной подписи, когда владелец секретного ключа может подписать документ, а его подпись может быть проверена любым желающим по открытому каналу. Цифровая подпись представляет собой некоторое число со специфической структурой, которое допускает проверку (с помощью открытого ключа) того факта, что оно было выработано для некоторого сообщения с использованием секретного ключа.

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

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

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

[2] Остальные способы связаны с организационными и техническими мероприятиями.