Практическая стойкость шифров.

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

Основными количественными мерами стойкости шифра служат так называемые «трудоемкость метода криптографического анализа» и «надежность его». Обозначим через А - класс применимых к шифру алгоритмов дешифрования и через Τ(ϕ) - трудоемкость реализации алгоритма ϕ на некотором вычислителЬном устройстве.

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

min ET(ϕ), ϕ A.

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

Второй количественной мерой стойкости шифра относительно метода криптоанализа является надежность метода π(ϕ) - вероятность дешифрования.

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

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

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

Вопросы имитозащиты.

Имитостойкость шифров.

Предположим, что имеется связь между абонентами А и В. Абонент А может в определенный момент времени отправить абоненту В сообщение «у» - криптограмму, зашифрованную шифром (Χ,Κ,Υ,f) на ключе k К (здесь в рассуждениях мы используем модель шифра Шеннона, где под X понимается множество открытых (содержательных) текстов). До момента передачи у У канал связи «пуст», но в шифратор абонента В введен ключ k в ожидании получения сообщения от абонента А.

Возможные действия противника сформулируем в виде предположений

о его возможностях:

- он знает действующий шифр;

- он имеет доступ к каналу связи;

- он может считывать из канала любое сообщение;

- он может формировать и вставлять в канал связи любое сообщение;

- он может заменять передаваемое сообщение на любое другое сообщение;

- все указанные действия он может совершать «мгновенно» (располагая соответствующими техническими средствами);

- он не знает действующего ключа шифра.

Пусть (У,К,Хʽ,Х,Ф) - шифр расшифрования, X - множество содержательных открытых текстов, X X. Уравнение расшифрования у У при ключе k Κ будет записываться в виде: k^-1 у=х, х Хʽ.

Пусть канал связи «пуст» и противник вставляет в канал связи некоторое шифрованное сообщение - элемент у У. При действующем ключе k абонент В расшифрует у. Априори возможны два исхода:

1) он получит k^-1у Х, то есть абонент В не прочтет сообщение и сочтет его за ложное сообщение (напомним, что в качестве X выступает множество всех содержательных текстов);

2) k^-1у Х. В этом случае В получит открытое ложное сообщение х= k^-1у и действуя в соответсвии с этим сообщением может нанести себе ущерб.

Заметим, что при таком «навязывании» ложной информации противник не знает какое именно сообщение х Х (во втором случае) он «навязал» абоненту В. Такое навязывание ложной информации можно назвать навязыванием «наугад». При случайно выбираемом ключе k событие: k^-1у Х имеет свою вероятность

Р_н(у)=Р(k^-1у Х),

называемую вероятностью навязывания криптограммы у. Считается естественным, что противник выберет навязываемый у У так, чтобы максимизировать вероятность Р_н(у)· Защищающаяся сторона, в свою очередь, зная о возможных действиях противника, будет выбирать такой шифр, в котором максимальное значение вероятностей навязывания Рн = mах Р(k^-1у Х) минимально.

Величину 1/Рн назвают коэффициентом имитозащиты в пустом канале. При навязывании противником «наилучших» криптограмм у^,: Рн(у^,)= Рн величина 1/Рн характеризует среднее число попыток противника до навязывания ложной информации (предполагается случайный выбор ключей при каждой попытке).

Противник может ужесточить свои действия: пусть х(0) Х - сообщение, которое наносит максимальный ущерб абоненту В; противник может попытаться навязывать такое сообщение у У, при котором вероятность Р(k^-1у = х(0)) максимальна. Такой способ навязывания можно назвать целевым (прицельным).

Аналогичные ситуации возникают и при навязывании путем подмены передаваемого сообщения. Противник может обладать и дополнительной информацией (не отраженной выше в перечне его возможностей). Например, может знать открытый текст х Х, который скрывается за криптограммой у в канале связи. Аналогично вводится величина max Р(k ^-1 у' Χ) характеризующая стремление противника максимизировать условную вероятность навязывания, а защищающаяся сторона стремится минимизировать этот максимум.

 

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

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

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

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

В этом случае

Р_H(y,y`)

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

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

Для защиты от ложных навязываемых сообщений используют имитовставки. При передаче сообщения а А (на передающем устройстве) вырабатывают гамму G Г и по каналу связи передают пару (a,z), где z=F(a,G). На приемном устройстве с помощью шифра вырабатывается та же самая гамма G и проверяется для принятой из канала пары (a^{`</sup>,z<sup>`}) совпадение значения F(a^{`</sup> G) со значением z<sup>`} При совпадении значений делается вывод о приеме истинного сообщения. В противном случае, делается вывод о приеме ложного сообщения.

Коды аутентификации сообщений (Message authentication codes или MACs) — это следующий базисный элемент защиты сообщений. Они не обеспечивают секретность, но гарантируют аутентификацию и целостность. Они дают уверенность, что сообщение пришло именно от того источника, который обозначен как автор (это аутентификация), и что сообщение по пути не изменилось (а это целостность). Можно рассматривать MAC как защищающую от вскрытия оболочку сообщения. Кто угодно может прочесть сообщение — оболочка не обеспечивает секретность. Но кто-то, кто знает ключ MAC, может удостовериться, что сообщение не было изменено. Конкретнее, MAC — это номер, который прикреплен к цифровому сообщению.

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

Помехоустойчивость шифров.

Для определения понятия помехоустойчивости шифров используем модель так называемых эндоморфных шифров (термин предложил К. Шеннон), то есть шифров (Χ,Κ,Υ,f), для которых множество открытых текстов X совпадает с множеством криптограмм У. Для таких шифров (Χ,Κ,Υ,f) каждое преобразование f_k, k K является биекцией X в X (подстановкой на X). Множество таких биекций обозначают через П(K,f)={f_k: k Κ}, а сам эндоморфный шифр – через Α=(Χ,Π(Κ,f)) и называют подстановочной моделью эндоморфного шифра. При этом под ключом этого шифра понимают биекцию π Π(Κ,f). Уравнение шифрования записывают в виде х=у, уравнение расшифования записывают в виде π^-1y=x.

В дальнейшем, для определенности, будем считать, что множество X - это множество текстов одной и той же длины L в некотором алфавите Ω, X = Q^L.

Под искажением сообщения при его передаче по каналу связи понимается замена шифрованного сообщения у У на некоторое другое у*, у* У*. Характер (правило) замены определяется физическим состоянием как самого канала связи, так и окружающей его cреды, У≤У*.

Примером искажений являются так называемые искажения типа замены. Передаваемое по каналу связи сообщение у=Ь₁Ь₂,…b_l заменяется на сообщение y`=b`₁,b`<sub>2</sub>...b`_L. Имеется в виду, что исказиться может любая буква b_j сообщения у, при этом искажении она заменится на букву b`_j. Примерами других искажений являются искажения типа «пропуск», «вставка». Искажение типа пропуска букв состоит в том, что из сообщения у=Ь₁Ь₂,…b_l пропадут одна или несколько букв, стоящих на некоторых местах. Искажение типа вставки состоит в добавлении одной или нескольких букв алфавита Ω в сообщение y=b₁,b₃,...,b_L.