Васюков В_Н_ Теория электрической связи_

и источник ключей с энтропией

m

H K P K j log P K j .

j 1

Количество информации источника не может быть больше, чем log n (это количество соответствует равновероятным сообщени-

ям). Эта информация может быть полностью скрыта, только если неопределенность ключа не меньше log n . Таким образом, неопре-

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

Если источник порождает последовательности бесконечной длины, то никакой конечный ключ не дает совершенной секретно-

сти. Пусть длина сообщения равна N , а длина ключа M . Тогда для совершенной секретности требуется

N log n M log m ,

где n и m – объемы алфавитов для сообщений и ключей соответ-

ственно.

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

В качестве теоретической меры секретности Шеннон предложил использовать ненадежность 11 . Имеются две ненадежности: ненадежность ключа

где P E,M – совместная вероятность криптограммы E и сообщения M , P E, K – совместная вероятность криптограммы E и

ключа K , P M | E и P K | E – апостериорные вероятности для сообщения и ключа при условии перехвата криптограммы E .

11 Ненадежностью называется условная энтропия (см. разд. 8.2).

364 13. ОСНОВЫ КРИПТОЗАЩИТЫ СООБЩЕНИЙ В СИСТЕМАХ СВЯЗИ

Суммирование в (13.2) и (13.3) проводится по всем возможным криптограммам и ключам (соответственно по всем возможным криптограммам и сообщениям) определенной длины, поэтому не-

надежности зависят от числа N перехваченных букв криптограм-

мы. Постепенное убывание ненадежностей с ростом N соответст-

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

ся к нулю при N , и даже «строго идеальную систему», в которой HE (K) H(K) . Для сообщений на естественных языках

характерны неравновероятность и зависимость букв исходного текста, поэтому для них построение идеальной системы хотя и возможно, но осуществить его практически очень сложно [26].

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

Для того чтобы затруднить раскрытие шифров статистическими методами, Шеннон предложил использовать две идеи, которые он назвал «распылением» и «запутыванием». Смысл «распыления» состоит в таком преобразовании текста, при котором статистические связи между его элементами становятся трудно наблюдаемыми, хотя избыточность сообщения при этом и не изменяется. Идея «запутывания» (перемешивания) заключается в том, чтобы сделать соотношения между простыми статистиками в пространстве криптограмм и простыми подмножествами в пространстве ключей весьма сложными и беспорядочными [26]. На этих идеях основано

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

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

Один из примеров реализации такого подхода – государственный стандарт шифрования США, известный под названием DES (Data Encryption Standard). Алгоритм шифрования является открытым; секретным при каждом использовании алгоритма является только ключ. Ключ длиной в 56 бит обеспечивает высокий уровень стойкости шифра, так как общее количество ключей составляет около 7,2·1016. Открытый текст и криптограмма при этом являются двоичными 64-значными последовательностями. Криптоалгоритм DES представляет собой суперпозицию из 16 последовательных шифроциклов, в каждом из которых происходят подстановки и перестановки в четырехбитовых группах, при этом в каждом цикле используются 48 бит ключа, которые выбираются из полного ключа длиной в 56 бит [25]. По утверждению Национального бюро стандартов США, метод DES имеет высокую криптостойкость, которая делает его раскрытие дороже получаемой при этом прибыли, экономичен в реализации и эффективен в смысле быстродействия. Наиболее существенным недостатком считается слишком короткий ключ: для дешифрования требуется перебрать 256 (или 7,2·1016) ключей, что достаточно много для современной аппаратуры, но может оказаться преодолимым в ближайшем будущем. Впрочем, метод допускает простую модификацию в виде последовательного применения к сообщению нескольких циклов шифрования с различными ключами: например, уже при трех ключах для дешифрования требуется выполнение около 2168 (т.е. 3,7·1050) операций.

Отечественный стандарт шифрования данных, предусмотренный ГОСТ 28147-89, предназначен для шифрования данных аппа-

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

ций [25].

366 13. ОСНОВЫ КРИПТОЗАЩИТЫ СООБЩЕНИЙ В СИСТЕМАХ СВЯЗИ

ратным или программным путем [25]. Стандарт предусматривает различные режимы шифрования, но в любом случае используется 256-разрядный двоичный ключ. Двоичные данные, подлежащие зашифрованию, разбиваются на блоки по 64 разряда, над которыми выполняются преобразования, включающие суммирования по модулям 2, 232 и 232–1, подстановки и циклические сдвиги. Стандарт обладает всеми достоинствами алгоритма DES и в то же время свободен от его недостатков, однако имеет собственный существенный недостаток – очень низкое быстродействие при программной реализации [25].

13.5.КРИПТОСИСТЕМЫ

СОТКРЫТЫМ КЛЮЧОМ

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

мами [29]. Наиболее известен метод шифрования с открытым клю-

чом RSA13.

Согласно методу RSA, для генерирования ключей необходимо выполнить следующие действия [25].

1.Выбрать два больших простых числа p и q.

2.Определить их произведение n pq.

3.Выбрать число d, взаимно простое с числом ( p 1)(q 1) .

4.Определить число e, для которого выполняется условие

ed mod[( p 1)(q 1)] 1 .

5. Назвать открытым ключом числа e и n , а секретным ключом числа d и n .

13 Метод назван по первым буквам фамилий авторов – Rivest, Shamir, Adleman.

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

Для расшифрования используется формула с секретным ключом

Пример 13.1. Рассмотрим в качестве простого примера алгоритм RSA, основанный на очень малых числах p и q . Предположим, что

шифрованию подлежит сообщение на русском языке [25]. Буквы сообщения можно представить числами от 0 до 32 (см. разд. 13.2). Тогда за n можно принять число 33, а за простые числа p и q со-

ответственно 3 и 11. Итак, согласно описанному алгоритму:

1)выберем два простых числа p 3 и q 11 ;

2)найдем n 3 11 33 ;

3)за число d, взаимно простое с числом ( p 1)(q 1) 20 , примем число 3;

4)соотношению e 3mod(20) 1 удовлетворяют числа 7, 27,

47,…; выберем e 7 .

Итак, открытым ключом для зашифрования является пара чисел e 7 и n 33 , а закрытым (секретным) ключом для расшиф-

рования – пара чисел d 3 и n 33 .

Зашифруем слово ДОМ. Буквам Д, О и М соответствуют числа 5, 15 и 13. Используя открытый ключ, получим на основании (13.4) криптограмму, состоящую из чисел:

C1 57 mod(33) 78125mod(33) 14; C2 157 mod(33) 170859375mod(33) 27 ;

C3 137 mod(33) 62748517mod(33) 7 .

Для расшифрования криптограммы {14, 27, 7} воспользуемся формулой (13.5) и секретным ключом:

M1 143 mod(33) 2744mod(33) 5 ;

M2 273 mod(33) 19683mod(33) 15 ;

M3 73 mod(33) 343mod(33) 13. ◄

368 13. ОСНОВЫ КРИПТОЗАЩИТЫ СООБЩЕНИЙ В СИСТЕМАХ СВЯЗИ

Легко видеть, что в результате расшифрования получилось исходное открытое сообщение ДОМ. Следует отметить, что на практике применяются настолько большие числа p и q , что, зная e и

n (открытый ключ), невозможно найти d за приемлемое время,

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

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

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

13.6. ЦИФРОВАЯ ПОДПИСЬ

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

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

14 Кроме метода RSA, к криптосистемам с открытым ключом относятся системы Эль-Гамаля и Мак-Элиса [25].

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

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

КОНТРОЛЬНЫЕ ВОПРОСЫ

1.В чем заключается проблема защиты информации?

2.Что такое совершенная секретная система?

3.В чем отличие криптографии и стеганографии?

4.Чем отличаются шифры от кодов?

5.В чем состоят задачи криптографии и криптоанализа?

6.Что такое система с открытым ключом? На чем основана ее криптостойкость?

7.Что такое цифровая подпись?

УПРАЖНЕНИЯ

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

2.Зашифруйте короткое (10…20 букв) сообщение при помощи

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

3. Зашифруйте короткое слово (3…5 букв) при помощи алгоритма RSA, воспользовавшись данными примера 13.1. Расшифруйте полученный шифртекст.

аналоговых системах – среднеквадратическое отклонение принятого сообщения от переданного.

Скорость передачи информации I измеряется в битах в секунду; ее не следует путать с технической скоростью, измеряемой в бодах (см. разд. 1). Предельная скорость передачи информации по данному каналу называется его пропускной способностью С . Одна-

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

ным показателем – информационной эффективностью I /C .

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

стики и др. Таким образом, поиск решения при проектировании системы связи имеет характер задачи оптимизации с ограничениями.

Обозначая различные количественные показатели эффективности (качества) через k1, k2,...,km , получаем вектор K , который ха-

рактеризует качество системы. Множество векторов пространства размерности выше 1 не является естественно упорядоченным, как

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

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

решению соответствует его максимум (или минимум); этот скалярный показатель называется целевой функцией. Иногда за скалярный показатель качества можно принять линейную комбинацию компонент вектора K , но тогда встает вопрос о назначении весовых коэффициентов. В большинстве случаев более оправданным является подход, когда максимизируется одна компонента вектора (например, скорость передачи информации) при ограничениях в форме неравенств, накладываемых на остальные компоненты (например, средняя вероятность ошибки при приеме двоичного символа не более 0,001; задержка не более 0,1 с; потребляемая мощность не более 0,5 Вт и т.п.).

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

перспективы развития систем данного класса и близких классов и т.д. Такой подход называется системным [12].

14.2. ОПТИМИЗАЦИЯ СИСТЕМ СВЯЗИ

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

рованный сигнал u(t) операторным выражением u(t) M{a, s(t)}, где s(t) – колебание-переносчик. Преобразование модулированного сигнала на выходе передатчика в наблюдаемое колебание на

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

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

Полная задача оптимизации проектирования системы согласно (14.1) может быть разложена на подзадачи, связанные с оптимизацией на уровне отдельных операторов, входящих в (14.1). В некоторых случаях, когда задана линия связи [12], оператор

z(t) T{u(t), (t)} , описывающий взаимодействие сигнала с помехой, считается неуправляемым, тогда оптимизация осуществляется